LCOV - code coverage report
Current view: top level - lib/Analysis - LoopPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 133 146 91.1 %
Date: 2017-09-14 15:23:50 Functions: 18 20 90.0 %
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/Support/Debug.h"
      24             : #include "llvm/Support/Timer.h"
      25             : #include "llvm/Support/raw_ostream.h"
      26             : using namespace llvm;
      27             : 
      28             : #define DEBUG_TYPE "loop-pass-manager"
      29             : 
      30             : namespace {
      31             : 
      32             : /// PrintLoopPass - Print a Function corresponding to a Loop.
      33             : ///
      34          64 : class PrintLoopPassWrapper : public LoopPass {
      35             :   raw_ostream &OS;
      36             :   std::string Banner;
      37             : 
      38             : public:
      39             :   static char ID;
      40             :   PrintLoopPassWrapper() : LoopPass(ID), OS(dbgs()) {}
      41             :   PrintLoopPassWrapper(raw_ostream &OS, const std::string &Banner)
      42          48 :       : LoopPass(ID), OS(OS), Banner(Banner) {}
      43             : 
      44          16 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      45          16 :     AU.setPreservesAll();
      46          16 :   }
      47             : 
      48           0 :   bool runOnLoop(Loop *L, LPPassManager &) override {
      49           0 :     auto BBI = find_if(L->blocks().begin(), L->blocks().end(),
      50           0 :                        [](BasicBlock *BB) { return BB; });
      51           0 :     if (BBI != L->blocks().end() &&
      52           0 :         isFunctionInPrintList((*BBI)->getParent()->getName())) {
      53           0 :       printLoop(*L, OS, Banner);
      54             :     }
      55           0 :     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       24117 : LPPassManager::LPPassManager()
      71       72351 :   : FunctionPass(ID), PMDataManager() {
      72       24117 :   LI = nullptr;
      73       24117 :   CurrentLoop = nullptr;
      74       24117 : }
      75             : 
      76             : // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
      77         114 : void LPPassManager::addLoop(Loop &L) {
      78         114 :   if (!L.getParentLoop()) {
      79             :     // This is the top level loop.
      80         168 :     LQ.push_front(&L);
      81          84 :     return;
      82             :   }
      83             : 
      84             :   // Insert L into the loop queue after the parent loop.
      85         104 :   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
      86          44 :     if (*I == L.getParentLoop()) {
      87             :       // deque does not support insert after.
      88          30 :       ++I;
      89          60 :       LQ.insert(I, 1, &L);
      90             :       return;
      91             :     }
      92             :   }
      93             : }
      94             : 
      95             : /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
      96             : /// all loop passes.
      97         408 : void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
      98             :                                                   BasicBlock *To, Loop *L) {
      99        1726 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     100         455 :     LoopPass *LP = getContainedPass(Index);
     101         455 :     LP->cloneBasicBlockAnalysis(From, To, L);
     102             :   }
     103         408 : }
     104             : 
     105             : /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
     106         140 : void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
     107           0 :   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
     108           0 :     for (Instruction &I : *BB) {
     109           0 :       deleteSimpleAnalysisValue(&I, L);
     110             :     }
     111             :   }
     112         751 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     113         157 :     LoopPass *LP = getContainedPass(Index);
     114         157 :     LP->deleteAnalysisValue(V, L);
     115             :   }
     116         140 : }
     117             : 
     118             : /// Invoke deleteAnalysisLoop hook for all passes.
     119         379 : void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
     120        2812 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     121        1027 :     LoopPass *LP = getContainedPass(Index);
     122        1027 :     LP->deleteAnalysisLoop(L);
     123             :   }
     124         379 : }
     125             : 
     126             : 
     127             : // Recurse through all subloops and all loops  into LQ.
     128       26379 : static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
     129       26379 :   LQ.push_back(L);
     130      115546 :   for (Loop *I : reverse(*L))
     131        5015 :     addLoopIntoQueue(I, LQ);
     132       26379 : }
     133             : 
     134             : /// Pass Manager itself does not invalidate any analysis info.
     135       24117 : void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
     136             :   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
     137             :   // become part of LPPassManager.
     138       24117 :   Info.addRequired<LoopInfoWrapperPass>();
     139       24117 :   Info.addRequired<DominatorTreeWrapperPass>();
     140       24117 :   Info.setPreservesAll();
     141       24117 : }
     142             : 
     143             : /// run - Execute all of the passes scheduled for execution.  Keep track of
     144             : /// whether any of the passes modifies the function, and if so, return true.
     145      288018 : bool LPPassManager::runOnFunction(Function &F) {
     146      288018 :   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
     147      288018 :   LI = &LIWP.getLoopInfo();
     148      576036 :   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     149      288018 :   bool Changed = false;
     150             : 
     151             :   // Collect inherited analysis from Module level pass manager.
     152      576036 :   populateInheritedAnalysis(TPM->activeStack);
     153             : 
     154             :   // Populate the loop queue in reverse program order. There is no clear need to
     155             :   // process sibling loops in either forward or reverse order. There may be some
     156             :   // advantage in deleting uses in a later loop before optimizing the
     157             :   // definitions in an earlier loop. If we find a clear reason to process in
     158             :   // forward order, then a forward variant of LoopPassManager should be created.
     159             :   //
     160             :   // Note that LoopInfo::iterator visits loops in reverse program
     161             :   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
     162             :   // reverses the order a third time by popping from the back.
     163     1194800 :   for (Loop *L : reverse(*LI))
     164       21364 :     addLoopIntoQueue(L, LQ);
     165             : 
     166      576036 :   if (LQ.empty()) // No loops, skip calling finalizers
     167             :     return false;
     168             : 
     169             :   // Initialization
     170       74406 :   for (Loop *L : LQ) {
     171      148596 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     172       47919 :       LoopPass *P = getContainedPass(Index);
     173       47919 :       Changed |= P->doInitialization(L, *this);
     174             :     }
     175             :   }
     176             : 
     177             :   // Walk Loops
     178      111497 :   while (!LQ.empty()) {
     179       26493 :     bool LoopWasDeleted = false;
     180       52986 :     CurrentLoop = LQ.back();
     181             : 
     182             :     // Run all passes on the current Loop.
     183      148130 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     184       47951 :       LoopPass *P = getContainedPass(Index);
     185             : 
     186       95902 :       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
     187       95902 :                    CurrentLoop->getHeader()->getName());
     188       47951 :       dumpRequiredSet(P);
     189             : 
     190       47951 :       initializeAnalysisImpl(P);
     191             : 
     192             :       {
     193      191804 :         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
     194      143853 :         TimeRegion PassTimer(getPassTimer(P));
     195             : 
     196       47951 :         Changed |= P->runOnLoop(CurrentLoop, *this);
     197             :       }
     198       47951 :       LoopWasDeleted = CurrentLoop->isInvalid();
     199             : 
     200       47951 :       if (Changed)
     201       32757 :         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
     202             :                      LoopWasDeleted ? "<deleted>"
     203       32378 :                                     : CurrentLoop->getHeader()->getName());
     204       47951 :       dumpPreservedSet(P);
     205             : 
     206       47951 :       if (LoopWasDeleted) {
     207             :         // Notify passes that the loop is being deleted.
     208         379 :         deleteSimpleAnalysisLoop(CurrentLoop);
     209             :       } else {
     210             :         // Manually check that this loop is still healthy. This is done
     211             :         // instead of relying on LoopInfo::verifyLoop since LoopInfo
     212             :         // is a function pass and it's really expensive to verify every
     213             :         // loop in the function every time. That level of checking can be
     214             :         // enabled with the -verify-loop-info option.
     215             :         {
     216      142716 :           TimeRegion PassTimer(getPassTimer(&LIWP));
     217       47572 :           CurrentLoop->verifyLoop();
     218             :         }
     219             :         // Here we apply same reasoning as in the above case. Only difference
     220             :         // is that LPPassManager might run passes which do not require LCSSA
     221             :         // form (LoopPassPrinter for example). We should skip verification for
     222             :         // such passes.
     223       47572 :         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
     224       35630 :           CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI);
     225             : 
     226             :         // Then call the regular verifyAnalysis functions.
     227       47572 :         verifyPreservedAnalysis(P);
     228             : 
     229       47572 :         F.getContext().yield();
     230             :       }
     231             : 
     232       47951 :       removeNotPreservedAnalysis(P);
     233       47951 :       recordAvailableAnalysis(P);
     234       95523 :       removeDeadPasses(P, LoopWasDeleted ? "<deleted>"
     235       95144 :                                          : CurrentLoop->getHeader()->getName(),
     236             :                        ON_LOOP_MSG);
     237             : 
     238       47951 :       if (LoopWasDeleted)
     239             :         // Do not run other passes on this loop.
     240             :         break;
     241             :     }
     242             : 
     243             :     // If the loop was deleted, release all the loop passes. This frees up
     244             :     // some memory, and avoids trouble with the pass manager trying to call
     245             :     // verifyAnalysis on them.
     246       26493 :     if (LoopWasDeleted) {
     247        3839 :       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     248        1027 :         Pass *P = getContainedPass(Index);
     249        2054 :         freePass(P, "<deleted>", ON_LOOP_MSG);
     250             :       }
     251             :     }
     252             : 
     253             :     // Pop the loop from queue after running all passes.
     254       26493 :     LQ.pop_back();
     255             :   }
     256             : 
     257             :   // Finalization
     258      119696 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     259       29226 :     LoopPass *P = getContainedPass(Index);
     260       29226 :     Changed |= P->doFinalization();
     261             :   }
     262             : 
     263             :   return Changed;
     264             : }
     265             : 
     266             : /// Print passes managed by this manager
     267          62 : void LPPassManager::dumpPassStructure(unsigned Offset) {
     268          62 :   errs().indent(Offset*2) << "Loop Pass Manager\n";
     269         338 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     270         107 :     Pass *P = getContainedPass(Index);
     271         107 :     P->dumpPassStructure(Offset + 1);
     272         107 :     dumpLastUses(P, Offset+1);
     273             :   }
     274          62 : }
     275             : 
     276             : 
     277             : //===----------------------------------------------------------------------===//
     278             : // LoopPass
     279             : 
     280          16 : Pass *LoopPass::createPrinterPass(raw_ostream &O,
     281             :                                   const std::string &Banner) const {
     282          32 :   return new PrintLoopPassWrapper(O, Banner);
     283             : }
     284             : 
     285             : // Check if this pass is suitable for the current LPPassManager, if
     286             : // available. This pass P is not suitable for a LPPassManager if P
     287             : // is not preserving higher level analysis info used by other
     288             : // LPPassManager passes. In such case, pop LPPassManager from the
     289             : // stack. This will force assignPassManager() to create new
     290             : // LPPassManger as expected.
     291       44598 : void LoopPass::preparePassManager(PMStack &PMS) {
     292             : 
     293             :   // Find LPPassManager
     294       89196 :   while (!PMS.empty() &&
     295       44598 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     296           0 :     PMS.pop();
     297             : 
     298             :   // If this pass is destroying high level information that is used
     299             :   // by other passes that are managed by LPM then do not insert
     300             :   // this pass in current LPM. Use new LPPassManager.
     301       49476 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
     302        4878 :       !PMS.top()->preserveHigherLevelAnalysis(this))
     303          12 :     PMS.pop();
     304       44598 : }
     305             : 
     306             : /// Assign pass manager to manage this pass.
     307       44614 : void LoopPass::assignPassManager(PMStack &PMS,
     308             :                                  PassManagerType PreferredType) {
     309             :   // Find LPPassManager
     310       89228 :   while (!PMS.empty() &&
     311       44614 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     312           0 :     PMS.pop();
     313             : 
     314             :   LPPassManager *LPPM;
     315       44614 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
     316       20497 :     LPPM = (LPPassManager*)PMS.top();
     317             :   else {
     318             :     // Create new Loop Pass Manager if it does not exist.
     319             :     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
     320       24117 :     PMDataManager *PMD = PMS.top();
     321             : 
     322             :     // [1] Create new Loop Pass Manager
     323       24117 :     LPPM = new LPPassManager();
     324       48234 :     LPPM->populateInheritedAnalysis(PMS);
     325             : 
     326             :     // [2] Set up new manager's top level manager
     327       24117 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
     328       48234 :     TPM->addIndirectPassManager(LPPM);
     329             : 
     330             :     // [3] Assign manager to manage this new manager. This may create
     331             :     // and push new managers into PMS
     332       24117 :     Pass *P = LPPM->getAsPass();
     333       24117 :     TPM->schedulePass(P);
     334             : 
     335             :     // [4] Push new manager into PMS
     336       24117 :     PMS.push(LPPM);
     337             :   }
     338             : 
     339       44614 :   LPPM->add(this);
     340       44614 : }
     341             : 
     342       41933 : bool LoopPass::skipLoop(const Loop *L) const {
     343       83866 :   const Function *F = L->getHeader()->getParent();
     344       41933 :   if (!F)
     345             :     return false;
     346             :   // Check the opt bisect limit.
     347       41933 :   LLVMContext &Context = F->getContext();
     348       41933 :   if (!Context.getOptBisect().shouldRunPass(this, *L))
     349             :     return true;
     350             :   // Check for the OptimizeNone attribute.
     351       41743 :   if (F->hasFnAttribute(Attribute::OptimizeNone)) {
     352             :     // FIXME: Report this to dbgs() only once per function.
     353             :     DEBUG(dbgs() << "Skipping pass '" << getPassName()
     354             :           << "' in function " << F->getName() << "\n");
     355             :     // FIXME: Delete loop from pass manager's queue?
     356             :     return true;
     357             :   }
     358       41703 :   return false;
     359             : }
     360             : 
     361             : char LCSSAVerificationPass::ID = 0;
     362      317945 : INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
     363             :                 false, false)
     364             : 

Generated by: LCOV version 1.13