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 <assert.h>\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         originalString = str;\r
  88         string = new std::vector<unsigned int>;\r
  89         unsigned int word;\r
  90         char* wordString = (char*)&word;\r
  91         char* wordPtr = wordString;\r
  92         int charCount = 0;\r
  93         char c;\r
  94         do {\r
  95             c = *(str++);\r
  96             *(wordPtr++) = c;\r
  97             ++charCount;\r
  98             if (charCount == 4) {\r
  99                 string->push_back(word);\r
 100                 wordPtr = wordString;\r
 101                 charCount = 0;\r
 102             }\r
 103         } while (c != 0);\r
 104 \r
 105         // deal with partial last word\r
 106         if (charCount > 0) {\r
 107             // pad with 0s\r
 108             for (; charCount < 4; ++charCount)\r
 109                 *(wordPtr++) = 0;\r
 110             string->push_back(word);\r
 111         }\r
 112     }\r
 113     Op getOpCode() const { return opCode; }\r
 114     int getNumOperands() const { return (int)operands.size(); }\r
 115     Id getResultId() const { return resultId; }\r
 116     Id getTypeId() const { return typeId; }\r
 117     Id getIdOperand(int op) const { return operands[op]; }\r
 118     unsigned int getImmediateOperand(int op) const { return operands[op]; }\r
 119     const char* getStringOperand() const { return originalString.c_str(); }\r
 120 \r
 121     // Write out the binary form.\r
 122     void dump(std::vector<unsigned int>& out) const\r
 123     {\r
 124         // Compute the wordCount\r
 125         unsigned int wordCount = 1;\r
 126         if (typeId)\r
 127             ++wordCount;\r
 128         if (resultId)\r
 129             ++wordCount;\r
 130         wordCount += (unsigned int)operands.size();\r
 131         if (string)\r
 132             wordCount += (unsigned int)string->size();\r
 133 \r
 134         // Write out the beginning of the instruction\r
 135         out.push_back(((wordCount) << WordCountShift) | opCode);\r
 136         if (typeId)\r
 137             out.push_back(typeId);\r
 138         if (resultId)\r
 139             out.push_back(resultId);\r
 140 \r
 141         // Write out the operands\r
 142         for (int op = 0; op < (int)operands.size(); ++op)\r
 143             out.push_back(operands[op]);\r
 144         if (string)\r
 145             for (int op = 0; op < (int)string->size(); ++op)\r
 146                 out.push_back((*string)[op]);\r
 147     }\r
 148 \r
 149 protected:\r
 150     Instruction(const Instruction&);\r
 151     Id resultId;\r
 152     Id typeId;\r
 153     Op opCode;\r
 154     std::vector<Id> operands;\r
 155     std::vector<unsigned int>* string; // usually non-existent\r
 156     std::string originalString;        // could be optimized away; convenience for getting string operand\r
 157 };\r
 158 \r
 159 //\r
 160 // SPIR-V IR block.\r
 161 //\r
 162 \r
 163 class Block {\r
 164 public:\r
 165     Block(Id id, Function& parent);\r
 166     virtual ~Block()\r
 167     {\r
 168         // TODO: free instructions\r
 169     }\r
 170     \r
 171     Id getId() { return instructions.front()->getResultId(); }\r
 172 \r
 173     Function& getParent() const { return parent; }\r
 174     void addInstruction(Instruction* inst);\r
 175     void addPredecessor(Block* pred) { predecessors.push_back(pred); }\r
 176     void addLocalVariable(Instruction* inst) { localVariables.push_back(inst); }\r
 177     int getNumPredecessors() const { return (int)predecessors.size(); }\r
 178     void setUnreachable() { unreachable = true; }\r
 179     bool isUnreachable() const { return unreachable; }\r
 180 \r
 181     bool isTerminated() const\r
 182     {\r
 183         switch (instructions.back()->getOpCode()) {\r
 184         case OpBranch:\r
 185         case OpBranchConditional:\r
 186         case OpSwitch:\r
 187         case OpKill:\r
 188         case OpReturn:\r
 189         case OpReturnValue:\r
 190             return true;\r
 191         default:\r
 192             return false;\r
 193         }\r
 194     }\r
 195 \r
 196     void dump(std::vector<unsigned int>& out) const\r
 197     {\r
 198         // skip the degenerate unreachable blocks\r
 199         // TODO: code gen: skip all unreachable blocks (transitive closure)\r
 200         //                 (but, until that's done safer to keep non-degenerate unreachable blocks, in case others depend on something)\r
 201         if (unreachable && instructions.size() <= 2)\r
 202             return;\r
 203 \r
 204         instructions[0]->dump(out);\r
 205         for (int i = 0; i < (int)localVariables.size(); ++i)\r
 206             localVariables[i]->dump(out);\r
 207         for (int i = 1; i < (int)instructions.size(); ++i)\r
 208             instructions[i]->dump(out);\r
 209     }\r
 210 \r
 211 protected:\r
 212     Block(const Block&);\r
 213     Block& operator=(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*) { 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     Function& operator=(Function&);\r
 274 \r
 275     Module& parent;\r
 276     Instruction functionInstruction;\r
 277     std::vector<Instruction*> parameterInstructions;\r
 278     std::vector<Block*> blocks;\r
 279 };\r
 280 \r
 281 //\r
 282 // SPIR-V IR Module.\r
 283 //\r
 284 \r
 285 class Module {\r
 286 public:\r
 287     Module() {}\r
 288     virtual ~Module()\r
 289     {\r
 290         // TODO delete things\r
 291     }\r
 292 \r
 293     void addFunction(Function *fun) { functions.push_back(fun); }\r
 294 \r
 295     void mapInstruction(Instruction *instruction)\r
 296     {\r
 297         spv::Id resultId = instruction->getResultId();\r
 298         // map the instruction's result id\r
 299         if (resultId >= idToInstruction.size())\r
 300             idToInstruction.resize(resultId + 16);\r
 301         idToInstruction[resultId] = instruction;\r
 302     }\r
 303 \r
 304     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }\r
 305     spv::Id getTypeId(Id resultId) const { return idToInstruction[resultId]->getTypeId(); }\r
 306     StorageClass getStorageClass(Id typeId) const { return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0); }\r
 307     void dump(std::vector<unsigned int>& out) const\r
 308     {\r
 309         for (int f = 0; f < (int)functions.size(); ++f)\r
 310             functions[f]->dump(out);\r
 311     }\r
 312 \r
 313 protected:\r
 314     Module(const Module&);\r
 315     std::vector<Function*> functions;\r
 316 \r
 317     // map from result id to instruction having that result id\r
 318     std::vector<Instruction*> idToInstruction;\r
 319 \r
 320     // map from a result id to its type id\r
 321 };\r
 322 \r
 323 //\r
 324 // Implementation (it's here due to circular type definitions).\r
 325 //\r
 326 \r
 327 // Add both\r
 328 // - the OpFunction instruction\r
 329 // - all the OpFunctionParameter instructions\r
 330 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)\r
 331     : parent(parent), functionInstruction(id, resultType, OpFunction)\r
 332 {\r
 333     // OpFunction\r
 334     functionInstruction.addImmediateOperand(FunctionControlMaskNone);\r
 335     functionInstruction.addIdOperand(functionType);\r
 336     parent.mapInstruction(&functionInstruction);\r
 337     parent.addFunction(this);\r
 338 \r
 339     // OpFunctionParameter\r
 340     Instruction* typeInst = parent.getInstruction(functionType);\r
 341     int numParams = typeInst->getNumOperands() - 1;\r
 342     for (int p = 0; p < numParams; ++p) {\r
 343         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);\r
 344         parent.mapInstruction(param);\r
 345         parameterInstructions.push_back(param);\r
 346     }\r
 347 }\r
 348 \r
 349 __inline void Function::addLocalVariable(Instruction* inst)\r
 350 {\r
 351     blocks[0]->addLocalVariable(inst);\r
 352     parent.mapInstruction(inst);\r
 353 }\r
 354 \r
 355 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)\r
 356 {\r
 357     instructions.push_back(new Instruction(id, NoType, OpLabel));\r
 358 }\r
 359 \r
 360 __inline void Block::addInstruction(Instruction* inst)\r
 361 {\r
 362     instructions.push_back(inst);\r
 363     if (inst->getResultId())\r
 364         parent.getParent().mapInstruction(inst);\r
 365 }\r
 366 \r
 367 };  // end spv namespace\r
 368 \r
 369 #endif // spvIR_H\r