Index: llvm/trunk/include/llvm/ADT/DepthFirstIterator.h =================================================================== --- llvm/trunk/include/llvm/ADT/DepthFirstIterator.h +++ llvm/trunk/include/llvm/ADT/DepthFirstIterator.h @@ -34,7 +34,7 @@ #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 @@ -59,38 +59,42 @@ }; // Generic Depth First Iterator -template::NodeType*, 8>, - bool ExtStorage = false, class GT = GraphTraits > -class df_iterator : public std::iterator, - public df_iterator_storage { - typedef std::iterator super; +template ::NodeRef, 8>, + bool ExtStorage = false, class GT = GraphTraits> +class df_iterator + : public std::iterator, + public df_iterator_storage { + typedef std::iterator + super; - typedef typename GT::NodeType NodeType; + typedef typename GT::NodeRef NodeRef; typedef typename GT::ChildIteratorType ChildItTy; - typedef PointerIntPair 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> 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> VisitStack; + std::vector 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(S) { + inline df_iterator(NodeRef Node, SetType &S) + : df_iterator_storage(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 +105,17 @@ inline void toNext() { do { - std::pair &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 &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; } } @@ -146,13 +145,13 @@ } 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 +179,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 +189,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 +211,7 @@ } // Provide global definitions of external depth first iterators... -template ::NodeType*> > +template ::NodeRef>> struct df_ext_iterator : public df_iterator { df_ext_iterator(const df_iterator &V) : df_iterator(V) {} @@ -238,7 +235,7 @@ // Provide global definitions of inverse depth first iterators... template ::NodeType*, 8>, + class SetTy = llvm::SmallPtrSet::NodeRef, 8>, bool External = false> struct idf_iterator : public df_iterator, SetTy, External> { idf_iterator(const df_iterator, SetTy, External> &V) @@ -262,7 +259,7 @@ } // Provide global definitions of external inverse depth first iterators... -template ::NodeType*> > +template ::NodeRef>> struct idf_ext_iterator : public idf_iterator { idf_ext_iterator(const idf_iterator &V) : idf_iterator(V) {} Index: llvm/trunk/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LoopInfo.h +++ llvm/trunk/include/llvm/Analysis/LoopInfo.h @@ -762,6 +762,7 @@ // Allow clients to walk the list of nested loops... template <> struct GraphTraits { 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 { typedef Loop NodeType; + typedef Loop *NodeRef; typedef LoopInfo::iterator ChildIteratorType; static NodeType *getEntryNode(Loop *L) { return L; } Index: llvm/trunk/include/llvm/Analysis/RegionIterator.h =================================================================== --- llvm/trunk/include/llvm/Analysis/RegionIterator.h +++ llvm/trunk/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 { \ - typedef NodeT NodeType; \ - typedef RNSuccIterator ChildIteratorType; \ - static NodeType *getEntryNode(NodeType* N) { return N; } \ - static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator(N); \ - } \ - static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator(N, true); \ - } \ -}; \ -template<> struct GraphTraits> { \ - typedef NodeT NodeType; \ - typedef RNSuccIterator, BlockT, RegionT > ChildIteratorType; \ - static NodeType *getEntryNode(NodeType* N) { return N; } \ - static inline ChildIteratorType child_begin(NodeType *N) { \ - return RNSuccIterator, BlockT, RegionT>(N); \ - } \ - static inline ChildIteratorType child_end(NodeType *N) { \ - return RNSuccIterator, BlockT, RegionT>(N, true); \ - } \ -} +#define RegionNodeGraphTraits(NodeT, BlockT, RegionT) \ + template <> struct GraphTraits { \ + typedef NodeT NodeType; \ + typedef NodeT *NodeRef; \ + typedef RNSuccIterator ChildIteratorType; \ + static NodeType *getEntryNode(NodeType *N) { return N; } \ + static inline ChildIteratorType child_begin(NodeType *N) { \ + return RNSuccIterator(N); \ + } \ + static inline ChildIteratorType child_end(NodeType *N) { \ + return RNSuccIterator(N, true); \ + } \ + }; \ + template <> struct GraphTraits> { \ + typedef NodeT NodeType; \ + typedef NodeT *NodeRef; \ + typedef RNSuccIterator, BlockT, RegionT> ChildIteratorType; \ + static NodeType *getEntryNode(NodeType *N) { return N; } \ + static inline ChildIteratorType child_begin(NodeType *N) { \ + return RNSuccIterator, BlockT, RegionT>(N); \ + } \ + static inline ChildIteratorType child_end(NodeType *N) { \ + return RNSuccIterator, BlockT, RegionT>(N, true); \ + } \ + } #define RegionGraphTraits(RegionT, NodeT) \ template<> struct GraphTraits \ Index: llvm/trunk/include/llvm/CodeGen/MachineDominators.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachineDominators.h +++ llvm/trunk/include/llvm/CodeGen/MachineDominators.h @@ -272,6 +272,7 @@ template struct MachineDomTreeGraphTraitsBase { typedef Node NodeType; + typedef Node *NodeRef; typedef ChildIterator ChildIteratorType; static NodeType *getEntryNode(NodeType *N) { return N; } Index: llvm/trunk/include/llvm/CodeGen/MachineLoopInfo.h =================================================================== --- llvm/trunk/include/llvm/CodeGen/MachineLoopInfo.h +++ llvm/trunk/include/llvm/CodeGen/MachineLoopInfo.h @@ -149,6 +149,7 @@ // Allow clients to walk the list of nested loops... template <> struct GraphTraits { 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 { typedef MachineLoop NodeType; + typedef MachineLoop *NodeRef; typedef MachineLoopInfo::iterator ChildIteratorType; static NodeType *getEntryNode(MachineLoop *L) { return L; } Index: llvm/trunk/include/llvm/IR/Dominators.h =================================================================== --- llvm/trunk/include/llvm/IR/Dominators.h +++ llvm/trunk/include/llvm/IR/Dominators.h @@ -156,6 +156,7 @@ template struct DomTreeGraphTraitsBase { typedef Node NodeType; + typedef Node *NodeRef; typedef ChildIterator ChildIteratorType; typedef df_iterator> nodes_iterator;