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 | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 55 | #include <cassert> |
| 56 | #include <functional> |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 57 | #include <iostream> |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 58 | #include <memory> |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 59 | #include <vector> |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 60 | |
| 61 | namespace spv { |
| 62 | |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 63 | class Block; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 64 | class Function; |
| 65 | class Module; |
| 66 | |
| 67 | const Id NoResult = 0; |
| 68 | const Id NoType = 0; |
| 69 | |
| 70 | const unsigned int BadValue = 0xFFFFFFFF; |
| 71 | const Decoration NoPrecision = (Decoration)BadValue; |
| 72 | const MemorySemanticsMask MemorySemanticsAllMemory = (MemorySemanticsMask)0x3FF; |
| 73 | |
| 74 | // |
| 75 | // SPIR-V IR instruction. |
| 76 | // |
| 77 | |
| 78 | class Instruction { |
| 79 | public: |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 80 | Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode) { } |
| 81 | explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode) { } |
| 82 | virtual ~Instruction() {} |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 83 | void addIdOperand(Id id) { operands.push_back(id); } |
| 84 | void addImmediateOperand(unsigned int immediate) { operands.push_back(immediate); } |
| 85 | void addStringOperand(const char* str) |
| 86 | { |
| 87 | originalString = str; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 88 | unsigned int word; |
| 89 | char* wordString = (char*)&word; |
| 90 | char* wordPtr = wordString; |
| 91 | int charCount = 0; |
| 92 | char c; |
| 93 | do { |
| 94 | c = *(str++); |
| 95 | *(wordPtr++) = c; |
| 96 | ++charCount; |
| 97 | if (charCount == 4) { |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 98 | addImmediateOperand(word); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 99 | wordPtr = wordString; |
| 100 | charCount = 0; |
| 101 | } |
| 102 | } while (c != 0); |
| 103 | |
| 104 | // deal with partial last word |
| 105 | if (charCount > 0) { |
| 106 | // pad with 0s |
| 107 | for (; charCount < 4; ++charCount) |
| 108 | *(wordPtr++) = 0; |
John Kessenich | 55e7d11 | 2015-11-15 21:33:39 -0700 | [diff] [blame] | 109 | addImmediateOperand(word); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 110 | } |
| 111 | } |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 112 | void setBlock(Block* b) { block = b; } |
Dejan Mircevski | fa24290 | 2016-01-19 11:31:55 -0500 | [diff] [blame^] | 113 | Block* getBlock() const { return block; } |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 114 | Op getOpCode() const { return opCode; } |
| 115 | int getNumOperands() const { return (int)operands.size(); } |
| 116 | Id getResultId() const { return resultId; } |
| 117 | Id getTypeId() const { return typeId; } |
| 118 | Id getIdOperand(int op) const { return operands[op]; } |
| 119 | unsigned int getImmediateOperand(int op) const { return operands[op]; } |
| 120 | const char* getStringOperand() const { return originalString.c_str(); } |
| 121 | |
| 122 | // Write out the binary form. |
| 123 | void dump(std::vector<unsigned int>& out) const |
| 124 | { |
| 125 | // Compute the wordCount |
| 126 | unsigned int wordCount = 1; |
| 127 | if (typeId) |
| 128 | ++wordCount; |
| 129 | if (resultId) |
| 130 | ++wordCount; |
| 131 | wordCount += (unsigned int)operands.size(); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 132 | |
| 133 | // Write out the beginning of the instruction |
| 134 | out.push_back(((wordCount) << WordCountShift) | opCode); |
| 135 | if (typeId) |
| 136 | out.push_back(typeId); |
| 137 | if (resultId) |
| 138 | out.push_back(resultId); |
| 139 | |
| 140 | // Write out the operands |
| 141 | for (int op = 0; op < (int)operands.size(); ++op) |
| 142 | out.push_back(operands[op]); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 143 | } |
| 144 | |
| 145 | protected: |
| 146 | Instruction(const Instruction&); |
| 147 | Id resultId; |
| 148 | Id typeId; |
| 149 | Op opCode; |
| 150 | std::vector<Id> operands; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 151 | std::string originalString; // could be optimized away; convenience for getting string operand |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 152 | Block* block; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 153 | }; |
| 154 | |
| 155 | // |
| 156 | // SPIR-V IR block. |
| 157 | // |
| 158 | |
| 159 | class Block { |
| 160 | public: |
| 161 | Block(Id id, Function& parent); |
| 162 | virtual ~Block() |
| 163 | { |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 164 | } |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 165 | |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 166 | Id getId() { return instructions.front()->getResultId(); } |
| 167 | |
| 168 | Function& getParent() const { return parent; } |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 169 | void addInstruction(std::unique_ptr<Instruction> inst); |
Dejan Mircevski | 5fe789b | 2016-01-17 23:27:45 -0500 | [diff] [blame] | 170 | void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);} |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 171 | void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); } |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 172 | const std::vector<Block*>& getPredecessors() const { return predecessors; } |
| 173 | const std::vector<Block*>& getSuccessors() const { return successors; } |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 174 | void setUnreachable() { unreachable = true; } |
| 175 | bool isUnreachable() const { return unreachable; } |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 176 | // Returns the block's merge instruction, if one exists (otherwise null). |
| 177 | const Instruction* getMergeInstruction() const { |
| 178 | if (instructions.size() < 2) return nullptr; |
Dejan Mircevski | 377f0ca | 2016-01-19 10:17:33 -0500 | [diff] [blame] | 179 | const Instruction* nextToLast = (instructions.cend() - 2)->get(); |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 180 | switch (nextToLast->getOpCode()) { |
| 181 | case OpSelectionMerge: |
| 182 | case OpLoopMerge: |
| 183 | return nextToLast; |
| 184 | default: |
| 185 | return nullptr; |
| 186 | } |
| 187 | return nullptr; |
| 188 | } |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 189 | |
| 190 | bool isTerminated() const |
| 191 | { |
| 192 | switch (instructions.back()->getOpCode()) { |
| 193 | case OpBranch: |
| 194 | case OpBranchConditional: |
| 195 | case OpSwitch: |
| 196 | case OpKill: |
| 197 | case OpReturn: |
| 198 | case OpReturnValue: |
| 199 | return true; |
| 200 | default: |
| 201 | return false; |
| 202 | } |
| 203 | } |
| 204 | |
| 205 | void dump(std::vector<unsigned int>& out) const |
| 206 | { |
| 207 | // skip the degenerate unreachable blocks |
| 208 | // TODO: code gen: skip all unreachable blocks (transitive closure) |
| 209 | // (but, until that's done safer to keep non-degenerate unreachable blocks, in case others depend on something) |
| 210 | if (unreachable && instructions.size() <= 2) |
| 211 | return; |
| 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 | |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 227 | std::vector<std::unique_ptr<Instruction> > instructions; |
Dejan Mircevski | 5fe789b | 2016-01-17 23:27:45 -0500 | [diff] [blame] | 228 | std::vector<Block*> predecessors, successors; |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 229 | std::vector<std::unique_ptr<Instruction> > localVariables; |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 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 | |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 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 | |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 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 popBlock(Block*) { blocks.pop_back(); } |
| 263 | |
| 264 | Module& getParent() const { return parent; } |
| 265 | Block* getEntryBlock() const { return blocks.front(); } |
| 266 | Block* getLastBlock() const { return blocks.back(); } |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 267 | void addLocalVariable(std::unique_ptr<Instruction> inst); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 268 | Id getReturnType() const { return functionInstruction.getTypeId(); } |
| 269 | void dump(std::vector<unsigned int>& out) const |
| 270 | { |
| 271 | // OpFunction |
| 272 | functionInstruction.dump(out); |
| 273 | |
| 274 | // OpFunctionParameter |
| 275 | for (int p = 0; p < (int)parameterInstructions.size(); ++p) |
| 276 | parameterInstructions[p]->dump(out); |
| 277 | |
| 278 | // Blocks |
Dejan Mircevski | 44bfb0d | 2016-01-18 16:18:37 -0500 | [diff] [blame] | 279 | inReadableOrder(blocks[0], [&out](const Block* b) { b->dump(out); }); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 280 | Instruction end(0, 0, OpFunctionEnd); |
| 281 | end.dump(out); |
| 282 | } |
| 283 | |
| 284 | protected: |
| 285 | Function(const Function&); |
| 286 | Function& operator=(Function&); |
| 287 | |
| 288 | Module& parent; |
| 289 | Instruction functionInstruction; |
| 290 | std::vector<Instruction*> parameterInstructions; |
| 291 | std::vector<Block*> blocks; |
| 292 | }; |
| 293 | |
| 294 | // |
| 295 | // SPIR-V IR Module. |
| 296 | // |
| 297 | |
| 298 | class Module { |
| 299 | public: |
| 300 | Module() {} |
| 301 | virtual ~Module() |
| 302 | { |
| 303 | // TODO delete things |
| 304 | } |
| 305 | |
| 306 | void addFunction(Function *fun) { functions.push_back(fun); } |
| 307 | |
| 308 | void mapInstruction(Instruction *instruction) |
| 309 | { |
| 310 | spv::Id resultId = instruction->getResultId(); |
| 311 | // map the instruction's result id |
| 312 | if (resultId >= idToInstruction.size()) |
| 313 | idToInstruction.resize(resultId + 16); |
| 314 | idToInstruction[resultId] = instruction; |
| 315 | } |
| 316 | |
| 317 | Instruction* getInstruction(Id id) const { return idToInstruction[id]; } |
| 318 | spv::Id getTypeId(Id resultId) const { return idToInstruction[resultId]->getTypeId(); } |
John Kessenich | e00e72d | 2015-12-08 20:48:49 -0700 | [diff] [blame] | 319 | StorageClass getStorageClass(Id typeId) const |
| 320 | { |
| 321 | assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer); |
| 322 | return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0); |
| 323 | } |
| 324 | |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 325 | void dump(std::vector<unsigned int>& out) const |
| 326 | { |
| 327 | for (int f = 0; f < (int)functions.size(); ++f) |
| 328 | functions[f]->dump(out); |
| 329 | } |
| 330 | |
| 331 | protected: |
| 332 | Module(const Module&); |
| 333 | std::vector<Function*> functions; |
| 334 | |
| 335 | // map from result id to instruction having that result id |
| 336 | std::vector<Instruction*> idToInstruction; |
| 337 | |
| 338 | // map from a result id to its type id |
| 339 | }; |
| 340 | |
| 341 | // |
| 342 | // Implementation (it's here due to circular type definitions). |
| 343 | // |
| 344 | |
| 345 | // Add both |
| 346 | // - the OpFunction instruction |
| 347 | // - all the OpFunctionParameter instructions |
| 348 | __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent) |
| 349 | : parent(parent), functionInstruction(id, resultType, OpFunction) |
| 350 | { |
| 351 | // OpFunction |
| 352 | functionInstruction.addImmediateOperand(FunctionControlMaskNone); |
| 353 | functionInstruction.addIdOperand(functionType); |
| 354 | parent.mapInstruction(&functionInstruction); |
| 355 | parent.addFunction(this); |
| 356 | |
| 357 | // OpFunctionParameter |
| 358 | Instruction* typeInst = parent.getInstruction(functionType); |
| 359 | int numParams = typeInst->getNumOperands() - 1; |
| 360 | for (int p = 0; p < numParams; ++p) { |
| 361 | Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter); |
| 362 | parent.mapInstruction(param); |
| 363 | parameterInstructions.push_back(param); |
| 364 | } |
| 365 | } |
| 366 | |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 367 | __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst) |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 368 | { |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 369 | Instruction* raw_instruction = inst.get(); |
| 370 | blocks[0]->addLocalVariable(std::move(inst)); |
| 371 | parent.mapInstruction(raw_instruction); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 372 | } |
| 373 | |
| 374 | __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false) |
| 375 | { |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 376 | instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel))); |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 377 | instructions.back()->setBlock(this); |
Dejan Mircevski | 377f0ca | 2016-01-19 10:17:33 -0500 | [diff] [blame] | 378 | parent.getParent().mapInstruction(instructions.back().get()); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 379 | } |
| 380 | |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 381 | __inline void Block::addInstruction(std::unique_ptr<Instruction> inst) |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 382 | { |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 383 | Instruction* raw_instruction = inst.get(); |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 384 | instructions.push_back(std::move(inst)); |
Dejan Mircevski | 38d039d | 2016-01-19 10:01:27 -0500 | [diff] [blame] | 385 | raw_instruction->setBlock(this); |
Andrew Woloszyn | b7946d1 | 2016-01-18 09:23:56 -0500 | [diff] [blame] | 386 | if (raw_instruction->getResultId()) |
| 387 | parent.getParent().mapInstruction(raw_instruction); |
John Kessenich | 140f3df | 2015-06-26 16:58:36 -0600 | [diff] [blame] | 388 | } |
| 389 | |
| 390 | }; // end spv namespace |
| 391 | |
| 392 | #endif // spvIR_H |