SPIRV/spvIR.h

   1 //
   2 // Copyright (C) 2014 LunarG, Inc.
   3 // Copyright (C) 2015-2018 Google, Inc.
   4 //
   5 // All rights reserved.
   6 //
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions
   9 // are met:
  10 //
  11 //    Redistributions of source code must retain the above copyright
  12 //    notice, this list of conditions and the following disclaimer.
  13 //
  14 //    Redistributions in binary form must reproduce the above
  15 //    copyright notice, this list of conditions and the following
  16 //    disclaimer in the documentation and/or other materials provided
  17 //    with the distribution.
  18 //
  19 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  20 //    contributors may be used to endorse or promote products derived
  21 //    from this software without specific prior written permission.
  22 //
  23 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  27 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  31 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  33 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34 // POSSIBILITY OF SUCH DAMAGE.
  35
  36 // SPIRV-IR
  37 //
  38 // Simple in-memory representation (IR) of SPIRV.  Just for holding
  39 // Each function's CFG of blocks.  Has this hierarchy:
  40 //  - Module, which is a list of
  41 //    - Function, which is a list of
  42 //      - Block, which is a list of
  43 //        - Instruction
  44 //
  45
  46 #pragma once
  47 #ifndef spvIR_H
  48 #define spvIR_H
  49
  50 #include "spirv.hpp"
  51
  52 #include <algorithm>
  53 #include <cassert>
  54 #include <functional>
  55 #include <iostream>
  56 #include <memory>
  57 #include <vector>
  58
  59 namespace spv {
  60
  61 class Block;
  62 class Function;
  63 class Module;
  64
  65 const Id NoResult = 0;
  66 const Id NoType = 0;
  67
  68 const Decoration NoPrecision = DecorationMax;
  69
  70 #ifdef __GNUC__
  71 #   define POTENTIALLY_UNUSED __attribute__((unused))
  72 #else
  73 #   define POTENTIALLY_UNUSED
  74 #endif
  75
  76 POTENTIALLY_UNUSED
  77 const MemorySemanticsMask MemorySemanticsAllMemory =
  78                 (MemorySemanticsMask)(MemorySemanticsUniformMemoryMask |
  79                                       MemorySemanticsWorkgroupMemoryMask |
  80                                       MemorySemanticsAtomicCounterMemoryMask |
  81                                       MemorySemanticsImageMemoryMask);
  82
  83 struct IdImmediate {
  84     bool isId;      // true if word is an Id, false if word is an immediate
  85     unsigned word;
  86 };
  87
  88 //
  89 // SPIR-V IR instruction.
  90 //
  91
  92 class Instruction {
  93 public:
  94     Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
  95     explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
  96     virtual ~Instruction() {}
  97     void addIdOperand(Id id) {
  98         operands.push_back(id);
  99         idOperand.push_back(true);
 100     }
 101     void addImmediateOperand(unsigned int immediate) {
 102         operands.push_back(immediate);
 103         idOperand.push_back(false);
 104     }
 105     void setImmediateOperand(unsigned idx, unsigned int immediate) {
 106         assert(!idOperand[idx]);
 107         operands[idx] = immediate;
 108     }
 109
 110     void addStringOperand(const char* str)
 111     {
 112         unsigned int word;
 113         char* wordString = (char*)&word;
 114         char* wordPtr = wordString;
 115         int charCount = 0;
 116         char c;
 117         do {
 118             c = *(str++);
 119             *(wordPtr++) = c;
 120             ++charCount;
 121             if (charCount == 4) {
 122                 addImmediateOperand(word);
 123                 wordPtr = wordString;
 124                 charCount = 0;
 125             }
 126         } while (c != 0);
 127
 128         // deal with partial last word
 129         if (charCount > 0) {
 130             // pad with 0s
 131             for (; charCount < 4; ++charCount)
 132                 *(wordPtr++) = 0;
 133             addImmediateOperand(word);
 134         }
 135     }
 136     bool isIdOperand(int op) const { return idOperand[op]; }
 137     void setBlock(Block* b) { block = b; }
 138     Block* getBlock() const { return block; }
 139     Op getOpCode() const { return opCode; }
 140     int getNumOperands() const
 141     {
 142         assert(operands.size() == idOperand.size());
 143         return (int)operands.size();
 144     }
 145     Id getResultId() const { return resultId; }
 146     Id getTypeId() const { return typeId; }
 147     Id getIdOperand(int op) const {
 148         assert(idOperand[op]);
 149         return operands[op];
 150     }
 151     unsigned int getImmediateOperand(int op) const {
 152         assert(!idOperand[op]);
 153         return operands[op];
 154     }
 155
 156     // Write out the binary form.
 157     void dump(std::vector<unsigned int>& out) const
 158     {
 159         // Compute the wordCount
 160         unsigned int wordCount = 1;
 161         if (typeId)
 162             ++wordCount;
 163         if (resultId)
 164             ++wordCount;
 165         wordCount += (unsigned int)operands.size();
 166
 167         // Write out the beginning of the instruction
 168         out.push_back(((wordCount) << WordCountShift) | opCode);
 169         if (typeId)
 170             out.push_back(typeId);
 171         if (resultId)
 172             out.push_back(resultId);
 173
 174         // Write out the operands
 175         for (int op = 0; op < (int)operands.size(); ++op)
 176             out.push_back(operands[op]);
 177     }
 178
 179 protected:
 180     Instruction(const Instruction&);
 181     Id resultId;
 182     Id typeId;
 183     Op opCode;
 184     std::vector<Id> operands;     // operands, both <id> and immediates (both are unsigned int)
 185     std::vector<bool> idOperand;  // true for operands that are <id>, false for immediates
 186     Block* block;
 187 };
 188
 189 //
 190 // SPIR-V IR block.
 191 //
 192
 193 class Block {
 194 public:
 195     Block(Id id, Function& parent);
 196     virtual ~Block()
 197     {
 198     }
 199
 200     Id getId() { return instructions.front()->getResultId(); }
 201
 202     Function& getParent() const { return parent; }
 203     void addInstruction(std::unique_ptr<Instruction> inst);
 204     void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
 205     void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
 206     const std::vector<Block*>& getPredecessors() const { return predecessors; }
 207     const std::vector<Block*>& getSuccessors() const { return successors; }
 208     const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
 209         return instructions;
 210     }
 211     const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
 212     void setUnreachable() { unreachable = true; }
 213     bool isUnreachable() const { return unreachable; }
 214     // Returns the block's merge instruction, if one exists (otherwise null).
 215     const Instruction* getMergeInstruction() const {
 216         if (instructions.size() < 2) return nullptr;
 217         const Instruction* nextToLast = (instructions.cend() - 2)->get();
 218         switch (nextToLast->getOpCode()) {
 219             case OpSelectionMerge:
 220             case OpLoopMerge:
 221                 return nextToLast;
 222             default:
 223                 return nullptr;
 224         }
 225         return nullptr;
 226     }
 227
 228     bool isTerminated() const
 229     {
 230         switch (instructions.back()->getOpCode()) {
 231         case OpBranch:
 232         case OpBranchConditional:
 233         case OpSwitch:
 234         case OpKill:
 235         case OpReturn:
 236         case OpReturnValue:
 237             return true;
 238         default:
 239             return false;
 240         }
 241     }
 242
 243     void dump(std::vector<unsigned int>& out) const
 244     {
 245         instructions[0]->dump(out);
 246         for (int i = 0; i < (int)localVariables.size(); ++i)
 247             localVariables[i]->dump(out);
 248         for (int i = 1; i < (int)instructions.size(); ++i)
 249             instructions[i]->dump(out);
 250     }
 251
 252 protected:
 253     Block(const Block&);
 254     Block& operator=(Block&);
 255
 256     // To enforce keeping parent and ownership in sync:
 257     friend Function;
 258
 259     std::vector<std::unique_ptr<Instruction> > instructions;
 260     std::vector<Block*> predecessors, successors;
 261     std::vector<std::unique_ptr<Instruction> > localVariables;
 262     Function& parent;
 263
 264     // track whether this block is known to be uncreachable (not necessarily
 265     // true for all unreachable blocks, but should be set at least
 266     // for the extraneous ones introduced by the builder).
 267     bool unreachable;
 268 };
 269
 270 // Traverses the control-flow graph rooted at root in an order suited for
 271 // readable code generation.  Invokes callback at every node in the traversal
 272 // order.
 273 void inReadableOrder(Block* root, std::function<void(Block*)> callback);
 274
 275 //
 276 // SPIR-V IR Function.
 277 //
 278
 279 class Function {
 280 public:
 281     Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent);
 282     virtual ~Function()
 283     {
 284         for (int i = 0; i < (int)parameterInstructions.size(); ++i)
 285             delete parameterInstructions[i];
 286
 287         for (int i = 0; i < (int)blocks.size(); ++i)
 288             delete blocks[i];
 289     }
 290     Id getId() const { return functionInstruction.getResultId(); }
 291     Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
 292     Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
 293
 294     void addBlock(Block* block) { blocks.push_back(block); }
 295     void removeBlock(Block* block)
 296     {
 297         auto found = find(blocks.begin(), blocks.end(), block);
 298         assert(found != blocks.end());
 299         blocks.erase(found);
 300         delete block;
 301     }
 302
 303     Module& getParent() const { return parent; }
 304     Block* getEntryBlock() const { return blocks.front(); }
 305     Block* getLastBlock() const { return blocks.back(); }
 306     const std::vector<Block*>& getBlocks() const { return blocks; }
 307     void addLocalVariable(std::unique_ptr<Instruction> inst);
 308     Id getReturnType() const { return functionInstruction.getTypeId(); }
 309
 310     void setImplicitThis() { implicitThis = true; }
 311     bool hasImplicitThis() const { return implicitThis; }
 312
 313     void dump(std::vector<unsigned int>& out) const
 314     {
 315         // OpFunction
 316         functionInstruction.dump(out);
 317
 318         // OpFunctionParameter
 319         for (int p = 0; p < (int)parameterInstructions.size(); ++p)
 320             parameterInstructions[p]->dump(out);
 321
 322         // Blocks
 323         inReadableOrder(blocks[0], [&out](const Block* b) { b->dump(out); });
 324         Instruction end(0, 0, OpFunctionEnd);
 325         end.dump(out);
 326     }
 327
 328 protected:
 329     Function(const Function&);
 330     Function& operator=(Function&);
 331
 332     Module& parent;
 333     Instruction functionInstruction;
 334     std::vector<Instruction*> parameterInstructions;
 335     std::vector<Block*> blocks;
 336     bool implicitThis;  // true if this is a member function expecting to be passed a 'this' as the first argument
 337 };
 338
 339 //
 340 // SPIR-V IR Module.
 341 //
 342
 343 class Module {
 344 public:
 345     Module() {}
 346     virtual ~Module()
 347     {
 348         // TODO delete things
 349     }
 350
 351     void addFunction(Function *fun) { functions.push_back(fun); }
 352
 353     void mapInstruction(Instruction *instruction)
 354     {
 355         spv::Id resultId = instruction->getResultId();
 356         // map the instruction's result id
 357         if (resultId >= idToInstruction.size())
 358             idToInstruction.resize(resultId + 16);
 359         idToInstruction[resultId] = instruction;
 360     }
 361
 362     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
 363     const std::vector<Function*>& getFunctions() const { return functions; }
 364     spv::Id getTypeId(Id resultId) const {
 365         return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
 366     }
 367     StorageClass getStorageClass(Id typeId) const
 368     {
 369         assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
 370         return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
 371     }
 372
 373     void dump(std::vector<unsigned int>& out) const
 374     {
 375         for (int f = 0; f < (int)functions.size(); ++f)
 376             functions[f]->dump(out);
 377     }
 378
 379 protected:
 380     Module(const Module&);
 381     std::vector<Function*> functions;
 382
 383     // map from result id to instruction having that result id
 384     std::vector<Instruction*> idToInstruction;
 385
 386     // map from a result id to its type id
 387 };
 388
 389 //
 390 // Implementation (it's here due to circular type definitions).
 391 //
 392
 393 // Add both
 394 // - the OpFunction instruction
 395 // - all the OpFunctionParameter instructions
 396 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
 397     : parent(parent), functionInstruction(id, resultType, OpFunction), implicitThis(false)
 398 {
 399     // OpFunction
 400     functionInstruction.addImmediateOperand(FunctionControlMaskNone);
 401     functionInstruction.addIdOperand(functionType);
 402     parent.mapInstruction(&functionInstruction);
 403     parent.addFunction(this);
 404
 405     // OpFunctionParameter
 406     Instruction* typeInst = parent.getInstruction(functionType);
 407     int numParams = typeInst->getNumOperands() - 1;
 408     for (int p = 0; p < numParams; ++p) {
 409         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);
 410         parent.mapInstruction(param);
 411         parameterInstructions.push_back(param);
 412     }
 413 }
 414
 415 __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst)
 416 {
 417     Instruction* raw_instruction = inst.get();
 418     blocks[0]->addLocalVariable(std::move(inst));
 419     parent.mapInstruction(raw_instruction);
 420 }
 421
 422 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)
 423 {
 424     instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel)));
 425     instructions.back()->setBlock(this);
 426     parent.getParent().mapInstruction(instructions.back().get());
 427 }
 428
 429 __inline void Block::addInstruction(std::unique_ptr<Instruction> inst)
 430 {
 431     Instruction* raw_instruction = inst.get();
 432     instructions.push_back(std::move(inst));
 433     raw_instruction->setBlock(this);
 434     if (raw_instruction->getResultId())
 435         parent.getParent().mapInstruction(raw_instruction);
 436 }
 437
 438 };  // end spv namespace
 439
 440 #endif // spvIR_H