LCOV - code coverage report
Current view: top level - include/llvm/ADT - PostOrderIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 68 68 100.0 %
Date: 2017-09-14 15:23:50 Functions: 106 112 94.6 %
Legend: Lines: hit not hit

          Line data    Source code
       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/Optional.h"
      21             : #include "llvm/ADT/SmallPtrSet.h"
      22             : #include "llvm/ADT/iterator_range.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   190088081 : 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    16802754 :     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       30656 :   po_iterator_storage(SetType &VSet) : Visited(VSet) {}
      79         169 :   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      118079 :     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   237770118 : 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    16015584 :   po_iterator(NodeRef BB) {
     108    21354112 :     this->insertEdge(Optional<NodeRef>(), BB);
     109    21354112 :     VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     110     5338528 :     traverseChild();
     111     5338528 :   }
     112             : 
     113    16015587 :   po_iterator() = default; // End is when stack is empty.
     114             : 
     115       19557 :   po_iterator(NodeRef BB, SetType &S)
     116       58671 :       : po_iterator_storage<SetType, ExtStorage>(S) {
     117       76654 :     if (this->insertEdge(Optional<NodeRef>(), BB)) {
     118       77828 :       VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     119       19457 :       traverseChild();
     120             :     }
     121       19557 :   }
     122             : 
     123             :   po_iterator(SetType &S)
     124       58674 :       : po_iterator_storage<SetType, ExtStorage>(S) {
     125             :   } // End is when stack is empty.
     126             : 
     127    14516989 :   void traverseChild() {
     128   130230734 :     while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
     129    40645780 :       NodeRef BB = *VisitStack.back().second++;
     130    57877430 :       if (this->insertEdge(Optional<NodeRef>(VisitStack.back().first), BB)) {
     131             :         // If the block is not visited...
     132    36636120 :         VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     133             :       }
     134             :     }
     135    14516989 :   }
     136             : 
     137             : public:
     138             :   using pointer = typename super::pointer;
     139             : 
     140             :   // Provide static "constructors"...
     141             :   static po_iterator begin(GraphT G) {
     142     5338528 :     return po_iterator(GT::getEntryNode(G));
     143             :   }
     144    10677058 :   static po_iterator end(GraphT G) { return po_iterator(); }
     145             : 
     146             :   static po_iterator begin(GraphT G, SetType &S) {
     147       19557 :     return po_iterator(GT::getEntryNode(G), S);
     148             :   }
     149       19558 :   static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
     150             : 
     151             :   bool operator==(const po_iterator &x) const {
     152    19874949 :     return VisitStack == x.VisitStack;
     153             :   }
     154    19874949 :   bool operator!=(const po_iterator &x) const { return !(*this == x); }
     155             : 
     156    29216152 :   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         514 :   NodeRef operator->() const { return **this; }
     163             : 
     164        4299 :   po_iterator &operator++() { // Preincrement
     165    29038029 :     this->finishPostorder(VisitStack.back().first);
     166    14516865 :     VisitStack.pop_back();
     167    29033730 :     if (!VisitStack.empty())
     168     9159004 :       traverseChild();
     169        4299 :     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    10677056 : po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); }
     183             : template <class T>
     184     5338529 : po_iterator<T> po_end  (const T &G) { return po_iterator<T>::end(G); }
     185             : 
     186     4134944 : template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
     187    12404832 :   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       32662 : struct po_ext_iterator : public po_iterator<T, SetType, true> {
     193             :   po_ext_iterator(const po_iterator<T, SetType, true> &V) :
     194       13774 :   po_iterator<T, SetType, true>(V) {}
     195             : };
     196             : 
     197             : template<class T, class SetType>
     198        3443 : po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
     199       10329 :   return po_ext_iterator<T, SetType>::begin(G, S);
     200             : }
     201             : 
     202             : template<class T, class SetType>
     203        3444 : po_ext_iterator<T, SetType> po_ext_end(T G, SetType &S) {
     204       13776 :   return po_ext_iterator<T, SetType>::end(G, S);
     205             : }
     206             : 
     207             : template <class T, class SetType>
     208         787 : iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
     209        3148 :   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       22624 : struct ipo_iterator : public po_iterator<Inverse<T>, SetType, External> {
     216             :   ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
     217        3232 :      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       22624 : 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        3232 :     ipo_iterator<T, SetType, true>(V) {}
     242             : };
     243             : 
     244             : template <class T, class SetType>
     245         808 : ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) {
     246        3232 :   return ipo_ext_iterator<T, SetType>::begin(G, S);
     247             : }
     248             : 
     249             : template <class T, class SetType>
     250         808 : ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) {
     251        3232 :   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         808 : inverse_post_order_ext(const T &G, SetType &S) {
     257        3232 :   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      856178 : class ReversePostOrderTraversal {
     289             :   using NodeRef = typename GT::NodeRef;
     290             : 
     291             :   std::vector<NodeRef> Blocks; // Block list in normal PO order
     292             : 
     293      428164 :   void Initialize(NodeRef BB) {
     294     1712656 :     std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
     295      428164 :   }
     296             : 
     297             : public:
     298             :   using rpo_iterator = typename std::vector<NodeRef>::reverse_iterator;
     299             : 
     300     1172405 :   ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
     301             : 
     302             :   // Because we want a reverse post order, use reverse iterators from the vector
     303     1208650 :   rpo_iterator begin() { return Blocks.rbegin(); }
     304     1178986 :   rpo_iterator end() { return Blocks.rend(); }
     305             : };
     306             : 
     307             : } // end namespace llvm
     308             : 
     309             : #endif // LLVM_ADT_POSTORDERITERATOR_H

Generated by: LCOV version 1.13