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>> |

42 | class scc_iterator : public iterator_facade_base< |

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 | |

117 | scc_iterator &operator++() { |

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> |

215 | bool scc_iterator<GraphT, GT>::hasCycle() const { |

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 |

240 |