diff options
Diffstat (limited to '')
-rw-r--r-- | src/shader_recompiler/frontend/ir/function.h | 1 | ||||
-rw-r--r-- | src/shader_recompiler/frontend/ir/post_order.cpp | 48 | ||||
-rw-r--r-- | src/shader_recompiler/frontend/ir/post_order.h | 13 |
3 files changed, 62 insertions, 0 deletions
diff --git a/src/shader_recompiler/frontend/ir/function.h b/src/shader_recompiler/frontend/ir/function.h index fd7d56419..d1f061146 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 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 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 000000000..30137ff57 --- /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 |