SCCIterator.h Source File (original) (raw)

22#ifndef LLVM_ADT_SCCITERATOR_H

23#define LLVM_ADT_SCCITERATOR_H

29#include

30#include

31#include

32#include

33#include

34#include <unordered_map>

35#include <unordered_set>

36#include

38namespace llvm {

46template <class GraphT, class GT = GraphTraits>

48 scc_iterator<GraphT, GT>, std::forward_iterator_tag,

49 const std::vector, ptrdiff_t> {

50 using NodeRef = typename GT::NodeRef;

51 using ChildItTy = typename GT::ChildIteratorType;

52 using SccTy = std::vector;

53 using reference = typename scc_iterator::reference;

56 struct StackElement {

57 NodeRef Node;

58 ChildItTy NextChild;

59 unsigned MinVisited;

61 StackElement(NodeRef Node, const ChildItTy &Child, unsigned Min)

62 : Node(Node), NextChild(Child), MinVisited(Min) {}

66 NextChild == Other.NextChild &&

67 MinVisited == Other.MinVisited;

68 }

69 };

75 unsigned visitNum;

79 std::vector SCCNodeStack;

82 SccTy CurrentSCC;

86 std::vector VisitStack;

89 void DFSVisitOne(NodeRef N);

92 void DFSVisitChildren();

95 void GetNextSCC();

97 scc_iterator(NodeRef entryN) : visitNum(0) {

98 DFSVisitOne(entryN);

99 GetNextSCC();

100 }

101

102

103 scc_iterator() = default;

104

105public:

106 static scc_iterator begin(const GraphT &G) {

107 return scc_iterator(GT::getEntryNode(G));

108 }

109 static scc_iterator end(const GraphT &) { return scc_iterator(); }

110

111

112

114 assert(!CurrentSCC.empty() || VisitStack.empty());

115 return CurrentSCC.empty();

116 }

117

119 return VisitStack == x.VisitStack && CurrentSCC == x.CurrentSCC;

120 }

121

123 GetNextSCC();

124 return *this;

125 }

126

128 assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");

129 return CurrentSCC;

130 }

131

132

133

134

135

137

138

139

141 assert(nodeVisitNumbers.count(Old) && "Old not in scc_iterator?");

142

143

144 auto tempVal = nodeVisitNumbers[Old];

145 nodeVisitNumbers[New] = tempVal;

146 nodeVisitNumbers.erase(Old);

147 }

148};

149

150template <class GraphT, class GT>

151void scc_iterator<GraphT, GT>::DFSVisitOne(NodeRef N) {

152 ++visitNum;

153 nodeVisitNumbers[N] = visitNum;

154 SCCNodeStack.push_back(N);

155 VisitStack.push_back(StackElement(N, GT::child_begin(N), visitNum));

156#if 0

157 dbgs() << "TarjanSCC: Node " << N <<

158 " : visitNum = " << visitNum << "\n";

159#endif

160}

161

162template <class GraphT, class GT>

163void scc_iterator<GraphT, GT>::DFSVisitChildren() {

164 assert(!VisitStack.empty());

165 while (VisitStack.back().NextChild != GT::child_end(VisitStack.back().Node)) {

166

167 NodeRef childN = *VisitStack.back().NextChild++;

169 nodeVisitNumbers.find(childN);

170 if (Visited == nodeVisitNumbers.end()) {

171

172 DFSVisitOne(childN);

173 continue;

174 }

175

176 unsigned childNum = Visited->second;

177 if (VisitStack.back().MinVisited > childNum)

178 VisitStack.back().MinVisited = childNum;

179 }

180}

181

182template <class GraphT, class GT> void scc_iterator<GraphT, GT>::GetNextSCC() {

183 CurrentSCC.clear();

184 while (!VisitStack.empty()) {

185 DFSVisitChildren();

186

187

188 NodeRef visitingN = VisitStack.back().Node;

189 unsigned minVisitNum = VisitStack.back().MinVisited;

190 assert(VisitStack.back().NextChild == GT::child_end(visitingN));

191 VisitStack.pop_back();

192

193

194 if (!VisitStack.empty() && VisitStack.back().MinVisited > minVisitNum)

195 VisitStack.back().MinVisited = minVisitNum;

196

197#if 0

198 dbgs() << "TarjanSCC: Popped node " << visitingN <<

199 " : minVisitNum = " << minVisitNum << "; Node visit num = " <<

200 nodeVisitNumbers[visitingN] << "\n";

201#endif

202

203 if (minVisitNum != nodeVisitNumbers[visitingN])

204 continue;

205

206

207

208

209

210 do {

211 CurrentSCC.push_back(SCCNodeStack.back());

212 SCCNodeStack.pop_back();

213 nodeVisitNumbers[CurrentSCC.back()] = ~0U;

214 } while (CurrentSCC.back() != visitingN);

215 return;

216 }

217}

218

219template <class GraphT, class GT>

221 assert(!CurrentSCC.empty() && "Dereferencing END SCC iterator!");

