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 (file)
--- a/src/Pipeline/SpirvShader.cpp
+++ b/src/Pipeline/SpirvShader.cpp
@@ -440,6 +440,20 @@ namespace sw
                                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 @@ namespace sw
                }
        }
 
+       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 (file)
--- 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 @@ namespace sw
                {
                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_;