LLVM API Documentation
00001 //===-- Support/SCCIterator.h - Strongly Connected Comp. Iter. --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected 00011 // components (SCCs) of a graph in O(N+E) time using Tarjan's DFS algorithm. 00012 // 00013 // The SCC iterator has the important property that if a node in SCC S1 has an 00014 // edge to a node in SCC S2, then it visits S1 *after* S2. 00015 // 00016 // To visit S1 *before* S2, use the scc_iterator on the Inverse graph. 00017 // (NOTE: This requires some simple wrappers and is not supported yet.) 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #ifndef LLVM_ADT_SCCITERATOR_H 00022 #define LLVM_ADT_SCCITERATOR_H 00023 00024 #include "llvm/ADT/GraphTraits.h" 00025 #include "llvm/ADT/iterator" 00026 #include <vector> 00027 #include <map> 00028 00029 namespace llvm { 00030 00031 //===----------------------------------------------------------------------===// 00032 /// 00033 /// scc_iterator - Enumerate the SCCs of a directed graph, in 00034 /// reverse topological order of the SCC DAG. 00035 /// 00036 template<class GraphT, class GT = GraphTraits<GraphT> > 00037 class scc_iterator 00038 : public forward_iterator<std::vector<typename GT::NodeType>, ptrdiff_t> { 00039 typedef typename GT::NodeType NodeType; 00040 typedef typename GT::ChildIteratorType ChildItTy; 00041 typedef std::vector<NodeType*> SccTy; 00042 typedef forward_iterator<SccTy, ptrdiff_t> super; 00043 typedef typename super::reference reference; 00044 typedef typename super::pointer pointer; 00045 00046 // The visit counters used to detect when a complete SCC is on the stack. 00047 // visitNum is the global counter. 00048 // nodeVisitNumbers are per-node visit numbers, also used as DFS flags. 00049 unsigned visitNum; 00050 std::map<NodeType *, unsigned> nodeVisitNumbers; 00051 00052 // SCCNodeStack - Stack holding nodes of the SCC. 00053 std::vector<NodeType *> SCCNodeStack; 00054 00055 // CurrentSCC - The current SCC, retrieved using operator*(). 00056 SccTy CurrentSCC; 00057 00058 // VisitStack - Used to maintain the ordering. Top = current block 00059 // First element is basic block pointer, second is the 'next child' to visit 00060 std::vector<std::pair<NodeType *, ChildItTy> > VisitStack; 00061 00062 // MinVistNumStack - Stack holding the "min" values for each node in the DFS. 00063 // This is used to track the minimum uplink values for all children of 00064 // the corresponding node on the VisitStack. 00065 std::vector<unsigned> MinVisitNumStack; 00066 00067 // A single "visit" within the non-recursive DFS traversal. 00068 void DFSVisitOne(NodeType* N) { 00069 ++visitNum; // Global counter for the visit order 00070 nodeVisitNumbers[N] = visitNum; 00071 SCCNodeStack.push_back(N); 00072 MinVisitNumStack.push_back(visitNum); 00073 VisitStack.push_back(std::make_pair(N, GT::child_begin(N))); 00074 //DEBUG(std::cerr << "TarjanSCC: Node " << N << 00075 // " : visitNum = " << visitNum << "\n"); 00076 } 00077 00078 // The stack-based DFS traversal; defined below. 00079 void DFSVisitChildren() { 00080 assert(!VisitStack.empty()); 00081 while (VisitStack.back().second != GT::child_end(VisitStack.back().first)) { 00082 // TOS has at least one more child so continue DFS 00083 NodeType *childN = *VisitStack.back().second++; 00084 if (!nodeVisitNumbers.count(childN)) { 00085 // this node has never been seen 00086 DFSVisitOne(childN); 00087 } else { 00088 unsigned childNum = nodeVisitNumbers[childN]; 00089 if (MinVisitNumStack.back() > childNum) 00090 MinVisitNumStack.back() = childNum; 00091 } 00092 } 00093 } 00094 00095 // Compute the next SCC using the DFS traversal. 00096 void GetNextSCC() { 00097 assert(VisitStack.size() == MinVisitNumStack.size()); 00098 CurrentSCC.clear(); // Prepare to compute the next SCC 00099 while (!VisitStack.empty()) { 00100 DFSVisitChildren(); 00101 assert(VisitStack.back().second ==GT::child_end(VisitStack.back().first)); 00102 NodeType* visitingN = VisitStack.back().first; 00103 unsigned minVisitNum = MinVisitNumStack.back(); 00104 VisitStack.pop_back(); 00105 MinVisitNumStack.pop_back(); 00106 if (!MinVisitNumStack.empty() && MinVisitNumStack.back() > minVisitNum) 00107 MinVisitNumStack.back() = minVisitNum; 00108 00109 //DEBUG(std::cerr << "TarjanSCC: Popped node " << visitingN << 00110 // " : minVisitNum = " << minVisitNum << "; Node visit num = " << 00111 // nodeVisitNumbers[visitingN] << "\n"); 00112 00113 if (minVisitNum == nodeVisitNumbers[visitingN]) { 00114 // A full SCC is on the SCCNodeStack! It includes all nodes below 00115 // visitingN on the stack. Copy those nodes to CurrentSCC, 00116 // reset their minVisit values, and return (this suspends 00117 // the DFS traversal till the next ++). 00118 do { 00119 CurrentSCC.push_back(SCCNodeStack.back()); 00120 SCCNodeStack.pop_back(); 00121 nodeVisitNumbers[CurrentSCC.back()] = ~0UL; 00122 } while (CurrentSCC.back() != visitingN); 00123 return; 00124 } 00125 } 00126 } 00127 00128 inline scc_iterator(NodeType *entryN) : visitNum(0) { 00129 DFSVisitOne(entryN); 00130 GetNextSCC(); 00131 } 00132 inline scc_iterator() { /* End is when DFS stack is empty */ } 00133 00134 public: 00135 typedef scc_iterator<GraphT, GT> _Self; 00136 00137 // Provide static "constructors"... 00138 static inline _Self begin(GraphT& G) { return _Self(GT::getEntryNode(G)); } 00139 static inline _Self end (GraphT& G) { return _Self(); } 00140 00141 // Direct loop termination test (I.fini() is more efficient than I == end()) 00142 inline bool fini() const { 00143 assert(!CurrentSCC.empty() || VisitStack.empty()); 00144 return CurrentSCC.empty(); 00145 } 00146 00147 inline bool operator==(const _Self& x) const { 00148 return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC; 00149 } 00150 inline bool operator!=(const _Self& x) const { return !operator==(x); } 00151 00152 // Iterator traversal: forward iteration only 00153 inline _Self& operator++() { // Preincrement 00154 GetNextSCC(); 00155 return *this; 00156 } 00157 inline _Self operator++(int) { // Postincrement 00158 _Self tmp = *this; ++*this; return tmp; 00159 } 00160 00161 // Retrieve a reference to the current SCC 00162 inline const SccTy &operator*() const { 00163 assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); 00164 return CurrentSCC; 00165 } 00166 inline SccTy &operator*() { 00167 assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); 00168 return CurrentSCC; 00169 } 00170 00171 // hasLoop() -- Test if the current SCC has a loop. If it has more than one 00172 // node, this is trivially true. If not, it may still contain a loop if the 00173 // node has an edge back to itself. 00174 bool hasLoop() const { 00175 assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!"); 00176 if (CurrentSCC.size() > 1) return true; 00177 NodeType *N = CurrentSCC.front(); 00178 for (ChildItTy CI = GT::child_begin(N), CE=GT::child_end(N); CI != CE; ++CI) 00179 if (*CI == N) 00180 return true; 00181 return false; 00182 } 00183 }; 00184 00185 00186 // Global constructor for the SCC iterator. 00187 template <class T> 00188 scc_iterator<T> scc_begin(T G) { 00189 return scc_iterator<T>::begin(G); 00190 } 00191 00192 template <class T> 00193 scc_iterator<T> scc_end(T G) { 00194 return scc_iterator<T>::end(G); 00195 } 00196 00197 } // End llvm namespace 00198 00199 #endif