summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp')
-rw-r--r--3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp88
1 files changed, 40 insertions, 48 deletions
diff --git a/3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp b/3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp
index c9346e1c53e..2680be2af49 100644
--- a/3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp
+++ b/3rdparty/bgfx/3rdparty/spirv-tools/source/opt/dominator_tree.cpp
@@ -22,8 +22,8 @@
// Calculates the dominator or postdominator tree for a given function.
// 1 - Compute the successors and predecessors for each BasicBlock. We add a
-// dummy node for the start node or for postdominators the exit. This node will
-// point to all entry or all exit nodes.
+// placeholder node for the start node or for postdominators the exit. This node
+// will point to all entry or all exit nodes.
// 2 - Using the CFA::DepthFirstTraversal get a depth first postordered list of
// all BasicBlocks. Using the successors (or for postdominator, predecessors)
// calculated in step 1 to traverse the tree.
@@ -48,7 +48,7 @@ namespace {
// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
// SuccessorLambda - Lamdba matching the signature of 'const
// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
-// succeding BasicBlock A.
+// succeeding BasicBlock A.
// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
// called on each node traversed AFTER their children.
// PreLambda - Lamdba matching the signature of 'void (const BBType*)' will be
@@ -57,9 +57,9 @@ template <typename BBType, typename SuccessorLambda, typename PreLambda,
typename PostLambda>
static void DepthFirstSearch(const BBType* bb, SuccessorLambda successors,
PreLambda pre, PostLambda post) {
- // Ignore backedge operation.
- auto nop_backedge = [](const BBType*, const BBType*) {};
- CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post, nop_backedge);
+ auto no_terminal_blocks = [](const BBType*) { return false; };
+ CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post,
+ no_terminal_blocks);
}
// Wrapper around CFA::DepthFirstTraversal to provide an interface to perform
@@ -69,7 +69,7 @@ static void DepthFirstSearch(const BBType* bb, SuccessorLambda successors,
// BBType - BasicBlock type. Will either be BasicBlock or DominatorTreeNode
// SuccessorLambda - Lamdba matching the signature of 'const
// std::vector<BBType>*(const BBType *A)'. Will return a vector of the nodes
-// succeding BasicBlock A.
+// succeeding BasicBlock A.
// PostLambda - Lamdba matching the signature of 'void (const BBType*)' will be
// called on each node traversed after their children.
template <typename BBType, typename SuccessorLambda, typename PostLambda>
@@ -103,12 +103,14 @@ class BasicBlockSuccessorHelper {
using Function = typename GetFunctionClass<BBType>::FunctionType;
using BasicBlockListTy = std::vector<BasicBlock*>;
- using BasicBlockMapTy = std::map<const BasicBlock*, BasicBlockListTy>;
+ using BasicBlockMapTy =
+ std::unordered_map<const BasicBlock*, BasicBlockListTy>;
public:
// For compliance with the dominance tree computation, entry nodes are
- // connected to a single dummy node.
- BasicBlockSuccessorHelper(Function& func, const BasicBlock* dummy_start_node,
+ // connected to a single placeholder node.
+ BasicBlockSuccessorHelper(Function& func,
+ const BasicBlock* placeholder_start_node,
bool post);
// CFA::CalculateDominators requires std::vector<BasicBlock*>.
@@ -139,72 +141,61 @@ class BasicBlockSuccessorHelper {
// Build the successors and predecessors map for each basic blocks |f|.
// If |invert_graph_| is true, all edges are reversed (successors becomes
// predecessors and vice versa).
- // For convenience, the start of the graph is |dummy_start_node|.
+ // For convenience, the start of the graph is |placeholder_start_node|.
// The dominator tree construction requires a unique entry node, which cannot
- // be guaranteed for the postdominator graph. The |dummy_start_node| BB is
- // here to gather all entry nodes.
- void CreateSuccessorMap(Function& f, const BasicBlock* dummy_start_node);
+ // be guaranteed for the postdominator graph. The |placeholder_start_node| BB
+ // is here to gather all entry nodes.
+ void CreateSuccessorMap(Function& f,
+ const BasicBlock* placeholder_start_node);
};
template <typename BBType>
BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper(
- Function& func, const BasicBlock* dummy_start_node, bool invert)
+ Function& func, const BasicBlock* placeholder_start_node, bool invert)
: invert_graph_(invert) {
- CreateSuccessorMap(func, dummy_start_node);
+ CreateSuccessorMap(func, placeholder_start_node);
}
template <typename BBType>
void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap(
- Function& f, const BasicBlock* dummy_start_node) {
- std::map<uint32_t, BasicBlock*> id_to_BB_map;
- auto GetSuccessorBasicBlock = [&f, &id_to_BB_map](uint32_t successor_id) {
- BasicBlock*& Succ = id_to_BB_map[successor_id];
- if (!Succ) {
- for (BasicBlock& BBIt : f) {
- if (successor_id == BBIt.id()) {
- Succ = &BBIt;
- break;
- }
- }
- }
- return Succ;
- };
+ Function& f, const BasicBlock* placeholder_start_node) {
+ IRContext* context = f.DefInst().context();
if (invert_graph_) {
// For the post dominator tree, we see the inverted graph.
// successors_ in the inverted graph are the predecessors in the CFG.
- // The tree construction requires 1 entry point, so we add a dummy node
- // that is connected to all function exiting basic blocks.
- // An exiting basic block is a block with an OpKill, OpUnreachable,
- // OpReturn or OpReturnValue as terminator instruction.
+ // The tree construction requires 1 entry point, so we add a placeholder
+ // node that is connected to all function exiting basic blocks. An exiting
+ // basic block is a block with an OpKill, OpUnreachable, OpReturn,
+ // OpReturnValue, or OpTerminateInvocation as terminator instruction.
for (BasicBlock& bb : f) {
if (bb.hasSuccessor()) {
BasicBlockListTy& pred_list = predecessors_[&bb];
const auto& const_bb = bb;
const_bb.ForEachSuccessorLabel(
- [this, &pred_list, &bb,
- &GetSuccessorBasicBlock](const uint32_t successor_id) {
- BasicBlock* succ = GetSuccessorBasicBlock(successor_id);
+ [this, &pred_list, &bb, context](const uint32_t successor_id) {
+ BasicBlock* succ = context->get_instr_block(successor_id);
// Inverted graph: our successors in the CFG
// are our predecessors in the inverted graph.
this->successors_[succ].push_back(&bb);
pred_list.push_back(succ);
});
} else {
- successors_[dummy_start_node].push_back(&bb);
- predecessors_[&bb].push_back(const_cast<BasicBlock*>(dummy_start_node));
+ successors_[placeholder_start_node].push_back(&bb);
+ predecessors_[&bb].push_back(
+ const_cast<BasicBlock*>(placeholder_start_node));
}
}
} else {
- successors_[dummy_start_node].push_back(f.entry().get());
+ successors_[placeholder_start_node].push_back(f.entry().get());
predecessors_[f.entry().get()].push_back(
- const_cast<BasicBlock*>(dummy_start_node));
+ const_cast<BasicBlock*>(placeholder_start_node));
for (BasicBlock& bb : f) {
BasicBlockListTy& succ_list = successors_[&bb];
const auto& const_bb = bb;
const_bb.ForEachSuccessorLabel([&](const uint32_t successor_id) {
- BasicBlock* succ = GetSuccessorBasicBlock(successor_id);
+ BasicBlock* succ = context->get_instr_block(successor_id);
succ_list.push_back(succ);
predecessors_[succ].push_back(&bb);
});
@@ -241,6 +232,7 @@ bool DominatorTree::Dominates(uint32_t a, uint32_t b) const {
bool DominatorTree::Dominates(const DominatorTreeNode* a,
const DominatorTreeNode* b) const {
+ if (!a || !b) return false;
// Node A dominates node B if they are the same.
if (a == b) return true;
@@ -286,7 +278,7 @@ DominatorTreeNode* DominatorTree::GetOrInsertNode(BasicBlock* bb) {
}
void DominatorTree::GetDominatorEdges(
- const Function* f, const BasicBlock* dummy_start_node,
+ const Function* f, const BasicBlock* placeholder_start_node,
std::vector<std::pair<BasicBlock*, BasicBlock*>>* edges) {
// Each time the depth first traversal calls the postorder callback
// std::function we push that node into the postorder vector to create our
@@ -300,7 +292,7 @@ void DominatorTree::GetDominatorEdges(
// BB are derived from F, so we need to const cast it at some point
// no modification is made on F.
BasicBlockSuccessorHelper<BasicBlock> helper{
- *const_cast<Function*>(f), dummy_start_node, postdominator_};
+ *const_cast<Function*>(f), placeholder_start_node, postdominator_};
// The successor function tells DepthFirstTraversal how to move to successive
// nodes by providing an interface to get a list of successor nodes from any
@@ -314,7 +306,7 @@ void DominatorTree::GetDominatorEdges(
// If we're building a post dominator tree we traverse the tree in reverse
// using the predecessor function in place of the successor function and vice
// versa.
- DepthFirstSearchPostOrder(dummy_start_node, successor_functor,
+ DepthFirstSearchPostOrder(placeholder_start_node, successor_functor,
postorder_function);
*edges = CFA<BasicBlock>::CalculateDominators(postorder, predecessor_functor);
}
@@ -327,12 +319,12 @@ void DominatorTree::InitializeTree(const CFG& cfg, const Function* f) {
return;
}
- const BasicBlock* dummy_start_node =
+ const BasicBlock* placeholder_start_node =
postdominator_ ? cfg.pseudo_exit_block() : cfg.pseudo_entry_block();
// Get the immediate dominator for each node.
std::vector<std::pair<BasicBlock*, BasicBlock*>> edges;
- GetDominatorEdges(f, dummy_start_node, &edges);
+ GetDominatorEdges(f, placeholder_start_node, &edges);
// Transform the vector<pair> into the tree structure which we can use to
// efficiently query dominance.
@@ -378,7 +370,7 @@ void DominatorTree::DumpTreeAsDot(std::ostream& out_stream) const {
}
// Print the arrow from the parent to this node. Entry nodes will not have
- // parents so draw them as children from the dummy node.
+ // parents so draw them as children from the placeholder node.
if (node->parent_) {
out_stream << node->parent_->bb_->id() << " -> " << node->bb_->id()
<< ";\n";