From 71f96fa6366dc6dd306a953bca1b958fb32bc55a Mon Sep 17 00:00:00 2001
From: ReinUsesLisp <reinuseslisp@airmail.cc>
Date: Sun, 14 Mar 2021 03:41:05 -0300
Subject: shader: Implement CAL inlining function calls
---
.../frontend/maxwell/control_flow.cpp | 78 +--
.../frontend/maxwell/control_flow.h | 19 +-
src/shader_recompiler/frontend/maxwell/program.cpp | 71 +-
.../frontend/maxwell/structured_control_flow.cpp | 770 +++++++++++++++++++++
.../frontend/maxwell/structured_control_flow.h | 24 +
.../frontend/maxwell/translate/impl/impl.h | 2 +-
.../maxwell/translate/impl/not_implemented.cpp | 4 +-
7 files changed, 869 insertions(+), 99 deletions(-)
create mode 100644 src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
create mode 100644 src/shader_recompiler/frontend/maxwell/structured_control_flow.h
(limited to 'src/shader_recompiler/frontend/maxwell')
diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.cpp b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
index d0dc663307..715c0e92d8 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.cpp
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
@@ -31,13 +31,12 @@ struct Compare {
return lhs.begin < rhs.begin;
}
};
-} // Anonymous namespace
-static u32 BranchOffset(Location pc, Instruction inst) {
+u32 BranchOffset(Location pc, Instruction inst) {
return pc.Offset() + inst.branch.Offset() + 8;
}
-static void Split(Block* old_block, Block* new_block, Location pc) {
+void Split(Block* old_block, Block* new_block, Location pc) {
if (pc <= old_block->begin || pc >= old_block->end) {
throw InvalidArgument("Invalid address to split={}", pc);
}
@@ -49,21 +48,19 @@ static void Split(Block* old_block, Block* new_block, Location pc) {
.cond{old_block->cond},
.branch_true{old_block->branch_true},
.branch_false{old_block->branch_false},
- .ir{nullptr},
};
*old_block = Block{
.begin{old_block->begin},
.end{pc},
.end_class{EndClass::Branch},
.stack{std::move(old_block->stack)},
- .cond{IR::Condition{true}},
+ .cond{true},
.branch_true{new_block},
.branch_false{nullptr},
- .ir{nullptr},
};
}
-static Token OpcodeToken(Opcode opcode) {
+Token OpcodeToken(Opcode opcode) {
switch (opcode) {
case Opcode::PBK:
case Opcode::BRK:
@@ -89,7 +86,7 @@ static Token OpcodeToken(Opcode opcode) {
}
}
-static bool IsAbsoluteJump(Opcode opcode) {
+bool IsAbsoluteJump(Opcode opcode) {
switch (opcode) {
case Opcode::JCAL:
case Opcode::JMP:
@@ -100,7 +97,7 @@ static bool IsAbsoluteJump(Opcode opcode) {
}
}
-static bool HasFlowTest(Opcode opcode) {
+bool HasFlowTest(Opcode opcode) {
switch (opcode) {
case Opcode::BRA:
case Opcode::BRX:
@@ -121,13 +118,14 @@ static bool HasFlowTest(Opcode opcode) {
}
}
-static std::string NameOf(const Block& block) {
+std::string NameOf(const Block& block) {
if (block.begin.IsVirtual()) {
return fmt::format("\"Virtual {}\"", block.begin);
} else {
return fmt::format("\"{}\"", block.begin);
}
}
+} // Anonymous namespace
void Stack::Push(Token token, Location target) {
entries.push_back({
@@ -166,26 +164,24 @@ bool Block::Contains(Location pc) const noexcept {
return pc >= begin && pc < end;
}
-Function::Function(Location start_address)
+Function::Function(ObjectPool<Block>& block_pool, Location start_address)
: entrypoint{start_address}, labels{{
.address{start_address},
- .block{nullptr},
+ .block{block_pool.Create(Block{
+ .begin{start_address},
+ .end{start_address},
+ .end_class{EndClass::Branch},
+ .stack{},
+ .cond{true},
+ .branch_true{nullptr},
+ .branch_false{nullptr},
+ })},
.stack{},
}} {}
CFG::CFG(Environment& env_, ObjectPool<Block>& block_pool_, Location start_address)
: env{env_}, block_pool{block_pool_} {
- functions.emplace_back(start_address);
- functions.back().labels.back().block = block_pool.Create(Block{
- .begin{start_address},
- .end{start_address},
- .end_class{EndClass::Branch},
- .stack{},
- .cond{IR::Condition{true}},
- .branch_true{nullptr},
- .branch_false{nullptr},
- .ir{nullptr},
- });
+ functions.emplace_back(block_pool, start_address);
for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) {
while (!functions[function_id].labels.empty()) {
Function& function{functions[function_id]};
@@ -308,11 +304,17 @@ CFG::AnalysisState CFG::AnalyzeInst(Block* block, FunctionId function_id, Locati
const Location cal_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
// Technically CAL pushes into PRET, but that's implicit in the function call for us
// Insert the function into the list if it doesn't exist
- if (std::ranges::find(functions, cal_pc, &Function::entrypoint) == functions.end()) {
- functions.emplace_back(cal_pc);
+ const auto it{std::ranges::find(functions, cal_pc, &Function::entrypoint)};
+ const bool exists{it != functions.end()};
+ const FunctionId call_id{exists ? std::distance(functions.begin(), it) : functions.size()};
+ if (!exists) {
+ functions.emplace_back(block_pool, cal_pc);
}
- // Handle CAL like a regular instruction
- break;
+ block->end_class = EndClass::Call;
+ block->function_call = call_id;
+ block->return_block = AddLabel(block, block->stack, pc + 1, function_id);
+ block->end = pc;
+ return AnalysisState::Branch;
}
default:
break;
@@ -348,7 +350,6 @@ void CFG::AnalyzeCondInst(Block* block, FunctionId function_id, Location pc,
.cond{cond},
.branch_true{conditional_block},
.branch_false{nullptr},
- .ir{nullptr},
};
// Save the contents of the visited block in the conditional block
*conditional_block = std::move(*block);
@@ -401,16 +402,6 @@ void CFG::AnalyzeBRX(Block*, Location, Instruction, bool is_absolute) {
throw NotImplementedException("{}", is_absolute ? "JMX" : "BRX");
}
-void CFG::AnalyzeCAL(Location pc, Instruction inst, bool is_absolute) {
- const Location cal_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
- // Technically CAL pushes into PRET, but that's implicit in the function call for us
- // Insert the function to the function list if it doesn't exist
- const auto it{std::ranges::find(functions, cal_pc, &Function::entrypoint)};
- if (it == functions.end()) {
- functions.emplace_back(cal_pc);
- }
-}
-
CFG::AnalysisState CFG::AnalyzeEXIT(Block* block, FunctionId function_id, Location pc,
Instruction inst) {
const IR::FlowTest flow_test{inst.branch.flow_test};
@@ -455,10 +446,9 @@ Block* CFG::AddLabel(Block* block, Stack stack, Location pc, FunctionId function
.end{pc},
.end_class{EndClass::Branch},
.stack{stack},
- .cond{IR::Condition{true}},
+ .cond{true},
.branch_true{nullptr},
.branch_false{nullptr},
- .ir{nullptr},
})};
function.labels.push_back(Label{
.address{pc},
@@ -495,6 +485,14 @@ std::string CFG::Dot() const {
add_branch(block.branch_false, false);
}
break;
+ case EndClass::Call:
+ dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
+ dot += fmt::format("\t\tN{}->{};\n", node_uid, NameOf(*block.return_block));
+ dot += fmt::format("\t\tN{} [label=\"Call {}\"][shape=square][style=stripped];\n",
+ node_uid, block.function_call);
+ dot += '\n';
+ ++node_uid;
+ break;
case EndClass::Exit:
dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
dot += fmt::format("\t\tN{} [label=\"Exit\"][shape=square][style=stripped];\n",
diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.h b/src/shader_recompiler/frontend/maxwell/control_flow.h
index 209c9e5510..fe74f210fb 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.h
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.h
@@ -20,16 +20,13 @@
#include "shader_recompiler/frontend/maxwell/opcodes.h"
#include "shader_recompiler/object_pool.h"
-namespace Shader::IR {
-class Block;
-}
-
namespace Shader::Maxwell::Flow {
using FunctionId = size_t;
enum class EndClass {
Branch,
+ Call,
Exit,
Return,
};
@@ -75,9 +72,14 @@ struct Block : boost::intrusive::set_base_hook<
EndClass end_class;
Stack stack;
IR::Condition cond;
- Block* branch_true;
- Block* branch_false;
- IR::Block* ir;
+ union {
+ Block* branch_true;
+ FunctionId function_call;
+ };
+ union {
+ Block* branch_false;
+ Block* return_block;
+ };
};
struct Label {
@@ -87,7 +89,7 @@ struct Label {
};
struct Function {
- Function(Location start_address);
+ explicit Function(ObjectPool<Block>& block_pool, Location start_address);
Location entrypoint;
boost::container::small_vector<Label, 16> labels;
@@ -137,7 +139,6 @@ private:
void AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
bool is_absolute);
void AnalyzeBRX(Block* block, Location pc, Instruction inst, bool is_absolute);
- void AnalyzeCAL(Location pc, Instruction inst, bool is_absolute);
AnalysisState AnalyzeEXIT(Block* block, FunctionId function_id, Location pc, Instruction inst);
/// Return the branch target block id
diff --git a/src/shader_recompiler/frontend/maxwell/program.cpp b/src/shader_recompiler/frontend/maxwell/program.cpp
index b270bbccdb..8bfa643268 100644
--- a/src/shader_recompiler/frontend/maxwell/program.cpp
+++ b/src/shader_recompiler/frontend/maxwell/program.cpp
@@ -8,67 +8,44 @@
#include "shader_recompiler/frontend/ir/basic_block.h"
#include "shader_recompiler/frontend/ir/post_order.h"
-#include "shader_recompiler/frontend/ir/structured_control_flow.h"
#include "shader_recompiler/frontend/maxwell/program.h"
+#include "shader_recompiler/frontend/maxwell/structured_control_flow.h"
#include "shader_recompiler/frontend/maxwell/translate/translate.h"
#include "shader_recompiler/ir_opt/passes.h"
namespace Shader::Maxwell {
-namespace {
-IR::BlockList TranslateCode(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
- Environment& env, Flow::Function& cfg_function) {
- const size_t num_blocks{cfg_function.blocks.size()};
- std::vector<IR::Block*> blocks(cfg_function.blocks.size());
- std::ranges::for_each(cfg_function.blocks, [&, i = size_t{0}](auto& cfg_block) mutable {
- const u32 begin{cfg_block.begin.Offset()};
- const u32 end{cfg_block.end.Offset()};
- blocks[i] = block_pool.Create(inst_pool, begin, end);
- cfg_block.ir = blocks[i];
- ++i;
- });
- std::ranges::for_each(cfg_function.blocks, [&, i = size_t{0}](auto& cfg_block) mutable {
- IR::Block* const block{blocks[i]};
- ++i;
- if (cfg_block.end_class != Flow::EndClass::Branch) {
- block->SetReturn();
- } else if (cfg_block.cond == IR::Condition{true}) {
- block->SetBranch(cfg_block.branch_true->ir);
- } else if (cfg_block.cond == IR::Condition{false}) {
- block->SetBranch(cfg_block.branch_false->ir);
- } else {
- block->SetBranches(cfg_block.cond, cfg_block.branch_true->ir,
- cfg_block.branch_false->ir);
- }
+
+static void RemoveUnreachableBlocks(IR::Program& program) {
+ // Some blocks might be unreachable if a function call exists unconditionally
+ // If this happens the number of blocks and post order blocks will mismatch
+ if (program.blocks.size() == program.post_order_blocks.size()) {
+ return;
+ }
+ const IR::BlockList& post_order{program.post_order_blocks};
+ std::erase_if(program.blocks, [&](IR::Block* block) {
+ return std::ranges::find(post_order, block) == post_order.end();
});
- return IR::VisitAST(inst_pool, block_pool, blocks,
- [&](IR::Block* block) { Translate(env, block); });
}
-} // Anonymous namespace
IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
Environment& env, Flow::CFG& cfg) {
IR::Program program;
- auto& functions{program.functions};
- functions.reserve(cfg.Functions().size());
- for (Flow::Function& cfg_function : cfg.Functions()) {
- functions.push_back(IR::Function{
- .blocks{TranslateCode(inst_pool, block_pool, env, cfg_function)},
- .post_order_blocks{},
- });
- }
+ program.blocks = VisitAST(inst_pool, block_pool, env, cfg);
+ program.post_order_blocks = PostOrder(program.blocks);
+ RemoveUnreachableBlocks(program);
+
+ // Replace instructions before the SSA rewrite
Optimization::LowerFp16ToFp32(program);
- for (IR::Function& function : functions) {
- function.post_order_blocks = PostOrder(function.blocks);
- Optimization::SsaRewritePass(function.post_order_blocks);
- }
+
+ Optimization::SsaRewritePass(program);
+
Optimization::GlobalMemoryToStorageBufferPass(program);
Optimization::TexturePass(env, program);
- for (IR::Function& function : functions) {
- Optimization::PostOrderInvoke(Optimization::ConstantPropagationPass, function);
- Optimization::PostOrderInvoke(Optimization::DeadCodeEliminationPass, function);
- Optimization::IdentityRemovalPass(function);
- Optimization::VerificationPass(function);
- }
+
+ Optimization::ConstantPropagationPass(program);
+ Optimization::DeadCodeEliminationPass(program);
+ Optimization::IdentityRemovalPass(program);
+ Optimization::VerificationPass(program);
Optimization::CollectShaderInfoPass(program);
return program;
}
diff --git a/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp b/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
new file mode 100644
index 0000000000..5f5d9cf173
--- /dev/null
+++ b/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
@@ -0,0 +1,770 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include <algorithm>
+#include <memory>
+#include <ranges>
+#include <string>
+#include <unordered_map>
+#include <utility>
+#include <vector>
+
+#include <fmt/format.h>
+
+#include <boost/intrusive/list.hpp>
+
+#include "shader_recompiler/environment.h"
+#include "shader_recompiler/frontend/ir/basic_block.h"
+#include "shader_recompiler/frontend/ir/ir_emitter.h"
+#include "shader_recompiler/frontend/maxwell/structured_control_flow.h"
+#include "shader_recompiler/frontend/maxwell/translate/translate.h"
+#include "shader_recompiler/object_pool.h"
+
+namespace Shader::Maxwell {
+namespace {
+struct Statement;
+
+// Use normal_link because we are not guaranteed to destroy the tree in order
+using ListBaseHook =
+ boost::intrusive::list_base_hook<boost::intrusive::link_mode<boost::intrusive::normal_link>>;
+
+using Tree = boost::intrusive::list<Statement,
+ // Allow using Statement without a definition
+ boost::intrusive::base_hook<ListBaseHook>,
+ // Avoid linear complexity on splice, size is never called
+ boost::intrusive::constant_time_size<false>>;
+using Node = Tree::iterator;
+using ConstNode = Tree::const_iterator;
+
+enum class StatementType {
+ Code,
+ Goto,
+ Label,
+ If,
+ Loop,
+ Break,
+ Return,
+ Function,
+ Identity,
+ Not,
+ Or,
+ SetVariable,
+ Variable,
+};
+
+bool HasChildren(StatementType type) {
+ switch (type) {
+ case StatementType::If:
+ case StatementType::Loop:
+ case StatementType::Function:
+ return true;
+ default:
+ return false;
+ }
+}
+
+struct Goto {};
+struct Label {};
+struct If {};
+struct Loop {};
+struct Break {};
+struct Return {};
+struct FunctionTag {};
+struct Identity {};
+struct Not {};
+struct Or {};
+struct SetVariable {};
+struct Variable {};
+
+#ifdef _MSC_VER
+#pragma warning(push)
+#pragma warning(disable : 26495) // Always initialize a member variable, expected in Statement
+#endif
+struct Statement : ListBaseHook {
+ Statement(IR::Block* code_, Statement* up_) : code{code_}, up{up_}, type{StatementType::Code} {}
+ Statement(Goto, Statement* cond_, Node label_, Statement* up_)
+ : label{label_}, cond{cond_}, up{up_}, type{StatementType::Goto} {}
+ Statement(Label, u32 id_, Statement* up_) : id{id_}, up{up_}, type{StatementType::Label} {}
+ Statement(If, Statement* cond_, Tree&& children_, Statement* up_)
+ : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::If} {}
+ Statement(Loop, Statement* cond_, Tree&& children_, Statement* up_)
+ : children{std::move(children_)}, cond{cond_}, up{up_}, type{StatementType::Loop} {}
+ Statement(Break, Statement* cond_, Statement* up_)
+ : cond{cond_}, up{up_}, type{StatementType::Break} {}
+ Statement(Return) : type{StatementType::Return} {}
+ Statement(FunctionTag) : children{}, type{StatementType::Function} {}
+ Statement(Identity, IR::Condition cond_) : guest_cond{cond_}, type{StatementType::Identity} {}
+ Statement(Not, Statement* op_) : op{op_}, type{StatementType::Not} {}
+ Statement(Or, Statement* op_a_, Statement* op_b_)
+ : op_a{op_a_}, op_b{op_b_}, type{StatementType::Or} {}
+ Statement(SetVariable, u32 id_, Statement* op_, Statement* up_)
+ : op{op_}, id{id_}, up{up_}, type{StatementType::SetVariable} {}
+ Statement(Variable, u32 id_) : id{id_}, type{StatementType::Variable} {}
+
+ ~Statement() {
+ if (HasChildren(type)) {
+ std::destroy_at(&children);
+ }
+ }
+
+ union {
+ IR::Block* code;
+ Node label;
+ Tree children;
+ IR::Condition guest_cond;
+ Statement* op;
+ Statement* op_a;
+ };
+ union {
+ Statement* cond;
+ Statement* op_b;
+ u32 id;
+ };
+ Statement* up{};
+ StatementType type;
+};
+#ifdef _MSC_VER
+#pragma warning(pop)
+#endif
+
+std::string DumpExpr(const Statement* stmt) {
+ switch (stmt->type) {
+ case StatementType::Identity:
+ return fmt::format("{}", stmt->guest_cond);
+ case StatementType::Not:
+ return fmt::format("!{}", DumpExpr(stmt->op));
+ case StatementType::Or:
+ return fmt::format("{} || {}", DumpExpr(stmt->op_a), DumpExpr(stmt->op_b));
+ case StatementType::Variable:
+ return fmt::format("goto_L{}", stmt->id);
+ default:
+ return "<invalid type>";
+ }
+}
+
+std::string DumpTree(const Tree& tree, u32 indentation = 0) {
+ std::string ret;
+ std::string indent(indentation, ' ');
+ for (auto stmt = tree.begin(); stmt != tree.end(); ++stmt) {
+ switch (stmt->type) {
+ case StatementType::Code:
+ ret += fmt::format("{} Block {:04x};\n", indent, stmt->code->LocationBegin());
+ break;
+ case StatementType::Goto:
+ ret += fmt::format("{} if ({}) goto L{};\n", indent, DumpExpr(stmt->cond),
+ stmt->label->id);
+ break;
+ case StatementType::Label:
+ ret += fmt::format("{}L{}:\n", indent, stmt->id);
+ break;
+ case StatementType::If:
+ ret += fmt::format("{} if ({}) {{\n", indent, DumpExpr(stmt->cond));
+ ret += DumpTree(stmt->children, indentation + 4);
+ ret += fmt::format("{} }}\n", indent);
+ break;
+ case StatementType::Loop:
+ ret += fmt::format("{} do {{\n", indent);
+ ret += DumpTree(stmt->children, indentation + 4);
+ ret += fmt::format("{} }} while ({});\n", indent, DumpExpr(stmt->cond));
+ break;
+ case StatementType::Break:
+ ret += fmt::format("{} if ({}) break;\n", indent, DumpExpr(stmt->cond));
+ break;
+ case StatementType::Return:
+ ret += fmt::format("{} return;\n", indent);
+ break;
+ case StatementType::SetVariable:
+ ret += fmt::format("{} goto_L{} = {};\n", indent, stmt->id, DumpExpr(stmt->op));
+ break;
+ case StatementType::Function:
+ case StatementType::Identity:
+ case StatementType::Not:
+ case StatementType::Or:
+ case StatementType::Variable:
+ throw LogicError("Statement can't be printed");
+ }
+ }
+ return ret;
+}
+
+bool HasNode(const Tree& tree, ConstNode stmt) {
+ const auto end{tree.end()};
+ for (auto it = tree.begin(); it != end; ++it) {
+ if (it == stmt || (HasChildren(it->type) && HasNode(it->children, stmt))) {
+ return true;
+ }
+ }
+ return false;
+}
+
+Node FindStatementWithLabel(Tree& tree, ConstNode goto_stmt) {
+ const ConstNode label_stmt{goto_stmt->label};
+ const ConstNode end{tree.end()};
+ for (auto it = tree.begin(); it != end; ++it) {
+ if (it == label_stmt || (HasChildren(it->type) && HasNode(it->children, label_stmt))) {
+ return it;
+ }
+ }
+ throw LogicError("Lift label not in tree");
+}
+
+void SanitizeNoBreaks(const Tree& tree) {
+ if (std::ranges::find(tree, StatementType::Break, &Statement::type) != tree.end()) {
+ throw NotImplementedException("Capturing statement with break nodes");
+ }
+}
+
+size_t Level(Node stmt) {
+ size_t level{0};
+ Statement* node{stmt->up};
+ while (node) {
+ ++level;
+ node = node->up;
+ }
+ return level;
+}
+
+bool IsDirectlyRelated(Node goto_stmt, Node label_stmt) {
+ const size_t goto_level{Level(goto_stmt)};
+ const size_t label_level{Level(label_stmt)};
+ size_t min_level;
+ size_t max_level;
+ Node min;
+ Node max;
+ if (label_level < goto_level) {
+ min_level = label_level;
+ max_level = goto_level;
+ min = label_stmt;
+ max = goto_stmt;
+ } else { // goto_level < label_level
+ min_level = goto_level;
+ max_level = label_level;
+ min = goto_stmt;
+ max = label_stmt;
+ }
+ while (max_level > min_level) {
+ --max_level;
+ max = max->up;
+ }
+ return min->up == max->up;
+}
+
+bool IsIndirectlyRelated(Node goto_stmt, Node label_stmt) {
+ return goto_stmt->up != label_stmt->up && !IsDirectlyRelated(goto_stmt, label_stmt);
+}
+
+bool SearchNode(const Tree& tree, ConstNode stmt, size_t& offset) {
+ ++offset;
+
+ const auto end = tree.end();
+ for (ConstNode it = tree.begin(); it != end; ++it) {
+ ++offset;
+ if (stmt == it) {
+ return true;
+ }
+ if (HasChildren(it->type) && SearchNode(it->children, stmt, offset)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+class GotoPass {
+public:
+ explicit GotoPass(Flow::CFG& cfg, ObjectPool<IR::Inst>& inst_pool_,
+ ObjectPool<IR::Block>& block_pool_, ObjectPool<Statement>& stmt_pool)
+ : inst_pool{inst_pool_}, block_pool{block_pool_}, pool{stmt_pool} {
+ std::vector gotos{BuildTree(cfg)};
+ for (const Node& goto_stmt : gotos | std::views::reverse) {
+ RemoveGoto(goto_stmt);
+ }
+ }
+
+ Statement& RootStatement() noexcept {
+ return root_stmt;
+ }
+
+private:
+ void RemoveGoto(Node goto_stmt) {
+ // Force goto_stmt and label_stmt to be directly related
+ const Node label_stmt{goto_stmt->label};
+ if (IsIndirectlyRelated(goto_stmt, label_stmt)) {
+ // Move goto_stmt out using outward-movement transformation until it becomes
+ // directly related to label_stmt
+ while (!IsDirectlyRelated(goto_stmt, label_stmt)) {
+ goto_stmt = MoveOutward(goto_stmt);
+ }
+ }
+ // Force goto_stmt and label_stmt to be siblings
+ if (IsDirectlyRelated(goto_stmt, label_stmt)) {
+ const size_t label_level{Level(label_stmt)};
+ size_t goto_level{Level(goto_stmt)};
+ if (goto_level > label_level) {
+ // Move goto_stmt out of its level using outward-movement transformations
+ while (goto_level > label_level) {
+ goto_stmt = MoveOutward(goto_stmt);
+ --goto_level;
+ }
+ } else { // Level(goto_stmt) < Level(label_stmt)
+ if (Offset(goto_stmt) > Offset(label_stmt)) {
+ // Lift goto_stmt to above stmt containing label_stmt using goto-lifting
+ // transformations
+ goto_stmt = Lift(goto_stmt);
+ }
+ // Move goto_stmt into label_stmt's level using inward-movement transformation
+ while (goto_level < label_level) {
+ goto_stmt = MoveInward(goto_stmt);
+ ++goto_level;
+ }
+ }
+ }
+ // TODO: Remove this
+ {
+ Node it{goto_stmt};
+ bool sibling{false};
+ do {
+ sibling |= it == label_stmt;
+ --it;
+ } while (it != goto_stmt->up->children.begin());
+ while (it != goto_stmt->up->children.end()) {
+ sibling |= it == label_stmt;
+ ++it;
+ }
+ if (!sibling) {
+ throw LogicError("Not siblings");
+ }
+ }
+ // goto_stmt and label_stmt are guaranteed to be siblings, eliminate
+ if (std::next(goto_stmt) == label_stmt) {
+ // Simply eliminate the goto if the label is next to it
+ goto_stmt->up->children.erase(goto_stmt);
+ } else if (Offset(goto_stmt) < Offset(label_stmt)) {
+ // Eliminate goto_stmt with a conditional
+ EliminateAsConditional(goto_stmt, label_stmt);
+ } else {
+ // Eliminate goto_stmt with a loop
+ EliminateAsLoop(goto_stmt, label_stmt);
+ }
+ }
+
+ std::vector<Node> BuildTree(Flow::CFG& cfg) {
+ u32 label_id{0};
+ std::vector<Node> gotos;
+ Flow::Function& first_function{cfg.Functions().front()};
+ BuildTree(cfg, first_function, label_id, gotos, root_stmt.children.end(), std::nullopt);
+ return gotos;
+ }
+
+ void BuildTree(Flow::CFG& cfg, Flow::Function& function, u32& label_id,
+ std::vector<Node>& gotos, Node function_insert_point,
+ std::optional<Node> return_label) {
+ Statement* const false_stmt{pool.Create(Identity{}, IR::Condition{false})};
+ Tree& root{root_stmt.children};
+ std::unordered_map<Flow::Block*, Node> local_labels;
+ local_labels.reserve(function.blocks.size());
+
+ for (Flow::Block& block : function.blocks) {
+ Statement* const label{pool.Create(Label{}, label_id, &root_stmt)};
+ const Node label_it{root.insert(function_insert_point, *label)};
+ local_labels.emplace(&block, label_it);
+ ++label_id;
+ }
+ for (Flow::Block& block : function.blocks) {
+ const Node label{local_labels.at(&block)};
+ // Insertion point
+ const Node ip{std::next(label)};
+
+ // Reset goto variables before the first block and after its respective label
+ const auto make_reset_variable{[&]() -> Statement& {
+ return *pool.Create(SetVariable{}, label->id, false_stmt, &root_stmt);
+ }};
+ root.push_front(make_reset_variable());
+ root.insert(ip, make_reset_variable());
+
+ const u32 begin_offset{block.begin.Offset()};
+ const u32 end_offset{block.end.Offset()};
+ IR::Block* const ir_block{block_pool.Create(inst_pool, begin_offset, end_offset)};
+ root.insert(ip, *pool.Create(ir_block, &root_stmt));
+
+ switch (block.end_class) {
+ case Flow::EndClass::Branch: {
+ Statement* const always_cond{pool.Create(Identity{}, IR::Condition{true})};
+ if (block.cond == IR::Condition{true}) {
+ const Node true_label{local_labels.at(block.branch_true)};
+ gotos.push_back(
+ root.insert(ip, *pool.Create(Goto{}, always_cond, true_label, &root_stmt)));
+ } else if (block.cond == IR::Condition{false}) {
+ const Node false_label{local_labels.at(block.branch_false)};
+ gotos.push_back(root.insert(
+ ip, *pool.Create(Goto{}, always_cond, false_label, &root_stmt)));
+ } else {
+ const Node true_label{local_labels.at(block.branch_true)};
+ const Node false_label{local_labels.at(block.branch_false)};
+ Statement* const true_cond{pool.Create(Identity{}, block.cond)};
+ gotos.push_back(
+ root.insert(ip, *pool.Create(Goto{}, true_cond, true_label, &root_stmt)));
+ gotos.push_back(root.insert(
+ ip, *pool.Create(Goto{}, always_cond, false_label, &root_stmt)));
+ }
+ break;
+ }
+ case Flow::EndClass::Call: {
+ Flow::Function& call{cfg.Functions()[block.function_call]};
+ const Node call_return_label{local_labels.at(block.return_block)};
+ BuildTree(cfg, call, label_id, gotos, ip, call_return_label);
+ break;
+ }
+ case Flow::EndClass::Exit:
+ root.insert(ip, *pool.Create(Return{}));
+ break;
+ case Flow::EndClass::Return: {
+ Statement* const always_cond{pool.Create(Identity{}, block.cond)};
+ auto goto_stmt{pool.Create(Goto{}, always_cond, return_label.value(), &root_stmt)};
+ gotos.push_back(root.insert(ip, *goto_stmt));
+ break;
+ }
+ }
+ }
+ }
+
+ void UpdateTreeUp(Statement* tree) {
+ for (Statement& stmt : tree->children) {
+ stmt.up = tree;
+ }
+ }
+
+ void EliminateAsConditional(Node goto_stmt, Node label_stmt) {
+ Tree& body{goto_stmt->up->children};
+ Tree if_body;
+ if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_stmt);
+ Statement* const cond{pool.Create(Not{}, goto_stmt->cond)};
+ Statement* const if_stmt{pool.Create(If{}, cond, std::move(if_body), goto_stmt->up)};
+ UpdateTreeUp(if_stmt);
+ body.insert(goto_stmt, *if_stmt);
+ body.erase(goto_stmt);
+ }
+
+ void EliminateAsLoop(Node goto_stmt, Node label_stmt) {
+ Tree& body{goto_stmt->up->children};
+ Tree loop_body;
+ loop_body.splice(loop_body.begin(), body, label_stmt, goto_stmt);
+ Statement* const cond{goto_stmt->cond};
+ Statement* const loop{pool.Create(Loop{}, cond, std::move(loop_body), goto_stmt->up)};
+ UpdateTreeUp(loop);
+ body.insert(goto_stmt, *loop);
+ body.erase(goto_stmt);
+ }
+
+ [[nodiscard]] Node MoveOutward(Node goto_stmt) {
+ switch (goto_stmt->up->type) {
+ case StatementType::If:
+ return MoveOutwardIf(goto_stmt);
+ case StatementType::Loop:
+ return MoveOutwardLoop(goto_stmt);
+ default:
+ throw LogicError("Invalid outward movement");
+ }
+ }
+
+ [[nodiscard]] Node MoveInward(Node goto_stmt) {
+ Statement* const parent{goto_stmt->up};
+ Tree& body{parent->children};
+ const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
+ const Node label{goto_stmt->label};
+ const u32 label_id{label->id};
+
+ Statement* const goto_cond{goto_stmt->cond};
+ Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
+ body.insert(goto_stmt, *set_var);
+
+ Tree if_body;
+ if_body.splice(if_body.begin(), body, std::next(goto_stmt), label_nested_stmt);
+ Statement* const variable{pool.Create(Variable{}, label_id)};
+ Statement* const neg_var{pool.Create(Not{}, variable)};
+ if (!if_body.empty()) {
+ Statement* const if_stmt{pool.Create(If{}, neg_var, std::move(if_body), parent)};
+ UpdateTreeUp(if_stmt);
+ body.insert(goto_stmt, *if_stmt);
+ }
+ body.erase(goto_stmt);
+
+ switch (label_nested_stmt->type) {
+ case StatementType::If:
+ // Update nested if condition
+ label_nested_stmt->cond = pool.Create(Or{}, variable, label_nested_stmt->cond);
+ break;
+ case StatementType::Loop:
+ break;
+ default:
+ throw LogicError("Invalid inward movement");
+ }
+ Tree& nested_tree{label_nested_stmt->children};
+ Statement* const new_goto{pool.Create(Goto{}, variable, label, &*label_nested_stmt)};
+ return nested_tree.insert(nested_tree.begin(), *new_goto);
+ }
+
+ [[nodiscard]] Node Lift(Node goto_stmt) {
+ Statement* const parent{goto_stmt->up};
+ Tree& body{parent->children};
+ const Node label{goto_stmt->label};
+ const u32 label_id{label->id};
+ const Node label_nested_stmt{FindStatementWithLabel(body, goto_stmt)};
+ const auto type{label_nested_stmt->type};
+
+ Tree loop_body;
+ loop_body.splice(loop_body.begin(), body, label_nested_stmt, goto_stmt);
+ SanitizeNoBreaks(loop_body);
+ Statement* const variable{pool.Create(Variable{}, label_id)};
+ Statement* const loop_stmt{pool.Create(Loop{}, variable, std::move(loop_body), parent)};
+ UpdateTreeUp(loop_stmt);
+ const Node loop_node{body.insert(goto_stmt, *loop_stmt)};
+
+ Statement* const new_goto{pool.Create(Goto{}, variable, label, loop_stmt)};
+ loop_stmt->children.push_front(*new_goto);
+ const Node new_goto_node{loop_stmt->children.begin()};
+
+ Statement* const set_var{pool.Create(SetVariable{}, label_id, goto_stmt->cond, loop_stmt)};
+ loop_stmt->children.push_back(*set_var);
+
+ body.erase(goto_stmt);
+ return new_goto_node;
+ }
+
+ Node MoveOutwardIf(Node goto_stmt) {
+ const Node parent{Tree::s_iterator_to(*goto_stmt->up)};
+ Tree& body{parent->children};
+ const u32 label_id{goto_stmt->label->id};
+ Statement* const goto_cond{goto_stmt->cond};
+ Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, &*parent)};
+ body.insert(goto_stmt, *set_goto_var);
+
+ Tree if_body;
+ if_body.splice(if_body.begin(), body, std::next(goto_stmt), body.end());
+ if_body.pop_front();
+ Statement* const cond{pool.Create(Variable{}, label_id)};
+ Statement* const neg_cond{pool.Create(Not{}, cond)};
+ Statement* const if_stmt{pool.Create(If{}, neg_cond, std::move(if_body), &*parent)};
+ UpdateTreeUp(if_stmt);
+ body.insert(goto_stmt, *if_stmt);
+
+ body.erase(goto_stmt);
+
+ Statement* const new_cond{pool.Create(Variable{}, label_id)};
+ Statement* const new_goto{pool.Create(Goto{}, new_cond, goto_stmt->label, parent->up)};
+ Tree& parent_tree{parent->up->children};
+ return parent_tree.insert(std::next(parent), *new_goto);
+ }
+
+ Node MoveOutwardLoop(Node goto_stmt) {
+ Statement* const parent{goto_stmt->up};
+ Tree& body{parent->children};
+ const u32 label_id{goto_stmt->label->id};
+ Statement* const goto_cond{goto_stmt->cond};
+ Statement* const set_goto_var{pool.Create(SetVariable{}, label_id, goto_cond, parent)};
+ Statement* const cond{pool.Create(Variable{}, label_id)};
+ Statement* const break_stmt{pool.Create(Break{}, cond, parent)};
+ body.insert(goto_stmt, *set_goto_var);
+ body.insert(goto_stmt, *break_stmt);
+ body.erase(goto_stmt);
+
+ const Node loop{Tree::s_iterator_to(*goto_stmt->up)};
+ Statement* const new_goto_cond{pool.Create(Variable{}, label_id)};
+ Statement* const new_goto{pool.Create(Goto{}, new_goto_cond, goto_stmt->label, loop->up)};
+ Tree& parent_tree{loop->up->children};
+ return parent_tree.insert(std::next(loop), *new_goto);
+ }
+
+ size_t Offset(ConstNode stmt) const {
+ size_t offset{0};
+ if (!SearchNode(root_stmt.children, stmt, offset)) {
+ throw LogicError("Node not found in tree");
+ }
+ return offset;
+ }
+
+ ObjectPool<IR::Inst>& inst_pool;
+ ObjectPool<IR::Block>& block_pool;
+ ObjectPool<Statement>& pool;
+ Statement root_stmt{FunctionTag{}};
+};
+
+IR::Block* TryFindForwardBlock(const Statement& stmt) {
+ const Tree& tree{stmt.up->children};
+ const ConstNode end{tree.cend()};
+ ConstNode forward_node{std::next(Tree::s_iterator_to(stmt))};
+ while (forward_node != end && !HasChildren(forward_node->type)) {
+ if (forward_node->type == StatementType::Code) {
+ return forward_node->code;
+ }
+ ++forward_node;
+ }
+ return nullptr;
+}
+
+[[nodiscard]] IR::U1 VisitExpr(IR::IREmitter& ir, const Statement& stmt) {
+ switch (stmt.type) {
+ case StatementType::Identity:
+ return ir.Condition(stmt.guest_cond);
+ case StatementType::Not:
+ return ir.LogicalNot(IR::U1{VisitExpr(ir, *stmt.op)});
+ case StatementType::Or:
+ return ir.LogicalOr(VisitExpr(ir, *stmt.op_a), VisitExpr(ir, *stmt.op_b));
+ case StatementType::Variable:
+ return ir.GetGotoVariable(stmt.id);
+ default:
+ throw NotImplementedException("Statement type {}", stmt.type);
+ }
+}
+
+class TranslatePass {
+public:
+ TranslatePass(ObjectPool<IR::Inst>& inst_pool_, ObjectPool<IR::Block>& block_pool_,
+ ObjectPool<Statement>& stmt_pool_, Environment& env_, Statement& root_stmt,
+ IR::BlockList& block_list_)
+ : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, env{env_},
+ block_list{block_list_} {
+ Visit(root_stmt, nullptr, nullptr);
+ }
+
+private:
+ void Visit(Statement& parent, IR::Block* continue_block, IR::Block* break_block) {
+ Tree& tree{parent.children};
+ IR::Block* current_block{nullptr};
+
+ for (auto it = tree.begin(); it != tree.end(); ++it) {
+ Statement& stmt{*it};
+ switch (stmt.type) {
+ case StatementType::Label:
+ // Labels can be ignored
+ break;
+ case StatementType::Code: {
+ if (current_block && current_block != stmt.code) {
+ IR::IREmitter{*current_block}.Branch(stmt.code);
+ }
+ current_block = stmt.code;
+ Translate(env, stmt.code);
+ block_list.push_back(stmt.code);
+ break;
+ }
+ case StatementType::SetVariable: {
+ if (!current_block) {
+ current_block = MergeBlock(parent, stmt);
+ }
+ IR::IREmitter ir{*current_block};
+ ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op));
+ break;
+ }
+ case StatementType::If: {
+ if (!current_block) {
+ current_block = block_pool.Create(inst_pool);
+ block_list.push_back(current_block);
+ }
+ IR::Block* const merge_block{MergeBlock(parent, stmt)};
+
+ // Visit children
+ const size_t first_block_index{block_list.size()};
+ Visit(stmt, merge_block, break_block);
+
+ // Implement if header block
+ IR::Block* const first_if_block{block_list.at(first_block_index)};
+ IR::IREmitter ir{*current_block};
+ const IR::U1 cond{VisitExpr(ir, *stmt.cond)};
+ ir.SelectionMerge(merge_block);
+ ir.BranchConditional(cond, first_if_block, merge_block);
+
+ current_block = merge_block;
+ break;
+ }
+ case StatementType::Loop: {
+ IR::Block* const loop_header_block{block_pool.Create(inst_pool)};
+ if (current_block) {
+ IR::IREmitter{*current_block}.Branch(loop_header_block);
+ }
+ block_list.push_back(loop_header_block);
+
+ IR::Block* const new_continue_block{block_pool.Create(inst_pool)};
+ IR::Block* const merge_block{MergeBlock(parent, stmt)};
+
+ // Visit children
+ const size_t first_block_index{block_list.size()};
+ Visit(stmt, new_continue_block, merge_block);
+
+ // The continue block is located at the end of the loop
+ block_list.push_back(new_continue_block);
+
+ // Implement loop header block
+ IR::Block* const first_loop_block{block_list.at(first_block_index)};
+ IR::IREmitter ir{*loop_header_block};
+ ir.LoopMerge(merge_block, new_continue_block);
+ ir.Branch(first_loop_block);
+
+ // Implement continue block
+ IR::IREmitter continue_ir{*new_continue_block};
+ const IR::U1 continue_cond{VisitExpr(continue_ir, *stmt.cond)};
+ continue_ir.BranchConditional(continue_cond, ir.block, merge_block);
+
+ current_block = merge_block;
+ break;
+ }
+ case StatementType::Break: {
+ if (!current_block) {
+ current_block = block_pool.Create(inst_pool);
+ block_list.push_back(current_block);
+ }
+ IR::Block* const skip_block{MergeBlock(parent, stmt)};
+
+ IR::IREmitter ir{*current_block};
+ ir.BranchConditional(VisitExpr(ir, *stmt.cond), break_block, skip_block);
+
+ current_block = skip_block;
+ break;
+ }
+ case StatementType::Return: {
+ if (!current_block) {
+ current_block = block_pool.Create(inst_pool);
+ block_list.push_back(current_block);
+ }
+ IR::IREmitter{*current_block}.Return();
+ current_block = nullptr;
+ break;
+ }
+ default:
+ throw NotImplementedException("Statement type {}", stmt.type);
+ }
+ }
+ if (current_block && continue_block) {
+ IR::IREmitter{*current_block}.Branch(continue_block);
+ }
+ }
+
+ IR::Block* MergeBlock(Statement& parent, Statement& stmt) {
+ if (IR::Block* const block{TryFindForwardBlock(stmt)}) {
+ return block;
+ }
+ // Create a merge block we can visit later
+ IR::Block* const block{block_pool.Create(inst_pool)};
+ Statement* const merge_stmt{stmt_pool.Create(block, &parent)};
+ parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
+ return block;
+ }
+
+ ObjectPool<Statement>& stmt_pool;
+ ObjectPool<IR::Inst>& inst_pool;
+ ObjectPool<IR::Block>& block_pool;
+ Environment& env;
+ IR::BlockList& block_list;
+};
+} // Anonymous namespace
+
+IR::BlockList VisitAST(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
+ Environment& env, Flow::CFG& cfg) {
+ ObjectPool<Statement> stmt_pool{64};
+ GotoPass goto_pass{cfg, inst_pool, block_pool, stmt_pool};
+ Statement& root{goto_pass.RootStatement()};
+ IR::BlockList block_list;
+ TranslatePass{inst_pool, block_pool, stmt_pool, env, root, block_list};
+ return block_list;
+}
+
+} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/structured_control_flow.h b/src/shader_recompiler/frontend/maxwell/structured_control_flow.h
new file mode 100644
index 0000000000..e4797291e2
--- /dev/null
+++ b/src/shader_recompiler/frontend/maxwell/structured_control_flow.h
@@ -0,0 +1,24 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include <functional>
+#include <span>
+
+#include <boost/intrusive/list.hpp>
+
+#include "shader_recompiler/environment.h"
+#include "shader_recompiler/frontend/ir/basic_block.h"
+#include "shader_recompiler/frontend/ir/microinstruction.h"
+#include "shader_recompiler/frontend/maxwell/control_flow.h"
+#include "shader_recompiler/object_pool.h"
+
+namespace Shader::Maxwell {
+
+[[nodiscard]] IR::BlockList VisitAST(ObjectPool<IR::Inst>& inst_pool,
+ ObjectPool<IR::Block>& block_pool, Environment& env,
+ Flow::CFG& cfg);
+
+} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/translate/impl/impl.h b/src/shader_recompiler/frontend/maxwell/translate/impl/impl.h
index c6253c40c1..45d6f5e060 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/impl/impl.h
+++ b/src/shader_recompiler/frontend/maxwell/translate/impl/impl.h
@@ -62,7 +62,7 @@ public:
void BRA(u64 insn);
void BRK(u64 insn);
void BRX(u64 insn);
- void CAL(u64 insn);
+ void CAL();
void CCTL(u64 insn);
void CCTLL(u64 insn);
void CONT(u64 insn);
diff --git a/src/shader_recompiler/frontend/maxwell/translate/impl/not_implemented.cpp b/src/shader_recompiler/frontend/maxwell/translate/impl/not_implemented.cpp
index 01ecbb4cc7..92da5c7e83 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/impl/not_implemented.cpp
+++ b/src/shader_recompiler/frontend/maxwell/translate/impl/not_implemented.cpp
@@ -65,8 +65,8 @@ void TranslatorVisitor::BRX(u64) {
ThrowNotImplemented(Opcode::BRX);
}
-void TranslatorVisitor::CAL(u64) {
- ThrowNotImplemented(Opcode::CAL);
+void TranslatorVisitor::CAL() {
+ // CAL is a no-op
}
void TranslatorVisitor::CCTL(u64) {
--
cgit v1.2.3-70-g09d2