LLVM  14.0.0git
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 cycle.
128  ///
129  /// If the SCC has more than one node, this is trivially true. If not, it may
130  /// still contain a cycle if the node has an edge back to itself.
131  bool hasCycle() 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  // Do the assignment in two steps, in case 'New' is not yet in the map, and
138  // inserting it causes the map to grow.
139  auto tempVal = nodeVisitNumbers[Old];
140  nodeVisitNumbers[New] = tempVal;
141  nodeVisitNumbers.erase(Old);
142  }
143 };
144 
145 template <class GraphT, class GT>
146 void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {
147  ++visitNum;
148  nodeVisitNumbers[N] = visitNum;
149  SCCNodeStack.push_back(N);
150  VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));
151 #if 0 // Enable if needed when debugging.
152  dbgs() << "TarjanSCC: Node " << N <<
153  " : visitNum = " << visitNum << "\n";
154 #endif
155 }
156 
157 template <class GraphT, class GT>
158 void scc_iterator<GraphT, GT>::DFSVisitChildren() {
159  assert(!VisitStack.empty());
160  while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {
161  // TOS has at least one more child so continue DFS
162  NodeRef childN = *VisitStack.back().NextChild++;
163  typename DenseMap<NodeRef, unsigned>::iterator Visited =
164  nodeVisitNumbers.find(childN);
165  if (Visited == nodeVisitNumbers.end()) {
166  // this node has never been seen.
167  DFSVisitOne(childN);
168  continue;
169  }
170 
171  unsigned childNum = Visited->second;
172  if (VisitStack.back().MinVisited > childNum)
173  VisitStack.back().MinVisited = childNum;
174  }
175 }
176 
177 template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {
178  CurrentSCC.clear(); // Prepare to compute the next SCC
179  while (!VisitStack.empty()) {
180  DFSVisitChildren();
181 
182  // Pop the leaf on top of the VisitStack.
183  NodeRef visitingN = VisitStack.back().Node;
184  unsigned minVisitNum = VisitStack.back().MinVisited;
185  assert(VisitStack.back().NextChild == GT::child_end(visitingN));
186  VisitStack.pop_back();
187 
188  // Propagate MinVisitNum to parent so we can detect the SCC starting node.
189  if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)
190  VisitStack.back().MinVisited = minVisitNum;
191 
192 #if 0 // Enable if needed when debugging.
193  dbgs() << "TarjanSCC: Popped node " << visitingN <<
194  " : minVisitNum = " << minVisitNum << "; Node visit num = " <<
195  nodeVisitNumbers[visitingN] << "\n";
196 #endif
197 
198  if (minVisitNum != nodeVisitNumbers[visitingN])
199  continue;
200 
201  // A full SCC is on the SCCNodeStack! It includes all nodes below
202  // visitingN on the stack. Copy those nodes to CurrentSCC,
203  // reset their minVisit values, and return (this suspends
204  // the DFS traversal till the next ++).
205  do {
206  CurrentSCC.push_back(SCCNodeStack.back());
207  SCCNodeStack.pop_back();
208  nodeVisitNumbers[CurrentSCC.back()] = ~0U;
209  } while (CurrentSCC.back() != visitingN);
210  return;
211  }
212 }
213 
214 template <class GraphT, class GT>
216  assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");
217  if (CurrentSCC.size() > 1)
218  return true;
219  NodeRef N = CurrentSCC.front();
220  for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;
221  ++CI)
222  if (*CI == N)
223  return true;
224  return false;
225  }
226 
227 /// Construct the begin iterator for a deduced graph type T.
228 template <class T> scc_iterator<T> scc_begin(const T &G) {
229  return scc_iterator<T>::begin(G);
230 }
231 
232 /// Construct the end iterator for a deduced graph type T.
233 template <class T> scc_iterator<T> scc_end(const T &G) {
234  return scc_iterator<T>::end(G);
235 }
236 
237 } // end namespace llvm
238 
239 #endif // LLVM_ADT_SCCITERATOR_H
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::scc_iterator::operator==
bool operator==(const scc_iterator &x) const
Definition: SCCIterator.h:113
llvm::DenseMapBase::erase
bool erase(const KeyT &Val)
Definition: DenseMap.h:302
DenseMap.h
llvm::DenseMapBase::count
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:145
llvm::scc_iterator::ReplaceNode
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
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
GraphTraits.h
llvm::rdf::detail::NodeRef
std::pair< NodeId, LaneBitmask > NodeRef
Definition: RDFLiveness.h:39
llvm::scc_begin
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Definition: SCCIterator.h:228
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::scc_iterator::operator*
reference operator*() const
Definition: SCCIterator.h:122
llvm::scc_iterator
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
Definition: SCCIterator.h:42
llvm::DenseMap< NodeRef, unsigned >
iterator.h
llvm::iterator_facade_base
CRTP base class which implements the entire standard iterator facade in terms of a minimal subset of ...
Definition: iterator.h:66
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::scc_iterator::end
static scc_iterator end(const GraphT &)
Definition: SCCIterator.h:104
llvm::scc_iterator::begin
static scc_iterator begin(const GraphT &G)
Definition: SCCIterator.h:101
Node
Definition: ItaniumDemangle.h:235
llvm::scc_iterator::hasCycle
bool hasCycle() const
Test if the current SCC has a cycle.
Definition: SCCIterator.h:215
x
TODO unsigned x
Definition: README.txt:10
llvm::scc_iterator::isAtEnd
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
Definition: SCCIterator.h:108
llvm::DenseMapBase< DenseMap< NodeRef, unsigned, DenseMapInfo< NodeRef >, llvm::detail::DenseMapPair< NodeRef, unsigned > >, NodeRef, unsigned, DenseMapInfo< NodeRef >, llvm::detail::DenseMapPair< NodeRef, unsigned > >::iterator
DenseMapIterator< NodeRef, unsigned, DenseMapInfo< NodeRef >, llvm::detail::DenseMapPair< NodeRef, unsigned > > iterator
Definition: DenseMap.h:70
llvm::scc_iterator::operator++
scc_iterator & operator++()
Definition: SCCIterator.h:117
N
#define N
llvm::scc_end
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Definition: SCCIterator.h:233
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1184