LCOV - code coverage report
Current view: top level - lib/Analysis - LoopPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 137 142 96.5 %
Date: 2018-10-20 13:21:21 Functions: 18 19 94.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
       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 implements LoopPass and LPPassManager. All loop optimization
      11             : // and transformation passes are derived from LoopPass. LPPassManager is
      12             : // responsible for managing LoopPasses.
      13             : //
      14             : //===----------------------------------------------------------------------===//
      15             : 
      16             : #include "llvm/Analysis/LoopPass.h"
      17             : #include "llvm/Analysis/LoopAnalysisManager.h"
      18             : #include "llvm/IR/Dominators.h"
      19             : #include "llvm/IR/IRPrintingPasses.h"
      20             : #include "llvm/IR/LLVMContext.h"
      21             : #include "llvm/IR/OptBisect.h"
      22             : #include "llvm/IR/PassManager.h"
      23             : #include "llvm/IR/PassTimingInfo.h"
      24             : #include "llvm/Support/Debug.h"
      25             : #include "llvm/Support/Timer.h"
      26             : #include "llvm/Support/raw_ostream.h"
      27             : using namespace llvm;
      28             : 
      29             : #define DEBUG_TYPE "loop-pass-manager"
      30             : 
      31             : namespace {
      32             : 
      33             : /// PrintLoopPass - Print a Function corresponding to a Loop.
      34             : ///
      35             : class PrintLoopPassWrapper : public LoopPass {
      36             :   raw_ostream &OS;
      37             :   std::string Banner;
      38             : 
      39             : public:
      40             :   static char ID;
      41             :   PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
      42             :   PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
      43          38 :       : LoopPass(ID), OS(OS), Banner(Banner) {}
      44             : 
      45          19 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      46             :     AU.setPreservesAll();
      47          19 :   }
      48             : 
      49           6 :   bool runOnLoop(Loop *L, LPPassManager &) override {
      50             :     auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
      51          12 :     if (BBI != L->blocks().end() &&
      52           6 :         isFunctionInPrintList((*BBI)->getParent()->getName())) {
      53           4 :       printLoop(*L, OS, Banner);
      54             :     }
      55           6 :     return false;
      56             :   }
      57             : 
      58           0 :   StringRef getPassName() const override { return "Print Loop IR"; }
      59             : };
      60             : 
      61             : char PrintLoopPassWrapper::ID = 0;
      62             : }
      63             : 
      64             : //===----------------------------------------------------------------------===//
      65             : // LPPassManager
      66             : //
      67             : 
      68             : char LPPassManager::ID = 0;
      69             : 
      70       37036 : LPPassManager::LPPassManager()
      71       37036 :   : FunctionPass(ID), PMDataManager() {
      72       37036 :   LI = nullptr;
      73       37036 :   CurrentLoop = nullptr;
      74       37036 : }
      75             : 
      76             : // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
      77         326 : void LPPassManager::addLoop(Loop &L) {
      78         326 :   if (!L.getParentLoop()) {
      79             :     // This is the top level loop.
      80         243 :     LQ.push_front(&L);
      81         243 :     return;
      82             :   }
      83             : 
      84             :   // Insert L into the loop queue after the parent loop.
      85         116 :   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
      86         116 :     if (*I == L.getParentLoop()) {
      87             :       // deque does not support insert after.
      88             :       ++I;
      89         166 :       LQ.insert(I, 1, &L);
      90             :       return;
      91             :     }
      92             :   }
      93             : }
      94             : 
      95             : /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
      96             : /// all loop passes.
      97         725 : void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
      98             :                                                   BasicBlock *To, Loop *L) {
      99        1497 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     100             :     LoopPass *LP = getContainedPass(Index);
     101         772 :     LP->cloneBasicBlockAnalysis(From, To, L);
     102             :   }
     103         725 : }
     104             : 
     105             : /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
     106         259 : void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
     107             :   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
     108           0 :     for (Instruction &I : *BB) {
     109           0 :       deleteSimpleAnalysisValue(&I, L);
     110             :     }
     111             :   }
     112         536 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     113             :     LoopPass *LP = getContainedPass(Index);
     114         277 :     LP->deleteAnalysisValue(V, L);
     115             :   }
     116         259 : }
     117             : 
     118             : /// Invoke deleteAnalysisLoop hook for all passes.
     119         935 : void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
     120        3276 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     121             :     LoopPass *LP = getContainedPass(Index);
     122        2341 :     LP->deleteAnalysisLoop(L);
     123             :   }
     124         935 : }
     125             : 
     126             : 
     127             : // Recurse through all subloops and all loops  into LQ.
     128       40879 : static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
     129             :   LQ.push_back(L);
     130       49243 :   for (Loop *I : reverse(*L))
     131        8364 :     addLoopIntoQueue(I, LQ);
     132       40879 : }
     133             : 
     134             : /// Pass Manager itself does not invalidate any analysis info.
     135       37036 : void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
     136             :   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
     137             :   // become part of LPPassManager.
     138             :   Info.addRequired<LoopInfoWrapperPass>();
     139             :   Info.addRequired<DominatorTreeWrapperPass>();
     140             :   Info.setPreservesAll();
     141       37036 : }
     142             : 
     143         668 : void LPPassManager::markLoopAsDeleted(Loop &L) {
     144             :   assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
     145             :          "Must not delete loop outside the current loop tree!");
     146             :   // If this loop appears elsewhere within the queue, we also need to remove it
     147             :   // there. However, we have to be careful to not remove the back of the queue
     148             :   // as that is assumed to match the current loop.
     149             :   assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
     150        2004 :   LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
     151             : 
     152         668 :   if (&L == CurrentLoop) {
     153         668 :     CurrentLoopDeleted = true;
     154             :     // Add this loop back onto the back of the queue to preserve our invariants.
     155        1336 :     LQ.push_back(&L);
     156             :   }
     157         668 : }
     158             : 
     159             : /// run - Execute all of the passes scheduled for execution.  Keep track of
     160             : /// whether any of the passes modifies the function, and if so, return true.
     161      426094 : bool LPPassManager::runOnFunction(Function &F) {
     162      426094 :   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
     163      426094 :   LI = &LIWP.getLoopInfo();
     164      426094 :   Module &M = *F.getParent();
     165             : #if 0
     166             :   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     167             : #endif
     168             :   bool Changed = false;
     169             : 
     170             :   // Collect inherited analysis from Module level pass manager.
     171      426094 :   populateInheritedAnalysis(TPM->activeStack);
     172             : 
     173             :   // Populate the loop queue in reverse program order. There is no clear need to
     174             :   // process sibling loops in either forward or reverse order. There may be some
     175             :   // advantage in deleting uses in a later loop before optimizing the
     176             :   // definitions in an earlier loop. If we find a clear reason to process in
     177             :   // forward order, then a forward variant of LoopPassManager should be created.
     178             :   //
     179             :   // Note that LoopInfo::iterator visits loops in reverse program
     180             :   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
     181             :   // reverses the order a third time by popping from the back.
     182      458609 :   for (Loop *L : reverse(*LI))
     183       32515 :     addLoopIntoQueue(L, LQ);
     184             : 
     185      426094 :   if (LQ.empty()) // No loops, skip calling finalizers
     186             :     return false;
     187             : 
     188             :   // Initialization
     189       64958 :   for (Loop *L : LQ) {
     190      114960 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     191             :       LoopPass *P = getContainedPass(Index);
     192       74081 :       Changed |= P->doInitialization(L, *this);
     193             :     }
     194             :   }
     195             : 
     196             :   // Walk Loops
     197             :   unsigned InstrCount, FunctionSize = 0;
     198       24079 :   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
     199       24079 :   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
     200             :   // Collect the initial size of the module and the function we're looking at.
     201       24079 :   if (EmitICRemark) {
     202           1 :     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
     203           1 :     FunctionSize = F.getInstructionCount();
     204             :   }
     205       65283 :   while (!LQ.empty()) {
     206       41204 :     CurrentLoopDeleted = false;
     207       41204 :     CurrentLoop = LQ.back();
     208             : 
     209             :     // Run all passes on the current Loop.
     210      114754 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     211             :       LoopPass *P = getContainedPass(Index);
     212             : 
     213       74218 :       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
     214       74218 :                    CurrentLoop->getHeader()->getName());
     215       74218 :       dumpRequiredSet(P);
     216             : 
     217       74218 :       initializeAnalysisImpl(P);
     218             : 
     219             :       {
     220      148436 :         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
     221       74218 :         TimeRegion PassTimer(getPassTimer(P));
     222       74218 :         Changed |= P->runOnLoop(CurrentLoop, *this);
     223       74218 :         if (EmitICRemark) {
     224           1 :           unsigned NewSize = F.getInstructionCount();
     225             :           // Update the size of the function, emit a remark, and update the
     226             :           // size of the module.
     227           1 :           if (NewSize != FunctionSize) {
     228           2 :             int64_t Delta = static_cast<int64_t>(NewSize) -
     229           1 :                             static_cast<int64_t>(FunctionSize);
     230           1 :             emitInstrCountChangedRemark(P, M, Delta, InstrCount,
     231             :                                         FunctionToInstrCount, &F);
     232           1 :             InstrCount = static_cast<int64_t>(InstrCount) + Delta;
     233             :             FunctionSize = NewSize;
     234             :           }
     235             :         }
     236             :       }
     237             : 
     238       74218 :       if (Changed)
     239       25464 :         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
     240       25464 :                      CurrentLoopDeleted ? "<deleted loop>"
     241       24796 :                                         : CurrentLoop->getName());
     242       74218 :       dumpPreservedSet(P);
     243             : 
     244       74218 :       if (CurrentLoopDeleted) {
     245             :         // Notify passes that the loop is being deleted.
     246         668 :         deleteSimpleAnalysisLoop(CurrentLoop);
     247             :       } else {
     248             :         // Manually check that this loop is still healthy. This is done
     249             :         // instead of relying on LoopInfo::verifyLoop since LoopInfo
     250             :         // is a function pass and it's really expensive to verify every
     251             :         // loop in the function every time. That level of checking can be
     252             :         // enabled with the -verify-loop-info option.
     253             :         {
     254       73550 :           TimeRegion PassTimer(getPassTimer(&LIWP));
     255       73550 :           CurrentLoop->verifyLoop();
     256             :         }
     257             :         // Here we apply same reasoning as in the above case. Only difference
     258             :         // is that LPPassManager might run passes which do not require LCSSA
     259             :         // form (LoopPassPrinter for example). We should skip verification for
     260             :         // such passes.
     261             :         // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
     262             :         // verification!
     263             : #if 0
     264             :         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
     265             :           assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
     266             : #endif
     267             : 
     268             :         // Then call the regular verifyAnalysis functions.
     269       73550 :         verifyPreservedAnalysis(P);
     270             : 
     271       73550 :         F.getContext().yield();
     272             :       }
     273             : 
     274       74218 :       removeNotPreservedAnalysis(P);
     275       74218 :       recordAvailableAnalysis(P);
     276       74218 :       removeDeadPasses(P,
     277       74218 :                        CurrentLoopDeleted ? "<deleted>"
     278      147100 :                                           : CurrentLoop->getHeader()->getName(),
     279             :                        ON_LOOP_MSG);
     280             : 
     281       74218 :       if (CurrentLoopDeleted)
     282             :         // Do not run other passes on this loop.
     283             :         break;
     284             :     }
     285             : 
     286             :     // If the loop was deleted, release all the loop passes. This frees up
     287             :     // some memory, and avoids trouble with the pass manager trying to call
     288             :     // verifyAnalysis on them.
     289       41204 :     if (CurrentLoopDeleted) {
     290        2731 :       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     291             :         Pass *P = getContainedPass(Index);
     292        4126 :         freePass(P, "<deleted>", ON_LOOP_MSG);
     293             :       }
     294             :     }
     295             : 
     296             :     // Pop the loop from queue after running all passes.
     297       41204 :     LQ.pop_back();
     298             :   }
     299             : 
     300             :   // Finalization
     301       67890 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     302             :     LoopPass *P = getContainedPass(Index);
     303       43811 :     Changed |= P->doFinalization();
     304             :   }
     305             : 
     306             :   return Changed;
     307             : }
     308             : 
     309             : /// Print passes managed by this manager
     310          64 : void LPPassManager::dumpPassStructure(unsigned Offset) {
     311          64 :   errs().indent(Offset*2) << "Loop Pass Manager\n";
     312         176 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     313             :     Pass *P = getContainedPass(Index);
     314         112 :     P->dumpPassStructure(Offset + 1);
     315         112 :     dumpLastUses(P, Offset+1);
     316             :   }
     317          64 : }
     318             : 
     319             : 
     320             : //===----------------------------------------------------------------------===//
     321             : // LoopPass
     322             : 
     323          19 : Pass *LoopPass::createPrinterPass(raw_ostream &O,
     324             :                                   const std::string &Banner) const {
     325          19 :   return new PrintLoopPassWrapper(O, Banner);
     326             : }
     327             : 
     328             : // Check if this pass is suitable for the current LPPassManager, if
     329             : // available. This pass P is not suitable for a LPPassManager if P
     330             : // is not preserving higher level analysis info used by other
     331             : // LPPassManager passes. In such case, pop LPPassManager from the
     332             : // stack. This will force assignPassManager() to create new
     333             : // LPPassManger as expected.
     334       64292 : void LoopPass::preparePassManager(PMStack &PMS) {
     335             : 
     336             :   // Find LPPassManager
     337       64292 :   while (!PMS.empty() &&
     338       64292 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     339           0 :     PMS.pop();
     340             : 
     341             :   // If this pass is destroying high level information that is used
     342             :   // by other passes that are managed by LPM then do not insert
     343             :   // this pass in current LPM. Use new LPPassManager.
     344       71487 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
     345        7195 :       !PMS.top()->preserveHigherLevelAnalysis(this))
     346          30 :     PMS.pop();
     347       64292 : }
     348             : 
     349             : /// Assign pass manager to manage this pass.
     350       64311 : void LoopPass::assignPassManager(PMStack &PMS,
     351             :                                  PassManagerType PreferredType) {
     352             :   // Find LPPassManager
     353       64311 :   while (!PMS.empty() &&
     354       64311 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     355           0 :     PMS.pop();
     356             : 
     357             :   LPPassManager *LPPM;
     358       64311 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
     359       27275 :     LPPM = (LPPassManager*)PMS.top();
     360             :   else {
     361             :     // Create new Loop Pass Manager if it does not exist.
     362             :     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
     363             :     PMDataManager *PMD = PMS.top();
     364             : 
     365             :     // [1] Create new Loop Pass Manager
     366       37036 :     LPPM = new LPPassManager();
     367             :     LPPM->populateInheritedAnalysis(PMS);
     368             : 
     369             :     // [2] Set up new manager's top level manager
     370       37036 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
     371       37036 :     TPM->addIndirectPassManager(LPPM);
     372             : 
     373             :     // [3] Assign manager to manage this new manager. This may create
     374             :     // and push new managers into PMS
     375       37036 :     Pass *P = LPPM->getAsPass();
     376       37036 :     TPM->schedulePass(P);
     377             : 
     378             :     // [4] Push new manager into PMS
     379       37036 :     PMS.push(LPPM);
     380             :   }
     381             : 
     382       64311 :   LPPM->add(this);
     383       64311 : }
     384             : 
     385       65266 : bool LoopPass::skipLoop(const Loop *L) const {
     386       65266 :   const Function *F = L->getHeader()->getParent();
     387       65266 :   if (!F)
     388             :     return false;
     389             :   // Check the opt bisect limit.
     390       65266 :   LLVMContext &Context = F->getContext();
     391       65266 :   if (!Context.getOptPassGate().shouldRunPass(this, *L))
     392             :     return true;
     393             :   // Check for the OptimizeNone attribute.
     394       65109 :   if (F->hasFnAttribute(Attribute::OptimizeNone)) {
     395             :     // FIXME: Report this to dbgs() only once per function.
     396             :     LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
     397             :                       << F->getName() << "\n");
     398             :     // FIXME: Delete loop from pass manager's queue?
     399          53 :     return true;
     400             :   }
     401             :   return false;
     402             : }
     403             : 
     404             : char LCSSAVerificationPass::ID = 0;
     405      195164 : INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
     406             :                 false, false)

Generated by: LCOV version 1.13