LCOV - code coverage report
Current view: top level - lib/Analysis - LoopPass.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 129 134 96.3 %
Date: 2018-07-13 00:08:38 Functions: 20 21 95.2 %
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          57 : 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          38 :       : LoopPass(ID), OS(OS), Banner(Banner) {}
      43             : 
      44          19 :   void getAnalysisUsage(AnalysisUsage &AU) const override {
      45             :     AU.setPreservesAll();
      46          19 :   }
      47             : 
      48           6 :   bool runOnLoop(Loop *L, LPPassManager &) override {
      49             :     auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; });
      50          12 :     if (BBI != L->blocks().end() &&
      51           6 :         isFunctionInPrintList((*BBI)->getParent()->getName())) {
      52           4 :       printLoop(*L, OS, Banner);
      53             :     }
      54           6 :     return false;
      55             :   }
      56             : 
      57           0 :   StringRef getPassName() const override { return "Print Loop IR"; }
      58             : };
      59             : 
      60             : char PrintLoopPassWrapper::ID = 0;
      61             : }
      62             : 
      63             : //===----------------------------------------------------------------------===//
      64             : // LPPassManager
      65             : //
      66             : 
      67             : char LPPassManager::ID = 0;
      68             : 
      69       34031 : LPPassManager::LPPassManager()
      70       34031 :   : FunctionPass(ID), PMDataManager() {
      71       34031 :   LI = nullptr;
      72       34031 :   CurrentLoop = nullptr;
      73       34031 : }
      74             : 
      75             : // Insert loop into loop nest (LoopInfo) and loop queue (LQ).
      76         260 : void LPPassManager::addLoop(Loop &L) {
      77         260 :   if (!L.getParentLoop()) {
      78             :     // This is the top level loop.
      79         398 :     LQ.push_front(&L);
      80         199 :     return;
      81             :   }
      82             : 
      83             :   // Insert L into the loop queue after the parent loop.
      84          87 :   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
      85          87 :     if (*I == L.getParentLoop()) {
      86             :       // deque does not support insert after.
      87             :       ++I;
      88         122 :       LQ.insert(I, 1, &L);
      89             :       return;
      90             :     }
      91             :   }
      92             : }
      93             : 
      94             : /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
      95             : /// all loop passes.
      96         408 : void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
      97             :                                                   BasicBlock *To, Loop *L) {
      98        1318 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
      99             :     LoopPass *LP = getContainedPass(Index);
     100         455 :     LP->cloneBasicBlockAnalysis(From, To, L);
     101             :   }
     102         408 : }
     103             : 
     104             : /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes.
     105         141 : void LPPassManager::deleteSimpleAnalysisValue(Value *V, Loop *L) {
     106             :   if (BasicBlock *BB = dyn_cast<BasicBlock>(V)) {
     107           0 :     for (Instruction &I : *BB) {
     108           0 :       deleteSimpleAnalysisValue(&I, L);
     109             :     }
     110             :   }
     111         459 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     112             :     LoopPass *LP = getContainedPass(Index);
     113         159 :     LP->deleteAnalysisValue(V, L);
     114             :   }
     115         141 : }
     116             : 
     117             : /// Invoke deleteAnalysisLoop hook for all passes.
     118         667 : void LPPassManager::deleteSimpleAnalysisLoop(Loop *L) {
     119        3481 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     120             :     LoopPass *LP = getContainedPass(Index);
     121        1407 :     LP->deleteAnalysisLoop(L);
     122             :   }
     123         667 : }
     124             : 
     125             : 
     126             : // Recurse through all subloops and all loops  into LQ.
     127       31210 : static void addLoopIntoQueue(Loop *L, std::deque<Loop *> &LQ) {
     128       31210 :   LQ.push_back(L);
     129       68054 :   for (Loop *I : reverse(*L))
     130        5634 :     addLoopIntoQueue(I, LQ);
     131       31210 : }
     132             : 
     133             : /// Pass Manager itself does not invalidate any analysis info.
     134       34031 : void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
     135             :   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
     136             :   // become part of LPPassManager.
     137             :   Info.addRequired<LoopInfoWrapperPass>();
     138             :   Info.addRequired<DominatorTreeWrapperPass>();
     139             :   Info.setPreservesAll();
     140       34031 : }
     141             : 
     142         431 : void LPPassManager::markLoopAsDeleted(Loop &L) {
     143             :   assert((&L == CurrentLoop || CurrentLoop->contains(&L)) &&
     144             :          "Must not delete loop outside the current loop tree!");
     145             :   // If this loop appears elsewhere within the queue, we also need to remove it
     146             :   // there. However, we have to be careful to not remove the back of the queue
     147             :   // as that is assumed to match the current loop.
     148             :   assert(LQ.back() == CurrentLoop && "Loop queue back isn't the current loop!");
     149        1724 :   LQ.erase(std::remove(LQ.begin(), LQ.end(), &L), LQ.end());
     150             : 
     151         431 :   if (&L == CurrentLoop) {
     152         431 :     CurrentLoopDeleted = true;
     153             :     // Add this loop back onto the back of the queue to preserve our invariants.
     154         862 :     LQ.push_back(&L);
     155             :   }
     156         431 : }
     157             : 
     158             : /// run - Execute all of the passes scheduled for execution.  Keep track of
     159             : /// whether any of the passes modifies the function, and if so, return true.
     160      374394 : bool LPPassManager::runOnFunction(Function &F) {
     161      374394 :   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
     162      374394 :   LI = &LIWP.getLoopInfo();
     163      374394 :   Module &M = *F.getParent();
     164             : #if 0
     165             :   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     166             : #endif
     167             :   bool Changed = false;
     168             : 
     169             :   // Collect inherited analysis from Module level pass manager.
     170      374394 :   populateInheritedAnalysis(TPM->activeStack);
     171             : 
     172             :   // Populate the loop queue in reverse program order. There is no clear need to
     173             :   // process sibling loops in either forward or reverse order. There may be some
     174             :   // advantage in deleting uses in a later loop before optimizing the
     175             :   // definitions in an earlier loop. If we find a clear reason to process in
     176             :   // forward order, then a forward variant of LoopPassManager should be created.
     177             :   //
     178             :   // Note that LoopInfo::iterator visits loops in reverse program
     179             :   // order. Here, reverse_iterator gives us a forward order, and the LoopQueue
     180             :   // reverses the order a third time by popping from the back.
     181      399970 :   for (Loop *L : reverse(*LI))
     182       25576 :     addLoopIntoQueue(L, LQ);
     183             : 
     184      374394 :   if (LQ.empty()) // No loops, skip calling finalizers
     185             :     return false;
     186             : 
     187             :   // Initialization
     188       50587 :   for (Loop *L : LQ) {
     189      142734 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     190             :       LoopPass *P = getContainedPass(Index);
     191       55762 :       Changed |= P->doInitialization(L, *this);
     192             :     }
     193             :   }
     194             : 
     195             :   // Walk Loops
     196       82315 :   while (!LQ.empty()) {
     197       31469 :     CurrentLoopDeleted = false;
     198       31469 :     CurrentLoop = LQ.back();
     199             : 
     200             :     // Run all passes on the current Loop.
     201      142433 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     202             :       LoopPass *P = getContainedPass(Index);
     203             : 
     204      111826 :       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
     205       55913 :                    CurrentLoop->getHeader()->getName());
     206       55913 :       dumpRequiredSet(P);
     207             : 
     208       55913 :       initializeAnalysisImpl(P);
     209             : 
     210             :       {
     211      111826 :         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
     212       55913 :         TimeRegion PassTimer(getPassTimer(P));
     213       55913 :         unsigned InstrCount = initSizeRemarkInfo(M);
     214       55913 :         Changed |= P->runOnLoop(CurrentLoop, *this);
     215       55913 :         emitInstrCountChangedRemark(P, M, InstrCount);
     216             :       }
     217             : 
     218       55913 :       if (Changed)
     219       38155 :         dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG,
     220       19293 :                      CurrentLoopDeleted ? "<deleted loop>"
     221       18862 :                                         : CurrentLoop->getName());
     222       55913 :       dumpPreservedSet(P);
     223             : 
     224       55913 :       if (CurrentLoopDeleted) {
     225             :         // Notify passes that the loop is being deleted.
     226         431 :         deleteSimpleAnalysisLoop(CurrentLoop);
     227             :       } else {
     228             :         // Manually check that this loop is still healthy. This is done
     229             :         // instead of relying on LoopInfo::verifyLoop since LoopInfo
     230             :         // is a function pass and it's really expensive to verify every
     231             :         // loop in the function every time. That level of checking can be
     232             :         // enabled with the -verify-loop-info option.
     233             :         {
     234       55482 :           TimeRegion PassTimer(getPassTimer(&LIWP));
     235       55482 :           CurrentLoop->verifyLoop();
     236             :         }
     237             :         // Here we apply same reasoning as in the above case. Only difference
     238             :         // is that LPPassManager might run passes which do not require LCSSA
     239             :         // form (LoopPassPrinter for example). We should skip verification for
     240             :         // such passes.
     241             :         // FIXME: Loop-sink currently break LCSSA. Fix it and reenable the
     242             :         // verification!
     243             : #if 0
     244             :         if (mustPreserveAnalysisID(LCSSAVerificationPass::ID))
     245             :           assert(CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI));
     246             : #endif
     247             : 
     248             :         // Then call the regular verifyAnalysis functions.
     249       55482 :         verifyPreservedAnalysis(P);
     250             : 
     251       55482 :         F.getContext().yield();
     252             :       }
     253             : 
     254       55913 :       removeNotPreservedAnalysis(P);
     255       55913 :       recordAvailableAnalysis(P);
     256      111395 :       removeDeadPasses(P,
     257       55913 :                        CurrentLoopDeleted ? "<deleted>"
     258      110964 :                                           : CurrentLoop->getHeader()->getName(),
     259             :                        ON_LOOP_MSG);
     260             : 
     261       55913 :       if (CurrentLoopDeleted)
     262             :         // Do not run other passes on this loop.
     263             :         break;
     264             :     }
     265             : 
     266             :     // If the loop was deleted, release all the loop passes. This frees up
     267             :     // some memory, and avoids trouble with the pass manager trying to call
     268             :     // verifyAnalysis on them.
     269       31469 :     if (CurrentLoopDeleted) {
     270        2751 :       for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     271             :         Pass *P = getContainedPass(Index);
     272        2320 :         freePass(P, "<deleted>", ON_LOOP_MSG);
     273             :       }
     274             :     }
     275             : 
     276             :     // Pop the loop from queue after running all passes.
     277       31469 :     LQ.pop_back();
     278             :   }
     279             : 
     280             :   // Finalization
     281       88861 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     282             :     LoopPass *P = getContainedPass(Index);
     283       34742 :     Changed |= P->doFinalization();
     284             :   }
     285             : 
     286             :   return Changed;
     287             : }
     288             : 
     289             : /// Print passes managed by this manager
     290          64 : void LPPassManager::dumpPassStructure(unsigned Offset) {
     291          64 :   errs().indent(Offset*2) << "Loop Pass Manager\n";
     292         288 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     293             :     Pass *P = getContainedPass(Index);
     294         112 :     P->dumpPassStructure(Offset + 1);
     295         112 :     dumpLastUses(P, Offset+1);
     296             :   }
     297          64 : }
     298             : 
     299             : 
     300             : //===----------------------------------------------------------------------===//
     301             : // LoopPass
     302             : 
     303          19 : Pass *LoopPass::createPrinterPass(raw_ostream &O,
     304             :                                   const std::string &Banner) const {
     305          38 :   return new PrintLoopPassWrapper(O, Banner);
     306             : }
     307             : 
     308             : // Check if this pass is suitable for the current LPPassManager, if
     309             : // available. This pass P is not suitable for a LPPassManager if P
     310             : // is not preserving higher level analysis info used by other
     311             : // LPPassManager passes. In such case, pop LPPassManager from the
     312             : // stack. This will force assignPassManager() to create new
     313             : // LPPassManger as expected.
     314       59158 : void LoopPass::preparePassManager(PMStack &PMS) {
     315             : 
     316             :   // Find LPPassManager
     317      118316 :   while (!PMS.empty() &&
     318       59158 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     319           0 :     PMS.pop();
     320             : 
     321             :   // If this pass is destroying high level information that is used
     322             :   // by other passes that are managed by LPM then do not insert
     323             :   // this pass in current LPM. Use new LPPassManager.
     324       65146 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager &&
     325        5988 :       !PMS.top()->preserveHigherLevelAnalysis(this))
     326          29 :     PMS.pop();
     327       59158 : }
     328             : 
     329             : /// Assign pass manager to manage this pass.
     330       59177 : void LoopPass::assignPassManager(PMStack &PMS,
     331             :                                  PassManagerType PreferredType) {
     332             :   // Find LPPassManager
     333      118354 :   while (!PMS.empty() &&
     334       59177 :          PMS.top()->getPassManagerType() > PMT_LoopPassManager)
     335           0 :     PMS.pop();
     336             : 
     337             :   LPPassManager *LPPM;
     338       59177 :   if (PMS.top()->getPassManagerType() == PMT_LoopPassManager)
     339       25146 :     LPPM = (LPPassManager*)PMS.top();
     340             :   else {
     341             :     // Create new Loop Pass Manager if it does not exist.
     342             :     assert (!PMS.empty() && "Unable to create Loop Pass Manager");
     343             :     PMDataManager *PMD = PMS.top();
     344             : 
     345             :     // [1] Create new Loop Pass Manager
     346       34031 :     LPPM = new LPPassManager();
     347             :     LPPM->populateInheritedAnalysis(PMS);
     348             : 
     349             :     // [2] Set up new manager's top level manager
     350       34031 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
     351       34031 :     TPM->addIndirectPassManager(LPPM);
     352             : 
     353             :     // [3] Assign manager to manage this new manager. This may create
     354             :     // and push new managers into PMS
     355       34031 :     Pass *P = LPPM->getAsPass();
     356       34031 :     TPM->schedulePass(P);
     357             : 
     358             :     // [4] Push new manager into PMS
     359       34031 :     PMS.push(LPPM);
     360             :   }
     361             : 
     362       59177 :   LPPM->add(this);
     363       59177 : }
     364             : 
     365       48273 : bool LoopPass::skipLoop(const Loop *L) const {
     366       48273 :   const Function *F = L->getHeader()->getParent();
     367       48273 :   if (!F)
     368             :     return false;
     369             :   // Check the opt bisect limit.
     370       48273 :   LLVMContext &Context = F->getContext();
     371       48273 :   if (!Context.getOptPassGate().shouldRunPass(this, *L))
     372             :     return true;
     373             :   // Check for the OptimizeNone attribute.
     374       48083 :   if (F->hasFnAttribute(Attribute::OptimizeNone)) {
     375             :     // FIXME: Report this to dbgs() only once per function.
     376             :     LLVM_DEBUG(dbgs() << "Skipping pass '" << getPassName() << "' in function "
     377             :                       << F->getName() << "\n");
     378             :     // FIXME: Delete loop from pass manager's queue?
     379             :     return true;
     380             :   }
     381       48030 :   return false;
     382             : }
     383             : 
     384             : char LCSSAVerificationPass::ID = 0;
     385      338330 : INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
     386             :                 false, false)

Generated by: LCOV version 1.13