222 if (CurrentSCC.size() > 1)

223 return true;

224 NodeRef N = CurrentSCC.front();

225 for (ChildItTy CI = GT::child_begin(N), CE = GT::child_end(N); CI != CE;

226 ++CI)

227 if (*CI == N)

228 return true;

229 return false;

230 }

231

232

236

237

241

242

243

244

245

246

247

248

249

250

251

252template <class GraphT, class GT = GraphTraits>

254 using NodeType = typename GT::NodeType;

255 using EdgeType = typename GT::EdgeType;

256 using NodesType = std::vector<NodeType *>;

257

258

259 struct NodeInfo {

260 NodeInfo *Group = this;

262 bool Visited = false;

264 };

265

266

267

268 NodeInfo *find(NodeInfo *Node) {

270 Node->Group = find(Node->Group);

271 return Node->Group;

272 }

273

274

275

276 bool unionGroups(const EdgeType *Edge) {

277 NodeInfo *G1 = find(&NodeInfoMap[Edge->Source]);

278 NodeInfo *G2 = find(&NodeInfoMap[Edge->Target]);

279

280

281 if (G1 == G2)

282 return false;

283

284

285 if (G1->Rank < G2->Rank)

286 G1->Group = G2;

287 else {

288 G2->Group = G1;

289

290 if (G1->Rank == G2->Rank)

291 G1->Rank++;

292 }

293 return true;

294 }

295

296 std::unordered_map<NodeType *, NodeInfo> NodeInfoMap;

297 NodesType Nodes;

298

299public:

301

303};

304

305template <class GraphT, class GT>

307 const NodesType &InputNodes) {

308 if (InputNodes.size() <= 1) {

309 Nodes = InputNodes;

310 return;

311 }

312

313

314 NodeInfoMap.clear();

315 for (auto *Node : InputNodes) {

316

317

318

319 NodeInfoMap.try_emplace(Node);

320 }

321

322

323 struct EdgeComparer {

324 bool operator()(const EdgeType *L, const EdgeType *R) const {

325 return L->Weight > R->Weight;

326 }

327 };

328

329 std::multiset<const EdgeType *, EdgeComparer> SortedEdges;

330 for (auto *Node : InputNodes) {

331 for (auto &Edge : Node->Edges) {

332 if (NodeInfoMap.count(Edge.Target))

333 SortedEdges.insert(&Edge);

334 }

335 }

336

337

338

339 std::unordered_set<const EdgeType *> MSTEdges;

340 for (auto *Edge : SortedEdges) {

341 if (unionGroups(Edge))

342 MSTEdges.insert(Edge);

343 }

344

345

346

347

348

349

350 std::queue<NodeType *> Queue;

351 for (const auto *Edge : MSTEdges)

352 NodeInfoMap[Edge->Target].IncomingMSTEdges.insert(Edge);

353

354

355

356 for (auto *Edge : SortedEdges) {

357 auto &Info = NodeInfoMap[Edge->Source];

358 if ( Info .Visited && Info.IncomingMSTEdges.empty()) {

359 Queue.push(Edge->Source);

360 Info.Visited = true;

361 }

362 }

363

364 while (!Queue.empty()) {

365 auto *Node = Queue.front();

366 Queue.pop();

367 Nodes.push_back(Node);

368 for (auto &Edge : Node->Edges) {

369 NodeInfo &Info = NodeInfoMap[Edge.Target];

370 Info.IncomingMSTEdges.erase(&Edge);

371 if (MSTEdges.count(&Edge) && Info.IncomingMSTEdges.empty()) {

372 Queue.push(Edge.Target);

373 }

374 }

375 }

376

377 assert(InputNodes.size() == Nodes.size() && "missing nodes in MST");

378 std::reverse(Nodes.begin(), Nodes.end());

379}

380}

381

382#endif

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

Analysis containing CSE Info

This file defines the DenseMap class.

This file defines the DenseSet and SmallDenseSet classes.

This file defines the little GraphTraits template class that should be specialized by classes that...

DenseMapIterator< KeyT, ValueT, KeyInfoT, BucketT > iterator

Implements a dense probed hash-table based set.

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.

Definition SCCIterator.h:49

scc_iterator & operator++()

Definition SCCIterator.h:122

static scc_iterator begin(const GraphT &G)

Definition SCCIterator.h:106

bool isAtEnd() const

Direct loop termination test which is more efficient than comparison with end().

Definition SCCIterator.h:113

static scc_iterator end(const GraphT &)

Definition SCCIterator.h:109

bool operator==(const scc_iterator &x) const

Definition SCCIterator.h:118

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

bool hasCycle() const

Test if the current SCC has a cycle.

Definition SCCIterator.h:220

reference operator*() const

Definition SCCIterator.h:127

scc_member_iterator(const NodesType &InputNodes)

Definition SCCIterator.h:306

NodesType & operator*()

Definition SCCIterator.h:302

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.

Definition SCCIterator.h:233

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

Definition SCCIterator.h:238