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