LCOV - code coverage report
Current view: top level - include/llvm/ADT - SCCIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 54 59 91.5 %
Date: 2018-07-13 00:08:38 Functions: 43 50 86.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- ADT/SCCIterator.h - Strongly Connected Comp. Iter. -------*- 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             : /// \file
      10             : ///
      11             : /// This builds on the llvm/ADT/GraphTraits.h file to find the strongly
      12             : /// connected components (SCCs) of a graph in O(N+E) time using Tarjan's DFS
      13             : /// algorithm.
      14             : ///
      15             : /// The SCC iterator has the important property that if a node in SCC S1 has an
      16             : /// edge to a node in SCC S2, then it visits S1 *after* S2.
      17             : ///
      18             : /// To visit S1 *before* S2, use the scc_iterator on the Inverse graph. (NOTE:
      19             : /// This requires some simple wrappers and is not supported yet.)
      20             : ///
      21             : //===----------------------------------------------------------------------===//
      22             : 
      23             : #ifndef LLVM_ADT_SCCITERATOR_H
      24             : #define LLVM_ADT_SCCITERATOR_H
      25             : 
      26             : #include "llvm/ADT/DenseMap.h"
      27             : #include "llvm/ADT/GraphTraits.h"
      28             : #include "llvm/ADT/iterator.h"
      29             : #include <cassert>
      30             : #include <cstddef>
      31             : #include <iterator>
      32             : #include <vector>
      33             : 
      34             : namespace llvm {
      35             : 
      36             : /// Enumerate the SCCs of a directed graph in reverse topological order
      37             : /// of the SCC DAG.
      38             : ///
      39             : /// This is implemented using Tarjan's DFS algorithm using an internal stack to
      40             : /// build up a vector of nodes in a particular SCC. Note that it is a forward
      41             : /// iterator and thus you cannot backtrack or re-visit nodes.
      42             : template <class GraphT, class GT = GraphTraits<GraphT>>
      43     1434688 : class scc_iterator : public iterator_facade_base<
      44             :                          scc_iterator<GraphT, GT>, std::forward_iterator_tag,
      45             :                          const std::vector<typename GT::NodeRef>, ptrdiff_t> {
      46             :   using NodeRef = typename GT::NodeRef;
      47             :   using ChildItTy = typename GT::ChildIteratorType;
      48             :   using SccTy = std::vector<NodeRef>;
      49             :   using reference = typename scc_iterator::reference;
      50             : 
      51             :   /// Element of VisitStack during DFS.
      52       45568 :   struct StackElement {
      53             :     NodeRef Node;         ///< The current node pointer.
      54             :     ChildItTy NextChild;  ///< The next child, modified inplace during DFS.
      55             :     unsigned MinVisited;  ///< Minimum uplink value of all children of Node.
      56             : 
      57     2144274 :     StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
      58     2157586 :         : Node(Node), NextChild(Child), MinVisited(Min) {}
      59             : 
      60             :     bool operator==(const StackElement &Other) const {
      61           0 :       return Node == Other.Node &&
      62           0 :              NextChild == Other.NextChild &&
      63           0 :              MinVisited == Other.MinVisited;
      64             :     }
      65             :   };
      66             : 
      67             :   /// The visit counters used to detect when a complete SCC is on the stack.
      68             :   /// visitNum is the global counter.
      69             :   ///
      70             :   /// nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
      71             :   unsigned visitNum;
      72             :   DenseMap<NodeRef, unsigned> nodeVisitNumbers;
      73             : 
      74             :   /// Stack holding nodes of the SCC.
      75             :   std::vector<NodeRef> SCCNodeStack;
      76             : 
      77             :   /// The current SCC, retrieved using operator*().
      78             :   SccTy CurrentSCC;
      79             : 
      80             :   /// DFS stack, Used to maintain the ordering.  The top contains the current
      81             :   /// node, the next child to visit, and the minimum uplink value of all child
      82             :   std::vector<StackElement> VisitStack;
      83             : 
      84             :   /// A single "visit" within the non-recursive DFS traversal.
      85             :   void DFSVisitOne(NodeRef N);
      86             : 
      87             :   /// The stack-based DFS traversal; defined below.
      88             :   void DFSVisitChildren();
      89             : 
      90             :   /// Compute the next SCC using the DFS traversal.
      91             :   void GetNextSCC();
      92             : 
      93             : public:
      94      713256 :   scc_iterator(NodeRef entryN) : visitNum(0) {
      95      713256 :     DFSVisitOne(entryN);
      96      713256 :     GetNextSCC();
      97      713256 :   }
      98             : 
      99             :   /// End is when the DFS stack is empty.
     100             :   scc_iterator() = default;
     101             : 
     102             :   /// Direct loop termination test which is more efficient than
     103             :   /// comparison with \c end().
     104             :   bool isAtEnd() const {
     105             :     assert(!CurrentSCC.empty() || VisitStack.empty());
     106             :     return CurrentSCC.empty();
     107             :   }
     108             : 
     109       10022 :   bool operator==(const scc_iterator &x) const {
     110       10022 :     return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
     111             :   }
     112             : 
     113             :   scc_iterator &operator++() {
     114     1988711 :     GetNextSCC();
     115             :     return *this;
     116             :   }
     117             : 
     118             :   reference operator*() const {
     119             :     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     120             :     return CurrentSCC;
     121             :   }
     122             : 
     123             :   /// Test if the current SCC has a loop.
     124             :   ///
     125             :   /// If the SCC has more than one node, this is trivially true.  If not, it may
     126             :   /// still contain a loop if the node has an edge back to itself.
     127             :   bool hasLoop() const;
     128             : 
     129             :   /// This informs the \c scc_iterator that the specified \c Old node
     130             :   /// has been deleted, and \c New is to be used in its place.
     131          45 :   void ReplaceNode(NodeRef Old, NodeRef New) {
     132             :     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     133          90 :     nodeVisitNumbers[New] = nodeVisitNumbers[Old];
     134          45 :     nodeVisitNumbers.erase(Old);
     135          45 :   }
     136             : };
     137             : 
     138             : template <class GraphT, class GT>
     139     2144274 : void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
     140     2144274 :   ++visitNum;
     141     4288548 :   nodeVisitNumbers[N] = visitNum;
     142     2144274 :   SCCNodeStack.push_back(N);
     143     4291611 :   VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
     144             : #if 0 // Enable if needed when debugging.
     145             :   dbgs() << "TarjanSCC: Node " << N <<
     146             :         " : visitNum = " << visitNum << "\n";
     147             : #endif
     148     2144274 : }
     149             : 
     150             : template <class GraphT, class GT>
     151     2144266 : void scc_iterator<GraphT, GT>::DFSVisitChildren() {
     152             :   assert(!VisitStack.empty());
     153    10137787 :   while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
     154             :     // TOS has at least one more child so continue DFS
     155     1516638 :     NodeRef childN = *VisitStack.back().NextChild++;
     156     2947930 :     typename DenseMap<NodeRef, unsigned>::iterator Visited =
     157             :         nodeVisitNumbers.find(childN);
     158     4378948 :     if (Visited == nodeVisitNumbers.end()) {
     159             :       // this node has never been seen.
     160     1431018 :       DFSVisitOne(childN);
     161     1431018 :       continue;
     162             :     }
     163             : 
     164     1516912 :     unsigned childNum = Visited->second;
     165     1516912 :     if (VisitStack.back().MinVisited > childNum)
     166       51318 :       VisitStack.back().MinVisited = childNum;
     167             :   }
     168     2144266 : }
     169             : 
     170     2701967 : template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
     171     2701967 :   CurrentSCC.clear(); // Prepare to compute the next SCC
     172     2857514 :   while (!VisitStack.empty()) {
     173     2144266 :     DFSVisitChildren();
     174             : 
     175             :     // Pop the leaf on top of the VisitStack.
     176     2144266 :     NodeRef visitingN = VisitStack.back().Node;
     177     2144266 :     unsigned minVisitNum = VisitStack.back().MinVisited;
     178             :     assert(VisitStack.back().NextChild == GT::child_end(visitingN));
     179             :     VisitStack.pop_back();
     180             : 
     181             :     // Propagate MinVisitNum to parent so we can detect the SCC starting node.
     182     2144266 :     if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)
     183      107099 :       VisitStack.back().MinVisited = minVisitNum;
     184             : 
     185             : #if 0 // Enable if needed when debugging.
     186             :     dbgs() << "TarjanSCC: Popped node " << visitingN <<
     187             :           " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
     188             :           nodeVisitNumbers[visitingN] << "\n";
     189             : #endif
     190             : 
     191     4288532 :     if (minVisitNum != nodeVisitNumbers[visitingN])
     192      155547 :       continue;
     193             : 
     194             :     // A full SCC is on the SCCNodeStack!  It includes all nodes below
     195             :     // visitingN on the stack.  Copy those nodes to CurrentSCC,
     196             :     // reset their minVisit values, and return (this suspends
     197             :     // the DFS traversal till the next ++).
     198             :     do {
     199     2144266 :       CurrentSCC.push_back(SCCNodeStack.back());
     200             :       SCCNodeStack.pop_back();
     201     2144266 :       nodeVisitNumbers[CurrentSCC.back()] = ~0U;
     202     2144266 :     } while (CurrentSCC.back() != visitingN);
     203     1988719 :     return;
     204             :   }
     205             : }
     206             : 
     207             : template <class GraphT, class GT>
     208           6 : bool scc_iterator<GraphT, GT>::hasLoop() const {
     209             :     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     210          12 :     if (CurrentSCC.size() > 1)
     211             :       return true;
     212           4 :     NodeRef N = CurrentSCC.front();
     213           9 :     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
     214             :          ++CI)
     215           5 :       if (*CI == N)
     216           0 :         return true;
     217           0 :     return false;
     218             :   }
     219             : 
     220             : /// Construct the begin iterator for a deduced graph type T, starting from its
     221             : /// entry node.
     222             : template <class T> scc_iterator<T> scc_begin(const T &G) {
     223      696894 :   return scc_iterator<T>(GraphTraits<T>::getEntryNode(G));
     224             : }
     225             : 
     226             : /// Construct the begin iterator for a graph type T, starting from the specified
     227             : /// node.
     228             : template <class T, class U = GraphTraits<T>>
     229             : scc_iterator<T, U> scc_begin(typename U::NodeRef N) {
     230       16362 :   return scc_iterator<T>(N);
     231             : }
     232             : 
     233             :   /// Construct the end iterator for a deduced graph type T.
     234             : template <class T> scc_iterator<T> scc_end(const T &G) {
     235        4096 :   return scc_iterator<T>();
     236             : }
     237             : 
     238             : 
     239             : } // end namespace llvm
     240             : 
     241             : #endif // LLVM_ADT_SCCITERATOR_H

Generated by: LCOV version 1.13