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