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

Generated by: LCOV version 1.13