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