summaryrefslogtreecommitdiffstats
path: root/src/shader_recompiler/ir_opt
diff options
context:
space:
mode:
authorReinUsesLisp <reinuseslisp@airmail.cc>2021-02-03 01:07:00 +0100
committerameerj <52414509+ameerj@users.noreply.github.com>2021-07-23 03:51:21 +0200
commit6c4cc0cd062fbbba5349da1108d3c23cb330ca8a (patch)
tree544291931da8a85fafcea71964c77d9278ec7f29 /src/shader_recompiler/ir_opt
parentshader: Initial recompiler work (diff)
downloadyuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar.gz
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar.bz2
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar.lz
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar.xz
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.tar.zst
yuzu-6c4cc0cd062fbbba5349da1108d3c23cb330ca8a.zip
Diffstat (limited to 'src/shader_recompiler/ir_opt')
-rw-r--r--src/shader_recompiler/ir_opt/identity_removal_pass.cpp1
-rw-r--r--src/shader_recompiler/ir_opt/passes.h9
-rw-r--r--src/shader_recompiler/ir_opt/ssa_rewrite_pass.cpp155
3 files changed, 164 insertions, 1 deletions
diff --git a/src/shader_recompiler/ir_opt/identity_removal_pass.cpp b/src/shader_recompiler/ir_opt/identity_removal_pass.cpp
index f9bb063fb..7f8500087 100644
--- a/src/shader_recompiler/ir_opt/identity_removal_pass.cpp
+++ b/src/shader_recompiler/ir_opt/identity_removal_pass.cpp
@@ -28,7 +28,6 @@ void IdentityRemovalPass(IR::Block& block) {
++inst;
}
}
-
for (IR::Inst* const inst : to_invalidate) {
inst->Invalidate();
}
diff --git a/src/shader_recompiler/ir_opt/passes.h b/src/shader_recompiler/ir_opt/passes.h
index fe5454e9a..83f094d73 100644
--- a/src/shader_recompiler/ir_opt/passes.h
+++ b/src/shader_recompiler/ir_opt/passes.h
@@ -5,12 +5,21 @@
#pragma once
#include "shader_recompiler/frontend/ir/basic_block.h"
+#include "shader_recompiler/frontend/ir/function.h"
namespace Shader::Optimization {
+template <typename Func>
+void Invoke(Func&& func, IR::Function& function) {
+ for (const auto& block : function.blocks) {
+ func(*block);
+ }
+}
+
void DeadCodeEliminationPass(IR::Block& block);
void GetSetElimination(IR::Block& block);
void IdentityRemovalPass(IR::Block& block);
+void SsaRewritePass(IR::Function& function);
void VerificationPass(const IR::Block& block);
} // namespace Shader::Optimization
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 <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