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