include/llvm/ADT/PostOrderIterator.h

   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/iterator_range.h"
  21 #include "llvm/ADT/Optional.h"
  22 #include "llvm/ADT/SmallPtrSet.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>
  58 class po_iterator_storage {
  59   SetType Visited;
  60
  61 public:
  62   // Return true if edge destination should be visited.
  63   template <typename NodeRef>
  64   bool insertEdge(Optional<NodeRef> From, NodeRef To) {
  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,
  93           class SetType =
  94               SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
  95           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
  96 class po_iterator
  97     : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
  98       public po_iterator_storage<SetType, ExtStorage> {
  99   using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
 100   using NodeRef = typename GT::NodeRef;
 101   using ChildItTy = typename GT::ChildIteratorType;
 102
 103   // VisitStack - Used to maintain the ordering.  Top = current block
 104   // First element is basic block pointer, second is the 'next child' to visit
 105   std::vector<std::pair<NodeRef, ChildItTy>> VisitStack;
 106
 107   po_iterator(NodeRef BB) {
 108     this->insertEdge(Optional<NodeRef>(), BB);
 109     VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
 110     traverseChild();
 111   }
 112
 113   po_iterator() = default; // End is when stack is empty.
 114
 115   po_iterator(NodeRef BB, SetType &S)
 116       : po_iterator_storage<SetType, ExtStorage>(S) {
 117     if (this->insertEdge(Optional<NodeRef>(), BB)) {
 118       VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
 119       traverseChild();
 120     }
 121   }
 122
 123   po_iterator(SetType &S)
 124       : po_iterator_storage<SetType, ExtStorage>(S) {
 125   } // End is when stack is empty.
 126
 127   void traverseChild() {
 128     while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
 129       NodeRef BB = *VisitStack.back().second++;
 130       if (this->insertEdge(Optional<NodeRef>(VisitStack.back().first), BB)) {
 131         // If the block is not visited...
 132         VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
 133       }
 134     }
 135   }
 136
 137 public:
 138   using pointer = typename super::pointer;
 139
 140   // Provide static "constructors"...
 141   static po_iterator begin(GraphT G) {
 142     return po_iterator(GT::getEntryNode(G));
 143   }
 144   static po_iterator end(GraphT G) { return po_iterator(); }
 145
 146   static po_iterator begin(GraphT G, SetType &S) {
 147     return po_iterator(GT::getEntryNode(G), S);
 148   }
 149   static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
 150
 151   bool operator==(const po_iterator &x) const {
 152     return VisitStack == x.VisitStack;
 153   }
 154   bool operator!=(const po_iterator &x) const { return !(*this == x); }
 155
 156   const NodeRef &operator*() const { return VisitStack.back().first; }
 157
 158   // This is a nonstandard operator-> that dereferences the pointer an extra
 159   // time... so that you can actually call methods ON the BasicBlock, because
 160   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
 161   //
 162   NodeRef operator->() const { return **this; }
 163
 164   po_iterator &operator++() { // Preincrement
 165     this->finishPostorder(VisitStack.back().first);
 166     VisitStack.pop_back();
 167     if (!VisitStack.empty())
 168       traverseChild();
 169     return *this;
 170   }
 171
 172   po_iterator operator++(int) { // Postincrement
 173     po_iterator tmp = *this;
 174     ++*this;
 175     return tmp;
 176   }
 177 };
 178
 179 // Provide global constructors that automatically figure out correct types...
 180 //
 181 template <class T>
 182 po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); }
 183 template <class T>
 184 po_iterator<T> po_end  (const T &G) { return po_iterator<T>::end(G); }
 185
 186 template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
 187   return make_range(po_begin(G), po_end(G));
 188 }
 189
 190 // Provide global definitions of external postorder iterators...
 191 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 192 struct po_ext_iterator : public po_iterator<T, SetType, true> {
 193   po_ext_iterator(const po_iterator<T, SetType, true> &V) :
 194   po_iterator<T, SetType, true>(V) {}
 195 };
 196
 197 template<class T, class SetType>
 198 po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
 199   return po_ext_iterator<T, SetType>::begin(G, S);
 200 }
 201
 202 template<class T, class SetType>
 203 po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
 204   return po_ext_iterator<T, SetType>::end(G, S);
 205 }
 206
 207 template <class T, class SetType>
 208 iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
 209   return make_range(po_ext_begin(G, S), po_ext_end(G, S));
 210 }
 211
 212 // Provide global definitions of inverse post order iterators...
 213 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>,
 214           bool External = false>
 215 struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External> {
 216   ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
 217      po_iterator<Inverse<T>, SetType, External> (V) {}
 218 };
 219
 220 template <class T>
 221 ipo_iterator<T> ipo_begin(const T &G) {
 222   return ipo_iterator<T>::begin(G);
 223 }
 224
 225 template <class T>
 226 ipo_iterator<T> ipo_end(const T &G){
 227   return ipo_iterator<T>::end(G);
 228 }
 229
 230 template <class T>
 231 iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
 232   return make_range(ipo_begin(G), ipo_end(G));
 233 }
 234
 235 // Provide global definitions of external inverse postorder iterators...
 236 template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
 237 struct ipo_ext_iterator : public ipo_iterator<T, SetType, true> {
 238   ipo_ext_iterator(const ipo_iterator<T, SetType, true> &V) :
 239     ipo_iterator<T, SetType, true>(V) {}
 240   ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
 241     ipo_iterator<T, SetType, true>(V) {}
 242 };
 243
 244 template <class T, class SetType>
 245 ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) {
 246   return ipo_ext_iterator<T, SetType>::begin(G, S);
 247 }
 248
 249 template <class T, class SetType>
 250 ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) {
 251   return ipo_ext_iterator<T, SetType>::end(G, S);
 252 }
 253
 254 template <class T, class SetType>
 255 iterator_range<ipo_ext_iterator<T, SetType>>
 256 inverse_post_order_ext(const T &G, SetType &S) {
 257   return make_range(ipo_ext_begin(G, S), ipo_ext_end(G, S));
 258 }
 259
 260 //===--------------------------------------------------------------------===//
 261 // Reverse Post Order CFG iterator code
 262 //===--------------------------------------------------------------------===//
 263 //
 264 // This is used to visit basic blocks in a method in reverse post order.  This
 265 // class is awkward to use because I don't know a good incremental algorithm to
 266 // computer RPO from a graph.  Because of this, the construction of the
 267 // ReversePostOrderTraversal object is expensive (it must walk the entire graph
 268 // with a postorder iterator to build the data structures).  The moral of this
 269 // story is: Don't create more ReversePostOrderTraversal classes than necessary.
 270 //
 271 // Because it does the traversal in its constructor, it won't invalidate when
 272 // BasicBlocks are removed, *but* it may contain erased blocks. Some places
 273 // rely on this behavior (i.e. GVN).
 274 //
 275 // This class should be used like this:
 276 // {
 277 //   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
 278 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
 279 //      ...
 280 //   }
 281 //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
 282 //      ...
 283 //   }
 284 // }
 285 //
 286
 287 template<class GraphT, class GT = GraphTraits<GraphT>>
 288 class ReversePostOrderTraversal {
 289   using NodeRef = typename GT::NodeRef;
 290
 291   std::vector<NodeRef> Blocks; // Block list in normal PO order
 292
 293   void Initialize(NodeRef BB) {
 294     std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
 295   }
 296
 297 public:
 298   using rpo_iterator = typename std::vector<NodeRef>::reverse_iterator;
 299
 300   ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
 301
 302   // Because we want a reverse post order, use reverse iterators from the vector
 303   rpo_iterator begin() { return Blocks.rbegin(); }
 304   rpo_iterator end() { return Blocks.rend(); }
 305 };
 306
 307 } // end namespace llvm
 308
 309 #endif // LLVM_ADT_POSTORDERITERATOR_H