Line data Source code
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 2771617 : df_iterator_storage(SetType &VSet) : Visited(VSet) {}
60 5386469 : 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 1872511 : struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> {
71 : using BaseSet = SmallPtrSet<NodeRef, SmallSize>;
72 : using iterator = typename BaseSet::iterator;
73 :
74 4928797 : 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 0 : 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 1931647 : class df_iterator
87 : : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
88 : public df_iterator_storage<SetType, ExtStorage> {
89 : using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
90 : using NodeRef = typename GT::NodeRef;
91 : using ChildItTy = typename GT::ChildIteratorType;
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 : using StackElement = std::pair<NodeRef, Optional<ChildItTy>>;
97 :
98 : // VisitStack - Used to maintain the ordering. Top = current block
99 : std::vector<StackElement> VisitStack;
100 :
101 : private:
102 1152310 : inline df_iterator(NodeRef Node) {
103 576155 : this->Visited.insert(Node);
104 576156 : VisitStack.push_back(StackElement(Node, None));
105 576156 : }
106 466 :
107 233 : inline df_iterator() = default; // End is when stack is empty
108 233 :
109 2772143 : inline df_iterator(NodeRef Node, SetType &S)
110 2816950 : : df_iterator_storage<SetType, ExtStorage>(S) {
111 2794431 : if (this->Visited.insert(Node).second)
112 2794349 : VisitStack.push_back(StackElement(Node, None));
113 2794431 : }
114 210830 :
115 210040 : inline df_iterator(SetType &S)
116 210041 : : df_iterator_storage<SetType, ExtStorage>(S) {
117 210040 : // End is when stack is empty
118 223494 : }
119 443757 :
120 8958605 : inline void toNext() {
121 443757 : do {
122 14768837 : NodeRef Node = VisitStack.back().first;
123 436635 : Optional<ChildItTy> &Opt = VisitStack.back().second;
124 :
125 14332202 : if (!Opt)
126 19629 : Opt.emplace(GT::child_begin(Node));
127 :
128 4121 : // Notice that we directly mutate *Opt here, so that
129 : // VisitStack.back().second actually gets updated as the iterator
130 3736901 : // increases.
131 16184338 : while (*Opt != GT::child_end(Node)) {
132 12571958 : NodeRef Next = *(*Opt)++;
133 5776 : // Has our next sibling been visited?
134 7680376 : if (this->Visited.insert(Next).second) {
135 6816364 : // No, do it now.
136 5818813 : VisitStack.push_back(StackElement(Next, None));
137 9422 : return;
138 28 : }
139 11732 : }
140 274237 : this->Visited.completed(Node);
141 7793123 :
142 359958 : // Oops, ran out of successors... go up a level on the stack.
143 9442 : VisitStack.pop_back();
144 12581022 : } while (!VisitStack.empty());
145 : }
146 3293521 :
147 38 : public:
148 302218 : using pointer = typename super::pointer;
149 :
150 20 : // Provide static begin and end methods as our public "constructors"
151 297894 : static df_iterator begin(const GraphT &G) {
152 67018 : return df_iterator(GT::getEntryNode(G));
153 : }
154 3780179 : static df_iterator end(const GraphT &G) { return df_iterator(); }
155 :
156 480548 : // Static begin and end methods as our public ctors for external iterators
157 303639 : static df_iterator begin(const GraphT &G, SetType &S) {
158 839296 : return df_iterator(GT::getEntryNode(G), S);
159 53 : }
160 108509 : static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
161 741535 :
162 93962 : bool operator==(const df_iterator &x) const {
163 10482470 : return VisitStack == x.VisitStack;
164 0 : }
165 19 : bool operator!=(const df_iterator &x) const { return !(*this == x); }
166 20 :
167 833509 : const NodeRef &operator*() const { return VisitStack.back().first; }
168 358118 :
169 8766 : // This is a nonstandard operator-> that dereferences the pointer an extra
170 566036 : // time... so that you can actually call methods ON the Node, because
171 : // the contained type is a pointer. This allows BBIt->getTerminator() f.e.
172 548338 : //
173 0 : NodeRef operator->() const { return **this; }
174 514818 :
175 : df_iterator &operator++() { // Preincrement
176 7968115 : toNext();
177 510828 : return *this;
178 5796 : }
179 :
180 479477 : /// Skips all children of the current node and traverses to next node
181 : ///
182 3266231 : /// Note: This function takes care of incrementing the iterator. If you
183 595471 : /// always increment and call this function, you risk walking off the end.
184 6079751 : df_iterator &skipChildren() {
185 5723 : VisitStack.pop_back();
186 319852 : if (!VisitStack.empty())
187 6075499 : toNext();
188 232662 : return *this;
189 656 : }
190 12 :
191 11713 : df_iterator operator++(int) { // Postincrement
192 274217 : df_iterator tmp = *this;
193 6959616 : ++*this;
194 1840 : return tmp;
195 676 : }
196 3983685 :
197 : // nodeVisited - return true if this iterator has already visited the
198 2819447 : // specified node. This is public, and will probably be used to iterate over
199 12 : // nodes that a depth first iteration did not find: ie unreachable nodes.
200 334 : //
201 : bool nodeVisited(NodeRef Node) const {
202 1282 : return this->Visited.count(Node) != 0;
203 0 : }
204 4088 :
205 : /// getPathLength - Return the length of the path from the entry node to the
206 3255732 : /// current node, counting both nodes.
207 10305126 : unsigned getPathLength() const { return VisitStack.size(); }
208 326 :
209 0 : /// getPath - Return the n'th node in the path from the entry node to the
210 0 : /// current node.
211 6560376 : NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
212 34 : };
213 :
214 10 : // Provide global constructors that automatically figure out correct types...
215 659354 : //
216 16 : template <class T>
217 0 : df_iterator<T> df_begin(const T& G) {
218 0 : return df_iterator<T>::begin(G);
219 16 : }
220 26 :
221 0 : template <class T>
222 0 : df_iterator<T> df_end(const T& G) {
223 0 : return df_iterator<T>::end(G);
224 0 : }
225 13896 :
226 0 : // Provide an accessor method to use them in range-based patterns.
227 : template <class T>
228 527860 : iterator_range<df_iterator<T>> depth_first(const T& G) {
229 63331 : return make_range(df_begin(G), df_end(G));
230 6 : }
231 4377011 :
232 : // Provide global definitions of external depth first iterators...
233 : template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
234 2289704 : struct df_ext_iterator : public df_iterator<T, SetTy, true> {
235 : df_ext_iterator(const df_iterator<T, SetTy, true> &V)
236 : : df_iterator<T, SetTy, true>(V) {}
237 : };
238 10 :
239 19 : template <class T, class SetTy>
240 0 : df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
241 0 : return df_ext_iterator<T, SetTy>::begin(G, S);
242 4121 : }
243 :
244 3731124 : template <class T, class SetTy>
245 0 : df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
246 26892 : return df_ext_iterator<T, SetTy>::end(G, S);
247 0 : }
248 0 :
249 0 : template <class T, class SetTy>
250 207769 : iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
251 0 : SetTy &S) {
252 207769 : return make_range(df_ext_begin(G, S), df_ext_end(G, S));
253 : }
254 0 :
255 0 : // Provide global definitions of inverse depth first iterators...
256 : template <class T,
257 0 : class SetTy =
258 0 : df_iterator_default_set<typename GraphTraits<T>::NodeRef>,
259 7729 : bool External = false>
260 19766 : struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
261 : idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
262 : : df_iterator<Inverse<T>, SetTy, External>(V) {}
263 : };
264 :
265 : template <class T>
266 : idf_iterator<T> idf_begin(const T& G) {
267 : return idf_iterator<T>::begin(Inverse<T>(G));
268 : }
269 4262 :
270 0 : template <class T>
271 : idf_iterator<T> idf_end(const T& G){
272 6115 : return idf_iterator<T>::end(Inverse<T>(G));
273 : }
274 0 :
275 0 : // Provide an accessor method to use them in range-based patterns.
276 : template <class T>
277 : iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
278 : return make_range(idf_begin(G), idf_end(G));
279 : }
280 0 :
281 0 : // Provide global definitions of external inverse depth first iterators...
282 3861 : template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
283 891 : struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
284 0 : idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
285 : : idf_iterator<T, SetTy, true>(V) {}
286 87596 : idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
287 0 : : idf_iterator<T, SetTy, true>(V) {}
288 0 : };
289 0 :
290 0 : template <class T, class SetTy>
291 0 : idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
292 0 : return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
293 0 : }
294 0 :
295 0 : template <class T, class SetTy>
296 0 : idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
297 0 : return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
298 0 : }
299 :
300 0 : template <class T, class SetTy>
301 292 : iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
302 1335570 : SetTy &S) {
303 292 : return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
304 43798 : }
305 :
306 0 : } // end namespace llvm
307 0 :
308 0 : #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H
|
