• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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