1//===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
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// This file defines the LoopInfo class that is used to identify natural loops
10// and determine the loop depth of various nodes of the CFG. Note that the
11// loops identified may actually be several natural loops that share the same
12// header node... not just a single natural loop.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/ADT/ScopeExit.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/Analysis/IVDescriptors.h"
20#include "llvm/Analysis/LoopIterator.h"
21#include "llvm/Analysis/LoopNestAnalysis.h"
22#include "llvm/Analysis/MemorySSA.h"
23#include "llvm/Analysis/MemorySSAUpdater.h"
24#include "llvm/Analysis/ScalarEvolutionExpressions.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/Config/llvm-config.h"
27#include "llvm/IR/CFG.h"
28#include "llvm/IR/Constants.h"
29#include "llvm/IR/DebugLoc.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Instructions.h"
32#include "llvm/IR/LLVMContext.h"
33#include "llvm/IR/Metadata.h"
34#include "llvm/IR/Module.h"
35#include "llvm/IR/PassManager.h"
36#include "llvm/IR/PrintPasses.h"
37#include "llvm/InitializePasses.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Support/GenericLoopInfoImpl.h"
40#include "llvm/Support/raw_ostream.h"
41using namespace llvm;
42
43// Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
44template class llvm::LoopBase<BasicBlock, Loop>;
45template class llvm::LoopInfoBase<BasicBlock, Loop>;
46
47// Always verify loopinfo if expensive checking is enabled.
48#ifdef EXPENSIVE_CHECKS
49bool llvm::VerifyLoopInfo = true;
50#else
51bool llvm::VerifyLoopInfo = false;
52#endif
53static cl::opt<bool, true>
54 VerifyLoopInfoX("verify-loop-info", cl::location(L&: VerifyLoopInfo),
55 cl::Hidden, cl::desc("Verify loop info (time consuming)"));
56
57//===----------------------------------------------------------------------===//
58// Loop implementation
59//
60
61bool Loop::isLoopInvariant(const Value *V) const {
62 if (const Instruction *I = dyn_cast<Instruction>(Val: V))
63 return !contains(Inst: I);
64 return true; // All non-instructions are loop invariant
65}
66
67bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
68 return all_of(Range: I->operands(), P: [this](Value *V) { return isLoopInvariant(V); });
69}
70
71bool Loop::makeLoopInvariant(Value *V, bool &Changed, Instruction *InsertPt,
72 MemorySSAUpdater *MSSAU,
73 ScalarEvolution *SE) const {
74 if (Instruction *I = dyn_cast<Instruction>(Val: V))
75 return makeLoopInvariant(I, Changed, InsertPt, MSSAU, SE);
76 return true; // All non-instructions are loop-invariant.
77}
78
79bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
80 Instruction *InsertPt, MemorySSAUpdater *MSSAU,
81 ScalarEvolution *SE) const {
82 // Test if the value is already loop-invariant.
83 if (isLoopInvariant(V: I))
84 return true;
85 if (!isSafeToSpeculativelyExecute(I))
86 return false;
87 if (I->mayReadFromMemory())
88 return false;
89 // EH block instructions are immobile.
90 if (I->isEHPad())
91 return false;
92 // Determine the insertion point, unless one was given.
93 if (!InsertPt) {
94 BasicBlock *Preheader = getLoopPreheader();
95 // Without a preheader, hoisting is not feasible.
96 if (!Preheader)
97 return false;
98 InsertPt = Preheader->getTerminator();
99 }
100 // Don't hoist instructions with loop-variant operands.
101 for (Value *Operand : I->operands())
102 if (!makeLoopInvariant(V: Operand, Changed, InsertPt, MSSAU, SE))
103 return false;
104
105 // Hoist.
106 I->moveBefore(MovePos: InsertPt);
107 if (MSSAU)
108 if (auto *MUD = MSSAU->getMemorySSA()->getMemoryAccess(I))
109 MSSAU->moveToPlace(What: MUD, BB: InsertPt->getParent(),
110 Where: MemorySSA::BeforeTerminator);
111
112 // There is possibility of hoisting this instruction above some arbitrary
113 // condition. Any metadata defined on it can be control dependent on this
114 // condition. Conservatively strip it here so that we don't give any wrong
115 // information to the optimizer.
116 I->dropUnknownNonDebugMetadata();
117
118 if (SE)
119 SE->forgetBlockAndLoopDispositions(V: I);
120
121 Changed = true;
122 return true;
123}
124
125bool Loop::getIncomingAndBackEdge(BasicBlock *&Incoming,
126 BasicBlock *&Backedge) const {
127 BasicBlock *H = getHeader();
128
129 Incoming = nullptr;
130 Backedge = nullptr;
131 pred_iterator PI = pred_begin(BB: H);
132 assert(PI != pred_end(H) && "Loop must have at least one backedge!");
133 Backedge = *PI++;
134 if (PI == pred_end(BB: H))
135 return false; // dead loop
136 Incoming = *PI++;
137 if (PI != pred_end(BB: H))
138 return false; // multiple backedges?
139
140 if (contains(BB: Incoming)) {
141 if (contains(BB: Backedge))
142 return false;
143 std::swap(a&: Incoming, b&: Backedge);
144 } else if (!contains(BB: Backedge))
145 return false;
146
147 assert(Incoming && Backedge && "expected non-null incoming and backedges");
148 return true;
149}
150
151PHINode *Loop::getCanonicalInductionVariable() const {
152 BasicBlock *H = getHeader();
153
154 BasicBlock *Incoming = nullptr, *Backedge = nullptr;
155 if (!getIncomingAndBackEdge(Incoming, Backedge))
156 return nullptr;
157
158 // Loop over all of the PHI nodes, looking for a canonical indvar.
159 for (BasicBlock::iterator I = H->begin(); isa<PHINode>(Val: I); ++I) {
160 PHINode *PN = cast<PHINode>(Val&: I);
161 if (ConstantInt *CI =
162 dyn_cast<ConstantInt>(Val: PN->getIncomingValueForBlock(BB: Incoming)))
163 if (CI->isZero())
164 if (Instruction *Inc =
165 dyn_cast<Instruction>(Val: PN->getIncomingValueForBlock(BB: Backedge)))
166 if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(i: 0) == PN)
167 if (ConstantInt *CI = dyn_cast<ConstantInt>(Val: Inc->getOperand(i: 1)))
168 if (CI->isOne())
169 return PN;
170 }
171 return nullptr;
172}
173
174/// Get the latch condition instruction.
175ICmpInst *Loop::getLatchCmpInst() const {
176 if (BasicBlock *Latch = getLoopLatch())
177 if (BranchInst *BI = dyn_cast_or_null<BranchInst>(Val: Latch->getTerminator()))
178 if (BI->isConditional())
179 return dyn_cast<ICmpInst>(Val: BI->getCondition());
180
181 return nullptr;
182}
183
184/// Return the final value of the loop induction variable if found.
185static Value *findFinalIVValue(const Loop &L, const PHINode &IndVar,
186 const Instruction &StepInst) {
187 ICmpInst *LatchCmpInst = L.getLatchCmpInst();
188 if (!LatchCmpInst)
189 return nullptr;
190
191 Value *Op0 = LatchCmpInst->getOperand(i_nocapture: 0);
192 Value *Op1 = LatchCmpInst->getOperand(i_nocapture: 1);
193 if (Op0 == &IndVar || Op0 == &StepInst)
194 return Op1;
195
196 if (Op1 == &IndVar || Op1 == &StepInst)
197 return Op0;
198
199 return nullptr;
200}
201
202std::optional<Loop::LoopBounds>
203Loop::LoopBounds::getBounds(const Loop &L, PHINode &IndVar,
204 ScalarEvolution &SE) {
205 InductionDescriptor IndDesc;
206 if (!InductionDescriptor::isInductionPHI(Phi: &IndVar, L: &L, SE: &SE, D&: IndDesc))
207 return std::nullopt;
208
209 Value *InitialIVValue = IndDesc.getStartValue();
210 Instruction *StepInst = IndDesc.getInductionBinOp();
211 if (!InitialIVValue || !StepInst)
212 return std::nullopt;
213
214 const SCEV *Step = IndDesc.getStep();
215 Value *StepInstOp1 = StepInst->getOperand(i: 1);
216 Value *StepInstOp0 = StepInst->getOperand(i: 0);
217 Value *StepValue = nullptr;
218 if (SE.getSCEV(V: StepInstOp1) == Step)
219 StepValue = StepInstOp1;
220 else if (SE.getSCEV(V: StepInstOp0) == Step)
221 StepValue = StepInstOp0;
222
223 Value *FinalIVValue = findFinalIVValue(L, IndVar, StepInst: *StepInst);
224 if (!FinalIVValue)
225 return std::nullopt;
226
227 return LoopBounds(L, *InitialIVValue, *StepInst, StepValue, *FinalIVValue,
228 SE);
229}
230
231using Direction = Loop::LoopBounds::Direction;
232
233ICmpInst::Predicate Loop::LoopBounds::getCanonicalPredicate() const {
234 BasicBlock *Latch = L.getLoopLatch();
235 assert(Latch && "Expecting valid latch");
236
237 BranchInst *BI = dyn_cast_or_null<BranchInst>(Val: Latch->getTerminator());
238 assert(BI && BI->isConditional() && "Expecting conditional latch branch");
239
240 ICmpInst *LatchCmpInst = dyn_cast<ICmpInst>(Val: BI->getCondition());
241 assert(LatchCmpInst &&
242 "Expecting the latch compare instruction to be a CmpInst");
243
244 // Need to inverse the predicate when first successor is not the loop
245 // header
246 ICmpInst::Predicate Pred = (BI->getSuccessor(i: 0) == L.getHeader())
247 ? LatchCmpInst->getPredicate()
248 : LatchCmpInst->getInversePredicate();
249
250 if (LatchCmpInst->getOperand(i_nocapture: 0) == &getFinalIVValue())
251 Pred = ICmpInst::getSwappedPredicate(pred: Pred);
252
253 // Need to flip strictness of the predicate when the latch compare instruction
254 // is not using StepInst
255 if (LatchCmpInst->getOperand(i_nocapture: 0) == &getStepInst() ||
256 LatchCmpInst->getOperand(i_nocapture: 1) == &getStepInst())
257 return Pred;
258
259 // Cannot flip strictness of NE and EQ
260 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
261 return ICmpInst::getFlippedStrictnessPredicate(pred: Pred);
262
263 Direction D = getDirection();
264 if (D == Direction::Increasing)
265 return ICmpInst::ICMP_SLT;
266
267 if (D == Direction::Decreasing)
268 return ICmpInst::ICMP_SGT;
269
270 // If cannot determine the direction, then unable to find the canonical
271 // predicate
272 return ICmpInst::BAD_ICMP_PREDICATE;
273}
274
275Direction Loop::LoopBounds::getDirection() const {
276 if (const SCEVAddRecExpr *StepAddRecExpr =
277 dyn_cast<SCEVAddRecExpr>(Val: SE.getSCEV(V: &getStepInst())))
278 if (const SCEV *StepRecur = StepAddRecExpr->getStepRecurrence(SE)) {
279 if (SE.isKnownPositive(S: StepRecur))
280 return Direction::Increasing;
281 if (SE.isKnownNegative(S: StepRecur))
282 return Direction::Decreasing;
283 }
284
285 return Direction::Unknown;
286}
287
288std::optional<Loop::LoopBounds> Loop::getBounds(ScalarEvolution &SE) const {
289 if (PHINode *IndVar = getInductionVariable(SE))
290 return LoopBounds::getBounds(L: *this, IndVar&: *IndVar, SE);
291
292 return std::nullopt;
293}
294
295PHINode *Loop::getInductionVariable(ScalarEvolution &SE) const {
296 if (!isLoopSimplifyForm())
297 return nullptr;
298
299 BasicBlock *Header = getHeader();
300 assert(Header && "Expected a valid loop header");
301 ICmpInst *CmpInst = getLatchCmpInst();
302 if (!CmpInst)
303 return nullptr;
304
305 Value *LatchCmpOp0 = CmpInst->getOperand(i_nocapture: 0);
306 Value *LatchCmpOp1 = CmpInst->getOperand(i_nocapture: 1);
307
308 for (PHINode &IndVar : Header->phis()) {
309 InductionDescriptor IndDesc;
310 if (!InductionDescriptor::isInductionPHI(Phi: &IndVar, L: this, SE: &SE, D&: IndDesc))
311 continue;
312
313 BasicBlock *Latch = getLoopLatch();
314 Value *StepInst = IndVar.getIncomingValueForBlock(BB: Latch);
315
316 // case 1:
317 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
318 // StepInst = IndVar + step
319 // cmp = StepInst < FinalValue
320 if (StepInst == LatchCmpOp0 || StepInst == LatchCmpOp1)
321 return &IndVar;
322
323 // case 2:
324 // IndVar = phi[{InitialValue, preheader}, {StepInst, latch}]
325 // StepInst = IndVar + step
326 // cmp = IndVar < FinalValue
327 if (&IndVar == LatchCmpOp0 || &IndVar == LatchCmpOp1)
328 return &IndVar;
329 }
330
331 return nullptr;
332}
333
334bool Loop::getInductionDescriptor(ScalarEvolution &SE,
335 InductionDescriptor &IndDesc) const {
336 if (PHINode *IndVar = getInductionVariable(SE))
337 return InductionDescriptor::isInductionPHI(Phi: IndVar, L: this, SE: &SE, D&: IndDesc);
338
339 return false;
340}
341
342bool Loop::isAuxiliaryInductionVariable(PHINode &AuxIndVar,
343 ScalarEvolution &SE) const {
344 // Located in the loop header
345 BasicBlock *Header = getHeader();
346 if (AuxIndVar.getParent() != Header)
347 return false;
348
349 // No uses outside of the loop
350 for (User *U : AuxIndVar.users())
351 if (const Instruction *I = dyn_cast<Instruction>(Val: U))
352 if (!contains(Inst: I))
353 return false;
354
355 InductionDescriptor IndDesc;
356 if (!InductionDescriptor::isInductionPHI(Phi: &AuxIndVar, L: this, SE: &SE, D&: IndDesc))
357 return false;
358
359 // The step instruction opcode should be add or sub.
360 if (IndDesc.getInductionOpcode() != Instruction::Add &&
361 IndDesc.getInductionOpcode() != Instruction::Sub)
362 return false;
363
364 // Incremented by a loop invariant step for each loop iteration
365 return SE.isLoopInvariant(S: IndDesc.getStep(), L: this);
366}
367
368BranchInst *Loop::getLoopGuardBranch() const {
369 if (!isLoopSimplifyForm())
370 return nullptr;
371
372 BasicBlock *Preheader = getLoopPreheader();
373 assert(Preheader && getLoopLatch() &&
374 "Expecting a loop with valid preheader and latch");
375
376 // Loop should be in rotate form.
377 if (!isRotatedForm())
378 return nullptr;
379
380 // Disallow loops with more than one unique exit block, as we do not verify
381 // that GuardOtherSucc post dominates all exit blocks.
382 BasicBlock *ExitFromLatch = getUniqueExitBlock();
383 if (!ExitFromLatch)
384 return nullptr;
385
386 BasicBlock *GuardBB = Preheader->getUniquePredecessor();
387 if (!GuardBB)
388 return nullptr;
389
390 assert(GuardBB->getTerminator() && "Expecting valid guard terminator");
391
392 BranchInst *GuardBI = dyn_cast<BranchInst>(Val: GuardBB->getTerminator());
393 if (!GuardBI || GuardBI->isUnconditional())
394 return nullptr;
395
396 BasicBlock *GuardOtherSucc = (GuardBI->getSuccessor(i: 0) == Preheader)
397 ? GuardBI->getSuccessor(i: 1)
398 : GuardBI->getSuccessor(i: 0);
399
400 // Check if ExitFromLatch (or any BasicBlock which is an empty unique
401 // successor of ExitFromLatch) is equal to GuardOtherSucc. If
402 // skipEmptyBlockUntil returns GuardOtherSucc, then the guard branch for the
403 // loop is GuardBI (return GuardBI), otherwise return nullptr.
404 if (&LoopNest::skipEmptyBlockUntil(From: ExitFromLatch, End: GuardOtherSucc,
405 /*CheckUniquePred=*/true) ==
406 GuardOtherSucc)
407 return GuardBI;
408 else
409 return nullptr;
410}
411
412bool Loop::isCanonical(ScalarEvolution &SE) const {
413 InductionDescriptor IndDesc;
414 if (!getInductionDescriptor(SE, IndDesc))
415 return false;
416
417 ConstantInt *Init = dyn_cast_or_null<ConstantInt>(Val: IndDesc.getStartValue());
418 if (!Init || !Init->isZero())
419 return false;
420
421 if (IndDesc.getInductionOpcode() != Instruction::Add)
422 return false;
423
424 ConstantInt *Step = IndDesc.getConstIntStepValue();
425 if (!Step || !Step->isOne())
426 return false;
427
428 return true;
429}
430
431// Check that 'BB' doesn't have any uses outside of the 'L'
432static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
433 const DominatorTree &DT, bool IgnoreTokens) {
434 for (const Instruction &I : BB) {
435 // Tokens can't be used in PHI nodes and live-out tokens prevent loop
436 // optimizations, so for the purposes of considered LCSSA form, we
437 // can ignore them.
438 if (IgnoreTokens && I.getType()->isTokenTy())
439 continue;
440
441 for (const Use &U : I.uses()) {
442 const Instruction *UI = cast<Instruction>(Val: U.getUser());
443 const BasicBlock *UserBB = UI->getParent();
444
445 // For practical purposes, we consider that the use in a PHI
446 // occurs in the respective predecessor block. For more info,
447 // see the `phi` doc in LangRef and the LCSSA doc.
448 if (const PHINode *P = dyn_cast<PHINode>(Val: UI))
449 UserBB = P->getIncomingBlock(U);
450
451 // Check the current block, as a fast-path, before checking whether
452 // the use is anywhere in the loop. Most values are used in the same
453 // block they are defined in. Also, blocks not reachable from the
454 // entry are special; uses in them don't need to go through PHIs.
455 if (UserBB != &BB && !L.contains(BB: UserBB) &&
456 DT.isReachableFromEntry(A: UserBB))
457 return false;
458 }
459 }
460 return true;
461}
462
463bool Loop::isLCSSAForm(const DominatorTree &DT, bool IgnoreTokens) const {
464 // For each block we check that it doesn't have any uses outside of this loop.
465 return all_of(Range: this->blocks(), P: [&](const BasicBlock *BB) {
466 return isBlockInLCSSAForm(L: *this, BB: *BB, DT, IgnoreTokens);
467 });
468}
469
470bool Loop::isRecursivelyLCSSAForm(const DominatorTree &DT, const LoopInfo &LI,
471 bool IgnoreTokens) const {
472 // For each block we check that it doesn't have any uses outside of its
473 // innermost loop. This process will transitively guarantee that the current
474 // loop and all of the nested loops are in LCSSA form.
475 return all_of(Range: this->blocks(), P: [&](const BasicBlock *BB) {
476 return isBlockInLCSSAForm(L: *LI.getLoopFor(BB), BB: *BB, DT, IgnoreTokens);
477 });
478}
479
480bool Loop::isLoopSimplifyForm() const {
481 // Normal-form loops have a preheader, a single backedge, and all of their
482 // exits have all their predecessors inside the loop.
483 return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
484}
485
486// Routines that reform the loop CFG and split edges often fail on indirectbr.
487bool Loop::isSafeToClone() const {
488 // Return false if any loop blocks contain indirectbrs, or there are any calls
489 // to noduplicate functions.
490 for (BasicBlock *BB : this->blocks()) {
491 if (isa<IndirectBrInst>(Val: BB->getTerminator()))
492 return false;
493
494 for (Instruction &I : *BB)
495 if (auto *CB = dyn_cast<CallBase>(Val: &I))
496 if (CB->cannotDuplicate())
497 return false;
498 }
499 return true;
500}
501
502MDNode *Loop::getLoopID() const {
503 MDNode *LoopID = nullptr;
504
505 // Go through the latch blocks and check the terminator for the metadata.
506 SmallVector<BasicBlock *, 4> LatchesBlocks;
507 getLoopLatches(LoopLatches&: LatchesBlocks);
508 for (BasicBlock *BB : LatchesBlocks) {
509 Instruction *TI = BB->getTerminator();
510 MDNode *MD = TI->getMetadata(KindID: LLVMContext::MD_loop);
511
512 if (!MD)
513 return nullptr;
514
515 if (!LoopID)
516 LoopID = MD;
517 else if (MD != LoopID)
518 return nullptr;
519 }
520 if (!LoopID || LoopID->getNumOperands() == 0 ||
521 LoopID->getOperand(I: 0) != LoopID)
522 return nullptr;
523 return LoopID;
524}
525
526void Loop::setLoopID(MDNode *LoopID) const {
527 assert((!LoopID || LoopID->getNumOperands() > 0) &&
528 "Loop ID needs at least one operand");
529 assert((!LoopID || LoopID->getOperand(0) == LoopID) &&
530 "Loop ID should refer to itself");
531
532 SmallVector<BasicBlock *, 4> LoopLatches;
533 getLoopLatches(LoopLatches);
534 for (BasicBlock *BB : LoopLatches)
535 BB->getTerminator()->setMetadata(KindID: LLVMContext::MD_loop, Node: LoopID);
536}
537
538void Loop::setLoopAlreadyUnrolled() {
539 LLVMContext &Context = getHeader()->getContext();
540
541 MDNode *DisableUnrollMD =
542 MDNode::get(Context, MDs: MDString::get(Context, Str: "llvm.loop.unroll.disable"));
543 MDNode *LoopID = getLoopID();
544 MDNode *NewLoopID = makePostTransformationMetadata(
545 Context, OrigLoopID: LoopID, RemovePrefixes: {"llvm.loop.unroll."}, AddAttrs: {DisableUnrollMD});
546 setLoopID(NewLoopID);
547}
548
549void Loop::setLoopMustProgress() {
550 LLVMContext &Context = getHeader()->getContext();
551
552 MDNode *MustProgress = findOptionMDForLoop(TheLoop: this, Name: "llvm.loop.mustprogress");
553
554 if (MustProgress)
555 return;
556
557 MDNode *MustProgressMD =
558 MDNode::get(Context, MDs: MDString::get(Context, Str: "llvm.loop.mustprogress"));
559 MDNode *LoopID = getLoopID();
560 MDNode *NewLoopID =
561 makePostTransformationMetadata(Context, OrigLoopID: LoopID, RemovePrefixes: {}, AddAttrs: {MustProgressMD});
562 setLoopID(NewLoopID);
563}
564
565bool Loop::isAnnotatedParallel() const {
566 MDNode *DesiredLoopIdMetadata = getLoopID();
567
568 if (!DesiredLoopIdMetadata)
569 return false;
570
571 MDNode *ParallelAccesses =
572 findOptionMDForLoop(TheLoop: this, Name: "llvm.loop.parallel_accesses");
573 SmallPtrSet<MDNode *, 4>
574 ParallelAccessGroups; // For scalable 'contains' check.
575 if (ParallelAccesses) {
576 for (const MDOperand &MD : drop_begin(RangeOrContainer: ParallelAccesses->operands())) {
577 MDNode *AccGroup = cast<MDNode>(Val: MD.get());
578 assert(isValidAsAccessGroup(AccGroup) &&
579 "List item must be an access group");
580 ParallelAccessGroups.insert(Ptr: AccGroup);
581 }
582 }
583
584 // The loop branch contains the parallel loop metadata. In order to ensure
585 // that any parallel-loop-unaware optimization pass hasn't added loop-carried
586 // dependencies (thus converted the loop back to a sequential loop), check
587 // that all the memory instructions in the loop belong to an access group that
588 // is parallel to this loop.
589 for (BasicBlock *BB : this->blocks()) {
590 for (Instruction &I : *BB) {
591 if (!I.mayReadOrWriteMemory())
592 continue;
593
594 if (MDNode *AccessGroup = I.getMetadata(KindID: LLVMContext::MD_access_group)) {
595 auto ContainsAccessGroup = [&ParallelAccessGroups](MDNode *AG) -> bool {
596 if (AG->getNumOperands() == 0) {
597 assert(isValidAsAccessGroup(AG) && "Item must be an access group");
598 return ParallelAccessGroups.count(Ptr: AG);
599 }
600
601 for (const MDOperand &AccessListItem : AG->operands()) {
602 MDNode *AccGroup = cast<MDNode>(Val: AccessListItem.get());
603 assert(isValidAsAccessGroup(AccGroup) &&
604 "List item must be an access group");
605 if (ParallelAccessGroups.count(Ptr: AccGroup))
606 return true;
607 }
608 return false;
609 };
610
611 if (ContainsAccessGroup(AccessGroup))
612 continue;
613 }
614
615 // The memory instruction can refer to the loop identifier metadata
616 // directly or indirectly through another list metadata (in case of
617 // nested parallel loops). The loop identifier metadata refers to
618 // itself so we can check both cases with the same routine.
619 MDNode *LoopIdMD =
620 I.getMetadata(KindID: LLVMContext::MD_mem_parallel_loop_access);
621
622 if (!LoopIdMD)
623 return false;
624
625 if (!llvm::is_contained(Range: LoopIdMD->operands(), Element: DesiredLoopIdMetadata))
626 return false;
627 }
628 }
629 return true;
630}
631
632DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
633
634Loop::LocRange Loop::getLocRange() const {
635 // If we have a debug location in the loop ID, then use it.
636 if (MDNode *LoopID = getLoopID()) {
637 DebugLoc Start;
638 // We use the first DebugLoc in the header as the start location of the loop
639 // and if there is a second DebugLoc in the header we use it as end location
640 // of the loop.
641 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
642 if (DILocation *L = dyn_cast<DILocation>(Val: MDO)) {
643 if (!Start)
644 Start = DebugLoc(L);
645 else
646 return LocRange(Start, DebugLoc(L));
647 }
648 }
649
650 if (Start)
651 return LocRange(Start);
652 }
653
654 // Try the pre-header first.
655 if (BasicBlock *PHeadBB = getLoopPreheader())
656 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
657 return LocRange(DL);
658
659 // If we have no pre-header or there are no instructions with debug
660 // info in it, try the header.
661 if (BasicBlock *HeadBB = getHeader())
662 return LocRange(HeadBB->getTerminator()->getDebugLoc());
663
664 return LocRange();
665}
666
667std::string Loop::getLocStr() const {
668 std::string Result;
669 raw_string_ostream OS(Result);
670 if (const DebugLoc LoopDbgLoc = getStartLoc())
671 LoopDbgLoc.print(OS);
672 else
673 // Just print the module name.
674 OS << getHeader()->getParent()->getParent()->getModuleIdentifier();
675 return Result;
676}
677
678#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
679LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
680
681LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
682 print(dbgs(), /*Verbose=*/true);
683}
684#endif
685
686//===----------------------------------------------------------------------===//
687// UnloopUpdater implementation
688//
689
690namespace {
691/// Find the new parent loop for all blocks within the "unloop" whose last
692/// backedges has just been removed.
693class UnloopUpdater {
694 Loop &Unloop;
695 LoopInfo *LI;
696
697 LoopBlocksDFS DFS;
698
699 // Map unloop's immediate subloops to their nearest reachable parents. Nested
700 // loops within these subloops will not change parents. However, an immediate
701 // subloop's new parent will be the nearest loop reachable from either its own
702 // exits *or* any of its nested loop's exits.
703 DenseMap<Loop *, Loop *> SubloopParents;
704
705 // Flag the presence of an irreducible backedge whose destination is a block
706 // directly contained by the original unloop.
707 bool FoundIB = false;
708
709public:
710 UnloopUpdater(Loop *UL, LoopInfo *LInfo) : Unloop(*UL), LI(LInfo), DFS(UL) {}
711
712 void updateBlockParents();
713
714 void removeBlocksFromAncestors();
715
716 void updateSubloopParents();
717
718protected:
719 Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
720};
721} // end anonymous namespace
722
723/// Update the parent loop for all blocks that are directly contained within the
724/// original "unloop".
725void UnloopUpdater::updateBlockParents() {
726 if (Unloop.getNumBlocks()) {
727 // Perform a post order CFG traversal of all blocks within this loop,
728 // propagating the nearest loop from successors to predecessors.
729 LoopBlocksTraversal Traversal(DFS, LI);
730 for (BasicBlock *POI : Traversal) {
731
732 Loop *L = LI->getLoopFor(BB: POI);
733 Loop *NL = getNearestLoop(BB: POI, BBLoop: L);
734
735 if (NL != L) {
736 // For reducible loops, NL is now an ancestor of Unloop.
737 assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
738 "uninitialized successor");
739 LI->changeLoopFor(BB: POI, L: NL);
740 } else {
741 // Or the current block is part of a subloop, in which case its parent
742 // is unchanged.
743 assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
744 }
745 }
746 }
747 // Each irreducible loop within the unloop induces a round of iteration using
748 // the DFS result cached by Traversal.
749 bool Changed = FoundIB;
750 for (unsigned NIters = 0; Changed; ++NIters) {
751 assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
752 (void)NIters;
753
754 // Iterate over the postorder list of blocks, propagating the nearest loop
755 // from successors to predecessors as before.
756 Changed = false;
757 for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
758 POE = DFS.endPostorder();
759 POI != POE; ++POI) {
760
761 Loop *L = LI->getLoopFor(BB: *POI);
762 Loop *NL = getNearestLoop(BB: *POI, BBLoop: L);
763 if (NL != L) {
764 assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
765 "uninitialized successor");
766 LI->changeLoopFor(BB: *POI, L: NL);
767 Changed = true;
768 }
769 }
770 }
771}
772
773/// Remove unloop's blocks from all ancestors below their new parents.
774void UnloopUpdater::removeBlocksFromAncestors() {
775 // Remove all unloop's blocks (including those in nested subloops) from
776 // ancestors below the new parent loop.
777 for (BasicBlock *BB : Unloop.blocks()) {
778 Loop *OuterParent = LI->getLoopFor(BB);
779 if (Unloop.contains(L: OuterParent)) {
780 while (OuterParent->getParentLoop() != &Unloop)
781 OuterParent = OuterParent->getParentLoop();
782 OuterParent = SubloopParents[OuterParent];
783 }
784 // Remove blocks from former Ancestors except Unloop itself which will be
785 // deleted.
786 for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
787 OldParent = OldParent->getParentLoop()) {
788 assert(OldParent && "new loop is not an ancestor of the original");
789 OldParent->removeBlockFromLoop(BB);
790 }
791 }
792}
793
794/// Update the parent loop for all subloops directly nested within unloop.
795void UnloopUpdater::updateSubloopParents() {
796 while (!Unloop.isInnermost()) {
797 Loop *Subloop = *std::prev(x: Unloop.end());
798 Unloop.removeChildLoop(I: std::prev(x: Unloop.end()));
799
800 assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
801 if (Loop *Parent = SubloopParents[Subloop])
802 Parent->addChildLoop(NewChild: Subloop);
803 else
804 LI->addTopLevelLoop(New: Subloop);
805 }
806}
807
808/// Return the nearest parent loop among this block's successors. If a successor
809/// is a subloop header, consider its parent to be the nearest parent of the
810/// subloop's exits.
811///
812/// For subloop blocks, simply update SubloopParents and return NULL.
813Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
814
815 // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
816 // is considered uninitialized.
817 Loop *NearLoop = BBLoop;
818
819 Loop *Subloop = nullptr;
820 if (NearLoop != &Unloop && Unloop.contains(L: NearLoop)) {
821 Subloop = NearLoop;
822 // Find the subloop ancestor that is directly contained within Unloop.
823 while (Subloop->getParentLoop() != &Unloop) {
824 Subloop = Subloop->getParentLoop();
825 assert(Subloop && "subloop is not an ancestor of the original loop");
826 }
827 // Get the current nearest parent of the Subloop exits, initially Unloop.
828 NearLoop = SubloopParents.insert(KV: {Subloop, &Unloop}).first->second;
829 }
830
831 if (succ_empty(BB)) {
832 assert(!Subloop && "subloop blocks must have a successor");
833 NearLoop = nullptr; // unloop blocks may now exit the function.
834 }
835 for (BasicBlock *Succ : successors(BB)) {
836 if (Succ == BB)
837 continue; // self loops are uninteresting
838
839 Loop *L = LI->getLoopFor(BB: Succ);
840 if (L == &Unloop) {
841 // This successor has not been processed. This path must lead to an
842 // irreducible backedge.
843 assert((FoundIB || !DFS.hasPostorder(Succ)) && "should have seen IB");
844 FoundIB = true;
845 }
846 if (L != &Unloop && Unloop.contains(L)) {
847 // Successor is in a subloop.
848 if (Subloop)
849 continue; // Branching within subloops. Ignore it.
850
851 // BB branches from the original into a subloop header.
852 assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
853
854 // Get the current nearest parent of the Subloop's exits.
855 L = SubloopParents[L];
856 // L could be Unloop if the only exit was an irreducible backedge.
857 }
858 if (L == &Unloop) {
859 continue;
860 }
861 // Handle critical edges from Unloop into a sibling loop.
862 if (L && !L->contains(L: &Unloop)) {
863 L = L->getParentLoop();
864 }
865 // Remember the nearest parent loop among successors or subloop exits.
866 if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
867 NearLoop = L;
868 }
869 if (Subloop) {
870 SubloopParents[Subloop] = NearLoop;
871 return BBLoop;
872 }
873 return NearLoop;
874}
875
876LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
877
878bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
879 FunctionAnalysisManager::Invalidator &) {
880 // Check whether the analysis, all analyses on functions, or the function's
881 // CFG have been preserved.
882 auto PAC = PA.getChecker<LoopAnalysis>();
883 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
884 PAC.preservedSet<CFGAnalyses>());
885}
886
887void LoopInfo::erase(Loop *Unloop) {
888 assert(!Unloop->isInvalid() && "Loop has already been erased!");
889
890 auto InvalidateOnExit = make_scope_exit(F: [&]() { destroy(L: Unloop); });
891
892 // First handle the special case of no parent loop to simplify the algorithm.
893 if (Unloop->isOutermost()) {
894 // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
895 for (BasicBlock *BB : Unloop->blocks()) {
896 // Don't reparent blocks in subloops.
897 if (getLoopFor(BB) != Unloop)
898 continue;
899
900 // Blocks no longer have a parent but are still referenced by Unloop until
901 // the Unloop object is deleted.
902 changeLoopFor(BB, L: nullptr);
903 }
904
905 // Remove the loop from the top-level LoopInfo object.
906 for (iterator I = begin();; ++I) {
907 assert(I != end() && "Couldn't find loop");
908 if (*I == Unloop) {
909 removeLoop(I);
910 break;
911 }
912 }
913
914 // Move all of the subloops to the top-level.
915 while (!Unloop->isInnermost())
916 addTopLevelLoop(New: Unloop->removeChildLoop(I: std::prev(x: Unloop->end())));
917
918 return;
919 }
920
921 // Update the parent loop for all blocks within the loop. Blocks within
922 // subloops will not change parents.
923 UnloopUpdater Updater(Unloop, this);
924 Updater.updateBlockParents();
925
926 // Remove blocks from former ancestor loops.
927 Updater.removeBlocksFromAncestors();
928
929 // Add direct subloops as children in their new parent loop.
930 Updater.updateSubloopParents();
931
932 // Remove unloop from its parent loop.
933 Loop *ParentLoop = Unloop->getParentLoop();
934 for (Loop::iterator I = ParentLoop->begin();; ++I) {
935 assert(I != ParentLoop->end() && "Couldn't find loop");
936 if (*I == Unloop) {
937 ParentLoop->removeChildLoop(I);
938 break;
939 }
940 }
941}
942
943bool LoopInfo::wouldBeOutOfLoopUseRequiringLCSSA(
944 const Value *V, const BasicBlock *ExitBB) const {
945 if (V->getType()->isTokenTy())
946 // We can't form PHIs of token type, so the definition of LCSSA excludes
947 // values of that type.
948 return false;
949
950 const Instruction *I = dyn_cast<Instruction>(Val: V);
951 if (!I)
952 return false;
953 const Loop *L = getLoopFor(BB: I->getParent());
954 if (!L)
955 return false;
956 if (L->contains(BB: ExitBB))
957 // Could be an exit bb of a subloop and contained in defining loop
958 return false;
959
960 // We found a (new) out-of-loop use location, for a value defined in-loop.
961 // (Note that because of LCSSA, we don't have to account for values defined
962 // in sibling loops. Such values will have LCSSA phis of their own in the
963 // common parent loop.)
964 return true;
965}
966
967AnalysisKey LoopAnalysis::Key;
968
969LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
970 // FIXME: Currently we create a LoopInfo from scratch for every function.
971 // This may prove to be too wasteful due to deallocating and re-allocating
972 // memory each time for the underlying map and vector datastructures. At some
973 // point it may prove worthwhile to use a freelist and recycle LoopInfo
974 // objects. I don't want to add that kind of complexity until the scope of
975 // the problem is better understood.
976 LoopInfo LI;
977 LI.analyze(DomTree: AM.getResult<DominatorTreeAnalysis>(IR&: F));
978 return LI;
979}
980
981PreservedAnalyses LoopPrinterPass::run(Function &F,
982 FunctionAnalysisManager &AM) {
983 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
984 OS << "Loop info for function '" << F.getName() << "':\n";
985 LI.print(OS);
986 return PreservedAnalyses::all();
987}
988
989void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
990
991 if (forcePrintModuleIR()) {
992 // handling -print-module-scope
993 OS << Banner << " (loop: ";
994 L.getHeader()->printAsOperand(O&: OS, PrintType: false);
995 OS << ")\n";
996
997 // printing whole module
998 OS << *L.getHeader()->getModule();
999 return;
1000 }
1001
1002 OS << Banner;
1003
1004 auto *PreHeader = L.getLoopPreheader();
1005 if (PreHeader) {
1006 OS << "\n; Preheader:";
1007 PreHeader->print(OS);
1008 OS << "\n; Loop:";
1009 }
1010
1011 for (auto *Block : L.blocks())
1012 if (Block)
1013 Block->print(OS);
1014 else
1015 OS << "Printing <null> block";
1016
1017 SmallVector<BasicBlock *, 8> ExitBlocks;
1018 L.getExitBlocks(ExitBlocks);
1019 if (!ExitBlocks.empty()) {
1020 OS << "\n; Exit blocks";
1021 for (auto *Block : ExitBlocks)
1022 if (Block)
1023 Block->print(OS);
1024 else
1025 OS << "Printing <null> block";
1026 }
1027}
1028
1029MDNode *llvm::findOptionMDForLoopID(MDNode *LoopID, StringRef Name) {
1030 // No loop metadata node, no loop properties.
1031 if (!LoopID)
1032 return nullptr;
1033
1034 // First operand should refer to the metadata node itself, for legacy reasons.
1035 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
1036 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
1037
1038 // Iterate over the metdata node operands and look for MDString metadata.
1039 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
1040 MDNode *MD = dyn_cast<MDNode>(Val: MDO);
1041 if (!MD || MD->getNumOperands() < 1)
1042 continue;
1043 MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
1044 if (!S)
1045 continue;
1046 // Return the operand node if MDString holds expected metadata.
1047 if (Name == S->getString())
1048 return MD;
1049 }
1050
1051 // Loop property not found.
1052 return nullptr;
1053}
1054
1055MDNode *llvm::findOptionMDForLoop(const Loop *TheLoop, StringRef Name) {
1056 return findOptionMDForLoopID(LoopID: TheLoop->getLoopID(), Name);
1057}
1058
1059/// Find string metadata for loop
1060///
1061/// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
1062/// operand or null otherwise. If the string metadata is not found return
1063/// Optional's not-a-value.
1064std::optional<const MDOperand *>
1065llvm::findStringMetadataForLoop(const Loop *TheLoop, StringRef Name) {
1066 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1067 if (!MD)
1068 return std::nullopt;
1069 switch (MD->getNumOperands()) {
1070 case 1:
1071 return nullptr;
1072 case 2:
1073 return &MD->getOperand(I: 1);
1074 default:
1075 llvm_unreachable("loop metadata has 0 or 1 operand");
1076 }
1077}
1078
1079std::optional<bool> llvm::getOptionalBoolLoopAttribute(const Loop *TheLoop,
1080 StringRef Name) {
1081 MDNode *MD = findOptionMDForLoop(TheLoop, Name);
1082 if (!MD)
1083 return std::nullopt;
1084 switch (MD->getNumOperands()) {
1085 case 1:
1086 // When the value is absent it is interpreted as 'attribute set'.
1087 return true;
1088 case 2:
1089 if (ConstantInt *IntMD =
1090 mdconst::extract_or_null<ConstantInt>(MD: MD->getOperand(I: 1).get()))
1091 return IntMD->getZExtValue();
1092 return true;
1093 }
1094 llvm_unreachable("unexpected number of options");
1095}
1096
1097bool llvm::getBooleanLoopAttribute(const Loop *TheLoop, StringRef Name) {
1098 return getOptionalBoolLoopAttribute(TheLoop, Name).value_or(u: false);
1099}
1100
1101std::optional<int> llvm::getOptionalIntLoopAttribute(const Loop *TheLoop,
1102 StringRef Name) {
1103 const MDOperand *AttrMD =
1104 findStringMetadataForLoop(TheLoop, Name).value_or(u: nullptr);
1105 if (!AttrMD)
1106 return std::nullopt;
1107
1108 ConstantInt *IntMD = mdconst::extract_or_null<ConstantInt>(MD: AttrMD->get());
1109 if (!IntMD)
1110 return std::nullopt;
1111
1112 return IntMD->getSExtValue();
1113}
1114
1115int llvm::getIntLoopAttribute(const Loop *TheLoop, StringRef Name,
1116 int Default) {
1117 return getOptionalIntLoopAttribute(TheLoop, Name).value_or(u&: Default);
1118}
1119
1120CallBase *llvm::getLoopConvergenceHeart(const Loop *TheLoop) {
1121 BasicBlock *H = TheLoop->getHeader();
1122 for (Instruction &II : *H) {
1123 if (auto *CB = dyn_cast<CallBase>(Val: &II)) {
1124 if (!CB->isConvergent())
1125 continue;
1126 // This is the heart if it uses a token defined outside the loop. The
1127 // verifier has already checked that only the loop intrinsic can use such
1128 // a token.
1129 if (auto *Token = CB->getConvergenceControlToken()) {
1130 auto *TokenDef = cast<Instruction>(Val: Token);
1131 if (!TheLoop->contains(BB: TokenDef->getParent()))
1132 return CB;
1133 }
1134 return nullptr;
1135 }
1136 }
1137 return nullptr;
1138}
1139
1140bool llvm::isFinite(const Loop *L) {
1141 return L->getHeader()->getParent()->willReturn();
1142}
1143
1144static const char *LLVMLoopMustProgress = "llvm.loop.mustprogress";
1145
1146bool llvm::hasMustProgress(const Loop *L) {
1147 return getBooleanLoopAttribute(TheLoop: L, Name: LLVMLoopMustProgress);
1148}
1149
1150bool llvm::isMustProgress(const Loop *L) {
1151 return L->getHeader()->getParent()->mustProgress() || hasMustProgress(L);
1152}
1153
1154bool llvm::isValidAsAccessGroup(MDNode *Node) {
1155 return Node->getNumOperands() == 0 && Node->isDistinct();
1156}
1157
1158MDNode *llvm::makePostTransformationMetadata(LLVMContext &Context,
1159 MDNode *OrigLoopID,
1160 ArrayRef<StringRef> RemovePrefixes,
1161 ArrayRef<MDNode *> AddAttrs) {
1162 // First remove any existing loop metadata related to this transformation.
1163 SmallVector<Metadata *, 4> MDs;
1164
1165 // Reserve first location for self reference to the LoopID metadata node.
1166 MDs.push_back(Elt: nullptr);
1167
1168 // Remove metadata for the transformation that has been applied or that became
1169 // outdated.
1170 if (OrigLoopID) {
1171 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: OrigLoopID->operands())) {
1172 bool IsVectorMetadata = false;
1173 Metadata *Op = MDO;
1174 if (MDNode *MD = dyn_cast<MDNode>(Val: Op)) {
1175 const MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
1176 if (S)
1177 IsVectorMetadata =
1178 llvm::any_of(Range&: RemovePrefixes, P: [S](StringRef Prefix) -> bool {
1179 return S->getString().starts_with(Prefix);
1180 });
1181 }
1182 if (!IsVectorMetadata)
1183 MDs.push_back(Elt: Op);
1184 }
1185 }
1186
1187 // Add metadata to avoid reapplying a transformation, such as
1188 // llvm.loop.unroll.disable and llvm.loop.isvectorized.
1189 MDs.append(in_start: AddAttrs.begin(), in_end: AddAttrs.end());
1190
1191 MDNode *NewLoopID = MDNode::getDistinct(Context, MDs);
1192 // Replace the temporary node with a self-reference.
1193 NewLoopID->replaceOperandWith(I: 0, New: NewLoopID);
1194 return NewLoopID;
1195}
1196
1197//===----------------------------------------------------------------------===//
1198// LoopInfo implementation
1199//
1200
1201LoopInfoWrapperPass::LoopInfoWrapperPass() : FunctionPass(ID) {
1202 initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
1203}
1204
1205char LoopInfoWrapperPass::ID = 0;
1206INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1207 true, true)
1208INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1209INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
1210 true, true)
1211
1212bool LoopInfoWrapperPass::runOnFunction(Function &) {
1213 releaseMemory();
1214 LI.analyze(DomTree: getAnalysis<DominatorTreeWrapperPass>().getDomTree());
1215 return false;
1216}
1217
1218void LoopInfoWrapperPass::verifyAnalysis() const {
1219 // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
1220 // function each time verifyAnalysis is called is very expensive. The
1221 // -verify-loop-info option can enable this. In order to perform some
1222 // checking by default, LoopPass has been taught to call verifyLoop manually
1223 // during loop pass sequences.
1224 if (VerifyLoopInfo) {
1225 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1226 LI.verify(DomTree: DT);
1227 }
1228}
1229
1230void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1231 AU.setPreservesAll();
1232 AU.addRequiredTransitive<DominatorTreeWrapperPass>();
1233}
1234
1235void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
1236 LI.print(OS);
1237}
1238
1239PreservedAnalyses LoopVerifierPass::run(Function &F,
1240 FunctionAnalysisManager &AM) {
1241 LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F);
1242 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
1243 LI.verify(DomTree: DT);
1244 return PreservedAnalyses::all();
1245}
1246
1247//===----------------------------------------------------------------------===//
1248// LoopBlocksDFS implementation
1249//
1250
1251/// Traverse the loop blocks and store the DFS result.
1252/// Useful for clients that just want the final DFS result and don't need to
1253/// visit blocks during the initial traversal.
1254void LoopBlocksDFS::perform(const LoopInfo *LI) {
1255 LoopBlocksTraversal Traversal(*this, LI);
1256 for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
1257 POE = Traversal.end();
1258 POI != POE; ++POI)
1259 ;
1260}
1261