summaryrefslogtreecommitdiff
path: root/src/shader_recompiler/frontend/ir
diff options
context:
space:
mode:
Diffstat (limited to 'src/shader_recompiler/frontend/ir')
-rw-r--r--src/shader_recompiler/frontend/ir/basic_block.cpp64
-rw-r--r--src/shader_recompiler/frontend/ir/basic_block.h40
-rw-r--r--src/shader_recompiler/frontend/ir/condition.cpp14
-rw-r--r--src/shader_recompiler/frontend/ir/condition.h2
-rw-r--r--src/shader_recompiler/frontend/ir/function.h2
-rw-r--r--src/shader_recompiler/frontend/ir/ir_emitter.cpp43
-rw-r--r--src/shader_recompiler/frontend/ir/ir_emitter.h23
-rw-r--r--src/shader_recompiler/frontend/ir/microinstruction.cpp4
-rw-r--r--src/shader_recompiler/frontend/ir/opcodes.inc16
-rw-r--r--src/shader_recompiler/frontend/ir/structured_control_flow.cpp742
-rw-r--r--src/shader_recompiler/frontend/ir/structured_control_flow.h22
11 files changed, 914 insertions, 58 deletions
diff --git a/src/shader_recompiler/frontend/ir/basic_block.cpp b/src/shader_recompiler/frontend/ir/basic_block.cpp
index da33ff6f1..b5616f394 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.cpp
+++ b/src/shader_recompiler/frontend/ir/basic_block.cpp
@@ -17,6 +17,8 @@ namespace Shader::IR {
17Block::Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end) 17Block::Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end)
18 : inst_pool{&inst_pool_}, location_begin{begin}, location_end{end} {} 18 : inst_pool{&inst_pool_}, location_begin{begin}, location_end{end} {}
19 19
20Block::Block(ObjectPool<Inst>& inst_pool_) : Block{inst_pool_, 0, 0} {}
21
20Block::~Block() = default; 22Block::~Block() = default;
21 23
22void Block::AppendNewInst(Opcode op, std::initializer_list<Value> args) { 24void Block::AppendNewInst(Opcode op, std::initializer_list<Value> args) {
@@ -38,8 +40,25 @@ Block::iterator Block::PrependNewInst(iterator insertion_point, Opcode op,
38 return result_it; 40 return result_it;
39} 41}
40 42
41void Block::AddImmediatePredecessor(IR::Block* immediate_predecessor) { 43void Block::SetBranches(Condition cond, Block* branch_true_, Block* branch_false_) {
42 imm_predecessors.push_back(immediate_predecessor); 44 branch_cond = cond;
45 branch_true = branch_true_;
46 branch_false = branch_false_;
47}
48
49void Block::SetBranch(Block* branch) {
50 branch_cond = Condition{true};
51 branch_true = branch;
52}
53
54void Block::SetReturn() {
55 branch_cond = Condition{true};
56 branch_true = nullptr;
57 branch_false = nullptr;
58}
59
60bool Block::IsVirtual() const noexcept {
61 return location_begin == location_end;
43} 62}
44 63
45u32 Block::LocationBegin() const noexcept { 64u32 Block::LocationBegin() const noexcept {
@@ -58,6 +77,12 @@ const Block::InstructionList& Block::Instructions() const noexcept {
58 return instructions; 77 return instructions;
59} 78}
60 79
80void Block::AddImmediatePredecessor(Block* block) {
81 if (std::ranges::find(imm_predecessors, block) == imm_predecessors.end()) {
82 imm_predecessors.push_back(block);
83 }
84}
85
61std::span<IR::Block* const> Block::ImmediatePredecessors() const noexcept { 86std::span<IR::Block* const> Block::ImmediatePredecessors() const noexcept {
62 return imm_predecessors; 87 return imm_predecessors;
63} 88}
@@ -70,8 +95,17 @@ static std::string BlockToIndex(const std::map<const Block*, size_t>& block_to_i
70 return fmt::format("$<unknown block {:016x}>", reinterpret_cast<u64>(block)); 95 return fmt::format("$<unknown block {:016x}>", reinterpret_cast<u64>(block));
71} 96}
72 97
98static size_t InstIndex(std::map<const Inst*, size_t>& inst_to_index, size_t& inst_index,
99 const Inst* inst) {
100 const auto [it, is_inserted]{inst_to_index.emplace(inst, inst_index + 1)};
101 if (is_inserted) {
102 ++inst_index;
103 }
104 return it->second;
105}
106
73static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_index, 107static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_index,
74 const std::map<const Inst*, size_t>& inst_to_index, 108 std::map<const Inst*, size_t>& inst_to_index, size_t& inst_index,
75 const Value& arg) { 109 const Value& arg) {
76 if (arg.IsEmpty()) { 110 if (arg.IsEmpty()) {
77 return "<null>"; 111 return "<null>";
@@ -80,10 +114,7 @@ static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_ind
80 return BlockToIndex(block_to_index, arg.Label()); 114 return BlockToIndex(block_to_index, arg.Label());
81 } 115 }
82 if (!arg.IsImmediate()) { 116 if (!arg.IsImmediate()) {
83 if (const auto it{inst_to_index.find(arg.Inst())}; it != inst_to_index.end()) { 117 return fmt::format("%{}", InstIndex(inst_to_index, inst_index, arg.Inst()));
84 return fmt::format("%{}", it->second);
85 }
86 return fmt::format("%<unknown inst {:016x}>", reinterpret_cast<u64>(arg.Inst()));
87 } 118 }
88 switch (arg.Type()) { 119 switch (arg.Type()) {
89 case Type::U1: 120 case Type::U1:
@@ -125,14 +156,14 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
125 const Opcode op{inst.Opcode()}; 156 const Opcode op{inst.Opcode()};
126 ret += fmt::format("[{:016x}] ", reinterpret_cast<u64>(&inst)); 157 ret += fmt::format("[{:016x}] ", reinterpret_cast<u64>(&inst));
127 if (TypeOf(op) != Type::Void) { 158 if (TypeOf(op) != Type::Void) {
128 ret += fmt::format("%{:<5} = {}", inst_index, op); 159 ret += fmt::format("%{:<5} = {}", InstIndex(inst_to_index, inst_index, &inst), op);
129 } else { 160 } else {
130 ret += fmt::format(" {}", op); // '%00000 = ' -> 1 + 5 + 3 = 9 spaces 161 ret += fmt::format(" {}", op); // '%00000 = ' -> 1 + 5 + 3 = 9 spaces
131 } 162 }
132 const size_t arg_count{NumArgsOf(op)}; 163 const size_t arg_count{inst.NumArgs()};
133 for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) { 164 for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) {
134 const Value arg{inst.Arg(arg_index)}; 165 const Value arg{inst.Arg(arg_index)};
135 const std::string arg_str{ArgToIndex(block_to_index, inst_to_index, arg)}; 166 const std::string arg_str{ArgToIndex(block_to_index, inst_to_index, inst_index, arg)};
136 ret += arg_index != 0 ? ", " : " "; 167 ret += arg_index != 0 ? ", " : " ";
137 if (op == Opcode::Phi) { 168 if (op == Opcode::Phi) {
138 ret += fmt::format("[ {}, {} ]", arg_index, 169 ret += fmt::format("[ {}, {} ]", arg_index,
@@ -140,10 +171,12 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
140 } else { 171 } else {
141 ret += arg_str; 172 ret += arg_str;
142 } 173 }
143 const Type actual_type{arg.Type()}; 174 if (op != Opcode::Phi) {
144 const Type expected_type{ArgTypeOf(op, arg_index)}; 175 const Type actual_type{arg.Type()};
145 if (!AreTypesCompatible(actual_type, expected_type)) { 176 const Type expected_type{ArgTypeOf(op, arg_index)};
146 ret += fmt::format("<type error: {} != {}>", actual_type, expected_type); 177 if (!AreTypesCompatible(actual_type, expected_type)) {
178 ret += fmt::format("<type error: {} != {}>", actual_type, expected_type);
179 }
147 } 180 }
148 } 181 }
149 if (TypeOf(op) != Type::Void) { 182 if (TypeOf(op) != Type::Void) {
@@ -151,9 +184,6 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
151 } else { 184 } else {
152 ret += '\n'; 185 ret += '\n';
153 } 186 }
154
155 inst_to_index.emplace(&inst, inst_index);
156 ++inst_index;
157 } 187 }
158 return ret; 188 return ret;
159} 189}
diff --git a/src/shader_recompiler/frontend/ir/basic_block.h b/src/shader_recompiler/frontend/ir/basic_block.h
index ec3ad6263..3205705e7 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.h
+++ b/src/shader_recompiler/frontend/ir/basic_block.h
@@ -11,7 +11,9 @@
11 11
12#include <boost/intrusive/list.hpp> 12#include <boost/intrusive/list.hpp>
13 13
14#include "shader_recompiler/frontend/ir/condition.h"
14#include "shader_recompiler/frontend/ir/microinstruction.h" 15#include "shader_recompiler/frontend/ir/microinstruction.h"
16#include "shader_recompiler/frontend/ir/value.h"
15#include "shader_recompiler/object_pool.h" 17#include "shader_recompiler/object_pool.h"
16 18
17namespace Shader::IR { 19namespace Shader::IR {
@@ -26,6 +28,7 @@ public:
26 using const_reverse_iterator = InstructionList::const_reverse_iterator; 28 using const_reverse_iterator = InstructionList::const_reverse_iterator;
27 29
28 explicit Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end); 30 explicit Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end);
31 explicit Block(ObjectPool<Inst>& inst_pool_);
29 ~Block(); 32 ~Block();
30 33
31 Block(const Block&) = delete; 34 Block(const Block&) = delete;
@@ -41,9 +44,15 @@ public:
41 iterator PrependNewInst(iterator insertion_point, Opcode op, 44 iterator PrependNewInst(iterator insertion_point, Opcode op,
42 std::initializer_list<Value> args = {}, u64 flags = 0); 45 std::initializer_list<Value> args = {}, u64 flags = 0);
43 46
44 /// Adds a new immediate predecessor to the basic block. 47 /// Set the branches to jump to when all instructions have executed.
45 void AddImmediatePredecessor(IR::Block* immediate_predecessor); 48 void SetBranches(Condition cond, Block* branch_true, Block* branch_false);
49 /// Set the branch to unconditionally jump to when all instructions have executed.
50 void SetBranch(Block* branch);
51 /// Mark the block as a return block.
52 void SetReturn();
46 53
54 /// Returns true when the block does not implement any guest instructions directly.
55 [[nodiscard]] bool IsVirtual() const noexcept;
47 /// Gets the starting location of this basic block. 56 /// Gets the starting location of this basic block.
48 [[nodiscard]] u32 LocationBegin() const noexcept; 57 [[nodiscard]] u32 LocationBegin() const noexcept;
49 /// Gets the end location for this basic block. 58 /// Gets the end location for this basic block.
@@ -54,8 +63,23 @@ public:
54 /// Gets an immutable reference to the instruction list for this basic block. 63 /// Gets an immutable reference to the instruction list for this basic block.
55 [[nodiscard]] const InstructionList& Instructions() const noexcept; 64 [[nodiscard]] const InstructionList& Instructions() const noexcept;
56 65
66 /// Adds a new immediate predecessor to this basic block.
67 void AddImmediatePredecessor(Block* block);
57 /// Gets an immutable span to the immediate predecessors. 68 /// Gets an immutable span to the immediate predecessors.
58 [[nodiscard]] std::span<IR::Block* const> ImmediatePredecessors() const noexcept; 69 [[nodiscard]] std::span<Block* const> ImmediatePredecessors() const noexcept;
70
71 [[nodiscard]] Condition BranchCondition() const noexcept {
72 return branch_cond;
73 }
74 [[nodiscard]] bool IsTerminationBlock() const noexcept {
75 return !branch_true && !branch_false;
76 }
77 [[nodiscard]] Block* TrueBranch() const noexcept {
78 return branch_true;
79 }
80 [[nodiscard]] Block* FalseBranch() const noexcept {
81 return branch_false;
82 }
59 83
60 [[nodiscard]] bool empty() const { 84 [[nodiscard]] bool empty() const {
61 return instructions.empty(); 85 return instructions.empty();
@@ -129,10 +153,18 @@ private:
129 /// List of instructions in this block 153 /// List of instructions in this block
130 InstructionList instructions; 154 InstructionList instructions;
131 155
156 /// Condition to choose the branch to take
157 Condition branch_cond{true};
158 /// Block to jump into when the branch condition evaluates as true
159 Block* branch_true{nullptr};
160 /// Block to jump into when the branch condition evaluates as false
161 Block* branch_false{nullptr};
132 /// Block immediate predecessors 162 /// Block immediate predecessors
133 std::vector<IR::Block*> imm_predecessors; 163 std::vector<Block*> imm_predecessors;
134}; 164};
135 165
166using BlockList = std::vector<Block*>;
167
136[[nodiscard]] std::string DumpBlock(const Block& block); 168[[nodiscard]] std::string DumpBlock(const Block& block);
137 169
138[[nodiscard]] std::string DumpBlock(const Block& block, 170[[nodiscard]] std::string DumpBlock(const Block& block,
diff --git a/src/shader_recompiler/frontend/ir/condition.cpp b/src/shader_recompiler/frontend/ir/condition.cpp
index edff35dc7..ec1659e2b 100644
--- a/src/shader_recompiler/frontend/ir/condition.cpp
+++ b/src/shader_recompiler/frontend/ir/condition.cpp
@@ -16,15 +16,13 @@ std::string NameOf(Condition condition) {
16 ret = fmt::to_string(condition.FlowTest()); 16 ret = fmt::to_string(condition.FlowTest());
17 } 17 }
18 const auto [pred, negated]{condition.Pred()}; 18 const auto [pred, negated]{condition.Pred()};
19 if (pred != Pred::PT || negated) { 19 if (!ret.empty()) {
20 if (!ret.empty()) { 20 ret += '&';
21 ret += '&';
22 }
23 if (negated) {
24 ret += '!';
25 }
26 ret += fmt::to_string(pred);
27 } 21 }
22 if (negated) {
23 ret += '!';
24 }
25 ret += fmt::to_string(pred);
28 return ret; 26 return ret;
29} 27}
30 28
diff --git a/src/shader_recompiler/frontend/ir/condition.h b/src/shader_recompiler/frontend/ir/condition.h
index 52737025c..16b4ae888 100644
--- a/src/shader_recompiler/frontend/ir/condition.h
+++ b/src/shader_recompiler/frontend/ir/condition.h
@@ -26,7 +26,7 @@ public:
26 explicit Condition(Pred pred_, bool pred_negated_ = false) noexcept 26 explicit Condition(Pred pred_, bool pred_negated_ = false) noexcept
27 : Condition(FlowTest::T, pred_, pred_negated_) {} 27 : Condition(FlowTest::T, pred_, pred_negated_) {}
28 28
29 Condition(bool value) : Condition(Pred::PT, !value) {} 29 explicit Condition(bool value) : Condition(Pred::PT, !value) {}
30 30
31 auto operator<=>(const Condition&) const noexcept = default; 31 auto operator<=>(const Condition&) const noexcept = default;
32 32
diff --git a/src/shader_recompiler/frontend/ir/function.h b/src/shader_recompiler/frontend/ir/function.h
index bba7d1d39..fd7d56419 100644
--- a/src/shader_recompiler/frontend/ir/function.h
+++ b/src/shader_recompiler/frontend/ir/function.h
@@ -11,7 +11,7 @@
11namespace Shader::IR { 11namespace Shader::IR {
12 12
13struct Function { 13struct Function {
14 boost::container::small_vector<Block*, 16> blocks; 14 BlockList blocks;
15}; 15};
16 16
17} // namespace Shader::IR 17} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/ir_emitter.cpp b/src/shader_recompiler/frontend/ir/ir_emitter.cpp
index ada0be834..30932043f 100644
--- a/src/shader_recompiler/frontend/ir/ir_emitter.cpp
+++ b/src/shader_recompiler/frontend/ir/ir_emitter.cpp
@@ -44,24 +44,27 @@ F64 IREmitter::Imm64(f64 value) const {
44 return F64{Value{value}}; 44 return F64{Value{value}};
45} 45}
46 46
47void IREmitter::Branch(IR::Block* label) { 47void IREmitter::Branch(Block* label) {
48 label->AddImmediatePredecessor(block);
48 Inst(Opcode::Branch, label); 49 Inst(Opcode::Branch, label);
49} 50}
50 51
51void IREmitter::BranchConditional(const U1& cond, IR::Block* true_label, IR::Block* false_label) { 52void IREmitter::BranchConditional(const U1& condition, Block* true_label, Block* false_label) {
52 Inst(Opcode::BranchConditional, cond, true_label, false_label); 53 true_label->AddImmediatePredecessor(block);
54 false_label->AddImmediatePredecessor(block);
55 Inst(Opcode::BranchConditional, condition, true_label, false_label);
53} 56}
54 57
55void IREmitter::Exit() { 58void IREmitter::LoopMerge(Block* merge_block, Block* continue_target) {
56 Inst(Opcode::Exit); 59 Inst(Opcode::LoopMerge, merge_block, continue_target);
57} 60}
58 61
59void IREmitter::Return() { 62void IREmitter::SelectionMerge(Block* merge_block) {
60 Inst(Opcode::Return); 63 Inst(Opcode::SelectionMerge, merge_block);
61} 64}
62 65
63void IREmitter::Unreachable() { 66void IREmitter::Return() {
64 Inst(Opcode::Unreachable); 67 Inst(Opcode::Return);
65} 68}
66 69
67U32 IREmitter::GetReg(IR::Reg reg) { 70U32 IREmitter::GetReg(IR::Reg reg) {
@@ -81,6 +84,14 @@ U1 IREmitter::GetPred(IR::Pred pred, bool is_negated) {
81 } 84 }
82} 85}
83 86
87U1 IREmitter::GetGotoVariable(u32 id) {
88 return Inst<U1>(Opcode::GetGotoVariable, id);
89}
90
91void IREmitter::SetGotoVariable(u32 id, const U1& value) {
92 Inst(Opcode::SetGotoVariable, id, value);
93}
94
84void IREmitter::SetPred(IR::Pred pred, const U1& value) { 95void IREmitter::SetPred(IR::Pred pred, const U1& value) {
85 Inst(Opcode::SetPred, pred, value); 96 Inst(Opcode::SetPred, pred, value);
86} 97}
@@ -121,6 +132,20 @@ void IREmitter::SetOFlag(const U1& value) {
121 Inst(Opcode::SetOFlag, value); 132 Inst(Opcode::SetOFlag, value);
122} 133}
123 134
135U1 IREmitter::Condition(IR::Condition cond) {
136 if (cond == IR::Condition{true}) {
137 return Imm1(true);
138 } else if (cond == IR::Condition{false}) {
139 return Imm1(false);
140 }
141 const FlowTest flow_test{cond.FlowTest()};
142 const auto [pred, is_negated]{cond.Pred()};
143 if (flow_test == FlowTest::T) {
144 return GetPred(pred, is_negated);
145 }
146 throw NotImplementedException("Condition {}", cond);
147}
148
124F32 IREmitter::GetAttribute(IR::Attribute attribute) { 149F32 IREmitter::GetAttribute(IR::Attribute attribute) {
125 return Inst<F32>(Opcode::GetAttribute, attribute); 150 return Inst<F32>(Opcode::GetAttribute, attribute);
126} 151}
diff --git a/src/shader_recompiler/frontend/ir/ir_emitter.h b/src/shader_recompiler/frontend/ir/ir_emitter.h
index bfd9916cc..4decb46bc 100644
--- a/src/shader_recompiler/frontend/ir/ir_emitter.h
+++ b/src/shader_recompiler/frontend/ir/ir_emitter.h
@@ -16,11 +16,11 @@ namespace Shader::IR {
16 16
17class IREmitter { 17class IREmitter {
18public: 18public:
19 explicit IREmitter(Block& block_) : block{block_}, insertion_point{block.end()} {} 19 explicit IREmitter(Block& block_) : block{&block_}, insertion_point{block->end()} {}
20 explicit IREmitter(Block& block_, Block::iterator insertion_point_) 20 explicit IREmitter(Block& block_, Block::iterator insertion_point_)
21 : block{block_}, insertion_point{insertion_point_} {} 21 : block{&block_}, insertion_point{insertion_point_} {}
22 22
23 Block& block; 23 Block* block;
24 24
25 [[nodiscard]] U1 Imm1(bool value) const; 25 [[nodiscard]] U1 Imm1(bool value) const;
26 [[nodiscard]] U8 Imm8(u8 value) const; 26 [[nodiscard]] U8 Imm8(u8 value) const;
@@ -31,11 +31,11 @@ public:
31 [[nodiscard]] U64 Imm64(u64 value) const; 31 [[nodiscard]] U64 Imm64(u64 value) const;
32 [[nodiscard]] F64 Imm64(f64 value) const; 32 [[nodiscard]] F64 Imm64(f64 value) const;
33 33
34 void Branch(IR::Block* label); 34 void Branch(Block* label);
35 void BranchConditional(const U1& cond, IR::Block* true_label, IR::Block* false_label); 35 void BranchConditional(const U1& condition, Block* true_label, Block* false_label);
36 void Exit(); 36 void LoopMerge(Block* merge_block, Block* continue_target);
37 void SelectionMerge(Block* merge_block);
37 void Return(); 38 void Return();
38 void Unreachable();
39 39
40 [[nodiscard]] U32 GetReg(IR::Reg reg); 40 [[nodiscard]] U32 GetReg(IR::Reg reg);
41 void SetReg(IR::Reg reg, const U32& value); 41 void SetReg(IR::Reg reg, const U32& value);
@@ -43,6 +43,9 @@ public:
43 [[nodiscard]] U1 GetPred(IR::Pred pred, bool is_negated = false); 43 [[nodiscard]] U1 GetPred(IR::Pred pred, bool is_negated = false);
44 void SetPred(IR::Pred pred, const U1& value); 44 void SetPred(IR::Pred pred, const U1& value);
45 45
46 [[nodiscard]] U1 GetGotoVariable(u32 id);
47 void SetGotoVariable(u32 id, const U1& value);
48
46 [[nodiscard]] U32 GetCbuf(const U32& binding, const U32& byte_offset); 49 [[nodiscard]] U32 GetCbuf(const U32& binding, const U32& byte_offset);
47 50
48 [[nodiscard]] U1 GetZFlag(); 51 [[nodiscard]] U1 GetZFlag();
@@ -55,6 +58,8 @@ public:
55 void SetCFlag(const U1& value); 58 void SetCFlag(const U1& value);
56 void SetOFlag(const U1& value); 59 void SetOFlag(const U1& value);
57 60
61 [[nodiscard]] U1 Condition(IR::Condition cond);
62
58 [[nodiscard]] F32 GetAttribute(IR::Attribute attribute); 63 [[nodiscard]] F32 GetAttribute(IR::Attribute attribute);
59 void SetAttribute(IR::Attribute attribute, const F32& value); 64 void SetAttribute(IR::Attribute attribute, const F32& value);
60 65
@@ -168,7 +173,7 @@ private:
168 173
169 template <typename T = Value, typename... Args> 174 template <typename T = Value, typename... Args>
170 T Inst(Opcode op, Args... args) { 175 T Inst(Opcode op, Args... args) {
171 auto it{block.PrependNewInst(insertion_point, op, {Value{args}...})}; 176 auto it{block->PrependNewInst(insertion_point, op, {Value{args}...})};
172 return T{Value{&*it}}; 177 return T{Value{&*it}};
173 } 178 }
174 179
@@ -184,7 +189,7 @@ private:
184 T Inst(Opcode op, Flags<FlagType> flags, Args... args) { 189 T Inst(Opcode op, Flags<FlagType> flags, Args... args) {
185 u64 raw_flags{}; 190 u64 raw_flags{};
186 std::memcpy(&raw_flags, &flags.proxy, sizeof(flags.proxy)); 191 std::memcpy(&raw_flags, &flags.proxy, sizeof(flags.proxy));
187 auto it{block.PrependNewInst(insertion_point, op, {Value{args}...}, raw_flags)}; 192 auto it{block->PrependNewInst(insertion_point, op, {Value{args}...}, raw_flags)};
188 return T{Value{&*it}}; 193 return T{Value{&*it}};
189 } 194 }
190}; 195};
diff --git a/src/shader_recompiler/frontend/ir/microinstruction.cpp b/src/shader_recompiler/frontend/ir/microinstruction.cpp
index e7ca92039..b4ae371bd 100644
--- a/src/shader_recompiler/frontend/ir/microinstruction.cpp
+++ b/src/shader_recompiler/frontend/ir/microinstruction.cpp
@@ -51,9 +51,9 @@ bool Inst::MayHaveSideEffects() const noexcept {
51 switch (op) { 51 switch (op) {
52 case Opcode::Branch: 52 case Opcode::Branch:
53 case Opcode::BranchConditional: 53 case Opcode::BranchConditional:
54 case Opcode::Exit: 54 case Opcode::LoopMerge:
55 case Opcode::SelectionMerge:
55 case Opcode::Return: 56 case Opcode::Return:
56 case Opcode::Unreachable:
57 case Opcode::SetAttribute: 57 case Opcode::SetAttribute:
58 case Opcode::SetAttributeIndexed: 58 case Opcode::SetAttributeIndexed:
59 case Opcode::WriteGlobalU8: 59 case Opcode::WriteGlobalU8:
diff --git a/src/shader_recompiler/frontend/ir/opcodes.inc b/src/shader_recompiler/frontend/ir/opcodes.inc
index 5dc65f2df..ede5e20c2 100644
--- a/src/shader_recompiler/frontend/ir/opcodes.inc
+++ b/src/shader_recompiler/frontend/ir/opcodes.inc
@@ -10,15 +10,17 @@ OPCODE(Identity, Opaque, Opaq
10// Control flow 10// Control flow
11OPCODE(Branch, Void, Label, ) 11OPCODE(Branch, Void, Label, )
12OPCODE(BranchConditional, Void, U1, Label, Label, ) 12OPCODE(BranchConditional, Void, U1, Label, Label, )
13OPCODE(Exit, Void, ) 13OPCODE(LoopMerge, Void, Label, Label, )
14OPCODE(SelectionMerge, Void, Label, )
14OPCODE(Return, Void, ) 15OPCODE(Return, Void, )
15OPCODE(Unreachable, Void, )
16 16
17// Context getters/setters 17// Context getters/setters
18OPCODE(GetRegister, U32, Reg, ) 18OPCODE(GetRegister, U32, Reg, )
19OPCODE(SetRegister, Void, Reg, U32, ) 19OPCODE(SetRegister, Void, Reg, U32, )
20OPCODE(GetPred, U1, Pred, ) 20OPCODE(GetPred, U1, Pred, )
21OPCODE(SetPred, Void, Pred, U1, ) 21OPCODE(SetPred, Void, Pred, U1, )
22OPCODE(GetGotoVariable, U1, U32, )
23OPCODE(SetGotoVariable, Void, U32, U1, )
22OPCODE(GetCbuf, U32, U32, U32, ) 24OPCODE(GetCbuf, U32, U32, U32, )
23OPCODE(GetAttribute, U32, Attribute, ) 25OPCODE(GetAttribute, U32, Attribute, )
24OPCODE(SetAttribute, Void, Attribute, U32, ) 26OPCODE(SetAttribute, Void, Attribute, U32, )
@@ -36,11 +38,11 @@ OPCODE(WorkgroupId, U32x3,
36OPCODE(LocalInvocationId, U32x3, ) 38OPCODE(LocalInvocationId, U32x3, )
37 39
38// Undefined 40// Undefined
39OPCODE(Undef1, U1, ) 41OPCODE(UndefU1, U1, )
40OPCODE(Undef8, U8, ) 42OPCODE(UndefU8, U8, )
41OPCODE(Undef16, U16, ) 43OPCODE(UndefU16, U16, )
42OPCODE(Undef32, U32, ) 44OPCODE(UndefU32, U32, )
43OPCODE(Undef64, U64, ) 45OPCODE(UndefU64, U64, )
44 46
45// Memory operations 47// Memory operations
46OPCODE(LoadGlobalU8, U32, U64, ) 48OPCODE(LoadGlobalU8, U32, U64, )
diff --git a/src/shader_recompiler/frontend/ir/structured_control_flow.cpp b/src/shader_recompiler/frontend/ir/structured_control_flow.cpp
new file mode 100644
index 000000000..2e9ce2525
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/structured_control_flow.cpp
@@ -0,0 +1,742 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#include <algorithm>
6#include <memory>
7#include <ranges>
8#include <string>
9#include <unordered_map>
10#include <utility>
11#include <vector>
12
13#include <fmt/format.h>
14
15#include <boost/intrusive/list.hpp>
16
17#include "shader_recompiler/frontend/ir/basic_block.h"
18#include "shader_recompiler/frontend/ir/ir_emitter.h"
19#include "shader_recompiler/object_pool.h"
20
21namespace Shader::IR {
22namespace {
23struct Statement;
24
25// Use normal_link because we are not guaranteed to destroy the tree in order
26using ListBaseHook =
27 boost::intrusive::list_base_hook<boost::intrusive::link_mode<boost::intrusive::normal_link>>;
28
29using Tree = boost::intrusive::list<Statement,
30 // Allow using Statement without a definition
31 boost::intrusive::base_hook<ListBaseHook>,
32 // Avoid linear complexity on splice, size is never called
33 boost::intrusive::constant_time_size<false>>;
34using Node = Tree::iterator;
35using ConstNode = Tree::const_iterator;
36
37enum class StatementType {
38 Code,
39 Goto,
40 Label,
41 If,
42 Loop,
43 Break,
44 Return,
45 Function,
46 Identity,
47 Not,
48 Or,
49 SetVariable,
50 Variable,
51};
52
53bool HasChildren(StatementType type) {
54 switch (type) {
55 case StatementType::If:
56 case StatementType::Loop:
57 case StatementType::Function:
58 return true;
59 default:
60 return false;
61 }
62}
63
64struct Goto {};
65struct Label {};
66struct If {};
67struct Loop {};
68struct Break {};
69struct Return {};
70struct FunctionTag {};
71struct Identity {};
72struct Not {};
73struct Or {};
74struct SetVariable {};
75struct Variable {};
76
77#ifdef _MSC_VER
78#pragma warning(push)
79#pragma warning(disable : 26495) // Always initialize a member variable, expected in Statement
80#endif
81struct Statement : ListBaseHook {
82 Statement(Block* code_, Statement* up_) : code{code_}, up{up_}, type{StatementType::Code} {}
83 Statement(Goto, Statement* cond_, Node label_, Statement* up_)
84 : label{label_}, cond{cond_}, up{up_}, type{StatementType::Goto} {}
85 Statement(Label, u32 id_, Statement* up_) : id{id_}, up{up_}, type{StatementType::Label} {}
86 Statement(If, Statement* cond_, Tree&& children_, Statement* up_)
87 : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::If} {}
88 Statement(Loop, Statement* cond_, Tree&& children_, Statement* up_)
89 : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::Loop} {}
90 Statement(Break, Statement* cond_, Statement* up_)
91 : cond{cond_}, up{up_}, type{StatementType::Break} {}
92 Statement(Return) : type{StatementType::Return} {}
93 Statement(FunctionTag) : children{}, type{StatementType::Function} {}
94 Statement(Identity, Condition cond_) : guest_cond{cond_}, type{StatementType::Identity} {}
95 Statement(Not, Statement* op_) : op{op_}, type{StatementType::Not} {}
96 Statement(Or, Statement* op_a_, Statement* op_b_)
97 : op_a{op_a_}, op_b{op_b_}, type{StatementType::Or} {}
98 Statement(SetVariable, u32 id_, Statement* op_, Statement* up_)
99 : op{op_}, id{id_}, up{up_}, type{StatementType::SetVariable} {}
100 Statement(Variable, u32 id_) : id{id_}, type{StatementType::Variable} {}
101
102 ~Statement() {
103 if (HasChildren(type)) {
104 std::destroy_at(&children);
105 }
106 }
107
108 union {
109 Block* code;
110 Node label;
111 Tree children;
112 Condition guest_cond;
113 Statement* op;
114 Statement* op_a;
115 };
116 union {
117 Statement* cond;
118 Statement* op_b;
119 u32 id;
120 };
121 Statement* up{};
122 StatementType type;
123};
124#ifdef _MSC_VER
125#pragma warning(pop)
126#endif
127
128std::string DumpExpr(const Statement* stmt) {
129 switch (stmt->type) {
130 case StatementType::Identity:
131 return fmt::format("{}", stmt->guest_cond);
132 case StatementType::Not:
133 return fmt::format("!{}", DumpExpr(stmt->op));
134 case StatementType::Or:
135 return fmt::format("{} || {}", DumpExpr(stmt->op_a), DumpExpr(stmt->op_b));
136 case StatementType::Variable:
137 return fmt::format("goto_L{}", stmt->id);
138 default:
139 return "<invalid type>";
140 }
141}
142
143std::string DumpTree(const Tree& tree, u32 indentation = 0) {
144 std::string ret;
145 std::string indent(indentation, ' ');
146 for (auto stmt = tree.begin(); stmt != tree.end(); ++stmt) {
147 switch (stmt->type) {
148 case StatementType::Code:
149 ret += fmt::format("{} Block {:04x};\n", indent, stmt->code->LocationBegin());
150 break;
151 case StatementType::Goto:
152 ret += fmt::format("{} if ({}) goto L{};\n", indent, DumpExpr(stmt->cond),
153 stmt->label->id);
154 break;
155 case StatementType::Label:
156 ret += fmt::format("{}L{}:\n", indent, stmt->id);
157 break;
158 case StatementType::If:
159 ret += fmt::format("{} if ({}) {{\n", indent, DumpExpr(stmt->cond));
160 ret += DumpTree(stmt->children, indentation + 4);
161 ret += fmt::format("{} }}\n", indent);
162 break;
163 case StatementType::Loop:
164 ret += fmt::format("{} do {{\n", indent);
165 ret += DumpTree(stmt->children, indentation + 4);
166 ret += fmt::format("{} }} while ({});\n", indent, DumpExpr(stmt->cond));
167 break;
168 case StatementType::Break:
169 ret += fmt::format("{} if ({}) break;\n", indent, DumpExpr(stmt->cond));
170 break;
171 case StatementType::Return:
172 ret += fmt::format("{} return;\n", indent);
173 break;
174 case StatementType::SetVariable:
175 ret += fmt::format("{} goto_L{} = {};\n", indent, stmt->id, DumpExpr(stmt->op));
176 break;
177 case StatementType::Function:
178 case StatementType::Identity:
179 case StatementType::Not:
180 case StatementType::Or:
181 case StatementType::Variable:
182 throw LogicError("Statement can't be printed");
183 }
184 }
185 return ret;
186}
187
188bool HasNode(const Tree& tree, ConstNode stmt) {
189 const auto end{tree.end()};
190 for (auto it = tree.begin(); it != end; ++it) {
191 if (it == stmt || (HasChildren(it->type) && HasNode(it->children, stmt))) {
192 return true;
193 }
194 }
195 return false;
196}
197
198Node FindStatementWithLabel(Tree& tree, ConstNode goto_stmt) {
199 const ConstNode label_stmt{goto_stmt->label};
200 const ConstNode end{tree.end()};
201 for (auto it = tree.begin(); it != end; ++it) {
202 if (it == label_stmt || (HasChildren(it->type) && HasNode(it->children, label_stmt))) {
203 return it;
204 }
205 }
206 throw LogicError("Lift label not in tree");
207}
208
209void SanitizeNoBreaks(const Tree& tree) {
210 if (std::ranges::find(tree, StatementType::Break, &Statement::type) != tree.end()) {
211 throw NotImplementedException("Capturing statement with break nodes");
212 }
213}
214
215size_t Level(Node stmt) {
216 size_t level{0};
217 Statement* node{stmt->up};
218 while (node) {
219 ++level;
220 node = node->up;
221 }
222 return level;
223}
224
225bool IsDirectlyRelated(Node goto_stmt, Node label_stmt) {
226 const size_t goto_level{Level(goto_stmt)};
227 const size_t label_level{Level(label_stmt)};
228 size_t min_level;
229 size_t max_level;
230 Node min;
231 Node max;
232 if (label_level < goto_level) {
233 min_level = label_level;
234 max_level = goto_level;
235 min = label_stmt;
236 max = goto_stmt;
237 } else { // goto_level < label_level
238 min_level = goto_level;
239 max_level = label_level;
240 min = goto_stmt;
241 max = label_stmt;
242 }
243 while (max_level > min_level) {
244 --max_level;
245 max = max->up;
246 }
247 return min->up == max->up;
248}
249
250bool IsIndirectlyRelated(Node goto_stmt, Node label_stmt) {
251 return goto_stmt->up != label_stmt->up && !IsDirectlyRelated(goto_stmt, label_stmt);
252}
253
254bool SearchNode(const Tree& tree, ConstNode stmt, size_t& offset) {
255 ++offset;
256
257 const auto end = tree.end();
258 for (ConstNode it = tree.begin(); it != end; ++it) {
259 ++offset;
260 if (stmt == it) {
261 return true;
262 }
263 if (HasChildren(it->type) && SearchNode(it->children, stmt, offset)) {
264 return true;
265 }
266 }
267 return false;
268}
269
270class GotoPass {
271public:
272 explicit GotoPass(std::span<Block* const> blocks, ObjectPool<Statement, 64>& stmt_pool)
273 : pool{stmt_pool} {
274 std::vector gotos{BuildUnorderedTreeGetGotos(blocks)};
275 fmt::print(stdout, "BEFORE\n{}\n", DumpTree(root_stmt.children));
276 for (const Node& goto_stmt : gotos | std::views::reverse) {
277 RemoveGoto(goto_stmt);
278 }
279 fmt::print(stdout, "AFTER\n{}\n", DumpTree(root_stmt.children));
280 }
281
282 Statement& RootStatement() noexcept {
283 return root_stmt;
284 }
285
286private:
287 void RemoveGoto(Node goto_stmt) {
288 // Force goto_stmt and label_stmt to be directly related
289 const Node label_stmt{goto_stmt->label};
290 if (IsIndirectlyRelated(goto_stmt, label_stmt)) {
291 // Move goto_stmt out using outward-movement transformation until it becomes
292 // directly related to label_stmt
293 while (!IsDirectlyRelated(goto_stmt, label_stmt)) {
294 goto_stmt = MoveOutward(goto_stmt);
295 }
296 }
297 // Force goto_stmt and label_stmt to be siblings
298 if (IsDirectlyRelated(goto_stmt, label_stmt)) {
299 const size_t label_level{Level(label_stmt)};
300 size_t goto_level{Level(goto_stmt)};
301 if (goto_level > label_level) {
302 // Move goto_stmt out of its level using outward-movement transformations
303 while (goto_level > label_level) {
304 goto_stmt = MoveOutward(goto_stmt);
305 --goto_level;
306 }
307 } else { // Level(goto_stmt) < Level(label_stmt)
308 if (Offset(goto_stmt) > Offset(label_stmt)) {
309 // Lift goto_stmt to above stmt containing label_stmt using goto-lifting
310 // transformations
311 goto_stmt = Lift(goto_stmt);
312 }
313 // Move goto_stmt into label_stmt's level using inward-movement transformation
314 while (goto_level < label_level) {
315 goto_stmt = MoveInward(goto_stmt);
316 ++goto_level;
317 }
318 }
319 }
320 // TODO: Remove this
321 Node it{goto_stmt};
322 bool sibling{false};
323 do {
324 sibling |= it == label_stmt;
325 --it;
326 } while (it != goto_stmt->up->children.begin());
327 while (it != goto_stmt->up->children.end()) {
328 sibling |= it == label_stmt;
329 ++it;
330 }
331 if (!sibling) {
332 throw LogicError("Not siblings");
333 }
334
335 // goto_stmt and label_stmt are guaranteed to be siblings, eliminate
336 if (std::next(goto_stmt) == label_stmt) {
337 // Simply eliminate the goto if the label is next to it
338 goto_stmt->up->children.erase(goto_stmt);
339 } else if (Offset(goto_stmt) < Offset(label_stmt)) {
340 // Eliminate goto_stmt with a conditional
341 EliminateAsConditional(goto_stmt, label_stmt);
342 } else {
343 // Eliminate goto_stmt with a loop
344 EliminateAsLoop(goto_stmt, label_stmt);
345 }
346 }
347
348 std::vector<Node> BuildUnorderedTreeGetGotos(std::span<Block* const> blocks) {
349 // Assume all blocks have two branches
350 std::vector<Node> gotos;
351 gotos.reserve(blocks.size() * 2);
352
353 const std::unordered_map labels_map{BuildLabels(blocks)};
354 Tree& root{root_stmt.children};
355 auto insert_point{root.begin()};
356 for (Block* const block : blocks) {
357 ++insert_point; // Skip label
358 ++insert_point; // Skip set variable
359 root.insert(insert_point, *pool.Create(block, &root_stmt));
360
361 if (block->IsTerminationBlock()) {
362 root.insert(insert_point, *pool.Create(Return{}));
363 continue;
364 }
365 const Condition cond{block->BranchCondition()};
366 Statement* const true_cond{pool.Create(Identity{}, Condition{true})};
367 if (cond == Condition{true} || cond == Condition{false}) {
368 const bool is_true{cond == Condition{true}};
369 const Block* const branch{is_true ? block->TrueBranch() : block->FalseBranch()};
370 const Node label{labels_map.at(branch)};
371 Statement* const goto_stmt{pool.Create(Goto{}, true_cond, label, &root_stmt)};
372 gotos.push_back(root.insert(insert_point, *goto_stmt));
373 } else {
374 Statement* const ident_cond{pool.Create(Identity{}, cond)};
375 const Node true_label{labels_map.at(block->TrueBranch())};
376 const Node false_label{labels_map.at(block->FalseBranch())};
377 Statement* goto_true{pool.Create(Goto{}, ident_cond, true_label, &root_stmt)};
378 Statement* goto_false{pool.Create(Goto{}, true_cond, false_label, &root_stmt)};
379 gotos.push_back(root.insert(insert_point, *goto_true));
380 gotos.push_back(root.insert(insert_point, *goto_false));
381 }
382 }
383 return gotos;
384 }
385
386 std::unordered_map<const Block*, Node> BuildLabels(std::span<Block* const> blocks) {
387 // TODO: Consider storing labels intrusively inside the block
388 std::unordered_map<const Block*, Node> labels_map;
389 Tree& root{root_stmt.children};
390 u32 label_id{0};
391 for (const Block* const block : blocks) {
392 Statement* const label{pool.Create(Label{}, label_id, &root_stmt)};
393 labels_map.emplace(block, root.insert(root.end(), *label));
394 Statement* const false_stmt{pool.Create(Identity{}, Condition{false})};
395 root.push_back(*pool.Create(SetVariable{}, label_id, false_stmt, &root_stmt));
396 ++label_id;
397 }
398 return labels_map;
399 }
400
401 void UpdateTreeUp(Statement* tree) {
402 for (Statement& stmt : tree->children) {
403 stmt.up = tree;
404 }
405 }
406
407 void EliminateAsConditional(Node goto_stmt, Node label_stmt) {
408 Tree& body{goto_stmt->up->children};
409 Tree if_body;
410 if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_stmt);
411 Statement* const cond{pool.Create(Not{}, goto_stmt->cond)};
412 Statement* const if_stmt{pool.Create(If{}, cond, std::move(if_body), goto_stmt->up)};
413 UpdateTreeUp(if_stmt);
414 body.insert(goto_stmt, *if_stmt);
415 body.erase(goto_stmt);
416 }
417
418 void EliminateAsLoop(Node goto_stmt, Node label_stmt) {
419 Tree& body{goto_stmt->up->children};
420 Tree loop_body;
421 loop_body.splice(loop_body.begin(), body, label_stmt, goto_stmt);
422 Statement* const cond{goto_stmt->cond};
423 Statement* const loop{pool.Create(Loop{}, cond, std::move(loop_body), goto_stmt->up)};
424 UpdateTreeUp(loop);
425 body.insert(goto_stmt, *loop);
426 body.erase(goto_stmt);
427 }
428
429 [[nodiscard]] Node MoveOutward(Node goto_stmt) {
430 switch (goto_stmt->up->type) {
431 case StatementType::If:
432 return MoveOutwardIf(goto_stmt);
433 case StatementType::Loop:
434 return MoveOutwardLoop(goto_stmt);
435 default:
436 throw LogicError("Invalid outward movement");
437 }
438 }
439
440 [[nodiscard]] Node MoveInward(Node goto_stmt) {
441 Statement* const parent{goto_stmt->up};
442 Tree& body{parent->children};
443 const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
444 const Node label{goto_stmt->label};
445 const u32 label_id{label->id};
446
447 Statement* const goto_cond{goto_stmt->cond};
448 Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
449 body.insert(goto_stmt, *set_var);
450
451 Tree if_body;
452 if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_nested_stmt);
453 Statement* const variable{pool.Create(Variable{}, label_id)};
454 Statement* const neg_var{pool.Create(Not{}, variable)};
455 if (!if_body.empty()) {
456 Statement* const if_stmt{pool.Create(If{}, neg_var, std::move(if_body), parent)};
457 UpdateTreeUp(if_stmt);
458 body.insert(goto_stmt, *if_stmt);
459 }
460 body.erase(goto_stmt);
461
462 // Update nested if condition
463 switch (label_nested_stmt->type) {
464 case StatementType::If:
465 label_nested_stmt->cond = pool.Create(Or{}, neg_var, label_nested_stmt->cond);
466 break;
467 case StatementType::Loop:
468 break;
469 default:
470 throw LogicError("Invalid inward movement");
471 }
472 Tree& nested_tree{label_nested_stmt->children};
473 Statement* const new_goto{pool.Create(Goto{}, variable, label, &*label_nested_stmt)};
474 return nested_tree.insert(nested_tree.begin(), *new_goto);
475 }
476
477 [[nodiscard]] Node Lift(Node goto_stmt) {
478 Statement* const parent{goto_stmt->up};
479 Tree& body{parent->children};
480 const Node label{goto_stmt->label};
481 const u32 label_id{label->id};
482 const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
483 const auto type{label_nested_stmt->type};
484
485 Tree loop_body;
486 loop_body.splice(loop_body.begin(), body, label_nested_stmt, goto_stmt);
487 SanitizeNoBreaks(loop_body);
488 Statement* const variable{pool.Create(Variable{}, label_id)};
489 Statement* const loop_stmt{pool.Create(Loop{}, variable, std::move(loop_body), parent)};
490 UpdateTreeUp(loop_stmt);
491 const Node loop_node{body.insert(goto_stmt, *loop_stmt)};
492
493 Statement* const new_goto{pool.Create(Goto{}, variable, label, loop_stmt)};
494 loop_stmt->children.push_front(*new_goto);
495 const Node new_goto_node{loop_stmt->children.begin()};
496
497 Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_stmt->cond, loop_stmt)};
498 loop_stmt->children.push_back(*set_var);
499
500 body.erase(goto_stmt);
501 return new_goto_node;
502 }
503
504 Node MoveOutwardIf(Node goto_stmt) {
505 const Node parent{Tree::s_iterator_to(*goto_stmt->up)};
506 Tree& body{parent->children};
507 const u32 label_id{goto_stmt->label->id};
508 Statement* const goto_cond{goto_stmt->cond};
509 Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, &*parent)};
510 body.insert(goto_stmt, *set_goto_var);
511
512 Tree if_body;
513 if_body.splice(if_body.begin(), body, std::next(goto_stmt), body.end());
514 if_body.pop_front();
515 Statement* const cond{pool.Create(Variable{}, label_id)};
516 Statement* const neg_cond{pool.Create(Not{}, cond)};
517 Statement* const if_stmt{pool.Create(If{}, neg_cond, std::move(if_body), &*parent)};
518 UpdateTreeUp(if_stmt);
519 body.insert(goto_stmt, *if_stmt);
520
521 body.erase(goto_stmt);
522
523 Statement* const new_cond{pool.Create(Variable{}, label_id)};
524 Statement* const new_goto{pool.Create(Goto{}, new_cond, goto_stmt->label, parent->up)};
525 Tree& parent_tree{parent->up->children};
526 return parent_tree.insert(std::next(parent), *new_goto);
527 }
528
529 Node MoveOutwardLoop(Node goto_stmt) {
530 Statement* const parent{goto_stmt->up};
531 Tree& body{parent->children};
532 const u32 label_id{goto_stmt->label->id};
533 Statement* const goto_cond{goto_stmt->cond};
534 Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
535 Statement* const cond{pool.Create(Variable{}, label_id)};
536 Statement* const break_stmt{pool.Create(Break{}, cond, parent)};
537 body.insert(goto_stmt, *set_goto_var);
538 body.insert(goto_stmt, *break_stmt);
539 body.erase(goto_stmt);
540
541 const Node loop{Tree::s_iterator_to(*goto_stmt->up)};
542 Statement* const new_goto_cond{pool.Create(Variable{}, label_id)};
543 Statement* const new_goto{pool.Create(Goto{}, new_goto_cond, goto_stmt->label, loop->up)};
544 Tree& parent_tree{loop->up->children};
545 return parent_tree.insert(std::next(loop), *new_goto);
546 }
547
548 size_t Offset(ConstNode stmt) const {
549 size_t offset{0};
550 if (!SearchNode(root_stmt.children, stmt, offset)) {
551 fmt::print(stdout, "{}\n", DumpTree(root_stmt.children));
552 throw LogicError("Node not found in tree");
553 }
554 return offset;
555 }
556
557 ObjectPool<Statement, 64>& pool;
558 Statement root_stmt{FunctionTag{}};
559};
560
561Block* TryFindForwardBlock(const Statement& stmt) {
562 const Tree& tree{stmt.up->children};
563 const ConstNode end{tree.cend()};
564 ConstNode forward_node{std::next(Tree::s_iterator_to(stmt))};
565 while (forward_node != end && !HasChildren(forward_node->type)) {
566 if (forward_node->type == StatementType::Code) {
567 return forward_node->code;
568 }
569 ++forward_node;
570 }
571 return nullptr;
572}
573
574[[nodiscard]] U1 VisitExpr(IREmitter& ir, const Statement& stmt) {
575 switch (stmt.type) {
576 case StatementType::Identity:
577 return ir.Condition(stmt.guest_cond);
578 case StatementType::Not:
579 return ir.LogicalNot(U1{VisitExpr(ir, *stmt.op)});
580 case StatementType::Or:
581 return ir.LogicalOr(VisitExpr(ir, *stmt.op_a), VisitExpr(ir, *stmt.op_b));
582 case StatementType::Variable:
583 return ir.GetGotoVariable(stmt.id);
584 default:
585 throw NotImplementedException("Statement type {}", stmt.type);
586 }
587}
588
589class TranslatePass {
590public:
591 TranslatePass(ObjectPool<Inst>& inst_pool_, ObjectPool<Block>& block_pool_,
592 ObjectPool<Statement, 64>& stmt_pool_, Statement& root_stmt,
593 const std::function<void(IR::Block*)>& func_, BlockList& block_list_)
594 : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, func{func_},
595 block_list{block_list_} {
596 Visit(root_stmt, nullptr, nullptr);
597 }
598
599private:
600 void Visit(Statement& parent, Block* continue_block, Block* break_block) {
601 Tree& tree{parent.children};
602 Block* current_block{nullptr};
603
604 for (auto it = tree.begin(); it != tree.end(); ++it) {
605 Statement& stmt{*it};
606 switch (stmt.type) {
607 case StatementType::Label:
608 // Labels can be ignored
609 break;
610 case StatementType::Code: {
611 if (current_block && current_block != stmt.code) {
612 IREmitter ir{*current_block};
613 ir.Branch(stmt.code);
614 }
615 current_block = stmt.code;
616 func(stmt.code);
617 block_list.push_back(stmt.code);
618 break;
619 }
620 case StatementType::SetVariable: {
621 if (!current_block) {
622 current_block = MergeBlock(parent, stmt);
623 }
624 IREmitter ir{*current_block};
625 ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op));
626 break;
627 }
628 case StatementType::If: {
629 if (!current_block) {
630 current_block = block_pool.Create(inst_pool);
631 block_list.push_back(current_block);
632 }
633 Block* const merge_block{MergeBlock(parent, stmt)};
634
635 // Visit children
636 const size_t first_block_index{block_list.size()};
637 Visit(stmt, merge_block, break_block);
638
639 // Implement if header block
640 Block* const first_if_block{block_list.at(first_block_index)};
641 IREmitter ir{*current_block};
642 const U1 cond{VisitExpr(ir, *stmt.cond)};
643 ir.SelectionMerge(merge_block);
644 ir.BranchConditional(cond, first_if_block, merge_block);
645
646 current_block = merge_block;
647 break;
648 }
649 case StatementType::Loop: {
650 Block* const loop_header_block{block_pool.Create(inst_pool)};
651 if (current_block) {
652 IREmitter{*current_block}.Branch(loop_header_block);
653 }
654 block_list.push_back(loop_header_block);
655
656 Block* const new_continue_block{block_pool.Create(inst_pool)};
657 Block* const merge_block{MergeBlock(parent, stmt)};
658
659 // Visit children
660 const size_t first_block_index{block_list.size()};
661 Visit(stmt, new_continue_block, merge_block);
662
663 // The continue block is located at the end of the loop
664 block_list.push_back(new_continue_block);
665
666 // Implement loop header block
667 Block* const first_loop_block{block_list.at(first_block_index)};
668 IREmitter ir{*loop_header_block};
669 ir.LoopMerge(merge_block, new_continue_block);
670 ir.Branch(first_loop_block);
671
672 // Implement continue block
673 IREmitter continue_ir{*new_continue_block};
674 const U1 continue_cond{VisitExpr(continue_ir, *stmt.cond)};
675 continue_ir.BranchConditional(continue_cond, ir.block, merge_block);
676
677 current_block = merge_block;
678 break;
679 }
680 case StatementType::Break: {
681 if (!current_block) {
682 current_block = block_pool.Create(inst_pool);
683 block_list.push_back(current_block);
684 }
685 Block* const skip_block{MergeBlock(parent, stmt)};
686
687 IREmitter ir{*current_block};
688 ir.BranchConditional(VisitExpr(ir, *stmt.cond), break_block, skip_block);
689
690 current_block = skip_block;
691 break;
692 }
693 case StatementType::Return: {
694 if (!current_block) {
695 current_block = block_pool.Create(inst_pool);
696 block_list.push_back(current_block);
697 }
698 IREmitter{*current_block}.Return();
699 current_block = nullptr;
700 break;
701 }
702 default:
703 throw NotImplementedException("Statement type {}", stmt.type);
704 }
705 }
706 if (current_block && continue_block) {
707 IREmitter ir{*current_block};
708 ir.Branch(continue_block);
709 }
710 }
711
712 Block* MergeBlock(Statement& parent, Statement& stmt) {
713 if (Block* const block{TryFindForwardBlock(stmt)}) {
714 return block;
715 }
716 // Create a merge block we can visit later
717 Block* const block{block_pool.Create(inst_pool)};
718 Statement* const merge_stmt{stmt_pool.Create(block, &parent)};
719 parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
720 return block;
721 }
722
723 ObjectPool<Statement, 64>& stmt_pool;
724 ObjectPool<Inst>& inst_pool;
725 ObjectPool<Block>& block_pool;
726 const std::function<void(IR::Block*)>& func;
727 BlockList& block_list;
728};
729} // Anonymous namespace
730
731BlockList VisitAST(ObjectPool<Inst>& inst_pool, ObjectPool<Block>& block_pool,
732 std::span<Block* const> unordered_blocks,
733 const std::function<void(Block*)>& func) {
734 ObjectPool<Statement, 64> stmt_pool;
735 GotoPass goto_pass{unordered_blocks, stmt_pool};
736 BlockList block_list;
737 TranslatePass translate_pass{inst_pool, block_pool, stmt_pool, goto_pass.RootStatement(),
738 func, block_list};
739 return block_list;
740}
741
742} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/structured_control_flow.h b/src/shader_recompiler/frontend/ir/structured_control_flow.h
new file mode 100644
index 000000000..a574c24f7
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/structured_control_flow.h
@@ -0,0 +1,22 @@
1// Copyright 2021 yuzu Emulator Project
2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included.
4
5#pragma once
6
7#include <functional>
8#include <span>
9
10#include <boost/intrusive/list.hpp>
11
12#include "shader_recompiler/frontend/ir/basic_block.h"
13#include "shader_recompiler/frontend/ir/microinstruction.h"
14#include "shader_recompiler/object_pool.h"
15
16namespace Shader::IR {
17
18[[nodiscard]] BlockList VisitAST(ObjectPool<Inst>& inst_pool, ObjectPool<Block>& block_pool,
19 std::span<Block* const> unordered_blocks,
20 const std::function<void(Block*)>& func);
21
22} // namespace Shader::IR
HIC SVNT DRACONES