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