Merge pull request #2303 from ben-clayton/limit-public-2
[platform/upstream/glslang.git] / SPIRV / spvIR.h
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 #include <set>
59
60 namespace spv {
61
62 class Block;
63 class Function;
64 class Module;
65
66 const Id NoResult = 0;
67 const Id NoType = 0;
68
69 const Decoration NoPrecision = DecorationMax;
70
71 #ifdef __GNUC__
72 #   define POTENTIALLY_UNUSED __attribute__((unused))
73 #else
74 #   define POTENTIALLY_UNUSED
75 #endif
76
77 POTENTIALLY_UNUSED
78 const MemorySemanticsMask MemorySemanticsAllMemory =
79                 (MemorySemanticsMask)(MemorySemanticsUniformMemoryMask |
80                                       MemorySemanticsWorkgroupMemoryMask |
81                                       MemorySemanticsAtomicCounterMemoryMask |
82                                       MemorySemanticsImageMemoryMask);
83
84 struct IdImmediate {
85     bool isId;      // true if word is an Id, false if word is an immediate
86     unsigned word;
87     IdImmediate(bool i, unsigned w) : isId(i), word(w) {}
88 };
89
90 //
91 // SPIR-V IR instruction.
92 //
93
94 class Instruction {
95 public:
96     Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
97     explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
98     virtual ~Instruction() {}
99     void addIdOperand(Id id) {
100         operands.push_back(id);
101         idOperand.push_back(true);
102     }
103     void addImmediateOperand(unsigned int immediate) {
104         operands.push_back(immediate);
105         idOperand.push_back(false);
106     }
107     void setImmediateOperand(unsigned idx, unsigned int immediate) {
108         assert(!idOperand[idx]);
109         operands[idx] = immediate;
110     }
111
112     void addStringOperand(const char* str)
113     {
114         unsigned int word;
115         char* wordString = (char*)&word;
116         char* wordPtr = wordString;
117         int charCount = 0;
118         char c;
119         do {
120             c = *(str++);
121             *(wordPtr++) = c;
122             ++charCount;
123             if (charCount == 4) {
124                 addImmediateOperand(word);
125                 wordPtr = wordString;
126                 charCount = 0;
127             }
128         } while (c != 0);
129
130         // deal with partial last word
131         if (charCount > 0) {
132             // pad with 0s
133             for (; charCount < 4; ++charCount)
134                 *(wordPtr++) = 0;
135             addImmediateOperand(word);
136         }
137     }
138     bool isIdOperand(int op) const { return idOperand[op]; }
139     void setBlock(Block* b) { block = b; }
140     Block* getBlock() const { return block; }
141     Op getOpCode() const { return opCode; }
142     int getNumOperands() const
143     {
144         assert(operands.size() == idOperand.size());
145         return (int)operands.size();
146     }
147     Id getResultId() const { return resultId; }
148     Id getTypeId() const { return typeId; }
149     Id getIdOperand(int op) const {
150         assert(idOperand[op]);
151         return operands[op];
152     }
153     unsigned int getImmediateOperand(int op) const {
154         assert(!idOperand[op]);
155         return operands[op];
156     }
157
158     // Write out the binary form.
159     void dump(std::vector<unsigned int>& out) const
160     {
161         // Compute the wordCount
162         unsigned int wordCount = 1;
163         if (typeId)
164             ++wordCount;
165         if (resultId)
166             ++wordCount;
167         wordCount += (unsigned int)operands.size();
168
169         // Write out the beginning of the instruction
170         out.push_back(((wordCount) << WordCountShift) | opCode);
171         if (typeId)
172             out.push_back(typeId);
173         if (resultId)
174             out.push_back(resultId);
175
176         // Write out the operands
177         for (int op = 0; op < (int)operands.size(); ++op)
178             out.push_back(operands[op]);
179     }
180
181 protected:
182     Instruction(const Instruction&);
183     Id resultId;
184     Id typeId;
185     Op opCode;
186     std::vector<Id> operands;     // operands, both <id> and immediates (both are unsigned int)
187     std::vector<bool> idOperand;  // true for operands that are <id>, false for immediates
188     Block* block;
189 };
190
191 //
192 // SPIR-V IR block.
193 //
194
195 class Block {
196 public:
197     Block(Id id, Function& parent);
198     virtual ~Block()
199     {
200     }
201
202     Id getId() { return instructions.front()->getResultId(); }
203
204     Function& getParent() const { return parent; }
205     void addInstruction(std::unique_ptr<Instruction> inst);
206     void addPredecessor(Block* pred) { predecessors.push_back(pred); pred->successors.push_back(this);}
207     void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
208     const std::vector<Block*>& getPredecessors() const { return predecessors; }
209     const std::vector<Block*>& getSuccessors() const { return successors; }
210     const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
211         return instructions;
212     }
213     const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
214     void setUnreachable() { unreachable = true; }
215     bool isUnreachable() const { return unreachable; }
216     // Returns the block's merge instruction, if one exists (otherwise null).
217     const Instruction* getMergeInstruction() const {
218         if (instructions.size() < 2) return nullptr;
219         const Instruction* nextToLast = (instructions.cend() - 2)->get();
220         switch (nextToLast->getOpCode()) {
221             case OpSelectionMerge:
222             case OpLoopMerge:
223                 return nextToLast;
224             default:
225                 return nullptr;
226         }
227         return nullptr;
228     }
229
230     // Change this block into a canonical dead merge block.  Delete instructions
231     // as necessary.  A canonical dead merge block has only an OpLabel and an
232     // OpUnreachable.
233     void rewriteAsCanonicalUnreachableMerge() {
234         assert(localVariables.empty());
235         // Delete all instructions except for the label.
236         assert(instructions.size() > 0);
237         instructions.resize(1);
238         successors.clear();
239         addInstruction(std::unique_ptr<Instruction>(new Instruction(OpUnreachable)));
240     }
241     // Change this block into a canonical dead continue target branching to the
242     // given header ID.  Delete instructions as necessary.  A canonical dead continue
243     // target has only an OpLabel and an unconditional branch back to the corresponding
244     // header.
245     void rewriteAsCanonicalUnreachableContinue(Block* header) {
246         assert(localVariables.empty());
247         // Delete all instructions except for the label.
248         assert(instructions.size() > 0);
249         instructions.resize(1);
250         successors.clear();
251         // Add OpBranch back to the header.
252         assert(header != nullptr);
253         Instruction* branch = new Instruction(OpBranch);
254         branch->addIdOperand(header->getId());
255         addInstruction(std::unique_ptr<Instruction>(branch));
256         successors.push_back(header);
257     }
258
259     bool isTerminated() const
260     {
261         switch (instructions.back()->getOpCode()) {
262         case OpBranch:
263         case OpBranchConditional:
264         case OpSwitch:
265         case OpKill:
266         case OpReturn:
267         case OpReturnValue:
268         case OpUnreachable:
269             return true;
270         default:
271             return false;
272         }
273     }
274
275     void dump(std::vector<unsigned int>& out) const
276     {
277         instructions[0]->dump(out);
278         for (int i = 0; i < (int)localVariables.size(); ++i)
279             localVariables[i]->dump(out);
280         for (int i = 1; i < (int)instructions.size(); ++i)
281             instructions[i]->dump(out);
282     }
283
284 protected:
285     Block(const Block&);
286     Block& operator=(Block&);
287
288     // To enforce keeping parent and ownership in sync:
289     friend Function;
290
291     std::vector<std::unique_ptr<Instruction> > instructions;
292     std::vector<Block*> predecessors, successors;
293     std::vector<std::unique_ptr<Instruction> > localVariables;
294     Function& parent;
295
296     // track whether this block is known to be uncreachable (not necessarily
297     // true for all unreachable blocks, but should be set at least
298     // for the extraneous ones introduced by the builder).
299     bool unreachable;
300 };
301
302 // The different reasons for reaching a block in the inReadableOrder traversal.
303 enum ReachReason {
304     // Reachable from the entry block via transfers of control, i.e. branches.
305     ReachViaControlFlow = 0,
306     // A continue target that is not reachable via control flow.
307     ReachDeadContinue,
308     // A merge block that is not reachable via control flow.
309     ReachDeadMerge
310 };
311
312 // Traverses the control-flow graph rooted at root in an order suited for
313 // readable code generation.  Invokes callback at every node in the traversal
314 // order.  The callback arguments are:
315 // - the block,
316 // - the reason we reached the block,
317 // - if the reason was that block is an unreachable continue or unreachable merge block
318 //   then the last parameter is the corresponding header block.
319 void inReadableOrder(Block* root, std::function<void(Block*, ReachReason, Block* header)> callback);
320
321 //
322 // SPIR-V IR Function.
323 //
324
325 class Function {
326 public:
327     Function(Id id, Id resultType, Id functionType, Id firstParam, Module& parent);
328     virtual ~Function()
329     {
330         for (int i = 0; i < (int)parameterInstructions.size(); ++i)
331             delete parameterInstructions[i];
332
333         for (int i = 0; i < (int)blocks.size(); ++i)
334             delete blocks[i];
335     }
336     Id getId() const { return functionInstruction.getResultId(); }
337     Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
338     Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
339
340     void addBlock(Block* block) { blocks.push_back(block); }
341     void removeBlock(Block* block)
342     {
343         auto found = find(blocks.begin(), blocks.end(), block);
344         assert(found != blocks.end());
345         blocks.erase(found);
346         delete block;
347     }
348
349     Module& getParent() const { return parent; }
350     Block* getEntryBlock() const { return blocks.front(); }
351     Block* getLastBlock() const { return blocks.back(); }
352     const std::vector<Block*>& getBlocks() const { return blocks; }
353     void addLocalVariable(std::unique_ptr<Instruction> inst);
354     Id getReturnType() const { return functionInstruction.getTypeId(); }
355     void setReturnPrecision(Decoration precision)
356     {
357         if (precision == DecorationRelaxedPrecision)
358             reducedPrecisionReturn = true;
359     }
360     Decoration getReturnPrecision() const
361         { return reducedPrecisionReturn ? DecorationRelaxedPrecision : NoPrecision; }
362
363     void setImplicitThis() { implicitThis = true; }
364     bool hasImplicitThis() const { return implicitThis; }
365
366     void addParamPrecision(unsigned param, Decoration precision)
367     {
368         if (precision == DecorationRelaxedPrecision)
369             reducedPrecisionParams.insert(param);
370     }
371     Decoration getParamPrecision(unsigned param) const
372     {
373         return reducedPrecisionParams.find(param) != reducedPrecisionParams.end() ?
374             DecorationRelaxedPrecision : NoPrecision;
375     }
376
377     void dump(std::vector<unsigned int>& out) const
378     {
379         // OpFunction
380         functionInstruction.dump(out);
381
382         // OpFunctionParameter
383         for (int p = 0; p < (int)parameterInstructions.size(); ++p)
384             parameterInstructions[p]->dump(out);
385
386         // Blocks
387         inReadableOrder(blocks[0], [&out](const Block* b, ReachReason, Block*) { b->dump(out); });
388         Instruction end(0, 0, OpFunctionEnd);
389         end.dump(out);
390     }
391
392 protected:
393     Function(const Function&);
394     Function& operator=(Function&);
395
396     Module& parent;
397     Instruction functionInstruction;
398     std::vector<Instruction*> parameterInstructions;
399     std::vector<Block*> blocks;
400     bool implicitThis;  // true if this is a member function expecting to be passed a 'this' as the first argument
401     bool reducedPrecisionReturn;
402     std::set<int> reducedPrecisionParams;  // list of parameter indexes that need a relaxed precision arg
403 };
404
405 //
406 // SPIR-V IR Module.
407 //
408
409 class Module {
410 public:
411     Module() {}
412     virtual ~Module()
413     {
414         // TODO delete things
415     }
416
417     void addFunction(Function *fun) { functions.push_back(fun); }
418
419     void mapInstruction(Instruction *instruction)
420     {
421         spv::Id resultId = instruction->getResultId();
422         // map the instruction's result id
423         if (resultId >= idToInstruction.size())
424             idToInstruction.resize(resultId + 16);
425         idToInstruction[resultId] = instruction;
426     }
427
428     Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
429     const std::vector<Function*>& getFunctions() const { return functions; }
430     spv::Id getTypeId(Id resultId) const {
431         return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
432     }
433     StorageClass getStorageClass(Id typeId) const
434     {
435         assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
436         return (StorageClass)idToInstruction[typeId]->getImmediateOperand(0);
437     }
438
439     void dump(std::vector<unsigned int>& out) const
440     {
441         for (int f = 0; f < (int)functions.size(); ++f)
442             functions[f]->dump(out);
443     }
444
445 protected:
446     Module(const Module&);
447     std::vector<Function*> functions;
448
449     // map from result id to instruction having that result id
450     std::vector<Instruction*> idToInstruction;
451
452     // map from a result id to its type id
453 };
454
455 //
456 // Implementation (it's here due to circular type definitions).
457 //
458
459 // Add both
460 // - the OpFunction instruction
461 // - all the OpFunctionParameter instructions
462 __inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
463     : parent(parent), functionInstruction(id, resultType, OpFunction), implicitThis(false),
464       reducedPrecisionReturn(false)
465 {
466     // OpFunction
467     functionInstruction.addImmediateOperand(FunctionControlMaskNone);
468     functionInstruction.addIdOperand(functionType);
469     parent.mapInstruction(&functionInstruction);
470     parent.addFunction(this);
471
472     // OpFunctionParameter
473     Instruction* typeInst = parent.getInstruction(functionType);
474     int numParams = typeInst->getNumOperands() - 1;
475     for (int p = 0; p < numParams; ++p) {
476         Instruction* param = new Instruction(firstParamId + p, typeInst->getIdOperand(p + 1), OpFunctionParameter);
477         parent.mapInstruction(param);
478         parameterInstructions.push_back(param);
479     }
480 }
481
482 __inline void Function::addLocalVariable(std::unique_ptr<Instruction> inst)
483 {
484     Instruction* raw_instruction = inst.get();
485     blocks[0]->addLocalVariable(std::move(inst));
486     parent.mapInstruction(raw_instruction);
487 }
488
489 __inline Block::Block(Id id, Function& parent) : parent(parent), unreachable(false)
490 {
491     instructions.push_back(std::unique_ptr<Instruction>(new Instruction(id, NoType, OpLabel)));
492     instructions.back()->setBlock(this);
493     parent.getParent().mapInstruction(instructions.back().get());
494 }
495
496 __inline void Block::addInstruction(std::unique_ptr<Instruction> inst)
497 {
498     Instruction* raw_instruction = inst.get();
499     instructions.push_back(std::move(inst));
500     raw_instruction->setBlock(this);
501     if (raw_instruction->getResultId())
502         parent.getParent().mapInstruction(raw_instruction);
503 }
504
505 }  // end spv namespace
506
507 #endif // spvIR_H