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