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