[ADT] NFC: Generalize GraphTraits requirement of "NodeType *" in interfaces to "NodeRef", and migrate SCCIterator.h to use NodeRef

[timshen]

Summary

By generalize the interface, users are able to inject more flexible Node token into the algorithm, for example, a pair of vector<Node>* and index integer. Currently I only migrated SCCIterator to use NodeRef, but more is coming. It's a NFC.

include/llvm/ADT/GraphTraits.h

 
 // GraphTraits - This class should be specialized by different graph types...
 // which is why the default version is empty.
 //
 template<class GraphType>
 struct GraphTraits {
   // Elements to provide:
 
+  // NOTICE: We are in a transition from migration interfaces that require
+  // NodeType *, to NodeRef. NodeRef is required to be cheap to copy, but does
+  // not have to be a raw pointer. In the transition, user should define
+  // NodeType, and NodeRef = NodeType *.
+  //
   // typedef NodeType          - Type of Node in the graph
+  // typedef NodeRef           - NodeType *
   // typedef ChildIteratorType - Type used to iterate over children in graph
 
-  // static NodeType *getEntryNode(const GraphType &)
+  // static NodeRef getEntryNode(const GraphType &)
   //    Return the entry node of the graph
 
-  // static ChildIteratorType child_begin(NodeType *)
-  // static ChildIteratorType child_end  (NodeType *)
+  // static ChildIteratorType child_begin(NodeRef)
+  // static ChildIteratorType child_end  (NodeRef)
   //    Return iterators that point to the beginning and ending of the child
   //    node list for the specified node.
   //
 
-
   // typedef  ...iterator nodes_iterator;
   // static nodes_iterator nodes_begin(GraphType *G)
   // static nodes_iterator nodes_end  (GraphType *G)
   //    nodes_iterator/begin/end - Allow iteration over all nodes in the graph
 
   // static unsigned       size       (GraphType *G)
   //    Return total number of nodes in the graph
   //
 
 
   // If anyone tries to use this class without having an appropriate
   // specialization, make an error.  If you get this error, it's because you
   // need to include the appropriate specialization of GraphTraits<> for your
   // graph, or you need to define it for a new graph type. Either that or
   // your argument to XXX_begin(...) is unknown or needs to have the proper .h
   // file #include'd.
   //
-  typedef typename GraphType::UnknownGraphTypeError NodeType;
+  typedef typename GraphType::UnknownGraphTypeError NodeRef;
 };
 
 
 // Inverse - This class is used as a little marker class to tell the graph
 // iterator to iterate over the graph in a graph defined "Inverse" ordering.
 // Not all graphs define an inverse ordering, and if they do, it depends on
 // the graph exactly what that is.  Here's an example of usage with the
 // df_iterator:

include/llvm/ADT/SCCIterator.h

 
 /// \brief Enumerate the SCCs of a directed graph in reverse topological order
 /// of the SCC DAG.
 ///
 /// This is implemented using Tarjan's DFS algorithm using an internal stack to
 /// build up a vector of nodes in a particular SCC. Note that it is a forward
 /// iterator and thus you cannot backtrack or re-visit nodes.
 template <class GraphT, class GT = GraphTraits<GraphT>>
-class scc_iterator
-    : public iterator_facade_base<
+class scc_iterator : public iterator_facade_base<
                          scc_iterator<GraphT, GT>, std::forward_iterator_tag,
