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