From f2187ed3210377902124b326957f8721bb58733a Mon Sep 17 00:00:00 2001
From: Tim Shen <timshen91@gmail.com>
Date: Mon, 22 Aug 2016 21:09:30 +0000
Subject: [PATCH] [GraphTraits] Replace all NodeType usage with NodeRef

This should finish the GraphTraits migration.

Differential Revision: http://reviews.llvm.org/D23730

llvm-svn: 279475
---
 clang/include/clang/AST/StmtGraphTraits.h          | 14 +++--
 clang/include/clang/Analysis/Analyses/Dominators.h | 17 ++----
 clang/include/clang/Analysis/CFG.h                 | 62 ++++++++++------------
 .../Core/PathSensitive/ExplodedGraph.h             | 42 +++++----------
 clang/lib/Serialization/ModuleManager.cpp          |  7 ++-
 llvm/include/llvm/ADT/GraphTraits.h                | 11 ++--
 llvm/include/llvm/Analysis/CallGraph.h             | 22 ++++----
 llvm/include/llvm/Analysis/Interval.h              | 20 +++----
 llvm/include/llvm/Analysis/LazyCallGraph.h         | 16 +++---
 llvm/include/llvm/Analysis/LoopInfo.h              | 22 +++-----
 llvm/include/llvm/Analysis/PostDominators.h        |  2 +-
 llvm/include/llvm/Analysis/RegionIterator.h        |  2 -
 llvm/include/llvm/CodeGen/MachineBasicBlock.h      | 36 +++++--------
 llvm/include/llvm/CodeGen/MachineDominators.h      | 11 ++--
 llvm/include/llvm/CodeGen/MachineFunction.h        | 12 ++---
 llvm/include/llvm/CodeGen/MachineLoopInfo.h        | 22 +++-----
 llvm/include/llvm/CodeGen/MachineRegionInfo.h      | 14 ++---
 llvm/include/llvm/CodeGen/ScheduleDAG.h            |  7 ++-
 llvm/include/llvm/CodeGen/SelectionDAGNodes.h      |  7 ++-
 llvm/include/llvm/IR/CFG.h                         | 46 ++++++----------
 llvm/include/llvm/IR/Dominators.h                  | 21 +++-----
 llvm/include/llvm/IR/Type.h                        | 14 +++--
 llvm/include/llvm/Transforms/Utils/MemorySSA.h     | 20 +++----
 llvm/lib/Analysis/BlockFrequencyInfo.cpp           |  9 ++--
 llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp       |  9 ++--
 llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp     | 10 ++--
 llvm/lib/Transforms/IPO/FunctionAttrs.cpp          | 13 ++---
 llvm/unittests/ADT/SCCIteratorTest.cpp             | 11 ++--
 llvm/unittests/Analysis/CallGraphTest.cpp          | 18 +++----
 29 files changed, 197 insertions(+), 320 deletions(-)

diff --git a/clang/include/clang/AST/StmtGraphTraits.h b/clang/include/clang/AST/StmtGraphTraits.h
index dac4495c..11084be 100644
--- a/clang/include/clang/AST/StmtGraphTraits.h
+++ b/clang/include/clang/AST/StmtGraphTraits.h
@@ -25,19 +25,18 @@ namespace llvm {
 
 
 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();
   }
@@ -53,19 +52,18 @@ template <> struct GraphTraits<clang::Stmt*> {
 
 
 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();
   }
diff --git a/clang/include/clang/Analysis/Analyses/Dominators.h b/clang/include/clang/Analysis/Analyses/Dominators.h
index df6118d..3e625d2 100644
--- a/clang/include/clang/Analysis/Analyses/Dominators.h
+++ b/clang/include/clang/Analysis/Analyses/Dominators.h
@@ -167,19 +167,12 @@ private:
 ///
 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;
