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 Decoration NoPrecision = DecorationMax;
  68 const MemorySemanticsMask MemorySemanticsAllMemory =
  69                 (MemorySemanticsMask)(MemorySemanticsSequentiallyConsistentMask |
  70                                       MemorySemanticsUniformMemoryMask |
  71                                       MemorySemanticsSubgroupMemoryMask |
  72                                       MemorySemanticsWorkgroupMemoryMask |
  73                                       MemorySemanticsCrossWorkgroupMemoryMask |
  74                                       MemorySemanticsAtomicCounterMemoryMask |
  75                                       MemorySemanticsImageMemoryMask);
  76
  77 //
  78 // SPIR-V IR instruction.
  79 //
  80
  81 class Instruction {
  82 public:
  83     Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
  84     explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
  85     virtual ~Instruction() {}
  86     void addIdOperand(Id id) { operands.push_back(id); }
  87     void addImmediateOperand(unsigned int immediate) { operands.push_back(immediate); }
  88     void addStringOperand(const char* str)
  89     {
  90         originalString = str;
  91         unsigned int word;
  92         char* wordString = (char*)&word;
  93         char* wordPtr = wordString;
  94         int charCount = 0;
  95         char c;
  96         do {
  97             c = *(str++);
  98             *(wordPtr++) = c;
  99             ++charCount;
 100             if (charCount == 4) {
 101                 addImmediateOperand(word);
 102                 wordPtr = wordString;
 103                 charCount = 0;
 104             }
 105         } while (c != 0);
 106
 107         // deal with partial last word
 108         if (charCount > 0) {
 109             // pad with 0s
 110             for (; charCount < 4; ++charCount)
 111                 *(wordPtr++) = 0;
 112             addImmediateOperand(word);
 113         }
 114     }
 115     void setBlock(Block* b) { block = b; }
 116     Block* getBlock() const { return block; }
 117     Op getOpCode() const { return opCode; }
 118     int getNumOperands() const { return (int)operands.size(); }
 119     Id getResultId() const { return resultId; }
 120     Id getTypeId() const { return typeId; }
 121     Id getIdOperand(int op) const { return operands[op]; }
 122     unsigned int getImmediateOperand(int op) const { return operands[op]; }
 123     const char* getStringOperand() const { return originalString.c_str(); }
 124
 125     // Write out the binary form.
 126     void dump(std::vector<unsigned int>& out) const
 127     {
 128         // Compute the wordCount
 129         unsigned int wordCount = 1;
 130         if (typeId)
 131             ++wordCount;
 132         if (resultId)
 133             ++wordCount;
 134         wordCount += (unsigned int)operands.size();
 135
 136         // Write out the beginning of the instruction
 137         out.push_back(((wordCount) << WordCountShift) | opCode);
 138         if (typeId)
 139             out.push_back(typeId);
 140         if (resultId)
 141             out.push_back(resultId);
 142
 143         // Write out the operands
 144         for (int op = 0; op < (int)operands.size(); ++op)
 145             out.push_back(operands[op]);
 146     }
 147
 148 protected:
 149     Instruction(const Instruction&);
 150     Id resultId;
 151     Id typeId;
 152     Op opCode;
 153     std::vector<Id> operands;
 154     std::string originalString;        // could be optimized away; convenience for getting string operand
 155     Block* block;
 156 };
 157
 158 //
 159 // SPIR-V IR block.
 160 //
 161
 162 class Block {
 163 public:
 164     Block(Id id, Function& parent);
 165     virtual ~Block()
 166     {
 167     }
 168
 169     Id getId() { return instructions.front()->getResultId(); }
 170
 171     Function& getParent() const { return parent; }
 172     void addInstruction(std::unique_ptr<Instruction> inst);
 173     void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
 174     void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
 175     const std::vector<Block*>& getPredecessors() const { return predecessors; }
 176     const std::vector<Block*>& getSuccessors() const { return successors; }
 177     const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
 178         return instructions;
 179     }
 180     void setUnreachable() { unreachable = true; }
 181     bool isUnreachable() const { return unreachable; }
 182     // Returns the block's merge instruction, if one exists (otherwise null).
 183     const Instruction* getMergeInstruction() const {
 184         if (instructions.size() < 2) return nullptr;
 185         const Instruction* nextToLast = (instructions.cend() - 2)->get();
 186         switch (nextToLast->getOpCode()) {
 187             case OpSelectionMerge:
 188             case OpLoopMerge:
 189                 return nextToLast;
 190             default:
 191                 return nullptr;
 192         }
 193         return nullptr;
 194     }
 195
 196     bool isTerminated() const
 197     {
 198         switch (instructions.back()->getOpCode()) {
 199         case OpBranch:
 200         case OpBranchConditional:
 201         case OpSwitch:
 202         case OpKill:
 203         case OpReturn:
 204         case OpReturnValue:
 205             return true;
 206         default:
 207             return false;
 208         }
 209     }
 210
 211     void dump(std::vector<unsigned int>& out) const
 212     {
 213         instructions[0]->dump(out);
 214         for (int i = 0; i < (int)localVariables.size(); ++i)
 215             localVariables[i]->dump(out);
 216         for (int i = 1; i < (int)instructions.size(); ++i)
 217             instructions[i]->dump(out);
 218     }
 219
 220 protected:
 221     Block(const Block&);
 222     Block& operator=(Block&);
 223
 224     // To enforce keeping parent and ownership in sync:
 225     friend Function;
 226
 227     std::vector<std::unique_ptr<Instruction> > instructions;
 228     std::vector<Block*> predecessors, successors;
 229     std::vector<std::unique_ptr<Instruction> > localVariables;
 230     Function& parent;
 231
 232     // track whether this block is known to be uncreachable (not necessarily
 233     // true for all unreachable blocks, but should be set at least
 234     // for the extraneous ones introduced by the builder).
 235     bool unreachable;
 236 };
 237
 238 // Traverses the control-flow graph rooted at root in an order suited for
 239 // readable code generation.  Invokes callback at every node in the traversal
 240 // order.
 241 void inReadableOrder(Block* root, std::function<void(Block*)> callback);
 242
 243 //
 244 // SPIR-V IR Function.
 245 //
 246
 247 class Function {
 248 public:
 249     Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent);
 250     virtual ~Function()
 251     {
 252         for (int i = 0; i < (int)parameterInstructions.size(); ++i)
 253             delete parameterInstructions[i];
 254
 255         for (int i = 0; i < (int)blocks.size(); ++i)
 256             delete blocks[i];
 257     }
 258     Id getId() const { return functionInstruction.getResultId(); }
 259     Id getParamId(int p) { return parameterInstructions[p]->getResultId(); }
 260
 261     void addBlock(Block* block) { blocks.push_back(block); }
 262     void removeBlock(Block* block)
 263     {
 264         auto found = find(blocks.begin(), blocks.end(), block);
 265         assert(found != blocks.end());
 266         blocks.erase(found);
 267         delete block;
 268     }
 269
 270     Module& getParent() const { return parent; }
 271     Block* getEntryBlock() const { return blocks.front(); }
 272     Block* getLastBlock() const { return blocks.back(); }
 273     const std::vector<Block*>& getBlocks() const { return blocks; }
 274     void addLocalVariable(std::unique_ptr<Instruction> inst);
 275     Id getReturnType() const { return functionInstruction.getTypeId(); }
 276     void dump(std::vector<unsigned int>& out) const
 277     {
 278         // OpFunction
 279         functionInstruction.dump(out);
 280
 281         // OpFunctionParameter
 282         for (int p = 0; p < (int)parameterInstructions.size(); ++p)
 283             parameterInstructions[p]->dump(out);
 284
 285         // Blocks
 286         inReadableOrder(blocks[0], [&out](const Block* b) { b->dump(out); });
 287         Instruction end(0, 0, OpFunctionEnd);
 288         end.dump(out);
 289     }
 290
 291 protected:
 292     Function(const Function&);
 293     Function& operator=(Function&);
 294
 295     Module& parent;
 296     Instruction functionInstruction;
 297     std::vector<Instruction*> parameterInstructions;
 298     std::vector<Block*> blocks;
 299 };
 300
 301 //
 302 // SPIR-V IR Module.
 303 //
 304
 305 class Module {
 306 public:
 307     Module() {}
 308     virtual ~Module()
 309     {
 310         // TODO delete things
 311     }
 312
 313     void addFunction(Function *fun) { functions.push_back(fun); }
 314
 315     void mapInstruction(Instruction *instruction)
 316     {
 317         spv::Id resultId = instruction->getResultId();
 318         // map the instruction's result id
 319         if (resultId >= idToInstruction.size())
 320             idToInstruction.resize(resultId + 16);
 321         idToInstruction[resultId] = instruction;
 322     }
 323
 324     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
 325     const std::vector<Function*>& getFunctions() const { return functions; }
 326     spv::Id getTypeId(Id resultId) const { return idToInstruction[resultId]->getTypeId(); }
 327     StorageClass getStorageClass(Id typeId) const
 328     {
 329         assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
 330         return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
 331     }
 332
 333     void dump(std::vector<unsigned int>& out) const
 334     {
 335         for (int f = 0; f < (int)functions.size(); ++f)
 336             functions[f]->dump(out);
 337     }
 338
 339 protected:
 340     Module(const Module&);
 341     std::vector<Function*> functions;
 342
 343     // map from result id to instruction having that result id
 344     std::vector<Instruction*> idToInstruction;
 345
 346     // map from a result id to its type id
 347 };
 348
 349 //
 350 // Implementation (it's here due to circular type definitions).
 351 //
 352
 353 // Add both
 354 // - the OpFunction instruction
 355 // - all the OpFunctionParameter instructions
 356 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
 357     : parent(parent), functionInstruction(id, resultType, OpFunction)
 358 {
 359     // OpFunction
 360     functionInstruction.addImmediateOperand(FunctionControlMaskNone);
 361     functionInstruction.addIdOperand(functionType);
 362     parent.mapInstruction(&functionInstruction);
 363     parent.addFunction(this);
 364
 365     // OpFunctionParameter
 366     Instruction* typeInst = parent.getInstruction(functionType);
 367     int numParams = typeInst->getNumOperands() - 1;
 368     for (int p = 0; p < numParams; ++p) {
 369         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);
 370         parent.mapInstruction(param);
 371         parameterInstructions.push_back(param);
 372     }
 373 }
 374
 375 __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst)
 376 {
 377     Instruction* raw_instruction = inst.get();
 378     blocks[0]->addLocalVariable(std::move(inst));
 379     parent.mapInstruction(raw_instruction);
 380 }
 381
 382 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)
 383 {
 384     instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel)));
 385     instructions.back()->setBlock(this);
 386     parent.getParent().mapInstruction(instructions.back().get());
 387 }
 388
 389 __inline void Block::addInstruction(std::unique_ptr<Instruction> inst)
 390 {
 391     Instruction* raw_instruction = inst.get();
 392     instructions.push_back(std::move(inst));
 393     raw_instruction->setBlock(this);
 394     if (raw_instruction->getResultId())
 395         parent.getParent().mapInstruction(raw_instruction);
 396 }
 397
 398 };  // end spv namespace
 399
 400 #endif // spvIR_H