[Dominators] Move SemiNCAInfo and helper functions out of DominatorTreeBase

[kuhar]

Summary

This moves SemiNCAInfo from DeminatorTreeBase to GenericDomTreeConstruction. It also put helper functions used during tree constructions in the same file.

The point of this change is to further clean up DominatorTreeBase and make it easier to construct and verify (in future patches).

[kuhar]

Also hoist running Semi-NCA out of Calculate.

[kuhar]

Revert to old patch -- the previous update was meant to be sent to a different revision.

[• dberlin]

I would just name the namespace seminca or something
detail is a random generic name :)

[• dberlin]

Fine once namespace is renamed

[kuhar]

Rename the namespace detail to DomTreeBuilder

include/llvm/Support/GenericDomTree.h

void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
                   unsigned Lev) {
   O.indent(2 * Lev) << "[" << Lev << "] " << N;
   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
                                                        E = N->end();
        I != E; ++I)
     PrintDomTree<NodeT>(*I, O, Lev + 1);
 }
 
+namespace detail {
+template <class NodeT>
+struct SemiNCAInfo;
+}  // namespace detail
+
 // The calculate routine is provided in a separate header but referenced here.
 template <class FuncT, class N>
 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F);
 
 /// \brief Core dominator tree base class.
 ///
 /// This class is a generic template over graph nodes. It is instantiated for
 /// various graphs in the LLVM IR or in the code generator.
if (!DFSInfoValid)
       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     O << "\n";
 
     // The postdom tree can have a null root if there are no returns.
     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
   }
 
 protected:
-  // Information record used by Semi-NCA during tree construction.
-  struct SemiNCAInfo {
-    using NodePtr = NodeT *;
-    struct InfoRec {
-      unsigned DFSNum = 0;
-      unsigned Parent = 0;
-      unsigned Semi = 0;
-      NodePtr Label = nullptr;
-      NodePtr IDom = nullptr;
-    };
-
-    std::vector<NodePtr> NumToNode;
-    DenseMap<NodePtr, InfoRec> NodeToInfo;
-
-    NodeT *getIDom(NodeT *BB) const {
-      auto InfoIt = NodeToInfo.find(BB);
-      if (InfoIt == NodeToInfo.end()) return nullptr;
-
-      return InfoIt->second.IDom;
-    }
-  };
-
-  template <class GraphT>
-  friend typename GraphT::NodeRef Eval(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned LastLinked);
-
-  template <class GraphT>
-  friend unsigned ReverseDFSPass(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned N);
-
-  template <class GraphT>
-  friend unsigned DFSPass(
-      DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-      typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &Info,
-      unsigned N);
+ friend struct detail::SemiNCAInfo<NodeT>;
+ using SNCAInfoTy = detail::SemiNCAInfo<NodeT>;
 
-  template <class FuncT, class N>
-  friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
+ template <class FuncT, class NodeTy>
+ friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeTy>> &DT,
                        FuncT &F);
 
