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