[Dominators] Move helper functions into SemiNCAInfo

[kuhar]

Summary

Helper functions (DFSPass, ReverseDFSPass, Eval) need SemiNCAInfo anyway, so it's simpler to have them there as member functions. This also makes them simpler by removing template boilerplate.

[kuhar]

Calculate doesn't have to be DominatorTreeBase's friend anymore.

[• dberlin]

The formatting looks a little odd.
I'm not sure we would name the namespace detail (i'll comment in the patch that adds it)
Otherwise, looks fine.

[kuhar]

Update the diff.

[kuhar]

Update the diff to apply cleanly.

llvm/trunk/include/llvm/Support/GenericDomTree.h

 protected:
  friend struct DomTreeBuilder::SemiNCAInfo<NodeT>;
  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
 
  template <class FuncT, class NodeTy>
  friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeTy>> &DT,
                        FuncT &F);
 
   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 
 public:
   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
   /// dominator tree in dfs order.
   void updateDFSNumbers() const {
     if (DFSInfoValid) {
       SlowQueries = 0;
       return;

llvm/trunk/include/llvm/Support/GenericDomTreeConstruction.h

TreeNodePtr getNodeForBlock(NodePtr BB) {
     TreeNodePtr IDomNode = getNodeForBlock(IDom);
 
     // Add a new tree node for this NodeT, and link it as a child of
     // IDomNode
     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
         .get();
   }
-};
-}  // namespace DomTreeBuilder
 
   // External storage for depth first iterator that reuses the info lookup map
-// domtree already has.  We don't have a set, but a map instead, so we are
+  // SemiNCAInfo already has. We don't have a set, but a map instead, so we are
   // converting the one argument insert calls.
-template <class NodeRef, class InfoType> struct df_iterator_dom_storage {
+  struct df_iterator_dom_storage {
    public:
-  using BaseSet = DenseMap<NodeRef, InfoType>;
+    using BaseSet = decltype(NodeToInfo);
     df_iterator_dom_storage(BaseSet &Storage) : Storage(Storage) {}
 
     using iterator = typename BaseSet::iterator;
-  std::pair<iterator, bool> insert(NodeRef N) {
-    return Storage.insert({N, InfoType()});
+    std::pair<iterator, bool> insert(NodePtr N) {
+      return Storage.insert({N, InfoRec()});
     }
-  void completed(NodeRef) {}
+    void completed(NodePtr) {}
 
    private:
     BaseSet &Storage;
   };
 
-template <class NodePtr,
-          class NodeT = typename std::remove_pointer<NodePtr>::type>
-unsigned ReverseDFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA,
-                        unsigned N) {
-  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
-  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
-      SNCA.NodeToInfo);
+  df_iterator_dom_storage getStorage() { return {NodeToInfo}; }
+
+  unsigned runReverseDFS(NodePtr V, unsigned N) {
+    auto DFStorage = getStorage();
 
     bool IsChildOfArtificialExit = (N != 0);
     for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
          I != E; ++I) {
       NodePtr BB = *I;
-    auto &BBInfo = SNCA.NodeToInfo[BB];
+      auto &BBInfo = NodeToInfo[BB];
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = BB;
       // Set the parent to the top of the visited stack.  The stack includes us,
       // and is 1 based, so we subtract to account for both of these.
       if (I.getPathLength() > 1)
-      BBInfo.Parent = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-    SNCA.NumToNode.push_back(BB);  // NumToNode[n] = V;
+        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+      NumToNode.push_back(BB);  // NumToNode[n] = V;
 
       if (IsChildOfArtificialExit)
         BBInfo.Parent = 1;
 
       IsChildOfArtificialExit = false;
     }
     return N;
   }
 
-template <class NodePtr,
-          class NodeT = typename std::remove_pointer<NodePtr>::type>
-unsigned DFSPass(NodePtr V, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA, unsigned N) {
-  using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>;
-  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
-      SNCA.NodeToInfo);
+  unsigned runDFS(NodePtr V, unsigned N) {
+    auto DFStorage = getStorage();
 
     for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
          I != E; ++I) {
       NodePtr BB = *I;
-    auto &BBInfo = SNCA.NodeToInfo[BB];
+      auto &BBInfo = NodeToInfo[BB];
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = BB;
       // Set the parent to the top of the visited stack.  The stack includes us,
       // and is 1 based, so we subtract to account for both of these.
       if (I.getPathLength() > 1)
-      BBInfo.Parent = SNCA.NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
-    SNCA.NumToNode.push_back(BB);  // NumToNode[n] = V;
+        BBInfo.Parent = NodeToInfo[I.getPath(I.getPathLength() - 2)].DFSNum;
+      NumToNode.push_back(BB);  // NumToNode[n] = V;
     }
     return N;
   }
 
