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
  59 namespace spv {
  60
  61 class Block;
  62 class Function;
  63 class Module;
  64
  65 const Id NoResult = 0;
  66 const Id NoType = 0;
  67
  68 const Decoration NoPrecision = DecorationMax;
  69
  70 #ifdef __GNUC__
  71 #   define POTENTIALLY_UNUSED __attribute__((unused))
  72 #else
  73 #   define POTENTIALLY_UNUSED
  74 #endif
  75
  76 POTENTIALLY_UNUSED
  77 const MemorySemanticsMask MemorySemanticsAllMemory =
  78                 (MemorySemanticsMask)(MemorySemanticsUniformMemoryMask |
  79                                       MemorySemanticsWorkgroupMemoryMask |
  80                                       MemorySemanticsAtomicCounterMemoryMask |
  81                                       MemorySemanticsImageMemoryMask);
  82
  83 struct IdImmediate {
  84     bool isId;      // true if word is an Id, false if word is an immediate
  85     unsigned word;
  86     IdImmediate(bool i, unsigned w) : isId(i), word(w) {}
  87 };
  88
  89 //
  90 // SPIR-V IR instruction.
  91 //
  92
  93 class Instruction {
  94 public:
  95     Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
  96     explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
  97     virtual ~Instruction() {}
  98     void addIdOperand(Id id) {
  99         operands.push_back(id);
 100         idOperand.push_back(true);
 101     }
 102     void addImmediateOperand(unsigned int immediate) {
 103         operands.push_back(immediate);
 104         idOperand.push_back(false);
 105     }
 106     void setImmediateOperand(unsigned idx, unsigned int immediate) {
 107         assert(!idOperand[idx]);
 108         operands[idx] = immediate;
 109     }
 110
 111     void addStringOperand(const char* str)
 112     {
 113         unsigned int word;
 114         char* wordString = (char*)&word;
 115         char* wordPtr = wordString;
 116         int charCount = 0;
 117         char c;
 118         do {
 119             c = *(str++);
 120             *(wordPtr++) = c;
 121             ++charCount;
 122             if (charCount == 4) {
 123                 addImmediateOperand(word);
 124                 wordPtr = wordString;
 125                 charCount = 0;
 126             }
 127         } while (c != 0);
 128
 129         // deal with partial last word
 130         if (charCount > 0) {
 131             // pad with 0s
 132             for (; charCount < 4; ++charCount)
 133                 *(wordPtr++) = 0;
 134             addImmediateOperand(word);
 135         }
 136     }
 137     bool isIdOperand(int op) const { return idOperand[op]; }
 138     void setBlock(Block* b) { block = b; }
 139     Block* getBlock() const { return block; }
 140     Op getOpCode() const { return opCode; }
 141     int getNumOperands() const
 142     {
 143         assert(operands.size() == idOperand.size());
 144         return (int)operands.size();
 145     }
 146     Id getResultId() const { return resultId; }
 147     Id getTypeId() const { return typeId; }
 148     Id getIdOperand(int op) const {
 149         assert(idOperand[op]);
 150         return operands[op];
 151     }
 152     unsigned int getImmediateOperand(int op) const {
 153         assert(!idOperand[op]);
 154         return operands[op];
 155     }
 156
 157     // Write out the binary form.
 158     void dump(std::vector<unsigned int>& out) const
 159     {
 160         // Compute the wordCount
 161         unsigned int wordCount = 1;
 162         if (typeId)
 163             ++wordCount;
 164         if (resultId)
 165             ++wordCount;
 166         wordCount += (unsigned int)operands.size();
 167
 168         // Write out the beginning of the instruction
 169         out.push_back(((wordCount) << WordCountShift) | opCode);
 170         if (typeId)
 171             out.push_back(typeId);
 172         if (resultId)
 173             out.push_back(resultId);
 174
 175         // Write out the operands
 176         for (int op = 0; op < (int)operands.size(); ++op)
 177             out.push_back(operands[op]);
 178     }
 179
 180 protected:
 181     Instruction(const Instruction&);
 182     Id resultId;
 183     Id typeId;
 184     Op opCode;
 185     std::vector<Id> operands;     // operands, both <id> and immediates (both are unsigned int)
 186     std::vector<bool> idOperand;  // true for operands that are <id>, false for immediates
 187     Block* block;
 188 };
 189
 190 //
 191 // SPIR-V IR block.
 192 //
 193
 194 class Block {
 195 public:
 196     Block(Id id, Function& parent);
 197     virtual ~Block()
 198     {
 199     }
 200
 201     Id getId() { return instructions.front()->getResultId(); }
 202
 203     Function& getParent() const { return parent; }
 204     void addInstruction(std::unique_ptr<Instruction> inst);
 205     void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
 206     void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
 207     const std::vector<Block*>& getPredecessors() const { return predecessors; }
 208     const std::vector<Block*>& getSuccessors() const { return successors; }
 209     const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
 210         return instructions;
 211     }
 212     const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
 213     void setUnreachable() { unreachable = true; }
 214     bool isUnreachable() const { return unreachable; }
 215     // Returns the block's merge instruction, if one exists (otherwise null).
 216     const Instruction* getMergeInstruction() const {
 217         if (instructions.size() < 2) return nullptr;
 218         const Instruction* nextToLast = (instructions.cend() - 2)->get();
 219         switch (nextToLast->getOpCode()) {
 220             case OpSelectionMerge:
 221             case OpLoopMerge:
 222                 return nextToLast;
 223             default:
 224                 return nullptr;
 225         }
 226         return nullptr;
 227     }
 228
 229     // Change this block into a canonical dead merge block.  Delete instructions
 230     // as necessary.  A canonical dead merge block has only an OpLabel and an
 231     // OpUnreachable.
 232     void rewriteAsCanonicalUnreachableMerge() {
 233         assert(localVariables.empty());
 234         // Delete all instructions except for the label.
 235         assert(instructions.size() > 0);
 236         instructions.resize(1);
 237         successors.clear();
 238         Instruction* unreachable = new Instruction(OpUnreachable);
 239         addInstruction(std::unique_ptr<Instruction>(unreachable));
 240     }
 241     // Change this block into a canonical dead continue target branching to the
 242     // given header ID.  Delete instructions as necessary.  A canonical dead continue
 243     // target has only an OpLabel and an unconditional branch back to the corresponding
 244     // header.
 245     void rewriteAsCanonicalUnreachableContinue(Block* header) {
 246         assert(localVariables.empty());
 247         // Delete all instructions except for the label.
 248         assert(instructions.size() > 0);
 249         instructions.resize(1);
 250         successors.clear();
 251         // Add OpBranch back to the header.
 252         assert(header != nullptr);
 253         Instruction* branch = new Instruction(OpBranch);
 254         branch->addIdOperand(header->getId());
 255         addInstruction(std::move(std::unique_ptr<Instruction>(branch)));
 256         successors.push_back(header);
 257     }
 258
 259     bool isTerminated() const
 260     {
 261         switch (instructions.back()->getOpCode()) {
 262         case OpBranch:
 263         case OpBranchConditional:
 264         case OpSwitch:
 265         case OpKill:
 266         case OpReturn:
 267         case OpReturnValue:
 268         case OpUnreachable:
 269             return true;
 270         default:
 271             return false;
 272         }
 273     }
 274
 275     void dump(std::vector<unsigned int>& out) const
 276     {
 277         instructions[0]->dump(out);
 278         for (int i = 0; i < (int)localVariables.size(); ++i)
 279             localVariables[i]->dump(out);
 280         for (int i = 1; i < (int)instructions.size(); ++i)
 281             instructions[i]->dump(out);
 282     }
 283
 284 protected:
 285     Block(const Block&);
 286     Block& operator=(Block&);
 287
 288     // To enforce keeping parent and ownership in sync:
 289     friend Function;
 290
 291     std::vector<std::unique_ptr<Instruction> > instructions;
 292     std::vector<Block*> predecessors, successors;
 293     std::vector<std::unique_ptr<Instruction> > localVariables;
 294     Function& parent;
 295
 296     // track whether this block is known to be uncreachable (not necessarily
 297     // true for all unreachable blocks, but should be set at least
 298     // for the extraneous ones introduced by the builder).
 299     bool unreachable;
 300 };
 301
 302 // The different reasons for reaching a block in the inReadableOrder traversal.
 303 enum ReachReason {
 304     // Reachable from the entry block via transfers of control, i.e. branches.
 305     ReachViaControlFlow = 0,
 306     // A continue target that is not reachable via control flow.
 307     ReachDeadContinue,
 308     // A merge block that is not reachable via control flow.
 309     ReachDeadMerge
 310 };
 311
 312 // Traverses the control-flow graph rooted at root in an order suited for
 313 // readable code generation.  Invokes callback at every node in the traversal
 314 // order.  The callback arguments are:
 315 // - the block,
 316 // - the reason we reached the block,
 317 // - if the reason was that block is an unreachable continue or unreachable merge block
 318 //   then the last parameter is the corresponding header block.
 319 void inReadableOrder(Block* root, std::function<void(Block*, ReachReason, Block* header)> callback);
 320
 321 //
 322 // SPIR-V IR Function.
 323 //
 324
 325 class Function {
 326 public:
 327     Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent);
 328     virtual ~Function()
 329     {
 330         for (int i = 0; i < (int)parameterInstructions.size(); ++i)
 331             delete parameterInstructions[i];
 332
 333         for (int i = 0; i < (int)blocks.size(); ++i)
 334             delete blocks[i];
 335     }
 336     Id getId() const { return functionInstruction.getResultId(); }
 337     Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
 338     Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
 339
 340     void addBlock(Block* block) { blocks.push_back(block); }
 341     void removeBlock(Block* block)
 342     {
 343         auto found = find(blocks.begin(), blocks.end(), block);
 344         assert(found != blocks.end());
 345         blocks.erase(found);
 346         delete block;
 347     }
 348
 349     Module& getParent() const { return parent; }
 350     Block* getEntryBlock() const { return blocks.front(); }
 351     Block* getLastBlock() const { return blocks.back(); }
 352     const std::vector<Block*>& getBlocks() const { return blocks; }
 353     void addLocalVariable(std::unique_ptr<Instruction> inst);
 354     Id getReturnType() const { return functionInstruction.getTypeId(); }
 355
 356     void setImplicitThis() { implicitThis = true; }
 357     bool hasImplicitThis() const { return implicitThis; }
 358
 359     void dump(std::vector<unsigned int>& out) const
 360     {
 361         // OpFunction
 362         functionInstruction.dump(out);
 363
 364         // OpFunctionParameter
 365         for (int p = 0; p < (int)parameterInstructions.size(); ++p)
 366             parameterInstructions[p]->dump(out);
 367
 368         // Blocks
 369         inReadableOrder(blocks[0], [&out](const Block* b, ReachReason, Block*) { b->dump(out); });
 370         Instruction end(0, 0, OpFunctionEnd);
 371         end.dump(out);
 372     }
 373
 374 protected:
 375     Function(const Function&);
 376     Function& operator=(Function&);
 377
 378     Module& parent;
 379     Instruction functionInstruction;
 380     std::vector<Instruction*> parameterInstructions;
 381     std::vector<Block*> blocks;
 382     bool implicitThis;  // true if this is a member function expecting to be passed a 'this' as the first argument
 383 };
 384
 385 //
 386 // SPIR-V IR Module.
 387 //
 388
 389 class Module {
 390 public:
 391     Module() {}
 392     virtual ~Module()
 393     {
 394         // TODO delete things
 395     }
 396
 397     void addFunction(Function *fun) { functions.push_back(fun); }
 398
 399     void mapInstruction(Instruction *instruction)
 400     {
 401         spv::Id resultId = instruction->getResultId();
 402         // map the instruction's result id
 403         if (resultId >= idToInstruction.size())
 404             idToInstruction.resize(resultId + 16);
 405         idToInstruction[resultId] = instruction;
 406     }
 407
 408     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
 409     const std::vector<Function*>& getFunctions() const { return functions; }
 410     spv::Id getTypeId(Id resultId) const {
 411         return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
 412     }
 413     StorageClass getStorageClass(Id typeId) const
 414     {
 415         assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
 416         return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
 417     }
 418
 419     void dump(std::vector<unsigned int>& out) const
 420     {
 421         for (int f = 0; f < (int)functions.size(); ++f)
 422             functions[f]->dump(out);
 423     }
 424
 425 protected:
 426     Module(const Module&);
 427     std::vector<Function*> functions;
 428
 429     // map from result id to instruction having that result id
 430     std::vector<Instruction*> idToInstruction;
 431
 432     // map from a result id to its type id
 433 };
 434
 435 //
 436 // Implementation (it's here due to circular type definitions).
 437 //
 438
 439 // Add both
 440 // - the OpFunction instruction
 441 // - all the OpFunctionParameter instructions
 442 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
 443     : parent(parent), functionInstruction(id, resultType, OpFunction), implicitThis(false)
 444 {
 445     // OpFunction
 446     functionInstruction.addImmediateOperand(FunctionControlMaskNone);
 447     functionInstruction.addIdOperand(functionType);
 448     parent.mapInstruction(&functionInstruction);
 449     parent.addFunction(this);
 450
 451     // OpFunctionParameter
 452     Instruction* typeInst = parent.getInstruction(functionType);
 453     int numParams = typeInst->getNumOperands() - 1;
 454     for (int p = 0; p < numParams; ++p) {
 455         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);
 456         parent.mapInstruction(param);
 457         parameterInstructions.push_back(param);
 458     }
 459 }
 460
 461 __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst)
 462 {
 463     Instruction* raw_instruction = inst.get();
 464     blocks[0]->addLocalVariable(std::move(inst));
 465     parent.mapInstruction(raw_instruction);
 466 }
 467
 468 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)
 469 {
 470     instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel)));
 471     instructions.back()->setBlock(this);
 472     parent.getParent().mapInstruction(instructions.back().get());
 473 }
 474
 475 __inline void Block::addInstruction(std::unique_ptr<Instruction> inst)
 476 {
 477     Instruction* raw_instruction = inst.get();
 478     instructions.push_back(std::move(inst));
 479     raw_instruction->setBlock(this);
 480     if (raw_instruction->getResultId())
 481         parent.getParent().mapInstruction(raw_instruction);
 482 }
 483
 484 }  // end spv namespace
 485
 486 #endif // spvIR_H