LCOV - code coverage report
Current view: top level - lib/IR - LegacyPassManager.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 716 819 87.4 %
Date: 2017-09-14 15:23:50 Functions: 97 122 79.5 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===//
       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 the legacy LLVM Pass Manager infrastructure.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/IR/LegacyPassManager.h"
      15             : #include "llvm/ADT/Statistic.h"
      16             : #include "llvm/IR/IRPrintingPasses.h"
      17             : #include "llvm/IR/LLVMContext.h"
      18             : #include "llvm/IR/LegacyPassManagers.h"
      19             : #include "llvm/IR/LegacyPassNameParser.h"
      20             : #include "llvm/IR/Module.h"
      21             : #include "llvm/Support/Chrono.h"
      22             : #include "llvm/Support/CommandLine.h"
      23             : #include "llvm/Support/Debug.h"
      24             : #include "llvm/Support/Error.h"
      25             : #include "llvm/Support/ErrorHandling.h"
      26             : #include "llvm/Support/ManagedStatic.h"
      27             : #include "llvm/Support/Mutex.h"
      28             : #include "llvm/Support/Timer.h"
      29             : #include "llvm/Support/raw_ostream.h"
      30             : #include <algorithm>
      31             : #include <map>
      32             : #include <unordered_set>
      33             : using namespace llvm;
      34             : using namespace llvm::legacy;
      35             : 
      36             : // See PassManagers.h for Pass Manager infrastructure overview.
      37             : 
      38             : //===----------------------------------------------------------------------===//
      39             : // Pass debugging information.  Often it is useful to find out what pass is
      40             : // running when a crash occurs in a utility.  When this library is compiled with
      41             : // debugging on, a command line option (--debug-pass) is enabled that causes the
      42             : // pass name to be printed before it executes.
      43             : //
      44             : 
      45             : namespace {
      46             : // Different debug levels that can be enabled...
      47             : enum PassDebugLevel {
      48             :   Disabled, Arguments, Structure, Executions, Details
      49             : };
      50             : }
      51             : 
      52             : static cl::opt<enum PassDebugLevel>
      53       72330 : PassDebugging("debug-pass", cl::Hidden,
      54      216990 :                   cl::desc("Print PassManager debugging information"),
      55      795630 :                   cl::values(
      56             :   clEnumVal(Disabled  , "disable debug output"),
      57             :   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
      58             :   clEnumVal(Structure , "print pass structure before run()"),
      59             :   clEnumVal(Executions, "print pass name before it is executed"),
      60       72330 :   clEnumVal(Details   , "print pass details when it is executed")));
      61             : 
      62             : namespace {
      63             : typedef llvm::cl::list<const llvm::PassInfo *, bool, PassNameParser>
      64             : PassOptionList;
      65             : }
      66             : 
      67             : // Print IR out before/after specified passes.
      68             : static PassOptionList
      69       72330 : PrintBefore("print-before",
      70      216990 :             llvm::cl::desc("Print IR before specified passes"),
      71      216990 :             cl::Hidden);
      72             : 
      73             : static PassOptionList
      74       72330 : PrintAfter("print-after",
      75      216990 :            llvm::cl::desc("Print IR after specified passes"),
      76      216990 :            cl::Hidden);
      77             : 
      78             : static cl::opt<bool>
      79       72330 : PrintBeforeAll("print-before-all",
      80      216990 :                llvm::cl::desc("Print IR before each pass"),
      81      289320 :                cl::init(false));
      82             : static cl::opt<bool>
      83       72330 : PrintAfterAll("print-after-all",
      84      216990 :               llvm::cl::desc("Print IR after each pass"),
      85      289320 :               cl::init(false));
      86             : 
      87             : static cl::list<std::string>
      88      289320 :     PrintFuncsList("filter-print-funcs", cl::value_desc("function names"),
      89      216990 :                    cl::desc("Only print IR for functions whose name "
      90             :                             "match this for all print-[before|after][-all] "
      91             :                             "options"),
      92      216990 :                    cl::CommaSeparated);
      93             : 
      94             : /// This is a helper to determine whether to print IR before or
      95             : /// after a pass.
      96             : 
      97     3045648 : static bool ShouldPrintBeforeOrAfterPass(const PassInfo *PI,
      98             :                                          PassOptionList &PassesToPrint) {
      99    12183865 :   for (auto *PassInf : PassesToPrint) {
     100        1288 :     if (PassInf)
     101        1288 :       if (PassInf->getPassArgument() == PI->getPassArgument()) {
     102             :         return true;
     103             :       }
     104             :   }
     105             :   return false;
     106             : }
     107             : 
     108             : /// This is a utility to check whether a pass should have IR dumped
     109             : /// before it.
     110             : static bool ShouldPrintBeforePass(const PassInfo *PI) {
     111     1523021 :   return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PI, PrintBefore);
     112             : }
     113             : 
     114             : /// This is a utility to check whether a pass should have IR dumped
     115             : /// after it.
     116             : static bool ShouldPrintAfterPass(const PassInfo *PI) {
     117     1523017 :   return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PI, PrintAfter);
     118             : }
     119             : 
     120       11823 : bool llvm::isFunctionInPrintList(StringRef FunctionName) {
     121             :   static std::unordered_set<std::string> PrintFuncNames(PrintFuncsList.begin(),
     122       62583 :                                                         PrintFuncsList.end());
     123       35761 :   return PrintFuncNames.empty() || PrintFuncNames.count(FunctionName);
     124             : }
     125             : /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
     126             : /// or higher is specified.
     127      500454 : bool PMDataManager::isPassDebuggingExecutionsOrMore() const {
     128      500454 :   return PassDebugging >= Executions;
     129             : }
     130             : 
     131             : 
     132             : 
     133             : 
     134           0 : void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
     135           0 :   if (!V && !M)
     136           0 :     OS << "Releasing pass '";
     137             :   else
     138           0 :     OS << "Running pass '";
     139             : 
     140           0 :   OS << P->getPassName() << "'";
     141             : 
     142           0 :   if (M) {
     143           0 :     OS << " on module '" << M->getModuleIdentifier() << "'.\n";
     144           0 :     return;
     145             :   }
     146           0 :   if (!V) {
     147             :     OS << '\n';
     148             :     return;
     149             :   }
     150             : 
     151           0 :   OS << " on ";
     152           0 :   if (isa<Function>(V))
     153           0 :     OS << "function";
     154           0 :   else if (isa<BasicBlock>(V))
     155           0 :     OS << "basic block";
     156             :   else
     157           0 :     OS << "value";
     158             : 
     159           0 :   OS << " '";
     160           0 :   V->printAsOperand(OS, /*PrintTy=*/false, M);
     161           0 :   OS << "'\n";
     162             : }
     163             : 
     164             : 
     165             : namespace {
     166             : //===----------------------------------------------------------------------===//
     167             : // BBPassManager
     168             : //
     169             : /// BBPassManager manages BasicBlockPass. It batches all the
     170             : /// pass together and sequence them to process one basic block before
     171             : /// processing next basic block.
     172         454 : class BBPassManager : public PMDataManager, public FunctionPass {
     173             : 
     174             : public:
     175             :   static char ID;
     176             :   explicit BBPassManager()
     177         468 :     : PMDataManager(), FunctionPass(ID) {}
     178             : 
     179             :   /// Execute all of the passes scheduled for execution.  Keep track of
     180             :   /// whether any of the passes modifies the function, and if so, return true.
     181             :   bool runOnFunction(Function &F) override;
     182             : 
     183             :   /// Pass Manager itself does not invalidate any analysis info.
     184         234 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     185         234 :     Info.setPreservesAll();
     186         234 :   }
     187             : 
     188             :   bool doInitialization(Module &M) override;
     189             :   bool doInitialization(Function &F);
     190             :   bool doFinalization(Module &M) override;
     191             :   bool doFinalization(Function &F);
     192             : 
     193         234 :   PMDataManager *getAsPMDataManager() override { return this; }
     194           0 :   Pass *getAsPass() override { return this; }
     195             : 
     196           0 :   StringRef getPassName() const override { return "BasicBlock Pass Manager"; }
     197             : 
     198             :   // Print passes managed by this manager
     199           0 :   void dumpPassStructure(unsigned Offset) override {
     200           0 :     dbgs().indent(Offset*2) << "BasicBlockPass Manager\n";
     201           0 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     202           0 :       BasicBlockPass *BP = getContainedPass(Index);
     203           0 :       BP->dumpPassStructure(Offset + 1);
     204           0 :       dumpLastUses(BP, Offset+1);
     205             :     }
     206           0 :   }
     207             : 
     208             :   BasicBlockPass *getContainedPass(unsigned N) {
     209             :     assert(N < PassVector.size() && "Pass number out of range!");
     210        7828 :     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
     211             :     return BP;
     212             :   }
     213             : 
     214         233 :   PassManagerType getPassManagerType() const override {
     215         233 :     return PMT_BasicBlockPassManager;
     216             :   }
     217             : };
     218             : 
     219             : char BBPassManager::ID = 0;
     220             : } // End anonymous namespace
     221             : 
     222             : namespace llvm {
     223             : namespace legacy {
     224             : //===----------------------------------------------------------------------===//
     225             : // FunctionPassManagerImpl
     226             : //
     227             : /// FunctionPassManagerImpl manages FPPassManagers
     228       17278 : class FunctionPassManagerImpl : public Pass,
     229             :                                 public PMDataManager,
     230             :                                 public PMTopLevelManager {
     231             :   virtual void anchor();
     232             : private:
     233             :   bool wasRun;
     234             : public:
     235             :   static char ID;
     236        8650 :   explicit FunctionPassManagerImpl() :
     237             :     Pass(PT_PassManager, ID), PMDataManager(),
     238       25950 :     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
     239             : 
     240             :   /// \copydoc FunctionPassManager::add()
     241             :   void add(Pass *P) {
     242       23786 :     schedulePass(P);
     243             :   }
     244             : 
     245             :   /// createPrinterPass - Get a function printer pass.
     246           0 :   Pass *createPrinterPass(raw_ostream &O,
     247             :                           const std::string &Banner) const override {
     248           0 :     return createPrintFunctionPass(O, Banner);
     249             :   }
     250             : 
     251             :   // Prepare for running an on the fly pass, freeing memory if needed
     252             :   // from a previous run.
     253             :   void releaseMemoryOnTheFly();
     254             : 
     255             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     256             :   /// whether any of the passes modifies the module, and if so, return true.
     257             :   bool run(Function &F);
     258             : 
     259             :   /// doInitialization - Run all of the initializers for the function passes.
     260             :   ///
     261             :   bool doInitialization(Module &M) override;
     262             : 
     263             :   /// doFinalization - Run all of the finalizers for the function passes.
     264             :   ///
     265             :   bool doFinalization(Module &M) override;
     266             : 
     267             : 
     268       13760 :   PMDataManager *getAsPMDataManager() override { return this; }
     269           0 :   Pass *getAsPass() override { return this; }
     270       13515 :   PassManagerType getTopLevelPassManagerType() override {
     271       13515 :     return PMT_FunctionPassManager;
     272             :   }
     273             : 
     274             :   /// Pass Manager itself does not invalidate any analysis info.
     275           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     276           0 :     Info.setPreservesAll();
     277           0 :   }
     278             : 
     279             :   FPPassManager *getContainedManager(unsigned N) {
     280             :     assert(N < PassManagers.size() && "Pass number out of range!");
     281      458884 :     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
     282             :     return FP;
     283             :   }
     284             : };
     285             : 
     286           0 : void FunctionPassManagerImpl::anchor() {}
     287             : 
     288             : char FunctionPassManagerImpl::ID = 0;
     289             : } // End of legacy namespace
     290             : } // End of llvm namespace
     291             : 
     292             : namespace {
     293             : //===----------------------------------------------------------------------===//
     294             : // MPPassManager
     295             : //
     296             : /// MPPassManager manages ModulePasses and function pass managers.
     297             : /// It batches all Module passes and function pass managers together and
     298             : /// sequences them to process one module.
     299             : class MPPassManager : public Pass, public PMDataManager {
     300             : public:
     301             :   static char ID;
     302       37066 :   explicit MPPassManager() :
     303      111198 :     Pass(PT_PassManager, ID), PMDataManager() { }
     304             : 
     305             :   // Delete on the fly managers.
     306      147580 :   ~MPPassManager() override {
     307      113625 :     for (auto &OnTheFlyManager : OnTheFlyManagers) {
     308        2940 :       FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
     309        2940 :       delete FPP;
     310             :     }
     311       73791 :   }
     312             : 
     313             :   /// createPrinterPass - Get a module printer pass.
     314           0 :   Pass *createPrinterPass(raw_ostream &O,
     315             :                           const std::string &Banner) const override {
     316           0 :     return createPrintModulePass(O, Banner);
     317             :   }
     318             : 
     319             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     320             :   /// whether any of the passes modifies the module, and if so, return true.
     321             :   bool runOnModule(Module &M);
     322             : 
     323             :   using llvm::Pass::doInitialization;
     324             :   using llvm::Pass::doFinalization;
     325             : 
     326             :   /// Pass Manager itself does not invalidate any analysis info.
     327           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     328           0 :     Info.setPreservesAll();
     329           0 :   }
     330             : 
     331             :   /// Add RequiredPass into list of lower level passes required by pass P.
     332             :   /// RequiredPass is run on the fly by Pass Manager when P requests it
     333             :   /// through getAnalysis interface.
     334             :   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
     335             : 
     336             :   /// Return function pass corresponding to PassInfo PI, that is
     337             :   /// required by module pass MP. Instantiate analysis pass, by using
     338             :   /// its runOnFunction() for function F.
     339             :   Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override;
     340             : 
     341           0 :   StringRef getPassName() const override { return "Module Pass Manager"; }
     342             : 
     343           0 :   PMDataManager *getAsPMDataManager() override { return this; }
     344     2800941 :   Pass *getAsPass() override { return this; }
     345             : 
     346             :   // Print passes managed by this manager
     347          31 :   void dumpPassStructure(unsigned Offset) override {
     348          31 :     dbgs().indent(Offset*2) << "ModulePass Manager\n";
     349         546 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     350         242 :       ModulePass *MP = getContainedPass(Index);
     351         242 :       MP->dumpPassStructure(Offset + 1);
     352             :       std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I =
     353         726 :         OnTheFlyManagers.find(MP);
     354         484 :       if (I != OnTheFlyManagers.end())
     355          15 :         I->second->dumpPassStructure(Offset + 2);
     356         242 :       dumpLastUses(MP, Offset+1);
     357             :     }
     358          31 :   }
     359             : 
     360             :   ModulePass *getContainedPass(unsigned N) {
     361             :     assert(N < PassVector.size() && "Pass number out of range!");
     362      906576 :     return static_cast<ModulePass *>(PassVector[N]);
     363             :   }
     364             : 
     365      332999 :   PassManagerType getPassManagerType() const override {
     366      332999 :     return PMT_ModulePassManager;
     367             :   }
     368             : 
     369             :  private:
     370             :   /// Collection of on the fly FPPassManagers. These managers manage
     371             :   /// function passes that are required by module passes.
     372             :   std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
     373             : };
     374             : 
     375             : char MPPassManager::ID = 0;
     376             : } // End anonymous namespace
     377             : 
     378             : namespace llvm {
     379             : namespace legacy {
     380             : //===----------------------------------------------------------------------===//
     381             : // PassManagerImpl
     382             : //
     383             : 
     384             : /// PassManagerImpl manages MPPassManagers
     385       73792 : class PassManagerImpl : public Pass,
     386             :                         public PMDataManager,
     387             :                         public PMTopLevelManager {
     388             :   virtual void anchor();
     389             : 
     390             : public:
     391             :   static char ID;
     392       37066 :   explicit PassManagerImpl() :
     393             :     Pass(PT_PassManager, ID), PMDataManager(),
     394      111198 :                               PMTopLevelManager(new MPPassManager()) {}
     395             : 
     396             :   /// \copydoc PassManager::add()
     397             :   void add(Pass *P) {
     398     1678070 :     schedulePass(P);
     399             :   }
     400             : 
     401             :   /// createPrinterPass - Get a module printer pass.
     402           0 :   Pass *createPrinterPass(raw_ostream &O,
     403             :                           const std::string &Banner) const override {
     404           0 :     return createPrintModulePass(O, Banner);
     405             :   }
     406             : 
     407             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     408             :   /// whether any of the passes modifies the module, and if so, return true.
     409             :   bool run(Module &M);
     410             : 
     411             :   using llvm::Pass::doInitialization;
     412             :   using llvm::Pass::doFinalization;
     413             : 
     414             :   /// Pass Manager itself does not invalidate any analysis info.
     415           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     416           0 :     Info.setPreservesAll();
     417           0 :   }
     418             : 
     419      232004 :   PMDataManager *getAsPMDataManager() override { return this; }
     420           0 :   Pass *getAsPass() override { return this; }
     421     2711645 :   PassManagerType getTopLevelPassManagerType() override {
     422     2711645 :     return PMT_ModulePassManager;
     423             :   }
     424             : 
     425             :   MPPassManager *getContainedManager(unsigned N) {
     426             :     assert(N < PassManagers.size() && "Pass number out of range!");
     427       73852 :     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
     428             :     return MP;
     429             :   }
     430             : };
     431             : 
     432           0 : void PassManagerImpl::anchor() {}
     433             : 
     434             : char PassManagerImpl::ID = 0;
     435             : } // End of legacy namespace
     436             : } // End of llvm namespace
     437             : 
     438             : namespace {
     439             : 
     440             : //===----------------------------------------------------------------------===//
     441             : /// TimingInfo Class - This class is used to calculate information about the
     442             : /// amount of time each pass takes to execute.  This only happens when
     443             : /// -time-passes is enabled on the command line.
     444             : ///
     445             : 
     446             : static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex;
     447             : 
     448             : class TimingInfo {
     449             :   DenseMap<Pass*, Timer*> TimingData;
     450             :   TimerGroup TG;
     451             : public:
     452             :   // Use 'create' member to get this.
     453          40 :   TimingInfo() : TG("pass", "... Pass execution timing report ...") {}
     454             : 
     455             :   // TimingDtor - Print out information about timing information
     456          30 :   ~TimingInfo() {
     457             :     // Delete all of the timers, which accumulate their info into the
     458             :     // TimerGroup.
     459         996 :     for (auto &I : TimingData)
     460         966 :       delete I.second;
     461             :     // TimerGroup is deleted next, printing the report.
     462          10 :   }
     463             : 
     464             :   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
     465             :   // to a non-null value (if the -time-passes option is enabled) or it leaves it
     466             :   // null.  It may be called multiple times.
     467             :   static void createTheTimeInfo();
     468             : 
     469             :   // print - Prints out timing information and then resets the timers.
     470           0 :   void print() {
     471           0 :     TG.print(*CreateInfoOutputFile());
     472           0 :   }
     473             : 
     474             :   /// getPassTimer - Return the timer for the specified pass if it exists.
     475        2088 :   Timer *getPassTimer(Pass *P) {
     476        2088 :     if (P->getAsPMDataManager())
     477             :       return nullptr;
     478             : 
     479        4052 :     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
     480        4052 :     Timer *&T = TimingData[P];
     481        2026 :     if (!T) {
     482         966 :       StringRef PassName = P->getPassName();
     483         966 :       T = new Timer(PassName, PassName, TG);
     484             :     }
     485        2026 :     return T;
     486             :   }
     487             : };
     488             : 
     489             : } // End of anon namespace
     490             : 
     491             : static TimingInfo *TheTimeInfo;
     492             : 
     493             : //===----------------------------------------------------------------------===//
     494             : // PMTopLevelManager implementation
     495             : 
     496             : /// Initialize top level manager. Create first pass manager.
     497      548592 : PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
     498       91432 :   PMDM->setTopLevelManager(this);
     499       45716 :   addPassManager(PMDM);
     500       45716 :   activeStack.push(PMDM);
     501       45716 : }
     502             : 
     503             : /// Set pass P as the last user of the given analysis passes.
     504             : void
     505    19223753 : PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
     506    19223753 :   unsigned PDepth = 0;
     507    19223753 :   if (P->getResolver())
     508    16401430 :     PDepth = P->getResolver()->getPMDataManager().getDepth();
     509             : 
     510    48276827 :   for (Pass *AP : AnalysisPasses) {
     511    19658587 :     LastUser[AP] = P;
     512             : 
     513     9829260 :     if (P == AP)
     514     2687154 :       continue;
     515             : 
     516             :     // Update the last users of passes that are required transitive by AP.
     517     7142106 :     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
     518     7142110 :     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
     519    14284277 :     SmallVector<Pass *, 12> LastUses;
     520    14284277 :     SmallVector<Pass *, 12> LastPMUses;
     521    22447098 :     for (AnalysisID ID : IDs) {
     522     1020766 :       Pass *AnalysisPass = findAnalysisPass(ID);
     523             :       assert(AnalysisPass && "Expected analysis pass to exist.");
     524     1020768 :       AnalysisResolver *AR = AnalysisPass->getResolver();
     525             :       assert(AR && "Expected analysis resolver to exist.");
     526     1020768 :       unsigned APDepth = AR->getPMDataManager().getDepth();
     527             : 
     528     1020768 :       if (PDepth == APDepth)
     529      798122 :         LastUses.push_back(AnalysisPass);
     530      222646 :       else if (PDepth > APDepth)
     531      222646 :         LastPMUses.push_back(AnalysisPass);
     532             :     }
     533             : 
     534     7142112 :     setLastUser(LastUses, P);
     535             : 
     536             :     // If this pass has a corresponding pass manager, push higher level
     537             :     // analysis to this pass manager.
     538     7142119 :     if (P->getResolver())
     539    14253410 :       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
     540             : 
     541             : 
     542             :     // If AP is the last user of other passes then make P last user of
     543             :     // such passes.
     544   619744623 :     for (auto LU : LastUser) {
     545   598318163 :       if (LU.second == AP)
     546             :         // DenseMap iterator is not invalidated here because
     547             :         // this is just updating existing entries.
     548     1262766 :         LastUser[LU.first] = P;
     549             :     }
     550             :   }
     551    19223747 : }
     552             : 
     553             : /// Collect passes whose last user is P
     554    26107824 : void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
     555             :                                         Pass *P) {
     556             :   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
     557    26107824 :     InversedLastUser.find(P);
     558    78323487 :   if (DMI == InversedLastUser.end())
     559    12426114 :     return;
     560             : 
     561    13681715 :   SmallPtrSet<Pass *, 8> &LU = DMI->second;
     562    39750918 :   for (Pass *LUP : LU) {
     563    26069203 :     LastUses.push_back(LUP);
     564             :   }
     565             : 
     566             : }
     567             : 
     568    68135437 : AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
     569    68135437 :   AnalysisUsage *AnUsage = nullptr;
     570    68135437 :   auto DMI = AnUsageMap.find(P);
     571   204406944 :   if (DMI != AnUsageMap.end())
     572    65109473 :     AnUsage = DMI->second;
     573             :   else {
     574             :     // Look up the analysis usage from the pass instance (different instances
     575             :     // of the same pass can produce different results), but unique the
     576             :     // resulting object to reduce memory usage.  This helps to greatly reduce
     577             :     // memory usage when we have many instances of only a few pass types
     578             :     // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
     579             :     // of dependencies.
     580     6052346 :     AnalysisUsage AU;
     581     3026175 :     P->getAnalysisUsage(AU);
     582             :     
     583     3026178 :     AUFoldingSetNode* Node = nullptr;
     584     6052349 :     FoldingSetNodeID ID;
     585     3026178 :     AUFoldingSetNode::Profile(ID, AU);
     586     3026178 :     void *IP = nullptr;
     587     6052355 :     if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
     588             :       Node = N;
     589             :     else {
     590     4108515 :       Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
     591     1369505 :       UniqueAnalysisUsages.InsertNode(Node, IP);
     592             :     }
     593             :     assert(Node && "cached analysis usage must be non null");
     594             : 
     595     6052348 :     AnUsageMap[P] = &Node->AU;
     596     3026171 :     AnUsage = &Node->AU;
     597             :   }
     598    68135645 :   return AnUsage;
     599             : }
     600             : 
     601             : /// Schedule pass P for execution. Make sure that passes required by
     602             : /// P are run before P is run. Update analysis info maintained by
     603             : /// the manager. Remove dead passes. This is a recursive function.
     604     2976057 : void PMTopLevelManager::schedulePass(Pass *P) {
     605             : 
     606             :   // TODO : Allocate function manager for this pass, other wise required set
     607             :   // may be inserted into previous function manager
     608             : 
     609             :   // Give pass a chance to prepare the stage.
     610     2976057 :   P->preparePassManager(activeStack);
     611             : 
     612             :   // If P is an analysis pass and it is available then do not
     613             :   // generate the analysis again. Stale analysis info should not be
     614             :   // available at this point.
     615     2976057 :   const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
     616     2976052 :   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
     617        5536 :     delete P;
     618             :     return;
     619             :   }
     620             : 
     621     2970515 :   AnalysisUsage *AnUsage = findAnalysisUsage(P);
     622             : 
     623     2970515 :   bool checkAnalysis = true;
     624     6052666 :   while (checkAnalysis) {
     625     3082145 :     checkAnalysis = false;
     626             : 
     627     3082145 :     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
     628    15338876 :     for (const AnalysisID ID : RequiredSet) {
     629             : 
     630     6092430 :       Pass *AnalysisPass = findAnalysisPass(ID);
     631     6092452 :       if (!AnalysisPass) {
     632     1239231 :         const PassInfo *PI = findAnalysisPassInfo(ID);
     633             : 
     634     1239229 :         if (!PI) {
     635             :           // Pass P is not in the global PassRegistry
     636           0 :           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
     637           0 :           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
     638           0 :           dbgs() << "Required Passes:" << "\n";
     639           0 :           for (const AnalysisID ID2 : RequiredSet) {
     640           0 :             if (ID == ID2)
     641             :               break;
     642           0 :             Pass *AnalysisPass2 = findAnalysisPass(ID2);
     643           0 :             if (AnalysisPass2) {
     644           0 :               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
     645             :             } else {
     646           0 :               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
     647           0 :               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
     648           0 :               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
     649             :             }
     650             :           }
     651             :         }
     652             : 
     653             :         assert(PI && "Expected required passes to be initialized");
     654     2478458 :         AnalysisPass = PI->createPass();
     655     2478459 :         if (P->getPotentialPassManagerType () ==
     656     1239229 :             AnalysisPass->getPotentialPassManagerType())
     657             :           // Schedule analysis pass that is managed by the same pass manager.
     658     1046802 :           schedulePass(AnalysisPass);
     659      384856 :         else if (P->getPotentialPassManagerType () >
     660      192428 :                  AnalysisPass->getPotentialPassManagerType()) {
     661             :           // Schedule analysis pass that is managed by a new manager.
     662      189453 :           schedulePass(AnalysisPass);
     663             :           // Recheck analysis passes to ensure that required analyses that
     664             :           // are already checked are still available.
     665      189453 :           checkAnalysis = true;
     666             :         } else
     667             :           // Do not schedule this analysis. Lower level analysis
     668             :           // passes are run on the fly.
     669        2975 :           delete AnalysisPass;
     670             :       }
     671             :     }
     672             :   }
     673             : 
     674             :   // Now all required passes are available.
     675     2970521 :   if (ImmutablePass *IP = P->getAsImmutablePass()) {
     676             :     // P is a immutable pass and it will be managed by this
     677             :     // top level manager. Set up analysis resolver to connect them.
     678      245764 :     PMDataManager *DM = getAsPMDataManager();
     679      491528 :     AnalysisResolver *AR = new AnalysisResolver(*DM);
     680      245764 :     P->setResolver(AR);
     681      245764 :     DM->initializeAnalysisImpl(P);
     682      245764 :     addImmutablePass(IP);
     683      245764 :     DM->recordAvailableAnalysis(IP);
     684      245764 :     return;
     685             :   }
     686             : 
     687     2724759 :   if (PI && !PI->isAnalysis() && ShouldPrintBeforePass(PI)) {
     688           4 :     Pass *PP = P->createPrinterPass(
     689          24 :         dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str());
     690           4 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     691             :   }
     692             : 
     693             :   // Add the requested pass to the best available pass manager.
     694     2724759 :   P->assignPassManager(activeStack, getTopLevelPassManagerType());
     695             : 
     696     2724751 :   if (PI && !PI->isAnalysis() && ShouldPrintAfterPass(PI)) {
     697         398 :     Pass *PP = P->createPrinterPass(
     698        2388 :         dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str());
     699         398 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     700             :   }
     701             : }
     702             : 
     703             : /// Find the pass that implements Analysis AID. Search immutable
     704             : /// passes and all pass managers. If desired pass is not found
     705             : /// then return NULL.
     706    54710712 : Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
     707             :   // For immutable passes we have a direct mapping from ID to pass, so check
     708             :   // that first.
     709   109421667 :   if (Pass *P = ImmutablePassMap.lookup(AID))
     710             :     return P;
     711             : 
     712             :   // Check pass managers
     713    70124883 :   for (PMDataManager *PassManager : PassManagers)
     714    17716485 :     if (Pass *P = PassManager->findAnalysisPass(AID, false))
     715             :       return P;
     716             : 
     717             :   // Check other pass managers
     718   265372430 :   for (PMDataManager *IndirectPassManager : IndirectPassManagers)
     719   217860590 :     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
     720             :       return P;
     721             : 
     722             :   return nullptr;
     723             : }
     724             : 
     725    59675110 : const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
     726   119350189 :   const PassInfo *&PI = AnalysisPassInfos[AID];
     727    59675079 :   if (!PI)
     728     5338678 :     PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
     729             :   else
     730             :     assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
     731             :            "The pass info pointer changed for an analysis ID!");
     732             : 
     733    59675080 :   return PI;
     734             : }
     735             : 
     736      245764 : void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
     737      245764 :   P->initializePass();
     738      245764 :   ImmutablePasses.push_back(P);
     739             : 
     740             :   // Add this pass to the map from its analysis ID. We clobber any prior runs
     741             :   // of the pass in the map so that the last one added is the one found when
     742             :   // doing lookups.
     743      245764 :   AnalysisID AID = P->getPassID();
     744      491528 :   ImmutablePassMap[AID] = P;
     745             : 
     746             :   // Also add any interfaces implemented by the immutable pass to the map for
     747             :   // fast lookup.
     748      245764 :   const PassInfo *PassInf = findAnalysisPassInfo(AID);
     749             :   assert(PassInf && "Expected all immutable passes to be initialized");
     750      983056 :   for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented())
     751           0 :     ImmutablePassMap[ImmPI->getTypeInfo()] = P;
     752      245764 : }
     753             : 
     754             : // Print passes managed by this top level manager.
     755       45544 : void PMTopLevelManager::dumpPasses() const {
     756             : 
     757       45544 :   if (PassDebugging < Structure)
     758             :     return;
     759             : 
     760             :   // Print out the immutable passes
     761         356 :   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
     762         496 :     ImmutablePasses[i]->dumpPassStructure(0);
     763             :   }
     764             : 
     765             :   // Every class that derives from PMDataManager also derives from Pass
     766             :   // (sometimes indirectly), but there's no inheritance relationship
     767             :   // between PMDataManager and Pass, so we have to getAsPass to get
     768             :   // from a PMDataManager* to a Pass*.
     769         216 :   for (PMDataManager *Manager : PassManagers)
     770          54 :     Manager->getAsPass()->dumpPassStructure(1);
     771             : }
     772             : 
     773       45544 : void PMTopLevelManager::dumpArguments() const {
     774             : 
     775       45544 :   if (PassDebugging < Arguments)
     776             :     return;
     777             : 
     778         115 :   dbgs() << "Pass Arguments: ";
     779         820 :   for (ImmutablePass *P : ImmutablePasses)
     780         475 :     if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) {
     781             :       assert(PI && "Expected all immutable passes to be initialized");
     782         475 :       if (!PI->isAnalysisGroup())
     783         475 :         dbgs() << " -" << PI->getPassArgument();
     784             :     }
     785         460 :   for (PMDataManager *PM : PassManagers)
     786         115 :     PM->dumpPassArguments();
     787         115 :   dbgs() << "\n";
     788             : }
     789             : 
     790      142541 : void PMTopLevelManager::initializeAllAnalysisInfo() {
     791      570164 :   for (PMDataManager *PM : PassManagers)
     792      142541 :     PM->initializeAnalysisInfo();
     793             : 
     794             :   // Initailize other pass managers
     795      613825 :   for (PMDataManager *IPM : IndirectPassManagers)
     796      186202 :     IPM->initializeAnalysisInfo();
     797             : 
     798     3660713 :   for (auto LU : LastUser) {
     799     6466180 :     SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
     800     3233088 :     L.insert(LU.first);
     801             :   }
     802      142541 : }
     803             : 
     804             : /// Destructor
     805      591956 : PMTopLevelManager::~PMTopLevelManager() {
     806      182143 :   for (PMDataManager *PM : PassManagers)
     807       45535 :     delete PM;
     808             : 
     809      381118 :   for (ImmutablePass *P : ImmutablePasses)
     810      244511 :     delete P;
     811       45535 : }
     812             : 
     813             : //===----------------------------------------------------------------------===//
     814             : // PMDataManager implementation
     815             : 
     816             : /// Augement AvailableAnalysis by adding analysis made available by pass P.
     817    29130150 : void PMDataManager::recordAvailableAnalysis(Pass *P) {
     818    29130150 :   AnalysisID PI = P->getPassID();
     819             : 
     820    58260305 :   AvailableAnalysis[PI] = P;
     821             : 
     822             :   assert(!AvailableAnalysis.empty());
     823             : 
     824             :   // This pass is the current implementation of all of the interfaces it
     825             :   // implements as well.
     826    29130155 :   const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
     827    31106092 :   if (!PInf) return;
     828    27154256 :   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     829    54308512 :   for (unsigned i = 0, e = II.size(); i != e; ++i)
     830           0 :     AvailableAnalysis[II[i]->getTypeInfo()] = P;
     831             : }
     832             : 
     833             : // Return true if P preserves high level analysis used by other
     834             : // passes managed by this manager
     835        8560 : bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
     836        8560 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     837        8560 :   if (AnUsage->getPreservesAll())
     838             :     return true;
     839             : 
     840        5663 :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     841       91477 :   for (Pass *P1 : HigherLevelAnalysis) {
     842      140341 :     if (P1->getAsImmutablePass() == nullptr &&
     843      131694 :         !is_contained(PreservedSet, P1->getPassID()))
     844             :       return false;
     845             :   }
     846             : 
     847             :   return true;
     848             : }
     849             : 
     850             : /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
     851    26103642 : void PMDataManager::verifyPreservedAnalysis(Pass *P) {
     852             :   // Don't do this unless assertions are enabled.
     853             : #ifdef NDEBUG
     854             :   return;
     855             : #endif
     856             :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     857             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     858             : 
     859             :   // Verify preserved analysis
     860             :   for (AnalysisID AID : PreservedSet) {
     861             :     if (Pass *AP = findAnalysisPass(AID, true)) {
     862             :       TimeRegion PassTimer(getPassTimer(AP));
     863             :       AP->verifyAnalysis();
     864             :     }
     865             :   }
     866             : }
     867             : 
     868             : /// Remove Analysis not preserved by Pass P
     869    28884399 : void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
     870    28884399 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     871    28884391 :   if (AnUsage->getPreservesAll())
     872             :     return;
     873             : 
     874    13059018 :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     875    52710315 :   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
     876    78828291 :          E = AvailableAnalysis.end(); I != E; ) {
     877    79302546 :     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
     878    79302575 :     if (Info->second->getAsImmutablePass() == nullptr &&
     879    79302604 :         !is_contained(PreservedSet, Info->first)) {
     880             :       // Remove this analysis
     881     8604629 :       if (PassDebugging >= Details) {
     882           2 :         Pass *S = Info->second;
     883           2 :         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     884           2 :         dbgs() << S->getPassName() << "'\n";
     885             :       }
     886     8604629 :       AvailableAnalysis.erase(Info);
     887             :     }
     888             :   }
     889             : 
     890             :   // Check inherited analysis also. If P is not preserving analysis
     891             :   // provided by parent manager then remove it here.
     892   104472133 :   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
     893             : 
     894    91413118 :     if (!InheritedAnalysis[Index])
     895    66348045 :       continue;
     896             : 
     897    22525623 :     for (DenseMap<AnalysisID, Pass*>::iterator
     898    25065073 :            I = InheritedAnalysis[Index]->begin(),
     899    97720788 :            E = InheritedAnalysis[Index]->end(); I != E; ) {
     900    45051224 :       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
     901    45051233 :       if (Info->second->getAsImmutablePass() == nullptr &&
     902    45051242 :           !is_contained(PreservedSet, Info->first)) {
     903             :         // Remove this analysis
     904      225632 :         if (PassDebugging >= Details) {
     905           1 :           Pass *S = Info->second;
     906           1 :           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     907           1 :           dbgs() << S->getPassName() << "'\n";
     908             :         }
     909      225632 :         InheritedAnalysis[Index]->erase(Info);
     910             :       }
     911             :     }
     912             :   }
     913             : }
     914             : 
     915             : /// Remove analysis passes that are not used any longer
     916    26104030 : void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
     917             :                                      enum PassDebuggingString DBG_STR) {
     918             : 
     919    52208056 :   SmallVector<Pass *, 12> DeadPasses;
     920             : 
     921             :   // If this is a on the fly manager then it does not have TPM.
     922    26104030 :   if (!TPM)
     923           0 :     return;
     924             : 
     925    26104030 :   TPM->collectLastUses(DeadPasses, P);
     926             : 
     927    26104024 :   if (PassDebugging >= Details && !DeadPasses.empty()) {
     928           3 :     dbgs() << " -*- '" <<  P->getPassName();
     929           3 :     dbgs() << "' is the last user of following pass instances.";
     930           3 :     dbgs() << " Free these instances\n";
     931             :   }
     932             : 
     933   104381260 :   for (Pass *P : DeadPasses)
     934    26069194 :     freePass(P, Msg, DBG_STR);
     935             : }
     936             : 
     937    26070223 : void PMDataManager::freePass(Pass *P, StringRef Msg,
     938             :                              enum PassDebuggingString DBG_STR) {
     939    26070223 :   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
     940             : 
     941             :   {
     942             :     // If the pass crashes releasing memory, remember this.
     943    52140458 :     PassManagerPrettyStackEntry X(P);
     944    78210689 :     TimeRegion PassTimer(getPassTimer(P));
     945             : 
     946    26070231 :     P->releaseMemory();
     947             :   }
     948             : 
     949    26070230 :   AnalysisID PI = P->getPassID();
     950    26070230 :   if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
     951             :     // Remove the pass itself (if it is not already removed).
     952    24784670 :     AvailableAnalysis.erase(PI);
     953             : 
     954             :     // Remove all interfaces this pass implements, for which it is also
     955             :     // listed as the available implementation.
     956    24784670 :     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     957    49569340 :     for (unsigned i = 0, e = II.size(); i != e; ++i) {
     958             :       DenseMap<AnalysisID, Pass*>::iterator Pos =
     959           0 :         AvailableAnalysis.find(II[i]->getTypeInfo());
     960           0 :       if (Pos != AvailableAnalysis.end() && Pos->second == P)
     961           0 :         AvailableAnalysis.erase(Pos);
     962             :     }
     963             :   }
     964    26070229 : }
     965             : 
     966             : /// Add pass P into the PassVector. Update
     967             : /// AvailableAnalysis appropriately if ProcessAnalysis is true.
     968     2780407 : void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
     969             :   // This manager is going to manage pass P. Set up analysis resolver
     970             :   // to connect them.
     971     5560818 :   AnalysisResolver *AR = new AnalysisResolver(*this);
     972     2780411 :   P->setResolver(AR);
     973             : 
     974             :   // If a FunctionPass F is the last user of ModulePass info M
     975             :   // then the F's manager, not F, records itself as a last user of M.
     976     5560816 :   SmallVector<Pass *, 12> TransferLastUses;
     977             : 
     978     2780413 :   if (!ProcessAnalysis) {
     979             :     // Add pass
     980           0 :     PassVector.push_back(P);
     981           0 :     return;
     982             :   }
     983             : 
     984             :   // At the moment, this pass is the last user of all required passes.
     985     5560816 :   SmallVector<Pass *, 12> LastUses;
     986     5560816 :   SmallVector<Pass *, 8> UsedPasses;
     987     5560816 :   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
     988             : 
     989     2780413 :   unsigned PDepth = this->getDepth();
     990             : 
     991     2780413 :   collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
     992    14459668 :   for (Pass *PUsed : UsedPasses) {
     993     6118421 :     unsigned RDepth = 0;
     994             : 
     995             :     assert(PUsed->getResolver() && "Analysis Resolver is not set");
     996     6118421 :     PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
     997     6118421 :     RDepth = DM.getDepth();
     998             : 
     999     6118421 :     if (PDepth == RDepth)
    1000     2830825 :       LastUses.push_back(PUsed);
    1001     3287596 :     else if (PDepth > RDepth) {
    1002             :       // Let the parent claim responsibility of last use
    1003     3287596 :       TransferLastUses.push_back(PUsed);
    1004             :       // Keep track of higher level analysis used by this manager.
    1005     3287595 :       HigherLevelAnalysis.push_back(PUsed);
    1006             :     } else
    1007           0 :       llvm_unreachable("Unable to accommodate Used Pass");
    1008             :   }
    1009             : 
    1010             :   // Set P as P's last user until someone starts using P.
    1011             :   // However, if P is a Pass Manager then it does not need
    1012             :   // to record its last user.
    1013     2780413 :   if (!P->getAsPMDataManager())
    1014     2687212 :     LastUses.push_back(P);
    1015     5560828 :   TPM->setLastUser(LastUses, P);
    1016             : 
    1017     2780410 :   if (!TransferLastUses.empty()) {
    1018     2171778 :     Pass *My_PM = getAsPass();
    1019     4343558 :     TPM->setLastUser(TransferLastUses, My_PM);
    1020             :     TransferLastUses.clear();
    1021             :   }
    1022             : 
    1023             :   // Now, take care of required analyses that are not available.
    1024     8344219 :   for (AnalysisID ID : ReqAnalysisNotAvailable) {
    1025        2980 :     const PassInfo *PI = TPM->findAnalysisPassInfo(ID);
    1026        5960 :     Pass *AnalysisPass = PI->createPass();
    1027        2980 :     this->addLowerLevelRequiredPass(P, AnalysisPass);
    1028             :   }
    1029             : 
    1030             :   // Take a note of analysis required and made available by this pass.
    1031             :   // Remove the analysis not preserved by this pass
    1032     2780413 :   removeNotPreservedAnalysis(P);
    1033     2780408 :   recordAvailableAnalysis(P);
    1034             : 
    1035             :   // Add pass
    1036     2780404 :   PassVector.push_back(P);
    1037             : }
    1038             : 
    1039             : 
    1040             : /// Populate UP with analysis pass that are used or required by
    1041             : /// pass P and are available. Populate RP_NotAvail with analysis
    1042             : /// pass that are required by pass P but are not available.
    1043     2780414 : void PMDataManager::collectRequiredAndUsedAnalyses(
    1044             :     SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
    1045             :     Pass *P) {
    1046     2780414 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1047             : 
    1048     8783296 :   for (const auto &UsedID : AnUsage->getUsedSet())
    1049      442057 :     if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
    1050      151778 :       UP.push_back(AnalysisPass);
    1051             : 
    1052    13992787 :   for (const auto &RequiredID : AnUsage->getRequiredSet())
    1053     5651547 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1054     5648570 :       UP.push_back(AnalysisPass);
    1055             :     else
    1056        2980 :       RP_NotAvail.push_back(RequiredID);
    1057             : 
    1058     8659303 :   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
    1059      318061 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1060      318061 :       UP.push_back(AnalysisPass);
    1061             :     else
    1062           0 :       RP_NotAvail.push_back(RequiredID);
    1063     2780414 : }
    1064             : 
    1065             : // All Required analyses should be available to the pass as it runs!  Here
    1066             : // we fill in the AnalysisImpls member of the pass so that it can
    1067             : // successfully use the getAnalysis() method to retrieve the
    1068             : // implementations it needs.
    1069             : //
    1070    26350122 : void PMDataManager::initializeAnalysisImpl(Pass *P) {
    1071    26350122 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1072             : 
    1073   134192886 :   for (const AnalysisID ID : AnUsage->getRequiredSet()) {
    1074    55142550 :     Pass *Impl = findAnalysisPass(ID, true);
    1075    55142546 :     if (!Impl)
    1076             :       // This may be analysis pass that is initialized on the fly.
    1077             :       // If that is not the case then it will raise an assert when it is used.
    1078      138778 :       continue;
    1079    55003768 :     AnalysisResolver *AR = P->getResolver();
    1080             :     assert(AR && "Analysis Resolver is not set");
    1081    55003768 :     AR->addAnalysisImplsPair(ID, Impl);
    1082             :   }
    1083    26350118 : }
    1084             : 
    1085             : /// Find the pass that implements Analysis AID. If desired pass is not found
    1086             : /// then return NULL.
    1087   313057081 : Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
    1088             : 
    1089             :   // Check if AvailableAnalysis map has one entry.
    1090   626115805 :   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
    1091             : 
    1092   939176172 :   if (I != AvailableAnalysis.end())
    1093    35258993 :     return I->second;
    1094             : 
    1095             :   // Search Parents through TopLevelManager
    1096   277799731 :   if (SearchParent)
    1097    46379880 :     return TPM->findAnalysisPass(AID);
    1098             : 
    1099             :   return nullptr;
    1100             : }
    1101             : 
    1102             : // Print list of passes that are last used by P.
    1103        3794 : void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
    1104             : 
    1105        7588 :   SmallVector<Pass *, 12> LUses;
    1106             : 
    1107             :   // If this is a on the fly manager then it does not have TPM.
    1108        3794 :   if (!TPM)
    1109           0 :     return;
    1110             : 
    1111        3794 :   TPM->collectLastUses(LUses, P);
    1112             : 
    1113       11382 :   for (Pass *P : LUses) {
    1114           0 :     dbgs() << "--" << std::string(Offset*2, ' ');
    1115           0 :     P->dumpPassStructure(0);
    1116             :   }
    1117             : }
    1118             : 
    1119         497 : void PMDataManager::dumpPassArguments() const {
    1120        9252 :   for (Pass *P : PassVector) {
    1121        7761 :     if (PMDataManager *PMD = P->getAsPMDataManager())
    1122         382 :       PMD->dumpPassArguments();
    1123             :     else
    1124        7379 :       if (const PassInfo *PI =
    1125        7379 :             TPM->findAnalysisPassInfo(P->getPassID()))
    1126        7179 :         if (!PI->isAnalysisGroup())
    1127        7179 :           dbgs() << " -" << PI->getPassArgument();
    1128             :   }
    1129         497 : }
    1130             : 
    1131    54173147 : void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
    1132             :                                  enum PassDebuggingString S2,
    1133             :                                  StringRef Msg) {
    1134    54173147 :   if (PassDebugging < Executions)
    1135             :     return;
    1136          42 :   dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this
    1137         210 :          << std::string(getDepth() * 2 + 1, ' ');
    1138          42 :   switch (S1) {
    1139          19 :   case EXECUTION_MSG:
    1140          19 :     dbgs() << "Executing Pass '" << P->getPassName();
    1141          19 :     break;
    1142           5 :   case MODIFICATION_MSG:
    1143           5 :     dbgs() << "Made Modification '" << P->getPassName();
    1144           5 :     break;
    1145          18 :   case FREEING_MSG:
    1146          18 :     dbgs() << " Freeing Pass '" << P->getPassName();
    1147          18 :     break;
    1148             :   default:
    1149             :     break;
    1150             :   }
    1151          42 :   switch (S2) {
    1152           0 :   case ON_BASICBLOCK_MSG:
    1153           0 :     dbgs() << "' on BasicBlock '" << Msg << "'...\n";
    1154           0 :     break;
    1155          22 :   case ON_FUNCTION_MSG:
    1156          22 :     dbgs() << "' on Function '" << Msg << "'...\n";
    1157          22 :     break;
    1158          12 :   case ON_MODULE_MSG:
    1159          12 :     dbgs() << "' on Module '"  << Msg << "'...\n";
    1160          12 :     break;
    1161           0 :   case ON_REGION_MSG:
    1162           0 :     dbgs() << "' on Region '"  << Msg << "'...\n";
    1163           0 :     break;
    1164           0 :   case ON_LOOP_MSG:
    1165           0 :     dbgs() << "' on Loop '" << Msg << "'...\n";
    1166           0 :     break;
    1167           8 :   case ON_CG_MSG:
    1168           8 :     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
    1169           8 :     break;
    1170             :   default:
    1171             :     break;
    1172             :   }
    1173             : }
    1174             : 
    1175    26060722 : void PMDataManager::dumpRequiredSet(const Pass *P) const {
    1176    26060722 :   if (PassDebugging < Details)
    1177    26060712 :     return;
    1178             : 
    1179          20 :   AnalysisUsage analysisUsage;
    1180          10 :   P->getAnalysisUsage(analysisUsage);
    1181          20 :   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
    1182             : }
    1183             : 
    1184    26060428 : void PMDataManager::dumpPreservedSet(const Pass *P) const {
    1185    26060428 :   if (PassDebugging < Details)
    1186    26060418 :     return;
    1187             : 
    1188          20 :   AnalysisUsage analysisUsage;
    1189          10 :   P->getAnalysisUsage(analysisUsage);
    1190          20 :   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
    1191             : }
    1192             : 
    1193    25642854 : void PMDataManager::dumpUsedSet(const Pass *P) const {
    1194    25642854 :   if (PassDebugging < Details)
    1195    25642844 :     return;
    1196             : 
    1197          20 :   AnalysisUsage analysisUsage;
    1198          10 :   P->getAnalysisUsage(analysisUsage);
    1199          20 :   dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
    1200             : }
    1201             : 
    1202          30 : void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
    1203             :                                    const AnalysisUsage::VectorType &Set) const {
    1204             :   assert(PassDebugging >= Details);
    1205          30 :   if (Set.empty())
    1206             :     return;
    1207          45 :   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
    1208         130 :   for (unsigned i = 0; i != Set.size(); ++i) {
    1209          56 :     if (i) dbgs() << ',';
    1210         112 :     const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
    1211          56 :     if (!PInf) {
    1212             :       // Some preserved passes, such as AliasAnalysis, may not be initialized by
    1213             :       // all drivers.
    1214           0 :       dbgs() << " Uninitialized Pass";
    1215           0 :       continue;
    1216             :     }
    1217         112 :     dbgs() << ' ' << PInf->getPassName();
    1218             :   }
    1219           9 :   dbgs() << '\n';
    1220             : }
    1221             : 
    1222             : /// Add RequiredPass into list of lower level passes required by pass P.
    1223             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1224             : /// through getAnalysis interface.
    1225             : /// This should be handled by specific pass manager.
    1226           0 : void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1227           0 :   if (TPM) {
    1228           0 :     TPM->dumpArguments();
    1229           0 :     TPM->dumpPasses();
    1230             :   }
    1231             : 
    1232             :   // Module Level pass may required Function Level analysis info
    1233             :   // (e.g. dominator info). Pass manager uses on the fly function pass manager
    1234             :   // to provide this on demand. In that case, in Pass manager terminology,
    1235             :   // module level pass is requiring lower level analysis info managed by
    1236             :   // lower level pass manager.
    1237             : 
    1238             :   // When Pass manager is not able to order required analysis info, Pass manager
    1239             :   // checks whether any lower level manager will be able to provide this
    1240             :   // analysis info on demand or not.
    1241             : #ifndef NDEBUG
    1242             :   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
    1243             :   dbgs() << "' required by '" << P->getPassName() << "'\n";
    1244             : #endif
    1245           0 :   llvm_unreachable("Unable to schedule pass");
    1246             : }
    1247             : 
    1248           0 : Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
    1249           0 :   llvm_unreachable("Unable to find on the fly pass");
    1250             : }
    1251             : 
    1252             : // Destructor
    1253      918904 : PMDataManager::~PMDataManager() {
    1254     3316729 :   for (Pass *P : PassVector)
    1255     2765388 :     delete P;
    1256      183781 : }
    1257             : 
    1258             : //===----------------------------------------------------------------------===//
    1259             : // NOTE: Is this the right place to define this method ?
    1260             : // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
    1261    15928831 : Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
    1262    15928831 :   return PM.findAnalysisPass(ID, dir);
    1263             : }
    1264             : 
    1265         985 : Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
    1266             :                                      Function &F) {
    1267         985 :   return PM.getOnTheFlyPass(P, AnalysisPI, F);
    1268             : }
    1269             : 
    1270             : //===----------------------------------------------------------------------===//
    1271             : // BBPassManager implementation
    1272             : 
    1273             : /// Execute all of the passes scheduled for execution by invoking
    1274             : /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
    1275             : /// the function, and if so, return true.
    1276        1093 : bool BBPassManager::runOnFunction(Function &F) {
    1277        1093 :   if (F.isDeclaration())
    1278             :     return false;
    1279             : 
    1280        1093 :   bool Changed = doInitialization(F);
    1281             : 
    1282        4546 :   for (BasicBlock &BB : F)
    1283        5068 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1284        1267 :       BasicBlockPass *BP = getContainedPass(Index);
    1285        1267 :       bool LocalChanged = false;
    1286             : 
    1287        1267 :       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, BB.getName());
    1288        1267 :       dumpRequiredSet(BP);
    1289             : 
    1290        1267 :       initializeAnalysisImpl(BP);
    1291             : 
    1292             :       {
    1293             :         // If the pass crashes, remember this.
    1294        3801 :         PassManagerPrettyStackEntry X(BP, BB);
    1295        3801 :         TimeRegion PassTimer(getPassTimer(BP));
    1296             : 
    1297        1267 :         LocalChanged |= BP->runOnBasicBlock(BB);
    1298             :       }
    1299             : 
    1300        1267 :       Changed |= LocalChanged;
    1301        1267 :       if (LocalChanged)
    1302          68 :         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
    1303             :                      BB.getName());
    1304        1267 :       dumpPreservedSet(BP);
    1305        1267 :       dumpUsedSet(BP);
    1306             : 
    1307        1267 :       verifyPreservedAnalysis(BP);
    1308        1267 :       removeNotPreservedAnalysis(BP);
    1309        1267 :       recordAvailableAnalysis(BP);
    1310        1267 :       removeDeadPasses(BP, BB.getName(), ON_BASICBLOCK_MSG);
    1311             :     }
    1312             : 
    1313        1093 :   return doFinalization(F) || Changed;
    1314             : }
    1315             : 
    1316             : // Implement doInitialization and doFinalization
    1317         234 : bool BBPassManager::doInitialization(Module &M) {
    1318         234 :   bool Changed = false;
    1319             : 
    1320         936 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1321         234 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1322             : 
    1323         234 :   return Changed;
    1324             : }
    1325             : 
    1326         227 : bool BBPassManager::doFinalization(Module &M) {
    1327         227 :   bool Changed = false;
    1328             : 
    1329         681 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1330         454 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1331             : 
    1332         227 :   return Changed;
    1333             : }
    1334             : 
    1335             : bool BBPassManager::doInitialization(Function &F) {
    1336             :   bool Changed = false;
    1337             : 
    1338        5465 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1339        1093 :     BasicBlockPass *BP = getContainedPass(Index);
    1340        1093 :     Changed |= BP->doInitialization(F);
    1341             :   }
    1342             : 
    1343             :   return Changed;
    1344             : }
    1345             : 
    1346             : bool BBPassManager::doFinalization(Function &F) {
    1347             :   bool Changed = false;
    1348             : 
    1349        5465 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1350        1093 :     BasicBlockPass *BP = getContainedPass(Index);
    1351        1093 :     Changed |= BP->doFinalization(F);
    1352             :   }
    1353             : 
    1354             :   return Changed;
    1355             : }
    1356             : 
    1357             : 
    1358             : //===----------------------------------------------------------------------===//
    1359             : // FunctionPassManager implementation
    1360             : 
    1361             : /// Create new Function pass manager
    1362        5701 : FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
    1363        5701 :   FPM = new FunctionPassManagerImpl();
    1364             :   // FPM is the top level manager.
    1365       11402 :   FPM->setTopLevelManager(FPM);
    1366             : 
    1367       11402 :   AnalysisResolver *AR = new AnalysisResolver(*FPM);
    1368        5701 :   FPM->setResolver(AR);
    1369        5701 : }
    1370             : 
    1371       11554 : FunctionPassManager::~FunctionPassManager() {
    1372        5699 :   delete FPM;
    1373        5855 : }
    1374             : 
    1375       20806 : void FunctionPassManager::add(Pass *P) {
    1376       41612 :   FPM->add(P);
    1377       20806 : }
    1378             : 
    1379             : /// run - Execute all of the passes scheduled for execution.  Keep
    1380             : /// track of whether any of the passes modifies the function, and if
    1381             : /// so, return true.
    1382             : ///
    1383      104630 : bool FunctionPassManager::run(Function &F) {
    1384      209260 :   handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) {
    1385           0 :     report_fatal_error("Error reading bitcode file: " + EIB.message());
    1386             :   });
    1387      104630 :   return FPM->run(F);
    1388             : }
    1389             : 
    1390             : 
    1391             : /// doInitialization - Run all of the initializers for the function passes.
    1392             : ///
    1393        5669 : bool FunctionPassManager::doInitialization() {
    1394        5669 :   return FPM->doInitialization(*M);
    1395             : }
    1396             : 
    1397             : /// doFinalization - Run all of the finalizers for the function passes.
    1398             : ///
    1399        5669 : bool FunctionPassManager::doFinalization() {
    1400        5669 :   return FPM->doFinalization(*M);
    1401             : }
    1402             : 
    1403             : //===----------------------------------------------------------------------===//
    1404             : // FunctionPassManagerImpl implementation
    1405             : //
    1406        8618 : bool FunctionPassManagerImpl::doInitialization(Module &M) {
    1407        8618 :   bool Changed = false;
    1408             : 
    1409        8618 :   dumpArguments();
    1410        8618 :   dumpPasses();
    1411             : 
    1412       39570 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1413       13716 :     Changed |= ImPass->doInitialization(M);
    1414             : 
    1415       43090 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1416        8618 :     Changed |= getContainedManager(Index)->doInitialization(M);
    1417             : 
    1418        8618 :   return Changed;
    1419             : }
    1420             : 
    1421        8609 : bool FunctionPassManagerImpl::doFinalization(Module &M) {
    1422        8609 :   bool Changed = false;
    1423             : 
    1424       25827 :   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
    1425       17218 :     Changed |= getContainedManager(Index)->doFinalization(M);
    1426             : 
    1427       39541 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1428       13714 :     Changed |= ImPass->doFinalization(M);
    1429             : 
    1430        8609 :   return Changed;
    1431             : }
    1432             : 
    1433             : /// cleanup - After running all passes, clean up pass manager cache.
    1434      105615 : void FPPassManager::cleanup() {
    1435      717158 :  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1436      252964 :     FunctionPass *FP = getContainedPass(Index);
    1437      252964 :     AnalysisResolver *AR = FP->getResolver();
    1438             :     assert(AR && "Analysis Resolver is not set");
    1439      252964 :     AR->clearAnalysisImpls();
    1440             :  }
    1441      105615 : }
    1442             : 
    1443        3925 : void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
    1444        3925 :   if (!wasRun)
    1445             :     return;
    1446        4925 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1447         985 :     FPPassManager *FPPM = getContainedManager(Index);
    1448        7788 :     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
    1449        2909 :       FPPM->getContainedPass(Index)->releaseMemory();
    1450             :     }
    1451             :   }
    1452         985 :   wasRun = false;
    1453             : }
    1454             : 
    1455             : // Execute all the passes managed by this top level manager.
    1456             : // Return true if any function is modified by a pass.
    1457      105615 : bool FunctionPassManagerImpl::run(Function &F) {
    1458      105615 :   bool Changed = false;
    1459      105615 :   TimingInfo::createTheTimeInfo();
    1460             : 
    1461      105615 :   initializeAllAnalysisInfo();
    1462      422460 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1463      105615 :     Changed |= getContainedManager(Index)->runOnFunction(F);
    1464      105615 :     F.getContext().yield();
    1465             :   }
    1466             : 
    1467      528075 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1468      105615 :     getContainedManager(Index)->cleanup();
    1469             : 
    1470      105615 :   wasRun = true;
    1471      105615 :   return Changed;
    1472             : }
    1473             : 
    1474             : //===----------------------------------------------------------------------===//
    1475             : // FPPassManager implementation
    1476             : 
    1477             : char FPPassManager::ID = 0;
    1478             : /// Print passes managed by this manager
    1479         100 : void FPPassManager::dumpPassStructure(unsigned Offset) {
    1480         100 :   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
    1481        7018 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1482        3409 :     FunctionPass *FP = getContainedPass(Index);
    1483        3409 :     FP->dumpPassStructure(Offset + 1);
    1484        3409 :     dumpLastUses(FP, Offset+1);
    1485             :   }
    1486         100 : }
    1487             : 
    1488             : 
    1489             : /// Execute all of the passes scheduled for execution by invoking
    1490             : /// runOnFunction method.  Keep track of whether any of the passes modifies
    1491             : /// the function, and if so, return true.
    1492      787333 : bool FPPassManager::runOnFunction(Function &F) {
    1493      787333 :   if (F.isDeclaration())
    1494             :     return false;
    1495             : 
    1496      621793 :   bool Changed = false;
    1497             : 
    1498             :   // Collect inherited analysis from Module level pass manager.
    1499      621793 :   populateInheritedAnalysis(TPM->activeStack);
    1500             : 
    1501    77715239 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1502    25490689 :     FunctionPass *FP = getContainedPass(Index);
    1503    25490689 :     bool LocalChanged = false;
    1504             : 
    1505    25490689 :     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
    1506    25490694 :     dumpRequiredSet(FP);
    1507             : 
    1508    25490694 :     initializeAnalysisImpl(FP);
    1509             : 
    1510             :     {
    1511    76471931 :       PassManagerPrettyStackEntry X(FP, F);
    1512    76471932 :       TimeRegion PassTimer(getPassTimer(FP));
    1513             : 
    1514    25490692 :       LocalChanged |= FP->runOnFunction(F);
    1515             :     }
    1516             : 
    1517    25490547 :     Changed |= LocalChanged;
    1518    25490547 :     if (LocalChanged)
    1519     2147307 :       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
    1520    25490547 :     dumpPreservedSet(FP);
    1521    25490549 :     dumpUsedSet(FP);
    1522             : 
    1523    25490548 :     verifyPreservedAnalysis(FP);
    1524    25490548 :     removeNotPreservedAnalysis(FP);
    1525    25490544 :     recordAvailableAnalysis(FP);
    1526    25490550 :     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
    1527             :   }
    1528             :   return Changed;
    1529             : }
    1530             : 
    1531       50593 : bool FPPassManager::runOnModule(Module &M) {
    1532       50593 :   bool Changed = false;
    1533             : 
    1534      756296 :   for (Function &F : M)
    1535      604517 :     Changed |= runOnFunction(F);
    1536             : 
    1537       50465 :   return Changed;
    1538             : }
    1539             : 
    1540       63525 : bool FPPassManager::doInitialization(Module &M) {
    1541       63525 :   bool Changed = false;
    1542             : 
    1543     5242384 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1544     2557670 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1545             : 
    1546       63522 :   return Changed;
    1547             : }
    1548             : 
    1549       63235 : bool FPPassManager::doFinalization(Module &M) {
    1550       63235 :   bool Changed = false;
    1551             : 
    1552     2670266 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1553     5087614 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1554             : 
    1555       63224 :   return Changed;
    1556             : }
    1557             : 
    1558             : //===----------------------------------------------------------------------===//
    1559             : // MPPassManager implementation
    1560             : 
    1561             : /// Execute all of the passes scheduled for execution by invoking
    1562             : /// runOnModule method.  Keep track of whether any of the passes modifies
    1563             : /// the module, and if so, return true.
    1564             : bool
    1565       36927 : MPPassManager::runOnModule(Module &M) {
    1566       36927 :   bool Changed = false;
    1567             : 
    1568             :   // Initialize on-the-fly passes
    1569      113730 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1570        2949 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1571        2949 :     Changed |= FPP->doInitialization(M);
    1572             :   }
    1573             : 
    1574             :   // Initialize module passes
    1575      527541 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1576      151238 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1577             : 
    1578      526953 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1579      151177 :     ModulePass *MP = getContainedPass(Index);
    1580      151177 :     bool LocalChanged = false;
    1581             : 
    1582      453531 :     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
    1583      151177 :     dumpRequiredSet(MP);
    1584             : 
    1585      151176 :     initializeAnalysisImpl(MP);
    1586             : 
    1587             :     {
    1588      302216 :       PassManagerPrettyStackEntry X(MP, M);
    1589      453393 :       TimeRegion PassTimer(getPassTimer(MP));
    1590             : 
    1591      151177 :       LocalChanged |= MP->runOnModule(M);
    1592             :     }
    1593             : 
    1594      151039 :     Changed |= LocalChanged;
    1595      151039 :     if (LocalChanged)
    1596       91110 :       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
    1597             :                    M.getModuleIdentifier());
    1598      151039 :     dumpPreservedSet(MP);
    1599      151039 :     dumpUsedSet(MP);
    1600             : 
    1601      151039 :     verifyPreservedAnalysis(MP);
    1602      151039 :     removeNotPreservedAnalysis(MP);
    1603      151039 :     recordAvailableAnalysis(MP);
    1604      453117 :     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
    1605             :   }
    1606             : 
    1607             :   // Finalize module passes
    1608      224182 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1609      301262 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1610             : 
    1611             :   // Finalize on-the-fly passes
    1612      113253 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1613        2940 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1614             :     // We don't know when is the last time an on-the-fly pass is run,
    1615             :     // so we need to releaseMemory / finalize here
    1616        2940 :     FPP->releaseMemoryOnTheFly();
    1617        2940 :     Changed |= FPP->doFinalization(M);
    1618             :   }
    1619             : 
    1620       36771 :   return Changed;
    1621             : }
    1622             : 
    1623             : /// Add RequiredPass into list of lower level passes required by pass P.
    1624             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1625             : /// through getAnalysis interface.
    1626        2980 : void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1627             :   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
    1628             :          "Unable to handle Pass that requires lower level Analysis pass");
    1629             :   assert((P->getPotentialPassManagerType() <
    1630             :           RequiredPass->getPotentialPassManagerType()) &&
    1631             :          "Unable to handle Pass that requires lower level Analysis pass");
    1632        2980 :   if (!RequiredPass)
    1633           0 :     return;
    1634             : 
    1635        2980 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
    1636        2980 :   if (!FPP) {
    1637        2949 :     FPP = new FunctionPassManagerImpl();
    1638             :     // FPP is the top level manager.
    1639        5898 :     FPP->setTopLevelManager(FPP);
    1640             : 
    1641        2949 :     OnTheFlyManagers[P] = FPP;
    1642             :   }
    1643             :   const PassInfo *RequiredPassPI =
    1644        2980 :       TPM->findAnalysisPassInfo(RequiredPass->getPassID());
    1645             : 
    1646        2980 :   Pass *FoundPass = nullptr;
    1647        2980 :   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
    1648        2979 :     FoundPass =
    1649        2979 :       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
    1650             :   }
    1651        2980 :   if (!FoundPass) {
    1652        2980 :     FoundPass = RequiredPass;
    1653             :     // This should be guaranteed to add RequiredPass to the passmanager given
    1654             :     // that we checked for an available analysis above.
    1655             :     FPP->add(RequiredPass);
    1656             :   }
    1657             :   // Register P as the last user of FoundPass or RequiredPass.
    1658        5960 :   SmallVector<Pass *, 1> LU;
    1659        2980 :   LU.push_back(FoundPass);
    1660        5960 :   FPP->setLastUser(LU,  P);
    1661             : }
    1662             : 
    1663             : /// Return function pass corresponding to PassInfo PI, that is
    1664             : /// required by module pass MP. Instantiate analysis pass, by using
    1665             : /// its runOnFunction() for function F.
    1666         985 : Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
    1667         985 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
    1668             :   assert(FPP && "Unable to find on the fly pass");
    1669             : 
    1670         985 :   FPP->releaseMemoryOnTheFly();
    1671         985 :   FPP->run(F);
    1672         985 :   return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
    1673             : }
    1674             : 
    1675             : 
    1676             : //===----------------------------------------------------------------------===//
    1677             : // PassManagerImpl implementation
    1678             : 
    1679             : //
    1680             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1681             : /// whether any of the passes modifies the module, and if so, return true.
    1682       36926 : bool PassManagerImpl::run(Module &M) {
    1683       36926 :   bool Changed = false;
    1684       36926 :   TimingInfo::createTheTimeInfo();
    1685             : 
    1686       36926 :   dumpArguments();
    1687       36926 :   dumpPasses();
    1688             : 
    1689      342471 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1690      231693 :     Changed |= ImPass->doInitialization(M);
    1691             : 
    1692       36926 :   initializeAllAnalysisInfo();
    1693      147393 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1694       36926 :     Changed |= getContainedManager(Index)->runOnModule(M);
    1695       36771 :     M.getContext().yield();
    1696             :   }
    1697             : 
    1698      340786 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1699      230474 :     Changed |= ImPass->doFinalization(M);
    1700             : 
    1701       36770 :   return Changed;
    1702             : }
    1703             : 
    1704             : //===----------------------------------------------------------------------===//
    1705             : // PassManager implementation
    1706             : 
    1707             : /// Create new pass manager
    1708       37066 : PassManager::PassManager() {
    1709       37066 :   PM = new PassManagerImpl();
    1710             :   // PM is the top level manager
    1711       74132 :   PM->setTopLevelManager(PM);
    1712       37066 : }
    1713             : 
    1714       73798 : PassManager::~PassManager() {
    1715       36895 :   delete PM;
    1716       36904 : }
    1717             : 
    1718     1678070 : void PassManager::add(Pass *P) {
    1719     3356138 :   PM->add(P);
    1720     1678068 : }
    1721             : 
    1722             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1723             : /// whether any of the passes modifies the module, and if so, return true.
    1724       36926 : bool PassManager::run(Module &M) {
    1725       36926 :   return PM->run(M);
    1726             : }
    1727             : 
    1728             : //===----------------------------------------------------------------------===//
    1729             : // TimingInfo implementation
    1730             : 
    1731             : bool llvm::TimePassesIsEnabled = false;
    1732             : static cl::opt<bool,true>
    1733      216990 : EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
    1734      289320 :             cl::desc("Time each pass, printing elapsed time for each on exit"));
    1735             : 
    1736             : // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
    1737             : // a non-null value (if the -time-passes option is enabled) or it leaves it
    1738             : // null.  It may be called multiple times.
    1739      142541 : void TimingInfo::createTheTimeInfo() {
    1740      142541 :   if (!TimePassesIsEnabled || TheTimeInfo) return;
    1741             : 
    1742             :   // Constructed the first time this is called, iff -time-passes is enabled.
    1743             :   // This guarantees that the object will be constructed before static globals,
    1744             :   // thus it will be destroyed before them.
    1745          10 :   static ManagedStatic<TimingInfo> TTI;
    1746          10 :   TheTimeInfo = &*TTI;
    1747             : }
    1748             : 
    1749             : /// If TimingInfo is enabled then start pass timer.
    1750    52260813 : Timer *llvm::getPassTimer(Pass *P) {
    1751    52260813 :   if (TheTimeInfo)
    1752        2088 :     return TheTimeInfo->getPassTimer(P);
    1753             :   return nullptr;
    1754             : }
    1755             : 
    1756             : /// If timing is enabled, report the times collected up to now and then reset
    1757             : /// them.
    1758          58 : void llvm::reportAndResetTimings() {
    1759          58 :   if (TheTimeInfo)
    1760           0 :     TheTimeInfo->print();
    1761          58 : }
    1762             : 
    1763             : //===----------------------------------------------------------------------===//
    1764             : // PMStack implementation
    1765             : //
    1766             : 
    1767             : // Pop Pass Manager from the stack and clear its analysis info.
    1768       70635 : void PMStack::pop() {
    1769             : 
    1770       70635 :   PMDataManager *Top = this->top();
    1771       70635 :   Top->initializeAnalysisInfo();
    1772             : 
    1773       70635 :   S.pop_back();
    1774       70635 : }
    1775             : 
    1776             : // Push PM on the stack and set its top level manager.
    1777      138917 : void PMStack::push(PMDataManager *PM) {
    1778             :   assert(PM && "Unable to push. Pass Manager expected");
    1779             :   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
    1780             : 
    1781      138917 :   if (!this->empty()) {
    1782             :     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
    1783             :            && "pushing bad pass manager to PMStack");
    1784       93201 :     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
    1785             : 
    1786             :     assert(TPM && "Unable to find top level manager");
    1787      186402 :     TPM->addIndirectPassManager(PM);
    1788      186402 :     PM->setTopLevelManager(TPM);
    1789      186402 :     PM->setDepth(this->top()->getDepth()+1);
    1790             :   } else {
    1791             :     assert((PM->getPassManagerType() == PMT_ModulePassManager
    1792             :            || PM->getPassManagerType() == PMT_FunctionPassManager)
    1793             :            && "pushing bad pass manager to PMStack");
    1794       45716 :     PM->setDepth(1);
    1795             :   }
    1796             : 
    1797      138917 :   S.push_back(PM);
    1798      138917 : }
    1799             : 
    1800             : // Dump content of the pass manager stack.
    1801           0 : LLVM_DUMP_METHOD void PMStack::dump() const {
    1802           0 :   for (PMDataManager *Manager : S)
    1803           0 :     dbgs() << Manager->getAsPass()->getPassName() << ' ';
    1804             : 
    1805           0 :   if (!S.empty())
    1806           0 :     dbgs() << '\n';
    1807           0 : }
    1808             : 
    1809             : /// Find appropriate Module Pass Manager in the PM Stack and
    1810             : /// add self into that manager.
    1811      155646 : void ModulePass::assignPassManager(PMStack &PMS,
    1812             :                                    PassManagerType PreferredType) {
    1813             :   // Find Module Pass Manager
    1814      237632 :   while (!PMS.empty()) {
    1815      196639 :     PassManagerType TopPMType = PMS.top()->getPassManagerType();
    1816      196639 :     if (TopPMType == PreferredType)
    1817             :       break; // We found desired pass manager
    1818       40993 :     else if (TopPMType > PMT_ModulePassManager)
    1819       40993 :       PMS.pop();    // Pop children pass managers
    1820             :     else
    1821             :       break;
    1822             :   }
    1823             :   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
    1824      155646 :   PMS.top()->add(this);
    1825      155646 : }
    1826             : 
    1827             : /// Find appropriate Function Pass Manager or Call Graph Pass Manager
    1828             : /// in the PM Stack and add self into that manager.
    1829     2557454 : void FunctionPass::assignPassManager(PMStack &PMS,
    1830             :                                      PassManagerType PreferredType) {
    1831             : 
    1832             :   // Find Function Pass Manager
    1833     2613780 :   while (!PMS.empty()) {
    1834     2585617 :     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
    1835       28163 :       PMS.pop();
    1836             :     else
    1837             :       break;
    1838             :   }
    1839             : 
    1840             :   // Create new Function Pass Manager if needed.
    1841             :   FPPassManager *FPP;
    1842     2557453 :   if (PMS.top()->getPassManagerType() == PMT_FunctionPassManager) {
    1843     2502435 :     FPP = (FPPassManager *)PMS.top();
    1844             :   } else {
    1845             :     assert(!PMS.empty() && "Unable to create Function Pass Manager");
    1846       55018 :     PMDataManager *PMD = PMS.top();
    1847             : 
    1848             :     // [1] Create new Function Pass Manager
    1849      110036 :     FPP = new FPPassManager();
    1850      110036 :     FPP->populateInheritedAnalysis(PMS);
    1851             : 
    1852             :     // [2] Set up new manager's top level manager
    1853       55018 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1854       55018 :     TPM->addIndirectPassManager(FPP);
    1855             : 
    1856             :     // [3] Assign manager to manage this new manager. This may create
    1857             :     // and push new managers into PMS
    1858       55018 :     FPP->assignPassManager(PMS, PMD->getPassManagerType());
    1859             : 
    1860             :     // [4] Push new manager into PMS
    1861       55018 :     PMS.push(FPP);
    1862             :   }
    1863             : 
    1864             :   // Assign FPP as the manager of this pass.
    1865     2557453 :   FPP->add(this);
    1866     2557449 : }
    1867             : 
    1868             : /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
    1869             : /// in the PM Stack and add self into that manager.
    1870         234 : void BasicBlockPass::assignPassManager(PMStack &PMS,
    1871             :                                        PassManagerType PreferredType) {
    1872             :   BBPassManager *BBP;
    1873             : 
    1874             :   // Basic Pass Manager is a leaf pass manager. It does not handle
    1875             :   // any other pass manager.
    1876         468 :   if (!PMS.empty() &&
    1877         234 :       PMS.top()->getPassManagerType() == PMT_BasicBlockPassManager) {
    1878           0 :     BBP = (BBPassManager *)PMS.top();
    1879             :   } else {
    1880             :     // If leaf manager is not Basic Block Pass manager then create new
    1881             :     // basic Block Pass manager.
    1882             :     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
    1883         234 :     PMDataManager *PMD = PMS.top();
    1884             : 
    1885             :     // [1] Create new Basic Block Manager
    1886         468 :     BBP = new BBPassManager();
    1887             : 
    1888             :     // [2] Set up new manager's top level manager
    1889             :     // Basic Block Pass Manager does not live by itself
    1890         234 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1891         234 :     TPM->addIndirectPassManager(BBP);
    1892             : 
    1893             :     // [3] Assign manager to manage this new manager. This may create
    1894             :     // and push new managers into PMS
    1895         234 :     BBP->assignPassManager(PMS, PreferredType);
    1896             : 
    1897             :     // [4] Push new manager into PMS
    1898         234 :     PMS.push(BBP);
    1899             :   }
    1900             : 
    1901             :   // Assign BBP as the manager of this pass.
    1902         234 :   BBP->add(this);
    1903         234 : }
    1904             : 
    1905      259585 : PassManagerBase::~PassManagerBase() {}

Generated by: LCOV version 1.13