From 6c4cc0cd062fbbba5349da1108d3c23cb330ca8a Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Tue, 2 Feb 2021 21:07:00 -0300 Subject: shader: SSA and dominance --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 155 ++++++++++++++++++++++ 1 file changed, 155 insertions(+) create mode 100644 src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp new file mode 100644 index 000000000..a4b256a40 --- /dev/null +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -0,0 +1,155 @@ +// Copyright 2021 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +// This file implements the SSA rewriting algorithm proposed in +// +// Simple and Efficient Construction of Static Single Assignment Form. +// Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. (2013) +// In: Jhala R., De Bosschere K. (eds) +// Compiler Construction. CC 2013. +// Lecture Notes in Computer Science, vol 7791. +// Springer, Berlin, Heidelberg +// +// https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6 +// + +#include + +#include + +#include "shader_recompiler/frontend/ir/basic_block.h" +#include "shader_recompiler/frontend/ir/function.h" +#include "shader_recompiler/frontend/ir/microinstruction.h" +#include "shader_recompiler/frontend/ir/opcode.h" +#include "shader_recompiler/frontend/ir/pred.h" +#include "shader_recompiler/frontend/ir/reg.h" +#include "shader_recompiler/ir_opt/passes.h" + +namespace Shader::Optimization { +namespace { +using ValueMap = boost::container::flat_map>; + +struct DefTable { + [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { + return regs[IR::RegIndex(variable)]; + } + + [[nodiscard]] ValueMap& operator[](IR::Pred variable) noexcept { + return preds[IR::PredIndex(variable)]; + } + + std::array regs; + std::array preds; +}; + +IR::Opcode UndefOpcode(IR::Reg) noexcept { + return IR::Opcode::Undef32; +} + +IR::Opcode UndefOpcode(IR::Pred) noexcept { + return IR::Opcode::Undef1; +} + +[[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { + return inst.Opcode() == IR::Opcode::Phi; +} + +class Pass { +public: + void WriteVariable(auto variable, IR::Block* block, const IR::Value& value) { + current_def[variable].insert_or_assign(block, value); + } + + IR::Value ReadVariable(auto variable, IR::Block* block) { + auto& def{current_def[variable]}; + if (const auto it{def.find(block)}; it != def.end()) { + return it->second; + } + return ReadVariableRecursive(variable, block); + } + +private: + IR::Value ReadVariableRecursive(auto variable, IR::Block* block) { + IR::Value val; + if (const std::span preds{block->ImmediatePredecessors()}; preds.size() == 1) { + val = ReadVariable(variable, preds.front()); + } else { + // Break potential cycles with operandless phi + val = IR::Value{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + WriteVariable(variable, block, val); + val = AddPhiOperands(variable, val, block); + } + WriteVariable(variable, block, val); + return val; + } + + IR::Value AddPhiOperands(auto variable, const IR::Value& phi, IR::Block* block) { + for (IR::Block* const pred : block->ImmediatePredecessors()) { + phi.Inst()->AddPhiOperand(pred, ReadVariable(variable, pred)); + } + return TryRemoveTrivialPhi(phi, block, UndefOpcode(variable)); + } + + IR::Value TryRemoveTrivialPhi(const IR::Value& phi, IR::Block* block, IR::Opcode undef_opcode) { + IR::Value same; + for (const auto& pair : phi.Inst()->PhiOperands()) { + const IR::Value& op{pair.second}; + if (op == same || op == phi) { + // Unique value or self-reference + continue; + } + if (!same.IsEmpty()) { + // The phi merges at least two values: not trivial + return phi; + } + same = op; + } + if (same.IsEmpty()) { + // The phi is unreachable or in the start block + const auto first_not_phi{std::ranges::find_if_not(block->Instructions(), IsPhi)}; + same = IR::Value{&*block->PrependNewInst(first_not_phi, undef_opcode)}; + } + // Reroute all uses of phi to same and remove phi + phi.Inst()->ReplaceUsesWith(same); + // TODO: Try to recursively remove all phi users, which might have become trivial + return same; + } + + DefTable current_def; +}; +} // Anonymous namespace + +void SsaRewritePass(IR::Function& function) { + Pass pass; + for (const auto& block : function.blocks) { + for (IR::Inst& inst : block->Instructions()) { + switch (inst.Opcode()) { + case IR::Opcode::SetRegister: + if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { + pass.WriteVariable(reg, block.get(), inst.Arg(1)); + } + break; + case IR::Opcode::SetPred: + if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { + pass.WriteVariable(pred, block.get(), inst.Arg(1)); + } + break; + case IR::Opcode::GetRegister: + if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { + inst.ReplaceUsesWith(pass.ReadVariable(reg, block.get())); + } + break; + case IR::Opcode::GetPred: + if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { + inst.ReplaceUsesWith(pass.ReadVariable(pred, block.get())); + } + break; + default: + break; + } + } + } +} + +} // namespace Shader::Optimization -- cgit v1.2.3 From e81739493a0cacc1efe3295f9d287d5d31b1a989 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 5 Feb 2021 05:58:02 -0300 Subject: shader: Constant propagation and global memory to storage buffer --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 56 ++++++++++++++++++++++- 1 file changed, 54 insertions(+), 2 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index a4b256a40..3c9b020e0 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -14,8 +14,6 @@ // https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6 // -#include - #include #include "shader_recompiler/frontend/ir/basic_block.h" @@ -30,6 +28,12 @@ namespace Shader::Optimization { namespace { using ValueMap = boost::container::flat_map>; +struct FlagTag {}; +struct ZeroFlagTag : FlagTag {}; +struct SignFlagTag : FlagTag {}; +struct CarryFlagTag : FlagTag {}; +struct OverflowFlagTag : FlagTag {}; + struct DefTable { [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { return regs[IR::RegIndex(variable)]; @@ -39,8 +43,28 @@ struct DefTable { return preds[IR::PredIndex(variable)]; } + [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept { + return zero_flag; + } + + [[nodiscard]] ValueMap& operator[](SignFlagTag) noexcept { + return sign_flag; + } + + [[nodiscard]] ValueMap& operator[](CarryFlagTag) noexcept { + return carry_flag; + } + + [[nodiscard]] ValueMap& operator[](OverflowFlagTag) noexcept { + return overflow_flag; + } + std::array regs; std::array preds; + ValueMap zero_flag; + ValueMap sign_flag; + ValueMap carry_flag; + ValueMap overflow_flag; }; IR::Opcode UndefOpcode(IR::Reg) noexcept { @@ -51,6 +75,10 @@ IR::Opcode UndefOpcode(IR::Pred) noexcept { return IR::Opcode::Undef1; } +IR::Opcode UndefOpcode(const FlagTag&) noexcept { + return IR::Opcode::Undef1; +} + [[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { return inst.Opcode() == IR::Opcode::Phi; } @@ -135,6 +163,18 @@ void SsaRewritePass(IR::Function& function) { pass.WriteVariable(pred, block.get(), inst.Arg(1)); } break; + case IR::Opcode::SetZFlag: + pass.WriteVariable(ZeroFlagTag{}, block.get(), inst.Arg(0)); + break; + case IR::Opcode::SetSFlag: + pass.WriteVariable(SignFlagTag{}, block.get(), inst.Arg(0)); + break; + case IR::Opcode::SetCFlag: + pass.WriteVariable(CarryFlagTag{}, block.get(), inst.Arg(0)); + break; + case IR::Opcode::SetOFlag: + pass.WriteVariable(OverflowFlagTag{}, block.get(), inst.Arg(0)); + break; case IR::Opcode::GetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { inst.ReplaceUsesWith(pass.ReadVariable(reg, block.get())); @@ -145,6 +185,18 @@ void SsaRewritePass(IR::Function& function) { inst.ReplaceUsesWith(pass.ReadVariable(pred, block.get())); } break; + case IR::Opcode::GetZFlag: + inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block.get())); + break; + case IR::Opcode::GetSFlag: + inst.ReplaceUsesWith(pass.ReadVariable(SignFlagTag{}, block.get())); + break; + case IR::Opcode::GetCFlag: + inst.ReplaceUsesWith(pass.ReadVariable(CarryFlagTag{}, block.get())); + break; + case IR::Opcode::GetOFlag: + inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block.get())); + break; default: break; } -- cgit v1.2.3 From dc04a50ac2aa0bc71db701d0eea857765c2581f0 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 9 Jul 2021 17:11:47 -0300 Subject: shader: Remove illegal character in SSA pass --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 3c9b020e0..a62d3f56b 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -5,7 +5,7 @@ // This file implements the SSA rewriting algorithm proposed in // // Simple and Efficient Construction of Static Single Assignment Form. -// Braun M., Buchwald S., Hack S., Leißa R., Mallon C., Zwinkau A. (2013) +// Braun M., Buchwald S., Hack S., Leiba R., Mallon C., Zwinkau A. (2013) // In: Jhala R., De Bosschere K. (eds) // Compiler Construction. CC 2013. // Lecture Notes in Computer Science, vol 7791. -- cgit v1.2.3 From 16cb00c521cae6e93ec49d10e15b575b7bc4857e Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 5 Feb 2021 23:11:23 -0300 Subject: shader: Add pools and rename files --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 28 +++++++++++------------ 1 file changed, 14 insertions(+), 14 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index a62d3f56b..7713e3ba9 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -19,7 +19,7 @@ #include "shader_recompiler/frontend/ir/basic_block.h" #include "shader_recompiler/frontend/ir/function.h" #include "shader_recompiler/frontend/ir/microinstruction.h" -#include "shader_recompiler/frontend/ir/opcode.h" +#include "shader_recompiler/frontend/ir/opcodes.h" #include "shader_recompiler/frontend/ir/pred.h" #include "shader_recompiler/frontend/ir/reg.h" #include "shader_recompiler/ir_opt/passes.h" @@ -150,52 +150,52 @@ private: void SsaRewritePass(IR::Function& function) { Pass pass; - for (const auto& block : function.blocks) { + for (IR::Block* const block : function.blocks) { for (IR::Inst& inst : block->Instructions()) { switch (inst.Opcode()) { case IR::Opcode::SetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { - pass.WriteVariable(reg, block.get(), inst.Arg(1)); + pass.WriteVariable(reg, block, inst.Arg(1)); } break; case IR::Opcode::SetPred: if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { - pass.WriteVariable(pred, block.get(), inst.Arg(1)); + pass.WriteVariable(pred, block, inst.Arg(1)); } break; case IR::Opcode::SetZFlag: - pass.WriteVariable(ZeroFlagTag{}, block.get(), inst.Arg(0)); + pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); break; case IR::Opcode::SetSFlag: - pass.WriteVariable(SignFlagTag{}, block.get(), inst.Arg(0)); + pass.WriteVariable(SignFlagTag{}, block, inst.Arg(0)); break; case IR::Opcode::SetCFlag: - pass.WriteVariable(CarryFlagTag{}, block.get(), inst.Arg(0)); + pass.WriteVariable(CarryFlagTag{}, block, inst.Arg(0)); break; case IR::Opcode::SetOFlag: - pass.WriteVariable(OverflowFlagTag{}, block.get(), inst.Arg(0)); + pass.WriteVariable(OverflowFlagTag{}, block, inst.Arg(0)); break; case IR::Opcode::GetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { - inst.ReplaceUsesWith(pass.ReadVariable(reg, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(reg, block)); } break; case IR::Opcode::GetPred: if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { - inst.ReplaceUsesWith(pass.ReadVariable(pred, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(pred, block)); } break; case IR::Opcode::GetZFlag: - inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); break; case IR::Opcode::GetSFlag: - inst.ReplaceUsesWith(pass.ReadVariable(SignFlagTag{}, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(SignFlagTag{}, block)); break; case IR::Opcode::GetCFlag: - inst.ReplaceUsesWith(pass.ReadVariable(CarryFlagTag{}, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(CarryFlagTag{}, block)); break; case IR::Opcode::GetOFlag: - inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block.get())); + inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); break; default: break; -- cgit v1.2.3 From da8096e6e35af250dcc56a1af76b8a211df63a90 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Sat, 6 Feb 2021 02:38:22 -0300 Subject: shader: Properly store phi on Inst --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 7713e3ba9..15a9db90a 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -104,32 +104,34 @@ private: val = ReadVariable(variable, preds.front()); } else { // Break potential cycles with operandless phi - val = IR::Value{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + IR::Inst& phi_inst{*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + val = IR::Value{&phi_inst}; WriteVariable(variable, block, val); - val = AddPhiOperands(variable, val, block); + val = AddPhiOperands(variable, phi_inst, block); } WriteVariable(variable, block, val); return val; } - IR::Value AddPhiOperands(auto variable, const IR::Value& phi, IR::Block* block) { + IR::Value AddPhiOperands(auto variable, IR::Inst& phi, IR::Block* block) { for (IR::Block* const pred : block->ImmediatePredecessors()) { - phi.Inst()->AddPhiOperand(pred, ReadVariable(variable, pred)); + phi.AddPhiOperand(pred, ReadVariable(variable, pred)); } return TryRemoveTrivialPhi(phi, block, UndefOpcode(variable)); } - IR::Value TryRemoveTrivialPhi(const IR::Value& phi, IR::Block* block, IR::Opcode undef_opcode) { + IR::Value TryRemoveTrivialPhi(IR::Inst& phi, IR::Block* block, IR::Opcode undef_opcode) { IR::Value same; - for (const auto& pair : phi.Inst()->PhiOperands()) { - const IR::Value& op{pair.second}; - if (op == same || op == phi) { + const size_t num_args{phi.NumArgs()}; + for (size_t arg_index = 0; arg_index < num_args; ++arg_index) { + const IR::Value& op{phi.Arg(arg_index)}; + if (op == same || op == IR::Value{&phi}) { // Unique value or self-reference continue; } if (!same.IsEmpty()) { // The phi merges at least two values: not trivial - return phi; + return IR::Value{&phi}; } same = op; } @@ -139,7 +141,7 @@ private: same = IR::Value{&*block->PrependNewInst(first_not_phi, undef_opcode)}; } // Reroute all uses of phi to same and remove phi - phi.Inst()->ReplaceUsesWith(same); + phi.ReplaceUsesWith(same); // TODO: Try to recursively remove all phi users, which might have become trivial return same; } -- cgit v1.2.3 From 9170200a11715d131645d1ffb92e86e6ef0d7e88 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Thu, 11 Feb 2021 16:39:06 -0300 Subject: shader: Initial implementation of an AST --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 24 ++++++++++++++++++++--- 1 file changed, 21 insertions(+), 3 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') 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 {}; struct CarryFlagTag : FlagTag {}; struct OverflowFlagTag : FlagTag {}; +struct GotoVariable : FlagTag { + GotoVariable() = default; + explicit GotoVariable(u32 index_) : index{index_} {} + + u32 index; +}; + struct DefTable { [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { return regs[IR::RegIndex(variable)]; @@ -43,6 +50,10 @@ struct DefTable { return preds[IR::PredIndex(variable)]; } + [[nodiscard]] ValueMap& operator[](GotoVariable goto_variable) { + return goto_vars[goto_variable.index]; + } + [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept { return zero_flag; } @@ -61,6 +72,7 @@ struct DefTable { std::array regs; std::array preds; + boost::container::flat_map goto_vars; ValueMap zero_flag; ValueMap sign_flag; ValueMap carry_flag; @@ -68,15 +80,15 @@ struct DefTable { }; IR::Opcode UndefOpcode(IR::Reg) noexcept { - return IR::Opcode::Undef32; + return IR::Opcode::UndefU32; } IR::Opcode UndefOpcode(IR::Pred) noexcept { - return IR::Opcode::Undef1; + return IR::Opcode::UndefU1; } IR::Opcode UndefOpcode(const FlagTag&) noexcept { - return IR::Opcode::Undef1; + return IR::Opcode::UndefU1; } [[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { @@ -165,6 +177,9 @@ void SsaRewritePass(IR::Function& function) { pass.WriteVariable(pred, block, inst.Arg(1)); } break; + case IR::Opcode::SetGotoVariable: + pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); + break; case IR::Opcode::SetZFlag: pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); break; @@ -187,6 +202,9 @@ void SsaRewritePass(IR::Function& function) { inst.ReplaceUsesWith(pass.ReadVariable(pred, block)); } break; + case IR::Opcode::GetGotoVariable: + inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); + break; case IR::Opcode::GetZFlag: inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); break; -- cgit v1.2.3 From 8af9297f0972d0aaa8306369c5d04926b886a89e Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Sun, 14 Feb 2021 01:24:32 -0300 Subject: shader: Misc fixes --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 113 +++++++++++----------- 1 file changed, 59 insertions(+), 54 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 8ca996e93..7eaf719c4 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -113,6 +113,7 @@ private: IR::Value ReadVariableRecursive(auto variable, IR::Block* block) { IR::Value val; if (const std::span preds{block->ImmediatePredecessors()}; preds.size() == 1) { + // Optimize the common case of one predecessor: no phi needed val = ReadVariable(variable, preds.front()); } else { // Break potential cycles with operandless phi @@ -160,66 +161,70 @@ private: DefTable current_def; }; + +void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { + switch (inst.Opcode()) { + case IR::Opcode::SetRegister: + if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { + pass.WriteVariable(reg, block, inst.Arg(1)); + } + break; + case IR::Opcode::SetPred: + if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { + pass.WriteVariable(pred, block, inst.Arg(1)); + } + break; + case IR::Opcode::SetGotoVariable: + pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); + break; + case IR::Opcode::SetZFlag: + pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetSFlag: + pass.WriteVariable(SignFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetCFlag: + pass.WriteVariable(CarryFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetOFlag: + pass.WriteVariable(OverflowFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::GetRegister: + if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { + inst.ReplaceUsesWith(pass.ReadVariable(reg, block)); + } + break; + case IR::Opcode::GetPred: + if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { + inst.ReplaceUsesWith(pass.ReadVariable(pred, block)); + } + break; + case IR::Opcode::GetGotoVariable: + inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); + break; + case IR::Opcode::GetZFlag: + inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); + break; + case IR::Opcode::GetSFlag: + inst.ReplaceUsesWith(pass.ReadVariable(SignFlagTag{}, block)); + break; + case IR::Opcode::GetCFlag: + inst.ReplaceUsesWith(pass.ReadVariable(CarryFlagTag{}, block)); + break; + case IR::Opcode::GetOFlag: + inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); + break; + default: + break; + } +} } // Anonymous namespace void SsaRewritePass(IR::Function& function) { Pass pass; for (IR::Block* const block : function.blocks) { for (IR::Inst& inst : block->Instructions()) { - switch (inst.Opcode()) { - case IR::Opcode::SetRegister: - if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { - pass.WriteVariable(reg, block, inst.Arg(1)); - } - break; - case IR::Opcode::SetPred: - if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { - pass.WriteVariable(pred, block, inst.Arg(1)); - } - break; - case IR::Opcode::SetGotoVariable: - pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); - break; - case IR::Opcode::SetZFlag: - pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetSFlag: - pass.WriteVariable(SignFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetCFlag: - pass.WriteVariable(CarryFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetOFlag: - pass.WriteVariable(OverflowFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::GetRegister: - if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { - inst.ReplaceUsesWith(pass.ReadVariable(reg, block)); - } - break; - case IR::Opcode::GetPred: - if (const IR::Pred pred{inst.Arg(0).Pred()}; pred != IR::Pred::PT) { - inst.ReplaceUsesWith(pass.ReadVariable(pred, block)); - } - break; - case IR::Opcode::GetGotoVariable: - inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); - break; - case IR::Opcode::GetZFlag: - inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); - break; - case IR::Opcode::GetSFlag: - inst.ReplaceUsesWith(pass.ReadVariable(SignFlagTag{}, block)); - break; - case IR::Opcode::GetCFlag: - inst.ReplaceUsesWith(pass.ReadVariable(CarryFlagTag{}, block)); - break; - case IR::Opcode::GetOFlag: - inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); - break; - default: - break; - } + VisitInst(pass, block, inst); } } } -- cgit v1.2.3 From cbfb7d182a4e90e4e263696d1fca35e47d3eabb4 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Sun, 14 Feb 2021 20:15:42 -0300 Subject: shader: Support SSA loops on IR --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 62 ++++++++++++++++++----- 1 file changed, 49 insertions(+), 13 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 7eaf719c4..13f9c914a 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -14,7 +14,13 @@ // https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6 // +#include +#include +#include +#include + #include +#include #include "shader_recompiler/frontend/ir/basic_block.h" #include "shader_recompiler/frontend/ir/function.h" @@ -26,9 +32,9 @@ namespace Shader::Optimization { namespace { -using ValueMap = boost::container::flat_map>; - -struct FlagTag {}; +struct FlagTag { + auto operator<=>(const FlagTag&) const noexcept = default; +}; struct ZeroFlagTag : FlagTag {}; struct SignFlagTag : FlagTag {}; struct CarryFlagTag : FlagTag {}; @@ -38,9 +44,15 @@ struct GotoVariable : FlagTag { GotoVariable() = default; explicit GotoVariable(u32 index_) : index{index_} {} + auto operator<=>(const GotoVariable&) const noexcept = default; + u32 index; }; +using Variant = std::variant; +using ValueMap = boost::container::flat_map>; + struct DefTable { [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { return regs[IR::RegIndex(variable)]; @@ -102,19 +114,35 @@ public: } IR::Value ReadVariable(auto variable, IR::Block* block) { - auto& def{current_def[variable]}; + const ValueMap& def{current_def[variable]}; if (const auto it{def.find(block)}; it != def.end()) { return it->second; } return ReadVariableRecursive(variable, block); } + void SealBlock(IR::Block* block) { + const auto it{incomplete_phis.find(block)}; + if (it != incomplete_phis.end()) { + for (auto& [variant, phi] : it->second) { + std::visit([&](auto& variable) { AddPhiOperands(variable, *phi, block); }, variant); + } + } + sealed_blocks.insert(block); + } + private: IR::Value ReadVariableRecursive(auto variable, IR::Block* block) { IR::Value val; - if (const std::span preds{block->ImmediatePredecessors()}; preds.size() == 1) { + if (!sealed_blocks.contains(block)) { + // Incomplete CFG + IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + incomplete_phis[block].insert_or_assign(variable, phi); + val = IR::Value{&*phi}; + } else if (const std::span imm_preds{block->ImmediatePredecessors()}; + imm_preds.size() == 1) { // Optimize the common case of one predecessor: no phi needed - val = ReadVariable(variable, preds.front()); + val = ReadVariable(variable, imm_preds.front()); } else { // Break potential cycles with operandless phi IR::Inst& phi_inst{*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; @@ -127,8 +155,8 @@ private: } IR::Value AddPhiOperands(auto variable, IR::Inst& phi, IR::Block* block) { - for (IR::Block* const pred : block->ImmediatePredecessors()) { - phi.AddPhiOperand(pred, ReadVariable(variable, pred)); + for (IR::Block* const imm_pred : block->ImmediatePredecessors()) { + phi.AddPhiOperand(imm_pred, ReadVariable(variable, imm_pred)); } return TryRemoveTrivialPhi(phi, block, UndefOpcode(variable)); } @@ -159,6 +187,9 @@ private: return same; } + boost::container::flat_set sealed_blocks; + boost::container::flat_map> + incomplete_phis; DefTable current_def; }; @@ -218,14 +249,19 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { break; } } + +void VisitBlock(Pass& pass, IR::Block* block) { + for (IR::Inst& inst : block->Instructions()) { + VisitInst(pass, block, inst); + } + pass.SealBlock(block); +} } // Anonymous namespace -void SsaRewritePass(IR::Function& function) { +void SsaRewritePass(std::span post_order_blocks) { Pass pass; - for (IR::Block* const block : function.blocks) { - for (IR::Inst& inst : block->Instructions()) { - VisitInst(pass, block, inst); - } + for (IR::Block* const block : post_order_blocks | std::views::reverse) { + VisitBlock(pass, block); } } -- cgit v1.2.3 From 8810c88b7e3de2766bf47e07e941fb2c58c6b4b0 Mon Sep 17 00:00:00 2001 From: ameerj <52414509+ameerj@users.noreply.github.com> Date: Wed, 24 Feb 2021 20:31:15 -0500 Subject: shader: Implement SEL --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 13f9c914a..19d35b1f8 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -109,11 +109,13 @@ IR::Opcode UndefOpcode(const FlagTag&) noexcept { class Pass { public: - void WriteVariable(auto variable, IR::Block* block, const IR::Value& value) { + template + void WriteVariable(Type variable, IR::Block* block, const IR::Value& value) { current_def[variable].insert_or_assign(block, value); } - IR::Value ReadVariable(auto variable, IR::Block* block) { + template + IR::Value ReadVariable(Type variable, IR::Block* block) { const ValueMap& def{current_def[variable]}; if (const auto it{def.find(block)}; it != def.end()) { return it->second; @@ -132,7 +134,8 @@ public: } private: - IR::Value ReadVariableRecursive(auto variable, IR::Block* block) { + template + IR::Value ReadVariableRecursive(Type variable, IR::Block* block) { IR::Value val; if (!sealed_blocks.contains(block)) { // Incomplete CFG @@ -154,7 +157,8 @@ private: return val; } - IR::Value AddPhiOperands(auto variable, IR::Inst& phi, IR::Block* block) { + template + IR::Value AddPhiOperands(Type variable, IR::Inst& phi, IR::Block* block) { for (IR::Block* const imm_pred : block->ImmediatePredecessors()) { phi.AddPhiOperand(imm_pred, ReadVariable(variable, imm_pred)); } -- cgit v1.2.3 From 71f96fa6366dc6dd306a953bca1b958fb32bc55a Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Sun, 14 Mar 2021 03:41:05 -0300 Subject: shader: Implement CAL inlining function calls --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 19d35b1f8..f89fd51c8 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -23,7 +23,6 @@ #include #include "shader_recompiler/frontend/ir/basic_block.h" -#include "shader_recompiler/frontend/ir/function.h" #include "shader_recompiler/frontend/ir/microinstruction.h" #include "shader_recompiler/frontend/ir/opcodes.h" #include "shader_recompiler/frontend/ir/pred.h" @@ -262,9 +261,9 @@ void VisitBlock(Pass& pass, IR::Block* block) { } } // Anonymous namespace -void SsaRewritePass(std::span post_order_blocks) { +void SsaRewritePass(IR::Program& program) { Pass pass; - for (IR::Block* const block : post_order_blocks | std::views::reverse) { + for (IR::Block* const block : program.post_order_blocks | std::views::reverse) { VisitBlock(pass, block); } } -- cgit v1.2.3 From 32b6c63485626f10b3bc8efb0239064cc781115e Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Wed, 17 Mar 2021 01:33:25 -0300 Subject: shader: Reorder phi nodes when redefined as undefined opcodes --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index f89fd51c8..d09bcec36 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -181,8 +181,16 @@ private: } if (same.IsEmpty()) { // The phi is unreachable or in the start block - const auto first_not_phi{std::ranges::find_if_not(block->Instructions(), IsPhi)}; + // First remove the phi node from the block, it will be reinserted + IR::Block::InstructionList& list{block->Instructions()}; + list.erase(IR::Block::InstructionList::s_iterator_to(phi)); + + // Insert an undef instruction after all phi nodes (to keep phi instructions on top) + const auto first_not_phi{std::ranges::find_if_not(list, IsPhi)}; same = IR::Value{&*block->PrependNewInst(first_not_phi, undef_opcode)}; + + // Insert the phi node after the undef opcode, this will be replaced with an identity + list.insert(first_not_phi, phi); } // Reroute all uses of phi to same and remove phi phi.ReplaceUsesWith(same); -- cgit v1.2.3 From 260743f371236f7c57b01334b1c3474b15a47c39 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 19 Mar 2021 19:28:31 -0300 Subject: shader: Add partial rasterizer integration --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index d09bcec36..bab7ca186 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -169,7 +169,7 @@ private: const size_t num_args{phi.NumArgs()}; for (size_t arg_index = 0; arg_index < num_args; ++arg_index) { const IR::Value& op{phi.Arg(arg_index)}; - if (op == same || op == IR::Value{&phi}) { + if (op.Resolve() == same.Resolve() || op == IR::Value{&phi}) { // Unique value or self-reference continue; } -- cgit v1.2.3 From 34aba9627a8fad20b3b173180e2f3d679dd32293 Mon Sep 17 00:00:00 2001 From: FernandoS27 Date: Sat, 27 Mar 2021 22:30:24 +0100 Subject: shader: Implement BRX --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 21 ++++++++++++++++++++- 1 file changed, 20 insertions(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index bab7ca186..259233746 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -48,8 +48,12 @@ struct GotoVariable : FlagTag { u32 index; }; +struct IndirectBranchVariable { + auto operator<=>(const IndirectBranchVariable&) const noexcept = default; +}; + using Variant = std::variant; + OverflowFlagTag, GotoVariable, IndirectBranchVariable>; using ValueMap = boost::container::flat_map>; struct DefTable { @@ -65,6 +69,10 @@ struct DefTable { return goto_vars[goto_variable.index]; } + [[nodiscard]] ValueMap& operator[](IndirectBranchVariable) { + return indirect_branch_var; + } + [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept { return zero_flag; } @@ -84,6 +92,7 @@ struct DefTable { std::array regs; std::array preds; boost::container::flat_map goto_vars; + ValueMap indirect_branch_var; ValueMap zero_flag; ValueMap sign_flag; ValueMap carry_flag; @@ -102,6 +111,10 @@ IR::Opcode UndefOpcode(const FlagTag&) noexcept { return IR::Opcode::UndefU1; } +IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { + return IR::Opcode::UndefU32; +} + [[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { return inst.Opcode() == IR::Opcode::Phi; } @@ -219,6 +232,9 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::SetGotoVariable: pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); break; + case IR::Opcode::SetIndirectBranchVariable: + pass.WriteVariable(IndirectBranchVariable{}, block, inst.Arg(0)); + break; case IR::Opcode::SetZFlag: pass.WriteVariable(ZeroFlagTag{}, block, inst.Arg(0)); break; @@ -244,6 +260,9 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetGotoVariable: inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); break; + case IR::Opcode::GetIndirectBranchVariable: + inst.ReplaceUsesWith(pass.ReadVariable(IndirectBranchVariable{}, block)); + break; case IR::Opcode::GetZFlag: inst.ReplaceUsesWith(pass.ReadVariable(ZeroFlagTag{}, block)); break; -- cgit v1.2.3 From ecb30c907266921818d5b6b03e341028fa2ea082 Mon Sep 17 00:00:00 2001 From: FernandoS27 Date: Thu, 1 Apr 2021 22:20:57 +0200 Subject: shader: Improve VOTE.VTG stub --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 51 ++++++++++++++++++++++- 1 file changed, 50 insertions(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 259233746..7dab33034 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -38,6 +38,10 @@ struct ZeroFlagTag : FlagTag {}; struct SignFlagTag : FlagTag {}; struct CarryFlagTag : FlagTag {}; struct OverflowFlagTag : FlagTag {}; +struct FCSMFlagTag : FlagTag {}; +struct TAFlagTag : FlagTag {}; +struct TRFlagTag : FlagTag {}; +struct MXFlagTag : FlagTag {}; struct GotoVariable : FlagTag { GotoVariable() = default; @@ -53,7 +57,8 @@ struct IndirectBranchVariable { }; using Variant = std::variant; + OverflowFlagTag, FCSMFlagTag, TAFlagTag, TRFlagTag, MXFlagTag, + GotoVariable, IndirectBranchVariable>; using ValueMap = boost::container::flat_map>; struct DefTable { @@ -89,6 +94,22 @@ struct DefTable { return overflow_flag; } + [[nodiscard]] ValueMap& operator[](FCSMFlagTag) noexcept { + return fcsm_flag; + } + + [[nodiscard]] ValueMap& operator[](TAFlagTag) noexcept { + return ta_flag; + } + + [[nodiscard]] ValueMap& operator[](TRFlagTag) noexcept { + return tr_flag; + } + + [[nodiscard]] ValueMap& operator[](MXFlagTag) noexcept { + return mr_flag; + } + std::array regs; std::array preds; boost::container::flat_map goto_vars; @@ -97,6 +118,10 @@ struct DefTable { ValueMap sign_flag; ValueMap carry_flag; ValueMap overflow_flag; + ValueMap fcsm_flag; + ValueMap ta_flag; + ValueMap tr_flag; + ValueMap mr_flag; }; IR::Opcode UndefOpcode(IR::Reg) noexcept { @@ -247,6 +272,18 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::SetOFlag: pass.WriteVariable(OverflowFlagTag{}, block, inst.Arg(0)); break; + case IR::Opcode::SetFCSMFlag: + pass.WriteVariable(FCSMFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetTAFlag: + pass.WriteVariable(TAFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetTRFlag: + pass.WriteVariable(TRFlagTag{}, block, inst.Arg(0)); + break; + case IR::Opcode::SetMXFlag: + pass.WriteVariable(MXFlagTag{}, block, inst.Arg(0)); + break; case IR::Opcode::GetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { inst.ReplaceUsesWith(pass.ReadVariable(reg, block)); @@ -275,6 +312,18 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetOFlag: inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); break; + case IR::Opcode::GetFCSMFlag: + inst.ReplaceUsesWith(pass.ReadVariable(FCSMFlagTag{}, block)); + break; + case IR::Opcode::GetTAFlag: + inst.ReplaceUsesWith(pass.ReadVariable(TAFlagTag{}, block)); + break; + case IR::Opcode::GetTRFlag: + inst.ReplaceUsesWith(pass.ReadVariable(TRFlagTag{}, block)); + break; + case IR::Opcode::GetMXFlag: + inst.ReplaceUsesWith(pass.ReadVariable(MXFlagTag{}, block)); + break; default: break; } -- cgit v1.2.3 From baec84247fe815199595d9e8077b71f3b5c8317e Mon Sep 17 00:00:00 2001 From: FernandoS27 Date: Sat, 3 Apr 2021 01:48:39 +0200 Subject: shader: Address Feedback --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 50 +---------------------- 1 file changed, 1 insertion(+), 49 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 7dab33034..72d4abb77 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -38,10 +38,6 @@ struct ZeroFlagTag : FlagTag {}; struct SignFlagTag : FlagTag {}; struct CarryFlagTag : FlagTag {}; struct OverflowFlagTag : FlagTag {}; -struct FCSMFlagTag : FlagTag {}; -struct TAFlagTag : FlagTag {}; -struct TRFlagTag : FlagTag {}; -struct MXFlagTag : FlagTag {}; struct GotoVariable : FlagTag { GotoVariable() = default; @@ -57,8 +53,7 @@ struct IndirectBranchVariable { }; using Variant = std::variant; + OverflowFlagTag, GotoVariable, IndirectBranchVariable>; using ValueMap = boost::container::flat_map>; struct DefTable { @@ -94,22 +89,6 @@ struct DefTable { return overflow_flag; } - [[nodiscard]] ValueMap& operator[](FCSMFlagTag) noexcept { - return fcsm_flag; - } - - [[nodiscard]] ValueMap& operator[](TAFlagTag) noexcept { - return ta_flag; - } - - [[nodiscard]] ValueMap& operator[](TRFlagTag) noexcept { - return tr_flag; - } - - [[nodiscard]] ValueMap& operator[](MXFlagTag) noexcept { - return mr_flag; - } - std::array regs; std::array preds; boost::container::flat_map goto_vars; @@ -118,10 +97,6 @@ struct DefTable { ValueMap sign_flag; ValueMap carry_flag; ValueMap overflow_flag; - ValueMap fcsm_flag; - ValueMap ta_flag; - ValueMap tr_flag; - ValueMap mr_flag; }; IR::Opcode UndefOpcode(IR::Reg) noexcept { @@ -272,18 +247,6 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::SetOFlag: pass.WriteVariable(OverflowFlagTag{}, block, inst.Arg(0)); break; - case IR::Opcode::SetFCSMFlag: - pass.WriteVariable(FCSMFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetTAFlag: - pass.WriteVariable(TAFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetTRFlag: - pass.WriteVariable(TRFlagTag{}, block, inst.Arg(0)); - break; - case IR::Opcode::SetMXFlag: - pass.WriteVariable(MXFlagTag{}, block, inst.Arg(0)); - break; case IR::Opcode::GetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { inst.ReplaceUsesWith(pass.ReadVariable(reg, block)); @@ -312,17 +275,6 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetOFlag: inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); break; - case IR::Opcode::GetFCSMFlag: - inst.ReplaceUsesWith(pass.ReadVariable(FCSMFlagTag{}, block)); - break; - case IR::Opcode::GetTAFlag: - inst.ReplaceUsesWith(pass.ReadVariable(TAFlagTag{}, block)); - break; - case IR::Opcode::GetTRFlag: - inst.ReplaceUsesWith(pass.ReadVariable(TRFlagTag{}, block)); - break; - case IR::Opcode::GetMXFlag: - inst.ReplaceUsesWith(pass.ReadVariable(MXFlagTag{}, block)); break; default: break; -- cgit v1.2.3 From ed6a1b1a3def4b8ed8c8fd1a7774a0a14edefc70 Mon Sep 17 00:00:00 2001 From: FernandoS27 Date: Sat, 3 Apr 2021 02:34:07 +0200 Subject: shader: Address feedback --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 1 - 1 file changed, 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 72d4abb77..259233746 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -275,7 +275,6 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetOFlag: inst.ReplaceUsesWith(pass.ReadVariable(OverflowFlagTag{}, block)); break; - break; default: break; } -- cgit v1.2.3 From 417fb5d385daa0fb40329709e6b4a53937580989 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Mon, 5 Apr 2021 19:10:55 -0300 Subject: shader: Move recursive SSA rewrite to the heap --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 118 ++++++++++++++++------ 1 file changed, 89 insertions(+), 29 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 259233746..ca36253d1 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -119,6 +119,26 @@ IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { return inst.Opcode() == IR::Opcode::Phi; } +enum class Status { + Start, + SetValue, + PreparePhiArgument, + PushPhiArgument, +}; + +template +struct ReadState { + ReadState(IR::Block* block_) : block{block_} {} + ReadState() = default; + + IR::Block* block{}; + IR::Value result{}; + IR::Inst* phi{}; + IR::Block* const* pred_it{}; + IR::Block* const* pred_end{}; + Status pc{Status::Start}; +}; + class Pass { public: template @@ -127,12 +147,75 @@ public: } template - IR::Value ReadVariable(Type variable, IR::Block* block) { - const ValueMap& def{current_def[variable]}; - if (const auto it{def.find(block)}; it != def.end()) { - return it->second; - } - return ReadVariableRecursive(variable, block); + IR::Value ReadVariable(Type variable, IR::Block* root_block) { + boost::container::small_vector, 64> stack{ + ReadState(nullptr), + ReadState(root_block), + }; + const auto prepare_phi_operand{[&] { + if (stack.back().pred_it == stack.back().pred_end) { + IR::Inst* const phi{stack.back().phi}; + IR::Block* const block{stack.back().block}; + const IR::Value result{TryRemoveTrivialPhi(*phi, block, UndefOpcode(variable))}; + stack.pop_back(); + stack.back().result = result; + WriteVariable(variable, block, result); + } else { + IR::Block* const imm_pred{*stack.back().pred_it}; + stack.back().pc = Status::PushPhiArgument; + stack.emplace_back(imm_pred); + } + }}; + do { + IR::Block* const block{stack.back().block}; + switch (stack.back().pc) { + case Status::Start: { + const ValueMap& def{current_def[variable]}; + if (const auto it{def.find(block)}; it != def.end()) { + stack.back().result = it->second; + } else if (!sealed_blocks.contains(block)) { + // Incomplete CFG + IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + incomplete_phis[block].insert_or_assign(variable, phi); + stack.back().result = IR::Value{&*phi}; + } else if (const std::span imm_preds{block->ImmediatePredecessors()}; + imm_preds.size() == 1) { + // Optimize the common case of one predecessor: no phi needed + stack.back().pc = Status::SetValue; + stack.emplace_back(imm_preds.front()); + break; + } else { + // Break potential cycles with operandless phi + IR::Inst* const phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + WriteVariable(variable, block, IR::Value{phi}); + + stack.back().phi = phi; + stack.back().pred_it = imm_preds.data(); + stack.back().pred_end = imm_preds.data() + imm_preds.size(); + prepare_phi_operand(); + break; + } + } + [[fallthrough]]; + case Status::SetValue: { + const IR::Value result{stack.back().result}; + WriteVariable(variable, block, result); + stack.pop_back(); + stack.back().result = result; + break; + } + case Status::PushPhiArgument: { + IR::Inst* const phi{stack.back().phi}; + phi->AddPhiOperand(*stack.back().pred_it, stack.back().result); + ++stack.back().pred_it; + } + [[fallthrough]]; + case Status::PreparePhiArgument: + prepare_phi_operand(); + break; + } + } while (stack.size() > 1); + return stack.back().result; } void SealBlock(IR::Block* block) { @@ -146,29 +229,6 @@ public: } private: - template - IR::Value ReadVariableRecursive(Type variable, IR::Block* block) { - IR::Value val; - if (!sealed_blocks.contains(block)) { - // Incomplete CFG - IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; - incomplete_phis[block].insert_or_assign(variable, phi); - val = IR::Value{&*phi}; - } else if (const std::span imm_preds{block->ImmediatePredecessors()}; - imm_preds.size() == 1) { - // Optimize the common case of one predecessor: no phi needed - val = ReadVariable(variable, imm_preds.front()); - } else { - // Break potential cycles with operandless phi - IR::Inst& phi_inst{*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; - val = IR::Value{&phi_inst}; - WriteVariable(variable, block, val); - val = AddPhiOperands(variable, phi_inst, block); - } - WriteVariable(variable, block, val); - return val; - } - template IR::Value AddPhiOperands(Type variable, IR::Inst& phi, IR::Block* block) { for (IR::Block* const imm_pred : block->ImmediatePredecessors()) { -- cgit v1.2.3 From 0bb85f6a753c769266c95c4ba146b25b9eaaaffd Mon Sep 17 00:00:00 2001 From: lat9nq <22451773+lat9nq@users.noreply.github.com> Date: Mon, 5 Apr 2021 22:25:22 -0400 Subject: shader_recompiler,video_core: Cleanup some GCC and Clang errors Mostly fixing unused *, implicit conversion, braced scalar init, fpermissive, and some others. Some Clang errors likely remain in video_core, and std::ranges is still a pertinent issue in shader_recompiler shader_recompiler: cmake: Force bracket depth to 1024 on Clang Increases the maximum fold expression depth thread_worker: Include condition_variable Don't use list initializers in control flow Co-authored-by: ReinUsesLisp --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index ca36253d1..346fcc377 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -116,7 +116,7 @@ IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { } [[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { - return inst.Opcode() == IR::Opcode::Phi; + return inst.GetOpcode() == IR::Opcode::Phi; } enum class Status { @@ -278,7 +278,7 @@ private: }; void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { - switch (inst.Opcode()) { + switch (inst.GetOpcode()) { case IR::Opcode::SetRegister: if (const IR::Reg reg{inst.Arg(0).Reg()}; reg != IR::Reg::RZ) { pass.WriteVariable(reg, block, inst.Arg(1)); -- cgit v1.2.3 From 50f8007172ce143a632270510f96093c82018952 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Sat, 17 Apr 2021 16:40:35 -0300 Subject: shader: Fix Phi node types --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 4 ++++ 1 file changed, 4 insertions(+) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 346fcc377..ddd679e39 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -176,6 +176,8 @@ public: } else if (!sealed_blocks.contains(block)) { // Incomplete CFG IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + phi->SetFlags(IR::TypeOf(UndefOpcode(variable))); + incomplete_phis[block].insert_or_assign(variable, phi); stack.back().result = IR::Value{&*phi}; } else if (const std::span imm_preds{block->ImmediatePredecessors()}; @@ -187,6 +189,8 @@ public: } else { // Break potential cycles with operandless phi IR::Inst* const phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; + phi->SetFlags(IR::TypeOf(UndefOpcode(variable))); + WriteVariable(variable, block, IR::Value{phi}); stack.back().phi = phi; -- cgit v1.2.3 From 420982864634a5e52cea42c43f8623f75483fbcc Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Wed, 21 Apr 2021 00:27:55 -0300 Subject: shader: Intrusively store register values in block for SSA pass --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 64 +++++++++++++++-------- 1 file changed, 43 insertions(+), 21 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index ddd679e39..bb1a90004 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -57,39 +57,62 @@ using Variant = std::variant>; struct DefTable { - [[nodiscard]] ValueMap& operator[](IR::Reg variable) noexcept { - return regs[IR::RegIndex(variable)]; + const IR::Value& Def(IR::Block* block, IR::Reg variable) noexcept { + return block->SsaRegValue(variable); + } + void SetDef(IR::Block* block, IR::Reg variable, const IR::Value& value) noexcept { + block->SetSsaRegValue(variable, value); } - [[nodiscard]] ValueMap& operator[](IR::Pred variable) noexcept { - return preds[IR::PredIndex(variable)]; + const IR::Value& Def(IR::Block* block, IR::Pred variable) noexcept { + return preds[IR::PredIndex(variable)][block]; + } + void SetDef(IR::Block* block, IR::Pred variable, const IR::Value& value) noexcept { + preds[IR::PredIndex(variable)].insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](GotoVariable goto_variable) { - return goto_vars[goto_variable.index]; + const IR::Value& Def(IR::Block* block, GotoVariable variable) noexcept { + return goto_vars[variable.index][block]; + } + void SetDef(IR::Block* block, GotoVariable variable, const IR::Value& value) noexcept { + goto_vars[variable.index].insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](IndirectBranchVariable) { - return indirect_branch_var; + const IR::Value& Def(IR::Block* block, IndirectBranchVariable) noexcept { + return indirect_branch_var[block]; + } + void SetDef(IR::Block* block, IndirectBranchVariable, const IR::Value& value) noexcept { + indirect_branch_var.insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](ZeroFlagTag) noexcept { - return zero_flag; + const IR::Value& Def(IR::Block* block, ZeroFlagTag) noexcept { + return zero_flag[block]; + } + void SetDef(IR::Block* block, ZeroFlagTag, const IR::Value& value) noexcept { + zero_flag.insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](SignFlagTag) noexcept { - return sign_flag; + const IR::Value& Def(IR::Block* block, SignFlagTag) noexcept { + return sign_flag[block]; + } + void SetDef(IR::Block* block, SignFlagTag, const IR::Value& value) noexcept { + sign_flag.insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](CarryFlagTag) noexcept { - return carry_flag; + const IR::Value& Def(IR::Block* block, CarryFlagTag) noexcept { + return carry_flag[block]; + } + void SetDef(IR::Block* block, CarryFlagTag, const IR::Value& value) noexcept { + carry_flag.insert_or_assign(block, value); } - [[nodiscard]] ValueMap& operator[](OverflowFlagTag) noexcept { - return overflow_flag; + const IR::Value& Def(IR::Block* block, OverflowFlagTag) noexcept { + return overflow_flag[block]; + } + void SetDef(IR::Block* block, OverflowFlagTag, const IR::Value& value) noexcept { + overflow_flag.insert_or_assign(block, value); } - std::array regs; std::array preds; boost::container::flat_map goto_vars; ValueMap indirect_branch_var; @@ -143,7 +166,7 @@ class Pass { public: template void WriteVariable(Type variable, IR::Block* block, const IR::Value& value) { - current_def[variable].insert_or_assign(block, value); + current_def.SetDef(block, variable, value); } template @@ -170,9 +193,8 @@ public: IR::Block* const block{stack.back().block}; switch (stack.back().pc) { case Status::Start: { - const ValueMap& def{current_def[variable]}; - if (const auto it{def.find(block)}; it != def.end()) { - stack.back().result = it->second; + if (const IR::Value& def = current_def.Def(block, variable); !def.IsEmpty()) { + stack.back().result = def; } else if (!sealed_blocks.contains(block)) { // Incomplete CFG IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; -- cgit v1.2.3 From 050e81500c002f304d581f28700de549b828a2bc Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Wed, 21 Apr 2021 00:35:47 -0300 Subject: shader: Move microinstruction header to the value header --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index bb1a90004..fe86a164b 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -23,10 +23,10 @@ #include #include "shader_recompiler/frontend/ir/basic_block.h" -#include "shader_recompiler/frontend/ir/microinstruction.h" #include "shader_recompiler/frontend/ir/opcodes.h" #include "shader_recompiler/frontend/ir/pred.h" #include "shader_recompiler/frontend/ir/reg.h" +#include "shader_recompiler/frontend/ir/value.h" #include "shader_recompiler/ir_opt/passes.h" namespace Shader::Optimization { -- cgit v1.2.3 From 23182fa59c45a88b706022c1373e307ba4636cca Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Wed, 21 Apr 2021 04:58:23 -0300 Subject: shader: Intrusively store in a block if it's sealed or not --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index fe86a164b..3bab742e7 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -195,7 +195,7 @@ public: case Status::Start: { if (const IR::Value& def = current_def.Def(block, variable); !def.IsEmpty()) { stack.back().result = def; - } else if (!sealed_blocks.contains(block)) { + } else if (!block->IsSsaSealed()) { // Incomplete CFG IR::Inst* phi{&*block->PrependNewInst(block->begin(), IR::Opcode::Phi)}; phi->SetFlags(IR::TypeOf(UndefOpcode(variable))); @@ -251,7 +251,7 @@ public: std::visit([&](auto& variable) { AddPhiOperands(variable, *phi, block); }, variant); } } - sealed_blocks.insert(block); + block->SsaSeal(); } private: @@ -297,7 +297,6 @@ private: return same; } - boost::container::flat_set sealed_blocks; boost::container::flat_map> incomplete_phis; DefTable current_def; -- cgit v1.2.3 From 25949b864c40405946d434ecc85d6c167f323a24 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Thu, 22 Apr 2021 18:33:49 -0300 Subject: shader: Fix forward referencing identity instructions when inserting phi --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 24 ++++++++++++----------- 1 file changed, 13 insertions(+), 11 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 3bab742e7..a8064a5d0 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -278,20 +278,22 @@ private: } same = op; } + // Remove the phi node from the block, it will be reinserted + IR::Block::InstructionList& list{block->Instructions()}; + list.erase(IR::Block::InstructionList::s_iterator_to(phi)); + + // Find the first non-phi instruction and use it as an insertion point + IR::Block::iterator reinsert_point{std::ranges::find_if_not(list, IsPhi)}; if (same.IsEmpty()) { // The phi is unreachable or in the start block - // First remove the phi node from the block, it will be reinserted - IR::Block::InstructionList& list{block->Instructions()}; - list.erase(IR::Block::InstructionList::s_iterator_to(phi)); - - // Insert an undef instruction after all phi nodes (to keep phi instructions on top) - const auto first_not_phi{std::ranges::find_if_not(list, IsPhi)}; - same = IR::Value{&*block->PrependNewInst(first_not_phi, undef_opcode)}; - - // Insert the phi node after the undef opcode, this will be replaced with an identity - list.insert(first_not_phi, phi); + // Insert an undefined instruction and make it the phi node replacement + // The "phi" node reinsertion point is specified after this instruction + reinsert_point = block->PrependNewInst(reinsert_point, undef_opcode); + same = IR::Value{&*reinsert_point}; + ++reinsert_point; } - // Reroute all uses of phi to same and remove phi + // Reinsert the phi node and reroute all its uses to the "same" value + list.insert(reinsert_point, phi); phi.ReplaceUsesWith(same); // TODO: Try to recursively remove all phi users, which might have become trivial return same; -- cgit v1.2.3 From d54d7de40e7295827b0e4e4026441b53d3fc9569 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 14 May 2021 00:40:54 -0300 Subject: glasm: Rework control flow introducing a syntax list This commit regresses VertexA shaders, their transformation pass has to be adapted to the new control flow. --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index a8064a5d0..26eb3a3ab 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -202,7 +202,7 @@ public: incomplete_phis[block].insert_or_assign(variable, phi); stack.back().result = IR::Value{&*phi}; - } else if (const std::span imm_preds{block->ImmediatePredecessors()}; + } else if (const std::span imm_preds = block->ImmPredecessors(); imm_preds.size() == 1) { // Optimize the common case of one predecessor: no phi needed stack.back().pc = Status::SetValue; @@ -257,7 +257,7 @@ public: private: template IR::Value AddPhiOperands(Type variable, IR::Inst& phi, IR::Block* block) { - for (IR::Block* const imm_pred : block->ImmediatePredecessors()) { + for (IR::Block* const imm_pred : block->ImmPredecessors()) { phi.AddPhiOperand(imm_pred, ReadVariable(variable, imm_pred)); } return TryRemoveTrivialPhi(phi, block, UndefOpcode(variable)); -- cgit v1.2.3 From bf5e48ffe4bd48ea681f2a01c8919c97125e88df Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Fri, 14 May 2021 04:48:46 -0300 Subject: glasm: Initial implementation of phi nodes on GLASM --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 6 +----- 1 file changed, 1 insertion(+), 5 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index 26eb3a3ab..e54499ba5 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -138,10 +138,6 @@ IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { return IR::Opcode::UndefU32; } -[[nodiscard]] bool IsPhi(const IR::Inst& inst) noexcept { - return inst.GetOpcode() == IR::Opcode::Phi; -} - enum class Status { Start, SetValue, @@ -283,7 +279,7 @@ private: list.erase(IR::Block::InstructionList::s_iterator_to(phi)); // Find the first non-phi instruction and use it as an insertion point - IR::Block::iterator reinsert_point{std::ranges::find_if_not(list, IsPhi)}; + IR::Block::iterator reinsert_point{std::ranges::find_if_not(list, IR::IsPhi)}; if (same.IsEmpty()) { // The phi is unreachable or in the start block // Insert an undefined instruction and make it the phi node replacement -- cgit v1.2.3 From 373f75d944473731408d7a72c967d5c4b37af5bb Mon Sep 17 00:00:00 2001 From: lat9nq <22451773+lat9nq@users.noreply.github.com> Date: Thu, 8 Jul 2021 17:22:31 -0400 Subject: shader: Add shader loop safety check settings Also add a setting for enable Nsight Aftermath. --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 66 ++++++++++++++++------- 1 file changed, 47 insertions(+), 19 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index e54499ba5..a4ba393ef 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -48,73 +48,91 @@ struct GotoVariable : FlagTag { u32 index; }; +struct LoopSafetyVariable { + LoopSafetyVariable() = default; + explicit LoopSafetyVariable(u32 index_) : index{index_} {} + + auto operator<=>(const LoopSafetyVariable&) const noexcept = default; + + u32 index; +}; + struct IndirectBranchVariable { auto operator<=>(const IndirectBranchVariable&) const noexcept = default; }; -using Variant = std::variant; -using ValueMap = boost::container::flat_map>; +using Variant = + std::variant; +using ValueMap = boost::container::flat_map; struct DefTable { - const IR::Value& Def(IR::Block* block, IR::Reg variable) noexcept { + const IR::Value& Def(IR::Block* block, IR::Reg variable) { return block->SsaRegValue(variable); } - void SetDef(IR::Block* block, IR::Reg variable, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, IR::Reg variable, const IR::Value& value) { block->SetSsaRegValue(variable, value); } - const IR::Value& Def(IR::Block* block, IR::Pred variable) noexcept { + const IR::Value& Def(IR::Block* block, IR::Pred variable) { return preds[IR::PredIndex(variable)][block]; } - void SetDef(IR::Block* block, IR::Pred variable, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, IR::Pred variable, const IR::Value& value) { preds[IR::PredIndex(variable)].insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, GotoVariable variable) noexcept { + const IR::Value& Def(IR::Block* block, GotoVariable variable) { return goto_vars[variable.index][block]; } - void SetDef(IR::Block* block, GotoVariable variable, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, GotoVariable variable, const IR::Value& value) { goto_vars[variable.index].insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, IndirectBranchVariable) noexcept { + const IR::Value& Def(IR::Block* block, LoopSafetyVariable variable) { + return loop_safety_vars[variable.index][block]; + } + void SetDef(IR::Block* block, LoopSafetyVariable variable, const IR::Value& value) { + loop_safety_vars[variable.index].insert_or_assign(block, value); + } + + const IR::Value& Def(IR::Block* block, IndirectBranchVariable) { return indirect_branch_var[block]; } - void SetDef(IR::Block* block, IndirectBranchVariable, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, IndirectBranchVariable, const IR::Value& value) { indirect_branch_var.insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, ZeroFlagTag) noexcept { + const IR::Value& Def(IR::Block* block, ZeroFlagTag) { return zero_flag[block]; } - void SetDef(IR::Block* block, ZeroFlagTag, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, ZeroFlagTag, const IR::Value& value) { zero_flag.insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, SignFlagTag) noexcept { + const IR::Value& Def(IR::Block* block, SignFlagTag) { return sign_flag[block]; } - void SetDef(IR::Block* block, SignFlagTag, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, SignFlagTag, const IR::Value& value) { sign_flag.insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, CarryFlagTag) noexcept { + const IR::Value& Def(IR::Block* block, CarryFlagTag) { return carry_flag[block]; } - void SetDef(IR::Block* block, CarryFlagTag, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, CarryFlagTag, const IR::Value& value) { carry_flag.insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, OverflowFlagTag) noexcept { + const IR::Value& Def(IR::Block* block, OverflowFlagTag) { return overflow_flag[block]; } - void SetDef(IR::Block* block, OverflowFlagTag, const IR::Value& value) noexcept { + void SetDef(IR::Block* block, OverflowFlagTag, const IR::Value& value) { overflow_flag.insert_or_assign(block, value); } std::array preds; boost::container::flat_map goto_vars; + boost::container::flat_map loop_safety_vars; ValueMap indirect_branch_var; ValueMap zero_flag; ValueMap sign_flag; @@ -134,6 +152,10 @@ IR::Opcode UndefOpcode(const FlagTag&) noexcept { return IR::Opcode::UndefU1; } +IR::Opcode UndefOpcode(const LoopSafetyVariable&) noexcept { + return IR::Opcode::UndefU32; +} + IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { return IR::Opcode::UndefU32; } @@ -315,6 +337,9 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::SetGotoVariable: pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); break; + case IR::Opcode::SetLoopSafetyVariable: + pass.WriteVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block, inst.Arg(0)); + break; case IR::Opcode::SetIndirectBranchVariable: pass.WriteVariable(IndirectBranchVariable{}, block, inst.Arg(0)); break; @@ -343,6 +368,9 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetGotoVariable: inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); break; + case IR::Opcode::GetLoopSafetyVariable: + inst.ReplaceUsesWith(pass.ReadVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block)); + break; case IR::Opcode::GetIndirectBranchVariable: inst.ReplaceUsesWith(pass.ReadVariable(IndirectBranchVariable{}, block)); break; -- cgit v1.2.3 From 7ac55c2a750f00b41582a86eba5a44dcd781ae98 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Tue, 15 Jun 2021 17:00:07 -0300 Subject: shader: Fix loop safety to SSA pass --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index a4ba393ef..fff25c4a2 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -338,7 +338,7 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); break; case IR::Opcode::SetLoopSafetyVariable: - pass.WriteVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block, inst.Arg(0)); + pass.WriteVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); break; case IR::Opcode::SetIndirectBranchVariable: pass.WriteVariable(IndirectBranchVariable{}, block, inst.Arg(0)); -- cgit v1.2.3 From 808ef97a086e7cc58a3ceded1de516ad6a6be5d3 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Mon, 21 Jun 2021 01:07:10 -0300 Subject: shader: Move loop safety tests to code emission --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 32 ++--------------------- 1 file changed, 2 insertions(+), 30 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index fff25c4a2..dcaced83f 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -48,22 +48,12 @@ struct GotoVariable : FlagTag { u32 index; }; -struct LoopSafetyVariable { - LoopSafetyVariable() = default; - explicit LoopSafetyVariable(u32 index_) : index{index_} {} - - auto operator<=>(const LoopSafetyVariable&) const noexcept = default; - - u32 index; -}; - struct IndirectBranchVariable { auto operator<=>(const IndirectBranchVariable&) const noexcept = default; }; -using Variant = - std::variant; +using Variant = std::variant; using ValueMap = boost::container::flat_map; struct DefTable { @@ -88,13 +78,6 @@ struct DefTable { goto_vars[variable.index].insert_or_assign(block, value); } - const IR::Value& Def(IR::Block* block, LoopSafetyVariable variable) { - return loop_safety_vars[variable.index][block]; - } - void SetDef(IR::Block* block, LoopSafetyVariable variable, const IR::Value& value) { - loop_safety_vars[variable.index].insert_or_assign(block, value); - } - const IR::Value& Def(IR::Block* block, IndirectBranchVariable) { return indirect_branch_var[block]; } @@ -132,7 +115,6 @@ struct DefTable { std::array preds; boost::container::flat_map goto_vars; - boost::container::flat_map loop_safety_vars; ValueMap indirect_branch_var; ValueMap zero_flag; ValueMap sign_flag; @@ -152,10 +134,6 @@ IR::Opcode UndefOpcode(const FlagTag&) noexcept { return IR::Opcode::UndefU1; } -IR::Opcode UndefOpcode(const LoopSafetyVariable&) noexcept { - return IR::Opcode::UndefU32; -} - IR::Opcode UndefOpcode(IndirectBranchVariable) noexcept { return IR::Opcode::UndefU32; } @@ -337,9 +315,6 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::SetGotoVariable: pass.WriteVariable(GotoVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); break; - case IR::Opcode::SetLoopSafetyVariable: - pass.WriteVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block, inst.Arg(1)); - break; case IR::Opcode::SetIndirectBranchVariable: pass.WriteVariable(IndirectBranchVariable{}, block, inst.Arg(0)); break; @@ -368,9 +343,6 @@ void VisitInst(Pass& pass, IR::Block* block, IR::Inst& inst) { case IR::Opcode::GetGotoVariable: inst.ReplaceUsesWith(pass.ReadVariable(GotoVariable{inst.Arg(0).U32()}, block)); break; - case IR::Opcode::GetLoopSafetyVariable: - inst.ReplaceUsesWith(pass.ReadVariable(LoopSafetyVariable{inst.Arg(0).U32()}, block)); - break; case IR::Opcode::GetIndirectBranchVariable: inst.ReplaceUsesWith(pass.ReadVariable(IndirectBranchVariable{}, block)); break; -- cgit v1.2.3 From bf2956d77ab0ad06c4b5505cc9906e51e5878274 Mon Sep 17 00:00:00 2001 From: ReinUsesLisp Date: Mon, 12 Jul 2021 05:22:01 -0300 Subject: shader: Avoid usage of C++20 ranges to build in clang --- src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) (limited to 'src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp') diff --git a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp index dcaced83f..53145fb5e 100644 --- a/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp +++ b/src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp @@ -14,7 +14,6 @@ // https://link.springer.com/chapter/10.1007/978-3-642-37051-9_6 // -#include #include #include #include @@ -243,7 +242,9 @@ public: void SealBlock(IR::Block* block) { const auto it{incomplete_phis.find(block)}; if (it != incomplete_phis.end()) { - for (auto& [variant, phi] : it->second) { + for (auto& pair : it->second) { + auto& variant{pair.first}; + auto& phi{pair.second}; std::visit([&](auto& variable) { AddPhiOperands(variable, *phi, block); }, variant); } } @@ -373,8 +374,9 @@ void VisitBlock(Pass& pass, IR::Block* block) { void SsaRewritePass(IR::Program& program) { Pass pass; - for (IR::Block* const block : program.post_order_blocks | std::views::reverse) { - VisitBlock(pass, block); + const auto end{program.post_order_blocks.rend()}; + for (auto block = program.post_order_blocks.rbegin(); block != end; ++block) { + VisitBlock(pass, *block); } } -- cgit v1.2.3