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