[GenericDomTree] Change GenericDomTree to use NodeRef in GraphTraits. NFC.

[timshen]

Summary

Looking at the implementation, GenericDomTree has more specific
requirements on NodeRef, e.g. NodeRefObject->getParent() should compile,
and NodeRef should be a pointer. We can remove the pointer requirement,
but it seems to have little gain, given the limited use cases.

Also changed GraphTraits<Inverse<Inverse<T>> to be more accurate.

include/llvm/ADT/GraphTraits.h

 struct Inverse {
   const GraphType &Graph;
 
   inline Inverse(const GraphType &G) : Graph(G) {}
 };
 
 // Provide a partial specialization of GraphTraits so that the inverse of an
 // inverse falls back to the original graph.
-template<class T>
-struct GraphTraits<Inverse<Inverse<T> > > {
-  typedef typename GraphTraits<T>::NodeType NodeType;
-  typedef typename GraphTraits<T>::ChildIteratorType ChildIteratorType;
-
-  static NodeType *getEntryNode(Inverse<Inverse<T> > *G) {
-    return GraphTraits<T>::getEntryNode(G->Graph.Graph);
-  }
-
-  static ChildIteratorType child_begin(NodeType* N) {
-    return GraphTraits<T>::child_begin(N);
-  }
-
-  static ChildIteratorType child_end(NodeType* N) {
-    return GraphTraits<T>::child_end(N);
-  }
-};
+template <class T> struct GraphTraits<Inverse<Inverse<T>>> : GraphTraits<T> {};
 
 } // End llvm namespace
 
 #endif

include/llvm/IR/Dominators.h

 class Function;
 class BasicBlock;
 class raw_ostream;
 
 extern template class DomTreeNodeBase<BasicBlock>;
 extern template class DominatorTreeBase<BasicBlock>;
 
 extern template void Calculate<Function, BasicBlock *>(
-    DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT, Function &F);
+    DominatorTreeBaseByGraphTraits<GraphTraits<BasicBlock *>> &DT, Function &F);
 extern template void Calculate<Function, Inverse<BasicBlock *>>(
-    DominatorTreeBase<GraphTraits<Inverse<BasicBlock *>>::NodeType> &DT,
+    DominatorTreeBaseByGraphTraits<GraphTraits<Inverse<BasicBlock *>>> &DT,
     Function &F);
 
 typedef DomTreeNodeBase<BasicBlock> DomTreeNode;
 
 class BasicBlockEdge {
   const BasicBlock *Start;
   const BasicBlock *End;
 public:

include/llvm/Support/GenericDomTree.h

 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// This file defines a set of templates that efficiently compute a dominator
 /// tree over a generic graph. This is used typically in LLVM for fast
 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
 /// graph types.
 ///
+/// Unlike ADT/* graph algorithms, generic dominator tree has more reuiqrement
+/// on the graph's NodeRef. The NodeRef should be a pointer and, depending on
+/// the implementation, e.g. NodeRef->getParent() return the parent node.
+///
+/// FIXME: Maybe GenericDomTree needs a TreeTraits, instead of GraphTraits.
+///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
 #define LLVM_SUPPORT_GENERICDOMTREE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 namespace llvm {
 
+template <class NodeT> class DominatorTreeBase;
+
+namespace detail {
+
+template <typename GT> struct DominatorTreeBaseTraits {
+  static_assert(std::is_pointer<typename GT::NodeRef>::value,
+                "Currently NodeRef must be a pointer type.");
+  using type = DominatorTreeBase<
+      typename std::remove_pointer<typename GT::NodeRef>::type>;
+};
+
+} // End namespace detail
+
+template <typename GT>
+using DominatorTreeBaseByGraphTraits =
+    typename detail::DominatorTreeBaseTraits<GT>::type;
+
 /// \brief Base class that other, more interesting dominator analyses
 /// inherit from.
 template <class NodeT> class DominatorBase {
 protected:
   std::vector<NodeT *> Roots;
   bool IsPostDominators;
   explicit DominatorBase(bool isPostDom)
       : Roots(), IsPostDominators(isPostDom) {}
public:
   ///
   const std::vector<NodeT *> &getRoots() const { return Roots; }
 
   /// isPostDominator - Returns true if analysis based of postdoms
   ///
   bool isPostDominator() const { return IsPostDominators; }
 };
 
-template <class NodeT> class DominatorTreeBase;
 struct PostDominatorTree;
 
 /// \brief Base class for the actual dominator tree node.
 template <class NodeT> class DomTreeNodeBase {
   NodeT *TheBB;
   DomTreeNodeBase<NodeT> *IDom;
   std::vector<DomTreeNodeBase<NodeT> *> Children;
   mutable int DFSNumIn, DFSNumOut;
void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
                                                        E = N->end();
        I != E; ++I)
     PrintDomTree<NodeT>(*I, o, Lev + 1);
 }
 
 // The calculate routine is provided in a separate header but referenced here.
 template <class FuncT, class N>
