Home | History | Annotate | Download | only in ADT
      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 
     24 namespace 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.
     53 template<class SetType, bool External>
     54 class po_iterator_storage {
     55   SetType Visited;
     56 public:
     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.
     69 template<class SetType>
     70 class po_iterator_storage<SetType, true> {
     71   SetType &Visited;
     72 public:
     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 
     87 template<class GraphT,
     88   class SetType = llvm::SmallPtrSet<typename GraphTraits<GraphT>::NodeType*, 8>,
     89   bool ExtStorage = false,
     90   class GT = GraphTraits<GraphT> >
     91 class 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.
    131 public:
    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 //
    174 template <class T>
    175 po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
    176 template <class T>
    177 po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
    178 
    179 // Provide global definitions of external postorder iterators...
    180 template<class T, class SetType=std::set<typename GraphTraits<T>::NodeType*> >
    181 struct 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 
    186 template<class T, class SetType>
    187 po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
    188   return po_ext_iterator<T, SetType>::begin(G, S);
    189 }
    190 
    191 template<class T, class SetType>
    192 po_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...
    197 template <class T,
    198           class SetType = std::set<typename GraphTraits<T>::NodeType*>,
    199           bool External = false>
    200 struct 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 
    205 template <class T>
    206 ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
    207   return ipo_iterator<T>::begin(G, Reverse);
    208 }
    209 
    210 template <class T>
    211 ipo_iterator<T> ipo_end(T G){
    212   return ipo_iterator<T>::end(G);
    213 }
    214 
    215 // Provide global definitions of external inverse postorder iterators...
    216 template <class T,
    217           class SetType = std::set<typename GraphTraits<T>::NodeType*> >
    218 struct 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 
    225 template <class T, class SetType>
    226 ipo_ext_iterator<T, SetType> ipo_ext_begin(T G, SetType &S) {
    227   return ipo_ext_iterator<T, SetType>::begin(G, S);
    228 }
    229 
    230 template <class T, class SetType>
    231 ipo_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 
    258 template<class GraphT, class GT = GraphTraits<GraphT> >
    259 class 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   }
    265 public:
    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