LCOV - code coverage report
Current view: top level - include/llvm/ADT - SCCIterator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 54 64 84.4 %
Date: 2017-09-14 15:23:50 Functions: 35 42 83.3 %
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             : /// \brief 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      511634 : 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      171574 :   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      401561 :     StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)
      58      429231 :         : 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      326230 :   scc_iterator(NodeRef entryN) : visitNum(0) {
      94       65246 :     DFSVisitOne(entryN);
      95       65246 :     GetNextSCC();
      96       65246 :   }
      97             : 
      98             :   /// End is when the DFS stack is empty.
      99       34460 :   scc_iterator() = default;
     100             : 
     101             : public:
     102             :   static scc_iterator begin(const GraphT &G) {
     103      123482 :     return scc_iterator(GT::getEntryNode(G));
     104             :   }
     105       13784 :   static scc_iterator end(const GraphT &) { return scc_iterator(); }
     106             : 
     107             :   /// \brief Direct loop termination test which is more efficient than
     108             :   /// comparison with \c end().
     109             :   bool isAtEnd() const {
     110             :     assert(!CurrentSCC.empty() || VisitStack.empty());
     111      861094 :     return CurrentSCC.empty();
     112             :   }
     113             : 
     114       27173 :   bool operator==(const scc_iterator &x) const {
     115       27173 :     return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
     116             :   }
     117             : 
     118             :   scc_iterator &operator++() {
     119      392482 :     GetNextSCC();
     120             :     return *this;
     121             :   }
     122             : 
     123             :   reference operator*() const {
     124             :     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     125             :     return CurrentSCC;
     126             :   }
     127             : 
     128             :   /// \brief Test if the current SCC has a loop.
     129             :   ///
     130             :   /// If the SCC has more than one node, this is trivially true.  If not, it may
     131             :   /// still contain a loop if the node has an edge back to itself.
     132             :   bool hasLoop() const;
     133             : 
     134             :   /// This informs the \c scc_iterator that the specified \c Old node
     135             :   /// has been deleted, and \c New is to be used in its place.
     136          42 :   void ReplaceNode(NodeRef Old, NodeRef New) {
     137             :     assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");
     138         126 :     nodeVisitNumbers[New] = nodeVisitNumbers[Old];
     139          42 :     nodeVisitNumbers.erase(Old);
     140          42 :   }
     141             : };
     142             : 
     143             : template <class GraphT, class GT>
     144      401561 : void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
     145      401561 :   ++visitNum;
     146      803122 :   nodeVisitNumbers[N] = visitNum;
     147      401561 :   SCCNodeStack.push_back(N);
     148     1620602 :   VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
     149             : #if 0 // Enable if needed when debugging.
     150             :   dbgs() << "TarjanSCC: Node " << N <<
     151             :         " : visitNum = " << visitNum << "\n";
     152             : #endif
     153      401561 : }
     154             : 
     155             : template <class GraphT, class GT>
     156      401560 : void scc_iterator<GraphT, GT>::DFSVisitChildren() {
     157             :   assert(!VisitStack.empty());
     158     9633696 :   while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
     159             :     // TOS has at least one more child so continue DFS
     160     4629920 :     NodeRef childN = *VisitStack.back().NextChild++;
     161     1533376 :     typename DenseMap<NodeRef, unsigned>::iterator Visited =
     162             :         nodeVisitNumbers.find(childN);
     163     4936443 :     if (Visited == nodeVisitNumbers.end()) {
     164             :       // this node has never been seen.
     165      336315 :       DFSVisitOne(childN);
     166      336315 :       continue;
     167             :     }
     168             : 
     169     1197061 :     unsigned childNum = Visited->second;
     170     2394122 :     if (VisitStack.back().MinVisited > childNum)
     171       13906 :       VisitStack.back().MinVisited = childNum;
     172             :   }
     173      401560 : }
     174             : 
     175      457728 : template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
     176      457728 :   CurrentSCC.clear(); // Prepare to compute the next SCC
     177      933594 :   while (!VisitStack.empty()) {
     178      401560 :     DFSVisitChildren();
     179             : 
     180             :     // Pop the leaf on top of the VisitStack.
     181      803120 :     NodeRef visitingN = VisitStack.back().Node;
     182      803120 :     unsigned minVisitNum = VisitStack.back().MinVisited;
     183             :     assert(VisitStack.back().NextChild == GT::child_end(visitingN));
     184      401560 :     VisitStack.pop_back();
     185             : 
     186             :     // Propagate MinVisitNum to parent so we can detect the SCC starting node.
     187     1139435 :     if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)
     188        4964 :       VisitStack.back().MinVisited = minVisitNum;
     189             : 
     190             : #if 0 // Enable if needed when debugging.
     191             :     dbgs() << "TarjanSCC: Popped node " << visitingN <<
     192             :           " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
     193             :           nodeVisitNumbers[visitingN] << "\n";
     194             : #endif
     195             : 
     196      803120 :     if (minVisitNum != nodeVisitNumbers[visitingN])
     197        9069 :       continue;
     198             : 
     199             :     // A full SCC is on the SCCNodeStack!  It includes all nodes below
     200             :     // visitingN on the stack.  Copy those nodes to CurrentSCC,
     201             :     // reset their minVisit values, and return (this suspends
     202             :     // the DFS traversal till the next ++).
     203             :     do {
     204      803120 :       CurrentSCC.push_back(SCCNodeStack.back());
     205      401560 :       SCCNodeStack.pop_back();
     206     1204680 :       nodeVisitNumbers[CurrentSCC.back()] = ~0U;
     207      817476 :     } while (CurrentSCC.back() != visitingN);
     208      392491 :     return;
     209             :   }
     210             : }
     211             : 
     212             : template <class GraphT, class GT>
     213           0 : bool scc_iterator<GraphT, GT>::hasLoop() const {
     214             :     assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
     215           0 :     if (CurrentSCC.size() > 1)
     216             :       return true;
     217           0 :     NodeRef N = CurrentSCC.front();
     218           0 :     for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
     219             :          ++CI)
     220           0 :       if (*CI == N)
     221           0 :         return true;
     222           0 :     return false;
     223             :   }
     224             : 
     225             : /// \brief Construct the begin iterator for a deduced graph type T.
     226             : template <class T> scc_iterator<T> scc_begin(const T &G) {
     227       62450 :   return scc_iterator<T>::begin(G);
     228             : }
     229             : 
     230             : /// \brief Construct the end iterator for a deduced graph type T.
     231             : template <class T> scc_iterator<T> scc_end(const T &G) {
     232        4096 :   return scc_iterator<T>::end(G);
     233             : }
     234             : 
     235             : } // end namespace llvm
     236             : 
     237             : #endif // LLVM_ADT_SCCITERATOR_H

Generated by: LCOV version 1.13