LCOV - code coverage report
Current view: top level - include/llvm/ADT - PostOrderIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 110 147 74.8 %
Date: 2018-10-20 13:21:21 Functions: 61 169 36.1 %
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             : class po_iterator_storage {
      59             :   SetType Visited;
      60             : 
      61             : public:
      62             :   // Return true if edge destination should be visited.
      63             :   template <typename NodeRef>
      64           0 :   bool insertEdge(Optional<NodeRef> From, NodeRef To) {
      65    22226691 :     return Visited.insert(To).second;
      66             :   }
      67           0 : 
      68           0 :   // Called after all children of BB have been visited.
      69           0 :   template <typename NodeRef> void finishPostorder(NodeRef BB) {}
      70           0 : };
      71           0 : 
      72             : /// Specialization of po_iterator_storage that references an external set.
      73             : template<class SetType>
      74             : class po_iterator_storage<SetType, true> {
      75           0 :   SetType &Visited;
      76             : 
      77             : public:
      78     3693125 :   po_iterator_storage(SetType &VSet) : Visited(VSet) {}
      79         126 :   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           0 :   template <class NodeRef> bool insertEdge(Optional<NodeRef> From, NodeRef To) {
      85     3693146 :     return Visited.insert(To).second;
      86             :   }
      87             : 
      88             :   // Called after all children of BB have been visited.
      89           0 :   template <class NodeRef> void finishPostorder(NodeRef BB) {}
      90           0 : };
      91           1 : 
      92             : template <class GraphT,
      93             :           class SetType =
      94             :               SmallPtrSet<typename GraphTraits<GraphT>::NodeRef, 8>,
      95             :           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
      96    16179915 : 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    11876722 : 
     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     6012938 :   po_iterator(NodeRef BB) {
     108             :     this->insertEdge(Optional<NodeRef>(), BB);
     109     3006470 :     VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     110     3006470 :     traverseChild();
     111     3006470 :   }
     112             : 
     113    10635014 :   po_iterator() = default; // End is when stack is empty.
     114             : 
     115     9011750 :   po_iterator(NodeRef BB, SetType &S)
     116     9012846 :       : po_iterator_storage<SetType, ExtStorage>(S) {
     117     9011750 :     if (this->insertEdge(Optional<NodeRef>(), BB)) {
     118     9416792 :       VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     119     3694146 :       traverseChild();
     120     2861324 :     }
     121     6555566 :   }
     122     2861872 : 
     123     4913464 :   po_iterator(SetType &S)
     124         548 :       : po_iterator_storage<SetType, ExtStorage>(S) {
     125     2456649 :   } // End is when stack is empty.
     126     2456649 : 
     127    36296096 :   void traverseChild() {
     128   102236295 :     while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) {
     129    16987273 :       NodeRef BB = *VisitStack.back().second++;
     130    30890535 :       if (this->insertEdge(Optional<NodeRef>(VisitStack.back().first), BB)) {
     131        9006 :         // If the block is not visited...
     132    39086685 :         VisitStack.push_back(std::make_pair(BB, GT::child_begin(BB)));
     133        8993 :       }
     134        8458 :     }
     135    33848918 :   }
     136             : 
     137        8458 : public:
     138             :   using pointer = typename super::pointer;
     139             : 
     140             :   // Provide static "constructors"...
     141        1585 :   static po_iterator begin(GraphT G) {
     142     2221526 :     return po_iterator(GT::getEntryNode(G));
     143     8529019 :   }
     144    31580992 :   static po_iterator end(GraphT G) { return po_iterator(); }
     145     6141983 : 
     146     6195994 :   static po_iterator begin(GraphT G, SetType &S) {
     147     3693125 :     return po_iterator(GT::getEntryNode(G), S);
     148    11372005 :   }
     149        1585 :   static po_iterator end(GraphT G, SetType &S) { return po_iterator(S); }
     150         860 : 
     151     8530997 :   bool operator==(const po_iterator &x) const {
     152    32616260 :     return VisitStack == x.VisitStack;
     153     5258424 :   }
     154     1364281 :   bool operator!=(const po_iterator &x) const { return !(*this == x); }
     155     1365069 : 
     156    21992616 :   const NodeRef &operator*() const { return VisitStack.back().first; }
     157     1795150 : 
     158         859 :   // This is a nonstandard operator-> that dereferences the pointer an extra
     159         726 :   // time... so that you can actually call methods ON the BasicBlock, because
     160     1266568 :   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
     161     7234179 :   //
     162    24024674 :   NodeRef operator->() const { return **this; }
     163     4777702 : 
     164     4778084 :   po_iterator &operator++() { // Preincrement
     165             :     this->finishPostorder(VisitStack.back().first);
     166     9555404 :     VisitStack.pop_back();
     167    24652439 :     if (!VisitStack.empty())
     168    17952249 :       traverseChild();
     169     7233734 :     return *this;
     170       29909 :   }
     171       82750 : 
     172             :   po_iterator operator++(int) { // Postincrement
     173       52841 :     po_iterator tmp = *this;
     174             :     ++*this;
     175       21451 :     return tmp;
     176      405443 :   }
     177             : };
     178      435352 : 
     179           0 : // Provide global constructors that automatically figure out correct types...
     180             : //
     181           0 : template <class T>
     182           0 : po_iterator<T> po_begin(const T &G) { return po_iterator<T>::begin(G); }
     183             : template <class T>
     184        2681 : po_iterator<T> po_end  (const T &G) { return po_iterator<T>::end(G); }
     185           0 : 
     186    10660035 : template <class T> iterator_range<po_iterator<T>> post_order(const T &G) {
     187      117122 :   return make_range(po_begin(G), po_end(G));
     188             : }
     189             : 
     190     3226997 : // Provide global definitions of external postorder iterators...
     191             : template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
     192           0 : 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    12440407 : };
     196             : 
     197             : template<class T, class SetType>
     198           1 : po_ext_iterator<T, SetType> po_ext_begin(T G, SetType &S) {
     199        1585 :   return po_ext_iterator<T, SetType>::begin(G, S);
     200         585 : }
     201     7971505 : 
     202     5341535 : 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       29909 : template <class T, class SetType>
     208       29909 : iterator_range<po_ext_iterator<T, SetType>> post_order_ext(const T &G, SetType &S) {
     209           0 :   return make_range(po_ext_begin(G, S), po_ext_end(G, S));
     210     9744411 : }
     211     7048415 : 
     212       29909 : // 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           0 :   ipo_iterator(const po_iterator<Inverse<T>, SetType, External> &V) :
     217             :      po_iterator<Inverse<T>, SetType, External> (V) {}
     218           0 : };
     219             : 
     220           0 : template <class T>
     221           0 : ipo_iterator<T> ipo_begin(const T &G) {
     222             :   return ipo_iterator<T>::begin(G);
     223             : }
     224        1013 : 
     225           0 : template <class T>
     226             : ipo_iterator<T> ipo_end(const T &G){
     227           0 :   return ipo_iterator<T>::end(G);
     228             : }
     229           0 : 
     230         548 : template <class T>
     231         548 : iterator_range<ipo_iterator<T>> inverse_post_order(const T &G) {
     232           0 :   return make_range(ipo_begin(G), ipo_end(G));
     233           0 : }
     234             : 
     235           0 : // Provide global definitions of external inverse postorder iterators...
     236           0 : template <class T, class SetType = std::set<typename GraphTraits<T>::NodeRef>>
     237          42 : 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         548 :   ipo_ext_iterator(const po_iterator<Inverse<T>, SetType, true> &V) :
     241         548 :     ipo_iterator<T, SetType, true>(V) {}
     242             : };
     243             : 
     244             : template <class T, class SetType>
     245           0 : ipo_ext_iterator<T, SetType> ipo_ext_begin(const T &G, SetType &S) {
     246           0 :   return ipo_ext_iterator<T, SetType>::begin(G, S);
     247        8458 : }
     248        8458 : 
     249             : template <class T, class SetType>
     250           0 : ipo_ext_iterator<T, SetType> ipo_ext_end(const T &G, SetType &S) {
     251           0 :   return ipo_ext_iterator<T, SetType>::end(G, S);
     252           0 : }
     253           0 : 
     254             : template <class T, class SetType>
     255             : iterator_range<ipo_ext_iterator<T, SetType>>
     256          21 : inverse_post_order_ext(const T &G, SetType &S) {
     257          21 :   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        1083 : // 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           0 : //   ReversePostOrderTraversal<Function*> RPOT(FuncPtr); // Expensive to create
     278           0 : //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
     279             : //      ...
     280             : //   }
     281             : //   for (rpo_iterator I = RPOT.begin(); I != RPOT.end(); ++I) {
     282           0 : //      ...
     283           0 : //   }
     284             : // }
     285             : //
     286             : 
     287             : template<class GraphT, class GT = GraphTraits<GraphT>>
     288      357413 : class ReversePostOrderTraversal {
     289         548 :   using NodeRef = typename GT::NodeRef;
     290             : 
     291             :   std::vector<NodeRef> Blocks; // Block list in normal PO order
     292             : 
     293      843245 :   void Initialize(NodeRef BB) {
     294      843245 :     std::copy(po_begin(BB), po_end(BB), std::back_inserter(Blocks));
     295      843244 :   }
     296             : 
     297             : public:
     298             :   using rpo_iterator = typename std::vector<NodeRef>::reverse_iterator;
     299             :   using const_rpo_iterator = typename std::vector<NodeRef>::const_reverse_iterator;
     300             : 
     301      843245 :   ReversePostOrderTraversal(GraphT G) { Initialize(GT::getEntryNode(G)); }
     302             : 
     303             :   // Because we want a reverse post order, use reverse iterators from the vector
     304             :   rpo_iterator begin() { return Blocks.rbegin(); }
     305             :   const_rpo_iterator begin() const { return Blocks.crbegin(); }
     306             :   rpo_iterator end() { return Blocks.rend(); }
     307             :   const_rpo_iterator end() const { return Blocks.crend(); }
     308             : };
     309             : 
     310             : } // end namespace llvm
     311             : 
     312             : #endif // LLVM_ADT_POSTORDERITERATOR_H

Generated by: LCOV version 1.13