SPIRV/spvIR.h

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