John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 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 | // |
| 36 | // Author: John Kessenich, LunarG |
| 37 | // |
| 38 | |
| 39 | // SPIRV-IR |
| 40 | // |
| 41 | // Simple in-memory representation (IR) of SPIRV. Just for holding |
| 42 | // Each function's CFG of blocks. Has this hierarchy: |
| 43 | // - Module, which is a list of |
| 44 | // - Function, which is a list of |
| 45 | // - Block, which is a list of |
| 46 | // - Instruction |
| 47 | // |
| 48 | |
| 49 | #pragma once |
| 50 | #ifndef spvIR_H |
| 51 | #define spvIR_H |
| 52 | |
John Kessenich | 5e4b124 | 2015-08-06 22:53:06 -0600 | [diff] [blame] | 53 | #include "spirv.hpp" |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 54 | |
Dejan Mircevski | e537b8b | 2016-01-10 19:37:00 -0500 | [diff] [blame^] | 55 | #include <algorithm> |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 56 | #include <vector> |
| 57 | #include <iostream> |
| 58 | #include <assert.h> |
| 59 | |
| 60 | namespace spv { |
| 61 | |
| 62 | class Function; |
| 63 | class Module; |
| 64 | |
| 65 | const Id NoResult = 0; |
| 66 | const Id NoType = 0; |
| 67 | |
| 68 | const unsigned int BadValue = 0xFFFFFFFF; |
| 69 | const Decoration NoPrecision = (Decoration)BadValue; |
| 70 | const MemorySemanticsMask MemorySemanticsAllMemory = (MemorySemanticsMask)0x3FF; |
| 71 | |
| 72 | // |
| 73 | // SPIR-V IR instruction. |
| 74 | // |
| 75 | |
| 76 | class Instruction { |
| 77 | public: |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 78 | Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode) { } |
| 79 | explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode) { } |
| 80 | virtual ~Instruction() {} |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 81 | void addIdOperand(Id id) { operands.push_back(id); } |
| 82 | void addImmediateOperand(unsigned int immediate) { operands.push_back(immediate); } |
| 83 | void addStringOperand(const char* str) |
| 84 | { |
| 85 | originalString = str; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 86 | unsigned int word; |
| 87 | char* wordString = (char*)&word; |
| 88 | char* wordPtr = wordString; |
| 89 | int charCount = 0; |
| 90 | char c; |
| 91 | do { |
| 92 | c = *(str++); |
| 93 | *(wordPtr++) = c; |
| 94 | ++charCount; |
| 95 | if (charCount == 4) { |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 96 | addImmediateOperand(word); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 97 | wordPtr = wordString; |
| 98 | charCount = 0; |
| 99 | } |
| 100 | } while (c != 0); |
| 101 | |
| 102 | // deal with partial last word |
| 103 | if (charCount > 0) { |
| 104 | // pad with 0s |
| 105 | for (; charCount < 4; ++charCount) |
| 106 | *(wordPtr++) = 0; |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 107 | addImmediateOperand(word); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 108 | } |
| 109 | } |
| 110 | Op getOpCode() const { return opCode; } |
| 111 | int getNumOperands() const { return (int)operands.size(); } |
| 112 | Id getResultId() const { return resultId; } |
| 113 | Id getTypeId() const { return typeId; } |
| 114 | Id getIdOperand(int op) const { return operands[op]; } |
| 115 | unsigned int getImmediateOperand(int op) const { return operands[op]; } |
| 116 | const char* getStringOperand() const { return originalString.c_str(); } |
| 117 | |
| 118 | // Write out the binary form. |
| 119 | void dump(std::vector<unsigned int>& out) const |
| 120 | { |
| 121 | // Compute the wordCount |
| 122 | unsigned int wordCount = 1; |
| 123 | if (typeId) |
| 124 | ++wordCount; |
| 125 | if (resultId) |
| 126 | ++wordCount; |
| 127 | wordCount += (unsigned int)operands.size(); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 128 | |
| 129 | // Write out the beginning of the instruction |
| 130 | out.push_back(((wordCount) << WordCountShift) | opCode); |
| 131 | if (typeId) |
| 132 | out.push_back(typeId); |
| 133 | if (resultId) |
| 134 | out.push_back(resultId); |
| 135 | |
| 136 | // Write out the operands |
| 137 | for (int op = 0; op < (int)operands.size(); ++op) |
| 138 | out.push_back(operands[op]); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 139 | } |
| 140 | |
| 141 | protected: |
| 142 | Instruction(const Instruction&); |
| 143 | Id resultId; |
| 144 | Id typeId; |
| 145 | Op opCode; |
| 146 | std::vector<Id> operands; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 147 | std::string originalString; // could be optimized away; convenience for getting string operand |
| 148 | }; |
| 149 | |
| 150 | // |
| 151 | // SPIR-V IR block. |
| 152 | // |
| 153 | |
| 154 | class Block { |
| 155 | public: |
| 156 | Block(Id id, Function& parent); |
| 157 | virtual ~Block() |
| 158 | { |
| 159 | // TODO: free instructions |
| 160 | } |
| 161 | |
| 162 | Id getId() { return instructions.front()->getResultId(); } |
| 163 | |
| 164 | Function& getParent() const { return parent; } |
| 165 | void addInstruction(Instruction* inst); |
| 166 | void addPredecessor(Block* pred) { predecessors.push_back(pred); } |
| 167 | void addLocalVariable(Instruction* inst) { localVariables.push_back(inst); } |
| 168 | int getNumPredecessors() const { return (int)predecessors.size(); } |
| 169 | void setUnreachable() { unreachable = true; } |
| 170 | bool isUnreachable() const { return unreachable; } |
| 171 | |
| 172 | bool isTerminated() const |
| 173 | { |
| 174 | switch (instructions.back()->getOpCode()) { |
| 175 | case OpBranch: |
| 176 | case OpBranchConditional: |
| 177 | case OpSwitch: |
| 178 | case OpKill: |
| 179 | case OpReturn: |
| 180 | case OpReturnValue: |
| 181 | return true; |
| 182 | default: |
| 183 | return false; |
| 184 | } |
| 185 | } |
| 186 | |
| 187 | void dump(std::vector<unsigned int>& out) const |
| 188 | { |
| 189 | // skip the degenerate unreachable blocks |
| 190 | // TODO: code gen: skip all unreachable blocks (transitive closure) |
| 191 | // (but, until that's done safer to keep non-degenerate unreachable blocks, in case others depend on something) |
| 192 | if (unreachable && instructions.size() <= 2) |
| 193 | return; |
| 194 | |
| 195 | instructions[0]->dump(out); |
| 196 | for (int i = 0; i < (int)localVariables.size(); ++i) |
| 197 | localVariables[i]->dump(out); |
| 198 | for (int i = 1; i < (int)instructions.size(); ++i) |
| 199 | instructions[i]->dump(out); |
| 200 | } |
| 201 | |
| 202 | protected: |
| 203 | Block(const Block&); |
| 204 | Block& operator=(Block&); |
| 205 | |
| 206 | // To enforce keeping parent and ownership in sync: |
| 207 | friend Function; |
| 208 | |
| 209 | std::vector<Instruction*> instructions; |
| 210 | std::vector<Block*> predecessors; |
| 211 | std::vector<Instruction*> localVariables; |
| 212 | Function& parent; |
| 213 | |
| 214 | // track whether this block is known to be uncreachable (not necessarily |
| 215 | // true for all unreachable blocks, but should be set at least |
| 216 | // for the extraneous ones introduced by the builder). |
| 217 | bool unreachable; |
| 218 | }; |
| 219 | |
| 220 | // |
| 221 | // SPIR-V IR Function. |
| 222 | // |
| 223 | |
| 224 | class Function { |
| 225 | public: |
| 226 | Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent); |
| 227 | virtual ~Function() |
| 228 | { |
| 229 | for (int i = 0; i < (int)parameterInstructions.size(); ++i) |
| 230 | delete parameterInstructions[i]; |
| 231 | |
| 232 | for (int i = 0; i < (int)blocks.size(); ++i) |
| 233 | delete blocks[i]; |
| 234 | } |
| 235 | Id getId() const { return functionInstruction.getResultId(); } |
| 236 | Id getParamId(int p) { return parameterInstructions[p]->getResultId(); } |
| 237 | |
| 238 | void addBlock(Block* block) { blocks.push_back(block); } |
Dejan Mircevski | e537b8b | 2016-01-10 19:37:00 -0500 | [diff] [blame^] | 239 | void removeBlock(Block* block) |
| 240 | { |
| 241 | auto found = find(blocks.begin(), blocks.end(), block); |
| 242 | assert(found != blocks.end()); |
| 243 | blocks.erase(found); |
| 244 | delete block; |
| 245 | } |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 246 | |
| 247 | Module& getParent() const { return parent; } |
| 248 | Block* getEntryBlock() const { return blocks.front(); } |
| 249 | Block* getLastBlock() const { return blocks.back(); } |
| 250 | void addLocalVariable(Instruction* inst); |
| 251 | Id getReturnType() const { return functionInstruction.getTypeId(); } |
| 252 | void dump(std::vector<unsigned int>& out) const |
| 253 | { |
| 254 | // OpFunction |
| 255 | functionInstruction.dump(out); |
| 256 | |
| 257 | // OpFunctionParameter |
| 258 | for (int p = 0; p < (int)parameterInstructions.size(); ++p) |
| 259 | parameterInstructions[p]->dump(out); |
| 260 | |
| 261 | // Blocks |
| 262 | for (int b = 0; b < (int)blocks.size(); ++b) |
| 263 | blocks[b]->dump(out); |
| 264 | Instruction end(0, 0, OpFunctionEnd); |
| 265 | end.dump(out); |
| 266 | } |
| 267 | |
| 268 | protected: |
| 269 | Function(const Function&); |
| 270 | Function& operator=(Function&); |
| 271 | |
| 272 | Module& parent; |
| 273 | Instruction functionInstruction; |
| 274 | std::vector<Instruction*> parameterInstructions; |
| 275 | std::vector<Block*> blocks; |
| 276 | }; |
| 277 | |
| 278 | // |
| 279 | // SPIR-V IR Module. |
| 280 | // |
| 281 | |
| 282 | class Module { |
| 283 | public: |
| 284 | Module() {} |
| 285 | virtual ~Module() |
| 286 | { |
| 287 | // TODO delete things |
| 288 | } |
| 289 | |
| 290 | void addFunction(Function *fun) { functions.push_back(fun); } |
| 291 | |
| 292 | void mapInstruction(Instruction *instruction) |
| 293 | { |
| 294 | spv::Id resultId = instruction->getResultId(); |
| 295 | // map the instruction's result id |
| 296 | if (resultId >= idToInstruction.size()) |
| 297 | idToInstruction.resize(resultId + 16); |
| 298 | idToInstruction[resultId] = instruction; |
| 299 | } |
| 300 | |
| 301 | Instruction* getInstruction(Id id) const { return idToInstruction[id]; } |
| 302 | spv::Id getTypeId(Id resultId) const { return idToInstruction[resultId]->getTypeId(); } |
| 303 | StorageClass getStorageClass(Id typeId) const { return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0); } |
| 304 | void dump(std::vector<unsigned int>& out) const |
| 305 | { |
| 306 | for (int f = 0; f < (int)functions.size(); ++f) |
| 307 | functions[f]->dump(out); |
| 308 | } |
| 309 | |
| 310 | protected: |
| 311 | Module(const Module&); |
| 312 | std::vector<Function*> functions; |
| 313 | |
| 314 | // map from result id to instruction having that result id |
| 315 | std::vector<Instruction*> idToInstruction; |
| 316 | |
| 317 | // map from a result id to its type id |
| 318 | }; |
| 319 | |
| 320 | // |
| 321 | // Implementation (it's here due to circular type definitions). |
| 322 | // |
| 323 | |
| 324 | // Add both |
| 325 | // - the OpFunction instruction |
| 326 | // - all the OpFunctionParameter instructions |
| 327 | __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent) |
| 328 | : parent(parent), functionInstruction(id, resultType, OpFunction) |
| 329 | { |
| 330 | // OpFunction |
| 331 | functionInstruction.addImmediateOperand(FunctionControlMaskNone); |
| 332 | functionInstruction.addIdOperand(functionType); |
| 333 | parent.mapInstruction(&functionInstruction); |
| 334 | parent.addFunction(this); |
| 335 | |
| 336 | // OpFunctionParameter |
| 337 | Instruction* typeInst = parent.getInstruction(functionType); |
| 338 | int numParams = typeInst->getNumOperands() - 1; |
| 339 | for (int p = 0; p < numParams; ++p) { |
| 340 | Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter); |
| 341 | parent.mapInstruction(param); |
| 342 | parameterInstructions.push_back(param); |
| 343 | } |
| 344 | } |
| 345 | |
| 346 | __inline void Function::addLocalVariable(Instruction* inst) |
| 347 | { |
| 348 | blocks[0]->addLocalVariable(inst); |
| 349 | parent.mapInstruction(inst); |
| 350 | } |
| 351 | |
| 352 | __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false) |
| 353 | { |
| 354 | instructions.push_back(new Instruction(id, NoType, OpLabel)); |
| 355 | } |
| 356 | |
| 357 | __inline void Block::addInstruction(Instruction* inst) |
| 358 | { |
| 359 | instructions.push_back(inst); |
| 360 | if (inst->getResultId()) |
| 361 | parent.getParent().mapInstruction(inst); |
| 362 | } |
| 363 | |
| 364 | }; // end spv namespace |
| 365 | |
| 366 | #endif // spvIR_H |