Index: include/llvm/ADT/DepthFirstIterator.h
===================================================================
--- include/llvm/ADT/DepthFirstIterator.h
+++ include/llvm/ADT/DepthFirstIterator.h
@@ -34,6 +34,7 @@
 #define LLVM_ADT_DEPTHFIRSTITERATOR_H
 
 #include "llvm/ADT/GraphTraits.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/iterator_range.h"
@@ -59,38 +60,40 @@
 };
 
 // Generic Depth First Iterator
-template<class GraphT,
-class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
-         bool ExtStorage = false, class GT = GraphTraits<GraphT> >
-class df_iterator : public std::iterator<std::forward_iterator_tag,
-                                         typename GT::NodeType, ptrdiff_t>,
-                    public df_iterator_storage<SetType, ExtStorage> {
-  typedef std::iterator<std::forward_iterator_tag,
-                        typename GT::NodeType, ptrdiff_t> super;
-
-  typedef typename GT::NodeType          NodeType;
+template <class GraphT,
+          class SetType =
+              llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
+          bool ExtStorage = false, class GT = GraphTraits<GraphT>>
+class df_iterator
+    : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef,
+                           ptrdiff_t, typename GT::NodeRef,
+                           typename GT::NodeRef>,
+      public df_iterator_storage<SetType, ExtStorage> {
+  typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef,
+                        ptrdiff_t, typename GT::NodeRef, typename GT::NodeRef>
+      super;
+
+  typedef typename GT::NodeRef NodeRef;
   typedef typename GT::ChildIteratorType ChildItTy;
-  typedef PointerIntPair<NodeType*, 1>   PointerIntTy;
+  typedef std::pair<NodeRef, Optional<ChildItTy>> StackElement;
 
   // VisitStack - Used to maintain the ordering.  Top = current block
   // First element is node pointer, second is the 'next child' to visit
   // if the int in PointerIntTy is 0, the 'next child' to visit is invalid
-  std::vector<std::pair<PointerIntTy, ChildItTy>> VisitStack;
+  std::vector<StackElement> VisitStack;
 
 private:
-  inline df_iterator(NodeType *Node) {
+  inline df_iterator(NodeRef Node) {
     this->Visited.insert(Node);
-    VisitStack.push_back(
-        std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node)));
+    VisitStack.push_back(StackElement{Node, None});
   }
   inline df_iterator() {
     // End is when stack is empty
   }
-  inline df_iterator(NodeType *Node, SetType &S)
-    : df_iterator_storage<SetType, ExtStorage>(S) {
+  inline df_iterator(NodeRef Node, SetType &S)
+      : df_iterator_storage<SetType, ExtStorage>(S) {
     if (!S.count(Node)) {
-      VisitStack.push_back(
-          std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node)));
+      VisitStack.push_back(StackElement{Node, None});
       this->Visited.insert(Node);
     }
   }
