1 //===- llvm/ADT/PostOrderIterator.h - PostOrder iterator --------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_ADT_POSTORDERITERATOR_H
17 #define LLVM_ADT_POSTORDERITERATOR_H
19 #include "llvm/ADT/GraphTraits.h"
20 #include "llvm/ADT/SmallPtrSet.h"
26 // The po_iterator_storage template provides access to the set of already
27 // visited nodes during the po_iterator's depth-first traversal.
29 // The default implementation simply contains a set of visited nodes, while
30 // the Extended=true version uses a reference to an external set.
32 // It is possible to prune the depth-first traversal in several ways:
34 // - When providing an external set that already contains some graph nodes,
35 // those nodes won't be visited again. This is useful for restarting a
36 // post-order traversal on a graph with nodes that aren't dominated by a
39 // - By providing a custom SetType class, unwanted graph nodes can be excluded
40 // by having the insert() function return false. This could for example
41 // confine a CFG traversal to blocks in a specific loop.
43 // - Finally, by specializing the po_iterator_storage template itself, graph
44 // edges can be pruned by returning false in the insertEdge() function. This
45 // could be used to remove loop back-edges from the CFG seen by po_iterator.
47 // A specialized po_iterator_storage class can observe both the pre-order and
48 // the post-order. The insertEdge() function is called in a pre-order, while
49 // the finishPostorder() function is called just before the po_iterator moves
50 // on to the next node.
52 /// Default po_iterator_storage implementation with an internal set object.
53 template<class SetType
, bool External
>
54 class po_iterator_storage
{
57 // Return true if edge destination should be visited.
58 template<typename NodeType
>
59 bool insertEdge(NodeType
*From
, NodeType
*To
) {
60 return Visited
.insert(To
).second
;
63 // Called after all children of BB have been visited.
64 template<typename NodeType
>
65 void finishPostorder(NodeType
*BB
) {}
68 /// Specialization of po_iterator_storage that references an external set.
69 template<class SetType
>
70 class po_iterator_storage
<SetType
, true> {
73 po_iterator_storage(SetType
&VSet
) : Visited(VSet
) {}
74 po_iterator_storage(const po_iterator_storage
&S
) : Visited(S
.Visited
) {}
76 // Return true if edge destination should be visited, called with From = 0 for
78 // Graph edges can be pruned by specializing this function.
79 template <class NodeType
> bool insertEdge(NodeType
*From
, NodeType
*To
) {
80 return Visited
.insert(To
).second
;
83 // Called after all children of BB have been visited.
84 template<class NodeType
>
85 void finishPostorder(NodeType
*BB
) {}
88 template<class GraphT
,
89 class SetType
= llvm::SmallPtrSet
<typename GraphTraits
<GraphT
>::NodeType
*, 8>,
90 bool ExtStorage
= false,
91 class GT
= GraphTraits
<GraphT
> >
92 class po_iterator
: public std::iterator
<std::forward_iterator_tag
,
93 typename
GT::NodeType
, ptrdiff_t>,
94 public po_iterator_storage
<SetType
, ExtStorage
> {
95 typedef std::iterator
<std::forward_iterator_tag
,
96 typename
GT::NodeType
, ptrdiff_t> super
;
97 typedef typename
GT::NodeType NodeType
;
98 typedef typename
GT::ChildIteratorType ChildItTy
;
100 // VisitStack - Used to maintain the ordering. Top = current block
101 // First element is basic block pointer, second is the 'next child' to visit
102 std::vector
<std::pair
<NodeType
*, ChildItTy
> > VisitStack
;
104 void traverseChild() {
105 while (VisitStack
.back().second
!= GT::child_end(VisitStack
.back().first
)) {
106 NodeType
*BB
= *VisitStack
.back().second
++;
107 if (this->insertEdge(VisitStack
.back().first
, BB
)) {
108 // If the block is not visited...
109 VisitStack
.push_back(std::make_pair(BB
, GT::child_begin(BB
)));
114 inline po_iterator(NodeType
*BB
) {
115 this->insertEdge((NodeType
*)nullptr, BB
);
116 VisitStack
.push_back(std::make_pair(BB
, GT::child_begin(BB
)));
119 inline po_iterator() {} // End is when stack is empty.
121 inline po_iterator(NodeType
*BB
, SetType
&S
) :
122 po_iterator_storage
<SetType
, ExtStorage
>(S
) {
123 if (this->insertEdge((NodeType
*)nullptr, BB
)) {
124 VisitStack
.push_back(std::make_pair(BB
, GT::child_begin(BB
)));
129 inline po_iterator(SetType
&S
) :
130 po_iterator_storage
<SetType
, ExtStorage
>(S
) {
131 } // End is when stack is empty.
133 typedef typename
super::pointer pointer
;
134 typedef po_iterator
<GraphT
, SetType
, ExtStorage
, GT
> _Self
;
136 // Provide static "constructors"...
137 static inline _Self
begin(GraphT G
) { return _Self(GT::getEntryNode(G
)); }
138 static inline _Self
end (GraphT G
) { return _Self(); }
140 static inline _Self
begin(GraphT G
, SetType
&S
) {
141 return _Self(GT::getEntryNode(G
), S
);
143 static inline _Self
end (GraphT G
, SetType
&S
) { return _Self(S
); }
145 inline bool operator==(const _Self
& x
) const {
146 return VisitStack
== x
.VisitStack
;
148 inline bool operator!=(const _Self
& x
) const { return !operator==(x
); }
150 inline pointer
operator*() const {
151 return VisitStack
.back().first
;
154 // This is a nonstandard operator-> that dereferences the pointer an extra
155 // time... so that you can actually call methods ON the BasicBlock, because
156 // the contained type is a pointer. This allows BBIt->getTerminator() f.e.
158 inline NodeType
*operator->() const { return operator*(); }
160 inline _Self
& operator++() { // Preincrement
161 this->finishPostorder(VisitStack
.back().first
);
162 VisitStack
.pop_back();
163 if (!VisitStack
.empty())
168 inline _Self
operator++(int) { // Postincrement
169 _Self tmp
= *this; ++*this; return tmp
;
173 // Provide global constructors that automatically figure out correct types...
176 po_iterator
<T
> po_begin(T G
) { return po_iterator
<T
>::begin(G
); }
178 po_iterator
<T
> po_end (T G
) { return po_iterator
<T
>::end(G
); }
180 // Provide global definitions of external postorder iterators...
181 template<class T
, class SetType
=std::set
<typename GraphTraits
<T
>::NodeType
*> >
182 struct po_ext_iterator
: public po_iterator
<T
, SetType
, true> {
183 po_ext_iterator(const po_iterator
<T
, SetType
, true> &V
) :
184 po_iterator
<T
, SetType
, true>(V
) {}
187 template<class T
, class SetType
>
188 po_ext_iterator
<T
, SetType
> po_ext_begin(T G
, SetType
&S
) {
189 return po_ext_iterator
<T
, SetType
>::begin(G
, S
);
192 template<class T
, class SetType
>
193 po_ext_iterator
<T
, SetType
> po_ext_end(T G
, SetType
&S
) {
194 return po_ext_iterator
<T
, SetType
>::end(G
, S
);
197 // Provide global definitions of inverse post order iterators...
199 class SetType
= std::set
<typename GraphTraits
<T
>::NodeType
*>,
200 bool External
= false>
201 struct ipo_iterator
: public po_iterator
<Inverse
<T
>, SetType
, External
> {
202 ipo_iterator(const po_iterator
<Inverse
<T
>, SetType
, External
> &V
) :
203 po_iterator
<Inverse
<T
>, SetType
, External
> (V
) {}
207 ipo_iterator
<T
> ipo_begin(T G
, bool Reverse
= false) {
208 return ipo_iterator
<T
>::begin(G
, Reverse
);
212 ipo_iterator
<T
> ipo_end(T G
){
213 return ipo_iterator
<T
>::end(G
);
216 // Provide global definitions of external inverse postorder iterators...
218 class SetType
= std::set
<typename GraphTraits
<T
>::NodeType
*> >
219 struct ipo_ext_iterator
: public ipo_iterator
<T
, SetType
, true> {
220 ipo_ext_iterator(const ipo_iterator
<T
, SetType
, true> &V
) :
221 ipo_iterator
<T
, SetType
, true>(V
) {}
222 ipo_ext_iterator(const po_iterator
<Inverse
<T
>, SetType
, true> &V
) :
223 ipo_iterator
<T
, SetType
, true>(V
) {}
226 template <class T
, class SetType
>
227 ipo_ext_iterator
<T
, SetType
> ipo_ext_begin(T G
, SetType
&S
) {
228 return ipo_ext_iterator
<T
, SetType
>::begin(G
, S
);
231 template <class T
, class SetType
>
232 ipo_ext_iterator
<T
, SetType
> ipo_ext_end(T G
, SetType
&S
) {
233 return ipo_ext_iterator
<T
, SetType
>::end(G
, S
);
236 //===--------------------------------------------------------------------===//
237 // Reverse Post Order CFG iterator code
238 //===--------------------------------------------------------------------===//
240 // This is used to visit basic blocks in a method in reverse post order. This
241 // class is awkward to use because I don't know a good incremental algorithm to
242 // computer RPO from a graph. Because of this, the construction of the
243 // ReversePostOrderTraversal object is expensive (it must walk the entire graph
244 // with a postorder iterator to build the data structures). The moral of this
245 // story is: Don't create more ReversePostOrderTraversal classes than necessary.
247 // This class should be used like this:
249 // ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
250 // for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
253 // for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
259 template<class GraphT
, class GT
= GraphTraits
<GraphT
> >
260 class ReversePostOrderTraversal
{
261 typedef typename
GT::NodeType NodeType
;
262 std::vector
<NodeType
*> Blocks
; // Block list in normal PO order
263 inline void Initialize(NodeType
*BB
) {
264 std::copy(po_begin(BB
), po_end(BB
), std::back_inserter(Blocks
));
267 typedef typename
std::vector
<NodeType
*>::reverse_iterator rpo_iterator
;
269 inline ReversePostOrderTraversal(GraphT G
) {
270 Initialize(GT::getEntryNode(G
));
273 // Because we want a reverse post order, use reverse iterators from the vector
274 inline rpo_iterator
begin() { return Blocks
.rbegin(); }
275 inline rpo_iterator
end() { return Blocks
.rend(); }
278 } // End llvm namespace