[ADT] Migrate DepthFirstIterator to use NodeRef

[timshen]

Summary

Notice that the data layout is changed: instead of using
std::pair<PointerIntPair<NodeType*, 1>, ChildItTy>, now use
std::pair<NodeRef, Optional<ChildItTy>>.

[timshen]

Updated comments to reflect the change.

[dblaikie]

Removing the ability to compare non-end iterators seems like a loss of functionality & would be pretty tricky for the average user (would catch them by surprise that only end iterators are comparable).

Unless there's a reason the design already precludes comparing non-end iterators, I'd say it's best to preserve the existing behavior there.

Other than that, it looks pretty reasonable.

include/llvm/ADT/DepthFirstIterator.h

111 ↗

(On Diff #66746)

I'd just write this as "if (!Opt)" - but up to you.

114–117 ↗

(On Diff #66746)

For a separate patch: any idea why this isn't a normal for (or even range-for) loop?

121 ↗

(On Diff #66746)

We aren't really using braced init like that much in the project so far. I'd probably stick with () when calling a ctor. (same feedback elsewhere)

[timshen]

Updated as commented.

[timshen]

include/llvm/ADT/DepthFirstIterator.h

114–117 ↗

(On Diff #66875)

Oops I already fixed it. I don't think that it's a functional change, but just a modernization.

[dblaikie]

Looks good, thanks! (I realize we've got to wait to finalize the Optional stuff first, of course)

llvm/trunk/include/llvm/ADT/DepthFirstIterator.h

 //     other purposes.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H
 #define LLVM_ADT_DEPTHFIRSTITERATOR_H
 
 #include "llvm/ADT/GraphTraits.h"
-#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/iterator_range.h"
 #include <set>
 #include <vector>
 
 namespace llvm {
 
 // df_iterator_storage - A private class which is used to figure out where to
 // store the visited set.
 template<class SetType, bool External>   // Non-external set
 class df_iterator_storage {
 public:
   SetType Visited;
 };
 
 template<class SetType>
 class df_iterator_storage<SetType, true> {
 public:
   df_iterator_storage(SetType &VSet) : Visited(VSet) {}
   df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
   SetType &Visited;
 };
 
 // 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;
+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>,
+  typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef,
+                        ptrdiff_t, typename GT::NodeRef, typename GT::NodeRef>
+      super;
 
-  typedef typename GT::NodeType          NodeType;
+  typedef typename GT::NodeRef NodeRef;
   typedef typename GT::ChildIteratorType ChildItTy;
-  typedef PointerIntPair<NodeType*, 1>   PointerIntTy;
+
+  // First element is node reference, second is the 'next child' to visit.
+  // The second child is initialized lazily to pick up graph changes during the
+  // DFS.
+  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)
+  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);
     }
   }
   inline df_iterator(SetType &S)
     : df_iterator_storage<SetType, ExtStorage>(S) {
     // End is when stack is empty
   }
 
   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;
 
-      while (It != GT::child_end(Node)) {
-        NodeType *Next = *It++;
+      if (!Opt)
+        Opt.emplace(GT::child_begin(Node));
+
+      for (NodeRef Next : make_range(*Opt, GT::child_end(Node))) {
         // 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;
         }
       }
 
       // Oops, ran out of successors... go up a level on the stack.
       VisitStack.pop_back();
     } while (!VisitStack.empty());
   }
public:
   }
   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
 
   bool operator==(const df_iterator &x) const {
     return VisitStack == x.VisitStack;
   }
   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();
     return *this;
   }
 
   /// \brief Skips all children of the current node and traverses to next node
   ///
df_iterator operator++(int) { // Postincrement
     ++*this;
     return tmp;
   }
 
   // nodeVisited - return true if this iterator has already visited the
   // 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;
   }
 
   /// getPathLength - Return the length of the path from the entry node to the
   /// current node, counting both nodes.
   unsigned getPathLength() const { return VisitStack.size(); }
 
   /// 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...
 //
 template <class T>
 df_iterator<T> df_begin(const T& G) {
   return df_iterator<T>::begin(G);
 }
 
 template <class T>
 df_iterator<T> df_end(const T& G) {
   return df_iterator<T>::end(G);
 }
 
 // Provide an accessor method to use them in range-based patterns.
 template <class T>
 iterator_range<df_iterator<T>> depth_first(const T& G) {
   return make_range(df_begin(G), df_end(G));
 }
 
 // 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) {}
 };
 
 template <class T, class SetTy>
 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
   return df_ext_iterator<T, SetTy>::begin(G, S);
 }
 
 template <class T, class SetTy>
 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
   return df_ext_iterator<T, SetTy>::end(G, S);
 }
 
 template <class T, class SetTy>
 iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
                                                           SetTy &S) {
   return make_range(df_ext_begin(G, S), df_ext_end(G, S));
 }
 
 // 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)
     : df_iterator<Inverse<T>, SetTy, External>(V) {}
 };
 
 template <class T>
 idf_iterator<T> idf_begin(const T& G) {
   return idf_iterator<T>::begin(Inverse<T>(G));
 }
 
 template <class T>
 idf_iterator<T> idf_end(const T& G){
   return idf_iterator<T>::end(Inverse<T>(G));
 }
 
 // Provide an accessor method to use them in range-based patterns.
 template <class T>
 iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
   return make_range(idf_begin(G), idf_end(G));
 }
 
 // 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) {}
   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
     : idf_iterator<T, SetTy, true>(V) {}
 };
 
 template <class T, class SetTy>

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();
   }
 };
 
 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();

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 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*> \
   : public GraphTraits<NodeT*> { \
   typedef df_iterator<NodeType*> nodes_iterator; \
   static NodeType *getEntryNode(RegionT* R) { \
     return R->getNode(R->getEntry()); \
   } \

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(); }
 };

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

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();
   }
 };
 
 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();
   }
 };
 
 } // End llvm namespace
 
 #endif

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

 };
 
 //===-------------------------------------
 // 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;
 
   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(); }