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