@@ -195,7 +188,7 @@ template <> struct GraphTraits< ::clang::DomTreeNode* > {
 
 template <> struct GraphTraits< ::clang::DominatorTree* >
   : public GraphTraits< ::clang::DomTreeNode* > {
-  static NodeType *getEntryNode(::clang::DominatorTree *DT) {
+  static NodeRef getEntryNode(::clang::DominatorTree *DT) {
     return DT->getRootNode();
   }
 
diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h
index 29d2008..36201b05 100644
--- a/clang/include/clang/Analysis/CFG.h
+++ b/clang/include/clang/Analysis/CFG.h
@@ -945,63 +945,59 @@ template <> struct simplify_type< ::clang::CFGTerminator> {
 // 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
@@ -1011,7 +1007,7 @@ template <> struct GraphTraits< ::clang::CFG* >
 
   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(); }
@@ -1022,9 +1018,7 @@ template <> struct GraphTraits<const ::clang::CFG* >
 
   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();
   }
@@ -1041,7 +1035,7 @@ template <> struct GraphTraits<Inverse< ::clang::CFG*> >
 
   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(); }
 };
@@ -1051,7 +1045,7 @@ template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
 
   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();
   }
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
index 03a0f11..48feef4 100644
--- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
+++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h
@@ -450,57 +450,43 @@ public:
 
 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
diff --git a/clang/lib/Serialization/ModuleManager.cpp b/clang/lib/Serialization/ModuleManager.cpp
index bc57d8c..f645248 100644
--- a/clang/lib/Serialization/ModuleManager.cpp
+++ b/clang/lib/Serialization/ModuleManager.cpp
@@ -433,16 +433,15 @@ bool ModuleManager::lookupModuleFile(StringRef FileName,
 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();
     }
     
diff --git a/llvm/include/llvm/ADT/GraphTraits.h b/llvm/include/llvm/ADT/GraphTraits.h
index 7ca0134..29bbcb0 100644
--- a/llvm/include/llvm/ADT/GraphTraits.h
+++ b/llvm/include/llvm/ADT/GraphTraits.h
@@ -27,15 +27,10 @@ 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
diff --git a/llvm/include/llvm/Analysis/CallGraph.h b/llvm/include/llvm/Analysis/CallGraph.h
index 54da6e8..58e2a63 100644
--- a/llvm/include/llvm/Analysis/CallGraph.h
+++ b/llvm/include/llvm/Analysis/CallGraph.h
@@ -409,50 +409,48 @@ public:
 // 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>>
