diff options
| author | bunnei <bunneidev@gmail.com> | 2021-07-25 11:39:04 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2021-07-25 11:39:04 -0700 |
| commit | 98b26b6e126d4775fdf3f773fe8a8ac808a8ff8f (patch) | |
| tree | 816faa96c2c4d291825063433331a8ea4b3d08f1 /src/shader_recompiler/frontend/ir/post_order.cpp | |
| parent | c2aaf5137003868b2375b96ee84e2cb42d5f355e (diff) | |
| parent | 7f13104c1778cfdfd54350e92603164070781124 (diff) | |
Merge pull request #6585 from ameerj/hades
Shader Decompiler Rewrite
Diffstat (limited to 'src/shader_recompiler/frontend/ir/post_order.cpp')
| -rw-r--r-- | src/shader_recompiler/frontend/ir/post_order.cpp | 46 |
1 files changed, 46 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 0000000000..16bc441018 --- /dev/null +++ b/src/shader_recompiler/frontend/ir/post_order.cpp @@ -0,0 +1,46 @@ +// Copyright 2021 yuzu Emulator Project +// Licensed under GPLv2 or any later version +// Refer to the license.txt file included. + +#include <algorithm> + +#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 AbstractSyntaxNode& root) { + boost::container::small_vector<Block*, 16> block_stack; + boost::container::flat_set<Block*> visited; + BlockList post_order_blocks; + + if (root.type != AbstractSyntaxNode::Type::Block) { + throw LogicError("First node in abstract syntax list root is not a block"); + } + Block* const first_block{root.data.block}; + visited.insert(first_block); + block_stack.push_back(first_block); + + while (!block_stack.empty()) { + Block* const block{block_stack.back()}; + const auto visit{[&](Block* branch) { + 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; + }}; + block_stack.pop_back(); + if (std::ranges::none_of(block->ImmSuccessors(), visit)) { + post_order_blocks.push_back(block); + } + } + return post_order_blocks; +} + +} // namespace Shader::IR |