1193323Sed//===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file builds on the ADT/GraphTraits.h file to build generic depth 11193323Sed// first graph iterator. This file exposes the following functions/types: 12193323Sed// 13193323Sed// df_begin/df_end/df_iterator 14193323Sed// * Normal depth-first iteration - visit a node and then all of its children. 15193323Sed// 16193323Sed// idf_begin/idf_end/idf_iterator 17193323Sed// * Depth-first iteration on the 'inverse' graph. 18193323Sed// 19193323Sed// df_ext_begin/df_ext_end/df_ext_iterator 20193323Sed// * Normal depth-first iteration - visit a node and then all of its children. 21193323Sed// This iterator stores the 'visited' set in an external set, which allows 22193323Sed// it to be more efficient, and allows external clients to use the set for 23193323Sed// other purposes. 24193323Sed// 25193323Sed// idf_ext_begin/idf_ext_end/idf_ext_iterator 26193323Sed// * Depth-first iteration on the 'inverse' graph. 27193323Sed// This iterator stores the 'visited' set in an external set, which allows 28193323Sed// it to be more efficient, and allows external clients to use the set for 29193323Sed// other purposes. 30193323Sed// 31193323Sed//===----------------------------------------------------------------------===// 32193323Sed 33193323Sed#ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H 34193323Sed#define LLVM_ADT_DEPTHFIRSTITERATOR_H 35193323Sed 36193323Sed#include "llvm/ADT/GraphTraits.h" 37249423Sdim#include "llvm/ADT/PointerIntPair.h" 38193323Sed#include "llvm/ADT/SmallPtrSet.h" 39193323Sed#include <set> 40193323Sed#include <vector> 41193323Sed 42193323Sednamespace llvm { 43193323Sed 44193323Sed// df_iterator_storage - A private class which is used to figure out where to 45193323Sed// store the visited set. 46193323Sedtemplate<class SetType, bool External> // Non-external set 47193323Sedclass df_iterator_storage { 48193323Sedpublic: 49193323Sed SetType Visited; 50193323Sed}; 51193323Sed 52193323Sedtemplate<class SetType> 53193323Sedclass df_iterator_storage<SetType, true> { 54193323Sedpublic: 55193323Sed df_iterator_storage(SetType &VSet) : Visited(VSet) {} 56193323Sed df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} 57193323Sed SetType &Visited; 58193323Sed}; 59193323Sed 60193323Sed 61193323Sed// Generic Depth First Iterator 62193323Sedtemplate<class GraphT, 63193323Sedclass SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, 64193323Sed bool ExtStorage = false, class GT = GraphTraits<GraphT> > 65198090Srdivackyclass df_iterator : public std::iterator<std::forward_iterator_tag, 66198090Srdivacky typename GT::NodeType, ptrdiff_t>, 67193323Sed public df_iterator_storage<SetType, ExtStorage> { 68198090Srdivacky typedef std::iterator<std::forward_iterator_tag, 69198090Srdivacky typename GT::NodeType, ptrdiff_t> super; 70193323Sed 71193323Sed typedef typename GT::NodeType NodeType; 72193323Sed typedef typename GT::ChildIteratorType ChildItTy; 73198090Srdivacky typedef PointerIntPair<NodeType*, 1> PointerIntTy; 74193323Sed 75193323Sed // VisitStack - Used to maintain the ordering. Top = current block 76193323Sed // First element is node pointer, second is the 'next child' to visit 77198090Srdivacky // if the int in PointerIntTy is 0, the 'next child' to visit is invalid 78198090Srdivacky std::vector<std::pair<PointerIntTy, ChildItTy> > VisitStack; 79193323Sedprivate: 80193323Sed inline df_iterator(NodeType *Node) { 81193323Sed this->Visited.insert(Node); 82198090Srdivacky VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 83198090Srdivacky GT::child_begin(Node))); 84193323Sed } 85198090Srdivacky inline df_iterator() { 86198090Srdivacky // End is when stack is empty 87198090Srdivacky } 88193323Sed inline df_iterator(NodeType *Node, SetType &S) 89193323Sed : df_iterator_storage<SetType, ExtStorage>(S) { 90193323Sed if (!S.count(Node)) { 91198090Srdivacky VisitStack.push_back(std::make_pair(PointerIntTy(Node, 0), 92198090Srdivacky GT::child_begin(Node))); 93193323Sed this->Visited.insert(Node); 94193323Sed } 95193323Sed } 96193323Sed inline df_iterator(SetType &S) 97193323Sed : df_iterator_storage<SetType, ExtStorage>(S) { 98193323Sed // End is when stack is empty 99193323Sed } 100193323Sed 101198090Srdivacky inline void toNext() { 102198090Srdivacky do { 103198090Srdivacky std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back(); 104198090Srdivacky NodeType *Node = Top.first.getPointer(); 105198090Srdivacky ChildItTy &It = Top.second; 106198090Srdivacky if (!Top.first.getInt()) { 107198090Srdivacky // now retrieve the real begin of the children before we dive in 108198090Srdivacky It = GT::child_begin(Node); 109198090Srdivacky Top.first.setInt(1); 110198090Srdivacky } 111198090Srdivacky 112198090Srdivacky while (It != GT::child_end(Node)) { 113198090Srdivacky NodeType *Next = *It++; 114198090Srdivacky // Has our next sibling been visited? 115198090Srdivacky if (Next && !this->Visited.count(Next)) { 116198090Srdivacky // No, do it now. 117198090Srdivacky this->Visited.insert(Next); 118198090Srdivacky VisitStack.push_back(std::make_pair(PointerIntTy(Next, 0), 119198090Srdivacky GT::child_begin(Next))); 120198090Srdivacky return; 121198090Srdivacky } 122198090Srdivacky } 123198090Srdivacky 124198090Srdivacky // Oops, ran out of successors... go up a level on the stack. 125198090Srdivacky VisitStack.pop_back(); 126198090Srdivacky } while (!VisitStack.empty()); 127198090Srdivacky } 128198090Srdivacky 129193323Sedpublic: 130193323Sed typedef typename super::pointer pointer; 131193323Sed typedef df_iterator<GraphT, SetType, ExtStorage, GT> _Self; 132193323Sed 133193323Sed // Provide static begin and end methods as our public "constructors" 134193323Sed static inline _Self begin(const GraphT& G) { 135193323Sed return _Self(GT::getEntryNode(G)); 136193323Sed } 137193323Sed static inline _Self end(const GraphT& G) { return _Self(); } 138193323Sed 139193323Sed // Static begin and end methods as our public ctors for external iterators 140193323Sed static inline _Self begin(const GraphT& G, SetType &S) { 141193323Sed return _Self(GT::getEntryNode(G), S); 142193323Sed } 143193323Sed static inline _Self end(const GraphT& G, SetType &S) { return _Self(S); } 144193323Sed 145193323Sed inline bool operator==(const _Self& x) const { 146221345Sdim return VisitStack == x.VisitStack; 147193323Sed } 148193323Sed inline bool operator!=(const _Self& x) const { return !operator==(x); } 149193323Sed 150193323Sed inline pointer operator*() const { 151198090Srdivacky return VisitStack.back().first.getPointer(); 152193323Sed } 153193323Sed 154193323Sed // This is a nonstandard operator-> that dereferences the pointer an extra 155193323Sed // time... so that you can actually call methods ON the Node, because 156193323Sed // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 157193323Sed // 158193323Sed inline NodeType *operator->() const { return operator*(); } 159193323Sed 160193323Sed inline _Self& operator++() { // Preincrement 161198090Srdivacky toNext(); 162198090Srdivacky return *this; 163198090Srdivacky } 164193323Sed 165198090Srdivacky // skips all children of the current node and traverses to next node 166198090Srdivacky // 167198090Srdivacky inline _Self& skipChildren() { 168198090Srdivacky VisitStack.pop_back(); 169198090Srdivacky if (!VisitStack.empty()) 170198090Srdivacky toNext(); 171193323Sed return *this; 172193323Sed } 173193323Sed 174193323Sed inline _Self operator++(int) { // Postincrement 175193323Sed _Self tmp = *this; ++*this; return tmp; 176193323Sed } 177193323Sed 178193323Sed // nodeVisited - return true if this iterator has already visited the 179193323Sed // specified node. This is public, and will probably be used to iterate over 180193323Sed // nodes that a depth first iteration did not find: ie unreachable nodes. 181193323Sed // 182193323Sed inline bool nodeVisited(NodeType *Node) const { 183193323Sed return this->Visited.count(Node) != 0; 184193323Sed } 185212904Sdim 186212904Sdim /// getPathLength - Return the length of the path from the entry node to the 187212904Sdim /// current node, counting both nodes. 188212904Sdim unsigned getPathLength() const { return VisitStack.size(); } 189212904Sdim 190239462Sdim /// getPath - Return the n'th node in the path from the entry node to the 191212904Sdim /// current node. 192212904Sdim NodeType *getPath(unsigned n) const { 193212904Sdim return VisitStack[n].first.getPointer(); 194212904Sdim } 195193323Sed}; 196193323Sed 197193323Sed 198193323Sed// Provide global constructors that automatically figure out correct types... 199193323Sed// 200193323Sedtemplate <class T> 201193323Seddf_iterator<T> df_begin(const T& G) { 202193323Sed return df_iterator<T>::begin(G); 203193323Sed} 204193323Sed 205193323Sedtemplate <class T> 206193323Seddf_iterator<T> df_end(const T& G) { 207193323Sed return df_iterator<T>::end(G); 208193323Sed} 209193323Sed 210193323Sed// Provide global definitions of external depth first iterators... 211193323Sedtemplate <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 212193323Sedstruct df_ext_iterator : public df_iterator<T, SetTy, true> { 213193323Sed df_ext_iterator(const df_iterator<T, SetTy, true> &V) 214193323Sed : df_iterator<T, SetTy, true>(V) {} 215193323Sed}; 216193323Sed 217193323Sedtemplate <class T, class SetTy> 218193323Seddf_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { 219193323Sed return df_ext_iterator<T, SetTy>::begin(G, S); 220193323Sed} 221193323Sed 222193323Sedtemplate <class T, class SetTy> 223193323Seddf_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { 224193323Sed return df_ext_iterator<T, SetTy>::end(G, S); 225193323Sed} 226193323Sed 227193323Sed 228193323Sed// Provide global definitions of inverse depth first iterators... 229193323Sedtemplate <class T, 230193323Sed class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>, 231193323Sed bool External = false> 232193323Sedstruct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { 233193323Sed idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) 234193323Sed : df_iterator<Inverse<T>, SetTy, External>(V) {} 235193323Sed}; 236193323Sed 237193323Sedtemplate <class T> 238193323Sedidf_iterator<T> idf_begin(const T& G) { 239193323Sed return idf_iterator<T>::begin(Inverse<T>(G)); 240193323Sed} 241193323Sed 242193323Sedtemplate <class T> 243193323Sedidf_iterator<T> idf_end(const T& G){ 244193323Sed return idf_iterator<T>::end(Inverse<T>(G)); 245193323Sed} 246193323Sed 247193323Sed// Provide global definitions of external inverse depth first iterators... 248193323Sedtemplate <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 249193323Sedstruct idf_ext_iterator : public idf_iterator<T, SetTy, true> { 250193323Sed idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) 251193323Sed : idf_iterator<T, SetTy, true>(V) {} 252193323Sed idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) 253193323Sed : idf_iterator<T, SetTy, true>(V) {} 254193323Sed}; 255193323Sed 256193323Sedtemplate <class T, class SetTy> 257193323Sedidf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { 258193323Sed return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); 259193323Sed} 260193323Sed 261193323Sedtemplate <class T, class SetTy> 262193323Sedidf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { 263193323Sed return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); 264193323Sed} 265193323Sed 266193323Sed} // End llvm namespace 267193323Sed 268193323Sed#endif 269