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"
30
31#define DEBUG_TYPE "generic-cycle-impl"
32
33namespace llvm {
34
35template <typename ContextT>
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>
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()) {
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>
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>
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>
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.");
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.
147 getExitBlocks(ExitBBs);
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>
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
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>
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>
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;
302 NewParent->Blocks.insert(Child->block_begin(), Child->block_end());
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>
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>
333 LLVM_DEBUG(errs() << "Entry block: " << Info.Context.print(EntryBlock)
334 << "\n");
335 dfs(EntryBlock);
336
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()) {
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 {
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(TLC);
433 }
434}
435
436/// \brief Recompute depth values of \p SubTree and all descendants.
437template <typename ContextT>
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.count(Block)) {
458 // We're visiting the block for the first time. Open its DFSInfo, add
459 // successors to the traversal stack, and remember the traversal stack
460 // depth at which the block was opened, so that we can correctly record
461 // its end time.
462 LLVM_DEBUG(errs() << " first encountered at depth "
463 << TraverseStack.size() << "\n");
464
465 DFSTreeStack.emplace_back(TraverseStack.size());
466 llvm::append_range(TraverseStack, successors(Block));
467
468 bool Added = BlockDFSInfo.try_emplace(Block, ++Counter).second;
469 (void)Added;
470 assert(Added);
471 BlockPreorder.push_back(Block);
472 LLVM_DEBUG(errs() << " preorder number: " << Counter << "\n");
473 } else {
474 assert(!DFSTreeStack.empty());
475 if (DFSTreeStack.back() == TraverseStack.size()) {
476 LLVM_DEBUG(errs() << " ended at " << Counter << "\n");
477 BlockDFSInfo.find(Block)->second.End = Counter;
478 DFSTreeStack.pop_back();
479 } else {
480 LLVM_DEBUG(errs() << " already done\n");
481 }
482 TraverseStack.pop_back();
483 }
484 } while (!TraverseStack.empty());
485 assert(DFSTreeStack.empty());
486
488 errs() << "Preorder:\n";
489 for (int i = 0, e = BlockPreorder.size(); i != e; ++i) {
490 errs() << " " << Info.Context.print(BlockPreorder[i]) << ": " << i << "\n";
491 }
492 );
493}
494
495/// \brief Reset the object to its initial state.
496template <typename ContextT> void GenericCycleInfo<ContextT>::clear() {
497 TopLevelCycles.clear();
498 BlockMap.clear();
499 BlockMapTopLevel.clear();
500}
501
502/// \brief Compute the cycle info for a function.
503template <typename ContextT>
506 Context = ContextT(&F);
507
508 LLVM_DEBUG(errs() << "Computing cycles for function: " << F.getName()
509 << "\n");
510 Compute.run(&F.front());
511}
512
513template <typename ContextT>
515 BlockT *NewBlock) {
516 // Edge Pred-Succ is replaced by edges Pred-NewBlock and NewBlock-Succ, all
517 // cycles that had blocks Pred and Succ also get NewBlock.
518 CycleT *Cycle = getSmallestCommonCycle(getCycle(Pred), getCycle(Succ));
519 if (!Cycle)
520 return;
521
522 addBlockToCycle(NewBlock, Cycle);
523 verifyCycleNest();
524}
525
526/// \brief Find the innermost cycle containing a given block.
527///
528/// \returns the innermost cycle containing \p Block or nullptr if
529/// it is not contained in any cycle.
530template <typename ContextT>
532 -> CycleT * {
533 return BlockMap.lookup(Block);
534}
535
536/// \brief Find the innermost cycle containing both given cycles.
537///
538/// \returns the innermost cycle containing both \p A and \p B
539/// or nullptr if there is no such cycle.
540template <typename ContextT>
542 CycleT *B) const
543 -> CycleT * {
544 if (!A || !B)
545 return nullptr;
546
547 // If cycles A and B have different depth replace them with parent cycle
548 // until they have the same depth.
549 while (A->getDepth() > B->getDepth())
550 A = A->getParentCycle();
551 while (B->getDepth() > A->getDepth())
552 B = B->getParentCycle();
553
554 // Cycles A and B are at same depth but may be disjoint, replace them with
555 // parent cycles until we find cycle that contains both or we run out of
556 // parent cycles.
557 while (A != B) {
558 A = A->getParentCycle();
559 B = B->getParentCycle();
560 }
561
562 return A;
563}
564
565/// \brief get the depth for the cycle which containing a given block.
566///
567/// \returns the depth for the innermost cycle containing \p Block or 0 if it is
568/// not contained in any cycle.
569template <typename ContextT>
571 CycleT *Cycle = getCycle(Block);
572 if (!Cycle)
573 return 0;
574 return Cycle->getDepth();
575}
576
577/// \brief Verify the internal consistency of the cycle tree.
578///
579/// Note that this does \em not check that cycles are really cycles in the CFG,
580/// or that the right set of cycles in the CFG were found.
581template <typename ContextT>
583#ifndef NDEBUG
584 DenseSet<BlockT *> CycleHeaders;
585
586 for (CycleT *TopCycle : toplevel_cycles()) {
587 for (CycleT *Cycle : depth_first(TopCycle)) {
588 BlockT *Header = Cycle->getHeader();
589 assert(CycleHeaders.insert(Header).second);
590 if (VerifyFull)
592 else
594 // Check the block map entries for blocks contained in this cycle.
595 for (BlockT *BB : Cycle->blocks()) {
596 auto MapIt = BlockMap.find(BB);
597 assert(MapIt != BlockMap.end());
598 assert(Cycle->contains(MapIt->second));
599 }
600 }
601 }
602#endif
603}
604
605/// \brief Verify that the entire cycle tree well-formed.
606template <typename ContextT> void GenericCycleInfo<ContextT>::verify() const {
607 verifyCycleNest(/*VerifyFull=*/true);
608}
609
610/// \brief Print the cycle info.
611template <typename ContextT>
613 for (const auto *TLC : toplevel_cycles()) {
614 for (const CycleT *Cycle : depth_first(TLC)) {
615 for (unsigned I = 0; I < Cycle->Depth; ++I)
616 Out << " ";
617
618 Out << Cycle->print(Context) << '\n';
619 }
620 }
621}
622
623} // namespace llvm
624
625#undef DEBUG_TYPE
626
627#endif // LLVM_ADT_GENERICCYCLEIMPL_H
aarch64 promote const
static const Function * getParent(const Value *V)
bbsections Prepares for basic block by splitting functions into clusters of basic blocks
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(...)
Definition: Debug.h:106
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
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
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool contains(SmallPtrSetImpl< ConstantExpr * > &Cache, ConstantExpr *Expr, Constant *C)
Definition: Value.cpp:469
This file contains some functions that are useful when dealing with strings.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:278
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 verify() const
Verify that the entire cycle tree well-formed.
void addBlockToCycle(BlockT *Block, CycleT *Cycle)
Assumes that Cycle is the innermost cycle containing Block.
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.
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.
void verifyCycleNest(bool VerifyFull=false) const
Methods for debug and self-test.
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 clearCache() const
Clear the cache of the cycle.
BlockT * getHeader() const
void getExitingBlocks(SmallVectorImpl< BlockT * > &TmpStorage) const
Return all blocks of this cycle that have successor outside of this cycle.
void verifyCycle() const
Verify that this is actually a well-formed cycle in the CFG.
void verifyCycleNest() const
Verify the parent-child relations of this cycle.
Printable print(const ContextT &Ctx) const
iterator_range< const_block_iterator > blocks() 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
size_type size() const
Definition: SmallPtrSet.h:94
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:452
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:384
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:519
bool empty() const
Definition: SmallVector.h:81
size_t size() const
Definition: SmallVector.h:78
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:573
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:937
void resize(size_type N)
Definition: SmallVector.h:638
void push_back(const T &Elt)
Definition: SmallVector.h:413
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1196
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:213
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition: DenseSet.h:193
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ 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
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
Definition: STLExtras.h:2115
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1746
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:420
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto succ_size(const MachineBasicBlock *BB)
raw_fd_ostream & errs()
This returns a reference to a raw_ostream for standard error.
@ Other
Any other memory.
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:1766
auto predecessors(const MachineBasicBlock *BB)
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
Definition: GraphTraits.h:149
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1903
iterator_range< df_iterator< T > > depth_first(const T &G)
std::pair< iterator, bool > insert(NodeRef N)