SpirvShader: Add flow control info to Block.
Bug: b/128527271
Change-Id: Ib66c32ba66bcb322be6fa72f01f6c8b1b4b90f0a
Reviewed-on: https://swiftshader-review.googlesource.com/c/SwiftShader/+/27768
Presubmit-Ready: Ben Clayton <bclayton@google.com>
Tested-by: Ben Clayton <bclayton@google.com>
Reviewed-by: Nicolas Capens <nicolascapens@google.com>
Kokoro-Presubmit: kokoro <noreply+kokoro@google.com>
diff --git a/src/Pipeline/SpirvShader.cpp b/src/Pipeline/SpirvShader.cpp
index afd397d..7d89221 100644
--- a/src/Pipeline/SpirvShader.cpp
+++ b/src/Pipeline/SpirvShader.cpp
@@ -440,6 +440,20 @@
UNIMPLEMENTED("%s", OpcodeName(insn.opcode()).c_str());
}
}
+
+ // Assign all Block::ins
+ for (auto &it : blocks)
+ {
+ auto &blockId = it.first;
+ auto &block = it.second;
+ for (auto &outId : block.outs)
+ {
+ auto outIt = blocks.find(outId);
+ ASSERT_MSG(outIt != blocks.end(), "Block %d has a non-existent out %d", blockId.value(), outId.value());
+ auto &out = outIt->second;
+ out.ins.emplace(blockId);
+ }
+ }
}
void SpirvShader::DeclareType(InsnIterator insn)
@@ -2513,6 +2527,92 @@
}
}
+ SpirvShader::Block::Block(InsnIterator begin, InsnIterator end) : begin_(begin), end_(end)
+ {
+ // Default to a Simple, this may change later.
+ kind = Block::Simple;
+
+ // Walk the instructions to find the last two of the block.
+ InsnIterator insns[2];
+ for (auto insn : *this)
+ {
+ insns[0] = insns[1];
+ insns[1] = insn;
+ }
+
+ switch (insns[1].opcode())
+ {
+ case spv::OpBranch:
+ branchInstruction = insns[1];
+ outs.emplace(Block::ID(branchInstruction.word(1)));
+
+ switch (insns[0].opcode())
+ {
+ case spv::OpLoopMerge:
+ kind = Loop;
+ mergeInstruction = insns[0];
+ mergeBlock = Block::ID(mergeInstruction.word(1));
+ continueTarget = Block::ID(mergeInstruction.word(2));
+ break;
+
+ default:
+ kind = Block::Simple;
+ break;
+ }
+ break;
+
+ case spv::OpBranchConditional:
+ branchInstruction = insns[1];
+ outs.emplace(Block::ID(branchInstruction.word(2)));
+ outs.emplace(Block::ID(branchInstruction.word(3)));
+
+ switch (insns[0].opcode())
+ {
+ case spv::OpSelectionMerge:
+ kind = StructuredBranchConditional;
+ mergeInstruction = insns[0];
+ mergeBlock = Block::ID(mergeInstruction.word(1));
+ break;
+
+ case spv::OpLoopMerge:
+ kind = Loop;
+ mergeInstruction = insns[0];
+ mergeBlock = Block::ID(mergeInstruction.word(1));
+ continueTarget = Block::ID(mergeInstruction.word(2));
+ break;
+
+ default:
+ kind = UnstructuredBranchConditional;
+ break;
+ }
+ break;
+
+ case spv::OpSwitch:
+ branchInstruction = insns[1];
+ outs.emplace(Block::ID(branchInstruction.word(2)));
+ for (uint32_t w = 4; w < branchInstruction.wordCount(); w += 2)
+ {
+ outs.emplace(Block::ID(branchInstruction.word(w)));
+ }
+
+ switch (insns[0].opcode())
+ {
+ case spv::OpSelectionMerge:
+ kind = StructuredSwitch;
+ mergeInstruction = insns[0];
+ mergeBlock = Block::ID(mergeInstruction.word(1));
+ break;
+
+ default:
+ kind = UnstructuredSwitch;
+ break;
+ }
+ break;
+
+ default:
+ break;
+ }
+ }
SpirvRoutine::SpirvRoutine(vk::PipelineLayout const *pipelineLayout) :
pipelineLayout(pipelineLayout)
{
diff --git a/src/Pipeline/SpirvShader.hpp b/src/Pipeline/SpirvShader.hpp
index 84f817b..927babb 100644
--- a/src/Pipeline/SpirvShader.hpp
+++ b/src/Pipeline/SpirvShader.hpp
@@ -29,6 +29,7 @@
#include <functional>
#include <string>
#include <vector>
+#include <unordered_set>
#include <unordered_map>
#include <cstdint>
#include <type_traits>
@@ -246,15 +247,51 @@
{
public:
using ID = SpirvID<Block>;
+ using Set = std::unordered_set<ID>;
+
+ // Edge represents the graph edge between two blocks.
+ struct Edge
+ {
+ ID from;
+ ID to;
+
+ bool operator == (const Edge& other) const { return from == other.from && to == other.to; }
+
+ struct Hash
+ {
+ std::size_t operator()(const Edge& edge) const noexcept
+ {
+ return std::hash<uint32_t>()(edge.from.value() * 31 + edge.to.value());
+ }
+ };
+ };
Block() = default;
Block(const Block& other) = default;
- explicit Block(InsnIterator begin, InsnIterator end) : begin_(begin), end_(end) {}
+ explicit Block(InsnIterator begin, InsnIterator end);
/* range-based-for interface */
inline InsnIterator begin() const { return begin_; }
inline InsnIterator end() const { return end_; }
+ enum Kind
+ {
+ Simple, // OpBranch or other simple terminator.
+ StructuredBranchConditional, // OpSelectionMerge + OpBranchConditional
+ UnstructuredBranchConditional, // OpBranchConditional
+ StructuredSwitch, // OpSelectionMerge + OpSwitch
+ UnstructuredSwitch, // OpSwitch
+ Loop, // OpLoopMerge + [OpBranchConditional | OpBranch]
+ };
+
+ Kind kind;
+ InsnIterator mergeInstruction; // Merge instruction.
+ InsnIterator branchInstruction; //
+ ID mergeBlock; // Structured flow merge block.
+ ID continueTarget; // Loop continue block.
+ Set ins; // Blocks that branch into this block.
+ Set outs; // Blocks that this block branches to.
+
private:
InsnIterator begin_;
InsnIterator end_;