1//===- llvm/ADT/PostOrderIterator.h - PostOrder iterator --------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
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/SmallPtrSet.h"
21#include <set>
22#include <vector>
23
24namespace llvm {
25
26// The po_iterator_storage template provides access to the set of already
27// visited nodes during the po_iterator's depth-first traversal.
28//
29// The default implementation simply contains a set of visited nodes, while
30// the Extended=true version uses a reference to an external set.
31//
32// It is possible to prune the depth-first traversal in several ways:
33//
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
37//   single node.
38//
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.
42//
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.
46//
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.
51
52/// Default po_iterator_storage implementation with an internal set object.
53template<class SetType, bool External>
54class po_iterator_storage {
55  SetType Visited;
56public:
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);
61  }
62
63  // Called after all children of BB have been visited.
64  template<typename NodeType>
65  void finishPostorder(NodeType *BB) {}
66};
67
68/// Specialization of po_iterator_storage that references an external set.
69template<class SetType>
70class po_iterator_storage<SetType, true> {
71  SetType &Visited;
72public:
73  po_iterator_storage(SetType &VSet) : Visited(VSet) {}
74  po_iterator_storage(const po_iterator_storage &S) : Visited(S.Visited) {}
75
76  // Return true if edge destination should be visited, called with From = 0 for
77  // the root node.
78  // Graph edges can be pruned by specializing this function.
79  template<class NodeType>
80  bool insertEdge(NodeType *From, NodeType *To) { return Visited.insert(To); }
81
82  // Called after all children of BB have been visited.
83  template<class NodeType>
84  void finishPostorder(NodeType *BB) {}
85};
86
87template<class GraphT,
88  class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
89  bool ExtStorage = false,
90  class GT = GraphTraits<GraphT> >
91class po_iterator : public std::iterator<std::forward_iterator_tag,
92                                         typename GT::NodeType, ptrdiff_t>,
93                    public po_iterator_storage<SetType, ExtStorage> {
94  typedef std::iterator<std::forward_iterator_tag,
95                        typename GT::NodeType, ptrdiff_t> super;
96  typedef typename GT::NodeType          NodeType;
97  typedef typename GT::ChildIteratorType ChildItTy;
98
99  // VisitStack - Used to maintain the ordering.  Top = current block
100  // First element is basic block pointer, second is the 'next child' to visit
101  std::vector<std::pair<NodeType *, ChildItTy> > VisitStack;
102
103  void traverseChild() {
104    while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
105      NodeType *BB = *VisitStack.back().second++;
106      if (this->insertEdge(VisitStack.back().first, BB)) {
107        // If the block is not visited...
108        VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
109      }
110    }
111  }
112
113  inline po_iterator(NodeType *BB) {
114    this->insertEdge((NodeType*)0, BB);
115    VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
116    traverseChild();
117  }
118  inline po_iterator() {} // End is when stack is empty.
119
120  inline po_iterator(NodeType *BB, SetType &S) :
121    po_iterator_storage<SetType, ExtStorage>(S) {
122    if (this->insertEdge((NodeType*)0, BB)) {
123      VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
124      traverseChild();
125    }
126  }
127
128  inline po_iterator(SetType &S) :
129      po_iterator_storage<SetType, ExtStorage>(S) {
130  } // End is when stack is empty.
131public:
132  typedef typename super::pointer pointer;
133  typedef po_iterator<GraphT, SetType, ExtStorage, GT> _Self;
134
135  // Provide static "constructors"...
136  static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
137  static inline _Self end  (GraphT G) { return _Self(); }
138
139  static inline _Self begin(GraphT G, SetType &S) {
140    return _Self(GT::getEntryNode(G), S);
141  }
142  static inline _Self end  (GraphT G, SetType &S) { return _Self(S); }
143
144  inline bool operator==(const _Self& x) const {
145    return VisitStack == x.VisitStack;
146  }
147  inline bool operator!=(const _Self& x) const { return !operator==(x); }
148
149  inline pointer operator*() const {
150    return VisitStack.back().first;
151  }
152
153  // This is a nonstandard operator-> that dereferences the pointer an extra
154  // time... so that you can actually call methods ON the BasicBlock, because
155  // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
156  //
157  inline NodeType *operator->() const { return operator*(); }
158
159  inline _Self& operator++() {   // Preincrement
160    this->finishPostorder(VisitStack.back().first);
161    VisitStack.pop_back();
162    if (!VisitStack.empty())
163      traverseChild();
164    return *this;
165  }
166
167  inline _Self operator++(int) { // Postincrement
168    _Self tmp = *this; ++*this; return tmp;
169  }
170};
171
172// Provide global constructors that automatically figure out correct types...
173//
174template <class T>
175po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
176template <class T>
177po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
178
179// Provide global definitions of external postorder iterators...
180template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
181struct po_ext_iterator : public po_iterator<T, SetType, true> {
182  po_ext_iterator(const po_iterator<T, SetType, true> &V) :
183  po_iterator<T, SetType, true>(V) {}
184};
185
186template<class T, class SetType>
187po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
188  return po_ext_iterator<T, SetType>::begin(G, S);
189}
190
191template<class T, class SetType>
192po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
193  return po_ext_iterator<T, SetType>::end(G, S);
194}
195
196// Provide global definitions of inverse post order iterators...
197template <class T,
198          class SetType = std::set<typename GraphTraits<T>::NodeType*>,
199          bool External = false>
200struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External > {
201  ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
202     po_iterator<Inverse<T>, SetType, External> (V) {}
203};
204
205template <class T>
206ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
207  return ipo_iterator<T>::begin(G, Reverse);
208}
209
210template <class T>
211ipo_iterator<T> ipo_end(T G){
212  return ipo_iterator<T>::end(G);
213}
214
215// Provide global definitions of external inverse postorder iterators...
216template <class T,
217          class SetType = std::set<typename GraphTraits<T>::NodeType*> >
218struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
219  ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
220    ipo_iterator<T, SetType, true>(V) {}
221  ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
222    ipo_iterator<T, SetType, true>(V) {}
223};
224
225template <class T, class SetType>
226ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) {
227  return ipo_ext_iterator<T, SetType>::begin(G, S);
228}
229
230template <class T, class SetType>
231ipo_ext_iterator<T, SetType> ipo_ext_end(T G, SetType &S) {
232  return ipo_ext_iterator<T, SetType>::end(G, S);
233}
234
235//===--------------------------------------------------------------------===//
236// Reverse Post Order CFG iterator code
237//===--------------------------------------------------------------------===//
238//
239// This is used to visit basic blocks in a method in reverse post order.  This
240// class is awkward to use because I don't know a good incremental algorithm to
241// computer RPO from a graph.  Because of this, the construction of the
242// ReversePostOrderTraversal object is expensive (it must walk the entire graph
243// with a postorder iterator to build the data structures).  The moral of this
244// story is: Don't create more ReversePostOrderTraversal classes than necessary.
245//
246// This class should be used like this:
247// {
248//   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
249//   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
250//      ...
251//   }
252//   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
253//      ...
254//   }
255// }
256//
257
258template<class GraphT, class GT = GraphTraits<GraphT> >
259class ReversePostOrderTraversal {
260  typedef typename GT::NodeType NodeType;
261  std::vector<NodeType*> Blocks;       // Block list in normal PO order
262  inline void Initialize(NodeType *BB) {
263    std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
264  }
265public:
266  typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
267
268  inline ReversePostOrderTraversal(GraphT G) {
269    Initialize(GT::getEntryNode(G));
270  }
271
272  // Because we want a reverse post order, use reverse iterators from the vector
273  inline rpo_iterator begin() { return Blocks.rbegin(); }
274  inline rpo_iterator end()   { return Blocks.rend(); }
275};
276
277} // End llvm namespace
278
279#endif
280