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/None.h" 38 #include "llvm/ADT/Optional.h" 39 #include "llvm/ADT/SmallPtrSet.h" 40 #include "llvm/ADT/iterator_range.h" 41 #include <iterator> 42 #include <set> 43 #include <utility> 44 #include <vector> 45 46 namespace llvm { 47 48 // df_iterator_storage - A private class which is used to figure out where to 49 // store the visited set. 50 template<class SetType, bool External> // Non-external set 51 class df_iterator_storage { 52 public: 53 SetType Visited; 54 }; 55 56 template<class SetType> 57 class df_iterator_storage<SetType, true> { 58 public: 59 df_iterator_storage(SetType &VSet) : Visited(VSet) {} 60 df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {} 61 62 SetType &Visited; 63 }; 64 65 // The visited stated for the iteration is a simple set augmented with 66 // one more method, completed, which is invoked when all children of a 67 // node have been processed. It is intended to distinguish of back and 68 // cross edges in the spanning tree but is not used in the common case. 69 template <typename NodeRef, unsigned SmallSize=8> 70 struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> { 71 typedef SmallPtrSet<NodeRef, SmallSize> BaseSet; 72 typedef typename BaseSet::iterator iterator; 73 std::pair<iterator,bool> insert(NodeRef N) { return BaseSet::insert(N) ; } 74 template <typename IterT> 75 void insert(IterT Begin, IterT End) { BaseSet::insert(Begin,End); } 76 77 void completed(NodeRef) { } 78 }; 79 80 // Generic Depth First Iterator 81 template <class GraphT, 82 class SetType = 83 df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>, 84 bool ExtStorage = false, class GT = GraphTraits<GraphT>> 85 class df_iterator 86 : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>, 87 public df_iterator_storage<SetType, ExtStorage> { 88 typedef std::iterator<std::forward_iterator_tag, typename GT::NodeRef> super; 89 90 typedef typename GT::NodeRef NodeRef; 91 typedef typename GT::ChildIteratorType ChildItTy; 92 93 // First element is node reference, second is the 'next child' to visit. 94 // The second child is initialized lazily to pick up graph changes during the 95 // DFS. 96 typedef std::pair<NodeRef, Optional<ChildItTy>> StackElement; 97 98 // VisitStack - Used to maintain the ordering. Top = current block 99 std::vector<StackElement> VisitStack; 100 101 private: 102 inline df_iterator(NodeRef Node) { 103 this->Visited.insert(Node); 104 VisitStack.push_back(StackElement(Node, None)); 105 } 106 inline df_iterator() = default; // End is when stack is empty 107 inline df_iterator(NodeRef Node, SetType &S) 108 : df_iterator_storage<SetType, ExtStorage>(S) { 109 if (this->Visited.insert(Node).second) 110 VisitStack.push_back(StackElement(Node, None)); 111 } 112 inline df_iterator(SetType &S) 113 : df_iterator_storage<SetType, ExtStorage>(S) { 114 // End is when stack is empty 115 } 116 117 inline void toNext() { 118 do { 119 NodeRef Node = VisitStack.back().first; 120 Optional<ChildItTy> &Opt = VisitStack.back().second; 121 122 if (!Opt) 123 Opt.emplace(GT::child_begin(Node)); 124 125 // Notice that we directly mutate *Opt here, so that 126 // VisitStack.back().second actually gets updated as the iterator 127 // increases. 128 while (*Opt != GT::child_end(Node)) { 129 NodeRef Next = *(*Opt)++; 130 // Has our next sibling been visited? 131 if (this->Visited.insert(Next).second) { 132 // No, do it now. 133 VisitStack.push_back(StackElement(Next, None)); 134 return; 135 } 136 } 137 this->Visited.completed(Node); 138 139 // Oops, ran out of successors... go up a level on the stack. 140 VisitStack.pop_back(); 141 } while (!VisitStack.empty()); 142 } 143 144 public: 145 typedef typename super::pointer pointer; 146 147 // Provide static begin and end methods as our public "constructors" 148 static df_iterator begin(const GraphT &G) { 149 return df_iterator(GT::getEntryNode(G)); 150 } 151 static df_iterator end(const GraphT &G) { return df_iterator(); } 152 153 // Static begin and end methods as our public ctors for external iterators 154 static df_iterator begin(const GraphT &G, SetType &S) { 155 return df_iterator(GT::getEntryNode(G), S); 156 } 157 static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); } 158 159 bool operator==(const df_iterator &x) const { 160 return VisitStack == x.VisitStack; 161 } 162 bool operator!=(const df_iterator &x) const { return !(*this == x); } 163 164 const NodeRef &operator*() const { return VisitStack.back().first; } 165 166 // This is a nonstandard operator-> that dereferences the pointer an extra 167 // time... so that you can actually call methods ON the Node, because 168 // the contained type is a pointer. This allows BBIt->getTerminator() f.e. 169 // 170 NodeRef operator->() const { return **this; } 171 172 df_iterator &operator++() { // Preincrement 173 toNext(); 174 return *this; 175 } 176 177 /// \brief Skips all children of the current node and traverses to next node 178 /// 179 /// Note: This function takes care of incrementing the iterator. If you 180 /// always increment and call this function, you risk walking off the end. 181 df_iterator &skipChildren() { 182 VisitStack.pop_back(); 183 if (!VisitStack.empty()) 184 toNext(); 185 return *this; 186 } 187 188 df_iterator operator++(int) { // Postincrement 189 df_iterator tmp = *this; 190 ++*this; 191 return tmp; 192 } 193 194 // nodeVisited - return true if this iterator has already visited the 195 // specified node. This is public, and will probably be used to iterate over 196 // nodes that a depth first iteration did not find: ie unreachable nodes. 197 // 198 bool nodeVisited(NodeRef Node) const { 199 return this->Visited.count(Node) != 0; 200 } 201 202 /// getPathLength - Return the length of the path from the entry node to the 203 /// current node, counting both nodes. 204 unsigned getPathLength() const { return VisitStack.size(); } 205 206 /// getPath - Return the n'th node in the path from the entry node to the 207 /// current node. 208 NodeRef getPath(unsigned n) const { return VisitStack[n].first; } 209 }; 210 211 // Provide global constructors that automatically figure out correct types... 212 // 213 template <class T> 214 df_iterator<T> df_begin(const T& G) { 215 return df_iterator<T>::begin(G); 216 } 217 218 template <class T> 219 df_iterator<T> df_end(const T& G) { 220 return df_iterator<T>::end(G); 221 } 222 223 // Provide an accessor method to use them in range-based patterns. 224 template <class T> 225 iterator_range<df_iterator<T>> depth_first(const T& G) { 226 return make_range(df_begin(G), df_end(G)); 227 } 228 229 // Provide global definitions of external depth first iterators... 230 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>> 231 struct df_ext_iterator : public df_iterator<T, SetTy, true> { 232 df_ext_iterator(const df_iterator<T, SetTy, true> &V) 233 : df_iterator<T, SetTy, true>(V) {} 234 }; 235 236 template <class T, class SetTy> 237 df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) { 238 return df_ext_iterator<T, SetTy>::begin(G, S); 239 } 240 241 template <class T, class SetTy> 242 df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) { 243 return df_ext_iterator<T, SetTy>::end(G, S); 244 } 245 246 template <class T, class SetTy> 247 iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G, 248 SetTy &S) { 249 return make_range(df_ext_begin(G, S), df_ext_end(G, S)); 250 } 251 252 // Provide global definitions of inverse depth first iterators... 253 template <class T, 254 class SetTy = 255 df_iterator_default_set<typename GraphTraits<T>::NodeRef>, 256 bool External = false> 257 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> { 258 idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V) 259 : df_iterator<Inverse<T>, SetTy, External>(V) {} 260 }; 261 262 template <class T> 263 idf_iterator<T> idf_begin(const T& G) { 264 return idf_iterator<T>::begin(Inverse<T>(G)); 265 } 266 267 template <class T> 268 idf_iterator<T> idf_end(const T& G){ 269 return idf_iterator<T>::end(Inverse<T>(G)); 270 } 271 272 // Provide an accessor method to use them in range-based patterns. 273 template <class T> 274 iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) { 275 return make_range(idf_begin(G), idf_end(G)); 276 } 277 278 // Provide global definitions of external inverse depth first iterators... 279 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>> 280 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> { 281 idf_ext_iterator(const idf_iterator<T, SetTy, true> &V) 282 : idf_iterator<T, SetTy, true>(V) {} 283 idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V) 284 : idf_iterator<T, SetTy, true>(V) {} 285 }; 286 287 template <class T, class SetTy> 288 idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) { 289 return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S); 290 } 291 292 template <class T, class SetTy> 293 idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) { 294 return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S); 295 } 296 297 template <class T, class SetTy> 298 iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G, 299 SetTy &S) { 300 return make_range(idf_ext_begin(G, S), idf_ext_end(G, S)); 301 } 302 303 } // end namespace llvm 304 305 #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H 306