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
30#define DEBUG_TYPE "generic-cycle-impl"
31
32namespace llvm {
33
34template <typename ContextT>
35bool GenericCycle<ContextT>::contains(const GenericCycle *C) const {
36 if (!C)
37 return false;
38
39 if (Depth > C->Depth)
40 return false;
41 while (Depth < C->Depth)
42 C = C->ParentCycle;
43 return this == C;
44}
45
46template <typename ContextT>
47void GenericCycle<ContextT>::getExitBlocks(
48 SmallVectorImpl<BlockT *> &TmpStorage) const {
49 TmpStorage.clear();
50
51 size_t NumExitBlocks = 0;
52 for (BlockT *Block : blocks()) {
53 llvm::append_range(TmpStorage, successors(Block));
54
55 for (size_t Idx = NumExitBlocks, End = TmpStorage.size(); Idx < End;
56 ++Idx) {
57 BlockT *Succ = TmpStorage[Idx];
58 if (!contains(Succ)) {
59 auto ExitEndIt = TmpStorage.begin() + NumExitBlocks;
60 if (std::find(TmpStorage.begin(), ExitEndIt, Succ) == ExitEndIt)
61 TmpStorage[NumExitBlocks++] = Succ;
62 }
63 }
64
65 TmpStorage.resize(NumExitBlocks);
66 }
67}
68
69template <typename ContextT>
70auto GenericCycle<ContextT>::getCyclePreheader() const -> BlockT * {
71 BlockT *Predecessor = getCyclePredecessor();
72 if (!Predecessor)
73 return nullptr;
74
75 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
76
77 if (succ_size(Predecessor) != 1)
78 return nullptr;
79
80 // Make sure we are allowed to hoist instructions into the predecessor.
81 if (!Predecessor->isLegalToHoistInto())
82 return nullptr;
83
84 return Predecessor;
85}
86
87template <typename ContextT>
88auto GenericCycle<ContextT>::getCyclePredecessor() const -> BlockT * {
89 if (!isReducible())
90 return nullptr;
91
92 BlockT *Out = nullptr;
93
94 // Loop over the predecessors of the header node...
95 BlockT *Header = getHeader();
96 for (const auto Pred : predecessors(Header)) {
97 if (!contains(Pred)) {
98 if (Out && Out != Pred)
99 return nullptr;
100 Out = Pred;
101 }
102 }
103
104 return Out;
105}
106
107/// \brief Helper class for computing cycle information.
108template <typename ContextT> class GenericCycleInfoCompute {
109 using BlockT = typename ContextT::BlockT;
110 using CycleInfoT = GenericCycleInfo<ContextT>;
111 using CycleT = typename CycleInfoT::CycleT;
112
113 CycleInfoT &Info;
114
115 struct DFSInfo {
116 unsigned Start = 0; // DFS start; positive if block is found
117 unsigned End = 0; // DFS end
118
119 DFSInfo() = default;
120 explicit DFSInfo(unsigned Start) : Start(Start) {}
121
122 /// Whether this node is an ancestor (or equal to) the node \p Other
123 /// in the DFS tree.
124 bool isAncestorOf(const DFSInfo &Other) const {
125 return Start <= Other.Start && Other.End <= End;
126 }
127 };
128
129 DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
130 SmallVector<BlockT *, 8> BlockPreorder;
131
132 GenericCycleInfoCompute(const GenericCycleInfoCompute &) = delete;
133 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
134
135public:
136 GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {}
137
138 void run(BlockT *EntryBlock);
139
140 static void updateDepth(CycleT *SubTree);
141
142private:
143 void dfs(BlockT *EntryBlock);
144};
145
146template <typename ContextT>
147auto GenericCycleInfo<ContextT>::getTopLevelParentCycle(BlockT *Block)
148 -> CycleT * {
149 auto Cycle = BlockMapTopLevel.find(Block);
150 if (Cycle != BlockMapTopLevel.end())
151 return Cycle->second;
152
153 auto MapIt = BlockMap.find(Block);
154 if (MapIt == BlockMap.end())
155 return nullptr;
156
157 auto *C = MapIt->second;
158 while (C->ParentCycle)
159 C = C->ParentCycle;
160 BlockMapTopLevel.try_emplace(Block, C);
161 return C;
162}
163
164template <typename ContextT>
165void GenericCycleInfo<ContextT>::moveTopLevelCycleToNewParent(CycleT *NewParent,
166 CycleT *Child) {
167 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
168 "NewParent and Child must be both top level cycle!\n");
169 auto &CurrentContainer =
170 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
171 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
172 return Child == Ptr.get();
173 });
174 assert(Pos != CurrentContainer.end());
175 NewParent->Children.push_back(std::move(*Pos));
176 *Pos = std::move(CurrentContainer.back());
177 CurrentContainer.pop_back();
178 Child->ParentCycle = NewParent;
179
180 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
181
182 for (auto &It : BlockMapTopLevel)
183 if (It.second == Child)
184 It.second = NewParent;
185}
186
187template <typename ContextT>
188void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) {
189 // FixMe: Appending NewBlock is fine as a set of blocks in a cycle. When
190 // printing, cycle NewBlock is at the end of list but it should be in the
191 // middle to represent actual traversal of a cycle.
192 Cycle->appendBlock(Block);
193 BlockMap.try_emplace(Block, Cycle);
194
195 CycleT *ParentCycle = Cycle->getParentCycle();
196 while (ParentCycle) {
197 Cycle = ParentCycle;
198 Cycle->appendBlock(Block);
199 ParentCycle = Cycle->getParentCycle();
200 }
201
202 BlockMapTopLevel.try_emplace(Block, Cycle);
203}
204
205/// \brief Main function of the cycle info computations.
206template <typename ContextT>
207void GenericCycleInfoCompute<ContextT>::run(BlockT *EntryBlock) {
208 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
209 << "\n");
210 dfs(EntryBlock);
211
212 SmallVector<BlockT *, 8> Worklist;
213
214 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
215 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
216
217 for (BlockT *Pred : predecessors(HeaderCandidate)) {
218 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
219 if (CandidateInfo.isAncestorOf(PredDFSInfo))
220 Worklist.push_back(Pred);
221 }
222 if (Worklist.empty()) {
223 continue;
224 }
225
226 // Found a cycle with the candidate as its header.
227 LLVM_DEBUG(errs() << "Found cycle for header: "
228 << Info.Context.print(HeaderCandidate) << "\n");
229 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
230 NewCycle->appendEntry(HeaderCandidate);
231 NewCycle->appendBlock(HeaderCandidate);
232 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
233
234 // Helper function to process (non-back-edge) predecessors of a discovered
235 // block and either add them to the worklist or recognize that the given
236 // block is an additional cycle entry.
237 auto ProcessPredecessors = [&](BlockT *Block) {
238 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
239
240 bool IsEntry = false;
241 for (BlockT *Pred : predecessors(Block)) {
242 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
243 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
244 Worklist.push_back(Pred);
245 } else {
246 IsEntry = true;
247 }
248 }
249 if (IsEntry) {
250 assert(!NewCycle->isEntry(Block));
251 LLVM_DEBUG(errs() << "append as entry\n");
252 NewCycle->appendEntry(Block);
253 } else {
254 LLVM_DEBUG(errs() << "append as child\n");
255 }
256 };
257
258 do {
259 BlockT *Block = Worklist.pop_back_val();
260 if (Block == HeaderCandidate)
261 continue;
262
263 // If the block has already been discovered by some cycle
264 // (possibly by ourself), then the outermost cycle containing it
265 // should become our child.
266 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
267 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
268
269 if (BlockParent != NewCycle.get()) {
270 LLVM_DEBUG(errs()
271 << "discovered child cycle "
272 << Info.Context.print(BlockParent->getHeader()) << "\n");
273 // Make BlockParent the child of NewCycle.
274 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
275
276 for (auto *ChildEntry : BlockParent->entries())
277 ProcessPredecessors(ChildEntry);
278 } else {
279 LLVM_DEBUG(errs()
280 << "known child cycle "
281 << Info.Context.print(BlockParent->getHeader()) << "\n");
282 }
283 } else {
284 Info.BlockMap.try_emplace(Block, NewCycle.get());
285 assert(!is_contained(NewCycle->Blocks, Block));
286 NewCycle->Blocks.insert(Block);
287 ProcessPredecessors(Block);
288 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
289 }
290 } while (!Worklist.empty());
291
292 Info.TopLevelCycles.push_back(std::move(NewCycle));
293 }
294
295 // Fix top-level cycle links and compute cycle depths.
296 for (auto *TLC : Info.toplevel_cycles()) {
297 LLVM_DEBUG(errs() << "top-level cycle: "
298 << Info.Context.print(TLC->getHeader()) << "\n");
299
300 TLC->ParentCycle = nullptr;
301 updateDepth(SubTree: TLC);
302 }
303}
304
305/// \brief Recompute depth values of \p SubTree and all descendants.
306template <typename ContextT>
307void GenericCycleInfoCompute<ContextT>::updateDepth(CycleT *SubTree) {
308 for (CycleT *Cycle : depth_first(SubTree))
309 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
310}
311
312/// \brief Compute a DFS of basic blocks starting at the function entry.
313///
314/// Fills BlockDFSInfo with start/end counters and BlockPreorder.
315template <typename ContextT>
316void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
317 SmallVector<unsigned, 8> DFSTreeStack;
318 SmallVector<BlockT *, 8> TraverseStack;
319 unsigned Counter = 0;
320 TraverseStack.emplace_back(EntryBlock);
321
322 do {
323 BlockT *Block = TraverseStack.back();
324 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
325 << "\n");
326 if (!BlockDFSInfo.count(Block)) {
327 // We're visiting the block for the first time. Open its DFSInfo, add
328 // successors to the traversal stack, and remember the traversal stack
329 // depth at which the block was opened, so that we can correctly record
330 // its end time.
331 LLVM_DEBUG(errs() << " first encountered at depth "
332 << TraverseStack.size() << "\n");
333
334 DFSTreeStack.emplace_back(TraverseStack.size());
335 llvm::append_range(TraverseStack, successors(Block));
336
337 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
338 (void)Added;
339 assert(Added);
340 BlockPreorder.push_back(Block);
341 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
342 } else {
343 assert(!DFSTreeStack.empty());
344 if (DFSTreeStack.back() == TraverseStack.size()) {
345 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
346 BlockDFSInfo.find(Block)->second.End = Counter;
347 DFSTreeStack.pop_back();
348 } else {
349 LLVM_DEBUG(errs() << " already done\n");
350 }
351 TraverseStack.pop_back();
352 }
353 } while (!TraverseStack.empty());
354 assert(DFSTreeStack.empty());
355
356 LLVM_DEBUG(
357 errs() << "Preorder:\n";
358 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
359 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
360 }
361 );
362}
363
364/// \brief Reset the object to its initial state.
365template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
366 TopLevelCycles.clear();
367 BlockMap.clear();
368 BlockMapTopLevel.clear();
369}
370
371/// \brief Compute the cycle info for a function.
372template <typename ContextT>
373void GenericCycleInfo<ContextT>::compute(FunctionT &F) {
374 GenericCycleInfoCompute<ContextT> Compute(*this);
375 Context = ContextT(&F);
376
377 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
378 << "\n");
379 Compute.run(&F.front());
380
381 assert(validateTree());
382}
383
384template <typename ContextT>
385void GenericCycleInfo<ContextT>::splitCriticalEdge(BlockT *Pred, BlockT *Succ,
386 BlockT *NewBlock) {
387 // Edge Pred-Succ is replaced by edges Pred-NewBlock and NewBlock-Succ, all
388 // cycles that had blocks Pred and Succ also get NewBlock.
389 CycleT *Cycle = getSmallestCommonCycle(A: getCycle(Block: Pred), B: getCycle(Block: Succ));
390 if (!Cycle)
391 return;
392
393 addBlockToCycle(Block: NewBlock, Cycle);
394 assert(validateTree());
395}
396
397/// \brief Find the innermost cycle containing a given block.
398///
399/// \returns the innermost cycle containing \p Block or nullptr if
400/// it is not contained in any cycle.
401template <typename ContextT>
402auto GenericCycleInfo<ContextT>::getCycle(const BlockT *Block) const
403 -> CycleT * {
404 return BlockMap.lookup(Block);
405}
406
407/// \brief Find the innermost cycle containing both given cycles.
408///
409/// \returns the innermost cycle containing both \p A and \p B
410/// or nullptr if there is no such cycle.
411template <typename ContextT>
412auto GenericCycleInfo<ContextT>::getSmallestCommonCycle(CycleT *A,
413 CycleT *B) const
414 -> CycleT * {
415 if (!A || !B)
416 return nullptr;
417
418 // If cycles A and B have different depth replace them with parent cycle
419 // until they have the same depth.
420 while (A->getDepth() > B->getDepth())
421 A = A->getParentCycle();
422 while (B->getDepth() > A->getDepth())
423 B = B->getParentCycle();
424
425 // Cycles A and B are at same depth but may be disjoint, replace them with
426 // parent cycles until we find cycle that contains both or we run out of
427 // parent cycles.
428 while (A != B) {
429 A = A->getParentCycle();
430 B = B->getParentCycle();
431 }
432
433 return A;
434}
435
436/// \brief get the depth for the cycle which containing a given block.
437///
438/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
439/// not contained in any cycle.
440template <typename ContextT>
441unsigned GenericCycleInfo<ContextT>::getCycleDepth(const BlockT *Block) const {
442 CycleT *Cycle = getCycle(Block);
443 if (!Cycle)
444 return 0;
445 return Cycle->getDepth();
446}
447
448#ifndef NDEBUG
449/// \brief Validate the internal consistency of the cycle tree.
450///
451/// Note that this does \em not check that cycles are really cycles in the CFG,
452/// or that the right set of cycles in the CFG were found.
453template <typename ContextT>
454bool GenericCycleInfo<ContextT>::validateTree() const {
455 DenseSet<BlockT *> Blocks;
456 DenseSet<BlockT *> Entries;
457
458 auto reportError = [](const char *File, int Line, const char *Cond) {
459 errs() << File << ':' << Line
460 << ": GenericCycleInfo::validateTree: " << Cond << '\n';
461 };
462#define check(cond) \
463 do { \
464 if (!(cond)) { \
465 reportError(__FILE__, __LINE__, #cond); \
466 return false; \
467 } \
468 } while (false)
469
470 for (const auto *TLC : toplevel_cycles()) {
471 for (const CycleT *Cycle : depth_first(TLC)) {
472 if (Cycle->ParentCycle)
473 check(is_contained(Cycle->ParentCycle->children(), Cycle));
474
475 for (BlockT *Block : Cycle->Blocks) {
476 auto MapIt = BlockMap.find(Block);
477 check(MapIt != BlockMap.end());
478 check(Cycle->contains(MapIt->second));
479 check(Blocks.insert(Block).second); // duplicates in block list?
480 }
481 Blocks.clear();
482
483 check(!Cycle->Entries.empty());
484 for (BlockT *Entry : Cycle->Entries) {
485 check(Entries.insert(Entry).second); // duplicate entry?
486 check(is_contained(Cycle->Blocks, Entry));
487 }
488 Entries.clear();
489
490 unsigned ChildDepth = 0;
491 for (const CycleT *Child : Cycle->children()) {
492 check(Child->Depth > Cycle->Depth);
493 if (!ChildDepth) {
494 ChildDepth = Child->Depth;
495 } else {
496 check(ChildDepth == Child->Depth);
497 }
498 }
499 }
500 }
501
502 for (const auto &Entry : BlockMap) {
503 BlockT *Block = Entry.first;
504 for (const CycleT *Cycle = Entry.second; Cycle;
505 Cycle = Cycle->ParentCycle) {
506 check(is_contained(Cycle->Blocks, Block));
507 }
508 }
509
510#undef check
511
512 return true;
513}
514#endif
515
516/// \brief Print the cycle info.
517template <typename ContextT>
518void GenericCycleInfo<ContextT>::print(raw_ostream &Out) const {
519 for (const auto *TLC : toplevel_cycles()) {
520 for (const CycleT *Cycle : depth_first(TLC)) {
521 for (unsigned I = 0; I < Cycle->Depth; ++I)
522 Out << " ";
523
524 Out << Cycle->print(Context) << '\n';
525 }
526 }
527}
528
529} // namespace llvm
530
531#undef DEBUG_TYPE
532
533#endif // LLVM_ADT_GENERICCYCLEIMPL_H
534

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