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