-template <class NodePtr,
-          class NodeT = typename std::remove_pointer<NodePtr>::type>
-NodePtr Eval(NodePtr VIn, DomTreeBuilder::SemiNCAInfo<NodeT> &SNCA,
-             unsigned LastLinked) {
-  auto &VInInfo = SNCA.NodeToInfo[VIn];
+  NodePtr eval(NodePtr VIn, unsigned LastLinked) {
+    auto &VInInfo = NodeToInfo[VIn];
     if (VInInfo.DFSNum < LastLinked)
       return VIn;
 
     SmallVector<NodePtr, 32> Work;
     SmallPtrSet<NodePtr, 32> Visited;
 
     if (VInInfo.Parent >= LastLinked)
       Work.push_back(VIn);
 
     while (!Work.empty()) {
       NodePtr V = Work.back();
-    auto &VInfo = SNCA.NodeToInfo[V];
-    NodePtr VAncestor = SNCA.NumToNode[VInfo.Parent];
+      auto &VInfo = NodeToInfo[V];
+      NodePtr VAncestor = NumToNode[VInfo.Parent];
 
       // Process Ancestor first
       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
         Work.push_back(VAncestor);
         continue;
       }
       Work.pop_back();
 
       // Update VInfo based on Ancestor info
       if (VInfo.Parent < LastLinked)
         continue;
 
-    auto &VAInfo = SNCA.NodeToInfo[VAncestor];
+      auto &VAInfo = NodeToInfo[VAncestor];
       NodePtr VAncestorLabel = VAInfo.Label;
       NodePtr VLabel = VInfo.Label;
-    if (SNCA.NodeToInfo[VAncestorLabel].Semi < SNCA.NodeToInfo[VLabel].Semi)
+      if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
         VInfo.Label = VAncestorLabel;
       VInfo.Parent = VAInfo.Parent;
     }
 
     return VInInfo.Label;
   }
 
