summaryrefslogtreecommitdiff
path: root/src/shader_recompiler/frontend
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/shader_recompiler/frontend/ir/abstract_syntax_list.h56
-rw-r--r--src/shader_recompiler/frontend/ir/basic_block.cpp56
-rw-r--r--src/shader_recompiler/frontend/ir/basic_block.h51
-rw-r--r--src/shader_recompiler/frontend/ir/ir_emitter.cpp60
-rw-r--r--src/shader_recompiler/frontend/ir/ir_emitter.h11
-rw-r--r--src/shader_recompiler/frontend/ir/microinstruction.cpp11
-rw-r--r--src/shader_recompiler/frontend/ir/opcodes.h1
-rw-r--r--src/shader_recompiler/frontend/ir/opcodes.inc21
-rw-r--r--src/shader_recompiler/frontend/ir/post_order.cpp36
-rw-r--r--src/shader_recompiler/frontend/ir/post_order.h3
-rw-r--r--src/shader_recompiler/frontend/ir/program.h4
-rw-r--r--src/shader_recompiler/frontend/ir/type.h49
-rw-r--r--src/shader_recompiler/frontend/ir/value.cpp8
-rw-r--r--src/shader_recompiler/frontend/ir/value.h9
-rw-r--r--src/shader_recompiler/frontend/maxwell/program.cpp24
-rw-r--r--src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp235
-rw-r--r--src/shader_recompiler/frontend/maxwell/structured_control_flow.h12
-rw-r--r--src/shader_recompiler/frontend/maxwell/translate/translate.cpp7
-rw-r--r--src/shader_recompiler/frontend/maxwell/translate/translate.h2
19 files changed, 312 insertions, 344 deletions
diff --git a/src/shader_recompiler/frontend/ir/abstract_syntax_list.h b/src/shader_recompiler/frontend/ir/abstract_syntax_list.h
new file mode 100644
index 000000000..1366414c2
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/abstract_syntax_list.h
@@ -0,0 +1,56 @@
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 <vector>
8
9#include "shader_recompiler/frontend/ir/value.h"
10
11namespace Shader::IR {
12
13class Block;
14
15struct AbstractSyntaxNode {
16 enum class Type {
17 Block,
18 If,
19 EndIf,
20 Loop,
21 Repeat,
22 Break,
23 Return,
24 Unreachable,
25 };
26 Type type{};
27 union {
28 Block* block{};
29 struct {
30 U1 cond;
31 Block* body;
32 Block* merge;
33 } if_node;
34 struct {
35 Block* merge;
36 } end_if;
37 struct {
38 Block* body;
39 Block* continue_block;
40 Block* merge;
41 } loop;
42 struct {
43 U1 cond;
44 Block* loop_header;
45 Block* merge;
46 } repeat;
47 struct {
48 U1 cond;
49 Block* merge;
50 Block* skip;
51 } break_node;
52 };
53};
54using AbstractSyntaxList = std::vector<AbstractSyntaxNode>;
55
56} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/basic_block.cpp b/src/shader_recompiler/frontend/ir/basic_block.cpp
index f92fc2571..7c08b25ce 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.cpp
+++ b/src/shader_recompiler/frontend/ir/basic_block.cpp
@@ -14,10 +14,7 @@
14 14
15namespace Shader::IR { 15namespace Shader::IR {
16 16
17Block::Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end) 17Block::Block(ObjectPool<Inst>& inst_pool_) : inst_pool{&inst_pool_} {}
18 : inst_pool{&inst_pool_}, location_begin{begin}, location_end{end} {}
19
20Block::Block(ObjectPool<Inst>& inst_pool_) : Block{inst_pool_, 0, 0} {}
21 18
22Block::~Block() = default; 19Block::~Block() = default;
23 20
@@ -40,39 +37,15 @@ Block::iterator Block::PrependNewInst(iterator insertion_point, Opcode op,
40 return result_it; 37 return result_it;
41} 38}
42 39
43void Block::SetBranches(Condition cond, Block* branch_true_, Block* branch_false_) { 40void Block::AddBranch(Block* block) {
44 branch_cond = cond; 41 if (std::ranges::find(imm_successors, block) != imm_successors.end()) {
45 branch_true = branch_true_; 42 throw LogicError("Successor already inserted");
46 branch_false = branch_false_; 43 }
47} 44 if (std::ranges::find(block->imm_predecessors, this) != block->imm_predecessors.end()) {
48 45 throw LogicError("Predecessor already inserted");
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;
62}
63
64u32 Block::LocationBegin() const noexcept {
65 return location_begin;
66}
67
68u32 Block::LocationEnd() const noexcept {
69 return location_end;
70}
71
72void Block::AddImmediatePredecessor(Block* block) {
73 if (std::ranges::find(imm_predecessors, block) == imm_predecessors.end()) {
74 imm_predecessors.push_back(block);
75 } 46 }
47 imm_successors.push_back(block);
48 block->imm_predecessors.push_back(this);
76} 49}
77 50
78static std::string BlockToIndex(const std::map<const Block*, size_t>& block_to_index, 51static std::string BlockToIndex(const std::map<const Block*, size_t>& block_to_index,
@@ -92,15 +65,11 @@ static size_t InstIndex(std::map<const Inst*, size_t>& inst_to_index, size_t& in
92 return it->second; 65 return it->second;
93} 66}
94 67
95static std::string ArgToIndex(const std::map<const Block*, size_t>& block_to_index, 68static std::string ArgToIndex(std::map<const Inst*, size_t>& inst_to_index, size_t& inst_index,
96 std::map<const Inst*, size_t>& inst_to_index, size_t& inst_index,
97 const Value& arg) { 69 const Value& arg) {
98 if (arg.IsEmpty()) { 70 if (arg.IsEmpty()) {
99 return "<null>"; 71 return "<null>";
100 } 72 }
101 if (arg.IsLabel()) {
102 return BlockToIndex(block_to_index, arg.Label());
103 }
104 if (!arg.IsImmediate() || arg.IsIdentity()) { 73 if (!arg.IsImmediate() || arg.IsIdentity()) {
105 return fmt::format("%{}", InstIndex(inst_to_index, inst_index, arg.Inst())); 74 return fmt::format("%{}", InstIndex(inst_to_index, inst_index, arg.Inst()));
106 } 75 }
@@ -140,8 +109,7 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
140 if (const auto it{block_to_index.find(&block)}; it != block_to_index.end()) { 109 if (const auto it{block_to_index.find(&block)}; it != block_to_index.end()) {
141 ret += fmt::format(" ${}", it->second); 110 ret += fmt::format(" ${}", it->second);
142 } 111 }
143 ret += fmt::format(": begin={:04x} end={:04x}\n", block.LocationBegin(), block.LocationEnd()); 112 ret += '\n';
144
145 for (const Inst& inst : block) { 113 for (const Inst& inst : block) {
146 const Opcode op{inst.GetOpcode()}; 114 const Opcode op{inst.GetOpcode()};
147 ret += fmt::format("[{:016x}] ", reinterpret_cast<u64>(&inst)); 115 ret += fmt::format("[{:016x}] ", reinterpret_cast<u64>(&inst));
@@ -153,7 +121,7 @@ std::string DumpBlock(const Block& block, const std::map<const Block*, size_t>&
153 const size_t arg_count{inst.NumArgs()}; 121 const size_t arg_count{inst.NumArgs()};
154 for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) { 122 for (size_t arg_index = 0; arg_index < arg_count; ++arg_index) {
155 const Value arg{inst.Arg(arg_index)}; 123 const Value arg{inst.Arg(arg_index)};
156 const std::string arg_str{ArgToIndex(block_to_index, inst_to_index, inst_index, arg)}; 124 const std::string arg_str{ArgToIndex(inst_to_index, inst_index, arg)};
157 ret += arg_index != 0 ? ", " : " "; 125 ret += arg_index != 0 ? ", " : " ";
158 if (op == Opcode::Phi) { 126 if (op == Opcode::Phi) {
159 ret += fmt::format("[ {}, {} ]", arg_str, 127 ret += fmt::format("[ {}, {} ]", arg_str,
diff --git a/src/shader_recompiler/frontend/ir/basic_block.h b/src/shader_recompiler/frontend/ir/basic_block.h
index 0b0c97af6..7e134b4c7 100644
--- a/src/shader_recompiler/frontend/ir/basic_block.h
+++ b/src/shader_recompiler/frontend/ir/basic_block.h
@@ -12,6 +12,7 @@
12#include <boost/intrusive/list.hpp> 12#include <boost/intrusive/list.hpp>
13 13
14#include "common/bit_cast.h" 14#include "common/bit_cast.h"
15#include "common/common_types.h"
15#include "shader_recompiler/frontend/ir/condition.h" 16#include "shader_recompiler/frontend/ir/condition.h"
16#include "shader_recompiler/frontend/ir/value.h" 17#include "shader_recompiler/frontend/ir/value.h"
17#include "shader_recompiler/object_pool.h" 18#include "shader_recompiler/object_pool.h"
@@ -27,7 +28,6 @@ public:
27 using reverse_iterator = InstructionList::reverse_iterator; 28 using reverse_iterator = InstructionList::reverse_iterator;
28 using const_reverse_iterator = InstructionList::const_reverse_iterator; 29 using const_reverse_iterator = InstructionList::const_reverse_iterator;
29 30
30 explicit Block(ObjectPool<Inst>& inst_pool_, u32 begin, u32 end);
31 explicit Block(ObjectPool<Inst>& inst_pool_); 31 explicit Block(ObjectPool<Inst>& inst_pool_);
32 ~Block(); 32 ~Block();
33 33
@@ -44,22 +44,8 @@ public:
44 iterator PrependNewInst(iterator insertion_point, Opcode op, 44 iterator PrependNewInst(iterator insertion_point, Opcode op,
45 std::initializer_list<Value> args = {}, u32 flags = 0); 45 std::initializer_list<Value> args = {}, u32 flags = 0);
46 46
47 /// Set the branches to jump to when all instructions have executed. 47 /// Adds a new branch to this basic block.
48 void SetBranches(Condition cond, Block* branch_true, Block* branch_false); 48 void AddBranch(Block* block);
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();
53
54 /// Returns true when the block does not implement any guest instructions directly.
55 [[nodiscard]] bool IsVirtual() const noexcept;
56 /// Gets the starting location of this basic block.
57 [[nodiscard]] u32 LocationBegin() const noexcept;
58 /// Gets the end location for this basic block.
59 [[nodiscard]] u32 LocationEnd() const noexcept;
60
61 /// Adds a new immediate predecessor to this basic block.
62 void AddImmediatePredecessor(Block* block);
63 49
64 /// Gets a mutable reference to the instruction list for this basic block. 50 /// Gets a mutable reference to the instruction list for this basic block.
65 [[nodiscard]] InstructionList& Instructions() noexcept { 51 [[nodiscard]] InstructionList& Instructions() noexcept {
@@ -71,9 +57,13 @@ public:
71 } 57 }
72 58
73 /// Gets an immutable span to the immediate predecessors. 59 /// Gets an immutable span to the immediate predecessors.
74 [[nodiscard]] std::span<Block* const> ImmediatePredecessors() const noexcept { 60 [[nodiscard]] std::span<Block* const> ImmPredecessors() const noexcept {
75 return imm_predecessors; 61 return imm_predecessors;
76 } 62 }
63 /// Gets an immutable span to the immediate successors.
64 [[nodiscard]] std::span<Block* const> ImmSuccessors() const noexcept {
65 return imm_successors;
66 }
77 67
78 /// Intrusively store the host definition of this instruction. 68 /// Intrusively store the host definition of this instruction.
79 template <typename DefinitionType> 69 template <typename DefinitionType>
@@ -87,19 +77,6 @@ public:
87 return Common::BitCast<DefinitionType>(definition); 77 return Common::BitCast<DefinitionType>(definition);
88 } 78 }
89 79
90 [[nodiscard]] Condition BranchCondition() const noexcept {
91 return branch_cond;
92 }
93 [[nodiscard]] bool IsTerminationBlock() const noexcept {
94 return !branch_true && !branch_false;
95 }
96 [[nodiscard]] Block* TrueBranch() const noexcept {
97 return branch_true;
98 }
99 [[nodiscard]] Block* FalseBranch() const noexcept {
100 return branch_false;
101 }
102
103 void SetSsaRegValue(IR::Reg reg, const Value& value) noexcept { 80 void SetSsaRegValue(IR::Reg reg, const Value& value) noexcept {
104 ssa_reg_values[RegIndex(reg)] = value; 81 ssa_reg_values[RegIndex(reg)] = value;
105 } 82 }
@@ -178,22 +155,14 @@ public:
178private: 155private:
179 /// Memory pool for instruction list 156 /// Memory pool for instruction list
180 ObjectPool<Inst>* inst_pool; 157 ObjectPool<Inst>* inst_pool;
181 /// Starting location of this block
182 u32 location_begin;
183 /// End location of this block
184 u32 location_end;
185 158
186 /// List of instructions in this block 159 /// List of instructions in this block
187 InstructionList instructions; 160 InstructionList instructions;
188 161
189 /// Condition to choose the branch to take
190 Condition branch_cond{true};
191 /// Block to jump into when the branch condition evaluates as true
192 Block* branch_true{nullptr};
193 /// Block to jump into when the branch condition evaluates as false
194 Block* branch_false{nullptr};
195 /// Block immediate predecessors 162 /// Block immediate predecessors
196 std::vector<Block*> imm_predecessors; 163 std::vector<Block*> imm_predecessors;
164 /// Block immediate successors
165 std::vector<Block*> imm_successors;
197 166
198 /// Intrusively store the value of a register in the block. 167 /// Intrusively store the value of a register in the block.
199 std::array<Value, NUM_REGS> ssa_reg_values; 168 std::array<Value, NUM_REGS> ssa_reg_values;
diff --git a/src/shader_recompiler/frontend/ir/ir_emitter.cpp b/src/shader_recompiler/frontend/ir/ir_emitter.cpp
index ce6c9af07..eb45aa477 100644
--- a/src/shader_recompiler/frontend/ir/ir_emitter.cpp
+++ b/src/shader_recompiler/frontend/ir/ir_emitter.cpp
@@ -61,25 +61,28 @@ F64 IREmitter::Imm64(f64 value) const {
61 return F64{Value{value}}; 61 return F64{Value{value}};
62} 62}
63 63
64void IREmitter::Branch(Block* label) { 64void IREmitter::Prologue() {
65 label->AddImmediatePredecessor(block); 65 Inst(Opcode::Prologue);
66 block->SetBranch(label);
67 Inst(Opcode::Branch, label);
68} 66}
69 67
70void IREmitter::BranchConditional(const U1& condition, Block* true_label, Block* false_label) { 68void IREmitter::Epilogue() {
71 block->SetBranches(IR::Condition{true}, true_label, false_label); 69 Inst(Opcode::Epilogue);
72 true_label->AddImmediatePredecessor(block);
73 false_label->AddImmediatePredecessor(block);
74 Inst(Opcode::BranchConditional, condition, true_label, false_label);
75} 70}
76 71
77void IREmitter::LoopMerge(Block* merge_block, Block* continue_target) { 72void IREmitter::BranchConditionRef(const U1& cond) {
78 Inst(Opcode::LoopMerge, merge_block, continue_target); 73 Inst(Opcode::BranchConditionRef, cond);
79} 74}
80 75
81void IREmitter::SelectionMerge(Block* merge_block) { 76void IREmitter::DemoteToHelperInvocation() {
82 Inst(Opcode::SelectionMerge, merge_block); 77 Inst(Opcode::DemoteToHelperInvocation);
78}
79
80void IREmitter::EmitVertex(const U32& stream) {
81 Inst(Opcode::EmitVertex, stream);
82}
83
84void IREmitter::EndPrimitive(const U32& stream) {
85 Inst(Opcode::EndPrimitive, stream);
83} 86}
84 87
85void IREmitter::Barrier() { 88void IREmitter::Barrier() {
@@ -94,37 +97,6 @@ void IREmitter::DeviceMemoryBarrier() {
94 Inst(Opcode::DeviceMemoryBarrier); 97 Inst(Opcode::DeviceMemoryBarrier);
95} 98}
96 99
97void IREmitter::Return() {
98 block->SetReturn();
99 Inst(Opcode::Return);
100}
101
102void IREmitter::Unreachable() {
103 Inst(Opcode::Unreachable);
104}
105
106void IREmitter::DemoteToHelperInvocation(Block* continue_label) {
107 block->SetBranch(continue_label);
108 continue_label->AddImmediatePredecessor(block);
109 Inst(Opcode::DemoteToHelperInvocation, continue_label);
110}
111
112void IREmitter::Prologue() {
113 Inst(Opcode::Prologue);
114}
115
116void IREmitter::Epilogue() {
117 Inst(Opcode::Epilogue);
118}
119
120void IREmitter::EmitVertex(const U32& stream) {
121 Inst(Opcode::EmitVertex, stream);
122}
123
124void IREmitter::EndPrimitive(const U32& stream) {
125 Inst(Opcode::EndPrimitive, stream);
126}
127
128U32 IREmitter::GetReg(IR::Reg reg) { 100U32 IREmitter::GetReg(IR::Reg reg) {
129 return Inst<U32>(Opcode::GetRegister, reg); 101 return Inst<U32>(Opcode::GetRegister, reg);
130} 102}
diff --git a/src/shader_recompiler/frontend/ir/ir_emitter.h b/src/shader_recompiler/frontend/ir/ir_emitter.h
index fd41b7e89..7a83c33d3 100644
--- a/src/shader_recompiler/frontend/ir/ir_emitter.h
+++ b/src/shader_recompiler/frontend/ir/ir_emitter.h
@@ -32,17 +32,10 @@ public:
32 [[nodiscard]] U64 Imm64(s64 value) const; 32 [[nodiscard]] U64 Imm64(s64 value) const;
33 [[nodiscard]] F64 Imm64(f64 value) const; 33 [[nodiscard]] F64 Imm64(f64 value) const;
34 34
35 void Branch(Block* label);
36 void BranchConditional(const U1& condition, Block* true_label, Block* false_label);
37 void LoopMerge(Block* merge_block, Block* continue_target);
38 void SelectionMerge(Block* merge_block);
39 void Return();
40 void Unreachable();
41 void DemoteToHelperInvocation(Block* continue_label);
42
43 void Prologue(); 35 void Prologue();
44 void Epilogue(); 36 void Epilogue();
45 37 void BranchConditionRef(const U1& cond);
38 void DemoteToHelperInvocation();
46 void EmitVertex(const U32& stream); 39 void EmitVertex(const U32& stream);
47 void EndPrimitive(const U32& stream); 40 void EndPrimitive(const U32& stream);
48 41
diff --git a/src/shader_recompiler/frontend/ir/microinstruction.cpp b/src/shader_recompiler/frontend/ir/microinstruction.cpp
index 616ef17d4..364574240 100644
--- a/src/shader_recompiler/frontend/ir/microinstruction.cpp
+++ b/src/shader_recompiler/frontend/ir/microinstruction.cpp
@@ -56,19 +56,14 @@ Inst::~Inst() {
56 56
57bool Inst::MayHaveSideEffects() const noexcept { 57bool Inst::MayHaveSideEffects() const noexcept {
58 switch (op) { 58 switch (op) {
59 case Opcode::Branch: 59 case Opcode::Prologue:
60 case Opcode::BranchConditional: 60 case Opcode::Epilogue:
61 case Opcode::LoopMerge: 61 case Opcode::BranchConditionRef:
62 case Opcode::SelectionMerge:
63 case Opcode::Return:
64 case Opcode::Join: 62 case Opcode::Join:
65 case Opcode::Unreachable:
66 case Opcode::DemoteToHelperInvocation: 63 case Opcode::DemoteToHelperInvocation:
67 case Opcode::Barrier: 64 case Opcode::Barrier:
68 case Opcode::WorkgroupMemoryBarrier: 65 case Opcode::WorkgroupMemoryBarrier:
69 case Opcode::DeviceMemoryBarrier: 66 case Opcode::DeviceMemoryBarrier:
70 case Opcode::Prologue:
71 case Opcode::Epilogue:
72 case Opcode::EmitVertex: 67 case Opcode::EmitVertex:
73 case Opcode::EndPrimitive: 68 case Opcode::EndPrimitive:
74 case Opcode::SetAttribute: 69 case Opcode::SetAttribute:
diff --git a/src/shader_recompiler/frontend/ir/opcodes.h b/src/shader_recompiler/frontend/ir/opcodes.h
index 2b9c0ed8c..56b001902 100644
--- a/src/shader_recompiler/frontend/ir/opcodes.h
+++ b/src/shader_recompiler/frontend/ir/opcodes.h
@@ -30,7 +30,6 @@ struct OpcodeMeta {
30// using enum Type; 30// using enum Type;
31constexpr Type Void{Type::Void}; 31constexpr Type Void{Type::Void};
32constexpr Type Opaque{Type::Opaque}; 32constexpr Type Opaque{Type::Opaque};
33constexpr Type Label{Type::Label};
34constexpr Type Reg{Type::Reg}; 33constexpr Type Reg{Type::Reg};
35constexpr Type Pred{Type::Pred}; 34constexpr Type Pred{Type::Pred};
36constexpr Type Attribute{Type::Attribute}; 35constexpr Type Attribute{Type::Attribute};
diff --git a/src/shader_recompiler/frontend/ir/opcodes.inc b/src/shader_recompiler/frontend/ir/opcodes.inc
index 9165421f8..75ddb6b6f 100644
--- a/src/shader_recompiler/frontend/ir/opcodes.inc
+++ b/src/shader_recompiler/frontend/ir/opcodes.inc
@@ -7,27 +7,20 @@ OPCODE(Phi, Opaque,
7OPCODE(Identity, Opaque, Opaque, ) 7OPCODE(Identity, Opaque, Opaque, )
8OPCODE(Void, Void, ) 8OPCODE(Void, Void, )
9 9
10// Control flow 10// Special operations
11OPCODE(Branch, Void, Label, ) 11OPCODE(Prologue, Void, )
12OPCODE(BranchConditional, Void, U1, Label, Label, ) 12OPCODE(Epilogue, Void, )
13OPCODE(LoopMerge, Void, Label, Label, ) 13OPCODE(BranchConditionRef, Void, U1, )
14OPCODE(SelectionMerge, Void, Label, )
15OPCODE(Return, Void, )
16OPCODE(Join, Void, ) 14OPCODE(Join, Void, )
17OPCODE(Unreachable, Void, ) 15OPCODE(DemoteToHelperInvocation, Void, )
18OPCODE(DemoteToHelperInvocation, Void, Label, ) 16OPCODE(EmitVertex, Void, U32, )
17OPCODE(EndPrimitive, Void, U32, )
19 18
20// Barriers 19// Barriers
21OPCODE(Barrier, Void, ) 20OPCODE(Barrier, Void, )
22OPCODE(WorkgroupMemoryBarrier, Void, ) 21OPCODE(WorkgroupMemoryBarrier, Void, )
23OPCODE(DeviceMemoryBarrier, Void, ) 22OPCODE(DeviceMemoryBarrier, Void, )
24 23
25// Special operations
26OPCODE(Prologue, Void, )
27OPCODE(Epilogue, Void, )
28OPCODE(EmitVertex, Void, U32, )
29OPCODE(EndPrimitive, Void, U32, )
30
31// Context getters/setters 24// Context getters/setters
32OPCODE(GetRegister, U32, Reg, ) 25OPCODE(GetRegister, U32, Reg, )
33OPCODE(SetRegister, Void, Reg, U32, ) 26OPCODE(SetRegister, Void, Reg, U32, )
diff --git a/src/shader_recompiler/frontend/ir/post_order.cpp b/src/shader_recompiler/frontend/ir/post_order.cpp
index 8709a2ea1..1a28df7fb 100644
--- a/src/shader_recompiler/frontend/ir/post_order.cpp
+++ b/src/shader_recompiler/frontend/ir/post_order.cpp
@@ -2,6 +2,8 @@
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 <algorithm>
6
5#include <boost/container/flat_set.hpp> 7#include <boost/container/flat_set.hpp>
6#include <boost/container/small_vector.hpp> 8#include <boost/container/small_vector.hpp>
7 9
@@ -10,35 +12,31 @@
10 12
11namespace Shader::IR { 13namespace Shader::IR {
12 14
13BlockList PostOrder(const BlockList& blocks) { 15BlockList PostOrder(const AbstractSyntaxNode& root) {
14 boost::container::small_vector<Block*, 16> block_stack; 16 boost::container::small_vector<Block*, 16> block_stack;
15 boost::container::flat_set<Block*> visited; 17 boost::container::flat_set<Block*> visited;
16
17 BlockList post_order_blocks; 18 BlockList post_order_blocks;
18 post_order_blocks.reserve(blocks.size());
19 19
20 Block* const first_block{blocks.front()}; 20 if (root.type != AbstractSyntaxNode::Type::Block) {
21 throw LogicError("First node in abstract syntax list root is not a block");
22 }
23 Block* const first_block{root.block};
21 visited.insert(first_block); 24 visited.insert(first_block);
22 block_stack.push_back(first_block); 25 block_stack.push_back(first_block);
23 26
24 const auto visit_branch = [&](Block* block, Block* branch) {
25 if (!branch) {
26 return false;
27 }
28 if (!visited.insert(branch).second) {
29 return false;
30 }
31 // Calling push_back twice is faster than insert on MSVC
32 block_stack.push_back(block);
33 block_stack.push_back(branch);
34 return true;
35 };
36 while (!block_stack.empty()) { 27 while (!block_stack.empty()) {
37 Block* const block{block_stack.back()}; 28 Block* const block{block_stack.back()};
29 const auto visit{[&](Block* branch) {
30 if (!visited.insert(branch).second) {
31 return false;
32 }
33 // Calling push_back twice is faster than insert on MSVC
34 block_stack.push_back(block);
35 block_stack.push_back(branch);
36 return true;
37 }};
38 block_stack.pop_back(); 38 block_stack.pop_back();
39 39 if (std::ranges::none_of(block->ImmSuccessors(), visit)) {
40 if (!visit_branch(block, block->TrueBranch()) &&
41 !visit_branch(block, block->FalseBranch())) {
42 post_order_blocks.push_back(block); 40 post_order_blocks.push_back(block);
43 } 41 }
44 } 42 }
diff --git a/src/shader_recompiler/frontend/ir/post_order.h b/src/shader_recompiler/frontend/ir/post_order.h
index 30137ff57..58a0467a0 100644
--- a/src/shader_recompiler/frontend/ir/post_order.h
+++ b/src/shader_recompiler/frontend/ir/post_order.h
@@ -5,9 +5,10 @@
5#pragma once 5#pragma once
6 6
7#include "shader_recompiler/frontend/ir/basic_block.h" 7#include "shader_recompiler/frontend/ir/basic_block.h"
8#include "shader_recompiler/frontend/ir/abstract_syntax_list.h"
8 9
9namespace Shader::IR { 10namespace Shader::IR {
10 11
11BlockList PostOrder(const BlockList& blocks); 12BlockList PostOrder(const AbstractSyntaxNode& root);
12 13
13} // namespace Shader::IR 14} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/program.h b/src/shader_recompiler/frontend/ir/program.h
index 51e1a8c77..9ede5b48d 100644
--- a/src/shader_recompiler/frontend/ir/program.h
+++ b/src/shader_recompiler/frontend/ir/program.h
@@ -7,8 +7,7 @@
7#include <array> 7#include <array>
8#include <string> 8#include <string>
9 9
10#include <boost/container/small_vector.hpp> 10#include "shader_recompiler/frontend/ir/abstract_syntax_list.h"
11
12#include "shader_recompiler/frontend/ir/basic_block.h" 11#include "shader_recompiler/frontend/ir/basic_block.h"
13#include "shader_recompiler/program_header.h" 12#include "shader_recompiler/program_header.h"
14#include "shader_recompiler/shader_info.h" 13#include "shader_recompiler/shader_info.h"
@@ -17,6 +16,7 @@
17namespace Shader::IR { 16namespace Shader::IR {
18 17
19struct Program { 18struct Program {
19 AbstractSyntaxList syntax_list;
20 BlockList blocks; 20 BlockList blocks;
21 BlockList post_order_blocks; 21 BlockList post_order_blocks;
22 Info info; 22 Info info;
diff --git a/src/shader_recompiler/frontend/ir/type.h b/src/shader_recompiler/frontend/ir/type.h
index 8b3b33852..294b230c4 100644
--- a/src/shader_recompiler/frontend/ir/type.h
+++ b/src/shader_recompiler/frontend/ir/type.h
@@ -16,31 +16,30 @@ namespace Shader::IR {
16enum class Type { 16enum class Type {
17 Void = 0, 17 Void = 0,
18 Opaque = 1 << 0, 18 Opaque = 1 << 0,
19 Label = 1 << 1, 19 Reg = 1 << 1,
20 Reg = 1 << 2, 20 Pred = 1 << 2,
21 Pred = 1 << 3, 21 Attribute = 1 << 3,
22 Attribute = 1 << 4, 22 Patch = 1 << 4,
23 Patch = 1 << 5, 23 U1 = 1 << 5,
24 U1 = 1 << 6, 24 U8 = 1 << 6,
25 U8 = 1 << 7, 25 U16 = 1 << 7,
26 U16 = 1 << 8, 26 U32 = 1 << 8,
27 U32 = 1 << 9, 27 U64 = 1 << 9,
28 U64 = 1 << 10, 28 F16 = 1 << 10,
29 F16 = 1 << 11, 29 F32 = 1 << 11,
30 F32 = 1 << 12, 30 F64 = 1 << 12,
31 F64 = 1 << 13, 31 U32x2 = 1 << 13,
32 U32x2 = 1 << 14, 32 U32x3 = 1 << 14,
33 U32x3 = 1 << 15, 33 U32x4 = 1 << 15,
34 U32x4 = 1 << 16, 34 F16x2 = 1 << 16,
35 F16x2 = 1 << 17, 35 F16x3 = 1 << 17,
36 F16x3 = 1 << 18, 36 F16x4 = 1 << 18,
37 F16x4 = 1 << 19, 37 F32x2 = 1 << 19,
38 F32x2 = 1 << 20, 38 F32x3 = 1 << 20,
39 F32x3 = 1 << 21, 39 F32x4 = 1 << 21,
40 F32x4 = 1 << 22, 40 F64x2 = 1 << 22,
41 F64x2 = 1 << 23, 41 F64x3 = 1 << 23,
42 F64x3 = 1 << 24, 42 F64x4 = 1 << 24,
43 F64x4 = 1 << 25,
44}; 43};
45DECLARE_ENUM_FLAG_OPERATORS(Type) 44DECLARE_ENUM_FLAG_OPERATORS(Type)
46 45
diff --git a/src/shader_recompiler/frontend/ir/value.cpp b/src/shader_recompiler/frontend/ir/value.cpp
index b962f170d..d365ea1bc 100644
--- a/src/shader_recompiler/frontend/ir/value.cpp
+++ b/src/shader_recompiler/frontend/ir/value.cpp
@@ -9,8 +9,6 @@ namespace Shader::IR {
9 9
10Value::Value(IR::Inst* value) noexcept : type{Type::Opaque}, inst{value} {} 10Value::Value(IR::Inst* value) noexcept : type{Type::Opaque}, inst{value} {}
11 11
12Value::Value(IR::Block* value) noexcept : type{Type::Label}, label{value} {}
13
14Value::Value(IR::Reg value) noexcept : type{Type::Reg}, reg{value} {} 12Value::Value(IR::Reg value) noexcept : type{Type::Reg}, reg{value} {}
15 13
16Value::Value(IR::Pred value) noexcept : type{Type::Pred}, pred{value} {} 14Value::Value(IR::Pred value) noexcept : type{Type::Pred}, pred{value} {}
@@ -33,10 +31,6 @@ Value::Value(u64 value) noexcept : type{Type::U64}, imm_u64{value} {}
33 31
34Value::Value(f64 value) noexcept : type{Type::F64}, imm_f64{value} {} 32Value::Value(f64 value) noexcept : type{Type::F64}, imm_f64{value} {}
35 33
36bool Value::IsLabel() const noexcept {
37 return type == Type::Label;
38}
39
40IR::Type Value::Type() const noexcept { 34IR::Type Value::Type() const noexcept {
41 if (IsPhi()) { 35 if (IsPhi()) {
42 // The type of a phi node is stored in its flags 36 // The type of a phi node is stored in its flags
@@ -60,8 +54,6 @@ bool Value::operator==(const Value& other) const {
60 return true; 54 return true;
61 case Type::Opaque: 55 case Type::Opaque:
62 return inst == other.inst; 56 return inst == other.inst;
63 case Type::Label:
64 return label == other.label;
65 case Type::Reg: 57 case Type::Reg:
66 return reg == other.reg; 58 return reg == other.reg;
67 case Type::Pred: 59 case Type::Pred:
diff --git a/src/shader_recompiler/frontend/ir/value.h b/src/shader_recompiler/frontend/ir/value.h
index beaf149f3..2ce49f953 100644
--- a/src/shader_recompiler/frontend/ir/value.h
+++ b/src/shader_recompiler/frontend/ir/value.h
@@ -37,7 +37,6 @@ class Value {
37public: 37public:
38 Value() noexcept = default; 38 Value() noexcept = default;
39 explicit Value(IR::Inst* value) noexcept; 39 explicit Value(IR::Inst* value) noexcept;
40 explicit Value(IR::Block* value) noexcept;
41 explicit Value(IR::Reg value) noexcept; 40 explicit Value(IR::Reg value) noexcept;
42 explicit Value(IR::Pred value) noexcept; 41 explicit Value(IR::Pred value) noexcept;
43 explicit Value(IR::Attribute value) noexcept; 42 explicit Value(IR::Attribute value) noexcept;
@@ -54,11 +53,9 @@ public:
54 [[nodiscard]] bool IsPhi() const noexcept; 53 [[nodiscard]] bool IsPhi() const noexcept;
55 [[nodiscard]] bool IsEmpty() const noexcept; 54 [[nodiscard]] bool IsEmpty() const noexcept;
56 [[nodiscard]] bool IsImmediate() const noexcept; 55 [[nodiscard]] bool IsImmediate() const noexcept;
57 [[nodiscard]] bool IsLabel() const noexcept;
58 [[nodiscard]] IR::Type Type() const noexcept; 56 [[nodiscard]] IR::Type Type() const noexcept;
59 57
60 [[nodiscard]] IR::Inst* Inst() const; 58 [[nodiscard]] IR::Inst* Inst() const;
61 [[nodiscard]] IR::Block* Label() const;
62 [[nodiscard]] IR::Inst* InstRecursive() const; 59 [[nodiscard]] IR::Inst* InstRecursive() const;
63 [[nodiscard]] IR::Value Resolve() const; 60 [[nodiscard]] IR::Value Resolve() const;
64 [[nodiscard]] IR::Reg Reg() const; 61 [[nodiscard]] IR::Reg Reg() const;
@@ -80,7 +77,6 @@ private:
80 IR::Type type{}; 77 IR::Type type{};
81 union { 78 union {
82 IR::Inst* inst{}; 79 IR::Inst* inst{};
83 IR::Block* label;
84 IR::Reg reg; 80 IR::Reg reg;
85 IR::Pred pred; 81 IR::Pred pred;
86 IR::Attribute attribute; 82 IR::Attribute attribute;
@@ -304,11 +300,6 @@ inline IR::Inst* Value::Inst() const {
304 return inst; 300 return inst;
305} 301}
306 302
307inline IR::Block* Value::Label() const {
308 DEBUG_ASSERT(type == Type::Label);
309 return label;
310}
311
312inline IR::Inst* Value::InstRecursive() const { 303inline IR::Inst* Value::InstRecursive() const {
313 DEBUG_ASSERT(type == Type::Opaque); 304 DEBUG_ASSERT(type == Type::Opaque);
314 if (IsIdentity()) { 305 if (IsIdentity()) {
diff --git a/src/shader_recompiler/frontend/maxwell/program.cpp b/src/shader_recompiler/frontend/maxwell/program.cpp
index 0d3f00699..017c4b8fd 100644
--- a/src/shader_recompiler/frontend/maxwell/program.cpp
+++ b/src/shader_recompiler/frontend/maxwell/program.cpp
@@ -4,6 +4,7 @@
4 4
5#include <algorithm> 5#include <algorithm>
6#include <memory> 6#include <memory>
7#include <ranges>
7#include <vector> 8#include <vector>
8 9
9#include "shader_recompiler/frontend/ir/basic_block.h" 10#include "shader_recompiler/frontend/ir/basic_block.h"
@@ -15,6 +16,16 @@
15 16
16namespace Shader::Maxwell { 17namespace Shader::Maxwell {
17namespace { 18namespace {
19IR::BlockList GenerateBlocks(const IR::AbstractSyntaxList& syntax_list) {
20 auto syntax_blocks{syntax_list | std::views::filter([](const auto& node) {
21 return node.type == IR::AbstractSyntaxNode::Type::Block;
22 })};
23 IR::BlockList blocks(std::ranges::distance(syntax_blocks));
24 std::ranges::transform(syntax_blocks, blocks.begin(),
25 [](const IR::AbstractSyntaxNode& node) { return node.block; });
26 return blocks;
27}
28
18void RemoveUnreachableBlocks(IR::Program& program) { 29void RemoveUnreachableBlocks(IR::Program& program) {
19 // Some blocks might be unreachable if a function call exists unconditionally 30 // Some blocks might be unreachable if a function call exists unconditionally
20 // If this happens the number of blocks and post order blocks will mismatch 31 // If this happens the number of blocks and post order blocks will mismatch
@@ -23,7 +34,7 @@ void RemoveUnreachableBlocks(IR::Program& program) {
23 } 34 }
24 const auto begin{program.blocks.begin() + 1}; 35 const auto begin{program.blocks.begin() + 1};
25 const auto end{program.blocks.end()}; 36 const auto end{program.blocks.end()};
26 const auto pred{[](IR::Block* block) { return block->ImmediatePredecessors().empty(); }}; 37 const auto pred{[](IR::Block* block) { return block->ImmPredecessors().empty(); }};
27 program.blocks.erase(std::remove_if(begin, end, pred), end); 38 program.blocks.erase(std::remove_if(begin, end, pred), end);
28} 39}
29 40
@@ -110,8 +121,9 @@ void AddNVNStorageBuffers(IR::Program& program) {
110IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool, 121IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
111 Environment& env, Flow::CFG& cfg) { 122 Environment& env, Flow::CFG& cfg) {
112 IR::Program program; 123 IR::Program program;
113 program.blocks = VisitAST(inst_pool, block_pool, env, cfg); 124 program.syntax_list = BuildASL(inst_pool, block_pool, env, cfg);
114 program.post_order_blocks = PostOrder(program.blocks); 125 program.blocks = GenerateBlocks(program.syntax_list);
126 program.post_order_blocks = PostOrder(program.syntax_list.front());
115 program.stage = env.ShaderStage(); 127 program.stage = env.ShaderStage();
116 program.local_memory_size = env.LocalMemorySize(); 128 program.local_memory_size = env.LocalMemorySize();
117 switch (program.stage) { 129 switch (program.stage) {
@@ -159,9 +171,7 @@ IR::Program MergeDualVertexPrograms(IR::Program& vertex_a, IR::Program& vertex_b
159 Optimization::VertexATransformPass(vertex_a); 171 Optimization::VertexATransformPass(vertex_a);
160 Optimization::VertexBTransformPass(vertex_b); 172 Optimization::VertexBTransformPass(vertex_b);
161 std::swap(result.blocks, vertex_a.blocks); 173 std::swap(result.blocks, vertex_a.blocks);
162 for (IR::Block* block : vertex_b.blocks) { 174 result.blocks.insert(result.blocks.end(), vertex_b.blocks.begin(), vertex_b.blocks.end());
163 result.blocks.push_back(block);
164 }
165 result.stage = Stage::VertexB; 175 result.stage = Stage::VertexB;
166 result.info = vertex_a.info; 176 result.info = vertex_a.info;
167 result.local_memory_size = std::max(vertex_a.local_memory_size, vertex_b.local_memory_size); 177 result.local_memory_size = std::max(vertex_a.local_memory_size, vertex_b.local_memory_size);
@@ -173,7 +183,7 @@ IR::Program MergeDualVertexPrograms(IR::Program& vertex_a, IR::Program& vertex_b
173 Optimization::JoinTextureInfo(result.info, vertex_b.info); 183 Optimization::JoinTextureInfo(result.info, vertex_b.info);
174 Optimization::JoinStorageInfo(result.info, vertex_b.info); 184 Optimization::JoinStorageInfo(result.info, vertex_b.info);
175 Optimization::DualVertexJoinPass(result); 185 Optimization::DualVertexJoinPass(result);
176 result.post_order_blocks = PostOrder(result.blocks); 186 result.post_order_blocks = PostOrder(result.syntax_list.front());
177 Optimization::DeadCodeEliminationPass(result); 187 Optimization::DeadCodeEliminationPass(result);
178 Optimization::VerificationPass(result); 188 Optimization::VerificationPass(result);
179 Optimization::CollectShaderInfoPass(env_vertex_b, result); 189 Optimization::CollectShaderInfoPass(env_vertex_b, result);
diff --git a/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp b/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
index cc5410c6d..e7e2e9c82 100644
--- a/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
+++ b/src/shader_recompiler/frontend/maxwell/structured_control_flow.cpp
@@ -36,7 +36,6 @@ using Tree = boost::intrusive::list<Statement,
36 // Avoid linear complexity on splice, size is never called 36 // Avoid linear complexity on splice, size is never called
37 boost::intrusive::constant_time_size<false>>; 37 boost::intrusive::constant_time_size<false>>;
38using Node = Tree::iterator; 38using Node = Tree::iterator;
39using ConstNode = Tree::const_iterator;
40 39
41enum class StatementType { 40enum class StatementType {
42 Code, 41 Code,
@@ -91,7 +90,8 @@ struct IndirectBranchCond {};
91#pragma warning(disable : 26495) // Always initialize a member variable, expected in Statement 90#pragma warning(disable : 26495) // Always initialize a member variable, expected in Statement
92#endif 91#endif
93struct Statement : ListBaseHook { 92struct Statement : ListBaseHook {
94 Statement(IR::Block* code_, Statement* up_) : code{code_}, up{up_}, type{StatementType::Code} {} 93 Statement(const Flow::Block* block_, Statement* up_)
94 : block{block_}, up{up_}, type{StatementType::Code} {}
95 Statement(Goto, Statement* cond_, Node label_, Statement* up_) 95 Statement(Goto, Statement* cond_, Node label_, Statement* up_)
96 : label{label_}, cond{cond_}, up{up_}, type{StatementType::Goto} {} 96 : label{label_}, cond{cond_}, up{up_}, type{StatementType::Goto} {}
97 Statement(Label, u32 id_, Statement* up_) : id{id_}, up{up_}, type{StatementType::Label} {} 97 Statement(Label, u32 id_, Statement* up_) : id{id_}, up{up_}, type{StatementType::Label} {}
@@ -125,7 +125,7 @@ struct Statement : ListBaseHook {
125 } 125 }
126 126
127 union { 127 union {
128 IR::Block* code; 128 const Flow::Block* block;
129 Node label; 129 Node label;
130 Tree children; 130 Tree children;
131 IR::Condition guest_cond; 131 IR::Condition guest_cond;
@@ -171,8 +171,8 @@ std::string DumpTree(const Tree& tree, u32 indentation = 0) {
171 switch (stmt->type) { 171 switch (stmt->type) {
172 case StatementType::Code: 172 case StatementType::Code:
173 ret += fmt::format("{} Block {:04x} -> {:04x} (0x{:016x});\n", indent, 173 ret += fmt::format("{} Block {:04x} -> {:04x} (0x{:016x});\n", indent,
174 stmt->code->LocationBegin(), stmt->code->LocationEnd(), 174 stmt->block->begin, stmt->block->end,
175 reinterpret_cast<uintptr_t>(stmt->code)); 175 reinterpret_cast<uintptr_t>(stmt->block));
176 break; 176 break;
177 case StatementType::Goto: 177 case StatementType::Goto:
178 ret += fmt::format("{} if ({}) goto L{};\n", indent, DumpExpr(stmt->cond), 178 ret += fmt::format("{} if ({}) goto L{};\n", indent, DumpExpr(stmt->cond),
@@ -407,11 +407,7 @@ private:
407 }}; 407 }};
408 root.push_front(make_reset_variable()); 408 root.push_front(make_reset_variable());
409 root.insert(ip, make_reset_variable()); 409 root.insert(ip, make_reset_variable());
410 410 root.insert(ip, *pool.Create(&block, &root_stmt));
411 const u32 begin_offset{block.begin.Offset()};
412 const u32 end_offset{block.end.Offset()};
413 IR::Block* const ir_block{block_pool.Create(inst_pool, begin_offset, end_offset)};
414 root.insert(ip, *pool.Create(ir_block, &root_stmt));
415 411
416 switch (block.end_class) { 412 switch (block.end_class) {
417 case Flow::EndClass::Branch: { 413 case Flow::EndClass::Branch: {
@@ -620,13 +616,13 @@ private:
620 Statement root_stmt{FunctionTag{}}; 616 Statement root_stmt{FunctionTag{}};
621}; 617};
622 618
623IR::Block* TryFindForwardBlock(const Statement& stmt) { 619[[nodiscard]] Statement* TryFindForwardBlock(Statement& stmt) {
624 const Tree& tree{stmt.up->children}; 620 Tree& tree{stmt.up->children};
625 const ConstNode end{tree.cend()}; 621 const Node end{tree.end()};
626 ConstNode forward_node{std::next(Tree::s_iterator_to(stmt))}; 622 Node forward_node{std::next(Tree::s_iterator_to(stmt))};
627 while (forward_node != end && !HasChildren(forward_node->type)) { 623 while (forward_node != end && !HasChildren(forward_node->type)) {
628 if (forward_node->type == StatementType::Code) { 624 if (forward_node->type == StatementType::Code) {
629 return forward_node->code; 625 return &*forward_node;
630 } 626 }
631 ++forward_node; 627 ++forward_node;
632 } 628 }
@@ -654,21 +650,29 @@ class TranslatePass {
654public: 650public:
655 TranslatePass(ObjectPool<IR::Inst>& inst_pool_, ObjectPool<IR::Block>& block_pool_, 651 TranslatePass(ObjectPool<IR::Inst>& inst_pool_, ObjectPool<IR::Block>& block_pool_,
656 ObjectPool<Statement>& stmt_pool_, Environment& env_, Statement& root_stmt, 652 ObjectPool<Statement>& stmt_pool_, Environment& env_, Statement& root_stmt,
657 IR::BlockList& block_list_) 653 IR::AbstractSyntaxList& syntax_list_)
658 : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, env{env_}, 654 : stmt_pool{stmt_pool_}, inst_pool{inst_pool_}, block_pool{block_pool_}, env{env_},
659 block_list{block_list_} { 655 syntax_list{syntax_list_} {
660 Visit(root_stmt, nullptr, nullptr); 656 Visit(root_stmt, nullptr, nullptr);
661 657
662 IR::Block& first_block{*block_list.front()}; 658 IR::Block& first_block{*syntax_list.front().block};
663 IR::IREmitter ir{first_block, first_block.begin()}; 659 IR::IREmitter ir{first_block, first_block.begin()};
664 ir.Prologue(); 660 ir.Prologue();
665 } 661 }
666 662
667private: 663private:
668 void Visit(Statement& parent, IR::Block* continue_block, IR::Block* break_block) { 664 void Visit(Statement& parent, IR::Block* break_block, IR::Block* fallthrough_block) {
665 IR::Block* current_block{};
666 const auto ensure_block{[&] {
667 if (current_block) {
668 return;
669 }
670 current_block = block_pool.Create(inst_pool);
671 auto& node{syntax_list.emplace_back()};
672 node.type = IR::AbstractSyntaxNode::Type::Block;
673 node.block = current_block;
674 }};
669 Tree& tree{parent.children}; 675 Tree& tree{parent.children};
670 IR::Block* current_block{nullptr};
671
672 for (auto it = tree.begin(); it != tree.end(); ++it) { 676 for (auto it = tree.begin(); it != tree.end(); ++it) {
673 Statement& stmt{*it}; 677 Statement& stmt{*it};
674 switch (stmt.type) { 678 switch (stmt.type) {
@@ -676,124 +680,157 @@ private:
676 // Labels can be ignored 680 // Labels can be ignored
677 break; 681 break;
678 case StatementType::Code: { 682 case StatementType::Code: {
679 if (current_block && current_block != stmt.code) { 683 ensure_block();
680 IR::IREmitter{*current_block}.Branch(stmt.code); 684 Translate(env, current_block, stmt.block->begin.Offset(), stmt.block->end.Offset());
681 }
682 current_block = stmt.code;
683 Translate(env, stmt.code);
684 block_list.push_back(stmt.code);
685 break; 685 break;
686 } 686 }
687 case StatementType::SetVariable: { 687 case StatementType::SetVariable: {
688 if (!current_block) { 688 ensure_block();
689 current_block = MergeBlock(parent, stmt);
690 }
691 IR::IREmitter ir{*current_block}; 689 IR::IREmitter ir{*current_block};
692 ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op)); 690 ir.SetGotoVariable(stmt.id, VisitExpr(ir, *stmt.op));
693 break; 691 break;
694 } 692 }
695 case StatementType::SetIndirectBranchVariable: { 693 case StatementType::SetIndirectBranchVariable: {
696 if (!current_block) { 694 ensure_block();
697 current_block = MergeBlock(parent, stmt);
698 }
699 IR::IREmitter ir{*current_block}; 695 IR::IREmitter ir{*current_block};
700 IR::U32 address{ir.IAdd(ir.GetReg(stmt.branch_reg), ir.Imm32(stmt.branch_offset))}; 696 IR::U32 address{ir.IAdd(ir.GetReg(stmt.branch_reg), ir.Imm32(stmt.branch_offset))};
701 ir.SetIndirectBranchVariable(address); 697 ir.SetIndirectBranchVariable(address);
702 break; 698 break;
703 } 699 }
704 case StatementType::If: { 700 case StatementType::If: {
705 if (!current_block) { 701 ensure_block();
706 current_block = block_pool.Create(inst_pool);
707 block_list.push_back(current_block);
708 }
709 IR::Block* const merge_block{MergeBlock(parent, stmt)}; 702 IR::Block* const merge_block{MergeBlock(parent, stmt)};
710 703
711 // Visit children
712 const size_t first_block_index{block_list.size()};
713 Visit(stmt, merge_block, break_block);
714
715 // Implement if header block 704 // Implement if header block
716 IR::Block* const first_if_block{block_list.at(first_block_index)};
717 IR::IREmitter ir{*current_block}; 705 IR::IREmitter ir{*current_block};
718 const IR::U1 cond{VisitExpr(ir, *stmt.cond)}; 706 const IR::U1 cond{VisitExpr(ir, *stmt.cond)};
719 ir.SelectionMerge(merge_block); 707 ir.BranchConditionRef(cond);
720 ir.BranchConditional(cond, first_if_block, merge_block);
721 708
709 const size_t if_node_index{syntax_list.size()};
710 syntax_list.emplace_back();
711
712 // Visit children
713 const size_t then_block_index{syntax_list.size()};
714 Visit(stmt, break_block, merge_block);
715
716 IR::Block* const then_block{syntax_list.at(then_block_index).block};
717 current_block->AddBranch(then_block);
718 current_block->AddBranch(merge_block);
722 current_block = merge_block; 719 current_block = merge_block;
720
721 auto& if_node{syntax_list[if_node_index]};
722 if_node.type = IR::AbstractSyntaxNode::Type::If;
723 if_node.if_node.cond = cond;
724 if_node.if_node.body = then_block;
725 if_node.if_node.merge = merge_block;
726
727 auto& endif_node{syntax_list.emplace_back()};
728 endif_node.type = IR::AbstractSyntaxNode::Type::EndIf;
729 endif_node.end_if.merge = merge_block;
730
731 auto& merge{syntax_list.emplace_back()};
732 merge.type = IR::AbstractSyntaxNode::Type::Block;
733 merge.block = merge_block;
723 break; 734 break;
724 } 735 }
725 case StatementType::Loop: { 736 case StatementType::Loop: {
726 IR::Block* const loop_header_block{block_pool.Create(inst_pool)}; 737 IR::Block* const loop_header_block{block_pool.Create(inst_pool)};
727 if (current_block) { 738 if (current_block) {
728 IR::IREmitter{*current_block}.Branch(loop_header_block); 739 current_block->AddBranch(loop_header_block);
729 } 740 }
730 block_list.push_back(loop_header_block); 741 auto& header_node{syntax_list.emplace_back()};
742 header_node.type = IR::AbstractSyntaxNode::Type::Block;
743 header_node.block = loop_header_block;
731 744
732 IR::Block* const new_continue_block{block_pool.Create(inst_pool)}; 745 IR::Block* const continue_block{block_pool.Create(inst_pool)};
733 IR::Block* const merge_block{MergeBlock(parent, stmt)}; 746 IR::Block* const merge_block{MergeBlock(parent, stmt)};
734 747
748 const size_t loop_node_index{syntax_list.size()};
749 syntax_list.emplace_back();
750
735 // Visit children 751 // Visit children
736 const size_t first_block_index{block_list.size()}; 752 const size_t body_block_index{syntax_list.size()};
737 Visit(stmt, new_continue_block, merge_block); 753 Visit(stmt, merge_block, continue_block);
738 754
739 // The continue block is located at the end of the loop 755 // The continue block is located at the end of the loop
740 block_list.push_back(new_continue_block); 756 IR::IREmitter ir{*continue_block};
757 const IR::U1 cond{VisitExpr(ir, *stmt.cond)};
758 ir.BranchConditionRef(cond);
741 759
742 // Implement loop header block 760 IR::Block* const body_block{syntax_list.at(body_block_index).block};
743 IR::Block* const first_loop_block{block_list.at(first_block_index)}; 761 loop_header_block->AddBranch(body_block);
744 IR::IREmitter ir{*loop_header_block};
745 ir.LoopMerge(merge_block, new_continue_block);
746 ir.Branch(first_loop_block);
747 762
748 // Implement continue block 763 continue_block->AddBranch(loop_header_block);
749 IR::IREmitter continue_ir{*new_continue_block}; 764 continue_block->AddBranch(merge_block);
750 const IR::U1 continue_cond{VisitExpr(continue_ir, *stmt.cond)};
751 continue_ir.BranchConditional(continue_cond, ir.block, merge_block);
752 765
753 current_block = merge_block; 766 current_block = merge_block;
767
768 auto& loop{syntax_list[loop_node_index]};
769 loop.type = IR::AbstractSyntaxNode::Type::Loop;
770 loop.loop.body = body_block;
771 loop.loop.continue_block = continue_block;
772 loop.loop.merge = merge_block;
773
774 auto& continue_block_node{syntax_list.emplace_back()};
775 continue_block_node.type = IR::AbstractSyntaxNode::Type::Block;
776 continue_block_node.block = continue_block;
777
778 auto& repeat{syntax_list.emplace_back()};
779 repeat.type = IR::AbstractSyntaxNode::Type::Repeat;
780 repeat.repeat.cond = cond;
781 repeat.repeat.loop_header = loop_header_block;
782 repeat.repeat.merge = merge_block;
783
784 auto& merge{syntax_list.emplace_back()};
785 merge.type = IR::AbstractSyntaxNode::Type::Block;
786 merge.block = merge_block;
754 break; 787 break;
755 } 788 }
756 case StatementType::Break: { 789 case StatementType::Break: {
757 if (!current_block) { 790 ensure_block();
758 current_block = block_pool.Create(inst_pool);
759 block_list.push_back(current_block);
760 }
761 IR::Block* const skip_block{MergeBlock(parent, stmt)}; 791 IR::Block* const skip_block{MergeBlock(parent, stmt)};
762 792
763 IR::IREmitter ir{*current_block}; 793 IR::IREmitter ir{*current_block};
764 ir.BranchConditional(VisitExpr(ir, *stmt.cond), break_block, skip_block); 794 const IR::U1 cond{VisitExpr(ir, *stmt.cond)};
765 795 ir.BranchConditionRef(cond);
796 current_block->AddBranch(break_block);
797 current_block->AddBranch(skip_block);
766 current_block = skip_block; 798 current_block = skip_block;
799
800 auto& break_node{syntax_list.emplace_back()};
801 break_node.type = IR::AbstractSyntaxNode::Type::Break;
802 break_node.break_node.cond = cond;
803 break_node.break_node.merge = break_block;
804 break_node.break_node.skip = skip_block;
805
806 auto& merge{syntax_list.emplace_back()};
807 merge.type = IR::AbstractSyntaxNode::Type::Block;
808 merge.block = skip_block;
767 break; 809 break;
768 } 810 }
769 case StatementType::Return: { 811 case StatementType::Return: {
770 if (!current_block) { 812 ensure_block();
771 current_block = block_pool.Create(inst_pool); 813 IR::IREmitter{*current_block}.Epilogue();
772 block_list.push_back(current_block);
773 }
774 IR::IREmitter ir{*current_block};
775 ir.Epilogue();
776 ir.Return();
777 current_block = nullptr; 814 current_block = nullptr;
815 syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Return;
778 break; 816 break;
779 } 817 }
780 case StatementType::Kill: { 818 case StatementType::Kill: {
781 if (!current_block) { 819 ensure_block();
782 current_block = block_pool.Create(inst_pool);
783 block_list.push_back(current_block);
784 }
785 IR::Block* demote_block{MergeBlock(parent, stmt)}; 820 IR::Block* demote_block{MergeBlock(parent, stmt)};
786 IR::IREmitter{*current_block}.DemoteToHelperInvocation(demote_block); 821 IR::IREmitter{*current_block}.DemoteToHelperInvocation();
822 current_block->AddBranch(demote_block);
787 current_block = demote_block; 823 current_block = demote_block;
824
825 auto& merge{syntax_list.emplace_back()};
826 merge.type = IR::AbstractSyntaxNode::Type::Block;
827 merge.block = demote_block;
788 break; 828 break;
789 } 829 }
790 case StatementType::Unreachable: { 830 case StatementType::Unreachable: {
791 if (!current_block) { 831 ensure_block();
792 current_block = block_pool.Create(inst_pool);
793 block_list.push_back(current_block);
794 }
795 IR::IREmitter{*current_block}.Unreachable();
796 current_block = nullptr; 832 current_block = nullptr;
833 syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Unreachable;
797 break; 834 break;
798 } 835 }
799 default: 836 default:
@@ -801,42 +838,42 @@ private:
801 } 838 }
802 } 839 }
803 if (current_block) { 840 if (current_block) {
804 IR::IREmitter ir{*current_block}; 841 if (fallthrough_block) {
805 if (continue_block) { 842 current_block->AddBranch(fallthrough_block);
806 ir.Branch(continue_block);
807 } else { 843 } else {
808 ir.Unreachable(); 844 syntax_list.emplace_back().type = IR::AbstractSyntaxNode::Type::Unreachable;
809 } 845 }
810 } 846 }
811 } 847 }
812 848
813 IR::Block* MergeBlock(Statement& parent, Statement& stmt) { 849 IR::Block* MergeBlock(Statement& parent, Statement& stmt) {
814 if (IR::Block* const block{TryFindForwardBlock(stmt)}) { 850 Statement* merge_stmt{TryFindForwardBlock(stmt)};
815 return block; 851 if (!merge_stmt) {
852 // Create a merge block we can visit later
853 merge_stmt = stmt_pool.Create(&dummy_flow_block, &parent);
854 parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
816 } 855 }
817 // Create a merge block we can visit later 856 return block_pool.Create(inst_pool);
818 IR::Block* const block{block_pool.Create(inst_pool)};
819 Statement* const merge_stmt{stmt_pool.Create(block, &parent)};
820 parent.children.insert(std::next(Tree::s_iterator_to(stmt)), *merge_stmt);
821 return block;
822 } 857 }
823 858
824 ObjectPool<Statement>& stmt_pool; 859 ObjectPool<Statement>& stmt_pool;
825 ObjectPool<IR::Inst>& inst_pool; 860 ObjectPool<IR::Inst>& inst_pool;
826 ObjectPool<IR::Block>& block_pool; 861 ObjectPool<IR::Block>& block_pool;
827 Environment& env; 862 Environment& env;
828 IR::BlockList& block_list; 863 IR::AbstractSyntaxList& syntax_list;
864 // TODO: Make this constexpr when std::vector is constexpr
865 const Flow::Block dummy_flow_block;
829}; 866};
830} // Anonymous namespace 867} // Anonymous namespace
831 868
832IR::BlockList VisitAST(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool, 869IR::AbstractSyntaxList BuildASL(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Block>& block_pool,
833 Environment& env, Flow::CFG& cfg) { 870 Environment& env, Flow::CFG& cfg) {
834 ObjectPool<Statement> stmt_pool{64}; 871 ObjectPool<Statement> stmt_pool{64};
835 GotoPass goto_pass{cfg, inst_pool, block_pool, stmt_pool}; 872 GotoPass goto_pass{cfg, inst_pool, block_pool, stmt_pool};
836 Statement& root{goto_pass.RootStatement()}; 873 Statement& root{goto_pass.RootStatement()};
837 IR::BlockList block_list; 874 IR::AbstractSyntaxList syntax_list;
838 TranslatePass{inst_pool, block_pool, stmt_pool, env, root, block_list}; 875 TranslatePass{inst_pool, block_pool, stmt_pool, env, root, syntax_list};
839 return block_list; 876 return syntax_list;
840} 877}
841 878
842} // namespace Shader::Maxwell 879} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/structured_control_flow.h b/src/shader_recompiler/frontend/maxwell/structured_control_flow.h
index a6be12ba2..88b083649 100644
--- a/src/shader_recompiler/frontend/maxwell/structured_control_flow.h
+++ b/src/shader_recompiler/frontend/maxwell/structured_control_flow.h
@@ -4,12 +4,8 @@
4 4
5#pragma once 5#pragma once
6 6
7#include <functional>
8#include <span>
9
10#include <boost/intrusive/list.hpp>
11
12#include "shader_recompiler/environment.h" 7#include "shader_recompiler/environment.h"
8#include "shader_recompiler/frontend/ir/abstract_syntax_list.h"
13#include "shader_recompiler/frontend/ir/basic_block.h" 9#include "shader_recompiler/frontend/ir/basic_block.h"
14#include "shader_recompiler/frontend/ir/value.h" 10#include "shader_recompiler/frontend/ir/value.h"
15#include "shader_recompiler/frontend/maxwell/control_flow.h" 11#include "shader_recompiler/frontend/maxwell/control_flow.h"
@@ -17,8 +13,8 @@
17 13
18namespace Shader::Maxwell { 14namespace Shader::Maxwell {
19 15
20[[nodiscard]] IR::BlockList VisitAST(ObjectPool<IR::Inst>& inst_pool, 16[[nodiscard]] IR::AbstractSyntaxList BuildASL(ObjectPool<IR::Inst>& inst_pool,
21 ObjectPool<IR::Block>& block_pool, Environment& env, 17 ObjectPool<IR::Block>& block_pool, Environment& env,
22 Flow::CFG& cfg); 18 Flow::CFG& cfg);
23 19
24} // namespace Shader::Maxwell 20} // namespace Shader::Maxwell
diff --git a/src/shader_recompiler/frontend/maxwell/translate/translate.cpp b/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
index f1230f58f..0f4e7a251 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
+++ b/src/shader_recompiler/frontend/maxwell/translate/translate.cpp
@@ -23,13 +23,12 @@ static void Invoke(TranslatorVisitor& visitor, Location pc, u64 insn) {
23 } 23 }
24} 24}
25 25
26void Translate(Environment& env, IR::Block* block) { 26void Translate(Environment& env, IR::Block* block, u32 location_begin, u32 location_end) {
27 if (block->IsVirtual()) { 27 if (location_begin == location_end) {
28 return; 28 return;
29 } 29 }
30 TranslatorVisitor visitor{env, *block}; 30 TranslatorVisitor visitor{env, *block};
31 const Location pc_end{block->LocationEnd()}; 31 for (Location pc = location_begin; pc != location_end; ++pc) {
32 for (Location pc = block->LocationBegin(); pc != pc_end; ++pc) {
33 const u64 insn{env.ReadInstruction(pc.Offset())}; 32 const u64 insn{env.ReadInstruction(pc.Offset())};
34 const Opcode opcode{Decode(insn)}; 33 const Opcode opcode{Decode(insn)};
35 switch (opcode) { 34 switch (opcode) {
diff --git a/src/shader_recompiler/frontend/maxwell/translate/translate.h b/src/shader_recompiler/frontend/maxwell/translate/translate.h
index e1aa2e0f4..a3edd2e46 100644
--- a/src/shader_recompiler/frontend/maxwell/translate/translate.h
+++ b/src/shader_recompiler/frontend/maxwell/translate/translate.h
@@ -9,6 +9,6 @@
9 9
10namespace Shader::Maxwell { 10namespace Shader::Maxwell {
11 11
12void Translate(Environment& env, IR::Block* block); 12void Translate(Environment& env, IR::Block* block, u32 location_begin, u32 location_end);
13 13
14} // namespace Shader::Maxwell 14} // namespace Shader::Maxwell
HIC SVNT DRACONES