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 <utility>
42 #include <vector>
43 
44 namespace llvm {
45 
46 // df_iterator_storage - A private class which is used to figure out where to
47 // store the visited set.
48 template<class SetType, bool External> // Non-external set
50 public:
51  SetType Visited;
52 };
53 
54 template<class SetType>
55 class df_iterator_storage<SetType, true> {
56 public:
57  df_iterator_storage(SetType &VSet) : Visited(VSet) {}
59 
60  SetType &Visited;
61 };
62 
63 // The visited stated for the iteration is a simple set augmented with
64 // one more method, completed, which is invoked when all children of a
65 // node have been processed. It is intended to distinguish of back and
66 // cross edges in the spanning tree but is not used in the common case.
67 template <typename NodeRef, unsigned SmallSize=8>
68 struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> {
70  using iterator = typename BaseSet::iterator;
71 
72  std::pair<iterator,bool> insert(NodeRef N) { return BaseSet::insert(N); }
73  template <typename IterT>
74  void insert(IterT Begin, IterT End) { BaseSet::insert(Begin,End); }
75 
76  void completed(NodeRef) {}
77 };
78 
79 // Generic Depth First Iterator
80 template <class GraphT,
81  class SetType =
83  bool ExtStorage = false, class GT = GraphTraits<GraphT>>
84 class df_iterator : public df_iterator_storage<SetType, ExtStorage> {
85 public:
86  using iterator_category = std::forward_iterator_tag;
87  using value_type = typename GT::NodeRef;
88  using difference_type = std::ptrdiff_t;
89  using pointer = value_type *;
90  using reference = value_type &;
91 
92 private:
93  using NodeRef = typename GT::NodeRef;
94  using ChildItTy = typename GT::ChildIteratorType;
95 
96  // First element is node reference, second is the 'next child' to visit.
97  // The second child is initialized lazily to pick up graph changes during the
98  // DFS.
99  using StackElement = std::pair<NodeRef, Optional<ChildItTy>>;
100 
101  // VisitStack - Used to maintain the ordering. Top = current block
102  std::vector<StackElement> VisitStack;
103 
104  inline df_iterator(NodeRef Node) {
105  this->Visited.insert(Node);
106  VisitStack.push_back(StackElement(Node, None));
107  }
108 
109  inline df_iterator() = default; // End is when stack is empty
110 
111  inline df_iterator(NodeRef Node, SetType &S)
112  : df_iterator_storage<SetType, ExtStorage>(S) {
113  if (this->Visited.insert(Node).second)
114  VisitStack.push_back(StackElement(Node, None));
115  }
116 
117  inline df_iterator(SetType &S)
118  : df_iterator_storage<SetType, ExtStorage>(S) {
119  // End is when stack is empty
120  }
121 
122  inline void toNext() {
123  do {
124  NodeRef Node = VisitStack.back().first;
125  Optional<ChildItTy> &Opt = VisitStack.back().second;
126 
127  if (!Opt)
128  Opt.emplace(GT::child_begin(Node));
129 
130  // Notice that we directly mutate *Opt here, so that
131  // VisitStack.back().second actually gets updated as the iterator
132  // increases.
133  while (*Opt != GT::child_end(Node)) {
134  NodeRef Next = *(*Opt)++;
135  // Has our next sibling been visited?
136  if (this->Visited.insert(Next).second) {
137  // No, do it now.
138  VisitStack.push_back(StackElement(Next, None));
139  return;
140  }
141  }
142  this->Visited.completed(Node);
143 
144  // Oops, ran out of successors... go up a level on the stack.
145  VisitStack.pop_back();
146  } while (!VisitStack.empty());
147  }
148 
149 public:
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  /// 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.contains(Node);
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...
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>
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>
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...
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
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:207
llvm::df_iterator< Inverse< T >, df_iterator_default_set< typename GraphTraits< T >::NodeRef >, External >::pointer
value_type * pointer
Definition: DepthFirstIterator.h:89
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:22
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:296
llvm::df_iterator_storage< SetType, true >::df_iterator_storage
df_iterator_storage(const df_iterator_storage &S)
Definition: DepthFirstIterator.h:58
llvm::df_end
df_iterator< T > df_end(const T &G)
Definition: DepthFirstIterator.h:222
llvm::df_iterator< Inverse< T >, df_iterator_default_set< typename GraphTraits< T >::NodeRef >, External >::difference_type
std::ptrdiff_t difference_type
Definition: DepthFirstIterator.h:88
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1886
llvm::df_iterator::end
static df_iterator end(const GraphT &G)
Definition: DepthFirstIterator.h:154
llvm::df_iterator_default_set::insert
void insert(IterT Begin, IterT End)
Definition: DepthFirstIterator.h:74
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:184
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:191
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:260
GraphTraits.h
llvm::idf_begin
idf_iterator< T > idf_begin(const T &G)
Definition: DepthFirstIterator.h:266
llvm::df_ext_begin
df_ext_iterator< T, SetTy > df_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:240
llvm::idf_end
idf_iterator< T > idf_end(const T &G)
Definition: DepthFirstIterator.h:271
llvm::df_iterator_default_set< typename GraphTraits< T >::NodeRef >::iterator
typename BaseSet::iterator iterator
Definition: DepthFirstIterator.h:70
llvm::idf_ext_iterator::idf_ext_iterator
idf_ext_iterator(const idf_iterator< T, SetTy, true > &V)
Definition: DepthFirstIterator.h:284
llvm::depth_first_ext
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:250
llvm::df_iterator::operator==
bool operator==(const df_iterator &x) const
Definition: DepthFirstIterator.h:162
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:76
llvm::df_iterator::operator*
const NodeRef & operator*() const
Definition: DepthFirstIterator.h:167
SmallPtrSet.h
llvm::df_iterator::end
static df_iterator end(const GraphT &G, SetType &S)
Definition: DepthFirstIterator.h:160
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:261
llvm::df_iterator_storage
Definition: DepthFirstIterator.h:49
llvm::SmallPtrSetImpl::iterator
SmallPtrSetIterator< PtrType > iterator
Definition: SmallPtrSet.h:353
llvm::df_iterator_storage::Visited
SetType Visited
Definition: DepthFirstIterator.h:51
llvm::df_iterator::begin
static df_iterator begin(const GraphT &G)
Definition: DepthFirstIterator.h:151
llvm::df_iterator< Inverse< T >, df_iterator_default_set< typename GraphTraits< T >::NodeRef >, External >::value_type
typename GraphTraits< Inverse< T > > ::NodeRef value_type
Definition: DepthFirstIterator.h:87
llvm::df_begin
df_iterator< T > df_begin(const T &G)
Definition: DepthFirstIterator.h:217
llvm::df_iterator::operator++
df_iterator & operator++()
Definition: DepthFirstIterator.h:175
iterator_range.h
llvm::df_iterator_default_set::insert
std::pair< iterator, bool > insert(NodeRef N)
Definition: DepthFirstIterator.h:72
llvm::df_iterator::nodeVisited
bool nodeVisited(NodeRef Node) const
Definition: DepthFirstIterator.h:201
llvm::df_iterator
Definition: DepthFirstIterator.h:84
llvm::df_iterator_default_set
Definition: DepthFirstIterator.h:68
llvm::df_iterator_storage< SetType, true >::df_iterator_storage
df_iterator_storage(SetType &VSet)
Definition: DepthFirstIterator.h:57
llvm::idf_ext_iterator::idf_ext_iterator
idf_ext_iterator(const df_iterator< Inverse< T >, SetTy, true > &V)
Definition: DepthFirstIterator.h:286
None.h
llvm::df_iterator_storage< SetType, true >::Visited
SetType & Visited
Definition: DepthFirstIterator.h:60
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:238
llvm::df_iterator::operator->
NodeRef operator->() const
Definition: DepthFirstIterator.h:173
llvm::df_ext_end
df_ext_iterator< T, SetTy > df_ext_end(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:245
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:228
llvm::df_iterator::operator!=
bool operator!=(const df_iterator &x) const
Definition: DepthFirstIterator.h:165
llvm::idf_ext_iterator
Definition: DepthFirstIterator.h:283
llvm::df_iterator< Inverse< T >, df_iterator_default_set< typename GraphTraits< T >::NodeRef >, External >::iterator_category
std::forward_iterator_tag iterator_category
Definition: DepthFirstIterator.h:86
x
TODO unsigned x
Definition: README.txt:10
llvm::df_iterator< Inverse< T >, df_iterator_default_set< typename GraphTraits< T >::NodeRef >, External >::reference
value_type & reference
Definition: DepthFirstIterator.h:90
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:211
llvm::inverse_depth_first
iterator_range< idf_iterator< T > > inverse_depth_first(const T &G)
Definition: DepthFirstIterator.h:277
N
#define N
llvm::df_iterator::begin
static df_iterator begin(const GraphT &G, SetType &S)
Definition: DepthFirstIterator.h:157
llvm::df_ext_iterator
Definition: DepthFirstIterator.h:234
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:301
llvm::idf_ext_begin
idf_ext_iterator< T, SetTy > idf_ext_begin(const T &G, SetTy &S)
Definition: DepthFirstIterator.h:291
llvm::df_ext_iterator::df_ext_iterator
df_ext_iterator(const df_iterator< T, SetTy, true > &V)
Definition: DepthFirstIterator.h:235
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
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