LLVM 20.0.0git
GenericCycleImpl.h
Go to the documentation of this file.
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"
29
30#define DEBUG_TYPE "generic-cycle-impl"
31
32namespace llvm {
33
34template <typename ContextT>
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>
48 SmallVectorImpl<BlockT *> &TmpStorage) const {
49 TmpStorage.clear();
50
51 size_t NumExitBlocks = 0;
52 for (BlockT *Block : blocks()) {
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>
71 SmallVectorImpl<BlockT *> &TmpStorage) const {
72 TmpStorage.clear();
73
74 for (BlockT *Block : blocks()) {
75 for (BlockT *Succ : successors(Block)) {
76 if (!contains(Succ)) {
77 TmpStorage.push_back(Block);
78 break;
79 }
80 }
81 }
82}
83
84template <typename ContextT>
86 BlockT *Predecessor = getCyclePredecessor();
87 if (!Predecessor)
88 return nullptr;
89
90 assert(isReducible() && "Cycle Predecessor must be in a reducible cycle!");
91
92 if (succ_size(Predecessor) != 1)
93 return nullptr;
94
95 // Make sure we are allowed to hoist instructions into the predecessor.
96 if (!Predecessor->isLegalToHoistInto())
97 return nullptr;
98
99 return Predecessor;
100}
101
102template <typename ContextT>
104 if (!isReducible())
105 return nullptr;
106
107 BlockT *Out = nullptr;
108
109 // Loop over the predecessors of the header node...
110 BlockT *Header = getHeader();
111 for (const auto Pred : predecessors(Header)) {
112 if (!contains(Pred)) {
113 if (Out && Out != Pred)
114 return nullptr;
115 Out = Pred;
116 }
117 }
118
119 return Out;
120}
121
122/// \brief Helper class for computing cycle information.
123template <typename ContextT> class GenericCycleInfoCompute {
124 using BlockT = typename ContextT::BlockT;
125 using CycleInfoT = GenericCycleInfo<ContextT>;
126 using CycleT = typename CycleInfoT::CycleT;
127
128 CycleInfoT &Info;
129
130 struct DFSInfo {
131 unsigned Start = 0; // DFS start; positive if block is found
132 unsigned End = 0; // DFS end
133
134 DFSInfo() = default;
135 explicit DFSInfo(unsigned Start) : Start(Start) {}
136
137 explicit operator bool() const { return Start; }
138
139 /// Whether this node is an ancestor (or equal to) the node \p Other
140 /// in the DFS tree.
141 bool isAncestorOf(const DFSInfo &Other) const {
142 return Start <= Other.Start && Other.End <= End;
143 }
144 };
145
146 DenseMap<BlockT *, DFSInfo> BlockDFSInfo;
147 SmallVector<BlockT *, 8> BlockPreorder;
148
150 GenericCycleInfoCompute &operator=(const GenericCycleInfoCompute &) = delete;
151
152public:
153 GenericCycleInfoCompute(CycleInfoT &Info) : Info(Info) {}
154
155 void run(BlockT *EntryBlock);
156
157 static void updateDepth(CycleT *SubTree);
158
159private:
160 void dfs(BlockT *EntryBlock);
161};
162
163template <typename ContextT>
165 -> CycleT * {
166 auto Cycle = BlockMapTopLevel.find(Block);
167 if (Cycle != BlockMapTopLevel.end())
168 return Cycle->second;
169
170 auto MapIt = BlockMap.find(Block);
171 if (MapIt == BlockMap.end())
172 return nullptr;
173
174 auto *C = MapIt->second;
175 while (C->ParentCycle)
176 C = C->ParentCycle;
177 BlockMapTopLevel.try_emplace(Block, C);
178 return C;
179}
180
181template <typename ContextT>
183 CycleT *Child) {
184 assert((!Child->ParentCycle && !NewParent->ParentCycle) &&
185 "NewParent and Child must be both top level cycle!\n");
186 auto &CurrentContainer =
187 Child->ParentCycle ? Child->ParentCycle->Children : TopLevelCycles;
188 auto Pos = llvm::find_if(CurrentContainer, [=](const auto &Ptr) -> bool {
189 return Child == Ptr.get();
190 });
191 assert(Pos != CurrentContainer.end());
192 NewParent->Children.push_back(std::move(*Pos));
193 *Pos = std::move(CurrentContainer.back());
194 CurrentContainer.pop_back();
195 Child->ParentCycle = NewParent;
196
197 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
198
199 for (auto &It : BlockMapTopLevel)
200 if (It.second == Child)
201 It.second = NewParent;
202}
203
204template <typename ContextT>
205void GenericCycleInfo<ContextT>::addBlockToCycle(BlockT *Block, CycleT *Cycle) {
206 // FixMe: Appending NewBlock is fine as a set of blocks in a cycle. When
207 // printing, cycle NewBlock is at the end of list but it should be in the
208 // middle to represent actual traversal of a cycle.
209 Cycle->appendBlock(Block);
210 BlockMap.try_emplace(Block, Cycle);
211
212 CycleT *ParentCycle = Cycle->getParentCycle();
213 while (ParentCycle) {
214 Cycle = ParentCycle;
215 Cycle->appendBlock(Block);
216 ParentCycle = Cycle->getParentCycle();
217 }
218
219 BlockMapTopLevel.try_emplace(Block, Cycle);
220}
221
222/// \brief Main function of the cycle info computations.
223template <typename ContextT>
225 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
226 << "\n");
227 dfs(EntryBlock);
228
230
231 for (BlockT *HeaderCandidate : llvm::reverse(BlockPreorder)) {
232 const DFSInfo CandidateInfo = BlockDFSInfo.lookup(HeaderCandidate);
233
234 for (BlockT *Pred : predecessors(HeaderCandidate)) {
235 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
236 // This automatically ignores unreachable predecessors since they have
237 // zeros in their DFSInfo.
238 if (CandidateInfo.isAncestorOf(PredDFSInfo))
239 Worklist.push_back(Pred);
240 }
241 if (Worklist.empty()) {
242 continue;
243 }
244
245 // Found a cycle with the candidate as its header.
246 LLVM_DEBUG(errs() << "Found cycle for header: "
247 << Info.Context.print(HeaderCandidate) << "\n");
248 std::unique_ptr<CycleT> NewCycle = std::make_unique<CycleT>();
249 NewCycle->appendEntry(HeaderCandidate);
250 NewCycle->appendBlock(HeaderCandidate);
251 Info.BlockMap.try_emplace(HeaderCandidate, NewCycle.get());
252
253 // Helper function to process (non-back-edge) predecessors of a discovered
254 // block and either add them to the worklist or recognize that the given
255 // block is an additional cycle entry.
256 auto ProcessPredecessors = [&](BlockT *Block) {
257 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
258
259 bool IsEntry = false;
260 for (BlockT *Pred : predecessors(Block)) {
261 const DFSInfo PredDFSInfo = BlockDFSInfo.lookup(Pred);
262 if (CandidateInfo.isAncestorOf(PredDFSInfo)) {
263 Worklist.push_back(Pred);
264 } else if (!PredDFSInfo) {
265 // Ignore an unreachable predecessor. It will will incorrectly cause
266 // Block to be treated as a cycle entry.
267 LLVM_DEBUG(errs() << " skipped unreachable predecessor.\n");
268 } else {
269 IsEntry = true;
270 }
271 }
272 if (IsEntry) {
273 assert(!NewCycle->isEntry(Block));
274 LLVM_DEBUG(errs() << "append as entry\n");
275 NewCycle->appendEntry(Block);
276 } else {
277 LLVM_DEBUG(errs() << "append as child\n");
278 }
279 };
280
281 do {
282 BlockT *Block = Worklist.pop_back_val();
283 if (Block == HeaderCandidate)
284 continue;
285
286 // If the block has already been discovered by some cycle
287 // (possibly by ourself), then the outermost cycle containing it
288 // should become our child.
289 if (auto *BlockParent = Info.getTopLevelParentCycle(Block)) {
290 LLVM_DEBUG(errs() << " block " << Info.Context.print(Block) << ": ");
291
292 if (BlockParent != NewCycle.get()) {
294 << "discovered child cycle "
295 << Info.Context.print(BlockParent->getHeader()) << "\n");
296 // Make BlockParent the child of NewCycle.
297 Info.moveTopLevelCycleToNewParent(NewCycle.get(), BlockParent);
298
299 for (auto *ChildEntry : BlockParent->entries())
300 ProcessPredecessors(ChildEntry);
301 } else {
303 << "known child cycle "
304 << Info.Context.print(BlockParent->getHeader()) << "\n");
305 }
306 } else {
307 Info.BlockMap.try_emplace(Block, NewCycle.get());
308 assert(!is_contained(NewCycle->Blocks, Block));
309 NewCycle->Blocks.insert(Block);
310 ProcessPredecessors(Block);
311 Info.BlockMapTopLevel.try_emplace(Block, NewCycle.get());
312 }
313 } while (!Worklist.empty());
314
315 Info.TopLevelCycles.push_back(std::move(NewCycle));
316 }
317
318 // Fix top-level cycle links and compute cycle depths.
319 for (auto *TLC : Info.toplevel_cycles()) {
320 LLVM_DEBUG(errs() << "top-level cycle: "
321 << Info.Context.print(TLC->getHeader()) << "\n");
322
323 TLC->ParentCycle = nullptr;
324 updateDepth(TLC);
325 }
326}
327
328/// \brief Recompute depth values of \p SubTree and all descendants.
329template <typename ContextT>
331 for (CycleT *Cycle : depth_first(SubTree))
332 Cycle->Depth = Cycle->ParentCycle ? Cycle->ParentCycle->Depth + 1 : 1;
333}
334
335/// \brief Compute a DFS of basic blocks starting at the function entry.
336///
337/// Fills BlockDFSInfo with start/end counters and BlockPreorder.
338template <typename ContextT>
339void GenericCycleInfoCompute<ContextT>::dfs(BlockT *EntryBlock) {
340 SmallVector<unsigned, 8> DFSTreeStack;
341 SmallVector<BlockT *, 8> TraverseStack;
342 unsigned Counter = 0;
343 TraverseStack.emplace_back(EntryBlock);
344
345 do {
346 BlockT *Block = TraverseStack.back();
347 LLVM_DEBUG(errs() << "DFS visiting block: " << Info.Context.print(Block)
348 << "\n");
349 if (!BlockDFSInfo.count(Block)) {
350 // We're visiting the block for the first time. Open its DFSInfo, add
351 // successors to the traversal stack, and remember the traversal stack
352 // depth at which the block was opened, so that we can correctly record
353 // its end time.
354 LLVM_DEBUG(errs() << " first encountered at depth "
355 << TraverseStack.size() << "\n");
356
357 DFSTreeStack.emplace_back(TraverseStack.size());
358 llvm::append_range(TraverseStack, successors(Block));
359
360 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
361 (void)Added;
362 assert(Added);
363 BlockPreorder.push_back(Block);
364 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
365 } else {
366 assert(!DFSTreeStack.empty());
367 if (DFSTreeStack.back() == TraverseStack.size()) {
368 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
369 BlockDFSInfo.find(Block)->second.End = Counter;
370 DFSTreeStack.pop_back();
371 } else {
372 LLVM_DEBUG(errs() << " already done\n");
373 }
374 TraverseStack.pop_back();
375 }
376 } while (!TraverseStack.empty());
377 assert(DFSTreeStack.empty());
378
380 errs() << "Preorder:\n";
381 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
382 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
383 }
384 );
385}
386
387/// \brief Reset the object to its initial state.
388template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
389 TopLevelCycles.clear();
390 BlockMap.clear();
391 BlockMapTopLevel.clear();
392}
393
394/// \brief Compute the cycle info for a function.
395template <typename ContextT>
398 Context = ContextT(&F);
399
400 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
401 << "\n");
402 Compute.run(&F.front());
403
404 assert(validateTree());
405}
406
407template <typename ContextT>
409 BlockT *NewBlock) {
410 // Edge Pred-Succ is replaced by edges Pred-NewBlock and NewBlock-Succ, all
411 // cycles that had blocks Pred and Succ also get NewBlock.
412 CycleT *Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
413 if (!Cycle)
414 return;
415
416 addBlockToCycle(NewBlock, Cycle);
417 assert(validateTree());
418}
419
420/// \brief Find the innermost cycle containing a given block.
421///
422/// \returns the innermost cycle containing \p Block or nullptr if
423/// it is not contained in any cycle.
424template <typename ContextT>
426 -> CycleT * {
427 return BlockMap.lookup(Block);
428}
429
430/// \brief Find the innermost cycle containing both given cycles.
431///
432/// \returns the innermost cycle containing both \p A and \p B
433/// or nullptr if there is no such cycle.
434template <typename ContextT>
436 CycleT *B) const
437 -> CycleT * {
438 if (!A || !B)
439 return nullptr;
440
441 // If cycles A and B have different depth replace them with parent cycle
442 // until they have the same depth.
443 while (A->getDepth() > B->getDepth())
444 A = A->getParentCycle();
445 while (B->getDepth() > A->getDepth())
446 B = B->getParentCycle();
447
448 // Cycles A and B are at same depth but may be disjoint, replace them with
449 // parent cycles until we find cycle that contains both or we run out of
450 // parent cycles.
451 while (A != B) {
452 A = A->getParentCycle();
453 B = B->getParentCycle();
454 }
455
456 return A;
457}
458
459/// \brief get the depth for the cycle which containing a given block.
460///
461/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
462/// not contained in any cycle.
463template <typename ContextT>
465 CycleT *Cycle = getCycle(Block);
466 if (!Cycle)
467 return 0;
468 return Cycle->getDepth();
469}
470
471#ifndef NDEBUG
472/// \brief Validate the internal consistency of the cycle tree.
473///
474/// Note that this does \em not check that cycles are really cycles in the CFG,
475/// or that the right set of cycles in the CFG were found.
476template <typename ContextT>
479 DenseSet<BlockT *> Entries;
480
481 auto reportError = [](const char *File, int Line, const char *Cond) {
482 errs() << File << ':' << Line
483 << ": GenericCycleInfo::validateTree: " << Cond << '\n';
484 };
485#define check(cond) \
486 do { \
487 if (!(cond)) { \
488 reportError(__FILE__, __LINE__, #cond); \
489 return false; \
490 } \
491 } while (false)
492
493 for (const auto *TLC : toplevel_cycles()) {
494 for (const CycleT *Cycle : depth_first(TLC)) {
495 if (Cycle->ParentCycle)
496 check(is_contained(Cycle->ParentCycle->children(), Cycle));
497
498 for (BlockT *Block : Cycle->Blocks) {
499 auto MapIt = BlockMap.find(Block);
500 check(MapIt != BlockMap.end());
501 check(Cycle->contains(MapIt->second));
502 check(Blocks.insert(Block).second); // duplicates in block list?
503 }
504 Blocks.clear();
505
506 check(!Cycle->Entries.empty());
507 for (BlockT *Entry : Cycle->Entries) {
508 check(Entries.insert(Entry).second); // duplicate entry?
509 check(is_contained(Cycle->Blocks, Entry));
510 }
511 Entries.clear();
512
513 unsigned ChildDepth = 0;
514 for (const CycleT *Child : Cycle->children()) {
515 check(Child->Depth > Cycle->Depth);
516 if (!ChildDepth) {
517 ChildDepth = Child->Depth;
518 } else {
519 check(ChildDepth == Child->Depth);
520 }
521 }
522 }
523 }
524
525 for (const auto &Entry : BlockMap) {
526 BlockT *Block = Entry.first;
527 for (const CycleT *Cycle = Entry.second; Cycle;
528 Cycle = Cycle->ParentCycle) {
529 check(is_contained(Cycle->Blocks, Block));
530 }
531 }
532
533#undef check
534
535 return true;
536}
537#endif
538
539/// \brief Print the cycle info.
540template <typename ContextT>
542 for (const auto *TLC : toplevel_cycles()) {
543 for (const CycleT *Cycle : depth_first(TLC)) {
544 for (unsigned I = 0; I < Cycle->Depth; ++I)
545 Out << " ";
546
547 Out << Cycle->print(Context) << '\n';
548 }
549 }
550}
551
552} // namespace llvm
553
554#undef DEBUG_TYPE
555
556#endif // LLVM_ADT_GENERICCYCLEIMPL_H
aarch64 promote const
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
static Error reportError(StringRef Message)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseSet and SmallDenseSet classes.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
bool End
Definition: ELF_riscv.cpp:480
DenseMap< Block *, BlockRelaxAux > Blocks
Definition: ELF_riscv.cpp:507
#define check(cond)
Find all cycles in a control-flow graph, including irreducible loops.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:469
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Helper class for computing cycle information.
void run(BlockT *EntryBlock)
Main function of the cycle info computations.
GenericCycleInfoCompute(CycleInfoT &Info)
static void updateDepth(CycleT *SubTree)
Recompute depth values of SubTree and all descendants.
Cycle information for a function.
typename ContextT::FunctionT FunctionT
void print(raw_ostream &Out) const
Print the cycle info.
CycleT * getSmallestCommonCycle(CycleT *A, CycleT *B) const
Find the innermost cycle containing both given cycles.
void clear()
Reset the object to its initial state.
bool validateTree() const
Methods for debug and self-test.
void compute(FunctionT &F)
Compute the cycle info for a function.
void splitCriticalEdge(BlockT *Pred, BlockT *Succ, BlockT *New)
unsigned getCycleDepth(const BlockT *Block) const
get the depth for the cycle which containing a given block.
typename ContextT::BlockT BlockT
CycleT * getTopLevelParentCycle(BlockT *Block)
CycleT * getCycle(const BlockT *Block) const
Find the innermost cycle containing a given block.
A possibly irreducible generalization of a Loop.
void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all blocks of this cycle that have successor outside of this cycle.
Printable print(const ContextT &Ctx) const
BlockT * getCyclePreheader() const
Return the preheader block for this cycle.
void getExitBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all of the successor blocks of this cycle.
BlockT * getCyclePredecessor() const
If the cycle has exactly one entry with exactly one predecessor, return it, otherwise return nullptr.
bool contains(const BlockT *Block) const
Return whether Block is contained in the cycle.
typename ContextT::BlockT BlockT
const GenericCycle * getParentCycle() const
unsigned getDepth() const
iterator_range< const_child_iterator > children() const
bool empty() const
Definition: SmallVector.h:95
size_t size() const
Definition: SmallVector.h:92
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:587
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:951
void resize(size_type N)
Definition: SmallVector.h:652
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2073
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:419
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Other
Any other memory.
CycleInfo::CycleT Cycle
Definition: CycleInfo.h:24
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1749
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1879
iterator_range< df_iterator< T > > depth_first(const T &G)
unsigned succ_size(const MachineBasicBlock *BB)