LLVM  14.0.0git
DepthFirstIterator.h
Go to the documentation of this file.
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"
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
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) {}
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> {
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 =
84  bool ExtStorage = false, class GT = GraphTraits<GraphT>>
85 class df_iterator : public df_iterator_storage<SetType, ExtStorage> {
86 public:
87  using iterator_category = std::forward_iterator_tag;
88  using value_type = typename GT::NodeRef;
89  using difference_type = std::ptrdiff_t;
90  using pointer = value_type *;
91  using reference = value_type &;
92 
93 private:
94  using NodeRef = typename GT::NodeRef;
95  using ChildItTy = typename GT::ChildIteratorType;
96 
97  // First element is node reference, second is the 'next child' to visit.
98  // The second child is initialized lazily to pick up graph changes during the
99  // DFS.
100  using StackElement = std::pair<NodeRef, Optional<ChildItTy>>;
101 
102  // VisitStack - Used to maintain the ordering. Top = current block
103  std::vector<StackElement> VisitStack;
104 
105  inline df_iterator(NodeRef Node) {
106  this->Visited.insert(Node);
107  VisitStack.push_back(StackElement(Node, None));
108  }
109 
110  inline df_iterator() = default; // End is when stack is empty
111 
112  inline df_iterator(NodeRef Node, SetType &S)
113  : df_iterator_storage<SetType, ExtStorage>(S) {
114  if (this->Visited.insert(Node).second)
115  VisitStack.push_back(StackElement(Node, None));
116  }
117 
118  inline df_iterator(SetType &S)
119  : df_iterator_storage<SetType, ExtStorage>(S) {
120  // End is when stack is empty
121  }
122 
123  inline void toNext() {
124  do {
125  NodeRef Node = VisitStack.back().first;
126  Optional<ChildItTy> &Opt = VisitStack.back().second;
127 
128  if (!Opt)
129  Opt.emplace(GT::child_begin(Node));
130 
131  // Notice that we directly mutate *Opt here, so that
132  // VisitStack.back().second actually gets updated as the iterator
133  // increases.
134  while (*Opt != GT::child_end(Node)) {
135  NodeRef Next = *(*Opt)++;
136  // Has our next sibling been visited?
137  if (this->Visited.insert(Next).second) {
138  // No, do it now.
139  VisitStack.push_back(StackElement(Next, None));
140  return;
141  }
142  }
143  this->Visited.completed(Node);
144 
145  // Oops, ran out of successors... go up a level on the stack.
146  VisitStack.pop_back();
147  } while (!VisitStack.empty());
148  }
149 
150 public:
151  // Provide static begin and end methods as our public "constructors"
152  static df_iterator begin(const GraphT &G) {
153  return df_iterator(GT::getEntryNode(G));
154  }
155  static df_iterator end(const GraphT &G) { return df_iterator(); }
156 
157  // Static begin and end methods as our public ctors for external iterators
158  static df_iterator begin(const GraphT &G, SetType &S) {
159  return df_iterator(GT::getEntryNode(G), S);
160  }
161  static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
162 
163  bool operator==(const df_iterator &x) const {
164  return VisitStack == x.VisitStack;
165  }
166  bool operator!=(const df_iterator &x) const { return !(*this == x); }
167 
168  const NodeRef &operator*() const { return VisitStack.back().first; }
169 
170  // This is a nonstandard operator-> that dereferences the pointer an extra
171  // time... so that you can actually call methods ON the Node, because
172  // the contained type is a pointer. This allows BBIt->getTerminator() f.e.
173  //
174  NodeRef operator->() const { return **this; }
175 
176  df_iterator &operator++() { // Preincrement
177  toNext();
178  return *this;
179  }
180 
181  /// Skips all children of the current node and traverses to next node
182  ///
183  /// Note: This function takes care of incrementing the iterator. If you
184  /// always increment and call this function, you risk walking off the end.
186  VisitStack.pop_back();
187  if (!VisitStack.empty())
188  toNext();
189  return *this;
190  }
191 
192  df_iterator operator++(int) { // Postincrement
193  df_iterator tmp = *this;
194  ++*this;
195  return tmp;
196  }
197 
198  // nodeVisited - return true if this iterator has already visited the
199  // specified node. This is public, and will probably be used to iterate over
200  // nodes that a depth first iteration did not find: ie unreachable nodes.
201  //
202  bool nodeVisited(NodeRef Node) const {
203  return this->Visited.contains(Node);
204  }
205 
206  /// getPathLength - Return the length of the path from the entry node to the
207  /// current node, counting both nodes.
208  unsigned getPathLength() const { return VisitStack.size(); }
209 
210  /// getPath - Return the n'th node in the path from the entry node to the
211  /// current node.
212  NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
213 };
214 
215 // Provide global constructors that automatically figure out correct types...
216 //
217 template <class T>
219  return df_iterator<T>::begin(G);
220 }
221 
222 template <class T>
224  return df_iterator<T>::end(G);
225 }
226 
227 // Provide an accessor method to use them in range-based patterns.
228 template <class T>
230  return make_range(df_begin(G), df_end(G));
231 }
232 
233 // Provide global definitions of external depth first iterators...
235 struct df_ext_iterator : public df_iterator<T, SetTy, true> {
237  : df_iterator<T, SetTy, true>(V) {}
238 };
239 
240 template <class T, class SetTy>
243 }
244 
245 template <class T, class SetTy>
248 }
249 
250 template <class T, class SetTy>
252  SetTy &S) {
253  return make_range(df_ext_begin(G, S), df_ext_end(G, S));
254 }
255 
256 // Provide global definitions of inverse depth first iterators...
257 template <class T,
258  class SetTy =
260  bool External = false>
261 struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
262  idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
263  : df_iterator<Inverse<T>, SetTy, External>(V) {}
264 };
265 
266 template <class T>
269 }
270 
271 template <class T>
274 }
275 
276 // Provide an accessor method to use them in range-based patterns.
277 template <class T>
279  return make_range(idf_begin(G), idf_end(G));
280 }
281 
282 // Provide global definitions of external inverse depth first iterators...
284 struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
286  : idf_iterator<T, SetTy, true>(V) {}
287  idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
288  : idf_iterator<T, SetTy, true>(V) {}
289 };
290 
291 template <class T, class SetTy>
294 }
295 
296 template <class T, class SetTy>
299 }
300 
301 template <class T, class SetTy>
303  SetTy &S) {
304  return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
305 }
306 
307 } // end namespace llvm
308 
309 #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H
llvm::df_iterator::getPathLength
unsigned getPathLength() const
getPathLength - Return the length of the path from the entry node to the current node,...
Definition: DepthFirstIterator.h:208
llvm::df_iterator< T, std::set< typename GraphTraits< T >::NodeRef >, true >::pointer
value_type * pointer
Definition: DepthFirstIterator.h:90
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
Optional.h
llvm::idf_ext_end
idf_ext_iterator< T, SetTy > idf_ext_end(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:297
llvm::df_iterator_storage< SetType, true >::df_iterator_storage
df_iterator_storage(const df_iterator_storage &S)
Definition: DepthFirstIterator.h:59
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:223
llvm::df_iterator< T, std::set< typename GraphTraits< T >::NodeRef >, true >::difference_type
std::ptrdiff_t difference_type
Definition: DepthFirstIterator.h:89
llvm::df_iterator::end
static df_iterator end(const GraphT &G)
Definition: DepthFirstIterator.h:155
llvm::df_iterator_default_set::insert
void insert(IterT Begin, IterT End)
Definition: DepthFirstIterator.h:75
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::df_iterator::skipChildren
df_iterator & skipChildren()
Skips all children of the current node and traverses to next node.
Definition: DepthFirstIterator.h:185
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
llvm::df_iterator::operator++
df_iterator operator++(int)
Definition: DepthFirstIterator.h:192
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::idf_iterator
Definition: DepthFirstIterator.h:261
GraphTraits.h
llvm::idf_begin
idf_iterator< T > idf_begin(const T &G)
Definition: DepthFirstIterator.h:267
llvm::df_ext_begin
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:241
llvm::idf_end
idf_iterator< T > idf_end(const T &G)
Definition: DepthFirstIterator.h:272
llvm::df_iterator_default_set< typename GraphTraits< T >::NodeRef >::iterator
typename BaseSet::iterator iterator
Definition: DepthFirstIterator.h:71
llvm::idf_ext_iterator::idf_ext_iterator
idf_ext_iterator(const idf_iterator< T, SetTy, true > &V)
Definition: DepthFirstIterator.h:285
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:251
llvm::df_iterator::operator==
bool operator==(const df_iterator &x) const
Definition: DepthFirstIterator.h:163
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::df_iterator_default_set::completed
void completed(NodeRef)
Definition: DepthFirstIterator.h:77
llvm::df_iterator::operator*
const NodeRef & operator*() const
Definition: DepthFirstIterator.h:168
SmallPtrSet.h
llvm::df_iterator::end
static df_iterator end(const GraphT &G, SetType &S)
Definition: DepthFirstIterator.h:161
llvm::None
const NoneType None
Definition: None.h:23
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::idf_iterator::idf_iterator
idf_iterator(const df_iterator< Inverse< T >, SetTy, External > &V)
Definition: DepthFirstIterator.h:262
llvm::df_iterator_storage
Definition: DepthFirstIterator.h:50
llvm::SmallPtrSetImpl::iterator
SmallPtrSetIterator< PtrType > iterator
Definition: SmallPtrSet.h:353
llvm::df_iterator_storage::Visited
SetType Visited
Definition: DepthFirstIterator.h:52
llvm::df_iterator::begin
static df_iterator begin(const GraphT &G)
Definition: DepthFirstIterator.h:152
llvm::df_iterator< T, std::set< typename GraphTraits< T >::NodeRef >, true >::value_type
typename GraphTraits< T > ::NodeRef value_type
Definition: DepthFirstIterator.h:88
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:218
llvm::df_iterator::operator++
df_iterator & operator++()
Definition: DepthFirstIterator.h:176
iterator_range.h
llvm::df_iterator_default_set::insert
std::pair< iterator, bool > insert(NodeRef N)
Definition: DepthFirstIterator.h:73
llvm::df_iterator::nodeVisited
bool nodeVisited(NodeRef Node) const
Definition: DepthFirstIterator.h:202
llvm::df_iterator
Definition: DepthFirstIterator.h:85
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:69
llvm::df_iterator_storage< SetType, true >::df_iterator_storage
df_iterator_storage(SetType &VSet)
Definition: DepthFirstIterator.h:58
llvm::idf_ext_iterator::idf_ext_iterator
idf_ext_iterator(const df_iterator< Inverse< T >, SetTy, true > &V)
Definition: DepthFirstIterator.h:287
None.h
llvm::df_iterator_storage< SetType, true >::Visited
SetType & Visited
Definition: DepthFirstIterator.h:61
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
Node
Definition: ItaniumDemangle.h:235
llvm::df_iterator::operator->
NodeRef operator->() const
Definition: DepthFirstIterator.h:174
llvm::df_ext_end
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:246
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
llvm::df_iterator::operator!=
bool operator!=(const df_iterator &x) const
Definition: DepthFirstIterator.h:166
llvm::idf_ext_iterator
Definition: DepthFirstIterator.h:284
llvm::df_iterator< T, std::set< typename GraphTraits< T >::NodeRef >, true >::iterator_category
std::forward_iterator_tag iterator_category
Definition: DepthFirstIterator.h:87
x
TODO unsigned x
Definition: README.txt:10
llvm::df_iterator< T, std::set< typename GraphTraits< T >::NodeRef >, true >::reference
value_type & reference
Definition: DepthFirstIterator.h:91
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:267
llvm::Inverse
Definition: GraphTraits.h:95
llvm::df_iterator::getPath
NodeRef getPath(unsigned n) const
getPath - Return the n'th node in the path from the entry node to the current node.
Definition: DepthFirstIterator.h:212
llvm::inverse_depth_first
iterator_range< idf_iterator< T > > inverse_depth_first(const T &G)
Definition: DepthFirstIterator.h:278
N
#define N
llvm::df_iterator::begin
static df_iterator begin(const GraphT &G, SetType &S)
Definition: DepthFirstIterator.h:158
llvm::df_ext_iterator
Definition: DepthFirstIterator.h:235
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::inverse_depth_first_ext
iterator_range< idf_ext_iterator< T, SetTy > > inverse_depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:302
llvm::idf_ext_begin
idf_ext_iterator< T, SetTy > idf_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:292
llvm::df_ext_iterator::df_ext_iterator
df_ext_iterator(const df_iterator< T, SetTy, true > &V)
Definition: DepthFirstIterator.h:236
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::SmallPtrSetImpl::contains
bool contains(ConstPtrType Ptr) const
Definition: SmallPtrSet.h:388
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1903
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364