@@ -475,7 +473,7 @@ struct GraphTraits<CallGraph *> : public GraphTraits<CallGraphNode *> {
 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>>
diff --git a/llvm/include/llvm/Analysis/Interval.h b/llvm/include/llvm/Analysis/Interval.h
index a904753..d16406f 100644
--- a/llvm/include/llvm/Analysis/Interval.h
+++ b/llvm/include/llvm/Analysis/Interval.h
@@ -121,30 +121,26 @@ inline Interval::pred_iterator pred_end(Interval *I)   {
 }
 
 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
diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h
index 9f62eaa..8a09535 100644
--- a/llvm/include/llvm/Analysis/LazyCallGraph.h
+++ b/llvm/include/llvm/Analysis/LazyCallGraph.h
@@ -953,20 +953,20 @@ inline LazyCallGraph::Node &LazyCallGraph::Edge::getNode(LazyCallGraph &G) {
 
 // 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.
diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h
index 52345e4..9fc7016 100644
--- a/llvm/include/llvm/Analysis/LoopInfo.h
+++ b/llvm/include/llvm/Analysis/LoopInfo.h
@@ -761,31 +761,21 @@ public:
 
 // 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.
diff --git a/llvm/include/llvm/Analysis/PostDominators.h b/llvm/include/llvm/Analysis/PostDominators.h
index b7638b7..f4bef12 100644
--- a/llvm/include/llvm/Analysis/PostDominators.h
+++ b/llvm/include/llvm/Analysis/PostDominators.h
@@ -89,7 +89,7 @@ FunctionPass* createPostDomTree();
 
 template <> struct GraphTraits<PostDominatorTree*>
   : public GraphTraits<DomTreeNode*> {
-  static NodeType *getEntryNode(PostDominatorTree *DT) {
+  static NodeRef getEntryNode(PostDominatorTree *DT) {
     return DT->getRootNode();
   }
 
diff --git a/llvm/include/llvm/Analysis/RegionIterator.h b/llvm/include/llvm/Analysis/RegionIterator.h
index 6d3bcd5..80b7523 100644
--- a/llvm/include/llvm/Analysis/RegionIterator.h
+++ b/llvm/include/llvm/Analysis/RegionIterator.h
@@ -255,7 +255,6 @@ inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
 
 #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; }                       \
@@ -267,7 +266,6 @@ inline RNSuccIterator<NodeRef, BlockT, RegionT> succ_end(NodeRef Node) {
     }                                                                          \
   };                                                                           \
   template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
-    typedef NodeT NodeType;                                                    \
     typedef NodeT *NodeRef;                                                    \
     typedef RNSuccIterator<FlatIt<NodeRef>, BlockT, RegionT>                   \
         ChildIteratorType;                                                     \
diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
index e789b2e..68a6ef3 100644
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -728,31 +728,25 @@ struct MBB2NumberFunctor :
 //
 
 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
@@ -762,33 +756,27 @@ template <> struct GraphTraits<const MachineBasicBlock *> {
 // 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(); }
 };
 
 
diff --git a/llvm/include/llvm/CodeGen/MachineDominators.h b/llvm/include/llvm/CodeGen/MachineDominators.h
index 694c449..7f95b65 100644
--- a/llvm/include/llvm/CodeGen/MachineDominators.h
+++ b/llvm/include/llvm/CodeGen/MachineDominators.h
@@ -271,15 +271,12 @@ public:
 
 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;
@@ -297,7 +294,7 @@ struct GraphTraits<const MachineDomTreeNode *>
 
 template <> struct GraphTraits<MachineDominatorTree*>
   : public GraphTraits<MachineDomTreeNode *> {
-  static NodeType *getEntryNode(MachineDominatorTree *DT) {
+  static NodeRef getEntryNode(MachineDominatorTree *DT) {
     return DT->getRootNode();
   }
 };
diff --git a/llvm/include/llvm/CodeGen/MachineFunction.h b/llvm/include/llvm/CodeGen/MachineFunction.h
index 8ad04e0..f34f376 100644
--- a/llvm/include/llvm/CodeGen/MachineFunction.h
+++ b/llvm/include/llvm/CodeGen/MachineFunction.h
@@ -614,9 +614,7 @@ public:
 //
 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;
@@ -630,9 +628,7 @@ template <> struct GraphTraits<MachineFunction*> :
 };
 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;
@@ -655,13 +651,13 @@ template <> struct GraphTraits<const MachineFunction*> :
 //
 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();
   }
 };
diff --git a/llvm/include/llvm/CodeGen/MachineLoopInfo.h b/llvm/include/llvm/CodeGen/MachineLoopInfo.h
index 308fc94..200234b 100644
--- a/llvm/include/llvm/CodeGen/MachineLoopInfo.h
+++ b/llvm/include/llvm/CodeGen/MachineLoopInfo.h
@@ -162,31 +162,21 @@ public:
 
 // 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
diff --git a/llvm/include/llvm/CodeGen/MachineRegionInfo.h b/llvm/include/llvm/CodeGen/MachineRegionInfo.h
index df9823f..13e86dd 100644
--- a/llvm/include/llvm/CodeGen/MachineRegionInfo.h
+++ b/llvm/include/llvm/CodeGen/MachineRegionInfo.h
@@ -142,10 +142,11 @@ 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) {
@@ -158,10 +159,11 @@ template <> struct GraphTraits<MachineRegionInfo*>
 
 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) {
diff --git a/llvm/include/llvm/CodeGen/ScheduleDAG.h b/llvm/include/llvm/CodeGen/ScheduleDAG.h
index f4e7123..4d62ee5 100644
--- a/llvm/include/llvm/CodeGen/ScheduleDAG.h
+++ b/llvm/include/llvm/CodeGen/ScheduleDAG.h
@@ -679,14 +679,13 @@ namespace llvm {
   };
 
   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);
     }
   };
diff --git a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
index b20a889..8b783b0 100644
--- a/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/llvm/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -2055,14 +2055,13 @@ public:
 };
 
 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);
   }
 };
