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