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.

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());