-void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT,
-               FuncT &F);
+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.
 template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
   DominatorTreeBase(const DominatorTreeBase &) = delete;
   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
void reset() {
     RootNode = nullptr;
     DFSInfoValid = false;
     SlowQueries = 0;
   }
 
   // NewBB is split and now it has one successor. Update dominator tree to
   // reflect this change.
   template <class N, class GraphT>
-  void Split(DominatorTreeBase<typename GraphT::NodeType> &DT,
-             typename GraphT::NodeType *NewBB) {
+  void Split(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+             typename GraphT::NodeRef NewBB) {
     assert(std::distance(GraphT::child_begin(NewBB),
                          GraphT::child_end(NewBB)) == 1 &&
            "NewBB should have a single successor!");
-    typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB);
+    typename GraphT::NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
 
-    std::vector<typename GraphT::NodeType *> PredBlocks;
+    std::vector<typename GraphT::NodeRef> PredBlocks;
     typedef GraphTraits<Inverse<N>> InvTraits;
     for (typename InvTraits::ChildIteratorType
              PI = InvTraits::child_begin(NewBB),
              PE = InvTraits::child_end(NewBB);
          PI != PE; ++PI)
       PredBlocks.push_back(*PI);
 
     assert(!PredBlocks.empty() && "No predblocks?");
 
     bool NewBBDominatesNewBBSucc = true;
     for (typename InvTraits::ChildIteratorType
              PI = InvTraits::child_begin(NewBBSucc),
              E = InvTraits::child_end(NewBBSucc);
          PI != E; ++PI) {
-      typename InvTraits::NodeType *ND = *PI;
+      typename InvTraits::NodeRef ND = *PI;
       if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
           DT.isReachableFromEntry(ND)) {
         NewBBDominatesNewBBSucc = false;
         break;
       }
     }
 
     // Find NewBB's immediate dominator and create new dominator tree node for
void print(raw_ostream &o) const {
 
     // The postdom tree can have a null root if there are no returns.
     if (getRootNode())
       PrintDomTree<NodeT>(getRootNode(), o, 1);
   }
 
 protected:
   template <class GraphT>
-  friend typename GraphT::NodeType *
-  Eval(DominatorTreeBase<typename GraphT::NodeType> &DT,
-       typename GraphT::NodeType *V, unsigned LastLinked);
+  friend typename GraphT::NodeRef
+  Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V,
+       unsigned LastLinked);
 
   template <class GraphT>
-  friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT,
-                          typename GraphT::NodeType *V, unsigned N);
+  friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                          typename GraphT::NodeRef V, unsigned N);
 
   template <class FuncT, class N>
-  friend void
-  Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F);
-
+  friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT,
+                        FuncT &F);
 
   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
     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 = getIDom(BB);

