diff options
author | Steven Perron <stevenperron@google.com> | 2022-09-02 19:27:10 +0300 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-09-02 19:27:10 +0300 |
commit | 529955e03dda72b66bf83e89a57565b03e55e14b (patch) | |
tree | 76dc80ac30248f260209c018363e7c6c3f4e1371 | |
parent | 8eb85098342a998d1b835bfd591fba2f19a6dcb9 (diff) |
Improve time to build dominators (#4916)
Changed a couple small parts of the algorithm to reduce time to build
the dominator trees. There should be no visible changes.
Add a depth first search algorithm that does not run a function on
backedges. The check if an edge is a back edge is time consuming, and
pointless if the function run on it is a nop.
-rw-r--r-- | source/cfa.h | 53 | ||||
-rw-r--r-- | source/opt/cfg.cpp | 4 | ||||
-rw-r--r-- | source/opt/dominator_tree.cpp | 28 | ||||
-rw-r--r-- | source/val/validate_cfg.cpp | 7 |
4 files changed, 56 insertions, 36 deletions
diff --git a/source/cfa.h b/source/cfa.h index f55a7bde6..2743ab40c 100644 --- a/source/cfa.h +++ b/source/cfa.h @@ -56,8 +56,33 @@ class CFA { /// /// This function performs a depth first traversal from the \p entry /// BasicBlock and calls the pre/postorder functions when it needs to process + /// the node in pre order, post order. + /// + /// @param[in] entry The root BasicBlock of a CFG + /// @param[in] successor_func A function which will return a pointer to the + /// successor nodes + /// @param[in] preorder A function that will be called for every block in a + /// CFG following preorder traversal semantics + /// @param[in] postorder A function that will be called for every block in a + /// CFG following postorder traversal semantics + /// @param[in] terminal A function that will be called to determine if the + /// search should stop at the given node. + /// NOTE: The @p successor_func and predecessor_func each return a pointer to + /// a collection such that iterators to that collection remain valid for the + /// lifetime of the algorithm. + static void DepthFirstTraversal(const BB* entry, + get_blocks_func successor_func, + std::function<void(cbb_ptr)> preorder, + std::function<void(cbb_ptr)> postorder, + std::function<bool(cbb_ptr)> terminal); + + /// @brief Depth first traversal starting from the \p entry BasicBlock + /// + /// This function performs a depth first traversal from the \p entry + /// BasicBlock and calls the pre/postorder functions when it needs to process /// the node in pre order, post order. It also calls the backedge function - /// when a back edge is encountered. + /// when a back edge is encountered. The backedge function can be empty. The + /// runtime of the algorithm is improved if backedge is empty. /// /// @param[in] entry The root BasicBlock of a CFG /// @param[in] successor_func A function which will return a pointer to the @@ -67,12 +92,11 @@ class CFA { /// @param[in] postorder A function that will be called for every block in a /// CFG following postorder traversal semantics /// @param[in] backedge A function that will be called when a backedge is - /// encountered during a traversal + /// encountered during a traversal. /// @param[in] terminal A function that will be called to determine if the /// search should stop at the given node. /// NOTE: The @p successor_func and predecessor_func each return a pointer to - /// a - /// collection such that iterators to that collection remain valid for the + /// a collection such that iterators to that collection remain valid for the /// lifetime of the algorithm. static void DepthFirstTraversal( const BB* entry, get_blocks_func successor_func, @@ -137,12 +161,27 @@ bool CFA<BB>::FindInWorkList(const std::vector<block_info>& work_list, } template <class BB> +void CFA<BB>::DepthFirstTraversal(const BB* entry, + get_blocks_func successor_func, + std::function<void(cbb_ptr)> preorder, + std::function<void(cbb_ptr)> postorder, + std::function<bool(cbb_ptr)> terminal) { + DepthFirstTraversal(entry, successor_func, preorder, postorder, + /* backedge = */ {}, terminal); +} + +template <class BB> void CFA<BB>::DepthFirstTraversal( const BB* entry, get_blocks_func successor_func, std::function<void(cbb_ptr)> preorder, std::function<void(cbb_ptr)> postorder, std::function<void(cbb_ptr, cbb_ptr)> backedge, std::function<bool(cbb_ptr)> terminal) { + assert(successor_func && "The successor function cannot be empty."); + assert(preorder && "The preorder function cannot be empty."); + assert(postorder && "The postorder function cannot be empty."); + assert(terminal && "The terminal function cannot be empty."); + std::unordered_set<uint32_t> processed; /// NOTE: work_list is the sequence of nodes from the root node to the node @@ -162,7 +201,7 @@ void CFA<BB>::DepthFirstTraversal( } else { BB* child = *top.iter; top.iter++; - if (FindInWorkList(work_list, child->id())) { + if (backedge && FindInWorkList(work_list, child->id())) { backedge(top.block, child); } if (processed.count(child->id()) == 0) { @@ -269,14 +308,12 @@ std::vector<BB*> CFA<BB>::TraversalRoots(const std::vector<BB*>& blocks, auto mark_visited = [&visited](const BB* b) { visited.insert(b); }; auto ignore_block = [](const BB*) {}; - auto ignore_blocks = [](const BB*, const BB*) {}; auto no_terminal_blocks = [](const BB*) { return false; }; auto traverse_from_root = [&mark_visited, &succ_func, &ignore_block, - &ignore_blocks, &no_terminal_blocks](const BB* entry) { DepthFirstTraversal(entry, succ_func, mark_visited, ignore_block, - ignore_blocks, no_terminal_blocks); + no_terminal_blocks); }; std::vector<BB*> result; diff --git a/source/opt/cfg.cpp b/source/opt/cfg.cpp index 66b1aeda8..a0248d54c 100644 --- a/source/opt/cfg.cpp +++ b/source/opt/cfg.cpp @@ -87,7 +87,6 @@ void CFG::ComputeStructuredOrder(Function* func, BasicBlock* root, // Compute structured successors and do DFS. ComputeStructuredSuccessors(func); auto ignore_block = [](cbb_ptr) {}; - auto ignore_edge = [](cbb_ptr, cbb_ptr) {}; auto terminal = [end](cbb_ptr bb) { return bb == end; }; auto get_structured_successors = [this](const BasicBlock* b) { @@ -100,8 +99,7 @@ void CFG::ComputeStructuredOrder(Function* func, BasicBlock* root, order->push_front(const_cast<BasicBlock*>(b)); }; CFA<BasicBlock>::DepthFirstTraversal(root, get_structured_successors, - ignore_block, post_order, ignore_edge, - terminal); + ignore_block, post_order, terminal); } void CFG::ForEachBlockInPostOrder(BasicBlock* bb, diff --git a/source/opt/dominator_tree.cpp b/source/opt/dominator_tree.cpp index d6017bb19..2680be2af 100644 --- a/source/opt/dominator_tree.cpp +++ b/source/opt/dominator_tree.cpp @@ -57,10 +57,8 @@ 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*) {}; auto no_terminal_blocks = [](const BBType*) { return false; }; - CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post, nop_backedge, + CFA<BBType>::DepthFirstTraversal(bb, successors, pre, post, no_terminal_blocks); } @@ -105,7 +103,8 @@ 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 @@ -160,19 +159,7 @@ BasicBlockSuccessorHelper<BBType>::BasicBlockSuccessorHelper( template <typename BBType> void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap( Function& f, const BasicBlock* placeholder_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; - }; + IRContext* context = f.DefInst().context(); if (invert_graph_) { // For the post dominator tree, we see the inverted graph. @@ -186,9 +173,8 @@ void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap( 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); @@ -209,7 +195,7 @@ void BasicBlockSuccessorHelper<BBType>::CreateSuccessorMap( 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); }); diff --git a/source/val/validate_cfg.cpp b/source/val/validate_cfg.cpp index 6c341cb8d..87975e1ef 100644 --- a/source/val/validate_cfg.cpp +++ b/source/val/validate_cfg.cpp @@ -896,14 +896,13 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { // CFG to ensure we cover all the blocks. std::vector<const BasicBlock*> postorder; auto ignore_block = [](const BasicBlock*) {}; - auto ignore_edge = [](const BasicBlock*, const BasicBlock*) {}; auto no_terminal_blocks = [](const BasicBlock*) { return false; }; if (!function.ordered_blocks().empty()) { /// calculate dominators CFA<BasicBlock>::DepthFirstTraversal( function.first_block(), function.AugmentedCFGSuccessorsFunction(), ignore_block, [&](const BasicBlock* b) { postorder.push_back(b); }, - ignore_edge, no_terminal_blocks); + no_terminal_blocks); auto edges = CFA<BasicBlock>::CalculateDominators( postorder, function.AugmentedCFGPredecessorsFunction()); for (auto edge : edges) { @@ -953,7 +952,7 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { CFA<BasicBlock>::DepthFirstTraversal( function.first_block(), function.AugmentedStructuralCFGSuccessorsFunction(), ignore_block, - [&](const BasicBlock* b) { postorder.push_back(b); }, ignore_edge, + [&](const BasicBlock* b) { postorder.push_back(b); }, no_terminal_blocks); auto edges = CFA<BasicBlock>::CalculateDominators( postorder, function.AugmentedStructuralCFGPredecessorsFunction()); @@ -967,7 +966,7 @@ spv_result_t PerformCfgChecks(ValidationState_t& _) { function.pseudo_exit_block(), function.AugmentedStructuralCFGPredecessorsFunction(), ignore_block, [&](const BasicBlock* b) { postdom_postorder.push_back(b); }, - ignore_edge, no_terminal_blocks); + no_terminal_blocks); auto postdom_edges = CFA<BasicBlock>::CalculateDominators( postdom_postorder, function.AugmentedStructuralCFGSuccessorsFunction()); |