-          const std::vector<typename GT::NodeType *>, ptrdiff_t> {
-  typedef typename GT::NodeType NodeType;
+                         const std::vector<typename GT::NodeRef>, ptrdiff_t> {
+  typedef typename GT::NodeRef NodeRef;
   typedef typename GT::ChildIteratorType ChildItTy;
-  typedef std::vector<NodeType *> SccTy;
+  typedef std::vector<NodeRef> SccTy;
   typedef typename scc_iterator::reference reference;
 
   /// Element of VisitStack during DFS.
   struct StackElement {
-    NodeType *Node;       ///< The current node pointer.
+    NodeRef Node;         ///< The current node pointer.
     ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
     unsigned MinVisited;  ///< Minimum uplink value of all children of Node.
 
-    StackElement(NodeType *Node, const ChildItTy &Child, unsigned Min)
+    StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
         : Node(Node), NextChild(Child), MinVisited(Min) {}
 
     bool operator==(const StackElement &Other) const {
       return Node == Other.Node &&
              NextChild == Other.NextChild &&
              MinVisited == Other.MinVisited;
     }
   };
 
   /// The visit counters used to detect when a complete SCC is on the stack.
   /// visitNum is the global counter.
   ///
   /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
   unsigned visitNum;
-  DenseMap<NodeType *, unsigned> nodeVisitNumbers;
+  DenseMap<NodeRef, unsigned> nodeVisitNumbers;
 
   /// Stack holding nodes of the SCC.
-  std::vector<NodeType *> SCCNodeStack;
+  std::vector<NodeRef> SCCNodeStack;
 
   /// The current SCC, retrieved using operator*().
   SccTy CurrentSCC;
 
   /// DFS stack, Used to maintain the ordering.  The top contains the current
   /// node, the next child to visit, and the minimum uplink value of all child
   std::vector<StackElement> VisitStack;
 
   /// A single "visit" within the non-recursive DFS traversal.
-  void DFSVisitOne(NodeType *N);
+  void DFSVisitOne(NodeRef N);
 
   /// The stack-based DFS traversal; defined below.
   void DFSVisitChildren();
 
   /// Compute the next SCC using the DFS traversal.
   void GetNextSCC();
 
-  scc_iterator(NodeType *entryN) : visitNum(0) {
+  scc_iterator(NodeRef entryN) : visitNum(0) {
     DFSVisitOne(entryN);
     GetNextSCC();
   }
 
   /// End is when the DFS stack is empty.
   scc_iterator() {}
 
 public:
public:
   /// \brief Test if the current SCC has a loop.
   ///
   /// If the SCC has more than one node, this is trivially true.  If not, it may
   /// still contain a loop if the node has an edge back to itself.
   bool hasLoop() const;
 
   /// This informs the \c scc_iterator that the specified \c Old node
   /// has been deleted, and \c New is to be used in its place.
-  void ReplaceNode(NodeType *Old, NodeType *New) {
+  void ReplaceNode(NodeRef Old, NodeRef New) {
     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     nodeVisitNumbers[New] = nodeVisitNumbers[Old];
     nodeVisitNumbers.erase(Old);
   }
 };
 
 template <class GraphT, class GT>
-void scc_iterator<GraphT, GT>::DFSVisitOne(NodeType *N) {
+void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
   ++visitNum;
   nodeVisitNumbers[N] = visitNum;
   SCCNodeStack.push_back(N);
   VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
 #if 0 // Enable if needed when debugging.
   dbgs() << "TarjanSCC: Node " << N <<
         " : visitNum = " << visitNum << "\n";
 #endif
 }
 
 template <class GraphT, class GT>
 void scc_iterator<GraphT, GT>::DFSVisitChildren() {
   assert(!VisitStack.empty());
   while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
     // TOS has at least one more child so continue DFS
-    NodeType *childN = *VisitStack.back().NextChild++;
-    typename DenseMap<NodeType *, unsigned>::iterator Visited =
+    NodeRef childN = *VisitStack.back().NextChild++;
+    typename DenseMap<NodeRef, unsigned>::iterator Visited =
         nodeVisitNumbers.find(childN);
     if (Visited == nodeVisitNumbers.end()) {
       // this node has never been seen.
       DFSVisitOne(childN);
       continue;
     }
 
     unsigned childNum = Visited->second;
     if (VisitStack.back().MinVisited > childNum)
       VisitStack.back().MinVisited = childNum;
   }
 }
 
 template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
   CurrentSCC.clear(); // Prepare to compute the next SCC
   while (!VisitStack.empty()) {
     DFSVisitChildren();
 
     // Pop the leaf on top of the VisitStack.
-    NodeType *visitingN = VisitStack.back().Node;
+    NodeRef visitingN = VisitStack.back().Node;
     unsigned minVisitNum = VisitStack.back().MinVisited;
     assert(VisitStack.back().NextChild == GT::child_end(visitingN));
     VisitStack.pop_back();
 
     // Propagate MinVisitNum to parent so we can detect the SCC starting node.
     if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)
       VisitStack.back().MinVisited = minVisitNum;
 
#endif
   }
 }
 
 template <class GraphT, class GT>
 bool scc_iterator<GraphT, GT>::hasLoop() const {
     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     if (CurrentSCC.size() > 1)
       return true;
-    NodeType *N = CurrentSCC.front();
+    NodeRef N = CurrentSCC.front();
     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
          ++CI)
       if (*CI == N)
         return true;
     return false;
   }
 
 /// \brief Construct the begin iterator for a deduced graph type T.