-  DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB,
-                                          const SemiNCAInfo& SNCAInfo) {
-    if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
-      return Node;
-
-    // Haven't calculated this node yet?  Get or calculate the node for the
-    // immediate dominator.
-    NodeT *IDom = SNCAInfo.getIDom(BB);
-
-    assert(IDom || DomTreeNodes[nullptr]);
-    DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom, SNCAInfo);
-
-    // Add a new tree node for this NodeT, and link it as a child of
-    // IDomNode
-    return (DomTreeNodes[BB] = IDomNode->addChild(
-                llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
-  }
-
-  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;

include/llvm/Support/GenericDomTreeConstruction.h

 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
+namespace detail {
+// Information record used by Semi-NCA during tree construction.
+template <typename NodeT>
+struct SemiNCAInfo {
+  using NodePtr = NodeT *;
+  using DomTreeT = DominatorTreeBase<NodeT>;
+  using TreeNodePtr = DomTreeNodeBase<NodeT> *;
+
+  struct InfoRec {
+    unsigned DFSNum = 0;
+    unsigned Parent = 0;
+    unsigned Semi = 0;
+    NodePtr Label = nullptr;
+    NodePtr IDom = nullptr;
+  };
+
+  DomTreeT &DT;
+  std::vector<NodePtr> NumToNode;
+  DenseMap<NodePtr, InfoRec> NodeToInfo;
+
+  SemiNCAInfo(DomTreeT &DT) : DT(DT) {}
+
+  NodePtr getIDom(NodePtr BB) const {
+    auto InfoIt = NodeToInfo.find(BB);
+    if (InfoIt == NodeToInfo.end()) return nullptr;
+
+    return InfoIt->second.IDom;
+  }
+
+  TreeNodePtr getNodeForBlock(NodePtr BB) {
+    if (TreeNodePtr Node = DT.getNode(BB)) return Node;
+
+    // Haven't calculated this node yet?  Get or calculate the node for the
+    // immediate dominator.
+    NodePtr IDom = getIDom(BB);
+
+    assert(IDom || DT.DomTreeNodes[nullptr]);
+    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 detail
+
 // 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
 // converting the one argument insert calls.
 template <class NodeRef, class InfoType> struct df_iterator_dom_storage {
 public:
   using BaseSet = DenseMap<NodeRef, InfoType>;
   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()});
   }
   void completed(NodeRef) {}
 
 private:
   BaseSet &Storage;
 };
 
-template <class GraphT>
-unsigned ReverseDFSPass(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+unsigned ReverseDFSPass(NodePtr V, detail::SemiNCAInfo<NodeT> &SNCA,
                         unsigned N) {
-  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
-  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
-      typename SNCAInfoTy::InfoRec>
-      DFStorage(SNCA.NodeToInfo);
+  using SNCAInfoTy = detail::SemiNCAInfo<NodeT>;
+  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
+      SNCA.NodeToInfo);
 
   bool IsChildOfArtificialExit = (N != 0);
   for (auto I = idf_ext_begin(V, DFStorage), E = idf_ext_end(V, DFStorage);
        I != E; ++I) {
-    typename GraphT::NodeRef BB = *I;
+    NodePtr BB = *I;
     auto &BBInfo = SNCA.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;
 
     if (IsChildOfArtificialExit)
       BBInfo.Parent = 1;
 
     IsChildOfArtificialExit = false;
   }
   return N;
 }
-template <class GraphT>
-unsigned DFSPass(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
-    unsigned N) {
-  using SNCAInfoTy = typename std::remove_reference<decltype(SNCA)>::type;
-  df_iterator_dom_storage<typename SNCAInfoTy::NodePtr,
-      typename SNCAInfoTy::InfoRec>
-      DFStorage(SNCA.NodeToInfo);
+
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+unsigned DFSPass(NodePtr V, detail::SemiNCAInfo<NodeT> &SNCA, unsigned N) {
+  using SNCAInfoTy = detail::SemiNCAInfo<NodeT>;
+  df_iterator_dom_storage<NodePtr, typename SNCAInfoTy::InfoRec> DFStorage(
+      SNCA.NodeToInfo);
+
   for (auto I = df_ext_begin(V, DFStorage), E = df_ext_end(V, DFStorage);
        I != E; ++I) {
-    typename GraphT::NodeRef BB = *I;
+    NodePtr BB = *I;
     auto &BBInfo = SNCA.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;
   }
   return N;
 }
 
-template <class GraphT>
-typename GraphT::NodeRef Eval(
-    DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef VIn,
-    typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo &SNCA,
+template <class NodePtr,
+          class NodeT = typename std::remove_pointer<NodePtr>::type>
+NodePtr Eval(NodePtr VIn, detail::SemiNCAInfo<NodeT> &SNCA,
              unsigned LastLinked) {
-  using NodePtr = typename GraphT::NodeRef;
-
   auto &VInInfo = SNCA.NodeToInfo[VIn];
   if (VInInfo.DFSNum < LastLinked)
     return VIn;
 
   SmallVector<NodePtr, 32> Work;
   SmallPtrSet<NodePtr, 32> Visited;
 
   if (VInInfo.Parent >= LastLinked)

 }
 
 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,
-                "NodeRef should be pointer type");
+                "NodePtr should be a pointer type");
   using NodeType = typename std::remove_pointer<NodePtr>::type;
 
   unsigned N = 0;
-  typename DominatorTreeBaseByGraphTraits<GraphT>::SemiNCAInfo SNCA;
+  detail::SemiNCAInfo<NodeType> SNCA(DT);
   SNCA.NumToNode.push_back(nullptr);
 
   bool MultipleRoots = (DT.Roots.size() > 1);
   if (MultipleRoots) {
     auto &BBInfo = SNCA.NodeToInfo[nullptr];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = nullptr;
 
     SNCA.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<GraphT>(DT, DT.Roots[i], SNCA, N);
+      N = ReverseDFSPass<NodePtr>(DT.Roots[i], SNCA, N);
   } else {
-    N = DFSPass<GraphT>(DT, DT.Roots[0], SNCA, N);
+    N = DFSPass<NodePtr>(DT.Roots[0], SNCA, 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));
 
   // 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];
   }
 
   // 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];
 
     // 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<GraphT>(DT, N, SNCA, i + 1)].Semi;
+        unsigned SemiU = SNCA.NodeToInfo[Eval<NodePtr>(N, SNCA, 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
for (unsigned i = 2; i <= N; ++i) {
     if (DT.DomTreeNodes[W])
       continue; // Haven't calculated this node yet?
 
     NodePtr ImmDom = SNCA.getIDom(W);
 
     assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
     // Get or calculate the node for the immediate dominator
-    DomTreeNodeBase<NodeType> *IDomNode = DT.getNodeForBlock(ImmDom, SNCA);
+    DomTreeNodeBase<NodeType> *IDomNode = SNCA.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));
   }
 
   DT.updateDFSNumbers();
 }
 }
 
 #endif