LLVM  6.0.0svn
DepthFirstIterator.h
Go to the documentation of this file.
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"
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
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) {}
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> {
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 =
85  bool ExtStorage = false, class GT = GraphTraits<GraphT>>
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  inline df_iterator(NodeRef Node) {
103  this->Visited.insert(Node);
104  VisitStack.push_back(StackElement(Node, None));
105  }
106 
107  inline df_iterator() = default; // End is when stack is empty
108 
109  inline df_iterator(NodeRef Node, SetType &S)
111  if (this->Visited.insert(Node).second)
112  VisitStack.push_back(StackElement(Node, None));
113  }
114 
115  inline df_iterator(SetType &S)
117  // End is when stack is empty
118  }
119 
120  inline void toNext() {
121  do {
122  NodeRef Node = VisitStack.back().first;
123  Optional<ChildItTy> &Opt = VisitStack.back().second;
124 
125  if (!Opt)
126  Opt.emplace(GT::child_begin(Node));
127 
128  // Notice that we directly mutate *Opt here, so that
129  // VisitStack.back().second actually gets updated as the iterator
130  // increases.
131  while (*Opt != GT::child_end(Node)) {
132  NodeRef Next = *(*Opt)++;
133  // Has our next sibling been visited?
134  if (this->Visited.insert(Next).second) {
135  // No, do it now.
136  VisitStack.push_back(StackElement(Next, None));
137  return;
138  }
139  }
140  this->Visited.completed(Node);
141 
142  // Oops, ran out of successors... go up a level on the stack.
143  VisitStack.pop_back();
144  } while (!VisitStack.empty());
145  }
146 
147 public:
148  using pointer = typename super::pointer;
149 
150  // Provide static begin and end methods as our public "constructors"
151  static df_iterator begin(const GraphT &G) {
152  return df_iterator(GT::getEntryNode(G));
153  }
154  static df_iterator end(const GraphT &G) { return df_iterator(); }
155 
156  // Static begin and end methods as our public ctors for external iterators
157  static df_iterator begin(const GraphT &G, SetType &S) {
158  return df_iterator(GT::getEntryNode(G), S);
159  }
160  static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
161 
162  bool operator==(const df_iterator &x) const {
163  return VisitStack == x.VisitStack;
164  }
165  bool operator!=(const df_iterator &x) const { return !(*this == x); }
166 
167  const NodeRef &operator*() const { return VisitStack.back().first; }
168 
169  // This is a nonstandard operator-> that dereferences the pointer an extra
170  // 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  //
173  NodeRef operator->() const { return **this; }
174 
175  df_iterator &operator++() { // Preincrement
176  toNext();
177  return *this;
178  }
179 
180  /// \brief Skips all children of the current node and traverses to next node
181  ///
182  /// Note: This function takes care of incrementing the iterator. If you
183  /// always increment and call this function, you risk walking off the end.
185  VisitStack.pop_back();
186  if (!VisitStack.empty())
187  toNext();
188  return *this;
189  }
190 
191  df_iterator operator++(int) { // Postincrement
192  df_iterator tmp = *this;
193  ++*this;
194  return tmp;
195  }
196 
197  // nodeVisited - return true if this iterator has already visited the
198  // specified node. This is public, and will probably be used to iterate over
199  // nodes that a depth first iteration did not find: ie unreachable nodes.
200  //
201  bool nodeVisited(NodeRef Node) const {
202  return this->Visited.count(Node) != 0;
203  }
204 
205  /// getPathLength - Return the length of the path from the entry node to the
206  /// current node, counting both nodes.
207  unsigned getPathLength() const { return VisitStack.size(); }
208 
209  /// getPath - Return the n'th node in the path from the entry node to the
210  /// current node.
211  NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
212 };
213 
214 // Provide global constructors that automatically figure out correct types...
215 //
216 template <class T>
218  return df_iterator<T>::begin(G);
219 }
220 
221 template <class T>
223  return df_iterator<T>::end(G);
224 }
225 
226 // Provide an accessor method to use them in range-based patterns.
227 template <class T>
229  return make_range(df_begin(G), df_end(G));
230 }
231 
232 // Provide global definitions of external depth first iterators...
233 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
234 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
236  : df_iterator<T, SetTy, true>(V) {}
237 };
238 
239 template <class T, class SetTy>
242 }
243 
244 template <class T, class SetTy>
246  return df_ext_iterator<T, SetTy>::end(G, S);
247 }
248 
249 template <class T, class SetTy>
251  SetTy &S) {
252  return make_range(df_ext_begin(G, S), df_ext_end(G, S));
253 }
254 
255 // Provide global definitions of inverse depth first iterators...
256 template <class T,
257  class SetTy =
259  bool External = false>
260 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>
268 }
269 
270 template <class T>
272  return idf_iterator<T>::end(Inverse<T>(G));
273 }
274 
275 // Provide an accessor method to use them in range-based patterns.
276 template <class T>
278  return make_range(idf_begin(G), idf_end(G));
279 }
280 
281 // Provide global definitions of external inverse depth first iterators...
282 template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
283 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
285  : idf_iterator<T, SetTy, true>(V) {}
286  idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
287  : idf_iterator<T, SetTy, true>(V) {}
288 };
289 
290 template <class T, class SetTy>
293 }
294 
295 template <class T, class SetTy>
298 }
299 
300 template <class T, class SetTy>
302  SetTy &S) {
303  return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
304 }
305 
306 } // end namespace llvm
307 
308 #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H
NodeRef operator->() const
bool operator==(const df_iterator &x) const
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
const NodeRef & operator*() const
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
void insert(IterT Begin, IterT End)
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
bool operator!=(const df_iterator &x) const
df_iterator & skipChildren()
Skips all children of the current node and traverses to next node.
NodeRef getPath(unsigned n) const
getPath - Return the n&#39;th node in the path from the entry node to the current node.
static df_iterator end(const GraphT &G)
unsigned getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node, counting both nodes.
idf_iterator(const df_iterator< Inverse< T >, SetTy, External > &V)
#define T
idf_iterator< T > idf_begin(const T &G)
idf_iterator< T > idf_end(const T &G)
SmallPtrSet< typename GraphTraits< std::conditional< IsConst, const BlockT, BlockT >::type * >::NodeRef, 8 > BaseSet
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
df_iterator< T > df_end(const T &G)
idf_ext_iterator< T, SetTy > idf_ext_end(const T &G, SetTy &S)
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
static const unsigned End
idf_ext_iterator(const idf_iterator< T, SetTy, true > &V)
static df_iterator begin(const GraphT &G)
idf_ext_iterator< T, SetTy > idf_ext_begin(const T &G, SetTy &S)
static df_iterator end(const GraphT &G, SetType &S)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
df_ext_iterator(const df_iterator< T, SetTy, true > &V)
iterator_range< idf_iterator< T > > inverse_depth_first(const T &G)
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:423
df_iterator operator++(int)
const DataFlowGraph & G
Definition: RDFGraph.cpp:206
df_iterator_storage(const df_iterator_storage &S)
const size_t N
std::pair< iterator, bool > insert(NodeRef N)
df_iterator< T > df_begin(const T &G)
bool nodeVisited(NodeRef Node) const
A range adaptor for a pair of iterators.
Basic Alias true
iterator_range< df_iterator< T > > depth_first(const T &G)
df_iterator & operator++()
idf_ext_iterator(const df_iterator< Inverse< T >, SetTy, true > &V)
static df_iterator begin(const GraphT &G, SetType &S)
void emplace(ArgTypes &&...Args)
Create a new object by constructing it in place with the given arguments.
Definition: Optional.h:87