include/llvm/Analysis/CallGraph.h

 // GraphTraits specializations for call graphs so that they can be treated as
 // graphs by the generic graph algorithms.
 //
 
 // Provide graph traits for tranversing call graphs using standard graph
 // traversals.
 template <> struct GraphTraits<CallGraphNode *> {
   typedef CallGraphNode NodeType;
+  typedef CallGraphNode *NodeRef;
 
   typedef CallGraphNode::CallRecord CGNPairTy;
   typedef std::pointer_to_unary_function<CGNPairTy, CallGraphNode *>
   CGNDerefFun;
 
   static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
 
   typedef mapped_iterator<NodeType::iterator, CGNDerefFun> ChildIteratorType;
 
   static inline ChildIteratorType child_begin(NodeType *N) {
     return map_iterator(N->begin(), CGNDerefFun(CGNDeref));
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return map_iterator(N->end(), CGNDerefFun(CGNDeref));
   }
 
   static CallGraphNode *CGNDeref(CGNPairTy P) { return P.second; }
 };
 
 template <> struct GraphTraits<const CallGraphNode *> {
   typedef const CallGraphNode NodeType;
+  typedef const CallGraphNode *NodeRef;
 
   typedef CallGraphNode::CallRecord CGNPairTy;
   typedef std::pointer_to_unary_function<CGNPairTy, const CallGraphNode *>
       CGNDerefFun;
 
   static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
 
   typedef mapped_iterator<NodeType::const_iterator, CGNDerefFun>

include/llvm/CodeGen/MachineBasicBlock.h

 //===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a
 // MachineFunction as a graph of MachineBasicBlocks.
 //
 
 template <> struct GraphTraits<MachineBasicBlock *> {
   typedef MachineBasicBlock NodeType;
+  typedef MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::succ_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->succ_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->succ_end();
   }
 };
 
 template <> struct GraphTraits<const MachineBasicBlock *> {
   typedef const MachineBasicBlock NodeType;
+  typedef const MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->succ_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->succ_end();
   }
 };
 
 // Provide specializations of GraphTraits to be able to treat a
 // MachineFunction as a graph of MachineBasicBlocks and to walk it
 // in inverse order.  Inverse order for a function is considered
 // to be when traversing the predecessor edges of a MBB
 // instead of the successor edges.
 //
 template <> struct GraphTraits<Inverse<MachineBasicBlock*> > {
   typedef MachineBasicBlock NodeType;
+  typedef MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::pred_iterator ChildIteratorType;
   static NodeType *getEntryNode(Inverse<MachineBasicBlock *> G) {
     return G.Graph;
   }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->pred_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->pred_end();
   }
 };
 
 template <> struct GraphTraits<Inverse<const MachineBasicBlock*> > {
   typedef const MachineBasicBlock NodeType;
+  typedef const MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::const_pred_iterator ChildIteratorType;
   static NodeType *getEntryNode(Inverse<const MachineBasicBlock*> G) {
     return G.Graph;
   }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->pred_begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {

include/llvm/IR/CFG.h

 // GraphTraits specializations for basic block graphs (CFGs)
 //===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks...
 
 template <> struct GraphTraits<BasicBlock*> {
   typedef BasicBlock NodeType;
+  typedef BasicBlock *NodeRef;
   typedef succ_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(BasicBlock *BB) { return BB; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return succ_begin(N);
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return succ_end(N);
   }
 };
 
 template <> struct GraphTraits<const BasicBlock*> {
   typedef const BasicBlock NodeType;
+  typedef const BasicBlock *NodeRef;
   typedef succ_const_iterator ChildIteratorType;
 
   static NodeType *getEntryNode(const BasicBlock *BB) { return BB; }
 
   static inline ChildIteratorType child_begin(NodeType *N) {
     return succ_begin(N);
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return succ_end(N);
   }
 };
 
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
 // a function is considered to be when traversing the predecessor edges of a BB
 // instead of the successor edges.
 //
 template <> struct GraphTraits<Inverse<BasicBlock*> > {
   typedef BasicBlock NodeType;
+  typedef BasicBlock *NodeRef;
   typedef pred_iterator ChildIteratorType;
   static NodeType *getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return pred_begin(N);
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return pred_end(N);
   }
 };
 
 template <> struct GraphTraits<Inverse<const BasicBlock*> > {
   typedef const BasicBlock NodeType;
+  typedef const BasicBlock *NodeRef;
   typedef const_pred_iterator ChildIteratorType;
   static NodeType *getEntryNode(Inverse<const BasicBlock*> G) {
     return G.Graph;
   }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return pred_begin(N);
   }
   static inline ChildIteratorType child_end(NodeType *N) {

lib/Analysis/BlockFrequencyInfoImpl.cpp

void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ,
   ++SuccIrr.NumIn;
 }
 
 namespace llvm {
 template <> struct GraphTraits<IrreducibleGraph> {
   typedef bfi_detail::IrreducibleGraph GraphT;
 
   typedef const GraphT::IrrNode NodeType;
+  typedef const GraphT::IrrNode *NodeRef;
   typedef GraphT::IrrNode::iterator ChildIteratorType;
 
   static const NodeType *getEntryNode(const GraphT &G) {
     return G.StartIrr;
   }
   static ChildIteratorType child_begin(NodeType *N) { return N->succ_begin(); }
   static ChildIteratorType child_end(NodeType *N) { return N->succ_end(); }
 };

lib/Transforms/IPO/FunctionAttrs.cpp

struct ArgumentUsesTracker : public CaptureTracker {
 
   const SCCNodeSet &SCCNodes;
 };
 }
 
 namespace llvm {
 template <> struct GraphTraits<ArgumentGraphNode *> {
   typedef ArgumentGraphNode NodeType;
+  typedef ArgumentGraphNode *NodeRef;
   typedef SmallVectorImpl<ArgumentGraphNode *>::iterator ChildIteratorType;
 
   static inline NodeType *getEntryNode(NodeType *A) { return A; }
   static inline ChildIteratorType child_begin(NodeType *N) {
     return N->Uses.begin();
   }
   static inline ChildIteratorType child_end(NodeType *N) {
     return N->Uses.end();

unittests/ADT/SCCIteratorTest.cpp

public:
   static ChildIterator child_end(NodeType *Parent) {
     return ChildIterator(Parent - Parent->first, NodeSubset());
   }
 };
 
 template <unsigned N>
 struct GraphTraits<Graph<N> > {
   typedef typename Graph<N>::NodeType NodeType;
+  typedef typename Graph<N>::NodeType *NodeRef;
   typedef typename Graph<N>::ChildIterator ChildIteratorType;
 
  static inline NodeType *getEntryNode(const Graph<N> &G) { return G.AccessNode(0); }
  static inline ChildIteratorType child_begin(NodeType *Node) {
    return Graph<N>::child_begin(Node);
  }
  static inline ChildIteratorType child_end(NodeType *Node) {
    return Graph<N>::child_end(Node);