LCOV - code coverage report
Current view: top level - lib/Analysis - LoopInfo.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 284 305 93.1 %
Date: 2017-09-14 15:23:50 Functions: 36 39 92.3 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13