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