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

source code of qtshadertools/src/3rdparty/glslang/SPIRV/spvIR.h