blob: f526615fc44ccfdfefb72140a7f8162a9e665072 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
// SPDX-FileCopyrightText: Copyright 2021 yuzu Emulator Project
// SPDX-License-Identifier: GPL-2.0-or-later
#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
|