diff --git a/llvm/include/llvm/IR/CFG.h b/llvm/include/llvm/IR/CFG.h
index 6e31cdc..9a3d984 100644
--- a/llvm/include/llvm/IR/CFG.h
+++ b/llvm/include/llvm/IR/CFG.h
@@ -154,32 +154,26 @@ struct isPodLike<TerminatorInst::SuccIterator<T, U>> {
 // 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
@@ -188,31 +182,23 @@ template <> struct GraphTraits<const BasicBlock*> {
 // 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); }
 };
 
 
@@ -226,7 +212,7 @@ template <> struct GraphTraits<Inverse<const BasicBlock*> > {
 // 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;
@@ -240,7 +226,7 @@ template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
 };
 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;
@@ -261,13 +247,13 @@ template <> struct GraphTraits<const Function*> :
 //
 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();
   }
 };
diff --git a/llvm/include/llvm/IR/Dominators.h b/llvm/include/llvm/IR/Dominators.h
index c1fb008..276423a 100644
--- a/llvm/include/llvm/IR/Dominators.h
+++ b/llvm/include/llvm/IR/Dominators.h
@@ -155,24 +155,19 @@ public:
 // 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 <>
@@ -186,9 +181,7 @@ struct GraphTraits<const DomTreeNode *>
 
 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));
diff --git a/llvm/include/llvm/IR/Type.h b/llvm/include/llvm/IR/Type.h
index e6125a6..c4044af 100644
--- a/llvm/include/llvm/IR/Type.h
+++ b/llvm/include/llvm/IR/Type.h
@@ -429,29 +429,27 @@ template <> struct isa_impl<PointerType, Type> {
 // 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();
   }
 };
diff --git a/llvm/include/llvm/Transforms/Utils/MemorySSA.h b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
index 40b065e..8f66695 100644
--- a/llvm/include/llvm/Transforms/Utils/MemorySSA.h
+++ b/llvm/include/llvm/Transforms/Utils/MemorySSA.h
@@ -876,29 +876,25 @@ inline const_memoryaccess_def_iterator MemoryAccess::defs_end() const {
 /// \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,
diff --git a/llvm/lib/Analysis/BlockFrequencyInfo.cpp b/llvm/lib/Analysis/BlockFrequencyInfo.cpp
index a20c8fb..08ace64 100644
--- a/llvm/lib/Analysis/BlockFrequencyInfo.cpp
+++ b/llvm/lib/Analysis/BlockFrequencyInfo.cpp
@@ -60,20 +60,17 @@ 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());
   }
diff --git a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
index 9d3045c..9850e02 100644
--- a/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
+++ b/llvm/lib/Analysis/BlockFrequencyInfoImpl.cpp
@@ -628,15 +628,12 @@ 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
 
diff --git a/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp b/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp
index 4147e5e..bda6aa4 100644
--- a/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp
+++ b/llvm/lib/CodeGen/MachineBlockFrequencyInfo.cpp
@@ -52,23 +52,19 @@ 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());
diff --git a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
index ce648e2..6e03666 100644
--- a/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
+++ b/llvm/lib/Transforms/IPO/FunctionAttrs.cpp
@@ -332,23 +332,18 @@ struct ArgumentUsesTracker : public CaptureTracker {
 
 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();
   }
diff --git a/llvm/unittests/ADT/SCCIteratorTest.cpp b/llvm/unittests/ADT/SCCIteratorTest.cpp
index 597661f..62eb0e6 100644
--- a/llvm/unittests/ADT/SCCIteratorTest.cpp
+++ b/llvm/unittests/ADT/SCCIteratorTest.cpp
@@ -229,15 +229,16 @@ public:
 
 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 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);
  }
 };
diff --git a/llvm/unittests/Analysis/CallGraphTest.cpp b/llvm/unittests/Analysis/CallGraphTest.cpp
index 0c92804..2d4e63f 100644
--- a/llvm/unittests/Analysis/CallGraphTest.cpp
+++ b/llvm/unittests/Analysis/CallGraphTest.cpp
@@ -17,29 +17,29 @@ 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");
 }
 
-- 
2.7.4