[GraphTraits] Replace all NodeType usage with NodeRef

[timshen]

Summary

This should finish the GraphTraits migration.

[dblaikie]

Not all of these already had NodeRef implemented - that implies that some algorithms weren't using NodeRef before this change, or that these traits are unused? I thought the plan was to migrate each algorithm then just do a strict cleanup. Did that not pan out/some other aspects I'm forgetting?

llvm/trunk/include/llvm/CodeGen/ScheduleDAG.h

684–688

If you like you could probably (separate commit) drop the 'inline' from these functions, they're implicitly inline anyway

llvm/trunk/include/llvm/CodeGen/SelectionDAGNodes.h

2060–2064

and here

llvm/trunk/include/llvm/IR/CFG.h

161–164

And here.. and so on.

[timshen]

In D23730#522396, @dblaikie wrote:

Not all of these already had NodeRef implemented - that implies that some algorithms weren't using NodeRef before this change, or that these traits are unused? I thought the plan was to migrate each algorithm then just do a strict cleanup. Did that not pan out/some other aspects I'm forgetting?

I think those traits are unused. Notice that by merely removing "NodeType *" declarations, the build/tests doesn't break, so at least they are not covered by the tests.

llvm/trunk/include/llvm/CodeGen/ScheduleDAG.h

684–688

Sure, I can do that in a following patch.

[dblaikie]

In D23730#522501, @timshen wrote:

In D23730#522396, @dblaikie wrote:

Not all of these already had NodeRef implemented - that implies that some algorithms weren't using NodeRef before this change, or that these traits are unused? I thought the plan was to migrate each algorithm then just do a strict cleanup. Did that not pan out/some other aspects I'm forgetting?

I think those traits are unused. Notice that by merely removing "NodeType *" declarations, the build/tests doesn't break, so at least they are not covered by the tests.

I'd sort of be inclined to remove them, then - but I leave that up to you.

Otherwise this review is already approved, so commit as you see fit.

[dblaikie]

Or it isn't approved (was mixing up reviews) - but now it is...

[timshen]

In D23730#522537, @dblaikie wrote:

I'd sort of be inclined to remove them, then - but I leave that up to you.

It looks like people create some class, and add GraphTraits specialization for it, in the hope that others can use it, but didn't write a test. The right thing is to add the test, but I'm not going to be the one. :)

So I'll keep them.

cfe/trunk/include/clang/AST/StmtGraphTraits.h

 #include "llvm/ADT/GraphTraits.h"
 
 namespace llvm {
 
 //template <typename T> struct GraphTraits;
 
 
 template <> struct GraphTraits<clang::Stmt*> {
-  typedef clang::Stmt                       NodeType;
   typedef clang::Stmt *                     NodeRef;
   typedef clang::Stmt::child_iterator       ChildIteratorType;
   typedef llvm::df_iterator<clang::Stmt*>   nodes_iterator;
 
-  static NodeType* getEntryNode(clang::Stmt* S) { return S; }
+  static NodeRef getEntryNode(clang::Stmt *S) { return S; }
 
-  static inline ChildIteratorType child_begin(NodeType* N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     if (N) return N->child_begin();
     else return ChildIteratorType();
   }
 
-  static inline ChildIteratorType child_end(NodeType* N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     if (N) return N->child_end();
     else return ChildIteratorType();
   }
 
   static nodes_iterator nodes_begin(clang::Stmt* S) {
     return df_begin(S);
   }
 
   static nodes_iterator nodes_end(clang::Stmt* S) {
     return df_end(S);
   }
 };
 
 
 template <> struct GraphTraits<const clang::Stmt*> {
-  typedef const clang::Stmt                       NodeType;
   typedef const clang::Stmt *                     NodeRef;
   typedef clang::Stmt::const_child_iterator       ChildIteratorType;
   typedef llvm::df_iterator<const clang::Stmt*>   nodes_iterator;
 
-  static NodeType* getEntryNode(const clang::Stmt* S) { return S; }
+  static NodeRef getEntryNode(const clang::Stmt *S) { return S; }
 
-  static inline ChildIteratorType child_begin(NodeType* N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     if (N) return N->child_begin();
     else return ChildIteratorType();
   }
 
-  static inline ChildIteratorType child_end(NodeType* N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     if (N) return N->child_end();
     else return ChildIteratorType();
   }
 
   static nodes_iterator nodes_begin(const clang::Stmt* S) {
     return df_begin(S);
   }
 

cfe/trunk/include/clang/Analysis/Analyses/Dominators.h

 } // end namespace clang
 
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 namespace llvm {
 template <> struct GraphTraits< ::clang::DomTreeNode* > {
-  typedef ::clang::DomTreeNode NodeType;
   typedef ::clang::DomTreeNode *NodeRef;
-  typedef NodeType::iterator  ChildIteratorType;
+  typedef ::clang::DomTreeNode::iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(NodeType *N) {
-    return N;
-  }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->end();
-  }
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 
   typedef llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>
       nodes_iterator;
 
   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
     return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
     return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 
 template <> struct GraphTraits< ::clang::DominatorTree* >
   : public GraphTraits< ::clang::DomTreeNode* > {
-  static NodeType *getEntryNode(::clang::DominatorTree *DT) {
+  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
     return DT->getRootNode();
   }
 
   static nodes_iterator nodes_begin(::clang::DominatorTree *N) {
     return nodes_iterator(df_begin(getEntryNode(N)));
   }
 
   static nodes_iterator nodes_end(::clang::DominatorTree *N) {
     return nodes_iterator(df_end(getEntryNode(N)));
   }
 };
 } // end namespace llvm
 
 #endif

cfe/trunk/include/clang/Analysis/CFG.h

template <> struct simplify_type< ::clang::CFGTerminator> {
   static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
     return Val.getStmt();
   }
 };
 
 // Traits for: CFGBlock
 
 template <> struct GraphTraits< ::clang::CFGBlock *> {
-  typedef ::clang::CFGBlock NodeType;
   typedef ::clang::CFGBlock *NodeRef;
   typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
 
-  static NodeType* getEntryNode(::clang::CFGBlock *BB)
-  { return BB; }
+  static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
 
-  static inline ChildIteratorType child_begin(NodeType* N)
-  { return N->succ_begin(); }
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->succ_begin();
+  }
 
