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/function.cpp5
-rw-r--r--src/shader_recompiler/frontend/ir/function.h18
-rw-r--r--src/shader_recompiler/frontend/ir/program.cpp18
-rw-r--r--src/shader_recompiler/frontend/ir/program.h5
-rw-r--r--src/shader_recompiler/frontend/ir/structured_control_flow.cpp744
-rw-r--r--src/shader_recompiler/frontend/ir/structured_control_flow.h22
6 files changed, 10 insertions, 802 deletions
diff --git a/src/shader_recompiler/frontend/ir/function.cpp b/src/shader_recompiler/frontend/ir/function.cpp
deleted file mode 100644
index d1fc9461d..000000000
--- a/src/shader_recompiler/frontend/ir/function.cpp
+++ /dev/null
@@ -1,5 +0,0 @@
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 "shader_recompiler/frontend/ir/function.h"
diff --git a/src/shader_recompiler/frontend/ir/function.h b/src/shader_recompiler/frontend/ir/function.h
deleted file mode 100644
index d1f061146..000000000
--- a/src/shader_recompiler/frontend/ir/function.h
+++ /dev/null
@@ -1,18 +0,0 @@
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 <boost/container/small_vector.hpp>
8
9#include "shader_recompiler/frontend/ir/basic_block.h"
10
11namespace Shader::IR {
12
13struct Function {
14 BlockList blocks;
15 BlockList post_order_blocks;
16};
17
18} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/program.cpp b/src/shader_recompiler/frontend/ir/program.cpp
index 8c301c3a1..5f51aeb5f 100644
--- a/src/shader_recompiler/frontend/ir/program.cpp
+++ b/src/shader_recompiler/frontend/ir/program.cpp
@@ -9,7 +9,8 @@
9 9
10#include <fmt/format.h> 10#include <fmt/format.h>
11 11
12#include "shader_recompiler/frontend/ir/function.h" 12#include "shader_recompiler/frontend/ir/basic_block.h"
13#include "shader_recompiler/frontend/ir/microinstruction.h"
13#include "shader_recompiler/frontend/ir/program.h" 14#include "shader_recompiler/frontend/ir/program.h"
14 15
15namespace Shader::IR { 16namespace Shader::IR {
@@ -19,18 +20,13 @@ std::string DumpProgram(const Program& program) {
19 std::map<const IR::Inst*, size_t> inst_to_index; 20 std::map<const IR::Inst*, size_t> inst_to_index;
20 std::map<const IR::Block*, size_t> block_to_index; 21 std::map<const IR::Block*, size_t> block_to_index;
21 22
22 for (const IR::Function& function : program.functions) { 23 for (const IR::Block* const block : program.blocks) {
23 for (const IR::Block* const block : function.blocks) { 24 block_to_index.emplace(block, index);
24 block_to_index.emplace(block, index); 25 ++index;
25 ++index;
26 }
27 } 26 }
28 std::string ret; 27 std::string ret;
29 for (const IR::Function& function : program.functions) { 28 for (const auto& block : program.blocks) {
30 ret += fmt::format("Function\n"); 29 ret += IR::DumpBlock(*block, block_to_index, inst_to_index, index) + '\n';
31 for (const auto& block : function.blocks) {
32 ret += IR::DumpBlock(*block, block_to_index, inst_to_index, index) + '\n';
33 }
34 } 30 }
35 return ret; 31 return ret;
36} 32}
diff --git a/src/shader_recompiler/frontend/ir/program.h b/src/shader_recompiler/frontend/ir/program.h
index 98aab2dc6..bce8b19b3 100644
--- a/src/shader_recompiler/frontend/ir/program.h
+++ b/src/shader_recompiler/frontend/ir/program.h
@@ -8,13 +8,14 @@
8 8
9#include <boost/container/small_vector.hpp> 9#include <boost/container/small_vector.hpp>
10 10
11#include "shader_recompiler/frontend/ir/function.h" 11#include "shader_recompiler/frontend/ir/basic_block.h"
12#include "shader_recompiler/shader_info.h" 12#include "shader_recompiler/shader_info.h"
13 13
14namespace Shader::IR { 14namespace Shader::IR {
15 15
16struct Program { 16struct Program {
17 boost::container::small_vector<Function, 1> functions; 17 BlockList blocks;
18 BlockList post_order_blocks;
18 Info info; 19 Info info;
19}; 20};
20 21
diff --git a/src/shader_recompiler/frontend/ir/structured_control_flow.cpp b/src/shader_recompiler/frontend/ir/structured_control_flow.cpp
deleted file mode 100644
index bfba55a7e..000000000
--- a/src/shader_recompiler/frontend/ir/structured_control_flow.cpp
+++ /dev/null
@@ -1,744 +0,0 @@
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>& stmt_pool)
273 : pool{stmt_pool} {
274 std::vector gotos{BuildUnorderedTreeGetGotos(blocks)};
275 for (const Node& goto_stmt : gotos | std::views::reverse) {
276 RemoveGoto(goto_stmt);
277 }
278 }
279
280 Statement& RootStatement() noexcept {
281 return root_stmt;
282 }
283
284private:
285 void RemoveGoto(Node goto_stmt) {
286 // Force goto_stmt and label_stmt to be directly related
287 const Node label_stmt{goto_stmt->label};
288 if (IsIndirectlyRelated(goto_stmt, label_stmt)) {
289 // Move goto_stmt out using outward-movement transformation until it becomes
290 // directly related to label_stmt
291 while (!IsDirectlyRelated(goto_stmt, label_stmt)) {
292 goto_stmt = MoveOutward(goto_stmt);
293 }
294 }
295 // Force goto_stmt and label_stmt to be siblings
296 if (IsDirectlyRelated(goto_stmt, label_stmt)) {
297 const size_t label_level{Level(label_stmt)};
298 size_t goto_level{Level(goto_stmt)};
299 if (goto_level > label_level) {
300 // Move goto_stmt out of its level using outward-movement transformations
301 while (goto_level > label_level) {
302 goto_stmt = MoveOutward(goto_stmt);
303 --goto_level;
304 }
305 } else { // Level(goto_stmt) < Level(label_stmt)
306 if (Offset(goto_stmt) > Offset(label_stmt)) {
307 // Lift goto_stmt to above stmt containing label_stmt using goto-lifting
308 // transformations
309 goto_stmt = Lift(goto_stmt);
310 }
311 // Move goto_stmt into label_stmt's level using inward-movement transformation
312 while (goto_level < label_level) {
313 goto_stmt = MoveInward(goto_stmt);
314 ++goto_level;
315 }
316 }
317 }
318 // TODO: Remove this
319 Node it{goto_stmt};
320 bool sibling{false};
321 do {
322 sibling |= it == label_stmt;
323 --it;
324 } while (it != goto_stmt->up->children.begin());
325 while (it != goto_stmt->up->children.end()) {
326 sibling |= it == label_stmt;
327 ++it;
328 }
329 if (!sibling) {
330 throw LogicError("Not siblings");
331 }
332 // goto_stmt and label_stmt are guaranteed to be siblings, eliminate
333 if (std::next(goto_stmt) == label_stmt) {
334 // Simply eliminate the goto if the label is next to it
335 goto_stmt->up->children.erase(goto_stmt);
336 } else if (Offset(goto_stmt) < Offset(label_stmt)) {
337 // Eliminate goto_stmt with a conditional
338 EliminateAsConditional(goto_stmt, label_stmt);
339 } else {
340 // Eliminate goto_stmt with a loop
341 EliminateAsLoop(goto_stmt, label_stmt);
342 }
343 }
344
345 std::vector<Node> BuildUnorderedTreeGetGotos(std::span<Block* const> blocks) {
346 // Assume all blocks have two branches
347 std::vector<Node> gotos;
348 gotos.reserve(blocks.size() * 2);
349
350 const std::unordered_map labels_map{BuildLabels(blocks)};
351 Tree& root{root_stmt.children};
352 auto insert_point{root.begin()};
353 // Skip all goto variables zero-initialization
354 std::advance(insert_point, labels_map.size());
355
356 for (Block* const block : blocks) {
357 // Skip label
358 ++insert_point;
359 // Skip set variable
360 ++insert_point;
361 root.insert(insert_point, *pool.Create(block, &root_stmt));
362
363 if (block->IsTerminationBlock()) {
364 root.insert(insert_point, *pool.Create(Return{}));
365 continue;
366 }
367 const Condition cond{block->BranchCondition()};
368 Statement* const true_cond{pool.Create(Identity{}, Condition{true})};
369 if (cond == Condition{true} || cond == Condition{false}) {
370 const bool is_true{cond == Condition{true}};
371 const Block* const branch{is_true ? block->TrueBranch() : block->FalseBranch()};
372 const Node label{labels_map.at(branch)};
373 Statement* const goto_stmt{pool.Create(Goto{}, true_cond, label, &root_stmt)};
374 gotos.push_back(root.insert(insert_point, *goto_stmt));
375 } else {
376 Statement* const ident_cond{pool.Create(Identity{}, cond)};
377 const Node true_label{labels_map.at(block->TrueBranch())};
378 const Node false_label{labels_map.at(block->FalseBranch())};
379 Statement* goto_true{pool.Create(Goto{}, ident_cond, true_label, &root_stmt)};
380 Statement* goto_false{pool.Create(Goto{}, true_cond, false_label, &root_stmt)};
381 gotos.push_back(root.insert(insert_point, *goto_true));
382 gotos.push_back(root.insert(insert_point, *goto_false));
383 }
384 }
385 return gotos;
386 }
387
388 std::unordered_map<const Block*, Node> BuildLabels(std::span<Block* const> blocks) {
389 // TODO: Consider storing labels intrusively inside the block
390 std::unordered_map<const Block*, Node> labels_map;
391 Tree& root{root_stmt.children};
392 u32 label_id{0};
393 for (const Block* const block : blocks) {
394 Statement* const label{pool.Create(Label{}, label_id, &root_stmt)};
395 labels_map.emplace(block, root.insert(root.end(), *label));
396 Statement* const false_stmt{pool.Create(Identity{}, Condition{false})};
397 root.push_back(*pool.Create(SetVariable{}, label_id, false_stmt, &root_stmt));
398 root.push_front(*pool.Create(SetVariable{}, label_id, false_stmt, &root_stmt));
399 ++label_id;
400 }
401 return labels_map;
402 }
403
404 void UpdateTreeUp(Statement* tree) {
405 for (Statement& stmt : tree->children) {
406 stmt.up = tree;
407 }
408 }
409
410 void EliminateAsConditional(Node goto_stmt, Node label_stmt) {
411 Tree& body{goto_stmt->up->children};
412 Tree if_body;
413 if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_stmt);
414 Statement* const cond{pool.Create(Not{}, goto_stmt->cond)};
415 Statement* const if_stmt{pool.Create(If{}, cond, std::move(if_body), goto_stmt->up)};
416 UpdateTreeUp(if_stmt);
417 body.insert(goto_stmt, *if_stmt);
418 body.erase(goto_stmt);
419 }
420
421 void EliminateAsLoop(Node goto_stmt, Node label_stmt) {
422 Tree& body{goto_stmt->up->children};
423 Tree loop_body;
424 loop_body.splice(loop_body.begin(), body, label_stmt, goto_stmt);
425 Statement* const cond{goto_stmt->cond};
426 Statement* const loop{pool.Create(Loop{}, cond, std::move(loop_body), goto_stmt->up)};
427 UpdateTreeUp(loop);
428 body.insert(goto_stmt, *loop);
429 body.erase(goto_stmt);
430 }
431
432 [[nodiscard]] Node MoveOutward(Node goto_stmt) {
433 switch (goto_stmt->up->type) {
434 case StatementType::If:
435 return MoveOutwardIf(goto_stmt);
436 case StatementType::Loop:
437 return MoveOutwardLoop(goto_stmt);
438 default:
439 throw LogicError("Invalid outward movement");
440 }
441 }
442
443 [[nodiscard]] Node MoveInward(Node goto_stmt) {
444 Statement* const parent{goto_stmt->up};
445 Tree& body{parent->children};
446 const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
447 const Node label{goto_stmt->label};
448 const u32 label_id{label->id};
449
450 Statement* const goto_cond{goto_stmt->cond};
451 Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
452 body.insert(goto_stmt, *set_var);
453
454 Tree if_body;
455 if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_nested_stmt);
456 Statement* const variable{pool.Create(Variable{}, label_id)};
457 Statement* const neg_var{pool.Create(Not{}, variable)};
458 if (!if_body.empty()) {
459 Statement* const if_stmt{pool.Create(If{}, neg_var, std::move(if_body), parent)};
460 UpdateTreeUp(if_stmt);
461 body.insert(goto_stmt, *if_stmt);
462 }
463 body.erase(goto_stmt);
464
465 switch (label_nested_stmt->type) {
466 case StatementType::If:
467 // Update nested if condition
468 label_nested_stmt->cond = pool.Create(Or{}, variable, label_nested_stmt->cond);
469 break;
470 case StatementType::Loop:
471 break;
472 default:
473 throw LogicError("Invalid inward movement");
474 }
475 Tree& nested_tree{label_nested_stmt->children};
476 Statement* const new_goto{pool.Create(Goto{}, variable, label, &*label_nested_stmt)};
477 return nested_tree.insert(nested_tree.begin(), *new_goto);
478 }
479
480 [[nodiscard]] Node Lift(Node goto_stmt) {
481 Statement* const parent{goto_stmt->up};
482 Tree& body{parent->children};
483 const Node label{goto_stmt->label};
484 const u32 label_id{label->id};
485 const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
486 const auto type{label_nested_stmt->type};
487
488 Tree loop_body;
489 loop_body.splice(loop_body.begin(), body, label_nested_stmt, goto_stmt);
490 SanitizeNoBreaks(loop_body);
491 Statement* const variable{pool.Create(Variable{}, label_id)};
492 Statement* const loop_stmt{pool.Create(Loop{}, variable, std::move(loop_body), parent)};
493 UpdateTreeUp(loop_stmt);
494 const Node loop_node{body.insert(goto_stmt, *loop_stmt)};
495
496 Statement* const new_goto{pool.Create(Goto{}, variable, label, loop_stmt)};
497 loop_stmt->children.push_front(*new_goto);
498 const Node new_goto_node{loop_stmt->children.begin()};
499
500 Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_stmt->cond, loop_stmt)};
501 loop_stmt->children.push_back(*set_var);
502
503 body.erase(goto_stmt);
504 return new_goto_node;
505 }
506
507 Node MoveOutwardIf(Node goto_stmt) {
508 const Node parent{Tree::s_iterator_to(*goto_stmt->up)};
509 Tree& body{parent->children};
510 const u32 label_id{goto_stmt->label->id};
511 Statement* const goto_cond{goto_stmt->cond};
512 Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, &*parent)};
513 body.insert(goto_stmt, *set_goto_var);
514
515 Tree if_body;
516 if_body.splice(if_body.begin(), body, std::next(goto_stmt), body.end());
517 if_body.pop_front();
518 Statement* const cond{pool.Create(Variable{}, label_id)};
519 Statement* const neg_cond{pool.Create(Not{}, cond)};
520 Statement* const if_stmt{pool.Create(If{}, neg_cond, std::move(if_body), &*parent)};
521 UpdateTreeUp(if_stmt);
522 body.insert(goto_stmt, *if_stmt);
523
524 body.erase(goto_stmt);
525
526 Statement* const new_cond{pool.Create(Variable{}, label_id)};
527 Statement* const new_goto{pool.Create(Goto{}, new_cond, goto_stmt->label, parent->up)};
528 Tree& parent_tree{parent->up->children};
529 return parent_tree.insert(std::next(parent), *new_goto);
530 }
531
532 Node MoveOutwardLoop(Node goto_stmt) {
533 Statement* const parent{goto_stmt->up};
534 Tree& body{parent->children};
535 const u32 label_id{goto_stmt->label->id};
536 Statement* const goto_cond{goto_stmt->cond};
537 Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
538 Statement* const cond{pool.Create(Variable{}, label_id)};
539 Statement* const break_stmt{pool.Create(Break{}, cond, parent)};
540 body.insert(goto_stmt, *set_goto_var);
541 body.insert(goto_stmt, *break_stmt);
542 body.erase(goto_stmt);
543
544 const Node loop{Tree::s_iterator_to(*goto_stmt->up)};
545 Statement* const new_goto_cond{pool.Create(Variable{}, label_id)};
546 Statement* const new_goto{pool.Create(Goto{}, new_goto_cond, goto_stmt->label, loop->up)};
547 Tree& parent_tree{loop->up->children};
548 return parent_tree.insert(std::next(loop), *new_goto);
549 }
550
551 size_t Offset(ConstNode stmt) const {
552 size_t offset{0};
553 if (!SearchNode(root_stmt.children, stmt, offset)) {
554 throw LogicError("Node not found in tree");
555 }
556 return offset;
557 }
558
559 ObjectPool<Statement>& pool;
560 Statement root_stmt{FunctionTag{}};
561};
562
563Block* TryFindForwardBlock(const Statement& stmt) {
564 const Tree& tree{stmt.up->children};
565 const ConstNode end{tree.cend()};
566 ConstNode forward_node{std::next(Tree::s_iterator_to(stmt))};
567 while (forward_node != end && !HasChildren(forward_node->type)) {
568 if (forward_node->type == StatementType::Code) {
569 return forward_node->code;
570 }
571 ++forward_node;
572 }
573 return nullptr;
574}
575
576[[nodiscard]] U1 VisitExpr(IREmitter& ir, const Statement& stmt) {
577 switch (stmt.type) {
578 case StatementType::Identity:
579 return ir.Condition(stmt.guest_cond);
580 case StatementType::Not:
581 return ir.LogicalNot(U1{VisitExpr(ir, *stmt.op)});
582 case StatementType::Or:
583 return ir.LogicalOr(VisitExpr(ir, *stmt.op_a), VisitExpr(ir, *stmt.op_b));
584 case StatementType::Variable:
585 return ir.GetGotoVariable(stmt.id);
586 default:
587 throw NotImplementedException("Statement type {}", stmt.type);
588 }
589}
590
591class TranslatePass {
592public:
593 TranslatePass(ObjectPool<Inst>& inst_pool_, ObjectPool<Block>& block_pool_,
594 ObjectPool<Statement>& stmt_pool_, Statement& root_stmt,
595 const std::function<void(IR::Block*)>& func_, BlockList& block_list_)
596 : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, func{func_},
597 block_list{block_list_} {
598 Visit(root_stmt, nullptr, nullptr);
599 }
600
601private:
602 void Visit(Statement& parent, Block* continue_block, Block* break_block) {
603 Tree& tree{parent.children};
604 Block* current_block{nullptr};
605
606 for (auto it = tree.begin(); it != tree.end(); ++it) {
607 Statement& stmt{*it};
608 switch (stmt.type) {
609 case StatementType::Label:
610 // Labels can be ignored
611 break;
612 case StatementType::Code: {
613 if (current_block && current_block != stmt.code) {
614 IREmitter ir{*current_block};
615 ir.Branch(stmt.code);
616 }
617 current_block = stmt.code;
618 func(stmt.code);
619 block_list.push_back(stmt.code);
620 break;
621 }
622 case StatementType::SetVariable: {
623 if (!current_block) {
624 current_block = MergeBlock(parent, stmt);
625 }
626 IREmitter ir{*current_block};
627 ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op));
628 break;
629 }
630 case StatementType::If: {
631 if (!current_block) {
632 current_block = block_pool.Create(inst_pool);
633 block_list.push_back(current_block);
634 }
635 Block* const merge_block{MergeBlock(parent, stmt)};
636
637 // Visit children
638 const size_t first_block_index{block_list.size()};
639 Visit(stmt, merge_block, break_block);
640
641 // Implement if header block
642 Block* const first_if_block{block_list.at(first_block_index)};
643 IREmitter ir{*current_block};
644 const U1 cond{VisitExpr(ir, *stmt.cond)};
645 ir.SelectionMerge(merge_block);
646 ir.BranchConditional(cond, first_if_block, merge_block);
647
648 current_block = merge_block;
649 break;
650 }
651 case StatementType::Loop: {
652 Block* const loop_header_block{block_pool.Create(inst_pool)};
653 if (current_block) {
654 IREmitter{*current_block}.Branch(loop_header_block);
655 }
656 block_list.push_back(loop_header_block);
657
658 Block* const new_continue_block{block_pool.Create(inst_pool)};
659 Block* const merge_block{MergeBlock(parent, stmt)};
660
661 // Visit children
662 const size_t first_block_index{block_list.size()};
663 Visit(stmt, new_continue_block, merge_block);
664
665 // The continue block is located at the end of the loop
666 block_list.push_back(new_continue_block);
667
668 // Implement loop header block
669 Block* const first_loop_block{block_list.at(first_block_index)};
670 IREmitter ir{*loop_header_block};
671 ir.LoopMerge(merge_block, new_continue_block);
672 ir.Branch(first_loop_block);
673
674 // Implement continue block
675 IREmitter continue_ir{*new_continue_block};
676 const U1 continue_cond{VisitExpr(continue_ir, *stmt.cond)};
677 continue_ir.BranchConditional(continue_cond, ir.block, merge_block);
678
679 current_block = merge_block;
680 break;
681 }
682 case StatementType::Break: {
683 if (!current_block) {
684 current_block = block_pool.Create(inst_pool);
685 block_list.push_back(current_block);
686 }
687 Block* const skip_block{MergeBlock(parent, stmt)};
688
689 IREmitter ir{*current_block};
690 ir.BranchConditional(VisitExpr(ir, *stmt.cond), break_block, skip_block);
691
692 current_block = skip_block;
693 break;
694 }
695 case StatementType::Return: {
696 if (!current_block) {
697 current_block = block_pool.Create(inst_pool);
698 block_list.push_back(current_block);
699 }
700 IREmitter{*current_block}.Return();
701 current_block = nullptr;
702 break;
703 }
704 default:
705 throw NotImplementedException("Statement type {}", stmt.type);
706 }
707 }
708 if (current_block && continue_block) {
709 IREmitter ir{*current_block};
710 ir.Branch(continue_block);
711 }
712 }
713
714 Block* MergeBlock(Statement& parent, Statement& stmt) {
715 if (Block* const block{TryFindForwardBlock(stmt)}) {
716 return block;
717 }
718 // Create a merge block we can visit later
719 Block* const block{block_pool.Create(inst_pool)};
720 Statement* const merge_stmt{stmt_pool.Create(block, &parent)};
721 parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
722 return block;
723 }
724
725 ObjectPool<Statement>& stmt_pool;
726 ObjectPool<Inst>& inst_pool;
727 ObjectPool<Block>& block_pool;
728 const std::function<void(IR::Block*)>& func;
729 BlockList& block_list;
730};
731} // Anonymous namespace
732
733BlockList VisitAST(ObjectPool<Inst>& inst_pool, ObjectPool<Block>& block_pool,
734 std::span<Block* const> unordered_blocks,
735 const std::function<void(Block*)>& func) {
736 ObjectPool<Statement> stmt_pool{64};
737 GotoPass goto_pass{unordered_blocks, stmt_pool};
738 BlockList block_list;
739 TranslatePass translate_pass{inst_pool, block_pool, stmt_pool, goto_pass.RootStatement(),
740 func, block_list};
741 return block_list;
742}
743
744} // 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
deleted file mode 100644
index a574c24f7..000000000
--- a/src/shader_recompiler/frontend/ir/structured_control_flow.h
+++ /dev/null
@@ -1,22 +0,0 @@
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