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

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