22#ifndef LLVM_ADT_SCCITERATOR_H
23#define LLVM_ADT_SCCITERATOR_H
33#include <unordered_map>
34#include <unordered_set>
45template <
class GraphT,
class GT = GraphTraits<GraphT>>
47 scc_iterator<GraphT, GT>, std::forward_iterator_tag,
48 const std::vector<typename GT::NodeRef>, ptrdiff_t> {
49 using NodeRef =
typename GT::NodeRef;
50 using ChildItTy =
typename GT::ChildIteratorType;
51 using SccTy = std::vector<NodeRef>;
52 using reference =
typename scc_iterator::reference;
60 StackElement(NodeRef
Node,
const ChildItTy &Child,
unsigned Min)
61 :
Node(
Node), NextChild(Child), MinVisited(Min) {}
65 NextChild ==
Other.NextChild &&
66 MinVisited ==
Other.MinVisited;
78 std::vector<NodeRef> SCCNodeStack;
85 std::vector<StackElement> VisitStack;
88 void DFSVisitOne(NodeRef
N);
91 void DFSVisitChildren();
113 assert(!CurrentSCC.empty() || VisitStack.empty());
114 return CurrentSCC.empty();
118 return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;
127 assert(!CurrentSCC.empty() &&
"Dereferencing END SCC iterator!");
140 assert(nodeVisitNumbers.
count(Old) &&
"Old not in scc_iterator?");
143 auto tempVal = nodeVisitNumbers[Old];
144 nodeVisitNumbers[New] = tempVal;
145 nodeVisitNumbers.
erase(Old);
149template <
class GraphT,
class GT>
150void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef
N) {
152 nodeVisitNumbers[
N] = visitNum;
153 SCCNodeStack.push_back(
N);
154 VisitStack.push_back(StackElement(
N, GT::child_begin(
N), visitNum));
156 dbgs() <<
"TarjanSCC: Node " <<
N <<
157 " : visitNum = " << visitNum <<
"\n";
161template <
class GraphT,
class GT>
162void scc_iterator<GraphT, GT>::DFSVisitChildren() {
163 assert(!VisitStack.empty());
164 while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
166 NodeRef childN = *VisitStack.back().NextChild++;
167 typename DenseMap<NodeRef, unsigned>::iterator Visited =
168 nodeVisitNumbers.find(childN);
169 if (Visited == nodeVisitNumbers.end()) {
175 unsigned childNum = Visited->second;
176 if (VisitStack.back().MinVisited > childNum)
177 VisitStack.back().MinVisited = childNum;
181template <
class GraphT,
class GT>
void scc_iterator<GraphT, GT>::GetNextSCC() {
183 while (!VisitStack.empty()) {
187 NodeRef visitingN = VisitStack.back().Node;
188 unsigned minVisitNum = VisitStack.back().MinVisited;
189 assert(VisitStack.back().NextChild == GT::child_end(visitingN));
190 VisitStack.pop_back();
193 if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)
194 VisitStack.back().MinVisited = minVisitNum;
197 dbgs() <<
"TarjanSCC: Popped node " << visitingN <<
198 " : minVisitNum = " << minVisitNum <<
"; Node visit num = " <<
199 nodeVisitNumbers[visitingN] <<
"\n";
202 if (minVisitNum != nodeVisitNumbers[visitingN])
210 CurrentSCC.push_back(SCCNodeStack.back());
211 SCCNodeStack.pop_back();
212 nodeVisitNumbers[CurrentSCC.back()] = ~0
U;
213 }
while (CurrentSCC.back() != visitingN);
218template <
class GraphT,
class GT>
220 assert(!CurrentSCC.empty() &&
"Dereferencing END SCC iterator!");
221 if (CurrentSCC.size() > 1)
223 NodeRef
N = CurrentSCC.front();
224 for (ChildItTy CI = GT::child_begin(
N), CE = GT::child_end(
N); CI != CE;
251template <
class GraphT,
class GT = GraphTraits<GraphT>>
253 using NodeType =
typename GT::NodeType;
254 using EdgeType =
typename GT::EdgeType;
255 using NodesType = std::vector<NodeType *>;
259 NodeInfo *Group =
this;
266 NodeInfo *find(NodeInfo *
Node) {
274 bool unionGroups(
const EdgeType *Edge) {
275 NodeInfo *G1 = find(&NodeInfoMap[Edge->Source]);
276 NodeInfo *G2 = find(&NodeInfoMap[Edge->Target]);
283 if (G1->Rank < G1->Rank)
288 if (G1->Rank == G2->Rank)
294 std::unordered_map<NodeType *, NodeInfo> NodeInfoMap;
303template <
class GraphT,
class GT>
305 const NodesType &InputNodes) {
306 if (InputNodes.size() <= 1) {
313 for (
auto *
Node : InputNodes) {
317 (void)NodeInfoMap[
Node].Group;
321 struct EdgeComparer {
322 bool operator()(
const EdgeType *L,
const EdgeType *R)
const {
323 return L->Weight > R->Weight;
327 std::multiset<const EdgeType *, EdgeComparer> SortedEdges;
328 for (
auto *
Node : InputNodes) {
329 for (
auto &Edge :
Node->Edges) {
330 if (NodeInfoMap.count(Edge.Target))
331 SortedEdges.insert(&Edge);
337 std::unordered_set<const EdgeType *> MSTEdges;
338 for (
auto *Edge : SortedEdges) {
339 if (unionGroups(Edge))
340 MSTEdges.insert(Edge);
347 for (
const auto *Edge : MSTEdges)
348 NodeInfoMap[Edge->Target].Visited =
false;
350 std::queue<NodeType *> Queue;
353 for (
auto *Edge : SortedEdges) {
354 if (NodeInfoMap[Edge->Source].Visited) {
355 Queue.push(Edge->Source);
356 NodeInfoMap[Edge->Source].Visited =
false;
360 while (!Queue.empty()) {
361 auto *
Node = Queue.front();
363 Nodes.push_back(
Node);
364 for (
auto &Edge :
Node->Edges) {
365 if (MSTEdges.count(&Edge) && !NodeInfoMap[Edge.Target].Visited) {
366 NodeInfoMap[Edge.Target].Visited =
true;
367 Queue.push(Edge.Target);
372 assert(InputNodes.size() == Nodes.size() &&
"missing nodes in MST");
373 std::reverse(Nodes.begin(), Nodes.end());
This file defines the DenseMap class.
This file defines the little GraphTraits<X> template class that should be specialized by classes that...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
scc_iterator & operator++()
static scc_iterator begin(const GraphT &G)
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
static scc_iterator end(const GraphT &)
bool operator==(const scc_iterator &x) const
void ReplaceNode(NodeRef Old, NodeRef New)
This informs the scc_iterator that the specified Old node has been deleted, and New is to be used in ...
bool hasCycle() const
Test if the current SCC has a cycle.
reference operator*() const
Sort the nodes of a directed SCC in the decreasing order of the edge weights.
scc_member_iterator(const NodesType &InputNodes)
std::pair< NodeId, LaneBitmask > NodeRef
This is an optimization pass for GlobalISel generic memory operations.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.