summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/shader_recompiler/CMakeLists.txt4
-rw-r--r--src/shader_recompiler/backend/spirv/emit_spirv.cpp45
-rw-r--r--src/shader_recompiler/backend/spirv/emit_spirv.h18
-rw-r--r--src/shader_recompiler/backend/spirv/emit_spirv_context_get_set.cpp8
-rw-r--r--src/shader_recompiler/backend/spirv/emit_spirv_control_flow.cpp25
-rw-r--r--src/shader_recompiler/backend/spirv/emit_spirv_undefined.cpp12
-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
-rw-r--r--src/shader_recompiler/frontend/maxwell/control_flow.cpp426
-rw-r--r--src/shader_recompiler/frontend/maxwell/control_flow.h77
-rw-r--r--src/shader_recompiler/frontend/maxwell/location.h12
-rw-r--r--src/shader_recompiler/frontend/maxwell/program.cpp69
-rw-r--r--src/shader_recompiler/frontend/maxwell/program.h2
-rw-r--r--src/shader_recompiler/frontend/maxwell/termination_code.cpp86
-rw-r--r--src/shader_recompiler/frontend/maxwell/termination_code.h17
-rw-r--r--src/shader_recompiler/frontend/maxwell/translate/impl/integer_shift_left.cpp2
-rw-r--r--src/shader_recompiler/frontend/maxwell/translate/translate.cpp17
-rw-r--r--src/shader_recompiler/frontend/maxwell/translate/translate.h7
-rw-r--r--src/shader_recompiler/ir_opt/constant_propagation_pass.cpp50
-rw-r--r--src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp24
-rw-r--r--src/shader_recompiler/ir_opt/verification_pass.cpp4
-rw-r--r--src/shader_recompiler/main.cpp29
-rw-r--r--src/shader_recompiler/shader_info.h28
32 files changed, 1345 insertions, 589 deletions
diff --git a/src/shader_recompiler/CMakeLists.txt b/src/shader_recompiler/CMakeLists.txt
index 12fbcb37c..27fc79e21 100644
--- a/src/shader_recompiler/CMakeLists.txt
+++ b/src/shader_recompiler/CMakeLists.txt
@@ -36,6 +36,8 @@ add_executable(shader_recompiler
36 frontend/ir/program.cpp 36 frontend/ir/program.cpp
37 frontend/ir/program.h 37 frontend/ir/program.h
38 frontend/ir/reg.h 38 frontend/ir/reg.h
39 frontend/ir/structured_control_flow.cpp
40 frontend/ir/structured_control_flow.h
39 frontend/ir/type.cpp 41 frontend/ir/type.cpp
40 frontend/ir/type.h 42 frontend/ir/type.h
41 frontend/ir/value.cpp 43 frontend/ir/value.cpp
@@ -51,8 +53,6 @@ add_executable(shader_recompiler
51 frontend/maxwell/opcodes.h 53 frontend/maxwell/opcodes.h
52 frontend/maxwell/program.cpp 54 frontend/maxwell/program.cpp
53 frontend/maxwell/program.h 55 frontend/maxwell/program.h
54 frontend/maxwell/termination_code.cpp
55 frontend/maxwell/termination_code.h
56 frontend/maxwell/translate/impl/common_encoding.h 56 frontend/maxwell/translate/impl/common_encoding.h
57 frontend/maxwell/translate/impl/floating_point_add.cpp 57 frontend/maxwell/translate/impl/floating_point_add.cpp
58 frontend/maxwell/translate/impl/floating_point_conversion_integer.cpp 58 frontend/maxwell/translate/impl/floating_point_conversion_integer.cpp
diff --git a/src/shader_recompiler/backend/spirv/emit_spirv.cpp b/src/shader_recompiler/backend/spirv/emit_spirv.cpp
index 7c4269fad..5022b5159 100644
--- a/src/shader_recompiler/backend/spirv/emit_spirv.cpp
+++ b/src/shader_recompiler/backend/spirv/emit_spirv.cpp
@@ -105,8 +105,26 @@ void EmitSPIRV::EmitInst(EmitContext& ctx, IR::Inst* inst) {
105 throw LogicError("Invalid opcode {}", inst->Opcode()); 105 throw LogicError("Invalid opcode {}", inst->Opcode());
106} 106}
107 107
108void EmitSPIRV::EmitPhi(EmitContext&) { 108static Id TypeId(const EmitContext& ctx, IR::Type type) {
109 throw NotImplementedException("SPIR-V Instruction"); 109 switch (type) {
110 case IR::Type::U1:
111 return ctx.u1;
112 default:
113 throw NotImplementedException("Phi node type {}", type);
114 }
115}
116
117Id EmitSPIRV::EmitPhi(EmitContext& ctx, IR::Inst* inst) {
118 const size_t num_args{inst->NumArgs()};
119 boost::container::small_vector<Id, 64> operands;
120 operands.reserve(num_args * 2);
121 for (size_t index = 0; index < num_args; ++index) {
122 IR::Block* const phi_block{inst->PhiBlock(index)};
123 operands.push_back(ctx.Def(inst->Arg(index)));
124 operands.push_back(ctx.BlockLabel(phi_block));
125 }
126 const Id result_type{TypeId(ctx, inst->Arg(0).Type())};
127 return ctx.OpPhi(result_type, std::span(operands.data(), operands.size()));
110} 128}
111 129
112void EmitSPIRV::EmitVoid(EmitContext&) {} 130void EmitSPIRV::EmitVoid(EmitContext&) {}
@@ -115,6 +133,29 @@ void EmitSPIRV::EmitIdentity(EmitContext&) {
115 throw NotImplementedException("SPIR-V Instruction"); 133 throw NotImplementedException("SPIR-V Instruction");
116} 134}
117 135
136// FIXME: Move to its own file
137void EmitSPIRV::EmitBranch(EmitContext& ctx, IR::Inst* inst) {
138 ctx.OpBranch(ctx.BlockLabel(inst->Arg(0).Label()));
139}
140
141void EmitSPIRV::EmitBranchConditional(EmitContext& ctx, IR::Inst* inst) {
142 ctx.OpBranchConditional(ctx.Def(inst->Arg(0)), ctx.BlockLabel(inst->Arg(1).Label()),
143 ctx.BlockLabel(inst->Arg(2).Label()));
144}
145
146void EmitSPIRV::EmitLoopMerge(EmitContext& ctx, IR::Inst* inst) {
147 ctx.OpLoopMerge(ctx.BlockLabel(inst->Arg(0).Label()), ctx.BlockLabel(inst->Arg(1).Label()),
148 spv::LoopControlMask::MaskNone);
149}
150
151void EmitSPIRV::EmitSelectionMerge(EmitContext& ctx, IR::Inst* inst) {
152 ctx.OpSelectionMerge(ctx.BlockLabel(inst->Arg(0).Label()), spv::SelectionControlMask::MaskNone);
153}
154
155void EmitSPIRV::EmitReturn(EmitContext& ctx) {
156 ctx.OpReturn();
157}
158
118void EmitSPIRV::EmitGetZeroFromOp(EmitContext&) { 159void EmitSPIRV::EmitGetZeroFromOp(EmitContext&) {
119 throw LogicError("Unreachable instruction"); 160 throw LogicError("Unreachable instruction");
120} 161}
diff --git a/src/shader_recompiler/backend/spirv/emit_spirv.h b/src/shader_recompiler/backend/spirv/emit_spirv.h
index 3f4b68a7d..9aa83b5de 100644
--- a/src/shader_recompiler/backend/spirv/emit_spirv.h
+++ b/src/shader_recompiler/backend/spirv/emit_spirv.h
@@ -124,18 +124,20 @@ private:
124 void EmitInst(EmitContext& ctx, IR::Inst* inst); 124 void EmitInst(EmitContext& ctx, IR::Inst* inst);
125 125
126 // Microinstruction emitters 126 // Microinstruction emitters
127 void EmitPhi(EmitContext& ctx); 127 Id EmitPhi(EmitContext& ctx, IR::Inst* inst);
128 void EmitVoid(EmitContext& ctx); 128 void EmitVoid(EmitContext& ctx);
129 void EmitIdentity(EmitContext& ctx); 129 void EmitIdentity(EmitContext& ctx);
130 void EmitBranch(EmitContext& ctx, IR::Inst* inst); 130 void EmitBranch(EmitContext& ctx, IR::Inst* inst);
131 void EmitBranchConditional(EmitContext& ctx, IR::Inst* inst); 131 void EmitBranchConditional(EmitContext& ctx, IR::Inst* inst);
132 void EmitExit(EmitContext& ctx); 132 void EmitLoopMerge(EmitContext& ctx, IR::Inst* inst);
133 void EmitSelectionMerge(EmitContext& ctx, IR::Inst* inst);
133 void EmitReturn(EmitContext& ctx); 134 void EmitReturn(EmitContext& ctx);
134 void EmitUnreachable(EmitContext& ctx);
135 void EmitGetRegister(EmitContext& ctx); 135 void EmitGetRegister(EmitContext& ctx);
136 void EmitSetRegister(EmitContext& ctx); 136 void EmitSetRegister(EmitContext& ctx);
137 void EmitGetPred(EmitContext& ctx); 137 void EmitGetPred(EmitContext& ctx);
138 void EmitSetPred(EmitContext& ctx); 138 void EmitSetPred(EmitContext& ctx);
139 void EmitSetGotoVariable(EmitContext& ctx);
140 void EmitGetGotoVariable(EmitContext& ctx);
139 Id EmitGetCbuf(EmitContext& ctx, const IR::Value& binding, const IR::Value& offset); 141 Id EmitGetCbuf(EmitContext& ctx, const IR::Value& binding, const IR::Value& offset);
140 void EmitGetAttribute(EmitContext& ctx); 142 void EmitGetAttribute(EmitContext& ctx);
141 void EmitSetAttribute(EmitContext& ctx); 143 void EmitSetAttribute(EmitContext& ctx);
@@ -151,11 +153,11 @@ private:
151 void EmitSetOFlag(EmitContext& ctx); 153 void EmitSetOFlag(EmitContext& ctx);
152 Id EmitWorkgroupId(EmitContext& ctx); 154 Id EmitWorkgroupId(EmitContext& ctx);
153 Id EmitLocalInvocationId(EmitContext& ctx); 155 Id EmitLocalInvocationId(EmitContext& ctx);
154 void EmitUndef1(EmitContext& ctx); 156 Id EmitUndefU1(EmitContext& ctx);
155 void EmitUndef8(EmitContext& ctx); 157 void EmitUndefU8(EmitContext& ctx);
156 void EmitUndef16(EmitContext& ctx); 158 void EmitUndefU16(EmitContext& ctx);
157 void EmitUndef32(EmitContext& ctx); 159 void EmitUndefU32(EmitContext& ctx);
158 void EmitUndef64(EmitContext& ctx); 160 void EmitUndefU64(EmitContext& ctx);
159 void EmitLoadGlobalU8(EmitContext& ctx); 161 void EmitLoadGlobalU8(EmitContext& ctx);
160 void EmitLoadGlobalS8(EmitContext& ctx); 162 void EmitLoadGlobalS8(EmitContext& ctx);
161 void EmitLoadGlobalU16(EmitContext& ctx); 163 void EmitLoadGlobalU16(EmitContext& ctx);
diff --git a/src/shader_recompiler/backend/spirv/emit_spirv_context_get_set.cpp b/src/shader_recompiler/backend/spirv/emit_spirv_context_get_set.cpp
index b121305ea..1eab739ed 100644
--- a/src/shader_recompiler/backend/spirv/emit_spirv_context_get_set.cpp
+++ b/src/shader_recompiler/backend/spirv/emit_spirv_context_get_set.cpp
@@ -22,6 +22,14 @@ void EmitSPIRV::EmitSetPred(EmitContext&) {
22 throw NotImplementedException("SPIR-V Instruction"); 22 throw NotImplementedException("SPIR-V Instruction");
23} 23}
24 24
25void EmitSPIRV::EmitSetGotoVariable(EmitContext&) {
26 throw NotImplementedException("SPIR-V Instruction");
27}
28
29void EmitSPIRV::EmitGetGotoVariable(EmitContext&) {
30 throw NotImplementedException("SPIR-V Instruction");
31}
32
25Id EmitSPIRV::EmitGetCbuf(EmitContext& ctx, const IR::Value& binding, const IR::Value& offset) { 33Id EmitSPIRV::EmitGetCbuf(EmitContext& ctx, const IR::Value& binding, const IR::Value& offset) {
26 if (!binding.IsImmediate()) { 34 if (!binding.IsImmediate()) {
27 throw NotImplementedException("Constant buffer indexing"); 35 throw NotImplementedException("Constant buffer indexing");
diff --git a/src/shader_recompiler/backend/spirv/emit_spirv_control_flow.cpp b/src/shader_recompiler/backend/spirv/emit_spirv_control_flow.cpp
index 770fe113c..66ce6c8c5 100644
--- a/src/shader_recompiler/backend/spirv/emit_spirv_control_flow.cpp
+++ b/src/shader_recompiler/backend/spirv/emit_spirv_control_flow.cpp
@@ -3,28 +3,3 @@
3// Refer to the license.txt file included. 3// Refer to the license.txt file included.
4 4
5#include "shader_recompiler/backend/spirv/emit_spirv.h" 5#include "shader_recompiler/backend/spirv/emit_spirv.h"
6
7namespace Shader::Backend::SPIRV {
8
9void EmitSPIRV::EmitBranch(EmitContext& ctx, IR::Inst* inst) {
10 ctx.OpBranch(ctx.BlockLabel(inst->Arg(0).Label()));
11}
12
13void EmitSPIRV::EmitBranchConditional(EmitContext& ctx, IR::Inst* inst) {
14 ctx.OpBranchConditional(ctx.Def(inst->Arg(0)), ctx.BlockLabel(inst->Arg(1).Label()),
15 ctx.BlockLabel(inst->Arg(2).Label()));
16}
17
18void EmitSPIRV::EmitExit(EmitContext& ctx) {
19 ctx.OpReturn();
20}
21
22void EmitSPIRV::EmitReturn(EmitContext&) {
23 throw NotImplementedException("SPIR-V Instruction");
24}
25
26void EmitSPIRV::EmitUnreachable(EmitContext&) {
27 throw NotImplementedException("SPIR-V Instruction");
28}
29
30} // namespace Shader::Backend::SPIRV
diff --git a/src/shader_recompiler/backend/spirv/emit_spirv_undefined.cpp b/src/shader_recompiler/backend/spirv/emit_spirv_undefined.cpp
index 3850b072c..859b60a95 100644
--- a/src/shader_recompiler/backend/spirv/emit_spirv_undefined.cpp
+++ b/src/shader_recompiler/backend/spirv/emit_spirv_undefined.cpp
@@ -6,23 +6,23 @@
6 6
7namespace Shader::Backend::SPIRV { 7namespace Shader::Backend::SPIRV {
8 8
9void EmitSPIRV::EmitUndef1(EmitContext&) { 9Id EmitSPIRV::EmitUndefU1(EmitContext& ctx) {
10 throw NotImplementedException("SPIR-V Instruction"); 10 return ctx.OpUndef(ctx.u1);
11} 11}
12 12
13void EmitSPIRV::EmitUndef8(EmitContext&) { 13void EmitSPIRV::EmitUndefU8(EmitContext&) {
14 throw NotImplementedException("SPIR-V Instruction"); 14 throw NotImplementedException("SPIR-V Instruction");
15} 15}
16 16
17void EmitSPIRV::EmitUndef16(EmitContext&) { 17void EmitSPIRV::EmitUndefU16(EmitContext&) {
18 throw NotImplementedException("SPIR-V Instruction"); 18 throw NotImplementedException("SPIR-V Instruction");
19} 19}
20 20
21void EmitSPIRV::EmitUndef32(EmitContext&) { 21void EmitSPIRV::EmitUndefU32(EmitContext&) {
22 throw NotImplementedException("SPIR-V Instruction"); 22 throw NotImplementedException("SPIR-V Instruction");
23} 23}
24 24
25void EmitSPIRV::EmitUndef64(EmitContext&) { 25void EmitSPIRV::EmitUndefU64(EmitContext&) {
26 throw NotImplementedException("SPIR-V Instruction"); 26 throw NotImplementedException("SPIR-V Instruction");
27} 27}
28 28
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
diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.cpp b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
index 21ee98137..e766b555b 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.cpp
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.cpp
@@ -17,38 +17,49 @@
17#include "shader_recompiler/frontend/maxwell/location.h" 17#include "shader_recompiler/frontend/maxwell/location.h"
18 18
19namespace Shader::Maxwell::Flow { 19namespace Shader::Maxwell::Flow {
20namespace {
21struct Compare {
22 bool operator()(const Block& lhs, Location rhs) const noexcept {
23 return lhs.begin < rhs;
24 }
25
26 bool operator()(Location lhs, const Block& rhs) const noexcept {
27 return lhs < rhs.begin;
28 }
29
30 bool operator()(const Block& lhs, const Block& rhs) const noexcept {
31 return lhs.begin < rhs.begin;
32 }
33};
34} // Anonymous namespace
20 35
21static u32 BranchOffset(Location pc, Instruction inst) { 36static u32 BranchOffset(Location pc, Instruction inst) {
22 return pc.Offset() + inst.branch.Offset() + 8; 37 return pc.Offset() + inst.branch.Offset() + 8;
23} 38}
24 39
25static std::array<Block, 2> Split(Block&& block, Location pc, BlockId new_id) { 40static void Split(Block* old_block, Block* new_block, Location pc) {
26 if (pc <= block.begin || pc >= block.end) { 41 if (pc <= old_block->begin || pc >= old_block->end) {
27 throw InvalidArgument("Invalid address to split={}", pc); 42 throw InvalidArgument("Invalid address to split={}", pc);
28 } 43 }
29 return { 44 *new_block = Block{
30 Block{ 45 .begin{pc},
31 .begin{block.begin}, 46 .end{old_block->end},
32 .end{pc}, 47 .end_class{old_block->end_class},
33 .end_class{EndClass::Branch}, 48 .stack{old_block->stack},
34 .id{block.id}, 49 .cond{old_block->cond},
35 .stack{block.stack}, 50 .branch_true{old_block->branch_true},
36 .cond{true}, 51 .branch_false{old_block->branch_false},
37 .branch_true{new_id}, 52 .ir{nullptr},
38 .branch_false{UNREACHABLE_BLOCK_ID}, 53 };
39 .imm_predecessors{}, 54 *old_block = Block{
40 }, 55 .begin{old_block->begin},
41 Block{ 56 .end{pc},
42 .begin{pc}, 57 .end_class{EndClass::Branch},
43 .end{block.end}, 58 .stack{std::move(old_block->stack)},
44 .end_class{block.end_class}, 59 .cond{IR::Condition{true}},
45 .id{new_id}, 60 .branch_true{new_block},
46 .stack{std::move(block.stack)}, 61 .branch_false{nullptr},
47 .cond{block.cond}, 62 .ir{nullptr},
48 .branch_true{block.branch_true},
49 .branch_false{block.branch_false},
50 .imm_predecessors{},
51 },
52 }; 63 };
53} 64}
54 65
@@ -112,7 +123,7 @@ static bool HasFlowTest(Opcode opcode) {
112 123
113static std::string NameOf(const Block& block) { 124static std::string NameOf(const Block& block) {
114 if (block.begin.IsVirtual()) { 125 if (block.begin.IsVirtual()) {
115 return fmt::format("\"Virtual {}\"", block.id); 126 return fmt::format("\"Virtual {}\"", block.begin);
116 } else { 127 } else {
117 return fmt::format("\"{}\"", block.begin); 128 return fmt::format("\"{}\"", block.begin);
118 } 129 }
@@ -158,126 +169,23 @@ bool Block::Contains(Location pc) const noexcept {
158Function::Function(Location start_address) 169Function::Function(Location start_address)
159 : entrypoint{start_address}, labels{{ 170 : entrypoint{start_address}, labels{{
160 .address{start_address}, 171 .address{start_address},
161 .block_id{0}, 172 .block{nullptr},
162 .stack{}, 173 .stack{},
163 }} {} 174 }} {}
164 175
165void Function::BuildBlocksMap() { 176CFG::CFG(Environment& env_, ObjectPool<Block>& block_pool_, Location start_address)
166 const size_t num_blocks{NumBlocks()}; 177 : env{env_}, block_pool{block_pool_} {
167 blocks_map.resize(num_blocks);
168 for (size_t block_index = 0; block_index < num_blocks; ++block_index) {
169 Block& block{blocks_data[block_index]};
170 blocks_map[block.id] = &block;
171 }
172}
173
174void Function::BuildImmediatePredecessors() {
175 for (const Block& block : blocks_data) {
176 if (block.branch_true != UNREACHABLE_BLOCK_ID) {
177 blocks_map[block.branch_true]->imm_predecessors.push_back(block.id);
178 }
179 if (block.branch_false != UNREACHABLE_BLOCK_ID) {
180 blocks_map[block.branch_false]->imm_predecessors.push_back(block.id);
181 }
182 }
183}
184
185void Function::BuildPostOrder() {
186 boost::container::small_vector<BlockId, 0x110> block_stack;
187 post_order_map.resize(NumBlocks());
188
189 Block& first_block{blocks_data[blocks.front()]};
190 first_block.post_order_visited = true;
191 block_stack.push_back(first_block.id);
192
193 const auto visit_branch = [&](BlockId block_id, BlockId branch_id) {
194 if (branch_id == UNREACHABLE_BLOCK_ID) {
195 return false;
196 }
197 if (blocks_map[branch_id]->post_order_visited) {
198 return false;
199 }
200 blocks_map[branch_id]->post_order_visited = true;
201
202 // Calling push_back twice is faster than insert on msvc
203 block_stack.push_back(block_id);
204 block_stack.push_back(branch_id);
205 return true;
206 };
207 while (!block_stack.empty()) {
208 const Block* const block{blocks_map[block_stack.back()]};
209 block_stack.pop_back();
210
211 if (!visit_branch(block->id, block->branch_true) &&
212 !visit_branch(block->id, block->branch_false)) {
213 post_order_map[block->id] = static_cast<u32>(post_order_blocks.size());
214 post_order_blocks.push_back(block->id);
215 }
216 }
217}
218
219void Function::BuildImmediateDominators() {
220 auto transform_block_id{std::views::transform([this](BlockId id) { return blocks_map[id]; })};
221 auto reverse_order_but_first{std::views::reverse | std::views::drop(1) | transform_block_id};
222 auto has_idom{std::views::filter([](Block* block) { return block->imm_dominator; })};
223 auto intersect{[this](Block* finger1, Block* finger2) {
224 while (finger1 != finger2) {
225 while (post_order_map[finger1->id] < post_order_map[finger2->id]) {
226 finger1 = finger1->imm_dominator;
227 }
228 while (post_order_map[finger2->id] < post_order_map[finger1->id]) {
229 finger2 = finger2->imm_dominator;
230 }
231 }
232 return finger1;
233 }};
234 for (Block& block : blocks_data) {
235 block.imm_dominator = nullptr;
236 }
237 Block* const start_block{&blocks_data[blocks.front()]};
238 start_block->imm_dominator = start_block;
239
240 bool changed{true};
241 while (changed) {
242 changed = false;
243 for (Block* const block : post_order_blocks | reverse_order_but_first) {
244 Block* new_idom{};
245 for (Block* predecessor : block->imm_predecessors | transform_block_id | has_idom) {
246 new_idom = new_idom ? intersect(predecessor, new_idom) : predecessor;
247 }
248 changed |= block->imm_dominator != new_idom;
249 block->imm_dominator = new_idom;
250 }
251 }
252}
253
254void Function::BuildDominanceFrontier() {
255 auto transform_block_id{std::views::transform([this](BlockId id) { return blocks_map[id]; })};
256 auto has_enough_predecessors{[](Block& block) { return block.imm_predecessors.size() >= 2; }};
257 for (Block& block : blocks_data | std::views::filter(has_enough_predecessors)) {
258 for (Block* current : block.imm_predecessors | transform_block_id) {
259 while (current != block.imm_dominator) {
260 current->dominance_frontiers.push_back(current->id);
261 current = current->imm_dominator;
262 }
263 }
264 }
265}
266
267CFG::CFG(Environment& env_, Location start_address) : env{env_} {
268 VisitFunctions(start_address);
269
270 for (Function& function : functions) {
271 function.BuildBlocksMap();
272 function.BuildImmediatePredecessors();
273 function.BuildPostOrder();
274 function.BuildImmediateDominators();
275 function.BuildDominanceFrontier();
276 }
277}
278
279void CFG::VisitFunctions(Location start_address) {
280 functions.emplace_back(start_address); 178 functions.emplace_back(start_address);
179 functions.back().labels.back().block = block_pool.Create(Block{
180 .begin{start_address},
181 .end{start_address},
182 .end_class{EndClass::Branch},
183 .stack{},
184 .cond{IR::Condition{true}},
185 .branch_true{nullptr},
186 .branch_false{nullptr},
187 .ir{nullptr},
188 });
281 for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) { 189 for (FunctionId function_id = 0; function_id < functions.size(); ++function_id) {
282 while (!functions[function_id].labels.empty()) { 190 while (!functions[function_id].labels.empty()) {
283 Function& function{functions[function_id]}; 191 Function& function{functions[function_id]};
@@ -294,35 +202,16 @@ void CFG::AnalyzeLabel(FunctionId function_id, Label& label) {
294 return; 202 return;
295 } 203 }
296 // Try to find the next block 204 // Try to find the next block
297 Function* function{&functions[function_id]}; 205 Function* const function{&functions[function_id]};
298 Location pc{label.address}; 206 Location pc{label.address};
299 const auto next{std::upper_bound(function->blocks.begin(), function->blocks.end(), pc, 207 const auto next_it{function->blocks.upper_bound(pc, Compare{})};
300 [function](Location pc, u32 block_index) { 208 const bool is_last{next_it == function->blocks.end()};
301 return pc < function->blocks_data[block_index].begin; 209 Block* const next{is_last ? nullptr : &*next_it};
302 })};
303 const auto next_index{std::distance(function->blocks.begin(), next)};
304 const bool is_last{next == function->blocks.end()};
305 Location next_pc;
306 BlockId next_id{UNREACHABLE_BLOCK_ID};
307 if (!is_last) {
308 next_pc = function->blocks_data[*next].begin;
309 next_id = function->blocks_data[*next].id;
310 }
311 // Insert before the next block 210 // Insert before the next block
312 Block block{ 211 Block* const block{label.block};
313 .begin{pc},
314 .end{pc},
315 .end_class{EndClass::Branch},
316 .id{label.block_id},
317 .stack{std::move(label.stack)},
318 .cond{true},
319 .branch_true{UNREACHABLE_BLOCK_ID},
320 .branch_false{UNREACHABLE_BLOCK_ID},
321 .imm_predecessors{},
322 };
323 // Analyze instructions until it reaches an already visited block or there's a branch 212 // Analyze instructions until it reaches an already visited block or there's a branch
324 bool is_branch{false}; 213 bool is_branch{false};
325 while (is_last || pc < next_pc) { 214 while (!next || pc < next->begin) {
326 is_branch = AnalyzeInst(block, function_id, pc) == AnalysisState::Branch; 215 is_branch = AnalyzeInst(block, function_id, pc) == AnalysisState::Branch;
327 if (is_branch) { 216 if (is_branch) {
328 break; 217 break;
@@ -332,43 +221,36 @@ void CFG::AnalyzeLabel(FunctionId function_id, Label& label) {
332 if (!is_branch) { 221 if (!is_branch) {
333 // If the block finished without a branch, 222 // If the block finished without a branch,
334 // it means that the next instruction is already visited, jump to it 223 // it means that the next instruction is already visited, jump to it
335 block.end = pc; 224 block->end = pc;
336 block.cond = true; 225 block->cond = IR::Condition{true};
337 block.branch_true = next_id; 226 block->branch_true = next;
338 block.branch_false = UNREACHABLE_BLOCK_ID; 227 block->branch_false = nullptr;
339 } 228 }
340 // Function's pointer might be invalid, resolve it again 229 // Function's pointer might be invalid, resolve it again
341 function = &functions[function_id]; 230 // Insert the new block
342 const u32 new_block_index = static_cast<u32>(function->blocks_data.size()); 231 functions[function_id].blocks.insert(*block);
343 function->blocks.insert(function->blocks.begin() + next_index, new_block_index);
344 function->blocks_data.push_back(std::move(block));
345} 232}
346 233
347bool CFG::InspectVisitedBlocks(FunctionId function_id, const Label& label) { 234bool CFG::InspectVisitedBlocks(FunctionId function_id, const Label& label) {
348 const Location pc{label.address}; 235 const Location pc{label.address};
349 Function& function{functions[function_id]}; 236 Function& function{functions[function_id]};
350 const auto it{std::ranges::find_if(function.blocks, [&function, pc](u32 block_index) { 237 const auto it{
351 return function.blocks_data[block_index].Contains(pc); 238 std::ranges::find_if(function.blocks, [pc](auto& block) { return block.Contains(pc); })};
352 })};
353 if (it == function.blocks.end()) { 239 if (it == function.blocks.end()) {
354 // Address has not been visited 240 // Address has not been visited
355 return false; 241 return false;
356 } 242 }
357 Block& block{function.blocks_data[*it]}; 243 Block* const visited_block{&*it};
358 if (block.begin == pc) { 244 if (visited_block->begin == pc) {
359 throw LogicError("Dangling branch"); 245 throw LogicError("Dangling block");
360 } 246 }
361 const u32 first_index{*it}; 247 Block* const new_block{label.block};
362 const u32 second_index{static_cast<u32>(function.blocks_data.size())}; 248 Split(visited_block, new_block, pc);
363 const std::array new_indices{first_index, second_index}; 249 function.blocks.insert(it, *new_block);
364 std::array split_blocks{Split(std::move(block), pc, label.block_id)};
365 function.blocks_data[*it] = std::move(split_blocks[0]);
366 function.blocks_data.push_back(std::move(split_blocks[1]));
367 function.blocks.insert(function.blocks.erase(it), new_indices.begin(), new_indices.end());
368 return true; 250 return true;
369} 251}
370 252
371CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Location pc) { 253CFG::AnalysisState CFG::AnalyzeInst(Block* block, FunctionId function_id, Location pc) {
372 const Instruction inst{env.ReadInstruction(pc.Offset())}; 254 const Instruction inst{env.ReadInstruction(pc.Offset())};
373 const Opcode opcode{Decode(inst.raw)}; 255 const Opcode opcode{Decode(inst.raw)};
374 switch (opcode) { 256 switch (opcode) {
@@ -390,12 +272,12 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
390 AnalyzeBRX(block, pc, inst, IsAbsoluteJump(opcode)); 272 AnalyzeBRX(block, pc, inst, IsAbsoluteJump(opcode));
391 break; 273 break;
392 case Opcode::RET: 274 case Opcode::RET:
393 block.end_class = EndClass::Return; 275 block->end_class = EndClass::Return;
394 break; 276 break;
395 default: 277 default:
396 break; 278 break;
397 } 279 }
398 block.end = pc; 280 block->end = pc;
399 return AnalysisState::Branch; 281 return AnalysisState::Branch;
400 case Opcode::BRK: 282 case Opcode::BRK:
401 case Opcode::CONT: 283 case Opcode::CONT:
@@ -404,9 +286,9 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
404 if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) { 286 if (!AnalyzeBranch(block, function_id, pc, inst, opcode)) {
405 return AnalysisState::Continue; 287 return AnalysisState::Continue;
406 } 288 }
407 const auto [stack_pc, new_stack]{block.stack.Pop(OpcodeToken(opcode))}; 289 const auto [stack_pc, new_stack]{block->stack.Pop(OpcodeToken(opcode))};
408 block.branch_true = AddLabel(block, new_stack, stack_pc, function_id); 290 block->branch_true = AddLabel(block, new_stack, stack_pc, function_id);
409 block.end = pc; 291 block->end = pc;
410 return AnalysisState::Branch; 292 return AnalysisState::Branch;
411 } 293 }
412 case Opcode::PBK: 294 case Opcode::PBK:
@@ -414,7 +296,7 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
414 case Opcode::PEXIT: 296 case Opcode::PEXIT:
415 case Opcode::PLONGJMP: 297 case Opcode::PLONGJMP:
416 case Opcode::SSY: 298 case Opcode::SSY:
417 block.stack.Push(OpcodeToken(opcode), BranchOffset(pc, inst)); 299 block->stack.Push(OpcodeToken(opcode), BranchOffset(pc, inst));
418 return AnalysisState::Continue; 300 return AnalysisState::Continue;
419 case Opcode::EXIT: 301 case Opcode::EXIT:
420 return AnalyzeEXIT(block, function_id, pc, inst); 302 return AnalyzeEXIT(block, function_id, pc, inst);
@@ -444,51 +326,51 @@ CFG::AnalysisState CFG::AnalyzeInst(Block& block, FunctionId function_id, Locati
444 return AnalysisState::Branch; 326 return AnalysisState::Branch;
445} 327}
446 328
447void CFG::AnalyzeCondInst(Block& block, FunctionId function_id, Location pc, 329void CFG::AnalyzeCondInst(Block* block, FunctionId function_id, Location pc,
448 EndClass insn_end_class, IR::Condition cond) { 330 EndClass insn_end_class, IR::Condition cond) {
449 if (block.begin != pc) { 331 if (block->begin != pc) {
450 // If the block doesn't start in the conditional instruction 332 // If the block doesn't start in the conditional instruction
451 // mark it as a label to visit it later 333 // mark it as a label to visit it later
452 block.end = pc; 334 block->end = pc;
453 block.cond = true; 335 block->cond = IR::Condition{true};
454 block.branch_true = AddLabel(block, block.stack, pc, function_id); 336 block->branch_true = AddLabel(block, block->stack, pc, function_id);
455 block.branch_false = UNREACHABLE_BLOCK_ID; 337 block->branch_false = nullptr;
456 return; 338 return;
457 } 339 }
458 // Impersonate the visited block with a virtual block 340 // Create a virtual block and a conditional block
459 // Jump from this virtual to the real conditional instruction and the next instruction 341 Block* const conditional_block{block_pool.Create()};
460 Function& function{functions[function_id]}; 342 Block virtual_block{
461 const BlockId conditional_block_id{++function.current_block_id}; 343 .begin{block->begin.Virtual()},
462 function.blocks.push_back(static_cast<u32>(function.blocks_data.size())); 344 .end{block->begin.Virtual()},
463 Block& virtual_block{function.blocks_data.emplace_back(Block{
464 .begin{}, // Virtual block
465 .end{},
466 .end_class{EndClass::Branch}, 345 .end_class{EndClass::Branch},
467 .id{block.id}, // Impersonating 346 .stack{block->stack},
468 .stack{block.stack},
469 .cond{cond}, 347 .cond{cond},
470 .branch_true{conditional_block_id}, 348 .branch_true{conditional_block},
471 .branch_false{UNREACHABLE_BLOCK_ID}, 349 .branch_false{nullptr},
472 .imm_predecessors{}, 350 .ir{nullptr},
473 })}; 351 };
474 // Set the end properties of the conditional instruction and give it a new identity 352 // Save the contents of the visited block in the conditional block
475 Block& conditional_block{block}; 353 *conditional_block = std::move(*block);
476 conditional_block.end = pc; 354 // Impersonate the visited block with a virtual block
477 conditional_block.end_class = insn_end_class; 355 *block = std::move(virtual_block);
478 conditional_block.id = conditional_block_id; 356 // Set the end properties of the conditional instruction
357 conditional_block->end = pc;
358 conditional_block->end_class = insn_end_class;
479 // Add a label to the instruction after the conditional instruction 359 // Add a label to the instruction after the conditional instruction
480 const BlockId endif_block_id{AddLabel(conditional_block, block.stack, pc + 1, function_id)}; 360 Block* const endif_block{AddLabel(conditional_block, block->stack, pc + 1, function_id)};
481 // Branch to the next instruction from the virtual block 361 // Branch to the next instruction from the virtual block
482 virtual_block.branch_false = endif_block_id; 362 block->branch_false = endif_block;
483 // And branch to it from the conditional instruction if it is a branch 363 // And branch to it from the conditional instruction if it is a branch
484 if (insn_end_class == EndClass::Branch) { 364 if (insn_end_class == EndClass::Branch) {
485 conditional_block.cond = true; 365 conditional_block->cond = IR::Condition{true};
486 conditional_block.branch_true = endif_block_id; 366 conditional_block->branch_true = endif_block;
487 conditional_block.branch_false = UNREACHABLE_BLOCK_ID; 367 conditional_block->branch_false = nullptr;
488 } 368 }
369 // Finally insert the condition block into the list of blocks
370 functions[function_id].blocks.insert(*conditional_block);
489} 371}
490 372
491bool CFG::AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instruction inst, 373bool CFG::AnalyzeBranch(Block* block, FunctionId function_id, Location pc, Instruction inst,
492 Opcode opcode) { 374 Opcode opcode) {
493 if (inst.branch.is_cbuf) { 375 if (inst.branch.is_cbuf) {
494 throw NotImplementedException("Branch with constant buffer offset"); 376 throw NotImplementedException("Branch with constant buffer offset");
@@ -500,21 +382,21 @@ bool CFG::AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instr
500 const bool has_flow_test{HasFlowTest(opcode)}; 382 const bool has_flow_test{HasFlowTest(opcode)};
501 const IR::FlowTest flow_test{has_flow_test ? inst.branch.flow_test.Value() : IR::FlowTest::T}; 383 const IR::FlowTest flow_test{has_flow_test ? inst.branch.flow_test.Value() : IR::FlowTest::T};
502 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) { 384 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
503 block.cond = IR::Condition(flow_test, static_cast<IR::Pred>(pred.index), pred.negated); 385 block->cond = IR::Condition(flow_test, static_cast<IR::Pred>(pred.index), pred.negated);
504 block.branch_false = AddLabel(block, block.stack, pc + 1, function_id); 386 block->branch_false = AddLabel(block, block->stack, pc + 1, function_id);
505 } else { 387 } else {
506 block.cond = true; 388 block->cond = IR::Condition{true};
507 } 389 }
508 return true; 390 return true;
509} 391}
510 392
511void CFG::AnalyzeBRA(Block& block, FunctionId function_id, Location pc, Instruction inst, 393void CFG::AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
512 bool is_absolute) { 394 bool is_absolute) {
513 const Location bra_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)}; 395 const Location bra_pc{is_absolute ? inst.branch.Absolute() : BranchOffset(pc, inst)};
514 block.branch_true = AddLabel(block, block.stack, bra_pc, function_id); 396 block->branch_true = AddLabel(block, block->stack, bra_pc, function_id);
515} 397}
516 398
517void CFG::AnalyzeBRX(Block&, Location, Instruction, bool is_absolute) { 399void CFG::AnalyzeBRX(Block*, Location, Instruction, bool is_absolute) {
518 throw NotImplementedException("{}", is_absolute ? "JMX" : "BRX"); 400 throw NotImplementedException("{}", is_absolute ? "JMX" : "BRX");
519} 401}
520 402
@@ -528,7 +410,7 @@ void CFG::AnalyzeCAL(Location pc, Instruction inst, bool is_absolute) {
528 } 410 }
529} 411}
530 412
531CFG::AnalysisState CFG::AnalyzeEXIT(Block& block, FunctionId function_id, Location pc, 413CFG::AnalysisState CFG::AnalyzeEXIT(Block* block, FunctionId function_id, Location pc,
532 Instruction inst) { 414 Instruction inst) {
533 const IR::FlowTest flow_test{inst.branch.flow_test}; 415 const IR::FlowTest flow_test{inst.branch.flow_test};
534 const Predicate pred{inst.Pred()}; 416 const Predicate pred{inst.Pred()};
@@ -537,41 +419,52 @@ CFG::AnalysisState CFG::AnalyzeEXIT(Block& block, FunctionId function_id, Locati
537 return AnalysisState::Continue; 419 return AnalysisState::Continue;
538 } 420 }
539 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) { 421 if (pred != Predicate{true} || flow_test != IR::FlowTest::T) {
540 if (block.stack.Peek(Token::PEXIT).has_value()) { 422 if (block->stack.Peek(Token::PEXIT).has_value()) {
541 throw NotImplementedException("Conditional EXIT with PEXIT token"); 423 throw NotImplementedException("Conditional EXIT with PEXIT token");
542 } 424 }
543 const IR::Condition cond{flow_test, static_cast<IR::Pred>(pred.index), pred.negated}; 425 const IR::Condition cond{flow_test, static_cast<IR::Pred>(pred.index), pred.negated};
544 AnalyzeCondInst(block, function_id, pc, EndClass::Exit, cond); 426 AnalyzeCondInst(block, function_id, pc, EndClass::Exit, cond);
545 return AnalysisState::Branch; 427 return AnalysisState::Branch;
546 } 428 }
547 if (const std::optional<Location> exit_pc{block.stack.Peek(Token::PEXIT)}) { 429 if (const std::optional<Location> exit_pc{block->stack.Peek(Token::PEXIT)}) {
548 const Stack popped_stack{block.stack.Remove(Token::PEXIT)}; 430 const Stack popped_stack{block->stack.Remove(Token::PEXIT)};
549 block.cond = true; 431 block->cond = IR::Condition{true};
550 block.branch_true = AddLabel(block, popped_stack, *exit_pc, function_id); 432 block->branch_true = AddLabel(block, popped_stack, *exit_pc, function_id);
551 block.branch_false = UNREACHABLE_BLOCK_ID; 433 block->branch_false = nullptr;
552 return AnalysisState::Branch; 434 return AnalysisState::Branch;
553 } 435 }
554 block.end = pc; 436 block->end = pc;
555 block.end_class = EndClass::Exit; 437 block->end_class = EndClass::Exit;
556 return AnalysisState::Branch; 438 return AnalysisState::Branch;
557} 439}
558 440
559BlockId CFG::AddLabel(const Block& block, Stack stack, Location pc, FunctionId function_id) { 441Block* CFG::AddLabel(Block* block, Stack stack, Location pc, FunctionId function_id) {
560 Function& function{functions[function_id]}; 442 Function& function{functions[function_id]};
561 if (block.begin == pc) { 443 if (block->begin == pc) {
562 return block.id; 444 // Jumps to itself
445 return block;
563 } 446 }
564 const auto target{std::ranges::find(function.blocks_data, pc, &Block::begin)}; 447 if (const auto it{function.blocks.find(pc, Compare{})}; it != function.blocks.end()) {
565 if (target != function.blocks_data.end()) { 448 // Block already exists and it has been visited
566 return target->id; 449 return &*it;
567 } 450 }
568 const BlockId block_id{++function.current_block_id}; 451 // TODO: FIX DANGLING BLOCKS
452 Block* const new_block{block_pool.Create(Block{
453 .begin{pc},
454 .end{pc},
455 .end_class{EndClass::Branch},
456 .stack{stack},
457 .cond{IR::Condition{true}},
458 .branch_true{nullptr},
459 .branch_false{nullptr},
460 .ir{nullptr},
461 })};
569 function.labels.push_back(Label{ 462 function.labels.push_back(Label{
570 .address{pc}, 463 .address{pc},
571 .block_id{block_id}, 464 .block{new_block},
572 .stack{std::move(stack)}, 465 .stack{std::move(stack)},
573 }); 466 });
574 return block_id; 467 return new_block;
575} 468}
576 469
577std::string CFG::Dot() const { 470std::string CFG::Dot() const {
@@ -581,18 +474,12 @@ std::string CFG::Dot() const {
581 for (const Function& function : functions) { 474 for (const Function& function : functions) {
582 dot += fmt::format("\tsubgraph cluster_{} {{\n", function.entrypoint); 475 dot += fmt::format("\tsubgraph cluster_{} {{\n", function.entrypoint);
583 dot += fmt::format("\t\tnode [style=filled];\n"); 476 dot += fmt::format("\t\tnode [style=filled];\n");
584 for (const u32 block_index : function.blocks) { 477 for (const Block& block : function.blocks) {
585 const Block& block{function.blocks_data[block_index]};
586 const std::string name{NameOf(block)}; 478 const std::string name{NameOf(block)};
587 const auto add_branch = [&](BlockId branch_id, bool add_label) { 479 const auto add_branch = [&](Block* branch, bool add_label) {
588 const auto it{std::ranges::find(function.blocks_data, branch_id, &Block::id)}; 480 dot += fmt::format("\t\t{}->{}", name, NameOf(*branch));
589 dot += fmt::format("\t\t{}->", name); 481 if (add_label && block.cond != IR::Condition{true} &&
590 if (it == function.blocks_data.end()) { 482 block.cond != IR::Condition{false}) {
591 dot += fmt::format("\"Unknown label {}\"", branch_id);
592 } else {
593 dot += NameOf(*it);
594 };
595 if (add_label && block.cond != true && block.cond != false) {
596 dot += fmt::format(" [label=\"{}\"]", block.cond); 483 dot += fmt::format(" [label=\"{}\"]", block.cond);
597 } 484 }
598 dot += '\n'; 485 dot += '\n';
@@ -600,10 +487,10 @@ std::string CFG::Dot() const {
600 dot += fmt::format("\t\t{};\n", name); 487 dot += fmt::format("\t\t{};\n", name);
601 switch (block.end_class) { 488 switch (block.end_class) {
602 case EndClass::Branch: 489 case EndClass::Branch:
603 if (block.cond != false) { 490 if (block.cond != IR::Condition{false}) {
604 add_branch(block.branch_true, true); 491 add_branch(block.branch_true, true);
605 } 492 }
606 if (block.cond != true) { 493 if (block.cond != IR::Condition{true}) {
607 add_branch(block.branch_false, false); 494 add_branch(block.branch_false, false);
608 } 495 }
609 break; 496 break;
@@ -619,12 +506,6 @@ std::string CFG::Dot() const {
619 node_uid); 506 node_uid);
620 ++node_uid; 507 ++node_uid;
621 break; 508 break;
622 case EndClass::Unreachable:
623 dot += fmt::format("\t\t{}->N{};\n", name, node_uid);
624 dot += fmt::format(
625 "\t\tN{} [label=\"Unreachable\"][shape=square][style=stripped];\n", node_uid);
626 ++node_uid;
627 break;
628 } 509 }
629 } 510 }
630 if (function.entrypoint == 8) { 511 if (function.entrypoint == 8) {
@@ -635,10 +516,11 @@ std::string CFG::Dot() const {
635 dot += "\t}\n"; 516 dot += "\t}\n";
636 } 517 }
637 if (!functions.empty()) { 518 if (!functions.empty()) {
638 if (functions.front().blocks.empty()) { 519 auto& function{functions.front()};
520 if (function.blocks.empty()) {
639 dot += "Start;\n"; 521 dot += "Start;\n";
640 } else { 522 } else {
641 dot += fmt::format("\tStart -> {};\n", NameOf(functions.front().blocks_data.front())); 523 dot += fmt::format("\tStart -> {};\n", NameOf(*function.blocks.begin()));
642 } 524 }
643 dot += fmt::format("\tStart [shape=diamond];\n"); 525 dot += fmt::format("\tStart [shape=diamond];\n");
644 } 526 }
diff --git a/src/shader_recompiler/frontend/maxwell/control_flow.h b/src/shader_recompiler/frontend/maxwell/control_flow.h
index 49b369282..8179787b8 100644
--- a/src/shader_recompiler/frontend/maxwell/control_flow.h
+++ b/src/shader_recompiler/frontend/maxwell/control_flow.h
@@ -11,25 +11,27 @@
11#include <vector> 11#include <vector>
12 12
13#include <boost/container/small_vector.hpp> 13#include <boost/container/small_vector.hpp>
14#include <boost/intrusive/set.hpp>
14 15
15#include "shader_recompiler/environment.h" 16#include "shader_recompiler/environment.h"
16#include "shader_recompiler/frontend/ir/condition.h" 17#include "shader_recompiler/frontend/ir/condition.h"
17#include "shader_recompiler/frontend/maxwell/instruction.h" 18#include "shader_recompiler/frontend/maxwell/instruction.h"
18#include "shader_recompiler/frontend/maxwell/location.h" 19#include "shader_recompiler/frontend/maxwell/location.h"
19#include "shader_recompiler/frontend/maxwell/opcodes.h" 20#include "shader_recompiler/frontend/maxwell/opcodes.h"
21#include "shader_recompiler/object_pool.h"
22
23namespace Shader::IR {
24class Block;
25}
20 26
21namespace Shader::Maxwell::Flow { 27namespace Shader::Maxwell::Flow {
22 28
23using BlockId = u32;
24using FunctionId = size_t; 29using FunctionId = size_t;
25 30
26constexpr BlockId UNREACHABLE_BLOCK_ID{static_cast<u32>(-1)};
27
28enum class EndClass { 31enum class EndClass {
29 Branch, 32 Branch,
30 Exit, 33 Exit,
31 Return, 34 Return,
32 Unreachable,
33}; 35};
34 36
35enum class Token { 37enum class Token {
@@ -59,58 +61,37 @@ private:
59 boost::container::small_vector<StackEntry, 3> entries; 61 boost::container::small_vector<StackEntry, 3> entries;
60}; 62};
61 63
62struct Block { 64struct Block : boost::intrusive::set_base_hook<
65 // Normal link is ~2.5% faster compared to safe link
66 boost::intrusive::link_mode<boost::intrusive::normal_link>> {
63 [[nodiscard]] bool Contains(Location pc) const noexcept; 67 [[nodiscard]] bool Contains(Location pc) const noexcept;
64 68
69 bool operator<(const Block& rhs) const noexcept {
70 return begin < rhs.begin;
71 }
72
65 Location begin; 73 Location begin;
66 Location end; 74 Location end;
67 EndClass end_class; 75 EndClass end_class;
68 BlockId id;
69 Stack stack; 76 Stack stack;
70 IR::Condition cond; 77 IR::Condition cond;
71 BlockId branch_true; 78 Block* branch_true;
72 BlockId branch_false; 79 Block* branch_false;
73 boost::container::small_vector<BlockId, 4> imm_predecessors; 80 IR::Block* ir;
74 boost::container::small_vector<BlockId, 8> dominance_frontiers;
75 union {
76 bool post_order_visited{false};
77 Block* imm_dominator;
78 };
79}; 81};
80 82
81struct Label { 83struct Label {
82 Location address; 84 Location address;
83 BlockId block_id; 85 Block* block;
84 Stack stack; 86 Stack stack;
85}; 87};
86 88
87struct Function { 89struct Function {
88 Function(Location start_address); 90 Function(Location start_address);
89 91
90 void BuildBlocksMap();
91
92 void BuildImmediatePredecessors();
93
94 void BuildPostOrder();
95
96 void BuildImmediateDominators();
97
98 void BuildDominanceFrontier();
99
100 [[nodiscard]] size_t NumBlocks() const noexcept {
101 return static_cast<size_t>(current_block_id) + 1;
102 }
103
104 Location entrypoint; 92 Location entrypoint;
105 BlockId current_block_id{0};
106 boost::container::small_vector<Label, 16> labels; 93 boost::container::small_vector<Label, 16> labels;
107 boost::container::small_vector<u32, 0x130> blocks; 94 boost::intrusive::set<Block> blocks;
108 boost::container::small_vector<Block, 0x130> blocks_data;
109 // Translates from BlockId to block index
110 boost::container::small_vector<Block*, 0x130> blocks_map;
111
112 boost::container::small_vector<u32, 0x130> post_order_blocks;
113 boost::container::small_vector<BlockId, 0x130> post_order_map;
114}; 95};
115 96
116class CFG { 97class CFG {
@@ -120,7 +101,7 @@ class CFG {
120 }; 101 };
121 102
122public: 103public:
123 explicit CFG(Environment& env, Location start_address); 104 explicit CFG(Environment& env, ObjectPool<Block>& block_pool, Location start_address);
124 105
125 CFG& operator=(const CFG&) = delete; 106 CFG& operator=(const CFG&) = delete;
126 CFG(const CFG&) = delete; 107 CFG(const CFG&) = delete;
@@ -133,35 +114,37 @@ public:
133 [[nodiscard]] std::span<const Function> Functions() const noexcept { 114 [[nodiscard]] std::span<const Function> Functions() const noexcept {
134 return std::span(functions.data(), functions.size()); 115 return std::span(functions.data(), functions.size());
135 } 116 }
117 [[nodiscard]] std::span<Function> Functions() noexcept {
118 return std::span(functions.data(), functions.size());
119 }
136 120
137private: 121private:
138 void VisitFunctions(Location start_address);
139
140 void AnalyzeLabel(FunctionId function_id, Label& label); 122 void AnalyzeLabel(FunctionId function_id, Label& label);
141 123
142 /// Inspect already visited blocks. 124 /// Inspect already visited blocks.
143 /// Return true when the block has already been visited 125 /// Return true when the block has already been visited
144 bool InspectVisitedBlocks(FunctionId function_id, const Label& label); 126 bool InspectVisitedBlocks(FunctionId function_id, const Label& label);
145 127
146 AnalysisState AnalyzeInst(Block& block, FunctionId function_id, Location pc); 128 AnalysisState AnalyzeInst(Block* block, FunctionId function_id, Location pc);
147 129
148 void AnalyzeCondInst(Block& block, FunctionId function_id, Location pc, EndClass insn_end_class, 130 void AnalyzeCondInst(Block* block, FunctionId function_id, Location pc, EndClass insn_end_class,
149 IR::Condition cond); 131 IR::Condition cond);
150 132
151 /// Return true when the branch instruction is confirmed to be a branch 133 /// Return true when the branch instruction is confirmed to be a branch
152 bool AnalyzeBranch(Block& block, FunctionId function_id, Location pc, Instruction inst, 134 bool AnalyzeBranch(Block* block, FunctionId function_id, Location pc, Instruction inst,
153 Opcode opcode); 135 Opcode opcode);
154 136
155 void AnalyzeBRA(Block& block, FunctionId function_id, Location pc, Instruction inst, 137 void AnalyzeBRA(Block* block, FunctionId function_id, Location pc, Instruction inst,
156 bool is_absolute); 138 bool is_absolute);
157 void AnalyzeBRX(Block& block, Location pc, Instruction inst, bool is_absolute); 139 void AnalyzeBRX(Block* block, Location pc, Instruction inst, bool is_absolute);
158 void AnalyzeCAL(Location pc, Instruction inst, bool is_absolute); 140 void AnalyzeCAL(Location pc, Instruction inst, bool is_absolute);
159 AnalysisState AnalyzeEXIT(Block& block, FunctionId function_id, Location pc, Instruction inst); 141 AnalysisState AnalyzeEXIT(Block* block, FunctionId function_id, Location pc, Instruction inst);
160 142
161 /// Return the branch target block id 143 /// Return the branch target block id
162 BlockId AddLabel(const Block& block, Stack stack, Location pc, FunctionId function_id); 144 Block* AddLabel(Block* block, Stack stack, Location pc, FunctionId function_id);
163 145
164 Environment& env; 146 Environment& env;
147 ObjectPool<Block>& block_pool;
165 boost::container::small_vector<Function, 1> functions; 148 boost::container::small_vector<Function, 1> functions;
166 FunctionId current_function_id{0}; 149 FunctionId current_function_id{0};
167}; 150};
diff --git a/src/shader_recompiler/frontend/maxwell/location.h b/src/shader_recompiler/frontend/maxwell/location.h
index 66b51a19e..26d29eae2 100644
--- a/src/shader_recompiler/frontend/maxwell/location.h
+++ b/src/shader_recompiler/frontend/maxwell/location.h
@@ -15,7 +15,7 @@
15namespace Shader::Maxwell { 15namespace Shader::Maxwell {
16 16
17class Location { 17class Location {
18 static constexpr u32 VIRTUAL_OFFSET{std::numeric_limits<u32>::max()}; 18 static constexpr u32 VIRTUAL_BIAS{4};
19 19
20public: 20public:
21 constexpr Location() = default; 21 constexpr Location() = default;
@@ -27,12 +27,18 @@ public:
27 Align(); 27 Align();
28 } 28 }
29 29
30 constexpr Location Virtual() const noexcept {
31 Location virtual_location;
32 virtual_location.offset = offset - VIRTUAL_BIAS;
33 return virtual_location;
34 }
35
30 [[nodiscard]] constexpr u32 Offset() const noexcept { 36 [[nodiscard]] constexpr u32 Offset() const noexcept {
31 return offset; 37 return offset;
32 } 38 }
33 39
34 [[nodiscard]] constexpr bool IsVirtual() const { 40 [[nodiscard]] constexpr bool IsVirtual() const {
35 return offset == VIRTUAL_OFFSET; 41 return offset % 8 == VIRTUAL_BIAS;
36 } 42 }
37 43
38 constexpr auto operator<=>(const Location&) const noexcept = default; 44 constexpr auto operator<=>(const Location&) const noexcept = default;
@@ -89,7 +95,7 @@ private:
89 offset -= 8 + (offset % 32 == 8 ? 8 : 0); 95 offset -= 8 + (offset % 32 == 8 ? 8 : 0);
90 } 96 }
91 97
92 u32 offset{VIRTUAL_OFFSET}; 98 u32 offset{0xcccccccc};
93}; 99};
94 100
95} // namespace Shader::Maxwell 101} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/program.cpp b/src/shader_recompiler/frontend/maxwell/program.cpp
index 8cdd20804..9fa912ed8 100644
--- a/src/shader_recompiler/frontend/maxwell/program.cpp
+++ b/src/shader_recompiler/frontend/maxwell/program.cpp
@@ -4,57 +4,58 @@
4 4
5#include <algorithm> 5#include <algorithm>
6#include <memory> 6#include <memory>
7#include <vector>
7 8
8#include "shader_recompiler/frontend/ir/basic_block.h" 9#include "shader_recompiler/frontend/ir/basic_block.h"
10#include "shader_recompiler/frontend/ir/structured_control_flow.h"
9#include "shader_recompiler/frontend/maxwell/program.h" 11#include "shader_recompiler/frontend/maxwell/program.h"
10#include "shader_recompiler/frontend/maxwell/termination_code.h"
11#include "shader_recompiler/frontend/maxwell/translate/translate.h" 12#include "shader_recompiler/frontend/maxwell/translate/translate.h"
12#include "shader_recompiler/ir_opt/passes.h" 13#include "shader_recompiler/ir_opt/passes.h"
13 14
14namespace Shader::Maxwell { 15namespace Shader::Maxwell {
15namespace { 16namespace {
16void TranslateCode(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool, 17IR::BlockList TranslateCode(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
17 Environment& env, const Flow::Function& cfg_function, IR::Function& function, 18 Environment& env, Flow::Function& cfg_function) {
18 std::span<IR::Block*> block_map) {
19 const size_t num_blocks{cfg_function.blocks.size()}; 19 const size_t num_blocks{cfg_function.blocks.size()};
20 function.blocks.reserve(num_blocks); 20 std::vector<IR::Block*> blocks(cfg_function.blocks.size());
21 21 std::ranges::for_each(cfg_function.blocks, [&, i = size_t{0}](auto& cfg_block) mutable {
22 for (const Flow::BlockId block_id : cfg_function.blocks) { 22 const u32 begin{cfg_block.begin.Offset()};
23 const Flow::Block& flow_block{cfg_function.blocks_data[block_id]}; 23 const u32 end{cfg_block.end.Offset()};
24 24 blocks[i] = block_pool.Create(inst_pool, begin, end);
25 IR::Block* const ir_block{block_pool.Create(Translate(inst_pool, env, flow_block))}; 25 cfg_block.ir = blocks[i];
26 block_map[flow_block.id] = ir_block; 26 ++i;
27 function.blocks.emplace_back(ir_block); 27 });
28 } 28 std::ranges::for_each(cfg_function.blocks, [&, i = size_t{0}](auto& cfg_block) mutable {
29} 29 IR::Block* const block{blocks[i]};
30 30 ++i;
31void EmitTerminationInsts(const Flow::Function& cfg_function, 31 if (cfg_block.end_class != Flow::EndClass::Branch) {
32 std::span<IR::Block* const> block_map) { 32 block->SetReturn();
33 for (const Flow::BlockId block_id : cfg_function.blocks) { 33 } else if (cfg_block.cond == IR::Condition{true}) {
34 const Flow::Block& flow_block{cfg_function.blocks_data[block_id]}; 34 block->SetBranch(cfg_block.branch_true->ir);
35 EmitTerminationCode(flow_block, block_map); 35 } else if (cfg_block.cond == IR::Condition{false}) {
36 } 36 block->SetBranch(cfg_block.branch_false->ir);
37} 37 } else {
38 38 block->SetBranches(cfg_block.cond, cfg_block.branch_true->ir,
39void TranslateFunction(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool, 39 cfg_block.branch_false->ir);
40 Environment& env, const Flow::Function& cfg_function, 40 }
41 IR::Function& function) { 41 });
42 std::vector<IR::Block*> block_map; 42 return IR::VisitAST(inst_pool, block_pool, blocks,
43 block_map.resize(cfg_function.blocks_data.size()); 43 [&](IR::Block* block) { Translate(env, block); });
44
45 TranslateCode(inst_pool, block_pool, env, cfg_function, function, block_map);
46 EmitTerminationInsts(cfg_function, block_map);
47} 44}
48} // Anonymous namespace 45} // Anonymous namespace
49 46
50IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool, 47IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
51 Environment& env, const Flow::CFG& cfg) { 48 Environment& env, Flow::CFG& cfg) {
52 IR::Program program; 49 IR::Program program;
53 auto& functions{program.functions}; 50 auto& functions{program.functions};
54 functions.reserve(cfg.Functions().size()); 51 functions.reserve(cfg.Functions().size());
55 for (const Flow::Function& cfg_function : cfg.Functions()) { 52 for (Flow::Function& cfg_function : cfg.Functions()) {
56 TranslateFunction(inst_pool, block_pool, env, cfg_function, functions.emplace_back()); 53 functions.push_back(IR::Function{
54 .blocks{TranslateCode(inst_pool, block_pool, env, cfg_function)},
55 });
57 } 56 }
57
58 fmt::print(stdout, "No optimizations: {}", IR::DumpProgram(program));
58 std::ranges::for_each(functions, Optimization::SsaRewritePass); 59 std::ranges::for_each(functions, Optimization::SsaRewritePass);
59 for (IR::Function& function : functions) { 60 for (IR::Function& function : functions) {
60 Optimization::Invoke(Optimization::GlobalMemoryToStorageBufferPass, function); 61 Optimization::Invoke(Optimization::GlobalMemoryToStorageBufferPass, function);
diff --git a/src/shader_recompiler/frontend/maxwell/program.h b/src/shader_recompiler/frontend/maxwell/program.h
index 3355ab129..542621a1d 100644
--- a/src/shader_recompiler/frontend/maxwell/program.h
+++ b/src/shader_recompiler/frontend/maxwell/program.h
@@ -19,6 +19,6 @@ namespace Shader::Maxwell {
19 19
20[[nodiscard]] IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, 20[[nodiscard]] IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool,
21 ObjectPool<IR::Block>& block_pool, Environment& env, 21 ObjectPool<IR::Block>& block_pool, Environment& env,
22 const Flow::CFG& cfg); 22 Flow::CFG& cfg);
23 23
24} // namespace Shader::Maxwell 24} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/termination_code.cpp b/src/shader_recompiler/frontend/maxwell/termination_code.cpp
deleted file mode 100644
index ed5137f20..000000000
--- a/src/shader_recompiler/frontend/maxwell/termination_code.cpp
+++ /dev/null
@@ -1,86 +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 <span>
6
7#include "shader_recompiler/exception.h"
8#include "shader_recompiler/frontend/ir/basic_block.h"
9#include "shader_recompiler/frontend/ir/ir_emitter.h"
10#include "shader_recompiler/frontend/maxwell/control_flow.h"
11#include "shader_recompiler/frontend/maxwell/termination_code.h"
12
13namespace Shader::Maxwell {
14
15static void EmitExit(IR::IREmitter& ir) {
16 ir.Exit();
17}
18
19static IR::U1 GetFlowTest(IR::FlowTest flow_test, IR::IREmitter& ir) {
20 switch (flow_test) {
21 case IR::FlowTest::T:
22 return ir.Imm1(true);
23 case IR::FlowTest::F:
24 return ir.Imm1(false);
25 case IR::FlowTest::NE:
26 // FIXME: Verify this
27 return ir.LogicalNot(ir.GetZFlag());
28 case IR::FlowTest::NaN:
29 // FIXME: Verify this
30 return ir.LogicalAnd(ir.GetSFlag(), ir.GetZFlag());
31 default:
32 throw NotImplementedException("Flow test {}", flow_test);
33 }
34}
35
36static IR::U1 GetCond(IR::Condition cond, IR::IREmitter& ir) {
37 const IR::FlowTest flow_test{cond.FlowTest()};
38 const auto [pred, pred_negated]{cond.Pred()};
39 if (pred == IR::Pred::PT && !pred_negated) {
40 return GetFlowTest(flow_test, ir);
41 }
42 if (flow_test == IR::FlowTest::T) {
43 return ir.GetPred(pred, pred_negated);
44 }
45 return ir.LogicalAnd(ir.GetPred(pred, pred_negated), GetFlowTest(flow_test, ir));
46}
47
48static void EmitBranch(const Flow::Block& flow_block, std::span<IR::Block* const> block_map,
49 IR::IREmitter& ir) {
50 const auto add_immediate_predecessor = [&](Flow::BlockId label) {
51 block_map[label]->AddImmediatePredecessor(&ir.block);
52 };
53 if (flow_block.cond == true) {
54 add_immediate_predecessor(flow_block.branch_true);
55 return ir.Branch(block_map[flow_block.branch_true]);
56 }
57 if (flow_block.cond == false) {
58 add_immediate_predecessor(flow_block.branch_false);
59 return ir.Branch(block_map[flow_block.branch_false]);
60 }
61 add_immediate_predecessor(flow_block.branch_true);
62 add_immediate_predecessor(flow_block.branch_false);
63 return ir.BranchConditional(GetCond(flow_block.cond, ir), block_map[flow_block.branch_true],
64 block_map[flow_block.branch_false]);
65}
66
67void EmitTerminationCode(const Flow::Block& flow_block, std::span<IR::Block* const> block_map) {
68 IR::Block* const block{block_map[flow_block.id]};
69 IR::IREmitter ir(*block);
70 switch (flow_block.end_class) {
71 case Flow::EndClass::Branch:
72 EmitBranch(flow_block, block_map, ir);
73 break;
74 case Flow::EndClass::Exit:
75 EmitExit(ir);
76 break;
77 case Flow::EndClass::Return:
78 ir.Return();
79 break;
80 case Flow::EndClass::Unreachable:
81 ir.Unreachable();
82 break;
83 }
84}
85
86} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/termination_code.h b/src/shader_recompiler/frontend/maxwell/termination_code.h
deleted file mode 100644
index 04e044534..000000000
--- a/src/shader_recompiler/frontend/maxwell/termination_code.h
+++ /dev/null
@@ -1,17 +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 <span>
8
9#include "shader_recompiler/frontend/ir/basic_block.h"
10#include "shader_recompiler/frontend/maxwell/control_flow.h"
11
12namespace Shader::Maxwell {
13
14/// Emit termination instructions and collect immediate predecessors
15void EmitTerminationCode(const Flow::Block& flow_block, std::span<IR::Block* const> block_map);
16
17} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/translate/impl/integer_shift_left.cpp b/src/shader_recompiler/frontend/maxwell/translate/impl/integer_shift_left.cpp
index d4b417d14..b752785d4 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/impl/integer_shift_left.cpp
+++ b/src/shader_recompiler/frontend/maxwell/translate/impl/integer_shift_left.cpp
@@ -28,7 +28,7 @@ void SHL(TranslatorVisitor& v, u64 insn, const IR::U32& unsafe_shift) {
28 IR::U32 result; 28 IR::U32 result;
29 if (shl.w != 0) { 29 if (shl.w != 0) {
30 // When .W is set, the shift value is wrapped 30 // When .W is set, the shift value is wrapped
31 // To emulate this we just have to clamp it ourselves. 31 // To emulate this we just have to wrap it ourselves.
32 const IR::U32 shift{v.ir.BitwiseAnd(unsafe_shift, v.ir.Imm32(31))}; 32 const IR::U32 shift{v.ir.BitwiseAnd(unsafe_shift, v.ir.Imm32(31))};
33 result = v.ir.ShiftLeftLogical(base, shift); 33 result = v.ir.ShiftLeftLogical(base, shift);
34 } else { 34 } else {
diff --git a/src/shader_recompiler/frontend/maxwell/translate/translate.cpp b/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
index 7e6bb07a2..f1230f58f 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
+++ b/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
@@ -23,14 +23,13 @@ static void Invoke(TranslatorVisitor& visitor, Location pc, u64 insn) {
23 } 23 }
24} 24}
25 25
26IR::Block Translate(ObjectPool<IR::Inst>& inst_pool, Environment& env, 26void Translate(Environment& env, IR::Block* block) {
27 const Flow::Block& flow_block) { 27 if (block->IsVirtual()) {
28 IR::Block block{inst_pool, flow_block.begin.Offset(), flow_block.end.Offset()}; 28 return;
29 TranslatorVisitor visitor{env, block}; 29 }
30 30 TranslatorVisitor visitor{env, *block};
31 const Location pc_end{flow_block.end}; 31 const Location pc_end{block->LocationEnd()};
32 Location pc{flow_block.begin}; 32 for (Location pc = block->LocationBegin(); pc != pc_end; ++pc) {
33 while (pc != pc_end) {
34 const u64 insn{env.ReadInstruction(pc.Offset())}; 33 const u64 insn{env.ReadInstruction(pc.Offset())};
35 const Opcode opcode{Decode(insn)}; 34 const Opcode opcode{Decode(insn)};
36 switch (opcode) { 35 switch (opcode) {
@@ -43,9 +42,7 @@ IR::Block Translate(ObjectPool<IR::Inst>& inst_pool, Environment& env,
43 default: 42 default:
44 throw LogicError("Invalid opcode {}", opcode); 43 throw LogicError("Invalid opcode {}", opcode);
45 } 44 }
46 ++pc;
47 } 45 }
48 return block;
49} 46}
50 47
51} // namespace Shader::Maxwell 48} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/translate/translate.h b/src/shader_recompiler/frontend/maxwell/translate/translate.h
index c1c21b278..e1aa2e0f4 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/translate.h
+++ b/src/shader_recompiler/frontend/maxwell/translate/translate.h
@@ -6,14 +6,9 @@
6 6
7#include "shader_recompiler/environment.h" 7#include "shader_recompiler/environment.h"
8#include "shader_recompiler/frontend/ir/basic_block.h" 8#include "shader_recompiler/frontend/ir/basic_block.h"
9#include "shader_recompiler/frontend/ir/microinstruction.h"
10#include "shader_recompiler/frontend/maxwell/control_flow.h"
11#include "shader_recompiler/frontend/maxwell/location.h"
12#include "shader_recompiler/object_pool.h"
13 9
14namespace Shader::Maxwell { 10namespace Shader::Maxwell {
15 11
16[[nodiscard]] IR::Block Translate(ObjectPool<IR::Inst>& inst_pool, Environment& env, 12void Translate(Environment& env, IR::Block* block);
17 const Flow::Block& flow_block);
18 13
19} // namespace Shader::Maxwell 14} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/ir_opt/constant_propagation_pass.cpp b/src/shader_recompiler/ir_opt/constant_propagation_pass.cpp
index f1170c61e..9fba6ac23 100644
--- a/src/shader_recompiler/ir_opt/constant_propagation_pass.cpp
+++ b/src/shader_recompiler/ir_opt/constant_propagation_pass.cpp
@@ -132,6 +132,32 @@ void FoldLogicalAnd(IR::Inst& inst) {
132 } 132 }
133} 133}
134 134
135void FoldLogicalOr(IR::Inst& inst) {
136 if (!FoldCommutative(inst, [](bool a, bool b) { return a || b; })) {
137 return;
138 }
139 const IR::Value rhs{inst.Arg(1)};
140 if (rhs.IsImmediate()) {
141 if (rhs.U1()) {
142 inst.ReplaceUsesWith(IR::Value{true});
143 } else {
144 inst.ReplaceUsesWith(inst.Arg(0));
145 }
146 }
147}
148
149void FoldLogicalNot(IR::Inst& inst) {
150 const IR::U1 value{inst.Arg(0)};
151 if (value.IsImmediate()) {
152 inst.ReplaceUsesWith(IR::Value{!value.U1()});
153 return;
154 }
155 IR::Inst* const arg{value.InstRecursive()};
156 if (arg->Opcode() == IR::Opcode::LogicalNot) {
157 inst.ReplaceUsesWith(arg->Arg(0));
158 }
159}
160
135template <typename Dest, typename Source> 161template <typename Dest, typename Source>
136void FoldBitCast(IR::Inst& inst, IR::Opcode reverse) { 162void FoldBitCast(IR::Inst& inst, IR::Opcode reverse) {
137 const IR::Value value{inst.Arg(0)}; 163 const IR::Value value{inst.Arg(0)};
@@ -160,6 +186,24 @@ void FoldWhenAllImmediates(IR::Inst& inst, Func&& func) {
160 inst.ReplaceUsesWith(EvalImmediates(inst, func, Indices{})); 186 inst.ReplaceUsesWith(EvalImmediates(inst, func, Indices{}));
161} 187}
162 188
189void FoldBranchConditional(IR::Inst& inst) {
190 const IR::U1 cond{inst.Arg(0)};
191 if (cond.IsImmediate()) {
192 // TODO: Convert to Branch
193 return;
194 }
195 const IR::Inst* cond_inst{cond.InstRecursive()};
196 if (cond_inst->Opcode() == IR::Opcode::LogicalNot) {
197 const IR::Value true_label{inst.Arg(1)};
198 const IR::Value false_label{inst.Arg(2)};
199 // Remove negation on the conditional (take the parameter out of LogicalNot) and swap
200 // the branches
201 inst.SetArg(0, cond_inst->Arg(0));
202 inst.SetArg(1, false_label);
203 inst.SetArg(2, true_label);
204 }
205}
206
163void ConstantPropagation(IR::Inst& inst) { 207void ConstantPropagation(IR::Inst& inst) {
164 switch (inst.Opcode()) { 208 switch (inst.Opcode()) {
165 case IR::Opcode::GetRegister: 209 case IR::Opcode::GetRegister:
@@ -178,6 +222,10 @@ void ConstantPropagation(IR::Inst& inst) {
178 return FoldSelect<u32>(inst); 222 return FoldSelect<u32>(inst);
179 case IR::Opcode::LogicalAnd: 223 case IR::Opcode::LogicalAnd:
180 return FoldLogicalAnd(inst); 224 return FoldLogicalAnd(inst);
225 case IR::Opcode::LogicalOr:
226 return FoldLogicalOr(inst);
227 case IR::Opcode::LogicalNot:
228 return FoldLogicalNot(inst);
181 case IR::Opcode::ULessThan: 229 case IR::Opcode::ULessThan:
182 return FoldWhenAllImmediates(inst, [](u32 a, u32 b) { return a < b; }); 230 return FoldWhenAllImmediates(inst, [](u32 a, u32 b) { return a < b; });
183 case IR::Opcode::BitFieldUExtract: 231 case IR::Opcode::BitFieldUExtract:
@@ -188,6 +236,8 @@ void ConstantPropagation(IR::Inst& inst) {
188 } 236 }
189 return (base >> shift) & ((1U << count) - 1); 237 return (base >> shift) & ((1U << count) - 1);
190 }); 238 });
239 case IR::Opcode::BranchConditional:
240 return FoldBranchConditional(inst);
191 default: 241 default:
192 break; 242 break;
193 } 243 }
diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp
index 15a9db90a..8ca996e93 100644
--- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp
+++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp
@@ -34,6 +34,13 @@ struct SignFlagTag : FlagTag {};
34struct CarryFlagTag : FlagTag {}; 34struct CarryFlagTag : FlagTag {};
35struct OverflowFlagTag : FlagTag {}; 35struct OverflowFlagTag : FlagTag {};
36 36
37struct GotoVariable : FlagTag {
38 GotoVariable() = default;
39 explicit GotoVariable(u32 index_) : index{index_} {}
40
41 u32 index;
42};
43
37struct DefTable { 44struct DefTable {
38 [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { 45 [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept {
39 return regs[IR::RegIndex(variable)]; 46 return regs[IR::RegIndex(variable)];
@@ -43,6 +50,10 @@ struct DefTable {
43 return preds[IR::PredIndex(variable)]; 50 return preds[IR::PredIndex(variable)];
44 } 51 }
45 52
53 [[nodiscard]] ValueMap& operator[](GotoVariable goto_variable) {
54 return goto_vars[goto_variable.index];
55 }
56
46 [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept { 57 [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept {
47 return zero_flag; 58 return zero_flag;
48 } 59 }
@@ -61,6 +72,7 @@ struct DefTable {
61 72
62 std::array<ValueMap, IR::NUM_USER_REGS> regs; 73 std::array<ValueMap, IR::NUM_USER_REGS> regs;
63 std::array<ValueMap, IR::NUM_USER_PREDS> preds; 74 std::array<ValueMap, IR::NUM_USER_PREDS> preds;
75 boost::container::flat_map<u32, ValueMap> goto_vars;
64 ValueMap zero_flag; 76 ValueMap zero_flag;
65 ValueMap sign_flag; 77 ValueMap sign_flag;
66 ValueMap carry_flag; 78 ValueMap carry_flag;
@@ -68,15 +80,15 @@ struct DefTable {
68}; 80};
69 81
70IR::Opcode UndefOpcode(IR::Reg) noexcept { 82IR::Opcode UndefOpcode(IR::Reg) noexcept {
71 return IR::Opcode::Undef32; 83 return IR::Opcode::UndefU32;
72} 84}
73 85
74IR::Opcode UndefOpcode(IR::Pred) noexcept { 86IR::Opcode UndefOpcode(IR::Pred) noexcept {
75 return IR::Opcode::Undef1; 87 return IR::Opcode::UndefU1;
76} 88}
77 89
78IR::Opcode UndefOpcode(const FlagTag&) noexcept { 90IR::Opcode UndefOpcode(const FlagTag&) noexcept {
79 return IR::Opcode::Undef1; 91 return IR::Opcode::UndefU1;
80} 92}
81 93
82[[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { 94[[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept {
@@ -165,6 +177,9 @@ void SsaRewritePass(IR::Function& function) {
165 pass.WriteVariable(pred, block, inst.Arg(1)); 177 pass.WriteVariable(pred, block, inst.Arg(1));
166 } 178 }
167 break; 179 break;
180 case IR::Opcode::SetGotoVariable:
181 pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1));
182 break;
168 case IR::Opcode::SetZFlag: 183 case IR::Opcode::SetZFlag:
169 pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); 184 pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0));
170 break; 185 break;
@@ -187,6 +202,9 @@ void SsaRewritePass(IR::Function& function) {
187 inst.ReplaceUsesWith(pass.ReadVariable(pred, block)); 202 inst.ReplaceUsesWith(pass.ReadVariable(pred, block));
188 } 203 }
189 break; 204 break;
205 case IR::Opcode::GetGotoVariable:
206 inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block));
207 break;
190 case IR::Opcode::GetZFlag: 208 case IR::Opcode::GetZFlag:
191 inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); 209 inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block));
192 break; 210 break;
diff --git a/src/shader_recompiler/ir_opt/verification_pass.cpp b/src/shader_recompiler/ir_opt/verification_pass.cpp
index 8a5adf5a2..32b56eb57 100644
--- a/src/shader_recompiler/ir_opt/verification_pass.cpp
+++ b/src/shader_recompiler/ir_opt/verification_pass.cpp
@@ -14,6 +14,10 @@ namespace Shader::Optimization {
14static void ValidateTypes(const IR::Function& function) { 14static void ValidateTypes(const IR::Function& function) {
15 for (const auto& block : function.blocks) { 15 for (const auto& block : function.blocks) {
16 for (const IR::Inst& inst : *block) { 16 for (const IR::Inst& inst : *block) {
17 if (inst.Opcode() == IR::Opcode::Phi) {
18 // Skip validation on phi nodes
19 continue;
20 }
17 const size_t num_args{inst.NumArgs()}; 21 const size_t num_args{inst.NumArgs()};
18 for (size_t i = 0; i < num_args; ++i) { 22 for (size_t i = 0; i < num_args; ++i) {
19 const IR::Type t1{inst.Arg(i).Type()}; 23 const IR::Type t1{inst.Arg(i).Type()};
diff --git a/src/shader_recompiler/main.cpp b/src/shader_recompiler/main.cpp
index 9887e066d..3ca1677c4 100644
--- a/src/shader_recompiler/main.cpp
+++ b/src/shader_recompiler/main.cpp
@@ -2,6 +2,7 @@
2// Licensed under GPLv2 or any later version 2// Licensed under GPLv2 or any later version
3// Refer to the license.txt file included. 3// Refer to the license.txt file included.
4 4
5#include <chrono>
5#include <filesystem> 6#include <filesystem>
6 7
7#include <fmt/format.h> 8#include <fmt/format.h>
@@ -36,34 +37,46 @@ void RunDatabase() {
36 ForEachFile("D:\\Shaders\\Database", [&](const std::filesystem::path& path) { 37 ForEachFile("D:\\Shaders\\Database", [&](const std::filesystem::path& path) {
37 map.emplace_back(std::make_unique<FileEnvironment>(path.string().c_str())); 38 map.emplace_back(std::make_unique<FileEnvironment>(path.string().c_str()));
38 }); 39 });
39 for (int i = 0; i < 300; ++i) { 40 auto block_pool{std::make_unique<ObjectPool<Flow::Block>>()};
41 auto t0 = std::chrono::high_resolution_clock::now();
42 int N = 1;
43 int n = 0;
44 for (int i = 0; i < N; ++i) {
40 for (auto& env : map) { 45 for (auto& env : map) {
46 ++n;
41 // fmt::print(stdout, "Decoding {}\n", path.string()); 47 // fmt::print(stdout, "Decoding {}\n", path.string());
48
42 const Location start_address{0}; 49 const Location start_address{0};
43 auto cfg{std::make_unique<Flow::CFG>(*env, start_address)}; 50 block_pool->ReleaseContents();
51 Flow::CFG cfg{*env, *block_pool, start_address};
44 // fmt::print(stdout, "{}\n", cfg->Dot()); 52 // fmt::print(stdout, "{}\n", cfg->Dot());
45 // IR::Program program{env, cfg}; 53 // IR::Program program{env, cfg};
46 // Optimize(program); 54 // Optimize(program);
47 // const std::string code{EmitGLASM(program)}; 55 // const std::string code{EmitGLASM(program)};
48 } 56 }
49 } 57 }
58 auto t = std::chrono::high_resolution_clock::now();
59 fmt::print(stdout, "{} ms",
60 std::chrono::duration_cast<std::chrono::milliseconds>(t - t0).count() / double(N));
50} 61}
51 62
52int main() { 63int main() {
53 // RunDatabase(); 64 // RunDatabase();
54 65
66 auto flow_block_pool{std::make_unique<ObjectPool<Flow::Block>>()};
55 auto inst_pool{std::make_unique<ObjectPool<IR::Inst>>()}; 67 auto inst_pool{std::make_unique<ObjectPool<IR::Inst>>()};
56 auto block_pool{std::make_unique<ObjectPool<IR::Block>>()}; 68 auto block_pool{std::make_unique<ObjectPool<IR::Block>>()};
57 69
58 // FileEnvironment env{"D:\\Shaders\\Database\\test.bin"}; 70 FileEnvironment env{"D:\\Shaders\\Database\\Oninaki\\CS8F146B41DB6BD826.bin"};
59 FileEnvironment env{"D:\\Shaders\\Database\\Oninaki\\CS15C2FB1F0B965767.bin"}; 71 // FileEnvironment env{"D:\\Shaders\\shader.bin"};
60 for (int i = 0; i < 1; ++i) { 72 for (int i = 0; i < 1; ++i) {
61 block_pool->ReleaseContents(); 73 block_pool->ReleaseContents();
62 inst_pool->ReleaseContents(); 74 inst_pool->ReleaseContents();
63 auto cfg{std::make_unique<Flow::CFG>(env, 0)}; 75 flow_block_pool->ReleaseContents();
64 // fmt::print(stdout, "{}\n", cfg->Dot()); 76 Flow::CFG cfg{env, *flow_block_pool, 0};
65 IR::Program program{TranslateProgram(*inst_pool, *block_pool, env, *cfg)}; 77 fmt::print(stdout, "{}\n", cfg.Dot());
66 // fmt::print(stdout, "{}\n", IR::DumpProgram(program)); 78 IR::Program program{TranslateProgram(*inst_pool, *block_pool, env, cfg)};
79 fmt::print(stdout, "{}\n", IR::DumpProgram(program));
67 Backend::SPIRV::EmitSPIRV spirv{program}; 80 Backend::SPIRV::EmitSPIRV spirv{program};
68 } 81 }
69} 82}
diff --git a/src/shader_recompiler/shader_info.h b/src/shader_recompiler/shader_info.h
new file mode 100644
index 000000000..1760bf4a9
--- /dev/null
+++ b/src/shader_recompiler/shader_info.h
@@ -0,0 +1,28 @@
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 <array>
8
9#include <boost/container/static_vector.hpp>
10
11namespace Shader {
12
13struct Info {
14 struct ConstantBuffer {
15
16 };
17
18 struct {
19 bool workgroup_id{};
20 bool local_invocation_id{};
21 bool fp16{};
22 bool fp64{};
23 } uses;
24
25 std::array<18
26};
27
28} // namespace Shader
HIC SVNT DRACONES