summaryrefslogtreecommitdiffstats
path: root/src/shader_recompiler/frontend/ir/post_order.cpp
diff options
context:
space:
mode:
authorReinUsesLisp <reinuseslisp@airmail.cc>2021-02-15 00:15:42 +0100
committerameerj <52414509+ameerj@users.noreply.github.com>2021-07-23 03:51:22 +0200
commitcbfb7d182a4e90e4e263696d1fca35e47d3eabb4 (patch)
treea8d384aa0daefdfafd9b61330e06b1cf7ac40ea6 /src/shader_recompiler/frontend/ir/post_order.cpp
parentshader: Misc fixes (diff)
downloadyuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar.gz
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar.bz2
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar.lz
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar.xz
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.tar.zst
yuzu-cbfb7d182a4e90e4e263696d1fca35e47d3eabb4.zip
Diffstat (limited to 'src/shader_recompiler/frontend/ir/post_order.cpp')
-rw-r--r--src/shader_recompiler/frontend/ir/post_order.cpp48
1 files changed, 48 insertions, 0 deletions
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 000000000..a48b8dec5
--- /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