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