shader: SSA and dominance

1 files changed, 38 insertions, 6 deletions

diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.h b/src/shader_recompiler/frontend/maxwell/control_flow.h
index b2ab0cdc3..20ada8afd 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.h
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.h
@@ -70,6 +70,12 @@ struct Block {
     IR::Condition cond;
     BlockId branch_true;
     BlockId branch_false;
+    boost::container::small_vector<BlockId, 4> imm_predecessors;
+    boost::container::small_vector<BlockId, 8> dominance_frontiers;
+    union {
+        bool post_order_visited{false};
+        Block* imm_dominator;
+    };
 };
 
 struct Label {
@@ -81,11 +87,30 @@ struct Label {
 struct Function {
     Function(Location start_address);
 
+    void BuildBlocksMap();
+
+    void BuildImmediatePredecessors();
+
+    void BuildPostOrder();
+
+    void BuildImmediateDominators();
+
+    void BuildDominanceFrontier();
+
+    [[nodiscard]] size_t NumBlocks() const noexcept {
+        return static_cast<size_t>(current_block_id) + 1;
+    }
+
     Location entrypoint;
     BlockId current_block_id{0};
     boost::container::small_vector<Label, 16> labels;
     boost::container::small_vector<u32, 0x130> blocks;
     boost::container::small_vector<Block, 0x130> blocks_data;
+    // Translates from BlockId to block index
+    boost::container::small_vector<Block*, 0x130> blocks_map;
+
+    boost::container::small_vector<u32, 0x130> post_order_blocks;
+    boost::container::small_vector<BlockId, 0x130> post_order_map;
 };
 
 class CFG {
@@ -97,6 +122,12 @@ class CFG {
 public:
     explicit CFG(Environment& env, Location start_address);
 
+    CFG& operator=(const CFG&) = delete;
+    CFG(const CFG&) = delete;
+
+    CFG& operator=(CFG&&) = delete;
+    CFG(CFG&&) = delete;
+
     [[nodiscard]] std::string Dot() const;
 
     [[nodiscard]] std::span<const Function> Functions() const noexcept {
@@ -104,20 +135,22 @@ public:
     }
 
 private:
+    void VisitFunctions(Location start_address);
+
     void AnalyzeLabel(FunctionId function_id, Label& label);
 
     /// Inspect already visited blocks.
     /// Return true when the block has already been visited
-    [[nodiscard]] bool InspectVisitedBlocks(FunctionId function_id, const Label& label);
+    bool InspectVisitedBlocks(FunctionId function_id, const Label& label);
 
-    [[nodiscard]] AnalysisState AnalyzeInst(Block& block, FunctionId function_id, Location pc);
+    AnalysisState AnalyzeInst(Block& block, FunctionId function_id, Location pc);
 
     void AnalyzeCondInst(Block& block, FunctionId function_id, Location pc, EndClass insn_end_class,
                          IR::Condition cond);
 
     /// Return true when the branch instruction is confirmed to be a branch
-    [[nodiscard]] bool AnalyzeBranch(Block& block, FunctionId function_id, Location pc,
-                                     Instruction inst, Opcode opcode);
+    bool AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instruction inst,
+                       Opcode opcode);
 
     void AnalyzeBRA(Block& block, FunctionId function_id, Location pc, Instruction inst,
                     bool is_absolute);
@@ -126,8 +159,7 @@ private:
     AnalysisState AnalyzeEXIT(Block& block, FunctionId function_id, Location pc, Instruction inst);
 
     /// Return the branch target block id
-    [[nodiscard]] BlockId AddLabel(const Block& block, Stack stack, Location pc,
-                                   FunctionId function_id);
+    BlockId AddLabel(const Block& block, Stack stack, Location pc, FunctionId function_id);
 
     Environment& env;
     boost::container::small_vector<Function, 1> functions;