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