LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

PostOrderIterator.h

Go to the documentation of this file.
00001 //===- llvm/ADT/PostOrderIterator.h - PostOrder iterator --------*- C++ -*-===//
00002 // 
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 // 
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file builds on the ADT/GraphTraits.h file to build a generic graph
00011 // post order iterator.  This should work over any graph type that has a
00012 // GraphTraits specialization.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #ifndef LLVM_ADT_POSTORDERITERATOR_H
00017 #define LLVM_ADT_POSTORDERITERATOR_H
00018 
00019 #include "llvm/ADT/GraphTraits.h"
00020 #include "llvm/ADT/iterator"
00021 #include <stack>
00022 #include <set>
00023 
00024 namespace llvm {
00025 
00026 template<class GraphT, class GT = GraphTraits<GraphT> >
00027 class po_iterator : public forward_iterator<typename GT::NodeType, ptrdiff_t> {
00028   typedef forward_iterator<typename GT::NodeType, ptrdiff_t> super;
00029   typedef typename GT::NodeType          NodeType;
00030   typedef typename GT::ChildIteratorType ChildItTy;
00031 
00032   std::set<NodeType *> Visited;    // All of the blocks visited so far...
00033   // VisitStack - Used to maintain the ordering.  Top = current block
00034   // First element is basic block pointer, second is the 'next child' to visit
00035   std::stack<std::pair<NodeType *, ChildItTy> > VisitStack;
00036 
00037   void traverseChild() {
00038     while (VisitStack.top().second != GT::child_end(VisitStack.top().first)) {
00039       NodeType *BB = *VisitStack.top().second++;
00040       if (!Visited.count(BB)) {  // If the block is not visited...
00041   Visited.insert(BB);
00042   VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
00043       }
00044     }
00045   }
00046 
00047   inline po_iterator(NodeType *BB) {
00048     Visited.insert(BB);
00049     VisitStack.push(std::make_pair(BB, GT::child_begin(BB)));
00050     traverseChild();
00051   }
00052   inline po_iterator() { /* End is when stack is empty */ }
00053 public:
00054   typedef typename super::pointer pointer;
00055   typedef po_iterator<GraphT, GT> _Self;
00056 
00057   // Provide static "constructors"...
00058   static inline _Self begin(GraphT G) { return _Self(GT::getEntryNode(G)); }
00059   static inline _Self end  (GraphT G) { return _Self(); }
00060 
00061   inline bool operator==(const _Self& x) const { 
00062     return VisitStack == x.VisitStack;
00063   }
00064   inline bool operator!=(const _Self& x) const { return !operator==(x); }
00065 
00066   inline pointer operator*() const { 
00067     return VisitStack.top().first;
00068   }
00069 
00070   // This is a nonstandard operator-> that dereferences the pointer an extra
00071   // time... so that you can actually call methods ON the BasicBlock, because
00072   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
00073   //
00074   inline NodeType *operator->() const { return operator*(); }
00075 
00076   inline _Self& operator++() {   // Preincrement
00077     VisitStack.pop();
00078     if (!VisitStack.empty())
00079       traverseChild();
00080     return *this; 
00081   }
00082 
00083   inline _Self operator++(int) { // Postincrement
00084     _Self tmp = *this; ++*this; return tmp; 
00085   }
00086 };
00087 
00088 // Provide global constructors that automatically figure out correct types...
00089 //
00090 template <class T>
00091 po_iterator<T> po_begin(T G) { return po_iterator<T>::begin(G); }
00092 template <class T>
00093 po_iterator<T> po_end  (T G) { return po_iterator<T>::end(G); }
00094 
00095 // Provide global definitions of inverse post order iterators...
00096 template <class T>
00097 struct ipo_iterator : public po_iterator<Inverse<T> > {
00098   ipo_iterator(const po_iterator<Inverse<T> > &V) :po_iterator<Inverse<T> >(V){}
00099 };
00100 
00101 template <class T>
00102 ipo_iterator<T> ipo_begin(T G, bool Reverse = false) {
00103   return ipo_iterator<T>::begin(G, Reverse);
00104 }
00105 
00106 template <class T>
00107 ipo_iterator<T> ipo_end(T G){
00108   return ipo_iterator<T>::end(G);
00109 }
00110 
00111 
00112 //===--------------------------------------------------------------------===//
00113 // Reverse Post Order CFG iterator code
00114 //===--------------------------------------------------------------------===//
00115 // 
00116 // This is used to visit basic blocks in a method in reverse post order.  This
00117 // class is awkward to use because I don't know a good incremental algorithm to
00118 // computer RPO from a graph.  Because of this, the construction of the 
00119 // ReversePostOrderTraversal object is expensive (it must walk the entire graph
00120 // with a postorder iterator to build the data structures).  The moral of this
00121 // story is: Don't create more ReversePostOrderTraversal classes than necessary.
00122 //
00123 // This class should be used like this:
00124 // {
00125 //   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
00126 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
00127 //      ...
00128 //   }
00129 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
00130 //      ...
00131 //   }
00132 // }
00133 //
00134 
00135 template<class GraphT, class GT = GraphTraits<GraphT> >
00136 class ReversePostOrderTraversal {
00137   typedef typename GT::NodeType NodeType;
00138   std::vector<NodeType*> Blocks;       // Block list in normal PO order
00139   inline void Initialize(NodeType *BB) {
00140     copy(po_begin(BB), po_end(BB), back_inserter(Blocks));
00141   }
00142 public:
00143   typedef typename std::vector<NodeType*>::reverse_iterator rpo_iterator;
00144 
00145   inline ReversePostOrderTraversal(GraphT G) {
00146     Initialize(GT::getEntryNode(G));
00147   }
00148 
00149   // Because we want a reverse post order, use reverse iterators from the vector
00150   inline rpo_iterator begin() { return Blocks.rbegin(); }
00151   inline rpo_iterator end()   { return Blocks.rend(); }
00152 };
00153 
00154 } // End llvm namespace
00155 
00156 #endif