-  static inline ChildIteratorType child_end(NodeType* N)
-  { return N->succ_end(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
 template <> struct GraphTraits< const ::clang::CFGBlock *> {
-  typedef const ::clang::CFGBlock NodeType;
   typedef const ::clang::CFGBlock *NodeRef;
   typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
 
-  static NodeType* getEntryNode(const clang::CFGBlock *BB)
-  { return BB; }
+  static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
 
-  static inline ChildIteratorType child_begin(NodeType* N)
-  { return N->succ_begin(); }
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->succ_begin();
+  }
 
-  static inline ChildIteratorType child_end(NodeType* N)
-  { return N->succ_end(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 
 template <> struct GraphTraits<Inverse< ::clang::CFGBlock*> > {
-  typedef ::clang::CFGBlock NodeType;
   typedef ::clang::CFGBlock *NodeRef;
   typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(Inverse< ::clang::CFGBlock*> G)
-  { return G.Graph; }
+  static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
+    return G.Graph;
+  }
 
-  static inline ChildIteratorType child_begin(NodeType* N)
-  { return N->pred_begin(); }
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->pred_begin();
+  }
 
-  static inline ChildIteratorType child_end(NodeType* N)
-  { return N->pred_end(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
 template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
-  typedef const ::clang::CFGBlock NodeType;
   typedef const ::clang::CFGBlock *NodeRef;
   typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
-  { return G.Graph; }
+  static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
+    return G.Graph;
+  }
 
-  static inline ChildIteratorType child_begin(NodeType* N)
-  { return N->pred_begin(); }
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return N->pred_begin();
+  }
 
-  static inline ChildIteratorType child_end(NodeType* N)
-  { return N->pred_end(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
 // Traits for: CFG
 
 template <> struct GraphTraits< ::clang::CFG* >
     : public GraphTraits< ::clang::CFGBlock *>  {
 
   typedef ::clang::CFG::iterator nodes_iterator;
 
-  static NodeType     *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
+  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
   static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
   static unsigned              size(::clang::CFG* F) { return F->size(); }
 };
 
 template <> struct GraphTraits<const ::clang::CFG* >
     : public GraphTraits<const ::clang::CFGBlock *>  {
 
   typedef ::clang::CFG::const_iterator nodes_iterator;
 
-  static NodeType *getEntryNode( const ::clang::CFG* F) {
-    return &F->getEntry();
-  }
+  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
     return F->nodes_begin();
   }
   static nodes_iterator nodes_end( const ::clang::CFG* F) {
     return F->nodes_end();
   }
   static unsigned size(const ::clang::CFG* F) {
     return F->size();
   }
 };
 
 template <> struct GraphTraits<Inverse< ::clang::CFG*> >
   : public GraphTraits<Inverse< ::clang::CFGBlock*> > {
 
   typedef ::clang::CFG::iterator nodes_iterator;
 
-  static NodeType *getEntryNode( ::clang::CFG* F) { return &F->getExit(); }
+  static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
   static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
   static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
 };
 
 template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
   : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
 
   typedef ::clang::CFG::const_iterator nodes_iterator;
 
-  static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
+  static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
   static nodes_iterator nodes_begin(const ::clang::CFG* F) {
     return F->nodes_begin();
   }
   static nodes_iterator nodes_end(const ::clang::CFG* F) {
     return F->nodes_end();
   }
 };
 } // end llvm namespace
 
 #endif // LLVM_CLANG_ANALYSIS_CFG_H

cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h

 } // end GR namespace
 
 } // end clang namespace
 
 // GraphTraits
 
 namespace llvm {
   template<> struct GraphTraits<clang::ento::ExplodedNode*> {
-    typedef clang::ento::ExplodedNode NodeType;
     typedef clang::ento::ExplodedNode *NodeRef;
-    typedef NodeType::succ_iterator  ChildIteratorType;
-    typedef llvm::df_iterator<NodeType*>      nodes_iterator;
+    typedef clang::ento::ExplodedNode::succ_iterator ChildIteratorType;
+    typedef llvm::df_iterator<NodeRef> nodes_iterator;
 
-    static inline NodeType* getEntryNode(NodeType* N) {
-      return N;
-    }
+    static inline NodeRef getEntryNode(NodeRef N) { return N; }
 
-    static inline ChildIteratorType child_begin(NodeType* N) {
+    static inline ChildIteratorType child_begin(NodeRef N) {
       return N->succ_begin();
     }
 
-    static inline ChildIteratorType child_end(NodeType* N) {
+    static inline ChildIteratorType child_end(NodeRef N) {
       return N->succ_end();
     }
 
-    static inline nodes_iterator nodes_begin(NodeType* N) {
-      return df_begin(N);
-    }
+    static inline nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
 
-    static inline nodes_iterator nodes_end(NodeType* N) {
-      return df_end(N);
-    }
+    static inline nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
   };
 
   template<> struct GraphTraits<const clang::ento::ExplodedNode*> {
-    typedef const clang::ento::ExplodedNode NodeType;
     typedef const clang::ento::ExplodedNode *NodeRef;
-    typedef NodeType::const_succ_iterator   ChildIteratorType;
-    typedef llvm::df_iterator<NodeType*>       nodes_iterator;
+    typedef clang::ento::ExplodedNode::const_succ_iterator ChildIteratorType;
+    typedef llvm::df_iterator<NodeRef> nodes_iterator;
 
-    static inline NodeType* getEntryNode(NodeType* N) {
-      return N;
-    }
+    static inline NodeRef getEntryNode(NodeRef N) { return N; }
 
-    static inline ChildIteratorType child_begin(NodeType* N) {
+    static inline ChildIteratorType child_begin(NodeRef N) {
       return N->succ_begin();
     }
 
-    static inline ChildIteratorType child_end(NodeType* N) {
+    static inline ChildIteratorType child_end(NodeRef N) {
       return N->succ_end();
     }
 
-    static inline nodes_iterator nodes_begin(NodeType* N) {
-      return df_begin(N);
-    }
+    static inline nodes_iterator nodes_begin(NodeRef N) { return df_begin(N); }
 
-    static inline nodes_iterator nodes_end(NodeType* N) {
-      return df_end(N);
-    }
+    static inline nodes_iterator nodes_end(NodeRef N) { return df_end(N); }
   };
 
 } // end llvm namespace
 
 #endif

cfe/trunk/lib/Serialization/ModuleManager.cpp

bool ModuleManager::lookupModuleFile(StringRef FileName,
 
   return false;
 }
 
 #ifndef NDEBUG
 namespace llvm {
   template<>
   struct GraphTraits<ModuleManager> {
-    typedef ModuleFile NodeType;
     typedef ModuleFile *NodeRef;
     typedef llvm::SetVector<ModuleFile *>::const_iterator ChildIteratorType;
     typedef ModuleManager::ModuleConstIterator nodes_iterator;
-    
-    static ChildIteratorType child_begin(NodeType *Node) {
+    static ChildIteratorType child_begin(NodeRef Node) {
       return Node->Imports.begin();
     }
 
-    static ChildIteratorType child_end(NodeType *Node) {
+    static ChildIteratorType child_end(NodeRef Node) {
       return Node->Imports.end();
     }
     
     static nodes_iterator nodes_begin(const ModuleManager &Manager) {
       return Manager.begin();
     }
     
     static nodes_iterator nodes_end(const ModuleManager &Manager) {

llvm/trunk/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 NodeRef           - Type of Node token in the graph, which should
+  //                             be cheap to copy.
   // typedef ChildIteratorType - Type used to iterate over children in graph,
-  //                             dereference to a NodeRef
+  //                             dereference to a NodeRef.
 
   // static NodeRef getEntryNode(const GraphType &)
   //    Return the entry node of the graph
 
   // 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.

llvm/trunk/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;
 
-  static NodeType *getEntryNode(CallGraphNode *CGN) { return CGN; }
+  static NodeRef getEntryNode(CallGraphNode *CGN) { return CGN; }
 
   static CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
 
-  typedef mapped_iterator<NodeType::iterator, decltype(&CGNGetValue)>
+  typedef mapped_iterator<CallGraphNode::iterator, decltype(&CGNGetValue)>
       ChildIteratorType;
 
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N->begin(), &CGNGetValue);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType(N->end(), &CGNGetValue);
   }
 };
 
 template <> struct GraphTraits<const CallGraphNode *> {
-  typedef const CallGraphNode NodeType;
   typedef const CallGraphNode *NodeRef;
 
   typedef CallGraphNode::CallRecord CGNPairTy;
 
-  static NodeType *getEntryNode(const CallGraphNode *CGN) { return CGN; }
+  static NodeRef getEntryNode(const CallGraphNode *CGN) { return CGN; }
 
   static const CallGraphNode *CGNGetValue(CGNPairTy P) { return P.second; }
 
-  typedef mapped_iterator<NodeType::const_iterator, decltype(&CGNGetValue)>
+  typedef mapped_iterator<CallGraphNode::const_iterator, decltype(&CGNGetValue)>
       ChildIteratorType;
 
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return ChildIteratorType(N->begin(), &CGNGetValue);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     return ChildIteratorType(N->end(), &CGNGetValue);
   }
 };
 
 template <>
 struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> {
-  static NodeType *getEntryNode(CallGraph *CGN) {
+  static NodeRef getEntryNode(CallGraph *CGN) {
     return CGN->getExternalCallingNode(); // Start at the external node!
   }
   typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
       PairTy;
   static CallGraphNode *CGGetValuePtr(const PairTy &P) {
     return P.second.get();
   }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef mapped_iterator<CallGraph::iterator, decltype(&CGGetValuePtr)>
       nodes_iterator;
   static nodes_iterator nodes_begin(CallGraph *CG) {
     return nodes_iterator(CG->begin(), &CGGetValuePtr);
   }
   static nodes_iterator nodes_end(CallGraph *CG) {
     return nodes_iterator(CG->end(), &CGGetValuePtr);
   }
 };
 
 template <>
 struct GraphTraits<const CallGraph *> : public GraphTraits<
                                             const CallGraphNode *> {
-  static NodeType *getEntryNode(const CallGraph *CGN) {
+  static NodeRef getEntryNode(const CallGraph *CGN) {
     return CGN->getExternalCallingNode(); // Start at the external node!
   }
   typedef std::pair<const Function *const, std::unique_ptr<CallGraphNode>>
       PairTy;
   static const CallGraphNode *CGGetValuePtr(const PairTy &P) {
     return P.second.get();
   }
 

llvm/trunk/include/llvm/Analysis/Interval.h

 inline Interval::pred_iterator pred_begin(Interval *I) {
   return I->Predecessors.begin();
 }
 inline Interval::pred_iterator pred_end(Interval *I)   {
   return I->Predecessors.end();
 }
 
 template <> struct GraphTraits<Interval*> {
-  typedef Interval NodeType;
+  typedef Interval *NodeRef;
   typedef Interval::succ_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(Interval *I) { return I; }
+  static NodeRef getEntryNode(Interval *I) { return I; }
 
   /// nodes_iterator/begin/end - Allow iteration over all nodes in the graph
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return succ_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return succ_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
 };
 
 template <> struct GraphTraits<Inverse<Interval*> > {
-  typedef Interval NodeType;
+  typedef Interval *NodeRef;
   typedef Interval::pred_iterator ChildIteratorType;
-  static NodeType *getEntryNode(Inverse<Interval *> G) { return G.Graph; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static NodeRef getEntryNode(Inverse<Interval *> G) { return G.Graph; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return pred_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return pred_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/Analysis/LazyCallGraph.h

inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) {
 
   Node &N = G.get(*P.get<Function *>());
   Value.setPointer(&N);
   return N;
 }
 
 // Provide GraphTraits specializations for call graphs.
 template <> struct GraphTraits<LazyCallGraph::Node *> {
-  typedef LazyCallGraph::Node NodeType;
+  typedef LazyCallGraph::Node *NodeRef;
   typedef LazyCallGraph::edge_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 template <> struct GraphTraits<LazyCallGraph *> {
-  typedef LazyCallGraph::Node NodeType;
+  typedef LazyCallGraph::Node *NodeRef;
   typedef LazyCallGraph::edge_iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static ChildIteratorType child_begin(NodeType *N) { return N->begin(); }
-  static ChildIteratorType child_end(NodeType *N) { return N->end(); }
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 /// An analysis pass which computes the call graph for a module.
 class LazyCallGraphAnalysis : public AnalysisInfoMixin<LazyCallGraphAnalysis> {
   friend AnalysisInfoMixin<LazyCallGraphAnalysis>;
   static char PassID;
 
 public:

llvm/trunk/include/llvm/Analysis/LoopInfo.h

bool movementPreservesLCSSAForm(Instruction *Inst, Instruction *NewLoc) {
     }
 
     return true;
   }
 };
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const Loop*> {
-  typedef const Loop NodeType;
   typedef const Loop *NodeRef;
   typedef LoopInfo::iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(const Loop *L) { return L; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->end();
-  }
+  static NodeRef getEntryNode(const Loop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 template <> struct GraphTraits<Loop*> {
-  typedef Loop NodeType;
   typedef Loop *NodeRef;
   typedef LoopInfo::iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(Loop *L) { return L; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->end();
-  }
+  static NodeRef getEntryNode(Loop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 /// \brief Analysis pass that exposes the \c LoopInfo for a function.
 class LoopAnalysis : public AnalysisInfoMixin<LoopAnalysis> {
   friend AnalysisInfoMixin<LoopAnalysis>;
   static char PassID;
 
 public:

llvm/trunk/include/llvm/Analysis/PostDominators.h

struct PostDominatorTreeWrapperPass : public FunctionPass {
 
   void print(raw_ostream &OS, const Module*) const override;
 };
 
 FunctionPass* createPostDomTree();
 
 template <> struct GraphTraits<PostDominatorTree*>
   : public GraphTraits<DomTreeNode*> {
-  static NodeType *getEntryNode(PostDominatorTree *DT) {
+  static NodeRef getEntryNode(PostDominatorTree *DT) {
     return DT->getRootNode();
   }
 
   static nodes_iterator nodes_begin(PostDominatorTree *N) {
     if (getEntryNode(N))
       return df_begin(getEntryNode(N));
     else
       return df_end(getEntryNode(N));

llvm/trunk/include/llvm/Analysis/RegionIterator.h

 // RegionNode GraphTraits specialization so the bbs in the region can be
 // iterate by generic graph iterators.
 //
 // NodeT can either be region node or const region node, otherwise child_begin
 // and child_end fail.
 
 #define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
   template <> struct GraphTraits<NodeT *> {                                    \
-    typedef NodeT NodeType;                                                    \
     typedef NodeT *NodeRef;                                                    \
     typedef RNSuccIterator<NodeRef, BlockT, RegionT> ChildIteratorType;        \
     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     static inline ChildIteratorType child_begin(NodeRef N) {                   \
       return RNSuccIterator<NodeRef, BlockT, RegionT>(N);                      \
     }                                                                          \
     static inline ChildIteratorType child_end(NodeRef N) {                     \
       return RNSuccIterator<NodeRef, BlockT, RegionT>(N, true);                \
     }                                                                          \
   };                                                                           \
   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
-    typedef NodeT NodeType;                                                    \
     typedef NodeT *NodeRef;                                                    \
     typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>                   \
         ChildIteratorType;                                                     \
     static NodeRef getEntryNode(NodeRef N) { return N; }                       \
     static inline ChildIteratorType child_begin(NodeRef N) {                   \
       return RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>(N);              \
     }                                                                          \
     static inline ChildIteratorType child_end(NodeRef N) {                     \

llvm/trunk/include/llvm/CodeGen/MachineBasicBlock.h

 // GraphTraits specializations for machine basic block graphs (machine-CFGs)
 //===--------------------------------------------------------------------===//
 
 // 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) {
+  static NodeRef getEntryNode(MachineBasicBlock *BB) { return BB; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->succ_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->succ_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef 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) {
+  static NodeRef getEntryNode(const MachineBasicBlock *BB) { return BB; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->succ_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->succ_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef 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) {
+  static NodeRef getEntryNode(Inverse<MachineBasicBlock *> G) {
     return G.Graph;
   }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->pred_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->pred_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef 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) {
+  static NodeRef getEntryNode(Inverse<const MachineBasicBlock *> G) {
     return G.Graph;
   }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->pred_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->pred_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
 };
 
 
 
 /// MachineInstrSpan provides an interface to get an iteration range
 /// containing the instruction it was initialized with, along with all
 /// those instructions inserted prior to or following that instruction
 /// at some point after the MachineInstrSpan is constructed.

llvm/trunk/include/llvm/CodeGen/MachineDominators.h

 
 //===-------------------------------------
 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 /// iterable by generic graph iterators.
 ///
 
 template <class Node, class ChildIterator>
 struct MachineDomTreeGraphTraitsBase {
-  typedef Node NodeType;
   typedef Node *NodeRef;
   typedef ChildIterator ChildIteratorType;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 template <class T> struct GraphTraits;
 
 template <>
 struct GraphTraits<MachineDomTreeNode *>
     : public MachineDomTreeGraphTraitsBase<MachineDomTreeNode,
                                            MachineDomTreeNode::iterator> {};
 
 template <>
 struct GraphTraits<const MachineDomTreeNode *>
     : public MachineDomTreeGraphTraitsBase<const MachineDomTreeNode,
                                            MachineDomTreeNode::const_iterator> {
 };
 
 template <> struct GraphTraits<MachineDominatorTree*>
   : public GraphTraits<MachineDomTreeNode *> {
-  static NodeType *getEntryNode(MachineDominatorTree *DT) {
+  static NodeRef getEntryNode(MachineDominatorTree *DT) {
     return DT->getRootNode();
   }
 };
 
 }
 
 #endif

llvm/trunk/include/llvm/CodeGen/MachineFunction.h

 
 // Provide specializations of GraphTraits to be able to treat a
 // machine function as a graph of machine basic blocks... these are
 // the same as the machine basic block iterators, except that the root
 // node is implicitly the first node of the function.
 //
 template <> struct GraphTraits<MachineFunction*> :
   public GraphTraits<MachineBasicBlock*> {
-  static NodeType *getEntryNode(MachineFunction *F) {
-    return &F->front();
-  }
+  static NodeRef getEntryNode(MachineFunction *F) { return &F->front(); }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef pointer_iterator<MachineFunction::iterator> nodes_iterator;
   static nodes_iterator nodes_begin(MachineFunction *F) {
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end(MachineFunction *F) {
     return nodes_iterator(F->end());
   }
   static unsigned       size       (MachineFunction *F) { return F->size(); }
 };
 template <> struct GraphTraits<const MachineFunction*> :
   public GraphTraits<const MachineBasicBlock*> {
-  static NodeType *getEntryNode(const MachineFunction *F) {
-    return &F->front();
-  }
+  static NodeRef getEntryNode(const MachineFunction *F) { return &F->front(); }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
   static nodes_iterator nodes_begin(const MachineFunction *F) {
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end  (const MachineFunction *F) {
     return nodes_iterator(F->end());
   }
   static unsigned       size       (const MachineFunction *F)  {
     return F->size();
   }
 };
 
 
 // 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<MachineFunction*> > :
   public GraphTraits<Inverse<MachineBasicBlock*> > {
-  static NodeType *getEntryNode(Inverse<MachineFunction*> G) {
+  static NodeRef getEntryNode(Inverse<MachineFunction *> G) {
     return &G.Graph->front();
   }
 };
 template <> struct GraphTraits<Inverse<const MachineFunction*> > :
   public GraphTraits<Inverse<const MachineBasicBlock*> > {
-  static NodeType *getEntryNode(Inverse<const MachineFunction *> G) {
+  static NodeRef getEntryNode(Inverse<const MachineFunction *> G) {
     return &G.Graph->front();
   }
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/CodeGen/MachineLoopInfo.h

public:
   void removeBlock(MachineBasicBlock *BB) {
     LI.removeBlock(BB);
   }
 };
 
 
 // Allow clients to walk the list of nested loops...
 template <> struct GraphTraits<const MachineLoop*> {
-  typedef const MachineLoop NodeType;
   typedef const MachineLoop *NodeRef;
   typedef MachineLoopInfo::iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(const MachineLoop *L) { return L; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->end();
-  }
+  static NodeRef getEntryNode(const MachineLoop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 template <> struct GraphTraits<MachineLoop*> {
-  typedef MachineLoop NodeType;
   typedef MachineLoop *NodeRef;
   typedef MachineLoopInfo::iterator ChildIteratorType;
 
-  static NodeType *getEntryNode(MachineLoop *L) { return L; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->end();
-  }
+  static NodeRef getEntryNode(MachineLoop *L) { return L; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/CodeGen/MachineRegionInfo.h

 RegionNodeGraphTraits(MachineRegionNode, MachineBasicBlock, MachineRegion);
 RegionNodeGraphTraits(const MachineRegionNode, MachineBasicBlock, MachineRegion);
 
 RegionGraphTraits(MachineRegion, MachineRegionNode);
 RegionGraphTraits(const MachineRegion, const MachineRegionNode);
 
 template <> struct GraphTraits<MachineRegionInfo*>
   : public GraphTraits<FlatIt<MachineRegionNode*> > {
-  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
-                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
+  typedef df_iterator<NodeRef, SmallPtrSet<NodeRef, 8>, false,
+                      GraphTraits<FlatIt<NodeRef>>>
+      nodes_iterator;
 
-  static NodeType *getEntryNode(MachineRegionInfo *RI) {
+  static NodeRef getEntryNode(MachineRegionInfo *RI) {
     return GraphTraits<FlatIt<MachineRegion*> >::getEntryNode(RI->getTopLevelRegion());
   }
   static nodes_iterator nodes_begin(MachineRegionInfo* RI) {
     return nodes_iterator::begin(getEntryNode(RI));
   }
   static nodes_iterator nodes_end(MachineRegionInfo *RI) {
     return nodes_iterator::end(getEntryNode(RI));
   }
 };
 
 template <> struct GraphTraits<MachineRegionInfoPass*>
   : public GraphTraits<MachineRegionInfo *> {
-  typedef df_iterator<NodeType*, SmallPtrSet<NodeType*, 8>, false,
-                      GraphTraits<FlatIt<NodeType*> > > nodes_iterator;
+  typedef df_iterator<NodeRef, SmallPtrSet<NodeRef, 8>, false,
+                      GraphTraits<FlatIt<NodeRef>>>
+      nodes_iterator;
 
-  static NodeType *getEntryNode(MachineRegionInfoPass *RI) {
+  static NodeRef getEntryNode(MachineRegionInfoPass *RI) {
     return GraphTraits<MachineRegionInfo*>::getEntryNode(&RI->getRegionInfo());
   }
   static nodes_iterator nodes_begin(MachineRegionInfoPass* RI) {
     return GraphTraits<MachineRegionInfo*>::nodes_begin(&RI->getRegionInfo());
   }
   static nodes_iterator nodes_end(MachineRegionInfoPass *RI) {
     return GraphTraits<MachineRegionInfo*>::nodes_end(&RI->getRegionInfo());
   }
 };
 
 extern template class RegionBase<RegionTraits<MachineFunction>>;
 extern template class RegionNodeBase<RegionTraits<MachineFunction>>;
 extern template class RegionInfoBase<RegionTraits<MachineFunction>>;
 }
 
 #endif

llvm/trunk/include/llvm/CodeGen/ScheduleDAG.h

bool isArtificialDep() const {
       return getSDep().isArtificial();
     }
     const SDep &getSDep() const {
       return Node->Preds[Operand];
     }
   };
 
   template <> struct GraphTraits<SUnit*> {
-    typedef SUnit NodeType;
     typedef SUnit *NodeRef;
     typedef SUnitIterator ChildIteratorType;
-    static inline NodeType *getEntryNode(SUnit *N) { return N; }
-    static inline ChildIteratorType child_begin(NodeType *N) {
+    static inline NodeRef getEntryNode(SUnit *N) { return N; }
+    static inline ChildIteratorType child_begin(NodeRef N) {
       return SUnitIterator::begin(N);
     }
-    static inline ChildIteratorType child_end(NodeType *N) {
+    static inline ChildIteratorType child_end(NodeRef N) {
       return SUnitIterator::end(N);
     }
   };
 
   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
     typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
     static nodes_iterator nodes_begin(ScheduleDAG *G) {
       return nodes_iterator(G->SUnits.begin());

llvm/trunk/include/llvm/CodeGen/SelectionDAGNodes.h

static SDNodeIterator end  (const SDNode *N) {
     return SDNodeIterator(N, N->getNumOperands());
   }
 
   unsigned getOperand() const { return Operand; }
   const SDNode *getNode() const { return Node; }
 };
 
 template <> struct GraphTraits<SDNode*> {
-  typedef SDNode NodeType;
   typedef SDNode *NodeRef;
   typedef SDNodeIterator ChildIteratorType;
-  static inline NodeType *getEntryNode(SDNode *N) { return N; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline NodeRef getEntryNode(SDNode *N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return SDNodeIterator::begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     return SDNodeIterator::end(N);
   }
 };
 
 /// A representation of the largest SDNode, for use in sizeof().
 ///
 /// This needs to be a union because the largest node differs on 32 bit systems
 /// with 4 and 8 byte pointer alignment, respectively.

llvm/trunk/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) {
+  static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return succ_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return succ_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef 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 NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
 
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return succ_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return succ_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef 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) {
+  static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return pred_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return pred_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef 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) {
+  static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return pred_begin(N);
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return pred_end(N);
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
 };
 
 
 
 //===--------------------------------------------------------------------===//
 // GraphTraits specializations for function basic block graphs (CFGs)
 //===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks... these are the same as the basic block iterators,
 // except that the root node is implicitly the first node of the function.
 //
 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
-  static NodeType *getEntryNode(Function *F) { return &F->getEntryBlock(); }
+  static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef pointer_iterator<Function::iterator> nodes_iterator;
   static nodes_iterator nodes_begin(Function *F) {
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end(Function *F) {
     return nodes_iterator(F->end());
   }
   static size_t         size       (Function *F) { return F->size(); }
 };
 template <> struct GraphTraits<const Function*> :
   public GraphTraits<const BasicBlock*> {
-  static NodeType *getEntryNode(const Function *F) {return &F->getEntryBlock();}
+  static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
 
   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
   typedef pointer_iterator<Function::const_iterator> nodes_iterator;
   static nodes_iterator nodes_begin(const Function *F) {
     return nodes_iterator(F->begin());
   }
   static nodes_iterator nodes_end(const Function *F) {
     return nodes_iterator(F->end());
   }
   static size_t         size       (const Function *F) { return F->size(); }
 };
 
 
 // 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<Function*> > :
   public GraphTraits<Inverse<BasicBlock*> > {
-  static NodeType *getEntryNode(Inverse<Function*> G) {
+  static NodeRef getEntryNode(Inverse<Function *> G) {
     return &G.Graph->getEntryBlock();
   }
 };
 template <> struct GraphTraits<Inverse<const Function*> > :
   public GraphTraits<Inverse<const BasicBlock*> > {
-  static NodeType *getEntryNode(Inverse<const Function *> G) {
+  static NodeRef getEntryNode(Inverse<const Function *> G) {
     return &G.Graph->getEntryBlock();
   }
 };
 
 } // End llvm namespace
 
 #endif

llvm/trunk/include/llvm/IR/Dominators.h

public:
   void verifyDomTree() const;
 };
 
 //===-------------------------------------
 // DominatorTree GraphTraits specializations so the DominatorTree can be
 // iterable by generic graph iterators.
 
 template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase {
-  typedef Node NodeType;
   typedef Node *NodeRef;
   typedef ChildIterator ChildIteratorType;
-  typedef df_iterator<Node *, SmallPtrSet<NodeType *, 8>> nodes_iterator;
+  typedef df_iterator<Node *, SmallPtrSet<NodeRef, 8>> nodes_iterator;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
-    return N->begin();
-  }
-  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->end(); }
 
-  static nodes_iterator nodes_begin(NodeType *N) {
+  static nodes_iterator nodes_begin(NodeRef N) {
     return df_begin(getEntryNode(N));
   }
 
-  static nodes_iterator nodes_end(NodeType *N) {
-    return df_end(getEntryNode(N));
-  }
+  static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); }
 };
 
 template <>
 struct GraphTraits<DomTreeNode *>
     : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {};
 
 template <>
 struct GraphTraits<const DomTreeNode *>
     : public DomTreeGraphTraitsBase<const DomTreeNode,
                                     DomTreeNode::const_iterator> {};
 
 template <> struct GraphTraits<DominatorTree*>
   : public GraphTraits<DomTreeNode*> {
-  static NodeType *getEntryNode(DominatorTree *DT) {
-    return DT->getRootNode();
-  }
+  static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); }
 
   static nodes_iterator nodes_begin(DominatorTree *N) {
     return df_begin(getEntryNode(N));
   }
 
   static nodes_iterator nodes_end(DominatorTree *N) {
     return df_end(getEntryNode(N));
   }

llvm/trunk/include/llvm/IR/Type.h

template <> struct isa_impl<PointerType, Type> {
   }
 };
 
 //===----------------------------------------------------------------------===//
 // Provide specializations of GraphTraits to be able to treat a type as a
 // graph of sub types.
 
 template <> struct GraphTraits<Type *> {
-  typedef Type NodeType;
   typedef Type *NodeRef;
   typedef Type::subtype_iterator ChildIteratorType;
 
-  static inline NodeType *getEntryNode(Type *T) { return T; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline NodeRef getEntryNode(Type *T) { return T; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->subtype_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     return N->subtype_end();
   }
 };
 
 template <> struct GraphTraits<const Type*> {
-  typedef const Type NodeType;
   typedef const Type *NodeRef;
   typedef Type::subtype_iterator ChildIteratorType;
 
-  static inline NodeType *getEntryNode(NodeType *T) { return T; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static inline NodeRef getEntryNode(NodeRef T) { return T; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->subtype_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
+  static inline ChildIteratorType child_end(NodeRef N) {
     return N->subtype_end();
   }
 };
 
 // Create wrappers for C Binding types (see CBindingWrapping.h).
 DEFINE_ISA_CONVERSION_FUNCTIONS(Type, LLVMTypeRef)
 
 /* Specialized opaque type conversions.

llvm/trunk/include/llvm/Transforms/Utils/MemorySSA.h

 
 inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
   return const_memoryaccess_def_iterator();
 }
 
 /// \brief GraphTraits for a MemoryAccess, which walks defs in the normal case,
 /// and uses in the inverse case.
 template <> struct GraphTraits<MemoryAccess *> {
-  using NodeType = MemoryAccess;
+  using NodeRef = MemoryAccess *;
   using ChildIteratorType = memoryaccess_def_iterator;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->defs_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->defs_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->defs_end(); }
 };
 
 template <> struct GraphTraits<Inverse<MemoryAccess *>> {
-  using NodeType = MemoryAccess;
+  using NodeRef = MemoryAccess *;
   using ChildIteratorType = MemoryAccess::iterator;
 
-  static NodeType *getEntryNode(NodeType *N) { return N; }
-  static inline ChildIteratorType child_begin(NodeType *N) {
+  static NodeRef getEntryNode(NodeRef N) { return N; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->user_begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->user_end();
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->user_end(); }
 };
 
 /// \brief Provide an iterator that walks defs, giving both the memory access,
 /// and the current pointer location, updating the pointer location as it
 /// changes due to phi node translation.
 ///
 /// This iterator, while somewhat specialized, is what most clients actually
 /// want when walking upwards through MemorySSA def chains. It takes a pair of

llvm/trunk/lib/Analysis/BlockFrequencyInfo.cpp

ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
                                 "in red: a block or edge whose frequency "
                                 "is no less than the max frequency of the "
                                 "function multiplied by this percent."));
 
 namespace llvm {
 
 template <>
 struct GraphTraits<BlockFrequencyInfo *> {
-  typedef const BasicBlock NodeType;
   typedef const BasicBlock *NodeRef;
   typedef succ_const_iterator ChildIteratorType;
   typedef pointer_iterator<Function::const_iterator> nodes_iterator;
 
-  static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
+  static inline NodeRef getEntryNode(const BlockFrequencyInfo *G) {
     return &G->getFunction()->front();
   }
-  static ChildIteratorType child_begin(const NodeType *N) {
+  static ChildIteratorType child_begin(const NodeRef N) {
     return succ_begin(N);
   }
-  static ChildIteratorType child_end(const NodeType *N) {
-    return succ_end(N);
-  }
+  static ChildIteratorType child_end(const NodeRef N) { return succ_end(N); }
   static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
     return nodes_iterator(G->getFunction()->begin());
   }
   static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
     return nodes_iterator(G->getFunction()->end());
   }
 };
 

llvm/trunk/lib/Analysis/BlockFrequencyInfoImpl.cpp

void IrreducibleGraph::addEdge(IrrNode &Irr, const BlockNode &Succ,
   SuccIrr.Edges.push_front(&Irr);
   ++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(); }
+  static NodeRef getEntryNode(const GraphT &G) { return G.StartIrr; }
+  static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
+  static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
 };
 } // end namespace llvm
 
 /// \brief Find extra irreducible headers.
 ///
 /// Find entry blocks and other blocks with backedges, which exist when \c G
 /// contains irreducible sub-SCCs.
 static void findIrreducibleHeaders(

llvm/trunk/lib/CodeGen/MachineBlockFrequencyInfo.cpp

cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
                clEnumValEnd));
 
 extern cl::opt<std::string> ViewBlockFreqFuncName;
 extern cl::opt<unsigned> ViewHotFreqPercent;
 
 namespace llvm {
 
 template <> struct GraphTraits<MachineBlockFrequencyInfo *> {
-  typedef const MachineBasicBlock NodeType;
   typedef const MachineBasicBlock *NodeRef;
   typedef MachineBasicBlock::const_succ_iterator ChildIteratorType;
   typedef pointer_iterator<MachineFunction::const_iterator> nodes_iterator;
 
-  static inline const NodeType *
-  getEntryNode(const MachineBlockFrequencyInfo *G) {
+  static inline NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) {
     return &G->getFunction()->front();
   }
 
-  static ChildIteratorType child_begin(const NodeType *N) {
+  static ChildIteratorType child_begin(const NodeRef N) {
     return N->succ_begin();
   }
 
-  static ChildIteratorType child_end(const NodeType *N) {
-    return N->succ_end();
-  }
+  static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); }
 
   static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) {
     return nodes_iterator(G->getFunction()->begin());
   }
 
   static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) {
     return nodes_iterator(G->getFunction()->end());
   }

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

struct ArgumentUsesTracker : public CaptureTracker {
   SmallVector<Argument *, 4> Uses; // Uses within our SCC.
 
   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) {
+  static inline NodeRef getEntryNode(NodeRef A) { return A; }
+  static inline ChildIteratorType child_begin(NodeRef N) {
     return N->Uses.begin();
   }
-  static inline ChildIteratorType child_end(NodeType *N) {
-    return N->Uses.end();
-  }
+  static inline ChildIteratorType child_end(NodeRef N) { return N->Uses.end(); }
 };
 template <>
 struct GraphTraits<ArgumentGraph *> : public GraphTraits<ArgumentGraphNode *> {
-  static NodeType *getEntryNode(ArgumentGraph *AG) {
-    return AG->getEntryNode();
-  }
+  static NodeRef getEntryNode(ArgumentGraph *AG) { return AG->getEntryNode(); }
   static ChildIteratorType nodes_begin(ArgumentGraph *AG) {
     return AG->begin();
   }
   static ChildIteratorType nodes_end(ArgumentGraph *AG) { return AG->end(); }
 };
 }
 
 /// Returns Attribute::None, Attribute::ReadOnly or Attribute::ReadNone.

llvm/trunk/unittests/ADT/SCCIteratorTest.cpp

public:
   /// child_end - Return the end iterator for children of the given node.
   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) {
+  static inline NodeRef getEntryNode(const Graph<N> &G) {
+    return G.AccessNode(0);
+  }
+  static inline ChildIteratorType child_begin(NodeRef Node) {
     return Graph<N>::child_begin(Node);
  }
- static inline ChildIteratorType child_end(NodeType *Node) {
+ static inline ChildIteratorType child_end(NodeRef Node) {
    return Graph<N>::child_end(Node);
  }
 };
 
 TEST(SCCIteratorTest, AllSmallGraphs) {
   // Test SCC computation against every graph with NUM_NODES nodes or less.
   // Since SCC considers every node to have an implicit self-edge, we only
   // create graphs for which every node has a self-edge.

llvm/trunk/unittests/Analysis/CallGraphTest.cpp

 #include "llvm/IR/Module.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 template <typename Ty> void canSpecializeGraphTraitsIterators(Ty *G) {
-  typedef typename GraphTraits<Ty *>::NodeType NodeTy;
+  typedef typename GraphTraits<Ty *>::NodeRef NodeRef;
 
   auto I = GraphTraits<Ty *>::nodes_begin(G);
   auto E = GraphTraits<Ty *>::nodes_end(G);
   auto X = ++I;
 
   // Should be able to iterate over all nodes of the graph.
-  static_assert(std::is_same<decltype(*I), NodeTy *>::value,
+  static_assert(std::is_same<decltype(*I), NodeRef>::value,
                 "Node type does not match");
-  static_assert(std::is_same<decltype(*X), NodeTy *>::value,
+  static_assert(std::is_same<decltype(*X), NodeRef>::value,
                 "Node type does not match");
-  static_assert(std::is_same<decltype(*E), NodeTy *>::value,
+  static_assert(std::is_same<decltype(*E), NodeRef>::value,
                 "Node type does not match");
 
-  NodeTy *N = GraphTraits<Ty *>::getEntryNode(G);
+  NodeRef N = GraphTraits<Ty *>::getEntryNode(G);
 
-  auto S = GraphTraits<NodeTy *>::child_begin(N);
-  auto F = GraphTraits<NodeTy *>::child_end(N);
+  auto S = GraphTraits<NodeRef>::child_begin(N);
+  auto F = GraphTraits<NodeRef>::child_end(N);
 
   // Should be able to iterate over immediate successors of a node.
-  static_assert(std::is_same<decltype(*S), NodeTy *>::value,
+  static_assert(std::is_same<decltype(*S), NodeRef>::value,
                 "Node type does not match");
-  static_assert(std::is_same<decltype(*F), NodeTy *>::value,
+  static_assert(std::is_same<decltype(*F), NodeRef>::value,
                 "Node type does not match");
 }
 
 TEST(CallGraphTest, GraphTraitsSpecialization) {
   LLVMContext Context;
   Module M("", Context);
   CallGraph CG(M);