From cbfb7d182a4e90e4e263696d1fca35e47d3eabb4 Mon Sep 17 00:00:00 2001
From: ReinUsesLisp <reinuseslisp@airmail.cc>
Date: Sun, 14 Feb 2021 20:15:42 -0300
Subject: shader: Support SSA loops on IR
---
src/shader_recompiler/frontend/ir/function.h | 1 +
src/shader_recompiler/frontend/ir/post_order.cpp | 48 ++++++++++++++++++++++
src/shader_recompiler/frontend/ir/post_order.h | 13 ++++++
src/shader_recompiler/frontend/maxwell/program.cpp | 12 ++++--
4 files changed, 70 insertions(+), 4 deletions(-)
create mode 100644 src/shader_recompiler/frontend/ir/post_order.cpp
create mode 100644 src/shader_recompiler/frontend/ir/post_order.h
(limited to 'src/shader_recompiler/frontend')
diff --git a/src/shader_recompiler/frontend/ir/function.h b/src/shader_recompiler/frontend/ir/function.h
index fd7d564191..d1f0611467 100644
--- a/src/shader_recompiler/frontend/ir/function.h
+++ b/src/shader_recompiler/frontend/ir/function.h
@@ -12,6 +12,7 @@ namespace Shader::IR {
struct Function {
BlockList blocks;
+ BlockList post_order_blocks;
};
} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/post_order.cpp b/src/shader_recompiler/frontend/ir/post_order.cpp
new file mode 100644
index 0000000000..a48b8dec5a
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/post_order.cpp
@@ -0,0 +1,48 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#include <boost/container/flat_set.hpp>
+#include <boost/container/small_vector.hpp>
+
+#include "shader_recompiler/frontend/ir/basic_block.h"
+#include "shader_recompiler/frontend/ir/post_order.h"
+
+namespace Shader::IR {
+
+BlockList PostOrder(const BlockList& blocks) {
+ boost::container::small_vector<Block*, 16> block_stack;
+ boost::container::flat_set<Block*> visited;
+
+ BlockList post_order_blocks;
+ post_order_blocks.reserve(blocks.size());
+
+ Block* const first_block{blocks.front()};
+ visited.insert(first_block);
+ block_stack.push_back(first_block);
+
+ const auto visit_branch = [&](Block* block, Block* branch) {
+ if (!branch) {
+ return false;
+ }
+ if (!visited.insert(branch).second) {
+ return false;
+ }
+ // Calling push_back twice is faster than insert on msvc
+ block_stack.push_back(block);
+ block_stack.push_back(branch);
+ return true;
+ };
+ while (!block_stack.empty()) {
+ Block* const block{block_stack.back()};
+ block_stack.pop_back();
+
+ if (!visit_branch(block, block->TrueBranch()) &&
+ !visit_branch(block, block->FalseBranch())) {
+ post_order_blocks.push_back(block);
+ }
+ }
+ return post_order_blocks;
+}
+
+} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/ir/post_order.h b/src/shader_recompiler/frontend/ir/post_order.h
new file mode 100644
index 0000000000..30137ff57a
--- /dev/null
+++ b/src/shader_recompiler/frontend/ir/post_order.h
@@ -0,0 +1,13 @@
+// Copyright 2021 yuzu Emulator Project
+// Licensed under GPLv2 or any later version
+// Refer to the license.txt file included.
+
+#pragma once
+
+#include "shader_recompiler/frontend/ir/basic_block.h"
+
+namespace Shader::IR {
+
+BlockList PostOrder(const BlockList& blocks);
+
+} // namespace Shader::IR
diff --git a/src/shader_recompiler/frontend/maxwell/program.cpp b/src/shader_recompiler/frontend/maxwell/program.cpp
index 9fa912ed8e..dab6d68c02 100644
--- a/src/shader_recompiler/frontend/maxwell/program.cpp
+++ b/src/shader_recompiler/frontend/maxwell/program.cpp
@@ -7,6 +7,7 @@
#include <vector>
#include "shader_recompiler/frontend/ir/basic_block.h"
+#include "shader_recompiler/frontend/ir/post_order.h"
#include "shader_recompiler/frontend/ir/structured_control_flow.h"
#include "shader_recompiler/frontend/maxwell/program.h"
#include "shader_recompiler/frontend/maxwell/translate/translate.h"
@@ -56,11 +57,14 @@ IR::Program TranslateProgram(ObjectPool<IR::Inst>& inst_pool, ObjectPool<IR::Blo
}
fmt::print(stdout, "No optimizations: {}", IR::DumpProgram(program));
- std::ranges::for_each(functions, Optimization::SsaRewritePass);
for (IR::Function& function : functions) {
- Optimization::Invoke(Optimization::GlobalMemoryToStorageBufferPass, function);
- Optimization::Invoke(Optimization::ConstantPropagationPass, function);
- Optimization::Invoke(Optimization::DeadCodeEliminationPass, function);
+ function.post_order_blocks = PostOrder(function.blocks);
+ Optimization::SsaRewritePass(function.post_order_blocks);
+ }
+ for (IR::Function& function : functions) {
+ Optimization::PostOrderInvoke(Optimization::GlobalMemoryToStorageBufferPass, function);
+ Optimization::PostOrderInvoke(Optimization::ConstantPropagationPass, function);
+ Optimization::PostOrderInvoke(Optimization::DeadCodeEliminationPass, function);
Optimization::IdentityRemovalPass(function);
Optimization::VerificationPass(function);
}
--
cgit v1.2.3-70-g09d2