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