SPIRV/spvIR.h

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