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