LLVM  16.0.0git
PostOrderIterator.h
Go to the documentation of this file.
1 //===- llvm/ADT/PostOrderIterator.h - PostOrder 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 a generic graph
11 /// post order iterator. This should work over any graph type that has a
12 /// GraphTraits specialization.
13 ///
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_ADT_POSTORDERITERATOR_H
17 #define LLVM_ADT_POSTORDERITERATOR_H
18 
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/ADT/SmallVector.h"
24 #include <iterator>
25 #include <set>
26 #include <utility>
27 #include <vector>
28 
29 namespace llvm {
30 
31 // The po_iterator_storage template provides access to the set of already
32 // visited nodes during the po_iterator's depth-first traversal.
33 //
34 // The default implementation simply contains a set of visited nodes, while
35 // the External=true version uses a reference to an external set.
36 //
37 // It is possible to prune the depth-first traversal in several ways:
38 //
39 // - When providing an external set that already contains some graph nodes,
40 // those nodes won't be visited again. This is useful for restarting a
41 // post-order traversal on a graph with nodes that aren't dominated by a
42 // single node.
43 //
44 // - By providing a custom SetType class, unwanted graph nodes can be excluded
45 // by having the insert() function return false. This could for example
46 // confine a CFG traversal to blocks in a specific loop.
47 //
48 // - Finally, by specializing the po_iterator_storage template itself, graph
49 // edges can be pruned by returning false in the insertEdge() function. This
50 // could be used to remove loop back-edges from the CFG seen by po_iterator.
51 //
52 // A specialized po_iterator_storage class can observe both the pre-order and
53 // the post-order. The insertEdge() function is called in a pre-order, while
54 // the finishPostorder() function is called just before the po_iterator moves
55 // on to the next node.
56 
57 /// Default po_iterator_storage implementation with an internal set object.
58 template<class SetType, bool External>
60  SetType Visited;
61 
62 public:
63  // Return true if edge destination should be visited.
64  template <typename NodeRef>
66  return Visited.insert(To).second;
67  }
68 
69  // Called after all children of BB have been visited.
70  template <typename NodeRef> void finishPostorder(NodeRef BB) {}
71 };
72 
73 /// Specialization of po_iterator_storage that references an external set.
74 template<class SetType>
75 class po_iterator_storage<SetType, true> {
76  SetType &Visited;
77 
78 public:
79  po_iterator_storage(SetType &VSet) : Visited(VSet) {}
80  po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
81 
82  // Return true if edge destination should be visited, called with From = 0 for
83  // the root node.
84  // Graph edges can be pruned by specializing this function.
85  template <class NodeRef> bool insertEdge(Optional<NodeRef> From, NodeRef To) {
86  return Visited.insert(To).second;
87  }
88 
89  // Called after all children of BB have been visited.
90  template <class NodeRef> void finishPostorder(NodeRef BB) {}
91 };
92 
93 template <class GraphT,
95  bool ExtStorage = false, class GT = GraphTraits<GraphT>>
96 class po_iterator : public po_iterator_storage<SetType, ExtStorage> {
97 public:
98  using iterator_category = std::forward_iterator_tag;
99  using value_type = typename GT::NodeRef;
100  using difference_type = std::ptrdiff_t;
101  using pointer = value_type *;
103 
104 private:
105  using NodeRef = typename GT::NodeRef;
106  using ChildItTy = typename GT::ChildIteratorType;
107 
108  // VisitStack - Used to maintain the ordering. Top = current block
109  // First element is basic block pointer, second is the 'next child' to visit
111 
112  po_iterator(NodeRef BB) {
113  this->insertEdge(Optional<NodeRef>(), BB);
114  VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
115  traverseChild();
116  }
117 
118  po_iterator() = default; // End is when stack is empty.
119 
120  po_iterator(NodeRef BB, SetType &S)
121  : po_iterator_storage<SetType, ExtStorage>(S) {
122  if (this->insertEdge(Optional<NodeRef>(), BB)) {
123  VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
124  traverseChild();
125  }
126  }
127 
128  po_iterator(SetType &S)
129  : po_iterator_storage<SetType, ExtStorage>(S) {
130  } // End is when stack is empty.
131 
132  void traverseChild() {
133  while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
134  NodeRef BB = *VisitStack.back().second++;
135  if (this->insertEdge(Optional<NodeRef>(VisitStack.back().first), BB)) {
136  // If the block is not visited...
137  VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
138  }
139  }
140  }
141 
142 public:
143  // Provide static "constructors"...
144  static po_iterator begin(const GraphT &G) {
145  return po_iterator(GT::getEntryNode(G));
146  }
147  static po_iterator end(const GraphT &G) { return po_iterator(); }
148 
149  static po_iterator begin(const GraphT &G, SetType &S) {
150  return po_iterator(GT::getEntryNode(G), S);
151  }
152  static po_iterator end(const GraphT &G, SetType &S) { return po_iterator(S); }
153 
154  bool operator==(const po_iterator &x) const {
155  return VisitStack == x.VisitStack;
156  }
157  bool operator!=(const po_iterator &x) const { return !(*this == x); }
158 
159  const NodeRef &operator*() const { return VisitStack.back().first; }
160 
161  // This is a nonstandard operator-> that dereferences the pointer an extra
162  // time... so that you can actually call methods ON the BasicBlock, because
163  // the contained type is a pointer. This allows BBIt->getTerminator() f.e.
164  //
165  NodeRef operator->() const { return **this; }
166 
167  po_iterator &operator++() { // Preincrement
168  this->finishPostorder(VisitStack.back().first);
169  VisitStack.pop_back();
170  if (!VisitStack.empty())
171  traverseChild();
172  return *this;
173  }
174 
175  po_iterator operator++(int) { // Postincrement
176  po_iterator tmp = *this;
177  ++*this;
178  return tmp;
179  }
180 };
181 
182 // Provide global constructors that automatically figure out correct types...
183 //
184 template <class T>
186 template <class T>
187 po_iterator<T> po_end (const T &G) { return po_iterator<T>::end(G); }
188 
189 template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
190  return make_range(po_begin(G), po_end(G));
191 }
192 
193 // Provide global definitions of external postorder iterators...
195 struct po_ext_iterator : public po_iterator<T, SetType, true> {
197  po_iterator<T, SetType, true>(V) {}
198 };
199 
200 template<class T, class SetType>
203 }
204 
205 template<class T, class SetType>
208 }
209 
210 template <class T, class SetType>
212  return make_range(po_ext_begin(G, S), po_ext_end(G, S));
213 }
214 
215 // Provide global definitions of inverse post order iterators...
217  bool External = false>
218 struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External> {
219  ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
220  po_iterator<Inverse<T>, SetType, External> (V) {}
221 };
222 
223 template <class T>
225  return ipo_iterator<T>::begin(G);
226 }
227 
228 template <class T>
230  return ipo_iterator<T>::end(G);
231 }
232 
233 template <class T>
235  return make_range(ipo_begin(G), ipo_end(G));
236 }
237 
238 // Provide global definitions of external inverse postorder iterators...
240 struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
242  ipo_iterator<T, SetType, true>(V) {}
243  ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
244  ipo_iterator<T, SetType, true>(V) {}
245 };
246 
247 template <class T, class SetType>
250 }
251 
252 template <class T, class SetType>
255 }
256 
257 template <class T, class SetType>
258 iterator_range<ipo_ext_iterator<T, SetType>>
259 inverse_post_order_ext(const T &G, SetType &S) {
260  return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S));
261 }
262 
263 //===--------------------------------------------------------------------===//
264 // Reverse Post Order CFG iterator code
265 //===--------------------------------------------------------------------===//
266 //
267 // This is used to visit basic blocks in a method in reverse post order. This
268 // class is awkward to use because I don't know a good incremental algorithm to
269 // computer RPO from a graph. Because of this, the construction of the
270 // ReversePostOrderTraversal object is expensive (it must walk the entire graph
271 // with a postorder iterator to build the data structures). The moral of this
272 // story is: Don't create more ReversePostOrderTraversal classes than necessary.
273 //
274 // Because it does the traversal in its constructor, it won't invalidate when
275 // BasicBlocks are removed, *but* it may contain erased blocks. Some places
276 // rely on this behavior (i.e. GVN).
277 //
278 // This class should be used like this:
279 // {
280 // ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
281 // for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
282 // ...
283 // }
284 // for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
285 // ...
286 // }
287 // }
288 //
289 
290 template<class GraphT, class GT = GraphTraits<GraphT>>
292  using NodeRef = typename GT::NodeRef;
293 
294  std::vector<NodeRef> Blocks; // Block list in normal PO order
295 
296  void Initialize(const GraphT &G) {
297  std::copy(po_begin(G), po_end(G), std::back_inserter(Blocks));
298  }
299 
300 public:
301  using rpo_iterator = typename std::vector<NodeRef>::reverse_iterator;
302  using const_rpo_iterator = typename std::vector<NodeRef>::const_reverse_iterator;
303 
304  ReversePostOrderTraversal(const GraphT &G) { Initialize(G); }
305 
306  // Because we want a reverse post order, use reverse iterators from the vector
307  rpo_iterator begin() { return Blocks.rbegin(); }
308  const_rpo_iterator begin() const { return Blocks.crbegin(); }
309  rpo_iterator end() { return Blocks.rend(); }
310  const_rpo_iterator end() const { return Blocks.crend(); }
311 };
312 
313 } // end namespace llvm
314 
315 #endif // LLVM_ADT_POSTORDERITERATOR_H
llvm::post_order_ext
iterator_range< po_ext_iterator< T, SetType > > post_order_ext(const T &G, SetType &S)
Definition: PostOrderIterator.h:211
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::ipo_ext_begin
ipo_ext_iterator< T, SetType > ipo_ext_begin(const T &G, SetType &S)
Definition: PostOrderIterator.h:248
llvm::inverse_post_order
iterator_range< ipo_iterator< T > > inverse_post_order(const T &G)
Definition: PostOrderIterator.h:234
llvm::po_end
po_iterator< T > po_end(const T &G)
Definition: PostOrderIterator.h:187
llvm::po_iterator::operator!=
bool operator!=(const po_iterator &x) const
Definition: PostOrderIterator.h:157
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
llvm::po_iterator_storage< SetType, true >::finishPostorder
void finishPostorder(NodeRef BB)
Definition: PostOrderIterator.h:90
llvm::po_iterator_storage::finishPostorder
void finishPostorder(NodeRef BB)
Definition: PostOrderIterator.h:70
llvm::ipo_begin
ipo_iterator< T > ipo_begin(const T &G)
Definition: PostOrderIterator.h:224
llvm::po_iterator::operator->
NodeRef operator->() const
Definition: PostOrderIterator.h:165
llvm::po_ext_end
po_ext_iterator< T, SetType > po_ext_end(T G, SetType &S)
Definition: PostOrderIterator.h:206
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1835
llvm::po_iterator_storage< SetType, true >::po_iterator_storage
po_iterator_storage(const po_iterator_storage &S)
Definition: PostOrderIterator.h:80
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
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::po_iterator_storage
Default po_iterator_storage implementation with an internal set object.
Definition: PostOrderIterator.h:59
GraphTraits.h
llvm::ipo_ext_iterator
Definition: PostOrderIterator.h:240
llvm::po_begin
po_iterator< T > po_begin(const T &G)
Definition: PostOrderIterator.h:185
llvm::ReversePostOrderTraversal::rpo_iterator
typename std::vector< NodeRef >::reverse_iterator rpo_iterator
Definition: PostOrderIterator.h:301
llvm::po_iterator::end
static po_iterator end(const GraphT &G)
Definition: PostOrderIterator.h:147
llvm::ipo_iterator::ipo_iterator
ipo_iterator(const po_iterator< Inverse< T >, SetType, External > &V)
Definition: PostOrderIterator.h:219
llvm::ReversePostOrderTraversal::end
rpo_iterator end()
Definition: PostOrderIterator.h:309
llvm::ReversePostOrderTraversal::ReversePostOrderTraversal
ReversePostOrderTraversal(const GraphT &G)
Definition: PostOrderIterator.h:304
llvm::po_ext_begin
po_ext_iterator< T, SetType > po_ext_begin(T G, SetType &S)
Definition: PostOrderIterator.h:201
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
SmallPtrSet.h
llvm::po_iterator::operator++
po_iterator operator++(int)
Definition: PostOrderIterator.h:175
llvm::po_iterator< Inverse< T >, std::set< typename GraphTraits< T >::NodeRef >, false >::iterator_category
std::forward_iterator_tag iterator_category
Definition: PostOrderIterator.h:98
llvm::ReversePostOrderTraversal::const_rpo_iterator
typename std::vector< NodeRef >::const_reverse_iterator const_rpo_iterator
Definition: PostOrderIterator.h:302
llvm::ReversePostOrderTraversal::begin
rpo_iterator begin()
Definition: PostOrderIterator.h:307
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::po_iterator::operator++
po_iterator & operator++()
Definition: PostOrderIterator.h:167
llvm::po_ext_iterator::po_ext_iterator
po_ext_iterator(const po_iterator< T, SetType, true > &V)
Definition: PostOrderIterator.h:196
llvm::po_iterator::operator==
bool operator==(const po_iterator &x) const
Definition: PostOrderIterator.h:154
llvm::po_iterator< Inverse< T >, std::set< typename GraphTraits< T >::NodeRef >, false >::reference
value_type & reference
Definition: PostOrderIterator.h:102
llvm::po_iterator
Definition: PostOrderIterator.h:96
iterator_range.h
llvm::inverse_post_order_ext
iterator_range< ipo_ext_iterator< T, SetType > > inverse_post_order_ext(const T &G, SetType &S)
Definition: PostOrderIterator.h:259
llvm::ReversePostOrderTraversal::begin
const_rpo_iterator begin() const
Definition: PostOrderIterator.h:308
llvm::po_iterator< Inverse< T >, std::set< typename GraphTraits< T >::NodeRef >, false >::value_type
typename GraphTraits< Inverse< T > > ::NodeRef value_type
Definition: PostOrderIterator.h:99
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
llvm::po_iterator< Inverse< T >, std::set< typename GraphTraits< T >::NodeRef >, false >::pointer
value_type * pointer
Definition: PostOrderIterator.h:101
llvm::ipo_ext_iterator::ipo_ext_iterator
ipo_ext_iterator(const po_iterator< Inverse< T >, SetType, true > &V)
Definition: PostOrderIterator.h:243
llvm::ipo_ext_iterator::ipo_ext_iterator
ipo_ext_iterator(const ipo_iterator< T, SetType, true > &V)
Definition: PostOrderIterator.h:241
llvm::po_iterator::begin
static po_iterator begin(const GraphT &G)
Definition: PostOrderIterator.h:144
llvm::post_order
iterator_range< po_iterator< T > > post_order(const T &G)
Definition: PostOrderIterator.h:189
llvm::po_ext_iterator
Definition: PostOrderIterator.h:195
x
TODO unsigned x
Definition: README.txt:10
llvm::AArch64CC::GT
@ GT
Definition: AArch64BaseInfo.h:267
llvm::Inverse
Definition: GraphTraits.h:97
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:291
llvm::ipo_ext_end
ipo_ext_iterator< T, SetType > ipo_ext_end(const T &G, SetType &S)
Definition: PostOrderIterator.h:253
llvm::po_iterator_storage< SetType, true >::insertEdge
bool insertEdge(Optional< NodeRef > From, NodeRef To)
Definition: PostOrderIterator.h:85
SmallVector.h
llvm::ipo_iterator
Definition: PostOrderIterator.h:218
llvm::po_iterator< Inverse< T >, std::set< typename GraphTraits< T >::NodeRef >, false >::difference_type
std::ptrdiff_t difference_type
Definition: PostOrderIterator.h:100
llvm::po_iterator::operator*
const NodeRef & operator*() const
Definition: PostOrderIterator.h:159
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::ReversePostOrderTraversal::end
const_rpo_iterator end() const
Definition: PostOrderIterator.h:310
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
From
BlockVerifier::State From
Definition: BlockVerifier.cpp:55
llvm::ipo_end
ipo_iterator< T > ipo_end(const T &G)
Definition: PostOrderIterator.h:229
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::po_iterator::begin
static po_iterator begin(const GraphT &G, SetType &S)
Definition: PostOrderIterator.h:149
llvm::po_iterator::end
static po_iterator end(const GraphT &G, SetType &S)
Definition: PostOrderIterator.h:152
llvm::po_iterator_storage< SetType, true >::po_iterator_storage
po_iterator_storage(SetType &VSet)
Definition: PostOrderIterator.h:79
llvm::po_iterator_storage::insertEdge
bool insertEdge(Optional< NodeRef > From, NodeRef To)
Definition: PostOrderIterator.h:65