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