SPIRV/spvIR.h

   1 //
   2 // Copyright (C) 2014 LunarG, Inc.
   3 // Copyright (C) 2015-2018 Google, Inc.
   4 //
   5 // All rights reserved.
   6 //
   7 // Redistribution and use in source and binary forms, with or without
   8 // modification, are permitted provided that the following conditions
   9 // are met:
  10 //
  11 //    Redistributions of source code must retain the above copyright
  12 //    notice, this list of conditions and the following disclaimer.
  13 //
  14 //    Redistributions in binary form must reproduce the above
  15 //    copyright notice, this list of conditions and the following
  16 //    disclaimer in the documentation and/or other materials provided
  17 //    with the distribution.
  18 //
  19 //    Neither the name of 3Dlabs Inc. Ltd. nor the names of its
  20 //    contributors may be used to endorse or promote products derived
  21 //    from this software without specific prior written permission.
  22 //
  23 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26 // FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  27 // COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28 // INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29 // BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30 // LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  31 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  33 // ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34 // POSSIBILITY OF SUCH DAMAGE.
  35
  36 // SPIRV-IR
  37 //
  38 // Simple in-memory representation (IR) of SPIRV.  Just for holding
  39 // Each function's CFG of blocks.  Has this hierarchy:
  40 //  - Module, which is a list of
  41 //    - Function, which is a list of
  42 //      - Block, which is a list of
  43 //        - Instruction
  44 //
  45
  46 #pragma once
  47 #ifndef spvIR_H
  48 #define spvIR_H
  49
  50 #include "spirv.hpp"
  51
  52 #include <algorithm>
  53 #include <cassert>
  54 #include <functional>
  55 #include <iostream>
  56 #include <memory>
  57 #include <vector>
  58 #include <set>
  59
  60 namespace spv {
  61
  62 class Block;
  63 class Function;
  64 class Module;
  65
  66 const Id NoResult = 0;
  67 const Id NoType = 0;
  68
  69 const Decoration NoPrecision = DecorationMax;
  70
  71 #ifdef __GNUC__
  72 #   define POTENTIALLY_UNUSED __attribute__((unused))
  73 #else
  74 #   define POTENTIALLY_UNUSED
  75 #endif
  76
  77 POTENTIALLY_UNUSED
  78 const MemorySemanticsMask MemorySemanticsAllMemory =
  79                 (MemorySemanticsMask)(MemorySemanticsUniformMemoryMask |
  80                                       MemorySemanticsWorkgroupMemoryMask |
  81                                       MemorySemanticsAtomicCounterMemoryMask |
  82                                       MemorySemanticsImageMemoryMask);
  83
  84 struct IdImmediate {
  85     bool isId;      // true if word is an Id, false if word is an immediate
  86     unsigned word;
  87     IdImmediate(bool i, unsigned w) : isId(i), word(w) {}
  88 };
  89
  90 //
  91 // SPIR-V IR instruction.
  92 //
  93
  94 class Instruction {
  95 public:
  96     Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
  97     explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
  98     virtual ~Instruction() {}
  99     void addIdOperand(Id id) {
 100         operands.push_back(id);
 101         idOperand.push_back(true);
 102     }
 103     void addImmediateOperand(unsigned int immediate) {
 104         operands.push_back(immediate);
 105         idOperand.push_back(false);
 106     }
 107     void setImmediateOperand(unsigned idx, unsigned int immediate) {
 108         assert(!idOperand[idx]);
 109         operands[idx] = immediate;
 110     }
 111
 112     void addStringOperand(const char* str)
 113     {
 114         unsigned int word = 0;
 115         unsigned int shiftAmount = 0;
 116         char c;
 117
 118         do {
 119             c = *(str++);
 120             word |= ((unsigned int)c) << shiftAmount;
 121             shiftAmount += 8;
 122             if (shiftAmount == 32) {
 123                 addImmediateOperand(word);
 124                 word = 0;
 125                 shiftAmount = 0;
 126             }
 127         } while (c != 0);
 128
 129         // deal with partial last word
 130         if (shiftAmount > 0) {
 131             addImmediateOperand(word);
 132         }
 133     }
 134     bool isIdOperand(int op) const { return idOperand[op]; }
 135     void setBlock(Block* b) { block = b; }
 136     Block* getBlock() const { return block; }
 137     Op getOpCode() const { return opCode; }
 138     int getNumOperands() const
 139     {
 140         assert(operands.size() == idOperand.size());
 141         return (int)operands.size();
 142     }
 143     Id getResultId() const { return resultId; }
 144     Id getTypeId() const { return typeId; }
 145     Id getIdOperand(int op) const {
 146         assert(idOperand[op]);
 147         return operands[op];
 148     }
 149     unsigned int getImmediateOperand(int op) const {
 150         assert(!idOperand[op]);
 151         return operands[op];
 152     }
 153
 154     // Write out the binary form.
 155     void dump(std::vector<unsigned int>& out) const
 156     {
 157         // Compute the wordCount
 158         unsigned int wordCount = 1;
 159         if (typeId)
 160             ++wordCount;
 161         if (resultId)
 162             ++wordCount;
 163         wordCount += (unsigned int)operands.size();
 164
 165         // Write out the beginning of the instruction
 166         out.push_back(((wordCount) << WordCountShift) | opCode);
 167         if (typeId)
 168             out.push_back(typeId);
 169         if (resultId)
 170             out.push_back(resultId);
 171
 172         // Write out the operands
 173         for (int op = 0; op < (int)operands.size(); ++op)
 174             out.push_back(operands[op]);
 175     }
 176
 177 protected:
 178     Instruction(const Instruction&);
 179     Id resultId;
 180     Id typeId;
 181     Op opCode;
 182     std::vector<Id> operands;     // operands, both <id> and immediates (both are unsigned int)
 183     std::vector<bool> idOperand;  // true for operands that are <id>, false for immediates
 184     Block* block;
 185 };
 186
 187 //
 188 // SPIR-V IR block.
 189 //
 190
 191 class Block {
 192 public:
 193     Block(Id id, Function& parent);
 194     virtual ~Block()
 195     {
 196     }
 197
 198     Id getId() { return instructions.front()->getResultId(); }
 199
 200     Function& getParent() const { return parent; }
 201     void addInstruction(std::unique_ptr<Instruction> inst);
 202     void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
 203     void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
 204     const std::vector<Block*>& getPredecessors() const { return predecessors; }
 205     const std::vector<Block*>& getSuccessors() const { return successors; }
 206     const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
 207         return instructions;
 208     }
 209     const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
 210     void setUnreachable() { unreachable = true; }
 211     bool isUnreachable() const { return unreachable; }
 212     // Returns the block's merge instruction, if one exists (otherwise null).
 213     const Instruction* getMergeInstruction() const {
 214         if (instructions.size() < 2) return nullptr;
 215         const Instruction* nextToLast = (instructions.cend() - 2)->get();
 216         switch (nextToLast->getOpCode()) {
 217             case OpSelectionMerge:
 218             case OpLoopMerge:
 219                 return nextToLast;
 220             default:
 221                 return nullptr;
 222         }
 223         return nullptr;
 224     }
 225
 226     // Change this block into a canonical dead merge block.  Delete instructions
 227     // as necessary.  A canonical dead merge block has only an OpLabel and an
 228     // OpUnreachable.
 229     void rewriteAsCanonicalUnreachableMerge() {
 230         assert(localVariables.empty());
 231         // Delete all instructions except for the label.
 232         assert(instructions.size() > 0);
 233         instructions.resize(1);
 234         successors.clear();
 235         addInstruction(std::unique_ptr<Instruction>(new Instruction(OpUnreachable)));
 236     }
 237     // Change this block into a canonical dead continue target branching to the
 238     // given header ID.  Delete instructions as necessary.  A canonical dead continue
 239     // target has only an OpLabel and an unconditional branch back to the corresponding
 240     // header.
 241     void rewriteAsCanonicalUnreachableContinue(Block* header) {
 242         assert(localVariables.empty());
 243         // Delete all instructions except for the label.
 244         assert(instructions.size() > 0);
 245         instructions.resize(1);
 246         successors.clear();
 247         // Add OpBranch back to the header.
 248         assert(header != nullptr);
 249         Instruction* branch = new Instruction(OpBranch);
 250         branch->addIdOperand(header->getId());
 251         addInstruction(std::unique_ptr<Instruction>(branch));
 252         successors.push_back(header);
 253     }
 254
 255     bool isTerminated() const
 256     {
 257         switch (instructions.back()->getOpCode()) {
 258         case OpBranch:
 259         case OpBranchConditional:
 260         case OpSwitch:
 261         case OpKill:
 262         case OpTerminateInvocation:
 263         case OpReturn:
 264         case OpReturnValue:
 265         case OpUnreachable:
 266             return true;
 267         default:
 268             return false;
 269         }
 270     }
 271
 272     void dump(std::vector<unsigned int>& out) const
 273     {
 274         instructions[0]->dump(out);
 275         for (int i = 0; i < (int)localVariables.size(); ++i)
 276             localVariables[i]->dump(out);
 277         for (int i = 1; i < (int)instructions.size(); ++i)
 278             instructions[i]->dump(out);
 279     }
 280
 281 protected:
 282     Block(const Block&);
 283     Block& operator=(Block&);
 284
 285     // To enforce keeping parent and ownership in sync:
 286     friend Function;
 287
 288     std::vector<std::unique_ptr<Instruction> > instructions;
 289     std::vector<Block*> predecessors, successors;
 290     std::vector<std::unique_ptr<Instruction> > localVariables;
 291     Function& parent;
 292
 293     // track whether this block is known to be uncreachable (not necessarily
 294     // true for all unreachable blocks, but should be set at least
 295     // for the extraneous ones introduced by the builder).
 296     bool unreachable;
 297 };
 298
 299 // The different reasons for reaching a block in the inReadableOrder traversal.
 300 enum ReachReason {
 301     // Reachable from the entry block via transfers of control, i.e. branches.
 302     ReachViaControlFlow = 0,
 303     // A continue target that is not reachable via control flow.
 304     ReachDeadContinue,
 305     // A merge block that is not reachable via control flow.
 306     ReachDeadMerge
 307 };
 308
 309 // Traverses the control-flow graph rooted at root in an order suited for
 310 // readable code generation.  Invokes callback at every node in the traversal
 311 // order.  The callback arguments are:
 312 // - the block,
 313 // - the reason we reached the block,
 314 // - if the reason was that block is an unreachable continue or unreachable merge block
 315 //   then the last parameter is the corresponding header block.
 316 void inReadableOrder(Block* root, std::function<void(Block*, ReachReason, Block* header)> callback);
 317
 318 //
 319 // SPIR-V IR Function.
 320 //
 321
 322 class Function {
 323 public:
 324     Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent);
 325     virtual ~Function()
 326     {
 327         for (int i = 0; i < (int)parameterInstructions.size(); ++i)
 328             delete parameterInstructions[i];
 329
 330         for (int i = 0; i < (int)blocks.size(); ++i)
 331             delete blocks[i];
 332     }
 333     Id getId() const { return functionInstruction.getResultId(); }
 334     Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
 335     Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
 336
 337     void addBlock(Block* block) { blocks.push_back(block); }
 338     void removeBlock(Block* block)
 339     {
 340         auto found = find(blocks.begin(), blocks.end(), block);
 341         assert(found != blocks.end());
 342         blocks.erase(found);
 343         delete block;
 344     }
 345
 346     Module& getParent() const { return parent; }
 347     Block* getEntryBlock() const { return blocks.front(); }
 348     Block* getLastBlock() const { return blocks.back(); }
 349     const std::vector<Block*>& getBlocks() const { return blocks; }
 350     void addLocalVariable(std::unique_ptr<Instruction> inst);
 351     Id getReturnType() const { return functionInstruction.getTypeId(); }
 352     void setReturnPrecision(Decoration precision)
 353     {
 354         if (precision == DecorationRelaxedPrecision)
 355             reducedPrecisionReturn = true;
 356     }
 357     Decoration getReturnPrecision() const
 358         { return reducedPrecisionReturn ? DecorationRelaxedPrecision : NoPrecision; }
 359
 360     void setImplicitThis() { implicitThis = true; }
 361     bool hasImplicitThis() const { return implicitThis; }
 362
 363     void addParamPrecision(unsigned param, Decoration precision)
 364     {
 365         if (precision == DecorationRelaxedPrecision)
 366             reducedPrecisionParams.insert(param);
 367     }
 368     Decoration getParamPrecision(unsigned param) const
 369     {
 370         return reducedPrecisionParams.find(param) != reducedPrecisionParams.end() ?
 371             DecorationRelaxedPrecision : NoPrecision;
 372     }
 373
 374     void dump(std::vector<unsigned int>& out) const
 375     {
 376         // OpFunction
 377         functionInstruction.dump(out);
 378
 379         // OpFunctionParameter
 380         for (int p = 0; p < (int)parameterInstructions.size(); ++p)
 381             parameterInstructions[p]->dump(out);
 382
 383         // Blocks
 384         inReadableOrder(blocks[0], [&out](const Block* b, ReachReason, Block*) { b->dump(out); });
 385         Instruction end(0, 0, OpFunctionEnd);
 386         end.dump(out);
 387     }
 388
 389 protected:
 390     Function(const Function&);
 391     Function& operator=(Function&);
 392
 393     Module& parent;
 394     Instruction functionInstruction;
 395     std::vector<Instruction*> parameterInstructions;
 396     std::vector<Block*> blocks;
 397     bool implicitThis;  // true if this is a member function expecting to be passed a 'this' as the first argument
 398     bool reducedPrecisionReturn;
 399     std::set<int> reducedPrecisionParams;  // list of parameter indexes that need a relaxed precision arg
 400 };
 401
 402 //
 403 // SPIR-V IR Module.
 404 //
 405
 406 class Module {
 407 public:
 408     Module() {}
 409     virtual ~Module()
 410     {
 411         // TODO delete things
 412     }
 413
 414     void addFunction(Function *fun) { functions.push_back(fun); }
 415
 416     void mapInstruction(Instruction *instruction)
 417     {
 418         spv::Id resultId = instruction->getResultId();
 419         // map the instruction's result id
 420         if (resultId >= idToInstruction.size())
 421             idToInstruction.resize(resultId + 16);
 422         idToInstruction[resultId] = instruction;
 423     }
 424
 425     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
 426     const std::vector<Function*>& getFunctions() const { return functions; }
 427     spv::Id getTypeId(Id resultId) const {
 428         return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
 429     }
 430     StorageClass getStorageClass(Id typeId) const
 431     {
 432         assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
 433         return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
 434     }
 435
 436     void dump(std::vector<unsigned int>& out) const
 437     {
 438         for (int f = 0; f < (int)functions.size(); ++f)
 439             functions[f]->dump(out);
 440     }
 441
 442 protected:
 443     Module(const Module&);
 444     std::vector<Function*> functions;
 445
 446     // map from result id to instruction having that result id
 447     std::vector<Instruction*> idToInstruction;
 448
 449     // map from a result id to its type id
 450 };
 451
 452 //
 453 // Implementation (it's here due to circular type definitions).
 454 //
 455
 456 // Add both
 457 // - the OpFunction instruction
 458 // - all the OpFunctionParameter instructions
 459 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
 460     : parent(parent), functionInstruction(id, resultType, OpFunction), implicitThis(false),
 461       reducedPrecisionReturn(false)
 462 {
 463     // OpFunction
 464     functionInstruction.addImmediateOperand(FunctionControlMaskNone);
 465     functionInstruction.addIdOperand(functionType);
 466     parent.mapInstruction(&functionInstruction);
 467     parent.addFunction(this);
 468
 469     // OpFunctionParameter
 470     Instruction* typeInst = parent.getInstruction(functionType);
 471     int numParams = typeInst->getNumOperands() - 1;
 472     for (int p = 0; p < numParams; ++p) {
 473         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);
 474         parent.mapInstruction(param);
 475         parameterInstructions.push_back(param);
 476     }
 477 }
 478
 479 __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst)
 480 {
 481     Instruction* raw_instruction = inst.get();
 482     blocks[0]->addLocalVariable(std::move(inst));
 483     parent.mapInstruction(raw_instruction);
 484 }
 485
 486 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)
 487 {
 488     instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel)));
 489     instructions.back()->setBlock(this);
 490     parent.getParent().mapInstruction(instructions.back().get());
 491 }
 492
 493 __inline void Block::addInstruction(std::unique_ptr<Instruction> inst)
 494 {
 495     Instruction* raw_instruction = inst.get();
 496     instructions.push_back(std::move(inst));
 497     raw_instruction->setBlock(this);
 498     if (raw_instruction->getResultId())
 499         parent.getParent().mapInstruction(raw_instruction);
 500 }
 501
 502 }  // end spv namespace
 503
 504 #endif // spvIR_H