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