@@ -101,22 +104,20 @@
 
   inline void toNext() {
     do {
-      std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back();
-      NodeType *Node = Top.first.getPointer();
-      ChildItTy &It  = Top.second;
-      if (!Top.first.getInt()) {
-        // now retrieve the real begin of the children before we dive in
-        It = GT::child_begin(Node);
-        Top.first.setInt(1);
-      }
+      NodeRef Node = VisitStack.back().first;
+      Optional<ChildItTy> &Opt = VisitStack.back().second;
+
+      if (!Opt.hasValue())
+        Opt.emplace(GT::child_begin(Node));
+
+      ChildItTy &It = *Opt;
 
       while (It != GT::child_end(Node)) {
-        NodeType *Next = *It++;
+        NodeRef Next = *It++;
         // Has our next sibling been visited?
-        if (Next && this->Visited.insert(Next).second) {
+        if (this->Visited.insert(Next).second) {
           // No, do it now.
-          VisitStack.push_back(
-              std::make_pair(PointerIntTy(Next, 0), GT::child_begin(Next)));
+          VisitStack.push_back(StackElement{Next, None});
           return;
         }
       }
@@ -142,17 +143,20 @@
   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
 
   bool operator==(const df_iterator &x) const {
-    return VisitStack == x.VisitStack;
+    // There is no practical reason to compare two non-end() iterators.
+    assert((VisitStack.empty() || x.VisitStack.empty()) &&
+           "The iterator is expected to compare against end()");
+    return VisitStack.empty() == x.VisitStack.empty();
   }
   bool operator!=(const df_iterator &x) const { return !(*this == x); }
 
-  pointer operator*() const { return VisitStack.back().first.getPointer(); }
+  NodeRef operator*() const { return VisitStack.back().first; }
 
   // This is a nonstandard operator-> that dereferences the pointer an extra
   // time... so that you can actually call methods ON the Node, because
   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
   //
-  NodeType *operator->() const { return **this; }
+  NodeRef operator->() const { return **this; }
 
   df_iterator &operator++() { // Preincrement
     toNext();
@@ -180,7 +184,7 @@
   // specified node.  This is public, and will probably be used to iterate over
   // nodes that a depth first iteration did not find: ie unreachable nodes.
   //
-  bool nodeVisited(NodeType *Node) const {
+  bool nodeVisited(NodeRef Node) const {
     return this->Visited.count(Node) != 0;
   }
 
@@ -190,9 +194,7 @@
 
   /// getPath - Return the n'th node in the path from the entry node to the
   /// current node.
-  NodeType *getPath(unsigned n) const {
-    return VisitStack[n].first.getPointer();
-  }
+  NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
 };
 
 // Provide global constructors that automatically figure out correct types...
@@ -214,7 +216,7 @@
 }
 
 // Provide global definitions of external depth first iterators...
-template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
+template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
     : df_iterator<T, SetTy, true>(V) {}
@@ -238,7 +240,7 @@
 
 // Provide global definitions of inverse depth first iterators...
 template <class T,
-  class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>,
+          class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeRef, 8>,
           bool External = false>
 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
@@ -262,7 +264,7 @@
 }
 
 // Provide global definitions of external inverse depth first iterators...
-template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> >
+template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
     : idf_iterator<T, SetTy, true>(V) {}
Index: include/llvm/Analysis/LoopInfo.h
===================================================================
--- include/llvm/Analysis/LoopInfo.h
+++ include/llvm/Analysis/LoopInfo.h
@@ -762,6 +762,7 @@
 // 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; }
@@ -775,6 +776,7 @@
 
 template <> struct GraphTraits<Loop*> {
   typedef Loop NodeType;
+  typedef Loop *NodeRef;
   typedef LoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(Loop *L) { return L; }
Index: include/llvm/Analysis/RegionIterator.h
===================================================================
--- include/llvm/Analysis/RegionIterator.h
+++ include/llvm/Analysis/RegionIterator.h
@@ -249,29 +249,31 @@
 // 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 RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType;  \
-  static NodeType *getEntryNode(NodeType* N) { return N; } \
-  static inline ChildIteratorType child_begin(NodeType *N) { \
-    return RNSuccIterator<NodeType, BlockT, RegionT>(N);             \
-  } \
-  static inline ChildIteratorType child_end(NodeType *N) { \
-    return RNSuccIterator<NodeType, BlockT, RegionT>(N, true);     \
-  } \
-}; \
-template<> struct GraphTraits<FlatIt<NodeT*>> {  \
-  typedef NodeT NodeType; \
-  typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT > ChildIteratorType;    \
-  static NodeType *getEntryNode(NodeType* N) { return N; } \
-  static inline ChildIteratorType child_begin(NodeType *N) { \
-    return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N); \
-  } \
-  static inline ChildIteratorType child_end(NodeType *N) { \
-    return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true); \
-  } \
-}
+#define RegionNodeGraphTraits(NodeT, BlockT, RegionT)                          \
+  template <> struct GraphTraits<NodeT *> {                                    \
+    typedef NodeT NodeType;                                                    \
+    typedef NodeT *NodeRef;                                                    \
+    typedef RNSuccIterator<NodeType, BlockT, RegionT> ChildIteratorType;       \
+    static NodeType *getEntryNode(NodeType *N) { return N; }                   \
+    static inline ChildIteratorType child_begin(NodeType *N) {                 \
+      return RNSuccIterator<NodeType, BlockT, RegionT>(N);                     \
+    }                                                                          \
+    static inline ChildIteratorType child_end(NodeType *N) {                   \
+      return RNSuccIterator<NodeType, BlockT, RegionT>(N, true);               \
+    }                                                                          \
+  };                                                                           \
+  template <> struct GraphTraits<FlatIt<NodeT *>> {                            \
+    typedef NodeT NodeType;                                                    \
+    typedef NodeT *NodeRef;                                                    \
+    typedef RNSuccIterator<FlatIt<NodeT>, BlockT, RegionT> ChildIteratorType;  \
+    static NodeType *getEntryNode(NodeType *N) { return N; }                   \
+    static inline ChildIteratorType child_begin(NodeType *N) {                 \
+      return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N);             \
+    }                                                                          \
+    static inline ChildIteratorType child_end(NodeType *N) {                   \
+      return RNSuccIterator<FlatIt<NodeType>, BlockT, RegionT>(N, true);       \
+    }                                                                          \
+  }
 
 #define RegionGraphTraits(RegionT, NodeT) \
 template<> struct GraphTraits<RegionT*> \
Index: include/llvm/CodeGen/MachineDominators.h
===================================================================
--- include/llvm/CodeGen/MachineDominators.h
+++ include/llvm/CodeGen/MachineDominators.h
@@ -272,6 +272,7 @@
 template <class Node, class ChildIterator>
 struct MachineDomTreeGraphTraitsBase {
   typedef Node NodeType;
+  typedef Node *NodeRef;
   typedef ChildIterator ChildIteratorType;
 
   static NodeType *getEntryNode(NodeType *N) { return N; }
Index: include/llvm/CodeGen/MachineLoopInfo.h
===================================================================
--- include/llvm/CodeGen/MachineLoopInfo.h
+++ include/llvm/CodeGen/MachineLoopInfo.h
@@ -149,6 +149,7 @@
 // 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; }
@@ -162,6 +163,7 @@
 
 template <> struct GraphTraits<MachineLoop*> {
   typedef MachineLoop NodeType;
+  typedef MachineLoop *NodeRef;
   typedef MachineLoopInfo::iterator ChildIteratorType;
 
   static NodeType *getEntryNode(MachineLoop *L) { return L; }
Index: include/llvm/IR/Dominators.h
===================================================================
--- include/llvm/IR/Dominators.h
+++ include/llvm/IR/Dominators.h
@@ -156,6 +156,7 @@
 
 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;