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