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