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

          Line data    Source code
       1             : //===- llvm/ADT/DepthFirstIterator.h - Depth First 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 generic depth
      11             : // first graph iterator.  This file exposes the following functions/types:
      12             : //
      13             : // df_begin/df_end/df_iterator
      14             : //   * Normal depth-first iteration - visit a node and then all of its children.
      15             : //
      16             : // idf_begin/idf_end/idf_iterator
      17             : //   * Depth-first iteration on the 'inverse' graph.
      18             : //
      19             : // df_ext_begin/df_ext_end/df_ext_iterator
      20             : //   * Normal depth-first iteration - visit a node and then all of its children.
      21             : //     This iterator stores the 'visited' set in an external set, which allows
      22             : //     it to be more efficient, and allows external clients to use the set for
      23             : //     other purposes.
      24             : //
      25             : // idf_ext_begin/idf_ext_end/idf_ext_iterator
      26             : //   * Depth-first iteration on the 'inverse' graph.
      27             : //     This iterator stores the 'visited' set in an external set, which allows
      28             : //     it to be more efficient, and allows external clients to use the set for
      29             : //     other purposes.
      30             : //
      31             : //===----------------------------------------------------------------------===//
      32             : 
      33             : #ifndef LLVM_ADT_DEPTHFIRSTITERATOR_H
      34             : #define LLVM_ADT_DEPTHFIRSTITERATOR_H
      35             : 
      36             : #include "llvm/ADT/GraphTraits.h"
      37             : #include "llvm/ADT/None.h"
      38             : #include "llvm/ADT/Optional.h"
      39             : #include "llvm/ADT/SmallPtrSet.h"
      40             : #include "llvm/ADT/iterator_range.h"
      41             : #include <iterator>
      42             : #include <set>
      43             : #include <utility>
      44             : #include <vector>
      45             : 
      46             : namespace llvm {
      47             : 
      48             : // df_iterator_storage - A private class which is used to figure out where to
      49             : // store the visited set.
      50             : template<class SetType, bool External>   // Non-external set
      51    11666528 : class df_iterator_storage {
      52             : public:
      53             :   SetType Visited;
      54             : };
      55             : 
      56             : template<class SetType>
      57             : class df_iterator_storage<SetType, true> {
      58             : public:
      59     3275318 :   df_iterator_storage(SetType &VSet) : Visited(VSet) {}
      60     6160292 :   df_iterator_storage(const df_iterator_storage &S) : Visited(S.Visited) {}
      61             : 
      62             :   SetType &Visited;
      63             : };
      64             : 
      65             : // The visited stated for the iteration is a simple set augmented with
      66             : // one more method, completed, which is invoked when all children of a
      67             : // node have been processed. It is intended to distinguish of back and
      68             : // cross edges in the spanning tree but is not used in the common case.
      69             : template <typename NodeRef, unsigned SmallSize=8>
      70    18081056 : struct df_iterator_default_set : public SmallPtrSet<NodeRef, SmallSize> {
      71             :   using BaseSet = SmallPtrSet<NodeRef, SmallSize>;
      72             :   using iterator = typename BaseSet::iterator;
      73             : 
      74     4828188 :   std::pair<iterator,bool> insert(NodeRef N) { return BaseSet::insert(N); }
      75             :   template <typename IterT>
      76             :   void insert(IterT Begin, IterT End) { BaseSet::insert(Begin,End); }
      77             : 
      78             :   void completed(NodeRef) {}
      79             : };
      80             : 
      81             : // Generic Depth First Iterator
      82             : template <class GraphT,
      83             :           class SetType =
      84             :               df_iterator_default_set<typename GraphTraits<GraphT>::NodeRef>,
      85             :           bool ExtStorage = false, class GT = GraphTraits<GraphT>>
      86    47613988 : class df_iterator
      87             :     : public std::iterator<std::forward_iterator_tag, typename GT::NodeRef>,
      88             :       public df_iterator_storage<SetType, ExtStorage> {
      89             :   using super = std::iterator<std::forward_iterator_tag, typename GT::NodeRef>;
      90             :   using NodeRef = typename GT::NodeRef;
      91             :   using ChildItTy = typename GT::ChildIteratorType;
      92             : 
      93             :   // First element is node reference, second is the 'next child' to visit.
      94             :   // The second child is initialized lazily to pick up graph changes during the
      95             :   // DFS.
      96             :   using StackElement = std::pair<NodeRef, Optional<ChildItTy>>;
      97             : 
      98             :   // VisitStack - Used to maintain the ordering.  Top = current block
      99             :   std::vector<StackElement> VisitStack;
     100             : 
     101             : private:
     102     1165014 :   inline df_iterator(NodeRef Node) {
     103      776676 :     this->Visited.insert(Node);
     104     1553352 :     VisitStack.push_back(StackElement(Node, None));
     105      388338 :   }
     106             : 
     107     1098126 :   inline df_iterator() = default; // End is when stack is empty
     108             : 
     109     1637660 :   inline df_iterator(NodeRef Node, SetType &S)
     110     4912980 :       : df_iterator_storage<SetType, ExtStorage>(S) {
     111     3275320 :     if (this->Visited.insert(Node).second)
     112     6550244 :       VisitStack.push_back(StackElement(Node, None));
     113     1637660 :   }
     114             : 
     115             :   inline df_iterator(SetType &S)
     116     4912979 :     : df_iterator_storage<SetType, ExtStorage>(S) {
     117             :     // End is when stack is empty
     118             :   }
     119             : 
     120     4225243 :   inline void toNext() {
     121             :     do {
     122    12849998 :       NodeRef Node = VisitStack.back().first;
     123    12849998 :       Optional<ChildItTy> &Opt = VisitStack.back().second;
     124             : 
     125     6424999 :       if (!Opt)
     126     8449136 :         Opt.emplace(GT::child_begin(Node));
     127             : 
     128             :       // Notice that we directly mutate *Opt here, so that
     129             :       // VisitStack.back().second actually gets updated as the iterator
     130             :       // increases.
     131    21685070 :       while (*Opt != GT::child_end(Node)) {
     132     7502016 :         NodeRef Next = *(*Opt)++;
     133             :         // Has our next sibling been visited?
     134     6027772 :         if (this->Visited.insert(Next).second) {
     135             :           // No, do it now.
     136     8804748 :           VisitStack.push_back(StackElement(Next, None));
     137     2201187 :           return;
     138             :         }
     139             :       }
     140     4391267 :       this->Visited.completed(Node);
     141             : 
     142             :       // Oops, ran out of successors... go up a level on the stack.
     143     4223812 :       VisitStack.pop_back();
     144     8447624 :     } while (!VisitStack.empty());
     145             :   }
     146             : 
     147             : public:
     148             :   using pointer = typename super::pointer;
     149             : 
     150             :   // Provide static begin and end methods as our public "constructors"
     151             :   static df_iterator begin(const GraphT &G) {
     152      488562 :     return df_iterator(GT::getEntryNode(G));
     153             :   }
     154      732084 :   static df_iterator end(const GraphT &G) { return df_iterator(); }
     155             : 
     156             :   // Static begin and end methods as our public ctors for external iterators
     157             :   static df_iterator begin(const GraphT &G, SetType &S) {
     158     3097635 :     return df_iterator(GT::getEntryNode(G), S);
     159             :   }
     160     1637660 :   static df_iterator end(const GraphT &G, SetType &S) { return df_iterator(S); }
     161             : 
     162             :   bool operator==(const df_iterator &x) const {
     163     6252058 :     return VisitStack == x.VisitStack;
     164             :   }
     165     6252057 :   bool operator!=(const df_iterator &x) const { return !(*this == x); }
     166             : 
     167     8520480 :   const NodeRef &operator*() const { return VisitStack.back().first; }
     168             : 
     169             :   // This is a nonstandard operator-> that dereferences the pointer an extra
     170             :   // time... so that you can actually call methods ON the Node, because
     171             :   // the contained type is a pointer.  This allows BBIt->getTerminator() f.e.
     172             :   //
     173       48048 :   NodeRef operator->() const { return **this; }
     174             : 
     175             :   df_iterator &operator++() { // Preincrement
     176     4224567 :     toNext();
     177             :     return *this;
     178             :   }
     179             : 
     180             :   /// \brief Skips all children of the current node and traverses to next node
     181             :   ///
     182             :   /// Note: This function takes care of incrementing the iterator. If you
     183             :   /// always increment and call this function, you risk walking off the end.
     184             :   df_iterator &skipChildren() {
     185        1461 :     VisitStack.pop_back();
     186        2922 :     if (!VisitStack.empty())
     187         675 :       toNext();
     188             :     return *this;
     189             :   }
     190             : 
     191             :   df_iterator operator++(int) { // Postincrement
     192             :     df_iterator tmp = *this;
     193             :     ++*this;
     194             :     return tmp;
     195             :   }
     196             : 
     197             :   // nodeVisited - return true if this iterator has already visited the
     198             :   // specified node.  This is public, and will probably be used to iterate over
     199             :   // nodes that a depth first iteration did not find: ie unreachable nodes.
     200             :   //
     201             :   bool nodeVisited(NodeRef Node) const {
     202        1045 :     return this->Visited.count(Node) != 0;
     203             :   }
     204             : 
     205             :   /// getPathLength - Return the length of the path from the entry node to the
     206             :   /// current node, counting both nodes.
     207     3580516 :   unsigned getPathLength() const { return VisitStack.size(); }
     208             : 
     209             :   /// getPath - Return the n'th node in the path from the entry node to the
     210             :   /// current node.
     211      846264 :   NodeRef getPath(unsigned n) const { return VisitStack[n].first; }
     212             : };
     213             : 
     214             : // Provide global constructors that automatically figure out correct types...
     215             : //
     216             : template <class T>
     217             : df_iterator<T> df_begin(const T& G) {
     218      360015 :   return df_iterator<T>::begin(G);
     219             : }
     220             : 
     221             : template <class T>
     222             : df_iterator<T> df_end(const T& G) {
     223      360015 :   return df_iterator<T>::end(G);
     224             : }
     225             : 
     226             : // Provide an accessor method to use them in range-based patterns.
     227             : template <class T>
     228      337368 : iterator_range<df_iterator<T>> depth_first(const T& G) {
     229     1012104 :   return make_range(df_begin(G), df_end(G));
     230             : }
     231             : 
     232             : // Provide global definitions of external depth first iterators...
     233             : template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
     234    18082494 : struct df_ext_iterator : public df_iterator<T, SetTy, true> {
     235             :   df_ext_iterator(const df_iterator<T, SetTy, true> &V)
     236     6549490 :     : df_iterator<T, SetTy, true>(V) {}
     237             : };
     238             : 
     239             : template <class T, class SetTy>
     240     1637373 : df_ext_iterator<T, SetTy> df_ext_begin(const T& G, SetTy &S) {
     241     6549491 :   return df_ext_iterator<T, SetTy>::begin(G, S);
     242             : }
     243             : 
     244             : template <class T, class SetTy>
     245     1637372 : df_ext_iterator<T, SetTy> df_ext_end(const T& G, SetTy &S) {
     246     6549490 :   return df_ext_iterator<T, SetTy>::end(G, S);
     247             : }
     248             : 
     249             : template <class T, class SetTy>
     250      480542 : iterator_range<df_ext_iterator<T, SetTy>> depth_first_ext(const T& G,
     251             :                                                           SetTy &S) {
     252     1922168 :   return make_range(df_ext_begin(G, S), df_ext_end(G, S));
     253             : }
     254             : 
     255             : // Provide global definitions of inverse depth first iterators...
     256             : template <class T,
     257             :           class SetTy =
     258             :               df_iterator_default_set<typename GraphTraits<T>::NodeRef>,
     259             :           bool External = false>
     260        8723 : struct idf_iterator : public df_iterator<Inverse<T>, SetTy, External> {
     261             :   idf_iterator(const df_iterator<Inverse<T>, SetTy, External> &V)
     262        2522 :     : df_iterator<Inverse<T>, SetTy, External>(V) {}
     263             : };
     264             : 
     265             : template <class T>
     266         335 : idf_iterator<T> idf_begin(const T& G) {
     267        1005 :   return idf_iterator<T>::begin(Inverse<T>(G));
     268             : }
     269             : 
     270             : template <class T>
     271         335 : idf_iterator<T> idf_end(const T& G){
     272        1005 :   return idf_iterator<T>::end(Inverse<T>(G));
     273             : }
     274             : 
     275             : // Provide an accessor method to use them in range-based patterns.
     276             : template <class T>
     277             : iterator_range<idf_iterator<T>> inverse_depth_first(const T& G) {
     278             :   return make_range(idf_begin(G), idf_end(G));
     279             : }
     280             : 
     281             : // Provide global definitions of external inverse depth first iterators...
     282             : template <class T, class SetTy = std::set<typename GraphTraits<T>::NodeRef>>
     283        8036 : struct idf_ext_iterator : public idf_iterator<T, SetTy, true> {
     284             :   idf_ext_iterator(const idf_iterator<T, SetTy, true> &V)
     285             :     : idf_iterator<T, SetTy, true>(V) {}
     286             :   idf_ext_iterator(const df_iterator<Inverse<T>, SetTy, true> &V)
     287        1148 :     : idf_iterator<T, SetTy, true>(V) {}
     288             : };
     289             : 
     290             : template <class T, class SetTy>
     291         287 : idf_ext_iterator<T, SetTy> idf_ext_begin(const T& G, SetTy &S) {
     292        1148 :   return idf_ext_iterator<T, SetTy>::begin(Inverse<T>(G), S);
     293             : }
     294             : 
     295             : template <class T, class SetTy>
     296         287 : idf_ext_iterator<T, SetTy> idf_ext_end(const T& G, SetTy &S) {
     297        1148 :   return idf_ext_iterator<T, SetTy>::end(Inverse<T>(G), S);
     298             : }
     299             : 
     300             : template <class T, class SetTy>
     301         287 : iterator_range<idf_ext_iterator<T, SetTy>> inverse_depth_first_ext(const T& G,
     302             :                                                                    SetTy &S) {
     303        1148 :   return make_range(idf_ext_begin(G, S), idf_ext_end(G, S));
     304             : }
     305             : 
     306             : } // end namespace llvm
     307             : 
     308             : #endif // LLVM_ADT_DEPTHFIRSTITERATOR_H

Generated by: LCOV version 1.13