include/llvm/Support/GenericDomTreeConstruction.h

 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
 
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/GenericDomTree.h"
 
 namespace llvm {
 
-template<class GraphT>
-unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType>& DT,
-                 typename GraphT::NodeType* V, unsigned N) {
+template <class GraphT>
+unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                 typename GraphT::NodeRef V, unsigned N) {
   // This is more understandable as a recursive algorithm, but we can't use the
   // recursive algorithm due to stack depth issues.  Keep it here for
   // documentation purposes.
 #if 0
   InfoRec &VInfo = DT.Info[DT.Roots[i]];
   VInfo.DFSNum = VInfo.Semi = ++N;
   VInfo.Label = V;
 
   Vertex.push_back(V);        // Vertex[n] = V;
 
   for (succ_iterator SI = succ_begin(V), E = succ_end(V); SI != E; ++SI) {
     InfoRec &SuccVInfo = DT.Info[*SI];
     if (SuccVInfo.Semi == 0) {
       SuccVInfo.Parent = V;
       N = DTDFSPass(DT, *SI, N);
     }
   }
 #else
   bool IsChildOfArtificialExit = (N != 0);
 
-  SmallVector<std::pair<typename GraphT::NodeType*,
-                        typename GraphT::ChildIteratorType>, 32> Worklist;
+  SmallVector<
+      std::pair<typename GraphT::NodeRef, typename GraphT::ChildIteratorType>,
+      32>
+      Worklist;
   Worklist.push_back(std::make_pair(V, GraphT::child_begin(V)));
   while (!Worklist.empty()) {
-    typename GraphT::NodeType* BB = Worklist.back().first;
+    typename GraphT::NodeRef BB = Worklist.back().first;
     typename GraphT::ChildIteratorType NextSucc = Worklist.back().second;
 
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
-                                                                    DT.Info[BB];
+    auto &BBInfo = DT.Info[BB];
 
     // First time we visited this BB?
     if (NextSucc == GraphT::child_begin(BB)) {
       BBInfo.DFSNum = BBInfo.Semi = ++N;
       BBInfo.Label = BB;
 
       DT.Vertex.push_back(BB);       // Vertex[n] = V;
 
if (NextSucc == GraphT::child_end(BB)) {
       Worklist.pop_back();
       continue;
     }
 
     // Increment the successor number for the next time we get to it.
     ++Worklist.back().second;
 
     // Visit the successor next, if it isn't already visited.
-    typename GraphT::NodeType* Succ = *NextSucc;
+    typename GraphT::NodeRef Succ = *NextSucc;
 
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &SuccVInfo =
-                                                                  DT.Info[Succ];
+    auto &SuccVInfo = DT.Info[Succ];
     if (SuccVInfo.Semi == 0) {
       SuccVInfo.Parent = BBDFSNum;
       Worklist.push_back(std::make_pair(Succ, GraphT::child_begin(Succ)));
     }
   }
 #endif
     return N;
 }
 
 template <class GraphT>
-typename GraphT::NodeType *
-Eval(DominatorTreeBase<typename GraphT::NodeType> &DT,
-     typename GraphT::NodeType *VIn, unsigned LastLinked) {
-  typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInInfo =
-                                                                  DT.Info[VIn];
+typename GraphT::NodeRef Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT,
+                              typename GraphT::NodeRef VIn,
+                              unsigned LastLinked) {
+  auto &VInInfo = DT.Info[VIn];
   if (VInInfo.DFSNum < LastLinked)
     return VIn;
 
-  SmallVector<typename GraphT::NodeType*, 32> Work;
-  SmallPtrSet<typename GraphT::NodeType*, 32> Visited;
+  SmallVector<typename GraphT::NodeRef, 32> Work;
+  SmallPtrSet<typename GraphT::NodeRef, 32> Visited;
 
   if (VInInfo.Parent >= LastLinked)
     Work.push_back(VIn);
 
   while (!Work.empty()) {
-    typename GraphT::NodeType* V = Work.back();
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VInfo =
-                                                                     DT.Info[V];
-    typename GraphT::NodeType* VAncestor = DT.Vertex[VInfo.Parent];
+    typename GraphT::NodeRef V = Work.back();
+    auto &VInfo = DT.Info[V];
+    typename GraphT::NodeRef VAncestor = DT.Vertex[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;
 
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &VAInfo =
-                                                             DT.Info[VAncestor];
-    typename GraphT::NodeType* VAncestorLabel = VAInfo.Label;
-    typename GraphT::NodeType* VLabel = VInfo.Label;
+    auto &VAInfo = DT.Info[VAncestor];
+    typename GraphT::NodeRef VAncestorLabel = VAInfo.Label;
+    typename GraphT::NodeRef VLabel = VInfo.Label;
     if (DT.Info[VAncestorLabel].Semi < DT.Info[VLabel].Semi)
       VInfo.Label = VAncestorLabel;
     VInfo.Parent = VAInfo.Parent;
   }
 
   return VInInfo.Label;
 }
 
-template<class FuncT, class NodeT>
-void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT,
-               FuncT& F) {
+template <class FuncT, class NodeT>
+void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
+               FuncT &F) {
   typedef GraphTraits<NodeT> GraphT;
+  static_assert(std::is_pointer<typename GraphT::NodeRef>::value,
+                "NodeRef should be pointer type");
+  typedef typename std::remove_pointer<typename GraphT::NodeRef>::type NodeType;
 
   unsigned N = 0;
   bool MultipleRoots = (DT.Roots.size() > 1);
   if (MultipleRoots) {
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &BBInfo =
-        DT.Info[nullptr];
+    auto &BBInfo = DT.Info[nullptr];
     BBInfo.DFSNum = BBInfo.Semi = ++N;
     BBInfo.Label = nullptr;
 
     DT.Vertex.push_back(nullptr);       // Vertex[n] = V;
   }
 
   // Step #1: Number blocks in depth-first order and initialize variables used
   // in later stages of the algorithm.
void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
   // bucket is processed, Buckets[i] stores the index of the next element in the
   // bucket containing V, if any.
   SmallVector<unsigned, 32> Buckets;
   Buckets.resize(N + 1);
   for (unsigned i = 1; i <= N; ++i)
     Buckets[i] = i;
 
   for (unsigned i = N; i >= 2; --i) {
-    typename GraphT::NodeType* W = DT.Vertex[i];
-    typename DominatorTreeBase<typename GraphT::NodeType>::InfoRec &WInfo =
-                                                                     DT.Info[W];
+    typename GraphT::NodeRef W = DT.Vertex[i];
+    auto &WInfo = DT.Info[W];
 
     // Step #2: Implicitly define the immediate dominator of vertices
     for (unsigned j = i; Buckets[j] != i; j = Buckets[j]) {
-      typename GraphT::NodeType* V = DT.Vertex[Buckets[j]];
-      typename GraphT::NodeType* U = Eval<GraphT>(DT, V, i + 1);
+      typename GraphT::NodeRef V = DT.Vertex[Buckets[j]];
+      typename GraphT::NodeRef U = Eval<GraphT>(DT, V, i + 1);
       DT.IDoms[V] = DT.Info[U].Semi < i ? U : W;
     }
 
     // Step #3: Calculate the semidominators of all vertices
 
     // initialize the semi dominator to point to the parent node
     WInfo.Semi = WInfo.Parent;
     typedef GraphTraits<Inverse<NodeT> > InvTraits;
     for (typename InvTraits::ChildIteratorType CI =
          InvTraits::child_begin(W),
          E = InvTraits::child_end(W); CI != E; ++CI) {
-      typename InvTraits::NodeType *N = *CI;
+      typename InvTraits::NodeRef N = *CI;
       if (DT.Info.count(N)) {  // Only if this predecessor is reachable!
         unsigned SemiU = DT.Info[Eval<GraphT>(DT, N, i + 1)].Semi;
         if (SemiU < WInfo.Semi)
           WInfo.Semi = SemiU;
       }
     }
 
     // If V is a non-root vertex and sdom(V) = parent(V), then idom(V) is
     // necessarily parent(V). In this case, set idom(V) here and avoid placing
     // V into a bucket.
     if (WInfo.Semi == WInfo.Parent) {
       DT.IDoms[W] = DT.Vertex[WInfo.Parent];
     } else {
       Buckets[i] = Buckets[WInfo.Semi];
       Buckets[WInfo.Semi] = i;
     }
   }
 
   if (N >= 1) {
-    typename GraphT::NodeType* Root = DT.Vertex[1];
+    typename GraphT::NodeRef Root = DT.Vertex[1];
     for (unsigned j = 1; Buckets[j] != 1; j = Buckets[j]) {
-      typename GraphT::NodeType* V = DT.Vertex[Buckets[j]];
+      typename GraphT::NodeRef V = DT.Vertex[Buckets[j]];
       DT.IDoms[V] = Root;
     }
   }
 
   // Step #4: Explicitly define the immediate dominator of each vertex
   for (unsigned i = 2; i <= N; ++i) {
-    typename GraphT::NodeType* W = DT.Vertex[i];
-    typename GraphT::NodeType*& WIDom = DT.IDoms[W];
+    typename GraphT::NodeRef W = DT.Vertex[i];
+    typename GraphT::NodeRef &WIDom = DT.IDoms[W];
     if (WIDom != DT.Vertex[DT.Info[W].Semi])
       WIDom = DT.IDoms[WIDom];
   }
 
   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.
-  typename GraphT::NodeType* Root = !MultipleRoots ? DT.Roots[0] : nullptr;
+  typename GraphT::NodeRef Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 
   DT.RootNode =
       (DT.DomTreeNodes[Root] =
-           llvm::make_unique<DomTreeNodeBase<typename GraphT::NodeType>>(
-               Root, nullptr)).get();
+           llvm::make_unique<DomTreeNodeBase<NodeType>>(Root, nullptr))
+          .get();
 
   // Loop over all of the reachable blocks in the function...
   for (unsigned i = 2; i <= N; ++i) {
-    typename GraphT::NodeType* W = DT.Vertex[i];
+    typename GraphT::NodeRef W = DT.Vertex[i];
 
     // Don't replace this with 'count', the insertion side effect is important
     if (DT.DomTreeNodes[W])
       continue; // Haven't calculated this node yet?
 
-    typename GraphT::NodeType* ImmDom = DT.getIDom(W);
+    typename GraphT::NodeRef ImmDom = DT.getIDom(W);
 
     assert(ImmDom || DT.DomTreeNodes[nullptr]);
 
     // Get or calculate the node for the immediate dominator
-    DomTreeNodeBase<typename GraphT::NodeType> *IDomNode =
-                                                     DT.getNodeForBlock(ImmDom);
+    DomTreeNodeBase<NodeType> *IDomNode = DT.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<typename GraphT::NodeType>>(
-            W, IDomNode));
+        llvm::make_unique<DomTreeNodeBase<NodeType>>(W, IDomNode));
   }
 
   // Free temporary memory used to construct idom's
   DT.IDoms.clear();
   DT.Info.clear();
   DT.Vertex.clear();
   DT.Vertex.shrink_to_fit();
 
   DT.updateDFSNumbers();
 }
 }
 
 #endif

lib/IR/Dominators.cpp

 // GenericDomTreeConstruction.h.
 //
 //===----------------------------------------------------------------------===//
 
 template class llvm::DomTreeNodeBase<BasicBlock>;
 template class llvm::DominatorTreeBase<BasicBlock>;
 
 template void llvm::Calculate<Function, BasicBlock *>(
-    DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT, Function &F);
+    DominatorTreeBase<
+        typename std::remove_pointer<GraphTraits<BasicBlock *>::NodeRef>::type>
+        &DT,
+    Function &F);
 template void llvm::Calculate<Function, Inverse<BasicBlock *>>(
-    DominatorTreeBase<GraphTraits<Inverse<BasicBlock *>>::NodeType> &DT,
+    DominatorTreeBase<typename std::remove_pointer<
+        GraphTraits<Inverse<BasicBlock *>>::NodeRef>::type> &DT,
     Function &F);
 
 // dominates - Return true if Def dominates a use in User. This performs
 // the special checks necessary if Def and User are in the same basic block.
 // Note that Def doesn't dominate a use in Def itself!
 bool DominatorTree::dominates(const Instruction *Def,
                               const Instruction *User) const {
   const BasicBlock *UseBB = User->getParent();