From 6c4cc0cd062fbbba5349da1108d3c23cb330ca8a Mon Sep 17 00:00:00 2001
From: ReinUsesLisp <reinuseslisp@airmail.cc>
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 0000000000..a4b256a40e
--- /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 <map>
+
+#include <boost/container/flat_map.hpp>
+
+#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<IR::Block*, IR::Value, std::less<IR::Block*>>;
+
+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<ValueMap, IR::NUM_USER_REGS> regs;
+ std::array<ValueMap, IR::NUM_USER_PREDS> 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-70-g09d2