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