//
-//Copyright (C) 2014 LunarG, Inc.
+// Copyright (C) 2014 LunarG, Inc.
+// Copyright (C) 2015-2018 Google, Inc.
//
-//All rights reserved.
+// All rights reserved.
//
-//Redistribution and use in source and binary forms, with or without
-//modification, are permitted provided that the following conditions
-//are met:
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions
+// are met:
//
// Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
-//THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-//"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-//LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
-//FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
-//COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
-//INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
-//BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
-//LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
-//CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
-//LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
-//ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
-//POSSIBILITY OF SUCH DAMAGE.
-
-//
-// Author: John Kessenich, LunarG
-//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+// FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+// COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+// BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+// ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+// POSSIBILITY OF SUCH DAMAGE.
// SPIRV-IR
//
// Simple in-memory representation (IR) of SPIRV. Just for holding
// Each function's CFG of blocks. Has this hierarchy:
-// - Module, which is a list of
-// - Function, which is a list of
-// - Block, which is a list of
+// - Module, which is a list of
+// - Function, which is a list of
+// - Block, which is a list of
// - Instruction
//
#include "spirv.hpp"
+#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <memory>
#include <vector>
+#include <set>
namespace spv {
const Id NoResult = 0;
const Id NoType = 0;
-const unsigned int BadValue = 0xFFFFFFFF;
-const Decoration NoPrecision = (Decoration)BadValue;
-const MemorySemanticsMask MemorySemanticsAllMemory = (MemorySemanticsMask)0x3FF;
+const Decoration NoPrecision = DecorationMax;
+
+#ifdef __GNUC__
+# define POTENTIALLY_UNUSED __attribute__((unused))
+#else
+# define POTENTIALLY_UNUSED
+#endif
+
+POTENTIALLY_UNUSED
+const MemorySemanticsMask MemorySemanticsAllMemory =
+ (MemorySemanticsMask)(MemorySemanticsUniformMemoryMask |
+ MemorySemanticsWorkgroupMemoryMask |
+ MemorySemanticsAtomicCounterMemoryMask |
+ MemorySemanticsImageMemoryMask);
+
+struct IdImmediate {
+ bool isId; // true if word is an Id, false if word is an immediate
+ unsigned word;
+ IdImmediate(bool i, unsigned w) : isId(i), word(w) {}
+};
//
// SPIR-V IR instruction.
Instruction(Id resultId, Id typeId, Op opCode) : resultId(resultId), typeId(typeId), opCode(opCode), block(nullptr) { }
explicit Instruction(Op opCode) : resultId(NoResult), typeId(NoType), opCode(opCode), block(nullptr) { }
virtual ~Instruction() {}
- void addIdOperand(Id id) { operands.push_back(id); }
- void addImmediateOperand(unsigned int immediate) { operands.push_back(immediate); }
+ void addIdOperand(Id id) {
+ operands.push_back(id);
+ idOperand.push_back(true);
+ }
+ void addImmediateOperand(unsigned int immediate) {
+ operands.push_back(immediate);
+ idOperand.push_back(false);
+ }
+ void setImmediateOperand(unsigned idx, unsigned int immediate) {
+ assert(!idOperand[idx]);
+ operands[idx] = immediate;
+ }
+
void addStringOperand(const char* str)
{
- originalString = str;
- unsigned int word;
- char* wordString = (char*)&word;
- char* wordPtr = wordString;
- int charCount = 0;
+ unsigned int word = 0;
+ unsigned int shiftAmount = 0;
char c;
+
do {
c = *(str++);
- *(wordPtr++) = c;
- ++charCount;
- if (charCount == 4) {
+ word |= ((unsigned int)c) << shiftAmount;
+ shiftAmount += 8;
+ if (shiftAmount == 32) {
addImmediateOperand(word);
- wordPtr = wordString;
- charCount = 0;
+ word = 0;
+ shiftAmount = 0;
}
} while (c != 0);
// deal with partial last word
- if (charCount > 0) {
- // pad with 0s
- for (; charCount < 4; ++charCount)
- *(wordPtr++) = 0;
+ if (shiftAmount > 0) {
addImmediateOperand(word);
}
}
+ bool isIdOperand(int op) const { return idOperand[op]; }
void setBlock(Block* b) { block = b; }
Block* getBlock() const { return block; }
Op getOpCode() const { return opCode; }
- int getNumOperands() const { return (int)operands.size(); }
+ int getNumOperands() const
+ {
+ assert(operands.size() == idOperand.size());
+ return (int)operands.size();
+ }
Id getResultId() const { return resultId; }
Id getTypeId() const { return typeId; }
- Id getIdOperand(int op) const { return operands[op]; }
- unsigned int getImmediateOperand(int op) const { return operands[op]; }
- const char* getStringOperand() const { return originalString.c_str(); }
+ Id getIdOperand(int op) const {
+ assert(idOperand[op]);
+ return operands[op];
+ }
+ unsigned int getImmediateOperand(int op) const {
+ assert(!idOperand[op]);
+ return operands[op];
+ }
// Write out the binary form.
void dump(std::vector<unsigned int>& out) const
Id resultId;
Id typeId;
Op opCode;
- std::vector<Id> operands;
- std::string originalString; // could be optimized away; convenience for getting string operand
+ std::vector<Id> operands; // operands, both <id> and immediates (both are unsigned int)
+ std::vector<bool> idOperand; // true for operands that are <id>, false for immediates
Block* block;
};
void addLocalVariable(std::unique_ptr<Instruction> inst) { localVariables.push_back(std::move(inst)); }
const std::vector<Block*>& getPredecessors() const { return predecessors; }
const std::vector<Block*>& getSuccessors() const { return successors; }
+ const std::vector<std::unique_ptr<Instruction> >& getInstructions() const {
+ return instructions;
+ }
+ const std::vector<std::unique_ptr<Instruction> >& getLocalVariables() const { return localVariables; }
void setUnreachable() { unreachable = true; }
bool isUnreachable() const { return unreachable; }
// Returns the block's merge instruction, if one exists (otherwise null).
return nullptr;
}
+ // Change this block into a canonical dead merge block. Delete instructions
+ // as necessary. A canonical dead merge block has only an OpLabel and an
+ // OpUnreachable.
+ void rewriteAsCanonicalUnreachableMerge() {
+ assert(localVariables.empty());
+ // Delete all instructions except for the label.
+ assert(instructions.size() > 0);
+ instructions.resize(1);
+ successors.clear();
+ addInstruction(std::unique_ptr<Instruction>(new Instruction(OpUnreachable)));
+ }
+ // Change this block into a canonical dead continue target branching to the
+ // given header ID. Delete instructions as necessary. A canonical dead continue
+ // target has only an OpLabel and an unconditional branch back to the corresponding
+ // header.
+ void rewriteAsCanonicalUnreachableContinue(Block* header) {
+ assert(localVariables.empty());
+ // Delete all instructions except for the label.
+ assert(instructions.size() > 0);
+ instructions.resize(1);
+ successors.clear();
+ // Add OpBranch back to the header.
+ assert(header != nullptr);
+ Instruction* branch = new Instruction(OpBranch);
+ branch->addIdOperand(header->getId());
+ addInstruction(std::unique_ptr<Instruction>(branch));
+ successors.push_back(header);
+ }
+
bool isTerminated() const
{
switch (instructions.back()->getOpCode()) {
case OpBranchConditional:
case OpSwitch:
case OpKill:
+ case OpTerminateInvocation:
case OpReturn:
case OpReturnValue:
+ case OpUnreachable:
return true;
default:
return false;
void dump(std::vector<unsigned int>& out) const
{
- // skip the degenerate unreachable blocks
- // TODO: code gen: skip all unreachable blocks (transitive closure)
- // (but, until that's done safer to keep non-degenerate unreachable blocks, in case others depend on something)
- if (unreachable && instructions.size() <= 2)
- return;
-
instructions[0]->dump(out);
for (int i = 0; i < (int)localVariables.size(); ++i)
localVariables[i]->dump(out);
std::vector<std::unique_ptr<Instruction> > localVariables;
Function& parent;
- // track whether this block is known to be uncreachable (not necessarily
+ // track whether this block is known to be uncreachable (not necessarily
// true for all unreachable blocks, but should be set at least
// for the extraneous ones introduced by the builder).
bool unreachable;
};
+// The different reasons for reaching a block in the inReadableOrder traversal.
+enum ReachReason {
+ // Reachable from the entry block via transfers of control, i.e. branches.
+ ReachViaControlFlow = 0,
+ // A continue target that is not reachable via control flow.
+ ReachDeadContinue,
+ // A merge block that is not reachable via control flow.
+ ReachDeadMerge
+};
+
// Traverses the control-flow graph rooted at root in an order suited for
// readable code generation. Invokes callback at every node in the traversal
-// order.
-void inReadableOrder(Block* root, std::function<void(Block*)> callback);
+// order. The callback arguments are:
+// - the block,
+// - the reason we reached the block,
+// - if the reason was that block is an unreachable continue or unreachable merge block
+// then the last parameter is the corresponding header block.
+void inReadableOrder(Block* root, std::function<void(Block*, ReachReason, Block* header)> callback);
//
// SPIR-V IR Function.
delete blocks[i];
}
Id getId() const { return functionInstruction.getResultId(); }
- Id getParamId(int p) { return parameterInstructions[p]->getResultId(); }
+ Id getParamId(int p) const { return parameterInstructions[p]->getResultId(); }
+ Id getParamType(int p) const { return parameterInstructions[p]->getTypeId(); }
void addBlock(Block* block) { blocks.push_back(block); }
- void popBlock(Block*) { blocks.pop_back(); }
+ void removeBlock(Block* block)
+ {
+ auto found = find(blocks.begin(), blocks.end(), block);
+ assert(found != blocks.end());
+ blocks.erase(found);
+ delete block;
+ }
Module& getParent() const { return parent; }
Block* getEntryBlock() const { return blocks.front(); }
Block* getLastBlock() const { return blocks.back(); }
+ const std::vector<Block*>& getBlocks() const { return blocks; }
void addLocalVariable(std::unique_ptr<Instruction> inst);
Id getReturnType() const { return functionInstruction.getTypeId(); }
+ Id getFuncId() const { return functionInstruction.getResultId(); }
+ void setReturnPrecision(Decoration precision)
+ {
+ if (precision == DecorationRelaxedPrecision)
+ reducedPrecisionReturn = true;
+ }
+ Decoration getReturnPrecision() const
+ { return reducedPrecisionReturn ? DecorationRelaxedPrecision : NoPrecision; }
+
+ void setDebugLineInfo(Id fileName, int line, int column) {
+ lineInstruction = std::unique_ptr<Instruction>{new Instruction(OpLine)};
+ lineInstruction->addIdOperand(fileName);
+ lineInstruction->addImmediateOperand(line);
+ lineInstruction->addImmediateOperand(column);
+ }
+ bool hasDebugLineInfo() const { return lineInstruction != nullptr; }
+
+ void setImplicitThis() { implicitThis = true; }
+ bool hasImplicitThis() const { return implicitThis; }
+
+ void addParamPrecision(unsigned param, Decoration precision)
+ {
+ if (precision == DecorationRelaxedPrecision)
+ reducedPrecisionParams.insert(param);
+ }
+ Decoration getParamPrecision(unsigned param) const
+ {
+ return reducedPrecisionParams.find(param) != reducedPrecisionParams.end() ?
+ DecorationRelaxedPrecision : NoPrecision;
+ }
+
void dump(std::vector<unsigned int>& out) const
{
+ // OpLine
+ if (lineInstruction != nullptr) {
+ lineInstruction->dump(out);
+ }
+
// OpFunction
functionInstruction.dump(out);
parameterInstructions[p]->dump(out);
// Blocks
- inReadableOrder(blocks[0], [&out](const Block* b) { b->dump(out); });
+ inReadableOrder(blocks[0], [&out](const Block* b, ReachReason, Block*) { b->dump(out); });
Instruction end(0, 0, OpFunctionEnd);
end.dump(out);
}
Function& operator=(Function&);
Module& parent;
+ std::unique_ptr<Instruction> lineInstruction;
Instruction functionInstruction;
std::vector<Instruction*> parameterInstructions;
std::vector<Block*> blocks;
+ bool implicitThis; // true if this is a member function expecting to be passed a 'this' as the first argument
+ bool reducedPrecisionReturn;
+ std::set<int> reducedPrecisionParams; // list of parameter indexes that need a relaxed precision arg
};
//
}
Instruction* getInstruction(Id id) const { return idToInstruction[id]; }
- spv::Id getTypeId(Id resultId) const { return idToInstruction[resultId]->getTypeId(); }
+ const std::vector<Function*>& getFunctions() const { return functions; }
+ spv::Id getTypeId(Id resultId) const {
+ return idToInstruction[resultId] == nullptr ? NoType : idToInstruction[resultId]->getTypeId();
+ }
StorageClass getStorageClass(Id typeId) const
{
assert(idToInstruction[typeId]->getOpCode() == spv::OpTypePointer);
// - the OpFunction instruction
// - all the OpFunctionParameter instructions
__inline Function::Function(Id id, Id resultType, Id functionType, Id firstParamId, Module& parent)
- : parent(parent), functionInstruction(id, resultType, OpFunction)
+ : parent(parent), lineInstruction(nullptr),
+ functionInstruction(id, resultType, OpFunction), implicitThis(false),
+ reducedPrecisionReturn(false)
{
// OpFunction
functionInstruction.addImmediateOperand(FunctionControlMaskNone);
parent.getParent().mapInstruction(raw_instruction);
}
-}; // end spv namespace
+} // end spv namespace
#endif // spvIR_H