-template <class FuncT, class NodeT>
-void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
-               FuncT &F) {
-  using GraphT = GraphTraits<NodeT>;
-  using NodePtr = typename GraphT::NodeRef;
-  static_assert(std::is_pointer<NodePtr>::value,
-                "NodePtr should be a pointer type");
-  using NodeType = typename std::remove_pointer<NodePtr>::type;
-
+  template <typename NodeType>
+  void runSemiNCA(unsigned NumBlocks) {
     unsigned N = 0;
-  DomTreeBuilder::SemiNCAInfo<NodeType> SNCA(DT);
-  SNCA.NumToNode.push_back(nullptr);
+    NumToNode.push_back(nullptr);
 
     bool MultipleRoots = (DT.Roots.size() > 1);
     if (MultipleRoots) {
-    auto &BBInfo = SNCA.NodeToInfo[nullptr];
+      auto &BBInfo = NodeToInfo[nullptr];
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = nullptr;
 
-    SNCA.NumToNode.push_back(nullptr); // NumToNode[n] = V;
+      NumToNode.push_back(nullptr); // NumToNode[n] = V;
     }
 
     // Step #1: Number blocks in depth-first order and initialize variables used
     // in later stages of the algorithm.
     if (DT.isPostDominator()){
       for (unsigned i = 0, e = static_cast<unsigned>(DT.Roots.size());
            i != e; ++i)
-      N = ReverseDFSPass<NodePtr>(DT.Roots[i], SNCA, N);
+        N = runReverseDFS(DT.Roots[i], N);
     } else {
-    N = DFSPass<NodePtr>(DT.Roots[0], SNCA, N);
+      N = runDFS(DT.Roots[0], N);
     }
 
     // It might be that some blocks did not get a DFS number (e.g., blocks of
     // infinite loops). In these cases an artificial exit node is required.
-  MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F));
+    MultipleRoots |= (DT.isPostDominator() && N != NumBlocks);
 
     // Initialize IDoms to spanning tree parents.
     for (unsigned i = 1; i <= N; ++i) {
-    const NodePtr V = SNCA.NumToNode[i];
-    auto &VInfo = SNCA.NodeToInfo[V];
-    VInfo.IDom = SNCA.NumToNode[VInfo.Parent];
+      const NodePtr V = NumToNode[i];
+      auto &VInfo = NodeToInfo[V];
+      VInfo.IDom = NumToNode[VInfo.Parent];
     }
 
     // Step #2: Calculate the semidominators of all vertices.
     for (unsigned i = N; i >= 2; --i) {
-    NodePtr W = SNCA.NumToNode[i];
-    auto &WInfo = SNCA.NodeToInfo[W];
+      NodePtr W = NumToNode[i];
+      auto &WInfo = NodeToInfo[W];
 
       // Initialize the semi dominator to point to the parent node.
       WInfo.Semi = WInfo.Parent;
-    for (const auto &N : inverse_children<NodeT>(W))
-      if (SNCA.NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
-        unsigned SemiU = SNCA.NodeToInfo[Eval<NodePtr>(N, SNCA, i + 1)].Semi;
+      for (const auto &N : inverse_children<NodeType>(W))
+        if (NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
+          unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
           if (SemiU < WInfo.Semi)
             WInfo.Semi = SemiU;
         }
     }
 
-
     // Step #3: Explicitly define the immediate dominator of each vertex.
     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
-  // Note that the parents were stored in IDoms and later got invalidated during
-  // path compression in Eval.
+    // Note that the parents were stored in IDoms and later got invalidated
+    // during path compression in Eval.
     for (unsigned i = 2; i <= N; ++i) {
-    const NodePtr W = SNCA.NumToNode[i];
-    auto &WInfo = SNCA.NodeToInfo[W];
-    const unsigned SDomNum = SNCA.NodeToInfo[SNCA.NumToNode[WInfo.Semi]].DFSNum;
+      const NodePtr W = NumToNode[i];
+      auto &WInfo = NodeToInfo[W];
+      const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
       NodePtr WIDomCandidate = WInfo.IDom;
-    while (SNCA.NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
-      WIDomCandidate = SNCA.NodeToInfo[WIDomCandidate].IDom;
+      while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
+        WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
 
       WInfo.IDom = WIDomCandidate;
     }
 
     if (DT.Roots.empty()) return;
 
     // Add a node for the root.  This node might be the actual root, if there is
-  // one exit block, or it may be the virtual exit (denoted by (BasicBlock *)0)
-  // which postdominates all real exits if there are multiple exit blocks, or
-  // an infinite loop.
+    // one exit block, or it may be the virtual exit (denoted by
+    // (BasicBlock *)0) which postdominates all real exits if there are multiple
+    // exit blocks, or an infinite loop.
     NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 
     DT.RootNode =
         (DT.DomTreeNodes[Root] =
-           llvm::make_unique<DomTreeNodeBase<NodeType>>(Root, nullptr))
+             llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
             .get();
 
     // Loop over all of the reachable blocks in the function...
     for (unsigned i = 2; i <= N; ++i) {
-    NodePtr W = SNCA.NumToNode[i];
+      NodePtr W = NumToNode[i];
 
       // Don't replace this with 'count', the insertion side effect is important
       if (DT.DomTreeNodes[W])
         continue; // Haven't calculated this node yet?
 
-    NodePtr ImmDom = SNCA.getIDom(W);
+      NodePtr ImmDom = getIDom(W);
 
       assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
       // Get or calculate the node for the immediate dominator
-    DomTreeNodeBase<NodeType> *IDomNode = SNCA.getNodeForBlock(ImmDom);
+      TreeNodePtr IDomNode = getNodeForBlock(ImmDom);
 
       // Add a new tree node for this BasicBlock, and link it as a child of
       // IDomNode
       DT.DomTreeNodes[W] = IDomNode->addChild(
-        llvm::make_unique<DomTreeNodeBase<NodeType>>(W, IDomNode));
+          llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
     }
 
     DT.updateDFSNumbers();
   }
-} // namespace DomTreeBuilder
+};
+}  // namespace DomTreeBuilder
 
+template <class FuncT, class NodeT>
+void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
+               FuncT &F) {
+  using NodePtr = typename GraphTraits<NodeT>::NodeRef;
+  static_assert(std::is_pointer<NodePtr>::value,
+                "NodePtr should be a pointer type");
+
+  DomTreeBuilder::SemiNCAInfo<typename std::remove_pointer<NodePtr>::type>
+      SNCA(DT);
+  SNCA.template runSemiNCA<NodeT>(GraphTraits<FuncT *>::size(&F));
+}
+}  // namespace llvm
+
 #endif