diff options
Diffstat (limited to '')
-rw-r--r-- | src/shader_recompiler/frontend/ir/post_order.cpp | 48 |
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 |