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