1 //===- llvm/ADT/DepthFirstIterator.h - Depth First iterator -----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file builds on the ADT/GraphTraits.h file to build generic depth 11 // first graph iterator. This file exposes the following functions/types: 12 // 13 // df_begin/df_end/df_iterator 14 // * Normal depth-first iteration - visit a node and then all of its children. 15 // 16 // idf_begin/idf_end/idf_iterator 17 // * Depth-first iteration on the 'inverse' graph. 18 // 19 // df_ext_begin/df_ext_end/df_ext_iterator 20 // * Normal depth-first iteration - visit a node and then all of its children. 21 // This iterator stores the 'visited' set in an external set, which allows 22 // it to be more efficient, and allows external clients to use the set for 23 // other purposes. 24 // 25 // idf_ext_begin/idf_ext_end/idf_ext_iterator 26 // * Depth-first iteration on the 'inverse' graph. 27 // This iterator stores the 'visited' set in an external set, which allows 28 // it to be more efficient, and allows external clients to use the set for 29 // other purposes. 30 // 31 //===----------------------------------------------------------------------===// 32 33 #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H 34 #define LLVM_ADT_DEPTHFIRSTITERATOR_H 35 36 #include "llvm/ADT/GraphTraits.h" 37 #include "llvm/ADT/PointerIntPair.h" 38 #include "llvm/ADT/SmallPtrSet.h" 39 #include "llvm/ADT/iterator_range.h" 40 #include <set> 41 #include <vector> 42 43 namespace llvm { 44 45 // df_iterator_storage - A private class which is used to figure out where to 46 // store the visited set. 47 template<class SetType, bool External> // Non-external set 48 class df_iterator_storage { 49 public: 50 SetType Visited; 51 }; 52 53 template<class SetType> 54 class df_iterator_storage<SetType, true> { 55 public: 56 df_iterator_storage(SetType &VSet) : Visited(VSet) {} 57 df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} 58 SetType &Visited; 59 }; 60 61 // Generic Depth First Iterator 62 template<class GraphT, 63 class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>, 64 bool ExtStorage = false, class GT = GraphTraits<GraphT> > 65 class df_iterator : public std::iterator<std::forward_iterator_tag, 66 typename GT::NodeType, ptrdiff_t>, 67 public df_iterator_storage<SetType, ExtStorage> { 68 typedef std::iterator<std::forward_iterator_tag, 69 typename GT::NodeType, ptrdiff_t> super; 70 71 typedef typename GT::NodeType NodeType; 72 typedef typename GT::ChildIteratorType ChildItTy; 73 typedef PointerIntPair<NodeType*, 1> PointerIntTy; 74 75 // VisitStack - Used to maintain the ordering. Top = current block 76 // First element is node pointer, second is the 'next child' to visit 77 // if the int in PointerIntTy is 0, the 'next child' to visit is invalid 78 std::vector<std::pair<PointerIntTy, ChildItTy>> VisitStack; 79 80 private: 81 inline df_iterator(NodeType *Node) { 82 this->Visited.insert(Node); 83 VisitStack.push_back( 84 std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node))); 85 } 86 inline df_iterator() { 87 // End is when stack is empty 88 } 89 inline df_iterator(NodeType *Node, SetType &S) 90 : df_iterator_storage<SetType, ExtStorage>(S) { 91 if (!S.count(Node)) { 92 VisitStack.push_back( 93 std::make_pair(PointerIntTy(Node, 0), GT::child_begin(Node))); 94 this->Visited.insert(Node); 95 } 96 } 97 inline df_iterator(SetType &S) 98 : df_iterator_storage<SetType, ExtStorage>(S) { 99 // End is when stack is empty 100 } 101 102 inline void toNext() { 103 do { 104 std::pair<PointerIntTy, ChildItTy> &Top = VisitStack.back(); 105 NodeType *Node = Top.first.getPointer(); 106 ChildItTy &It = Top.second; 107 if (!Top.first.getInt()) { 108 // now retrieve the real begin of the children before we dive in 109 It = GT::child_begin(Node); 110 Top.first.setInt(1); 111 } 112 113 while (It != GT::child_end(Node)) { 114 NodeType *Next = *It++; 115 // Has our next sibling been visited? 116 if (Next && this->Visited.insert(Next).second) { 117 // No, do it now. 118 VisitStack.push_back( 119 std::make_pair(PointerIntTy(Next, 0), GT::child_begin(Next))); 120 return; 121 } 122 } 123 124 // Oops, ran out of successors... go up a level on the stack. 125 VisitStack.pop_back(); 126 } while (!VisitStack.empty()); 127 } 128 129 public: 130 typedef typename super::pointer pointer; 131 132 // Provide static begin and end methods as our public "constructors" 133 static df_iterator begin(const GraphT &G) { 134 return df_iterator(GT::getEntryNode(G)); 135 } 136 static df_iterator end(const GraphT &G) { return df_iterator(); } 137 138 // Static begin and end methods as our public ctors for external iterators 139 static df_iterator begin(const GraphT &G, SetType &S) { 140 return df_iterator(GT::getEntryNode(G), S); 141 } 142 static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); } 143 144 bool operator==(const df_iterator &x) const { 145 return VisitStack == x.VisitStack; 146 } 147 bool operator!=(const df_iterator &x) const { return !(*this == x); } 148 149 pointer operator*() const { return VisitStack.back().first.getPointer(); } 150 151 // This is a nonstandard operator-> that dereferences the pointer an extra 152 // time... so that you can actually call methods ON the Node, because 153 // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 154 // 155 NodeType *operator->() const { return **this; } 156 157 df_iterator &operator++() { // Preincrement 158 toNext(); 159 return *this; 160 } 161 162 /// \brief Skips all children of the current node and traverses to next node 163 /// 164 /// Note: This function takes care of incrementing the iterator. If you 165 /// always increment and call this function, you risk walking off the end. 166 df_iterator &skipChildren() { 167 VisitStack.pop_back(); 168 if (!VisitStack.empty()) 169 toNext(); 170 return *this; 171 } 172 173 df_iterator operator++(int) { // Postincrement 174 df_iterator tmp = *this; 175 ++*this; 176 return tmp; 177 } 178 179 // nodeVisited - return true if this iterator has already visited the 180 // specified node. This is public, and will probably be used to iterate over 181 // nodes that a depth first iteration did not find: ie unreachable nodes. 182 // 183 bool nodeVisited(NodeType *Node) const { 184 return this->Visited.count(Node) != 0; 185 } 186 187 /// getPathLength - Return the length of the path from the entry node to the 188 /// current node, counting both nodes. 189 unsigned getPathLength() const { return VisitStack.size(); } 190 191 /// getPath - Return the n'th node in the path from the entry node to the 192 /// current node. 193 NodeType *getPath(unsigned n) const { 194 return VisitStack[n].first.getPointer(); 195 } 196 }; 197 198 // Provide global constructors that automatically figure out correct types... 199 // 200 template <class T> 201 df_iterator<T> df_begin(const T& G) { 202 return df_iterator<T>::begin(G); 203 } 204 205 template <class T> 206 df_iterator<T> df_end(const T& G) { 207 return df_iterator<T>::end(G); 208 } 209 210 // Provide an accessor method to use them in range-based patterns. 211 template <class T> 212 iterator_range<df_iterator<T>> depth_first(const T& G) { 213 return make_range(df_begin(G), df_end(G)); 214 } 215 216 // Provide global definitions of external depth first iterators... 217 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 218 struct df_ext_iterator : public df_iterator<T, SetTy, true> { 219 df_ext_iterator(const df_iterator<T, SetTy, true> &V) 220 : df_iterator<T, SetTy, true>(V) {} 221 }; 222 223 template <class T, class SetTy> 224 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { 225 return df_ext_iterator<T, SetTy>::begin(G, S); 226 } 227 228 template <class T, class SetTy> 229 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { 230 return df_ext_iterator<T, SetTy>::end(G, S); 231 } 232 233 template <class T, class SetTy> 234 iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G, 235 SetTy &S) { 236 return make_range(df_ext_begin(G, S), df_ext_end(G, S)); 237 } 238 239 // Provide global definitions of inverse depth first iterators... 240 template <class T, 241 class SetTy = llvm::SmallPtrSet<typename GraphTraits<T>::NodeType*, 8>, 242 bool External = false> 243 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { 244 idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) 245 : df_iterator<Inverse<T>, SetTy, External>(V) {} 246 }; 247 248 template <class T> 249 idf_iterator<T> idf_begin(const T& G) { 250 return idf_iterator<T>::begin(Inverse<T>(G)); 251 } 252 253 template <class T> 254 idf_iterator<T> idf_end(const T& G){ 255 return idf_iterator<T>::end(Inverse<T>(G)); 256 } 257 258 // Provide an accessor method to use them in range-based patterns. 259 template <class T> 260 iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { 261 return make_range(idf_begin(G), idf_end(G)); 262 } 263 264 // Provide global definitions of external inverse depth first iterators... 265 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeType*> > 266 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> { 267 idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) 268 : idf_iterator<T, SetTy, true>(V) {} 269 idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) 270 : idf_iterator<T, SetTy, true>(V) {} 271 }; 272 273 template <class T, class SetTy> 274 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { 275 return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); 276 } 277 278 template <class T, class SetTy> 279 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { 280 return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); 281 } 282 283 template <class T, class SetTy> 284 iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G, 285 SetTy &S) { 286 return make_range(idf_ext_begin(G, S), idf_ext_end(G, S)); 287 } 288 289 } // End llvm namespace 290 291 #endif 292