include/llvm/ADT/SCCIterator.h

   1 //===-- Support/TarjanSCCIterator.h -Generic Tarjan SCC iterator -*- C++ -*--=//
   2 //
   3 // This builds on the Support/GraphTraits.h file to find the strongly
   4 // connected components (SCCs) of a graph in O(N+E) time using
   5 // Tarjan's DFS algorithm.
   6 //
   7 // The SCC iterator has the important property that if a node in SCC S1
   8 // has an edge to a node in SCC S2, then it visits S1 *after* S2.
   9 //
  10 // To visit S1 *before* S2, use the TarjanSCCIterator on the Inverse graph.
  11 // (NOTE: This requires some simple wrappers and is not supported yet.)
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_SUPPORT_TARJANSCC_ITERATOR_H
  15 #define LLVM_SUPPORT_TARJANSCC_ITERATOR_H
  16
  17 #include "Support/GraphTraits.h"
  18 #include <Support/Statistic.h>
  19 #include <Support/iterator>
  20 #include <vector>
  21 #include <stack>
  22 #include <map>
  23
  24
  25 //--------------------------------------------------------------------------
  26 // class SCC : A simple representation of an SCC in a generic Graph.
  27 //--------------------------------------------------------------------------
  28
  29 template<class GraphT, class GT = GraphTraits<GraphT> >
  30 struct SCC: public std::vector<typename GT::NodeType*> {
  31
  32   typedef typename GT::NodeType NodeType;
  33   typedef typename GT::ChildIteratorType ChildItTy;
  34
  35   typedef std::vector<typename GT::NodeType*> super;
  36   typedef typename super::iterator               iterator;
  37   typedef typename super::const_iterator         const_iterator;
  38   typedef typename super::reverse_iterator       reverse_iterator;
  39   typedef typename super::const_reverse_iterator const_reverse_iterator;
  40
  41   // HasLoop() -- Test if this SCC has a loop.  If it has more than one
  42   // node, this is trivially true.  If not, it may still contain a loop
  43   // if the node has an edge back to itself.
  44   bool HasLoop() const {
  45     if (size() > 1) return true;
  46     NodeType* N = front();
  47     for (ChildItTy CI=GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI)
  48       if (*CI == N)
  49         return true;
  50     return false;
  51   }
  52 };
  53
  54 //--------------------------------------------------------------------------
  55 // class TarjanSCC_iterator: Enumerate the SCCs of a directed graph, in
  56 // reverse topological order of the SCC DAG.
  57 //--------------------------------------------------------------------------
  58
  59 const unsigned long MAXLONG = (1 << (8 * sizeof(unsigned long) - 1));
  60
  61 namespace {
  62   Statistic<> NumSCCs("NumSCCs", "Number of Strongly Connected Components");
  63   Statistic<> MaxSCCSize("MaxSCCSize", "Size of largest Strongly Connected Component");
  64 }
  65
  66 template<class GraphT, class GT = GraphTraits<GraphT> >
  67 class TarjanSCC_iterator : public forward_iterator<SCC<GraphT, GT>, ptrdiff_t>
  68 {
  69   typedef SCC<GraphT, GT> SccTy;
  70   typedef forward_iterator<SccTy, ptrdiff_t> super;
  71   typedef typename super::reference reference;
  72   typedef typename super::pointer pointer;
  73   typedef typename GT::NodeType          NodeType;
  74   typedef typename GT::ChildIteratorType ChildItTy;
  75
  76   // The visit counters used to detect when a complete SCC is on the stack.
  77   // visitNum is the global counter.
  78   // nodeVisitNumbers are per-node visit numbers, also used as DFS flags.
  79   unsigned long visitNum;
  80   std::map<NodeType *, unsigned long> nodeVisitNumbers;
  81
  82   // SCCNodeStack - Stack holding nodes of the SCC.
  83   std::stack<NodeType *> SCCNodeStack;
  84
  85   // CurrentSCC - The current SCC, retrieved using operator*().
  86   SccTy CurrentSCC;
  87
  88   // VisitStack - Used to maintain the ordering.  Top = current block
  89   // First element is basic block pointer, second is the 'next child' to visit
  90   std::stack<std::pair<NodeType *, ChildItTy> > VisitStack;
  91
  92   // MinVistNumStack - Stack holding the "min" values for each node in the DFS.
  93   // This is used to track the minimum uplink values for all children of
  94   // the corresponding node on the VisitStack.
  95   std::stack<unsigned long> MinVisitNumStack;
  96
  97   // A single "visit" within the non-recursive DFS traversal.
  98   void DFSVisitOne(NodeType* N) {
  99     ++visitNum;                         // Global counter for the visit order
 100     nodeVisitNumbers[N] = visitNum;
 101     SCCNodeStack.push(N);
 102     MinVisitNumStack.push(visitNum);
 103     VisitStack.push(make_pair(N, GT::child_begin(N)));
 104     DEBUG(std::cerr << "TarjanSCC: Node " << N <<
 105           " : visitNum = " << visitNum << "\n");
 106   }
 107
 108   // The stack-based DFS traversal; defined below.
 109   void DFSVisitChildren() {
 110     assert(!VisitStack.empty());
 111     while (VisitStack.top().second != GT::child_end(VisitStack.top().first))
 112       { // TOS has at least one more child so continue DFS
 113         NodeType *childN = *VisitStack.top().second++;
 114         if (nodeVisitNumbers.find(childN) == nodeVisitNumbers.end())
 115           { // this node has never been seen
 116             DFSVisitOne(childN);
 117           }
 118         else
 119           {
 120             unsigned long childNum = nodeVisitNumbers[childN];
 121             if (MinVisitNumStack.top() > childNum)
 122               MinVisitNumStack.top() = childNum;
 123           }
 124       }
 125   }
 126
 127   // Compute the next SCC using the DFS traversal.
 128   void GetNextSCC() {
 129     assert(VisitStack.size() == MinVisitNumStack.size());
 130     CurrentSCC.clear();                 // Prepare to compute the next SCC
 131     while (! VisitStack.empty())
 132       {
 133         DFSVisitChildren();
 134
 135         assert(VisitStack.top().second==GT::child_end(VisitStack.top().first));
 136         NodeType* visitingN = VisitStack.top().first;
 137         unsigned long minVisitNum = MinVisitNumStack.top();
 138         VisitStack.pop();
 139         MinVisitNumStack.pop();
 140         if (! MinVisitNumStack.empty() && MinVisitNumStack.top() > minVisitNum)
 141           MinVisitNumStack.top() = minVisitNum;
 142
 143         DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN <<
 144               " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
 145               nodeVisitNumbers[visitingN] << "\n");
 146
 147         if (minVisitNum == nodeVisitNumbers[visitingN])
 148           { // A full SCC is on the SCCNodeStack!  It includes all nodes below
 149             // visitingN on the stack.  Copy those nodes to CurrentSCC,
 150             // reset their minVisit values, and return (this suspends
 151             // the DFS traversal till the next ++).
 152             do {
 153               CurrentSCC.push_back(SCCNodeStack.top());
 154               SCCNodeStack.pop();
 155               nodeVisitNumbers[CurrentSCC.back()] = MAXLONG;
 156             } while (CurrentSCC.back() != visitingN);
 157
 158             ++NumSCCs;
 159             if (CurrentSCC.size() > MaxSCCSize) MaxSCCSize = CurrentSCC.size();
 160
 161             return;
 162           }
 163       }
 164   }
 165
 166   inline TarjanSCC_iterator(NodeType *entryN) : visitNum(0) {
 167     DFSVisitOne(entryN);
 168     GetNextSCC();
 169   }
 170   inline TarjanSCC_iterator() { /* End is when DFS stack is empty */ }
 171
 172 public:
 173   typedef TarjanSCC_iterator<GraphT, GT> _Self;
 174
 175   // Provide static "constructors"...
 176   static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); }
 177   static inline _Self end  (GraphT& G) { return _Self(); }
 178
 179   // Direct loop termination test (I.fini() is more efficient than I == end())
 180   inline bool fini() const {
 181     return VisitStack.empty();
 182   }
 183
 184   inline bool operator==(const _Self& x) const {
 185     return VisitStack == x.VisitStack;
 186   }
 187   inline bool operator!=(const _Self& x) const { return !operator==(x); }
 188
 189   // Iterator traversal: forward iteration only
 190   inline _Self& operator++() {          // Preincrement
 191     GetNextSCC();
 192     return *this;
 193   }
 194   inline _Self operator++(int) {        // Postincrement
 195     _Self tmp = *this; ++*this; return tmp;
 196   }
 197
 198   // Retrieve a pointer to the current SCC.  Returns NULL when done.
 199   inline const SccTy* operator*() const {
 200     assert(!CurrentSCC.empty() || fini());
 201     return CurrentSCC.empty()? NULL : &CurrentSCC;
 202   }
 203   inline SccTy* operator*() {
 204     assert(!CurrentSCC.empty() || fini());
 205     return CurrentSCC.empty()? NULL : &CurrentSCC;
 206   }
 207 };
 208
 209
 210 // Global constructor for the Tarjan SCC iterator.  Use *I == NULL or I.fini()
 211 // to test termination efficiently, instead of I == the "end" iterator.
 212 template <class T>
 213 TarjanSCC_iterator<T> tarj_begin(T G)
 214 {
 215   return TarjanSCC_iterator<T>::begin(G);
 216 }
 217
 218 template <class T>
 219 TarjanSCC_iterator<T> tarj_end(T G)
 220 {
 221   return TarjanSCC_iterator<T>::end(G);
 222 }
 223
 224 //===----------------------------------------------------------------------===//
 225
 226 #endif