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:
Instruction(Id resultId,Id typeId,Op opCode)94 Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
Instruction(Op opCode)95 explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
~Instruction()96 virtual ~Instruction() {}
addIdOperand(Id id)97 void addIdOperand(Id id) {
98 operands.push_back(id);
99 idOperand.push_back(true);
100 }
addImmediateOperand(unsigned int immediate)101 void addImmediateOperand(unsigned int immediate) {
102 operands.push_back(immediate);
103 idOperand.push_back(false);
104 }
setImmediateOperand(unsigned idx,unsigned int immediate)105 void setImmediateOperand(unsigned idx, unsigned int immediate) {
106 assert(!idOperand[idx]);
107 operands[idx] = immediate;
108 }
109
addStringOperand(const char * str)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 }
isIdOperand(int op)136 bool isIdOperand(int op) const { return idOperand[op]; }
setBlock(Block * b)137 void setBlock(Block* b) { block = b; }
getBlock()138 Block* getBlock() const { return block; }
getOpCode()139 Op getOpCode() const { return opCode; }
getNumOperands()140 int getNumOperands() const
141 {
142 assert(operands.size() == idOperand.size());
143 return (int)operands.size();
144 }
getResultId()145 Id getResultId() const { return resultId; }
getTypeId()146 Id getTypeId() const { return typeId; }
getIdOperand(int op)147 Id getIdOperand(int op) const {
148 assert(idOperand[op]);
149 return operands[op];
150 }
getImmediateOperand(int op)151 unsigned int getImmediateOperand(int op) const {
152 assert(!idOperand[op]);
153 return operands[op];
154 }
155
156 // Write out the binary form.
dump(std::vector<unsigned int> & out)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);
~Block()196 virtual ~Block()
197 {
198 }
199
getId()200 Id getId() { return instructions.front()->getResultId(); }
201
getParent()202 Function& getParent() const { return parent; }
203 void addInstruction(std::unique_ptr<Instruction> inst);
addPredecessor(Block * pred)204 void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
addLocalVariable(std::unique_ptr<Instruction> inst)205 void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
getPredecessors()206 const std::vector<Block*>& getPredecessors() const { return predecessors; }
getSuccessors()207 const std::vector<Block*>& getSuccessors() const { return successors; }
getInstructions()208 const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
209 return instructions;
210 }
getLocalVariables()211 const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
setUnreachable()212 void setUnreachable() { unreachable = true; }
isUnreachable()213 bool isUnreachable() const { return unreachable; }
214 // Returns the block's merge instruction, if one exists (otherwise null).
getMergeInstruction()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
isTerminated()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
dump(std::vector<unsigned int> & out)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);
~Function()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 }
getId()290 Id getId() const { return functionInstruction.getResultId(); }
getParamId(int p)291 Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
getParamType(int p)292 Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
293
addBlock(Block * block)294 void addBlock(Block* block) { blocks.push_back(block); }
removeBlock(Block * 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
getParent()303 Module& getParent() const { return parent; }
getEntryBlock()304 Block* getEntryBlock() const { return blocks.front(); }
getLastBlock()305 Block* getLastBlock() const { return blocks.back(); }
getBlocks()306 const std::vector<Block*>& getBlocks() const { return blocks; }
307 void addLocalVariable(std::unique_ptr<Instruction> inst);
getReturnType()308 Id getReturnType() const { return functionInstruction.getTypeId(); }
309
setImplicitThis()310 void setImplicitThis() { implicitThis = true; }
hasImplicitThis()311 bool hasImplicitThis() const { return implicitThis; }
312
dump(std::vector<unsigned int> & out)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:
Module()345 Module() {}
~Module()346 virtual ~Module()
347 {
348 // TODO delete things
349 }
350
addFunction(Function * fun)351 void addFunction(Function *fun) { functions.push_back(fun); }
352
mapInstruction(Instruction * instruction)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
getInstruction(Id id)362 Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
getFunctions()363 const std::vector<Function*>& getFunctions() const { return functions; }
getTypeId(Id resultId)364 spv::Id getTypeId(Id resultId) const {
365 return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
366 }
getStorageClass(Id typeId)367 StorageClass getStorageClass(Id typeId) const
368 {
369 assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
370 return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
371 }
372
dump(std::vector<unsigned int> & out)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
Function(Id id,Id resultType,Id functionType,Id firstParamId,Module & parent)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
addLocalVariable(std::unique_ptr<Instruction> inst)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
Block(Id id,Function & parent)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
addInstruction(std::unique_ptr<Instruction> inst)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