contrib/llvm/lib/Analysis/LoopInfo.cpp

   1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the LoopInfo class that is used to identify natural loops
  11 // and determine the loop depth of various nodes of the CFG.  Note that the
  12 // loops identified may actually be several natural loops that share the same
  13 // header node... not just a single natural loop.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/ADT/DepthFirstIterator.h"
  19 #include "llvm/ADT/ScopeExit.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/Analysis/LoopInfoImpl.h"
  22 #include "llvm/Analysis/LoopIterator.h"
  23 #include "llvm/Analysis/ValueTracking.h"
  24 #include "llvm/Config/llvm-config.h"
  25 #include "llvm/IR/CFG.h"
  26 #include "llvm/IR/Constants.h"
  27 #include "llvm/IR/DebugLoc.h"
  28 #include "llvm/IR/Dominators.h"
  29 #include "llvm/IR/Instructions.h"
  30 #include "llvm/IR/LLVMContext.h"
  31 #include "llvm/IR/Metadata.h"
  32 #include "llvm/IR/PassManager.h"
  33 #include "llvm/Support/CommandLine.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include <algorithm>
  37 using namespace llvm;
  38
  39 // Explicitly instantiate methods in LoopInfoImpl.h for IR-level Loops.
  40 template class llvm::LoopBase<BasicBlock, Loop>;
  41 template class llvm::LoopInfoBase<BasicBlock, Loop>;
  42
  43 // Always verify loopinfo if expensive checking is enabled.
  44 #ifdef EXPENSIVE_CHECKS
  45 bool llvm::VerifyLoopInfo = true;
  46 #else
  47 bool llvm::VerifyLoopInfo = false;
  48 #endif
  49 static cl::opt<bool, true>
  50     VerifyLoopInfoX("verify-loop-info", cl::location(VerifyLoopInfo),
  51                     cl::Hidden, cl::desc("Verify loop info (time consuming)"));
  52
  53 //===----------------------------------------------------------------------===//
  54 // Loop implementation
  55 //
  56
  57 bool Loop::isLoopInvariant(const Value *V) const {
  58   if (const Instruction *I = dyn_cast<Instruction>(V))
  59     return !contains(I);
  60   return true; // All non-instructions are loop invariant
  61 }
  62
  63 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
  64   return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
  65 }
  66
  67 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
  68                              Instruction *InsertPt) const {
  69   if (Instruction *I = dyn_cast<Instruction>(V))
  70     return makeLoopInvariant(I, Changed, InsertPt);
  71   return true; // All non-instructions are loop-invariant.
  72 }
  73
  74 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,
  75                              Instruction *InsertPt) const {
  76   // Test if the value is already loop-invariant.
  77   if (isLoopInvariant(I))
  78     return true;
  79   if (!isSafeToSpeculativelyExecute(I))
  80     return false;
  81   if (I->mayReadFromMemory())
  82     return false;
  83   // EH block instructions are immobile.
  84   if (I->isEHPad())
  85     return false;
  86   // Determine the insertion point, unless one was given.
  87   if (!InsertPt) {
  88     BasicBlock *Preheader = getLoopPreheader();
  89     // Without a preheader, hoisting is not feasible.
  90     if (!Preheader)
  91       return false;
  92     InsertPt = Preheader->getTerminator();
  93   }
  94   // Don't hoist instructions with loop-variant operands.
  95   for (Value *Operand : I->operands())
  96     if (!makeLoopInvariant(Operand, Changed, InsertPt))
  97       return false;
  98
  99   // Hoist.
 100   I->moveBefore(InsertPt);
 101
 102   // There is possibility of hoisting this instruction above some arbitrary
 103   // condition. Any metadata defined on it can be control dependent on this
 104   // condition. Conservatively strip it here so that we don't give any wrong
 105   // information to the optimizer.
 106   I->dropUnknownNonDebugMetadata();
 107
 108   Changed = true;
 109   return true;
 110 }
 111
 112 PHINode *Loop::getCanonicalInductionVariable() const {
 113   BasicBlock *H = getHeader();
 114
 115   BasicBlock *Incoming = nullptr, *Backedge = nullptr;
 116   pred_iterator PI = pred_begin(H);
 117   assert(PI != pred_end(H) && "Loop must have at least one backedge!");
 118   Backedge = *PI++;
 119   if (PI == pred_end(H))
 120     return nullptr; // dead loop
 121   Incoming = *PI++;
 122   if (PI != pred_end(H))
 123     return nullptr; // multiple backedges?
 124
 125   if (contains(Incoming)) {
 126     if (contains(Backedge))
 127       return nullptr;
 128     std::swap(Incoming, Backedge);
 129   } else if (!contains(Backedge))
 130     return nullptr;
 131
 132   // Loop over all of the PHI nodes, looking for a canonical indvar.
 133   for (BasicBlock::iterator I = H->begin(); isa<PHINode>(I); ++I) {
 134     PHINode *PN = cast<PHINode>(I);
 135     if (ConstantInt *CI =
 136             dyn_cast<ConstantInt>(PN->getIncomingValueForBlock(Incoming)))
 137       if (CI->isZero())
 138         if (Instruction *Inc =
 139                 dyn_cast<Instruction>(PN->getIncomingValueForBlock(Backedge)))
 140           if (Inc->getOpcode() == Instruction::Add && Inc->getOperand(0) == PN)
 141             if (ConstantInt *CI = dyn_cast<ConstantInt>(Inc->getOperand(1)))
 142               if (CI->isOne())
 143                 return PN;
 144   }
 145   return nullptr;
 146 }
 147
 148 // Check that 'BB' doesn't have any uses outside of the 'L'
 149 static bool isBlockInLCSSAForm(const Loop &L, const BasicBlock &BB,
 150                                DominatorTree &DT) {
 151   for (const Instruction &I : BB) {
 152     // Tokens can't be used in PHI nodes and live-out tokens prevent loop
 153     // optimizations, so for the purposes of considered LCSSA form, we
 154     // can ignore them.
 155     if (I.getType()->isTokenTy())
 156       continue;
 157
 158     for (const Use &U : I.uses()) {
 159       const Instruction *UI = cast<Instruction>(U.getUser());
 160       const BasicBlock *UserBB = UI->getParent();
 161       if (const PHINode *P = dyn_cast<PHINode>(UI))
 162         UserBB = P->getIncomingBlock(U);
 163
 164       // Check the current block, as a fast-path, before checking whether
 165       // the use is anywhere in the loop.  Most values are used in the same
 166       // block they are defined in.  Also, blocks not reachable from the
 167       // entry are special; uses in them don't need to go through PHIs.
 168       if (UserBB != &BB && !L.contains(UserBB) &&
 169           DT.isReachableFromEntry(UserBB))
 170         return false;
 171     }
 172   }
 173   return true;
 174 }
 175
 176 bool Loop::isLCSSAForm(DominatorTree &DT) const {
 177   // For each block we check that it doesn't have any uses outside of this loop.
 178   return all_of(this->blocks(), [&](const BasicBlock *BB) {
 179     return isBlockInLCSSAForm(*this, *BB, DT);
 180   });
 181 }
 182
 183 bool Loop::isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const {
 184   // For each block we check that it doesn't have any uses outside of its
 185   // innermost loop. This process will transitively guarantee that the current
 186   // loop and all of the nested loops are in LCSSA form.
 187   return all_of(this->blocks(), [&](const BasicBlock *BB) {
 188     return isBlockInLCSSAForm(*LI.getLoopFor(BB), *BB, DT);
 189   });
 190 }
 191
 192 bool Loop::isLoopSimplifyForm() const {
 193   // Normal-form loops have a preheader, a single backedge, and all of their
 194   // exits have all their predecessors inside the loop.
 195   return getLoopPreheader() && getLoopLatch() && hasDedicatedExits();
 196 }
 197
 198 // Routines that reform the loop CFG and split edges often fail on indirectbr.
 199 bool Loop::isSafeToClone() const {
 200   // Return false if any loop blocks contain indirectbrs, or there are any calls
 201   // to noduplicate functions.
 202   for (BasicBlock *BB : this->blocks()) {
 203     if (isa<IndirectBrInst>(BB->getTerminator()))
 204       return false;
 205
 206     for (Instruction &I : *BB)
 207       if (auto CS = CallSite(&I))
 208         if (CS.cannotDuplicate())
 209           return false;
 210   }
 211   return true;
 212 }
 213
 214 MDNode *Loop::getLoopID() const {
 215   MDNode *LoopID = nullptr;
 216   if (BasicBlock *Latch = getLoopLatch()) {
 217     LoopID = Latch->getTerminator()->getMetadata(LLVMContext::MD_loop);
 218   } else {
 219     assert(!getLoopLatch() &&
 220            "The loop should have no single latch at this point");
 221     // Go through each predecessor of the loop header and check the
 222     // terminator for the metadata.
 223     BasicBlock *H = getHeader();
 224     for (BasicBlock *BB : this->blocks()) {
 225       TerminatorInst *TI = BB->getTerminator();
 226       MDNode *MD = nullptr;
 227
 228       // Check if this terminator branches to the loop header.
 229       for (BasicBlock *Successor : TI->successors()) {
 230         if (Successor == H) {
 231           MD = TI->getMetadata(LLVMContext::MD_loop);
 232           break;
 233         }
 234       }
 235       if (!MD)
 236         return nullptr;
 237
 238       if (!LoopID)
 239         LoopID = MD;
 240       else if (MD != LoopID)
 241         return nullptr;
 242     }
 243   }
 244   if (!LoopID || LoopID->getNumOperands() == 0 ||
 245       LoopID->getOperand(0) != LoopID)
 246     return nullptr;
 247   return LoopID;
 248 }
 249
 250 void Loop::setLoopID(MDNode *LoopID) const {
 251   assert(LoopID && "Loop ID should not be null");
 252   assert(LoopID->getNumOperands() > 0 && "Loop ID needs at least one operand");
 253   assert(LoopID->getOperand(0) == LoopID && "Loop ID should refer to itself");
 254
 255   if (BasicBlock *Latch = getLoopLatch()) {
 256     Latch->getTerminator()->setMetadata(LLVMContext::MD_loop, LoopID);
 257     return;
 258   }
 259
 260   assert(!getLoopLatch() &&
 261          "The loop should have no single latch at this point");
 262   BasicBlock *H = getHeader();
 263   for (BasicBlock *BB : this->blocks()) {
 264     TerminatorInst *TI = BB->getTerminator();
 265     for (BasicBlock *Successor : TI->successors()) {
 266       if (Successor == H)
 267         TI->setMetadata(LLVMContext::MD_loop, LoopID);
 268     }
 269   }
 270 }
 271
 272 void Loop::setLoopAlreadyUnrolled() {
 273   MDNode *LoopID = getLoopID();
 274   // First remove any existing loop unrolling metadata.
 275   SmallVector<Metadata *, 4> MDs;
 276   // Reserve first location for self reference to the LoopID metadata node.
 277   MDs.push_back(nullptr);
 278
 279   if (LoopID) {
 280     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 281       bool IsUnrollMetadata = false;
 282       MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
 283       if (MD) {
 284         const MDString *S = dyn_cast<MDString>(MD->getOperand(0));
 285         IsUnrollMetadata = S && S->getString().startswith("llvm.loop.unroll.");
 286       }
 287       if (!IsUnrollMetadata)
 288         MDs.push_back(LoopID->getOperand(i));
 289     }
 290   }
 291
 292   // Add unroll(disable) metadata to disable future unrolling.
 293   LLVMContext &Context = getHeader()->getContext();
 294   SmallVector<Metadata *, 1> DisableOperands;
 295   DisableOperands.push_back(MDString::get(Context, "llvm.loop.unroll.disable"));
 296   MDNode *DisableNode = MDNode::get(Context, DisableOperands);
 297   MDs.push_back(DisableNode);
 298
 299   MDNode *NewLoopID = MDNode::get(Context, MDs);
 300   // Set operand 0 to refer to the loop id itself.
 301   NewLoopID->replaceOperandWith(0, NewLoopID);
 302   setLoopID(NewLoopID);
 303 }
 304
 305 bool Loop::isAnnotatedParallel() const {
 306   MDNode *DesiredLoopIdMetadata = getLoopID();
 307
 308   if (!DesiredLoopIdMetadata)
 309     return false;
 310
 311   // The loop branch contains the parallel loop metadata. In order to ensure
 312   // that any parallel-loop-unaware optimization pass hasn't added loop-carried
 313   // dependencies (thus converted the loop back to a sequential loop), check
 314   // that all the memory instructions in the loop contain parallelism metadata
 315   // that point to the same unique "loop id metadata" the loop branch does.
 316   for (BasicBlock *BB : this->blocks()) {
 317     for (Instruction &I : *BB) {
 318       if (!I.mayReadOrWriteMemory())
 319         continue;
 320
 321       // The memory instruction can refer to the loop identifier metadata
 322       // directly or indirectly through another list metadata (in case of
 323       // nested parallel loops). The loop identifier metadata refers to
 324       // itself so we can check both cases with the same routine.
 325       MDNode *LoopIdMD =
 326           I.getMetadata(LLVMContext::MD_mem_parallel_loop_access);
 327
 328       if (!LoopIdMD)
 329         return false;
 330
 331       bool LoopIdMDFound = false;
 332       for (const MDOperand &MDOp : LoopIdMD->operands()) {
 333         if (MDOp == DesiredLoopIdMetadata) {
 334           LoopIdMDFound = true;
 335           break;
 336         }
 337       }
 338
 339       if (!LoopIdMDFound)
 340         return false;
 341     }
 342   }
 343   return true;
 344 }
 345
 346 DebugLoc Loop::getStartLoc() const { return getLocRange().getStart(); }
 347
 348 Loop::LocRange Loop::getLocRange() const {
 349   // If we have a debug location in the loop ID, then use it.
 350   if (MDNode *LoopID = getLoopID()) {
 351     DebugLoc Start;
 352     // We use the first DebugLoc in the header as the start location of the loop
 353     // and if there is a second DebugLoc in the header we use it as end location
 354     // of the loop.
 355     for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) {
 356       if (DILocation *L = dyn_cast<DILocation>(LoopID->getOperand(i))) {
 357         if (!Start)
 358           Start = DebugLoc(L);
 359         else
 360           return LocRange(Start, DebugLoc(L));
 361       }
 362     }
 363
 364     if (Start)
 365       return LocRange(Start);
 366   }
 367
 368   // Try the pre-header first.
 369   if (BasicBlock *PHeadBB = getLoopPreheader())
 370     if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
 371       return LocRange(DL);
 372
 373   // If we have no pre-header or there are no instructions with debug
 374   // info in it, try the header.
 375   if (BasicBlock *HeadBB = getHeader())
 376     return LocRange(HeadBB->getTerminator()->getDebugLoc());
 377
 378   return LocRange();
 379 }
 380
 381 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 382 LLVM_DUMP_METHOD void Loop::dump() const { print(dbgs()); }
 383
 384 LLVM_DUMP_METHOD void Loop::dumpVerbose() const {
 385   print(dbgs(), /*Depth=*/0, /*Verbose=*/true);
 386 }
 387 #endif
 388
 389 //===----------------------------------------------------------------------===//
 390 // UnloopUpdater implementation
 391 //
 392
 393 namespace {
 394 /// Find the new parent loop for all blocks within the "unloop" whose last
 395 /// backedges has just been removed.
 396 class UnloopUpdater {
 397   Loop &Unloop;
 398   LoopInfo *LI;
 399
 400   LoopBlocksDFS DFS;
 401
 402   // Map unloop's immediate subloops to their nearest reachable parents. Nested
 403   // loops within these subloops will not change parents. However, an immediate
 404   // subloop's new parent will be the nearest loop reachable from either its own
 405   // exits *or* any of its nested loop's exits.
 406   DenseMap<Loop *, Loop *> SubloopParents;
 407
 408   // Flag the presence of an irreducible backedge whose destination is a block
 409   // directly contained by the original unloop.
 410   bool FoundIB;
 411
 412 public:
 413   UnloopUpdater(Loop *UL, LoopInfo *LInfo)
 414       : Unloop(*UL), LI(LInfo), DFS(UL), FoundIB(false) {}
 415
 416   void updateBlockParents();
 417
 418   void removeBlocksFromAncestors();
 419
 420   void updateSubloopParents();
 421
 422 protected:
 423   Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
 424 };
 425 } // end anonymous namespace
 426
 427 /// Update the parent loop for all blocks that are directly contained within the
 428 /// original "unloop".
 429 void UnloopUpdater::updateBlockParents() {
 430   if (Unloop.getNumBlocks()) {
 431     // Perform a post order CFG traversal of all blocks within this loop,
 432     // propagating the nearest loop from successors to predecessors.
 433     LoopBlocksTraversal Traversal(DFS, LI);
 434     for (BasicBlock *POI : Traversal) {
 435
 436       Loop *L = LI->getLoopFor(POI);
 437       Loop *NL = getNearestLoop(POI, L);
 438
 439       if (NL != L) {
 440         // For reducible loops, NL is now an ancestor of Unloop.
 441         assert((NL != &Unloop && (!NL || NL->contains(&Unloop))) &&
 442                "uninitialized successor");
 443         LI->changeLoopFor(POI, NL);
 444       } else {
 445         // Or the current block is part of a subloop, in which case its parent
 446         // is unchanged.
 447         assert((FoundIB || Unloop.contains(L)) && "uninitialized successor");
 448       }
 449     }
 450   }
 451   // Each irreducible loop within the unloop induces a round of iteration using
 452   // the DFS result cached by Traversal.
 453   bool Changed = FoundIB;
 454   for (unsigned NIters = 0; Changed; ++NIters) {
 455     assert(NIters < Unloop.getNumBlocks() && "runaway iterative algorithm");
 456
 457     // Iterate over the postorder list of blocks, propagating the nearest loop
 458     // from successors to predecessors as before.
 459     Changed = false;
 460     for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
 461                                    POE = DFS.endPostorder();
 462          POI != POE; ++POI) {
 463
 464       Loop *L = LI->getLoopFor(*POI);
 465       Loop *NL = getNearestLoop(*POI, L);
 466       if (NL != L) {
 467         assert(NL != &Unloop && (!NL || NL->contains(&Unloop)) &&
 468                "uninitialized successor");
 469         LI->changeLoopFor(*POI, NL);
 470         Changed = true;
 471       }
 472     }
 473   }
 474 }
 475
 476 /// Remove unloop's blocks from all ancestors below their new parents.
 477 void UnloopUpdater::removeBlocksFromAncestors() {
 478   // Remove all unloop's blocks (including those in nested subloops) from
 479   // ancestors below the new parent loop.
 480   for (Loop::block_iterator BI = Unloop.block_begin(), BE = Unloop.block_end();
 481        BI != BE; ++BI) {
 482     Loop *OuterParent = LI->getLoopFor(*BI);
 483     if (Unloop.contains(OuterParent)) {
 484       while (OuterParent->getParentLoop() != &Unloop)
 485         OuterParent = OuterParent->getParentLoop();
 486       OuterParent = SubloopParents[OuterParent];
 487     }
 488     // Remove blocks from former Ancestors except Unloop itself which will be
 489     // deleted.
 490     for (Loop *OldParent = Unloop.getParentLoop(); OldParent != OuterParent;
 491          OldParent = OldParent->getParentLoop()) {
 492       assert(OldParent && "new loop is not an ancestor of the original");
 493       OldParent->removeBlockFromLoop(*BI);
 494     }
 495   }
 496 }
 497
 498 /// Update the parent loop for all subloops directly nested within unloop.
 499 void UnloopUpdater::updateSubloopParents() {
 500   while (!Unloop.empty()) {
 501     Loop *Subloop = *std::prev(Unloop.end());
 502     Unloop.removeChildLoop(std::prev(Unloop.end()));
 503
 504     assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
 505     if (Loop *Parent = SubloopParents[Subloop])
 506       Parent->addChildLoop(Subloop);
 507     else
 508       LI->addTopLevelLoop(Subloop);
 509   }
 510 }
 511
 512 /// Return the nearest parent loop among this block's successors. If a successor
 513 /// is a subloop header, consider its parent to be the nearest parent of the
 514 /// subloop's exits.
 515 ///
 516 /// For subloop blocks, simply update SubloopParents and return NULL.
 517 Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
 518
 519   // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
 520   // is considered uninitialized.
 521   Loop *NearLoop = BBLoop;
 522
 523   Loop *Subloop = nullptr;
 524   if (NearLoop != &Unloop && Unloop.contains(NearLoop)) {
 525     Subloop = NearLoop;
 526     // Find the subloop ancestor that is directly contained within Unloop.
 527     while (Subloop->getParentLoop() != &Unloop) {
 528       Subloop = Subloop->getParentLoop();
 529       assert(Subloop && "subloop is not an ancestor of the original loop");
 530     }
 531     // Get the current nearest parent of the Subloop exits, initially Unloop.
 532     NearLoop = SubloopParents.insert({Subloop, &Unloop}).first->second;
 533   }
 534
 535   succ_iterator I = succ_begin(BB), E = succ_end(BB);
 536   if (I == E) {
 537     assert(!Subloop && "subloop blocks must have a successor");
 538     NearLoop = nullptr; // unloop blocks may now exit the function.
 539   }
 540   for (; I != E; ++I) {
 541     if (*I == BB)
 542       continue; // self loops are uninteresting
 543
 544     Loop *L = LI->getLoopFor(*I);
 545     if (L == &Unloop) {
 546       // This successor has not been processed. This path must lead to an
 547       // irreducible backedge.
 548       assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
 549       FoundIB = true;
 550     }
 551     if (L != &Unloop && Unloop.contains(L)) {
 552       // Successor is in a subloop.
 553       if (Subloop)
 554         continue; // Branching within subloops. Ignore it.
 555
 556       // BB branches from the original into a subloop header.
 557       assert(L->getParentLoop() == &Unloop && "cannot skip into nested loops");
 558
 559       // Get the current nearest parent of the Subloop's exits.
 560       L = SubloopParents[L];
 561       // L could be Unloop if the only exit was an irreducible backedge.
 562     }
 563     if (L == &Unloop) {
 564       continue;
 565     }
 566     // Handle critical edges from Unloop into a sibling loop.
 567     if (L && !L->contains(&Unloop)) {
 568       L = L->getParentLoop();
 569     }
 570     // Remember the nearest parent loop among successors or subloop exits.
 571     if (NearLoop == &Unloop || !NearLoop || NearLoop->contains(L))
 572       NearLoop = L;
 573   }
 574   if (Subloop) {
 575     SubloopParents[Subloop] = NearLoop;
 576     return BBLoop;
 577   }
 578   return NearLoop;
 579 }
 580
 581 LoopInfo::LoopInfo(const DomTreeBase<BasicBlock> &DomTree) { analyze(DomTree); }
 582
 583 bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
 584                           FunctionAnalysisManager::Invalidator &) {
 585   // Check whether the analysis, all analyses on functions, or the function's
 586   // CFG have been preserved.
 587   auto PAC = PA.getChecker<LoopAnalysis>();
 588   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
 589            PAC.preservedSet<CFGAnalyses>());
 590 }
 591
 592 void LoopInfo::erase(Loop *Unloop) {
 593   assert(!Unloop->isInvalid() && "Loop has already been erased!");
 594
 595   auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); });
 596
 597   // First handle the special case of no parent loop to simplify the algorithm.
 598   if (!Unloop->getParentLoop()) {
 599     // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
 600     for (Loop::block_iterator I = Unloop->block_begin(),
 601                               E = Unloop->block_end();
 602          I != E; ++I) {
 603
 604       // Don't reparent blocks in subloops.
 605       if (getLoopFor(*I) != Unloop)
 606         continue;
 607
 608       // Blocks no longer have a parent but are still referenced by Unloop until
 609       // the Unloop object is deleted.
 610       changeLoopFor(*I, nullptr);
 611     }
 612
 613     // Remove the loop from the top-level LoopInfo object.
 614     for (iterator I = begin();; ++I) {
 615       assert(I != end() && "Couldn't find loop");
 616       if (*I == Unloop) {
 617         removeLoop(I);
 618         break;
 619       }
 620     }
 621
 622     // Move all of the subloops to the top-level.
 623     while (!Unloop->empty())
 624       addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end())));
 625
 626     return;
 627   }
 628
 629   // Update the parent loop for all blocks within the loop. Blocks within
 630   // subloops will not change parents.
 631   UnloopUpdater Updater(Unloop, this);
 632   Updater.updateBlockParents();
 633
 634   // Remove blocks from former ancestor loops.
 635   Updater.removeBlocksFromAncestors();
 636
 637   // Add direct subloops as children in their new parent loop.
 638   Updater.updateSubloopParents();
 639
 640   // Remove unloop from its parent loop.
 641   Loop *ParentLoop = Unloop->getParentLoop();
 642   for (Loop::iterator I = ParentLoop->begin();; ++I) {
 643     assert(I != ParentLoop->end() && "Couldn't find loop");
 644     if (*I == Unloop) {
 645       ParentLoop->removeChildLoop(I);
 646       break;
 647     }
 648   }
 649 }
 650
 651 AnalysisKey LoopAnalysis::Key;
 652
 653 LoopInfo LoopAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
 654   // FIXME: Currently we create a LoopInfo from scratch for every function.
 655   // This may prove to be too wasteful due to deallocating and re-allocating
 656   // memory each time for the underlying map and vector datastructures. At some
 657   // point it may prove worthwhile to use a freelist and recycle LoopInfo
 658   // objects. I don't want to add that kind of complexity until the scope of
 659   // the problem is better understood.
 660   LoopInfo LI;
 661   LI.analyze(AM.getResult<DominatorTreeAnalysis>(F));
 662   return LI;
 663 }
 664
 665 PreservedAnalyses LoopPrinterPass::run(Function &F,
 666                                        FunctionAnalysisManager &AM) {
 667   AM.getResult<LoopAnalysis>(F).print(OS);
 668   return PreservedAnalyses::all();
 669 }
 670
 671 void llvm::printLoop(Loop &L, raw_ostream &OS, const std::string &Banner) {
 672
 673   if (forcePrintModuleIR()) {
 674     // handling -print-module-scope
 675     OS << Banner << " (loop: ";
 676     L.getHeader()->printAsOperand(OS, false);
 677     OS << ")\n";
 678
 679     // printing whole module
 680     OS << *L.getHeader()->getModule();
 681     return;
 682   }
 683
 684   OS << Banner;
 685
 686   auto *PreHeader = L.getLoopPreheader();
 687   if (PreHeader) {
 688     OS << "\n; Preheader:";
 689     PreHeader->print(OS);
 690     OS << "\n; Loop:";
 691   }
 692
 693   for (auto *Block : L.blocks())
 694     if (Block)
 695       Block->print(OS);
 696     else
 697       OS << "Printing <null> block";
 698
 699   SmallVector<BasicBlock *, 8> ExitBlocks;
 700   L.getExitBlocks(ExitBlocks);
 701   if (!ExitBlocks.empty()) {
 702     OS << "\n; Exit blocks";
 703     for (auto *Block : ExitBlocks)
 704       if (Block)
 705         Block->print(OS);
 706       else
 707         OS << "Printing <null> block";
 708   }
 709 }
 710
 711 //===----------------------------------------------------------------------===//
 712 // LoopInfo implementation
 713 //
 714
 715 char LoopInfoWrapperPass::ID = 0;
 716 INITIALIZE_PASS_BEGIN(LoopInfoWrapperPass, "loops", "Natural Loop Information",
 717                       true, true)
 718 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 719 INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information",
 720                     true, true)
 721
 722 bool LoopInfoWrapperPass::runOnFunction(Function &) {
 723   releaseMemory();
 724   LI.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree());
 725   return false;
 726 }
 727
 728 void LoopInfoWrapperPass::verifyAnalysis() const {
 729   // LoopInfoWrapperPass is a FunctionPass, but verifying every loop in the
 730   // function each time verifyAnalysis is called is very expensive. The
 731   // -verify-loop-info option can enable this. In order to perform some
 732   // checking by default, LoopPass has been taught to call verifyLoop manually
 733   // during loop pass sequences.
 734   if (VerifyLoopInfo) {
 735     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 736     LI.verify(DT);
 737   }
 738 }
 739
 740 void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
 741   AU.setPreservesAll();
 742   AU.addRequired<DominatorTreeWrapperPass>();
 743 }
 744
 745 void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const {
 746   LI.print(OS);
 747 }
 748
 749 PreservedAnalyses LoopVerifierPass::run(Function &F,
 750                                         FunctionAnalysisManager &AM) {
 751   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 752   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 753   LI.verify(DT);
 754   return PreservedAnalyses::all();
 755 }
 756
 757 //===----------------------------------------------------------------------===//
 758 // LoopBlocksDFS implementation
 759 //
 760
 761 /// Traverse the loop blocks and store the DFS result.
 762 /// Useful for clients that just want the final DFS result and don't need to
 763 /// visit blocks during the initial traversal.
 764 void LoopBlocksDFS::perform(LoopInfo *LI) {
 765   LoopBlocksTraversal Traversal(*this, LI);
 766   for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
 767                                         POE = Traversal.end();
 768        POI != POE; ++POI)
 769     ;
 770 }