1//===- GenericCycleImpl.h -------------------------------------*- 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///
9/// \file
10/// This template implementation resides in a separate file so that it
11/// does not get injected into every .cpp file that includes the
12/// generic header.
13///
14/// DO NOT INCLUDE THIS FILE WHEN MERELY USING CYCLEINFO.
15///
16/// This file should only be included by files that implement a
17/// specialization of the relevant templates. Currently these are:
18/// - llvm/lib/IR/CycleInfo.cpp
19/// - llvm/lib/CodeGen/MachineCycleAnalysis.cpp
20///
21//===----------------------------------------------------------------------===//
22
23#ifndef LLVM_ADT_GENERICCYCLEIMPL_H
24#define LLVM_ADT_GENERICCYCLEIMPL_H
25
26#include "llvm/ADT/DenseSet.h"
27#include "llvm/ADT/DepthFirstIterator.h"
28#include "llvm/ADT/GenericCycleInfo.h"
29#include "llvm/ADT/StringExtras.h"
30
31#define DEBUG_TYPE "generic-cycle-impl"
32
33namespace llvm {
34
35template <typename ContextT>
36bool GenericCycle<ContextT>::contains(const GenericCycle *C) const {
37 if (!C)
38 return false;
39
40 if (Depth > C->Depth)
41 return false;
42 while (Depth < C->Depth)
43 C = C->ParentCycle;
44 return this == C;
45}
46
47template <typename ContextT>
48void GenericCycle<ContextT>::getExitBlocks(
49 SmallVectorImpl<BlockT *> &TmpStorage) const {
50 if (!ExitBlocksCache.empty()) {
51 TmpStorage = ExitBlocksCache;
52 return;
53 }
54
55 TmpStorage.clear();
56
57 size_t NumExitBlocks = 0;
58 for (BlockT *Block : blocks()) {
59 llvm::append_range(TmpStorage, successors(Block));
60
61 for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
62 ++Idx) {
63 BlockT *Succ = TmpStorage[Idx];
64 if (!contains(Succ)) {
65 auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
66 if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
67 TmpStorage[NumExitBlocks++] = Succ;
68 }
69 }
70
71 TmpStorage.resize(NumExitBlocks);
72 }
73 ExitBlocksCache.append(TmpStorage.begin(), TmpStorage.end());
74}
75
76template <typename ContextT>
77void GenericCycle<ContextT>::getExitingBlocks(
78 SmallVectorImpl<BlockT *> &TmpStorage) const {
79 TmpStorage.clear();
80
81 for (BlockT *Block : blocks()) {
82 for (BlockT *Succ : successors(Block)) {
83 if (!contains(Succ)) {
84 TmpStorage.push_back(Block);
85 break;
86 }
87 }
88 }
89}
90
91template <typename ContextT>
92auto GenericCycle<ContextT>::getCyclePreheader() const -> BlockT * {
93 BlockT *Predecessor = getCyclePredecessor();
94 if (!Predecessor)
95 return nullptr;
96
97 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
98
99 if (succ_size(Predecessor) != 1)
100 return nullptr;
101
102 // Make sure we are allowed to hoist instructions into the predecessor.
103 if (!Predecessor->isLegalToHoistInto())
104 return nullptr;
105
106 return Predecessor;
107}
108
109template <typename ContextT>
110auto GenericCycle<ContextT>::getCyclePredecessor() const -> BlockT * {
111 if (!isReducible())
112 return nullptr;
113
114 BlockT *Out = nullptr;
115
116 // Loop over the predecessors of the header node...
117 BlockT *Header = getHeader();
118 for (const auto Pred : predecessors(Header)) {
119 if (!contains(Pred)) {
120 if (Out && Out != Pred)
121 return nullptr;
122 Out = Pred;
123 }
124 }
125
126 return Out;
127}
128
129/// \brief Verify that this is actually a well-formed cycle in the CFG.
130template <typename ContextT> void GenericCycle<ContextT>::verifyCycle() const {
131#ifndef NDEBUG
132 assert(!Blocks.empty() && "Cycle cannot be empty.");
133 DenseSet<BlockT *> Blocks;
134 for (BlockT *BB : blocks()) {
135 assert(Blocks.insert(BB).second); // duplicates in block list?
136 }
137 assert(!Entries.empty() && "Cycle must have one or more entries.");
138
139 DenseSet<BlockT *> Entries;
140 for (BlockT *Entry : entries()) {
141 assert(Entries.insert(Entry).second); // duplicate entry?
142 assert(contains(Entry));
143 }
144
145 // Setup for using a depth-first iterator to visit every block in the cycle.
146 SmallVector<BlockT *, 8> ExitBBs;
147 getExitBlocks(ExitBBs);
148 df_iterator_default_set<BlockT *> VisitSet;
149 VisitSet.insert(ExitBBs.begin(), ExitBBs.end());
150
151 // Keep track of the BBs visited.
152 SmallPtrSet<BlockT *, 8> VisitedBBs;
153
154 // Check the individual blocks.
155 for (BlockT *BB : depth_first_ext(getHeader(), VisitSet)) {
156 assert(llvm::any_of(llvm::children<BlockT *>(BB),
157 [&](BlockT *B) { return contains(B); }) &&
158 "Cycle block has no in-cycle successors!");
159
160 assert(llvm::any_of(llvm::inverse_children<BlockT *>(BB),
161 [&](BlockT *B) { return contains(B); }) &&
162 "Cycle block has no in-cycle predecessors!");
163
164 DenseSet<BlockT *> OutsideCyclePreds;
165 for (BlockT *B : llvm::inverse_children<BlockT *>(BB))
166 if (!contains(B))
167 OutsideCyclePreds.insert(B);
168
169 if (Entries.contains(BB)) {
170 assert(!OutsideCyclePreds.empty() && "Entry is unreachable!");
171 } else if (!OutsideCyclePreds.empty()) {
172 // A non-entry block shouldn't be reachable from outside the cycle,
173 // though it is permitted if the predecessor is not itself actually
174 // reachable.
175 BlockT *EntryBB = &BB->getParent()->front();
176 for (BlockT *CB : depth_first(EntryBB))
177 assert(!OutsideCyclePreds.contains(CB) &&
178 "Non-entry block reachable from outside!");
179 }
180 assert(BB != &getHeader()->getParent()->front() &&
181 "Cycle contains function entry block!");
182
183 VisitedBBs.insert(BB);
184 }
185
186 if (VisitedBBs.size() != getNumBlocks()) {
187 dbgs() << "The following blocks are unreachable in the cycle:\n ";
188 ListSeparator LS;
189 for (auto *BB : Blocks) {
190 if (!VisitedBBs.count(BB)) {
191 dbgs() << LS;
192 BB->printAsOperand(dbgs());
193 }
194 }
195 dbgs() << "\n";
196 llvm_unreachable("Unreachable block in cycle");
197 }
198
199 verifyCycleNest();
200#endif
201}
202
203/// \brief Verify the parent-child relations of this cycle.
204///
205/// Note that this does \em not check that cycle is really a cycle in the CFG.
206template <typename ContextT>
207void GenericCycle<ContextT>::verifyCycleNest() const {
208#ifndef NDEBUG
209 // Check the subcycles.
210 for (GenericCycle *Child : children()) {
211 // Each block in each subcycle should be contained within this cycle.
212 for (BlockT *BB : Child->blocks()) {
213 assert(contains(BB) &&
214 "Cycle does not contain all the blocks of a subcycle!");
215 }
216 assert(Child->Depth == Depth + 1);
217 }
218
219 // Check the parent cycle pointer.
220 if (ParentCycle) {
221 assert(is_contained(ParentCycle->children(), this) &&
222 "Cycle is not a subcycle of its parent!");
223 }
224#endif
225}
226
227/// \brief Helper class for computing cycle information.
228template <typename ContextT> class GenericCycleInfoCompute {
229 using BlockT = typename ContextT::BlockT;
230 using CycleInfoT = GenericCycleInfo<ContextT>;
231 using CycleT = typename CycleInfoT::CycleT;
232
233 CycleInfoT &Info;
234
235 struct DFSInfo {
236 unsigned Start = 0; // DFS start; positive if block is found
237 unsigned End = 0; // DFS end
238
239 DFSInfo() = default;
240 explicit DFSInfo(unsigned Start) : Start(Start) {}
241
242 explicit operator bool() const { return Start; }
243
244 /// Whether this node is an ancestor (or equal to) the node \p Other
245 /// in the DFS tree.
246 bool isAncestorOf(const DFSInfo &Other) const {
247 return Start <= Other.Start && Other.End <= End;
248 }
249 };
250
251 DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
252 SmallVector<BlockT *, 8> BlockPreorder;
253
254 GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete;
255 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
256
257public:
258 GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {}
259
260 void run(BlockT *EntryBlock);
261
262 static void updateDepth(CycleT *SubTree);
263
264private:
265 void dfs(BlockT *EntryBlock);
266};
267
268template <typename ContextT>
269auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(BlockT *Block)
270 -> CycleT * {
271 auto Cycle = BlockMapTopLevel.find(Block);
272 if (Cycle != BlockMapTopLevel.end())
273 return Cycle->second;
274
275 auto MapIt = BlockMap.find(Block);
276 if (MapIt == BlockMap.end())
277 return nullptr;
278
279 auto *C = MapIt->second;
280 while (C->ParentCycle)
281 C = C->ParentCycle;
282 BlockMapTopLevel.try_emplace(Block, C);
283 return C;
284}
285
286template <typename ContextT>
287void GenericCycleInfo<ContextT>::moveTopLevelCycleToNewParent(CycleT *NewParent,
288 CycleT *Child) {
289 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
290 "NewParent and Child must be both top level cycle!\n");
291 auto &CurrentContainer =
292 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
293 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
294 return Child == Ptr.get();
295 });
296 assert(Pos != CurrentContainer.end());
297 NewParent->Children.push_back(std::move(*Pos));
298 *Pos = std::move(CurrentContainer.back());
299 CurrentContainer.pop_back();
300 Child->ParentCycle = NewParent;
301
302 NewParent->Blocks.insert_range(Child->blocks());
303
304 for (auto &It : BlockMapTopLevel)
305 if (It.second == Child)
306 It.second = NewParent;
307 NewParent->clearCache();
308 Child->clearCache();
309}
310
311template <typename ContextT>
312void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) {
313 // FixMe: Appending NewBlock is fine as a set of blocks in a cycle. When
314 // printing, cycle NewBlock is at the end of list but it should be in the
315 // middle to represent actual traversal of a cycle.
316 Cycle->appendBlock(Block);
317 BlockMap.try_emplace(Block, Cycle);
318
319 CycleT *ParentCycle = Cycle->getParentCycle();
320 while (ParentCycle) {
321 Cycle = ParentCycle;
322 Cycle->appendBlock(Block);
323 ParentCycle = Cycle->getParentCycle();
324 }
325
326 BlockMapTopLevel.try_emplace(Block, Cycle);
327 Cycle->clearCache();
328}
329
330/// \brief Main function of the cycle info computations.
331template <typename ContextT>
332void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) {
333 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
334 << "\n");
335 dfs(EntryBlock);
336
337 SmallVector<BlockT *, 8> Worklist;
338
339 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
340 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
341
342 for (BlockT *Pred : predecessors(HeaderCandidate)) {
343 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
344 // This automatically ignores unreachable predecessors since they have
345 // zeros in their DFSInfo.
346 if (CandidateInfo.isAncestorOf(PredDFSInfo))
347 Worklist.push_back(Pred);
348 }
349 if (Worklist.empty()) {
350 continue;
351 }
352
353 // Found a cycle with the candidate as its header.
354 LLVM_DEBUG(errs() << "Found cycle for header: "
355 << Info.Context.print(HeaderCandidate) << "\n");
356 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
357 NewCycle->appendEntry(HeaderCandidate);
358 NewCycle->appendBlock(HeaderCandidate);
359 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
360
361 // Helper function to process (non-back-edge) predecessors of a discovered
362 // block and either add them to the worklist or recognize that the given
363 // block is an additional cycle entry.
364 auto ProcessPredecessors = [&](BlockT *Block) {
365 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
366
367 bool IsEntry = false;
368 for (BlockT *Pred : predecessors(Block)) {
369 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
370 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
371 Worklist.push_back(Pred);
372 } else if (!PredDFSInfo) {
373 // Ignore an unreachable predecessor. It will will incorrectly cause
374 // Block to be treated as a cycle entry.
375 LLVM_DEBUG(errs() << " skipped unreachable predecessor.\n");
376 } else {
377 IsEntry = true;
378 }
379 }
380 if (IsEntry) {
381 assert(!NewCycle->isEntry(Block));
382 LLVM_DEBUG(errs() << "append as entry\n");
383 NewCycle->appendEntry(Block);
384 } else {
385 LLVM_DEBUG(errs() << "append as child\n");
386 }
387 };
388
389 do {
390 BlockT *Block = Worklist.pop_back_val();
391 if (Block == HeaderCandidate)
392 continue;
393
394 // If the block has already been discovered by some cycle
395 // (possibly by ourself), then the outermost cycle containing it
396 // should become our child.
397 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
398 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
399
400 if (BlockParent != NewCycle.get()) {
401 LLVM_DEBUG(errs()
402 << "discovered child cycle "
403 << Info.Context.print(BlockParent->getHeader()) << "\n");
404 // Make BlockParent the child of NewCycle.
405 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
406
407 for (auto *ChildEntry : BlockParent->entries())
408 ProcessPredecessors(ChildEntry);
409 } else {
410 LLVM_DEBUG(errs()
411 << "known child cycle "
412 << Info.Context.print(BlockParent->getHeader()) << "\n");
413 }
414 } else {
415 Info.BlockMap.try_emplace(Block, NewCycle.get());
416 assert(!is_contained(NewCycle->Blocks, Block));
417 NewCycle->Blocks.insert(Block);
418 ProcessPredecessors(Block);
419 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
420 }
421 } while (!Worklist.empty());
422
423 Info.TopLevelCycles.push_back(std::move(NewCycle));
424 }
425
426 // Fix top-level cycle links and compute cycle depths.
427 for (auto *TLC : Info.toplevel_cycles()) {
428 LLVM_DEBUG(errs() << "top-level cycle: "
429 << Info.Context.print(TLC->getHeader()) << "\n");
430
431 TLC->ParentCycle = nullptr;
432 updateDepth(SubTree: TLC);
433 }
434}
435
436/// \brief Recompute depth values of \p SubTree and all descendants.
437template <typename ContextT>
438void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) {
439 for (CycleT *Cycle : depth_first(SubTree))
440 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
441}
442
443/// \brief Compute a DFS of basic blocks starting at the function entry.
444///
445/// Fills BlockDFSInfo with start/end counters and BlockPreorder.
446template <typename ContextT>
447void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
448 SmallVector<unsigned, 8> DFSTreeStack;
449 SmallVector<BlockT *, 8> TraverseStack;
450 unsigned Counter = 0;
451 TraverseStack.emplace_back(EntryBlock);
452
453 do {
454 BlockT *Block = TraverseStack.back();
455 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
456 << "\n");
457 if (BlockDFSInfo.try_emplace(Block, Counter + 1).second) {
458 ++Counter;
459
460 // We're visiting the block for the first time. Open its DFSInfo, add
461 // successors to the traversal stack, and remember the traversal stack
462 // depth at which the block was opened, so that we can correctly record
463 // its end time.
464 LLVM_DEBUG(errs() << " first encountered at depth "
465 << TraverseStack.size() << "\n");
466
467 DFSTreeStack.emplace_back(TraverseStack.size());
468 llvm::append_range(TraverseStack, successors(Block));
469
470 BlockPreorder.push_back(Block);
471 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
472 } else {
473 assert(!DFSTreeStack.empty());
474 if (DFSTreeStack.back() == TraverseStack.size()) {
475 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
476 BlockDFSInfo.find(Block)->second.End = Counter;
477 DFSTreeStack.pop_back();
478 } else {
479 LLVM_DEBUG(errs() << " already done\n");
480 }
481 TraverseStack.pop_back();
482 }
483 } while (!TraverseStack.empty());
484 assert(DFSTreeStack.empty());
485
486 LLVM_DEBUG(
487 errs() << "Preorder:\n";
488 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
489 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
490 }
491 );
492}
493
494/// \brief Reset the object to its initial state.
495template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
496 TopLevelCycles.clear();
497 BlockMap.clear();
498 BlockMapTopLevel.clear();
499}
500
501/// \brief Compute the cycle info for a function.
502template <typename ContextT>
503void GenericCycleInfo<ContextT>::compute(FunctionT &F) {
504 GenericCycleInfoCompute<ContextT> Compute(*this);
505 Context = ContextT(&F);
506
507 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
508 << "\n");
509 Compute.run(&F.front());
510}
511
512template <typename ContextT>
513void GenericCycleInfo<ContextT>::splitCriticalEdge(BlockT *Pred, BlockT *Succ,
514 BlockT *NewBlock) {
515 // Edge Pred-Succ is replaced by edges Pred-NewBlock and NewBlock-Succ, all
516 // cycles that had blocks Pred and Succ also get NewBlock.
517 CycleT *Cycle = getSmallestCommonCycle(A: getCycle(Block: Pred), B: getCycle(Block: Succ));
518 if (!Cycle)
519 return;
520
521 addBlockToCycle(Block: NewBlock, Cycle);
522 verifyCycleNest();
523}
524
525/// \brief Find the innermost cycle containing a given block.
526///
527/// \returns the innermost cycle containing \p Block or nullptr if
528/// it is not contained in any cycle.
529template <typename ContextT>
530auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
531 -> CycleT * {
532 return BlockMap.lookup(Block);
533}
534
535/// \brief Find the innermost cycle containing both given cycles.
536///
537/// \returns the innermost cycle containing both \p A and \p B
538/// or nullptr if there is no such cycle.
539template <typename ContextT>
540auto GenericCycleInfo<ContextT>::getSmallestCommonCycle(CycleT *A,
541 CycleT *B) const
542 -> CycleT * {
543 if (!A || !B)
544 return nullptr;
545
546 // If cycles A and B have different depth replace them with parent cycle
547 // until they have the same depth.
548 while (A->getDepth() > B->getDepth())
549 A = A->getParentCycle();
550 while (B->getDepth() > A->getDepth())
551 B = B->getParentCycle();
552
553 // Cycles A and B are at same depth but may be disjoint, replace them with
554 // parent cycles until we find cycle that contains both or we run out of
555 // parent cycles.
556 while (A != B) {
557 A = A->getParentCycle();
558 B = B->getParentCycle();
559 }
560
561 return A;
562}
563
564/// \brief get the depth for the cycle which containing a given block.
565///
566/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
567/// not contained in any cycle.
568template <typename ContextT>
569unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const {
570 CycleT *Cycle = getCycle(Block);
571 if (!Cycle)
572 return 0;
573 return Cycle->getDepth();
574}
575
576/// \brief Verify the internal consistency of the cycle tree.
577///
578/// Note that this does \em not check that cycles are really cycles in the CFG,
579/// or that the right set of cycles in the CFG were found.
580template <typename ContextT>
581void GenericCycleInfo<ContextT>::verifyCycleNest(bool VerifyFull) const {
582#ifndef NDEBUG
583 DenseSet<BlockT *> CycleHeaders;
584
585 for (CycleT *TopCycle : toplevel_cycles()) {
586 for (CycleT *Cycle : depth_first(TopCycle)) {
587 BlockT *Header = Cycle->getHeader();
588 assert(CycleHeaders.insert(Header).second);
589 if (VerifyFull)
590 Cycle->verifyCycle();
591 else
592 Cycle->verifyCycleNest();
593 // Check the block map entries for blocks contained in this cycle.
594 for (BlockT *BB : Cycle->blocks()) {
595 auto MapIt = BlockMap.find(BB);
596 assert(MapIt != BlockMap.end());
597 assert(Cycle->contains(MapIt->second));
598 }
599 }
600 }
601#endif
602}
603
604/// \brief Verify that the entire cycle tree well-formed.
605template <typename ContextT> void GenericCycleInfo<ContextT>::verify() const {
606 verifyCycleNest(/*VerifyFull=*/VerifyFull: true);
607}
608
609/// \brief Print the cycle info.
610template <typename ContextT>
611void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const {
612 for (const auto *TLC : toplevel_cycles()) {
613 for (const CycleT *Cycle : depth_first(TLC)) {
614 for (unsigned I = 0; I < Cycle->Depth; ++I)
615 Out << " ";
616
617 Out << Cycle->print(Context) << '\n';
618 }
619 }
620}
621
622} // namespace llvm
623
624#undef DEBUG_TYPE
625
626#endif // LLVM_ADT_GENERICCYCLEIMPL_H
627

source code of llvm/include/llvm/ADT/GenericCycleImpl.h