Index: llvm/trunk/include/llvm/ADT/GraphTraits.h =================================================================== --- llvm/trunk/include/llvm/ADT/GraphTraits.h +++ llvm/trunk/include/llvm/ADT/GraphTraits.h @@ -27,19 +27,24 @@ 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) @@ -57,7 +62,7 @@ // 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; }; Index: llvm/trunk/include/llvm/ADT/SCCIterator.h =================================================================== --- llvm/trunk/include/llvm/ADT/SCCIterator.h +++ llvm/trunk/include/llvm/ADT/SCCIterator.h @@ -37,23 +37,22 @@ /// 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 scc_iterator - : public iterator_facade_base< - scc_iterator, std::forward_iterator_tag, - const std::vector, ptrdiff_t> { - typedef typename GT::NodeType NodeType; +class scc_iterator : public iterator_facade_base< + scc_iterator, std::forward_iterator_tag, + const std::vector, ptrdiff_t> { + typedef typename GT::NodeRef NodeRef; typedef typename GT::ChildIteratorType ChildItTy; - typedef std::vector SccTy; + typedef std::vector 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) - : Node(Node), NextChild(Child), MinVisited(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 && @@ -67,10 +66,10 @@ /// /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags. unsigned visitNum; - DenseMap nodeVisitNumbers; + DenseMap nodeVisitNumbers; /// Stack holding nodes of the SCC. - std::vector SCCNodeStack; + std::vector SCCNodeStack; /// The current SCC, retrieved using operator*(). SccTy CurrentSCC; @@ -80,7 +79,7 @@ std::vector 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(); @@ -88,7 +87,7 @@ /// 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(); } @@ -131,7 +130,7 @@ /// 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); @@ -139,7 +138,7 @@ }; template -void scc_iterator::DFSVisitOne(NodeType *N) { +void scc_iterator::DFSVisitOne(NodeRef N) { ++visitNum; nodeVisitNumbers[N] = visitNum; SCCNodeStack.push_back(N); @@ -155,8 +154,8 @@ 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::iterator Visited = + NodeRef childN = *VisitStack.back().NextChild++; + typename DenseMap::iterator Visited = nodeVisitNumbers.find(childN); if (Visited == nodeVisitNumbers.end()) { // this node has never been seen. @@ -176,7 +175,7 @@ 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(); @@ -212,7 +211,7 @@ 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) Index: llvm/trunk/include/llvm/Analysis/CallGraph.h =================================================================== --- llvm/trunk/include/llvm/Analysis/CallGraph.h +++ llvm/trunk/include/llvm/Analysis/CallGraph.h @@ -410,6 +410,7 @@ // traversals. template <> struct GraphTraits { typedef CallGraphNode NodeType; + typedef CallGraphNode *NodeRef; typedef CallGraphNode::CallRecord CGNPairTy; typedef std::pointer_to_unary_function @@ -431,6 +432,7 @@ template <> struct GraphTraits { typedef const CallGraphNode NodeType; + typedef const CallGraphNode *NodeRef; typedef CallGraphNode::CallRecord CGNPairTy; typedef std::pointer_to_unary_function Index: llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h +++ llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h @@ -740,6 +740,7 @@ template <> struct GraphTraits { typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock *NodeRef; typedef MachineBasicBlock::succ_iterator ChildIteratorType; static NodeType *getEntryNode(MachineBasicBlock *BB) { return BB; } @@ -753,6 +754,7 @@ template <> struct GraphTraits { typedef const MachineBasicBlock NodeType; + typedef const MachineBasicBlock *NodeRef; typedef MachineBasicBlock::const_succ_iterator ChildIteratorType; static NodeType *getEntryNode(const MachineBasicBlock *BB) { return BB; } @@ -772,6 +774,7 @@ // template <> struct GraphTraits > { typedef MachineBasicBlock NodeType; + typedef MachineBasicBlock *NodeRef; typedef MachineBasicBlock::pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse G) { return G.Graph; @@ -786,6 +789,7 @@ template <> struct GraphTraits > { typedef const MachineBasicBlock NodeType; + typedef const MachineBasicBlock *NodeRef; typedef MachineBasicBlock::const_pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse G) { return G.Graph; Index: llvm/trunk/include/llvm/IR/CFG.h =================================================================== --- llvm/trunk/include/llvm/IR/CFG.h +++ llvm/trunk/include/llvm/IR/CFG.h @@ -155,6 +155,7 @@ template <> struct GraphTraits { typedef BasicBlock NodeType; + typedef BasicBlock *NodeRef; typedef succ_iterator ChildIteratorType; static NodeType *getEntryNode(BasicBlock *BB) { return BB; } @@ -168,6 +169,7 @@ template <> struct GraphTraits { typedef const BasicBlock NodeType; + typedef const BasicBlock *NodeRef; typedef succ_const_iterator ChildIteratorType; static NodeType *getEntryNode(const BasicBlock *BB) { return BB; } @@ -187,6 +189,7 @@ // template <> struct GraphTraits > { typedef BasicBlock NodeType; + typedef BasicBlock *NodeRef; typedef pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse G) { return G.Graph; } static inline ChildIteratorType child_begin(NodeType *N) { @@ -199,6 +202,7 @@ template <> struct GraphTraits > { typedef const BasicBlock NodeType; + typedef const BasicBlock *NodeRef; typedef const_pred_iterator ChildIteratorType; static NodeType *getEntryNode(Inverse G) { return G.Graph; Index: llvm/trunk/lib/Analysis/BlockFrequencyInfoImpl.cpp =================================================================== --- llvm/trunk/lib/Analysis/BlockFrequencyInfoImpl.cpp +++ llvm/trunk/lib/Analysis/BlockFrequencyInfoImpl.cpp @@ -623,6 +623,7 @@ 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) { Index: llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp +++ llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp @@ -333,6 +333,7 @@ namespace llvm { template <> struct GraphTraits { typedef ArgumentGraphNode NodeType; + typedef ArgumentGraphNode *NodeRef; typedef SmallVectorImpl::iterator ChildIteratorType; static inline NodeType *getEntryNode(NodeType *A) { return A; } Index: llvm/trunk/unittests/ADT/SCCIteratorTest.cpp =================================================================== --- llvm/trunk/unittests/ADT/SCCIteratorTest.cpp +++ llvm/trunk/unittests/ADT/SCCIteratorTest.cpp @@ -230,6 +230,7 @@ template struct GraphTraits > { typedef typename Graph::NodeType NodeType; + typedef typename Graph::NodeType *NodeRef; typedef typename Graph::ChildIterator ChildIteratorType; static inline NodeType *getEntryNode(const Graph &G) { return G.AccessNode(0); }