LCOV - code coverage report
Current view: top level - lib/IR - LegacyPassManager.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 648 742 87.3 %
Date: 2018-02-23 15:42:53 Functions: 98 123 79.7 %
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       81710 : PassDebugging("debug-pass", cl::Hidden,
      54       81710 :                   cl::desc("Print PassManager debugging information"),
      55      571970 :                   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       81710 :   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       81710 : PrintBefore("print-before",
      70       81710 :             llvm::cl::desc("Print IR before specified passes"),
      71      245130 :             cl::Hidden);
      72             : 
      73             : static PassOptionList
      74       81710 : PrintAfter("print-after",
      75       81710 :            llvm::cl::desc("Print IR after specified passes"),
      76      245130 :            cl::Hidden);
      77             : 
      78       81710 : static cl::opt<bool> PrintBeforeAll("print-before-all",
      79       81710 :                                     llvm::cl::desc("Print IR before each pass"),
      80      245130 :                                     cl::init(false), cl::Hidden);
      81       81710 : static cl::opt<bool> PrintAfterAll("print-after-all",
      82       81710 :                                    llvm::cl::desc("Print IR after each pass"),
      83      245130 :                                    cl::init(false), cl::Hidden);
      84             : 
      85             : static cl::opt<bool>
      86       81710 :     PrintModuleScope("print-module-scope",
      87       81710 :                      cl::desc("When printing IR for print-[before|after]{-all} "
      88             :                               "always print a module IR"),
      89      245130 :                      cl::init(false));
      90             : 
      91             : static cl::list<std::string>
      92      163420 :     PrintFuncsList("filter-print-funcs", cl::value_desc("function names"),
      93       81710 :                    cl::desc("Only print IR for functions whose name "
      94             :                             "match this for all print-[before|after][-all] "
      95             :                             "options"),
      96      245130 :                    cl::CommaSeparated, cl::Hidden);
      97             : 
      98             : /// This is a helper to determine whether to print IR before or
      99             : /// after a pass.
     100             : 
     101     3624318 : static bool ShouldPrintBeforeOrAfterPass(const PassInfo *PI,
     102             :                                          PassOptionList &PassesToPrint) {
     103     3625985 :   for (auto *PassInf : PassesToPrint) {
     104        1690 :     if (PassInf)
     105             :       if (PassInf->getPassArgument() == PI->getPassArgument()) {
     106             :         return true;
     107             :       }
     108             :   }
     109             :   return false;
     110             : }
     111             : 
     112             : /// This is a utility to check whether a pass should have IR dumped
     113             : /// before it.
     114             : static bool ShouldPrintBeforePass(const PassInfo *PI) {
     115     1812371 :   return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PI, PrintBefore);
     116             : }
     117             : 
     118             : /// This is a utility to check whether a pass should have IR dumped
     119             : /// after it.
     120             : static bool ShouldPrintAfterPass(const PassInfo *PI) {
     121     1812372 :   return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PI, PrintAfter);
     122             : }
     123             : 
     124         458 : bool llvm::forcePrintModuleIR() { return PrintModuleScope; }
     125             : 
     126       14921 : bool llvm::isFunctionInPrintList(StringRef FunctionName) {
     127             :   static std::unordered_set<std::string> PrintFuncNames(PrintFuncsList.begin(),
     128       27985 :                                                         PrintFuncsList.end());
     129       30008 :   return PrintFuncNames.empty() || PrintFuncNames.count(FunctionName);
     130             : }
     131             : /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
     132             : /// or higher is specified.
     133      570169 : bool PMDataManager::isPassDebuggingExecutionsOrMore() const {
     134      570169 :   return PassDebugging >= Executions;
     135             : }
     136             : 
     137             : 
     138             : 
     139             : 
     140           0 : void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
     141           0 :   if (!V && !M)
     142           0 :     OS << "Releasing pass '";
     143             :   else
     144           0 :     OS << "Running pass '";
     145             : 
     146           0 :   OS << P->getPassName() << "'";
     147             : 
     148           0 :   if (M) {
     149           0 :     OS << " on module '" << M->getModuleIdentifier() << "'.\n";
     150           0 :     return;
     151             :   }
     152           0 :   if (!V) {
     153             :     OS << '\n';
     154             :     return;
     155             :   }
     156             : 
     157           0 :   OS << " on ";
     158           0 :   if (isa<Function>(V))
     159           0 :     OS << "function";
     160           0 :   else if (isa<BasicBlock>(V))
     161           0 :     OS << "basic block";
     162             :   else
     163           0 :     OS << "value";
     164             : 
     165           0 :   OS << " '";
     166           0 :   V->printAsOperand(OS, /*PrintTy=*/false, M);
     167           0 :   OS << "'\n";
     168             : }
     169             : 
     170             : 
     171             : namespace {
     172             : //===----------------------------------------------------------------------===//
     173             : // BBPassManager
     174             : //
     175             : /// BBPassManager manages BasicBlockPass. It batches all the
     176             : /// pass together and sequence them to process one basic block before
     177             : /// processing next basic block.
     178         468 : class BBPassManager : public PMDataManager, public FunctionPass {
     179             : 
     180             : public:
     181             :   static char ID;
     182             :   explicit BBPassManager()
     183         482 :     : PMDataManager(), FunctionPass(ID) {}
     184             : 
     185             :   /// Execute all of the passes scheduled for execution.  Keep track of
     186             :   /// whether any of the passes modifies the function, and if so, return true.
     187             :   bool runOnFunction(Function &F) override;
     188             : 
     189             :   /// Pass Manager itself does not invalidate any analysis info.
     190         241 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     191             :     Info.setPreservesAll();
     192         241 :   }
     193             : 
     194             :   bool doInitialization(Module &M) override;
     195             :   bool doInitialization(Function &F);
     196             :   bool doFinalization(Module &M) override;
     197             :   bool doFinalization(Function &F);
     198             : 
     199         241 :   PMDataManager *getAsPMDataManager() override { return this; }
     200           0 :   Pass *getAsPass() override { return this; }
     201             : 
     202           0 :   StringRef getPassName() const override { return "BasicBlock Pass Manager"; }
     203             : 
     204             :   // Print passes managed by this manager
     205           0 :   void dumpPassStructure(unsigned Offset) override {
     206           0 :     dbgs().indent(Offset*2) << "BasicBlockPass Manager\n";
     207           0 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     208             :       BasicBlockPass *BP = getContainedPass(Index);
     209           0 :       BP->dumpPassStructure(Offset + 1);
     210           0 :       dumpLastUses(BP, Offset+1);
     211             :     }
     212           0 :   }
     213             : 
     214             :   BasicBlockPass *getContainedPass(unsigned N) {
     215             :     assert(N < PassVector.size() && "Pass number out of range!");
     216        8028 :     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
     217             :     return BP;
     218             :   }
     219             : 
     220         240 :   PassManagerType getPassManagerType() const override {
     221         240 :     return PMT_BasicBlockPassManager;
     222             :   }
     223             : };
     224             : 
     225             : char BBPassManager::ID = 0;
     226             : } // End anonymous namespace
     227             : 
     228             : namespace llvm {
     229             : namespace legacy {
     230             : //===----------------------------------------------------------------------===//
     231             : // FunctionPassManagerImpl
     232             : //
     233             : /// FunctionPassManagerImpl manages FPPassManagers
     234       25556 : class FunctionPassManagerImpl : public Pass,
     235             :                                 public PMDataManager,
     236             :                                 public PMTopLevelManager {
     237             :   virtual void anchor();
     238             : private:
     239             :   bool wasRun;
     240             : public:
     241             :   static char ID;
     242       12792 :   explicit FunctionPassManagerImpl() :
     243             :     Pass(PT_PassManager, ID), PMDataManager(),
     244       25584 :     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
     245             : 
     246             :   /// \copydoc FunctionPassManager::add()
     247             :   void add(Pass *P) {
     248       44577 :     schedulePass(P);
     249             :   }
     250             : 
     251             :   /// createPrinterPass - Get a function printer pass.
     252           0 :   Pass *createPrinterPass(raw_ostream &O,
     253             :                           const std::string &Banner) const override {
     254           0 :     return createPrintFunctionPass(O, Banner);
     255             :   }
     256             : 
     257             :   // Prepare for running an on the fly pass, freeing memory if needed
     258             :   // from a previous run.
     259             :   void releaseMemoryOnTheFly();
     260             : 
     261             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     262             :   /// whether any of the passes modifies the module, and if so, return true.
     263             :   bool run(Function &F);
     264             : 
     265             :   /// doInitialization - Run all of the initializers for the function passes.
     266             :   ///
     267             :   bool doInitialization(Module &M) override;
     268             : 
     269             :   /// doFinalization - Run all of the finalizers for the function passes.
     270             :   ///
     271             :   bool doFinalization(Module &M) override;
     272             : 
     273             : 
     274       22308 :   PMDataManager *getAsPMDataManager() override { return this; }
     275           0 :   Pass *getAsPass() override { return this; }
     276       34890 :   PassManagerType getTopLevelPassManagerType() override {
     277       34890 :     return PMT_FunctionPassManager;
     278             :   }
     279             : 
     280             :   /// Pass Manager itself does not invalidate any analysis info.
     281           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     282             :     Info.setPreservesAll();
     283           0 :   }
     284             : 
     285             :   FPPassManager *getContainedManager(unsigned N) {
     286             :     assert(N < PassManagers.size() && "Pass number out of range!");
     287      623062 :     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
     288             :     return FP;
     289             :   }
     290             : };
     291             : 
     292           0 : void FunctionPassManagerImpl::anchor() {}
     293             : 
     294             : char FunctionPassManagerImpl::ID = 0;
     295             : } // End of legacy namespace
     296             : } // End of llvm namespace
     297             : 
     298             : namespace {
     299             : //===----------------------------------------------------------------------===//
     300             : // MPPassManager
     301             : //
     302             : /// MPPassManager manages ModulePasses and function pass managers.
     303             : /// It batches all Module passes and function pass managers together and
     304             : /// sequences them to process one module.
     305             : class MPPassManager : public Pass, public PMDataManager {
     306             : public:
     307             :   static char ID;
     308       45111 :   explicit MPPassManager() :
     309       45111 :     Pass(PT_PassManager, ID), PMDataManager() { }
     310             : 
     311             :   // Delete on the fly managers.
     312      134716 :   ~MPPassManager() override {
     313       49247 :     for (auto &OnTheFlyManager : OnTheFlyManagers) {
     314        4342 :       FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
     315        4342 :       delete FPP;
     316             :     }
     317       89812 :   }
     318             : 
     319             :   /// createPrinterPass - Get a module printer pass.
     320           0 :   Pass *createPrinterPass(raw_ostream &O,
     321             :                           const std::string &Banner) const override {
     322           0 :     return createPrintModulePass(O, Banner);
     323             :   }
     324             : 
     325             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     326             :   /// whether any of the passes modifies the module, and if so, return true.
     327             :   bool runOnModule(Module &M);
     328             : 
     329             :   using llvm::Pass::doInitialization;
     330             :   using llvm::Pass::doFinalization;
     331             : 
     332             :   /// Pass Manager itself does not invalidate any analysis info.
     333           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     334             :     Info.setPreservesAll();
     335           0 :   }
     336             : 
     337             :   /// Add RequiredPass into list of lower level passes required by pass P.
     338             :   /// RequiredPass is run on the fly by Pass Manager when P requests it
     339             :   /// through getAnalysis interface.
     340             :   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
     341             : 
     342             :   /// Return function pass corresponding to PassInfo PI, that is
     343             :   /// required by module pass MP. Instantiate analysis pass, by using
     344             :   /// its runOnFunction() for function F.
     345             :   Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override;
     346             : 
     347           0 :   StringRef getPassName() const override { return "Module Pass Manager"; }
     348             : 
     349           0 :   PMDataManager *getAsPMDataManager() override { return this; }
     350     3276478 :   Pass *getAsPass() override { return this; }
     351             : 
     352             :   // Print passes managed by this manager
     353          33 :   void dumpPassStructure(unsigned Offset) override {
     354          33 :     dbgs().indent(Offset*2) << "ModulePass Manager\n";
     355         593 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     356             :       ModulePass *MP = getContainedPass(Index);
     357         280 :       MP->dumpPassStructure(Offset + 1);
     358             :       std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I =
     359             :         OnTheFlyManagers.find(MP);
     360         280 :       if (I != OnTheFlyManagers.end())
     361          23 :         I->second->dumpPassStructure(Offset + 2);
     362         280 :       dumpLastUses(MP, Offset+1);
     363             :     }
     364          33 :   }
     365             : 
     366             :   ModulePass *getContainedPass(unsigned N) {
     367             :     assert(N < PassVector.size() && "Pass number out of range!");
     368     1126144 :     return static_cast<ModulePass *>(PassVector[N]);
     369             :   }
     370             : 
     371      396557 :   PassManagerType getPassManagerType() const override {
     372      396557 :     return PMT_ModulePassManager;
     373             :   }
     374             : 
     375             :  private:
     376             :   /// Collection of on the fly FPPassManagers. These managers manage
     377             :   /// function passes that are required by module passes.
     378             :   std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
     379             : };
     380             : 
     381             : char MPPassManager::ID = 0;
     382             : } // End anonymous namespace
     383             : 
     384             : namespace llvm {
     385             : namespace legacy {
     386             : //===----------------------------------------------------------------------===//
     387             : // PassManagerImpl
     388             : //
     389             : 
     390             : /// PassManagerImpl manages MPPassManagers
     391       89809 : class PassManagerImpl : public Pass,
     392             :                         public PMDataManager,
     393             :                         public PMTopLevelManager {
     394             :   virtual void anchor();
     395             : 
     396             : public:
     397             :   static char ID;
     398       45111 :   explicit PassManagerImpl() :
     399             :     Pass(PT_PassManager, ID), PMDataManager(),
     400       90222 :                               PMTopLevelManager(new MPPassManager()) {}
     401             : 
     402             :   /// \copydoc PassManager::add()
     403             :   void add(Pass *P) {
     404     1978742 :     schedulePass(P);
     405             :   }
     406             : 
     407             :   /// createPrinterPass - Get a module printer pass.
     408           0 :   Pass *createPrinterPass(raw_ostream &O,
     409             :                           const std::string &Banner) const override {
     410           0 :     return createPrintModulePass(O, Banner);
     411             :   }
     412             : 
     413             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     414             :   /// whether any of the passes modifies the module, and if so, return true.
     415             :   bool run(Module &M);
     416             : 
     417             :   using llvm::Pass::doInitialization;
     418             :   using llvm::Pass::doFinalization;
     419             : 
     420             :   /// Pass Manager itself does not invalidate any analysis info.
     421           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     422             :     Info.setPreservesAll();
     423           0 :   }
     424             : 
     425      269348 :   PMDataManager *getAsPMDataManager() override { return this; }
     426           0 :   Pass *getAsPass() override { return this; }
     427     3150647 :   PassManagerType getTopLevelPassManagerType() override {
     428     3150647 :     return PMT_ModulePassManager;
     429             :   }
     430             : 
     431             :   MPPassManager *getContainedManager(unsigned N) {
     432             :     assert(N < PassManagers.size() && "Pass number out of range!");
     433       89868 :     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
     434             :     return MP;
     435             :   }
     436             : };
     437             : 
     438           0 : void PassManagerImpl::anchor() {}
     439             : 
     440             : char PassManagerImpl::ID = 0;
     441             : } // End of legacy namespace
     442             : } // End of llvm namespace
     443             : 
     444             : namespace {
     445             : 
     446             : //===----------------------------------------------------------------------===//
     447             : /// TimingInfo Class - This class is used to calculate information about the
     448             : /// amount of time each pass takes to execute.  This only happens when
     449             : /// -time-passes is enabled on the command line.
     450             : ///
     451             : 
     452             : static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex;
     453             : 
     454             : class TimingInfo {
     455             :   DenseMap<Pass*, Timer*> TimingData;
     456             :   TimerGroup TG;
     457             : public:
     458             :   // Use 'create' member to get this.
     459          30 :   TimingInfo() : TG("pass", "... Pass execution timing report ...") {}
     460             : 
     461             :   // TimingDtor - Print out information about timing information
     462          30 :   ~TimingInfo() {
     463             :     // Delete all of the timers, which accumulate their info into the
     464             :     // TimerGroup.
     465        1002 :     for (auto &I : TimingData)
     466         982 :       delete I.second;
     467             :     // TimerGroup is deleted next, printing the report.
     468          10 :   }
     469             : 
     470             :   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
     471             :   // to a non-null value (if the -time-passes option is enabled) or it leaves it
     472             :   // null.  It may be called multiple times.
     473             :   static void createTheTimeInfo();
     474             : 
     475             :   // print - Prints out timing information and then resets the timers.
     476           0 :   void print() {
     477           0 :     TG.print(*CreateInfoOutputFile());
     478           0 :   }
     479             : 
     480             :   /// getPassTimer - Return the timer for the specified pass if it exists.
     481        2128 :   Timer *getPassTimer(Pass *P) {
     482        2128 :     if (P->getAsPMDataManager())
     483             :       return nullptr;
     484             : 
     485        2066 :     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
     486        2066 :     Timer *&T = TimingData[P];
     487        2066 :     if (!T) {
     488         982 :       StringRef PassName = P->getPassName();
     489         982 :       T = new Timer(PassName, PassName, TG);
     490             :     }
     491        2066 :     return T;
     492             :   }
     493             : };
     494             : 
     495             : } // End of anon namespace
     496             : 
     497             : static TimingInfo *TheTimeInfo;
     498             : 
     499             : //===----------------------------------------------------------------------===//
     500             : // PMTopLevelManager implementation
     501             : 
     502             : /// Initialize top level manager. Create first pass manager.
     503      231612 : PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
     504             :   PMDM->setTopLevelManager(this);
     505             :   addPassManager(PMDM);
     506       57903 :   activeStack.push(PMDM);
     507       57903 : }
     508             : 
     509             : /// Set pass P as the last user of the given analysis passes.
     510             : void
     511    22126420 : PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
     512             :   unsigned PDepth = 0;
     513    22126420 :   if (P->getResolver())
     514    18804356 :     PDepth = P->getResolver()->getPMDataManager().getDepth();
     515             : 
     516    44781032 :   for (Pass *AP : AnalysisPasses) {
     517    22654574 :     LastUser[AP] = P;
     518             : 
     519    11327271 :     if (P == AP)
     520     3140644 :       continue;
     521             : 
     522             :     // Update the last users of passes that are required transitive by AP.
     523     8186627 :     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
     524             :     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
     525             :     SmallVector<Pass *, 12> LastUses;
     526             :     SmallVector<Pass *, 12> LastPMUses;
     527    10483629 :     for (AnalysisID ID : IDs) {
     528     1148501 :       Pass *AnalysisPass = findAnalysisPass(ID);
     529             :       assert(AnalysisPass && "Expected analysis pass to exist.");
     530     1148504 :       AnalysisResolver *AR = AnalysisPass->getResolver();
     531             :       assert(AR && "Expected analysis resolver to exist.");
     532     1148504 :       unsigned APDepth = AR->getPMDataManager().getDepth();
     533             : 
     534     1148504 :       if (PDepth == APDepth)
     535      894929 :         LastUses.push_back(AnalysisPass);
     536      253575 :       else if (PDepth > APDepth)
     537      253575 :         LastPMUses.push_back(AnalysisPass);
     538             :     }
     539             : 
     540     8186624 :     setLastUser(LastUses, P);
     541             : 
     542             :     // If this pass has a corresponding pass manager, push higher level
     543             :     // analysis to this pass manager.
     544     8186641 :     if (P->getResolver())
     545    16324392 :       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
     546             : 
     547             : 
     548             :     // If AP is the last user of other passes then make P last user of
     549             :     // such passes.
     550   723530695 :     for (auto LU : LastUser) {
     551   707157394 :       if (LU.second == AP)
     552             :         // DenseMap iterator is not invalidated here because
     553             :         // this is just updating existing entries.
     554      718281 :         LastUser[LU.first] = P;
     555             :     }
     556             :   }
     557    22126423 : }
     558             : 
     559             : /// Collect passes whose last user is P
     560    30826693 : void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
     561             :                                         Pass *P) {
     562             :   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
     563    30826693 :     InversedLastUser.find(P);
     564    30826709 :   if (DMI == InversedLastUser.end())
     565    14021833 :     return;
     566             : 
     567             :   SmallPtrSet<Pass *, 8> &LU = DMI->second;
     568    47610348 :   for (Pass *LUP : LU) {
     569    30805472 :     LastUses.push_back(LUP);
     570             :   }
     571             : 
     572             : }
     573             : 
     574    80104567 : AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
     575             :   AnalysisUsage *AnUsage = nullptr;
     576    80104567 :   auto DMI = AnUsageMap.find(P);
     577    80104765 :   if (DMI != AnUsageMap.end())
     578    76565441 :     AnUsage = DMI->second;
     579             :   else {
     580             :     // Look up the analysis usage from the pass instance (different instances
     581             :     // of the same pass can produce different results), but unique the
     582             :     // resulting object to reduce memory usage.  This helps to greatly reduce
     583             :     // memory usage when we have many instances of only a few pass types
     584             :     // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
     585             :     // of dependencies.
     586     3539323 :     AnalysisUsage AU;
     587     3539324 :     P->getAnalysisUsage(AU);
     588             :     
     589             :     AUFoldingSetNode* Node = nullptr;
     590             :     FoldingSetNodeID ID;
     591     3539315 :     AUFoldingSetNode::Profile(ID, AU);
     592     3539331 :     void *IP = nullptr;
     593     3539327 :     if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
     594             :       Node = N;
     595             :     else {
     596             :       Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
     597     1576657 :       UniqueAnalysisUsages.InsertNode(Node, IP);
     598             :     }
     599             :     assert(Node && "cached analysis usage must be non null");
     600             : 
     601     3539323 :     AnUsageMap[P] = &Node->AU;
     602             :     AnUsage = &Node->AU;
     603             :   }
     604    80104765 :   return AnUsage;
     605             : }
     606             : 
     607             : /// Schedule pass P for execution. Make sure that passes required by
     608             : /// P are run before P is run. Update analysis info maintained by
     609             : /// the manager. Remove dead passes. This is a recursive function.
     610     3482855 : void PMTopLevelManager::schedulePass(Pass *P) {
     611             : 
     612             :   // TODO : Allocate function manager for this pass, other wise required set
     613             :   // may be inserted into previous function manager
     614             : 
     615             :   // Give pass a chance to prepare the stage.
     616     3482855 :   P->preparePassManager(activeStack);
     617             : 
     618             :   // If P is an analysis pass and it is available then do not
     619             :   // generate the analysis again. Stale analysis info should not be
     620             :   // available at this point.
     621     3482853 :   const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
     622     3482848 :   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
     623        6100 :     delete P;
     624             :     return;
     625             :   }
     626             : 
     627     3476749 :   AnalysisUsage *AnUsage = findAnalysisUsage(P);
     628             : 
     629             :   bool checkAnalysis = true;
     630     7084198 :   while (checkAnalysis) {
     631             :     checkAnalysis = false;
     632             : 
     633             :     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
     634    17657791 :     for (const AnalysisID ID : RequiredSet) {
     635             : 
     636     7025167 :       Pass *AnalysisPass = findAnalysisPass(ID);
     637     7025189 :       if (!AnalysisPass) {
     638     1422027 :         const PassInfo *PI = findAnalysisPassInfo(ID);
     639             : 
     640     1422027 :         if (!PI) {
     641             :           // Pass P is not in the global PassRegistry
     642           0 :           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
     643           0 :           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
     644           0 :           dbgs() << "Required Passes:" << "\n";
     645           0 :           for (const AnalysisID ID2 : RequiredSet) {
     646           0 :             if (ID == ID2)
     647             :               break;
     648           0 :             Pass *AnalysisPass2 = findAnalysisPass(ID2);
     649           0 :             if (AnalysisPass2) {
     650           0 :               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
     651             :             } else {
     652           0 :               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
     653           0 :               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
     654           0 :               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
     655             :             }
     656             :           }
     657             :         }
     658             : 
     659             :         assert(PI && "Expected required passes to be initialized");
     660     1422027 :         AnalysisPass = PI->createPass();
     661     2844051 :         if (P->getPotentialPassManagerType () ==
     662     1422027 :             AnalysisPass->getPotentialPassManagerType())
     663             :           // Schedule analysis pass that is managed by the same pass manager.
     664     1192584 :           schedulePass(AnalysisPass);
     665      458886 :         else if (P->getPotentialPassManagerType () >
     666      229443 :                  AnalysisPass->getPotentialPassManagerType()) {
     667             :           // Schedule analysis pass that is managed by a new manager.
     668      222097 :           schedulePass(AnalysisPass);
     669             :           // Recheck analysis passes to ensure that required analyses that
     670             :           // are already checked are still available.
     671             :           checkAnalysis = true;
     672             :         } else
     673             :           // Do not schedule this analysis. Lower level analysis
     674             :           // passes are run on the fly.
     675        7346 :           delete AnalysisPass;
     676             :       }
     677             :     }
     678             :   }
     679             : 
     680             :   // Now all required passes are available.
     681     3476749 :   if (ImmutablePass *IP = P->getAsImmutablePass()) {
     682             :     // P is a immutable pass and it will be managed by this
     683             :     // top level manager. Set up analysis resolver to connect them.
     684      291656 :     PMDataManager *DM = getAsPMDataManager();
     685      291656 :     AnalysisResolver *AR = new AnalysisResolver(*DM);
     686      291656 :     P->setResolver(AR);
     687      291656 :     DM->initializeAnalysisImpl(P);
     688      291655 :     addImmutablePass(IP);
     689      291656 :     DM->recordAvailableAnalysis(IP);
     690      291656 :     return;
     691             :   }
     692             : 
     693     3185094 :   if (PI && !PI->isAnalysis() && ShouldPrintBeforePass(PI)) {
     694           6 :     Pass *PP = P->createPrinterPass(
     695          30 :         dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str());
     696           6 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     697             :   }
     698             : 
     699             :   // Add the requested pass to the best available pass manager.
     700     3185094 :   P->assignPassManager(activeStack, getTopLevelPassManagerType());
     701             : 
     702     3185094 :   if (PI && !PI->isAnalysis() && ShouldPrintAfterPass(PI)) {
     703         436 :     Pass *PP = P->createPrinterPass(
     704        2180 :         dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str());
     705         436 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     706             :   }
     707             : }
     708             : 
     709             : /// Find the pass that implements Analysis AID. Search immutable
     710             : /// passes and all pass managers. If desired pass is not found
     711             : /// then return NULL.
     712    63297157 : Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
     713             :   // For immutable passes we have a direct mapping from ID to pass, so check
     714             :   // that first.
     715   107024434 :   if (Pass *P = ImmutablePassMap.lookup(AID))
     716             :     return P;
     717             : 
     718             :   // Check pass managers
     719    57080508 :   for (PMDataManager *PassManager : PassManagers)
     720    19570070 :     if (Pass *P = PassManager->findAnalysisPass(AID, false))
     721             :       return P;
     722             : 
     723             :   // Check other pass managers
     724   474223915 :   for (PMDataManager *IndirectPassManager : IndirectPassManagers)
     725   231544261 :     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
     726             :       return P;
     727             : 
     728             :   return nullptr;
     729             : }
     730             : 
     731    70387974 : const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
     732    70387974 :   const PassInfo *&PI = AnalysisPassInfos[AID];
     733    70387968 :   if (!PI)
     734     6270617 :     PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
     735             :   else
     736             :     assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
     737             :            "The pass info pointer changed for an analysis ID!");
     738             : 
     739    70387970 :   return PI;
     740             : }
     741             : 
     742      291656 : void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
     743      291656 :   P->initializePass();
     744      291655 :   ImmutablePasses.push_back(P);
     745             : 
     746             :   // Add this pass to the map from its analysis ID. We clobber any prior runs
     747             :   // of the pass in the map so that the last one added is the one found when
     748             :   // doing lookups.
     749      291655 :   AnalysisID AID = P->getPassID();
     750      583311 :   ImmutablePassMap[AID] = P;
     751             : 
     752             :   // Also add any interfaces implemented by the immutable pass to the map for
     753             :   // fast lookup.
     754      291656 :   const PassInfo *PassInf = findAnalysisPassInfo(AID);
     755             :   assert(PassInf && "Expected all immutable passes to be initialized");
     756      291656 :   for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented())
     757           0 :     ImmutablePassMap[ImmPI->getTypeInfo()] = P;
     758      291656 : }
     759             : 
     760             : // Print passes managed by this top level manager.
     761       57693 : void PMTopLevelManager::dumpPasses() const {
     762             : 
     763       57693 :   if (PassDebugging < Structure)
     764             :     return;
     765             : 
     766             :   // Print out the immutable passes
     767         345 :   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
     768         562 :     ImmutablePasses[i]->dumpPassStructure(0);
     769             :   }
     770             : 
     771             :   // Every class that derives from PMDataManager also derives from Pass
     772             :   // (sometimes indirectly), but there's no inheritance relationship
     773             :   // between PMDataManager and Pass, so we have to getAsPass to get
     774             :   // from a PMDataManager* to a Pass*.
     775         192 :   for (PMDataManager *Manager : PassManagers)
     776          64 :     Manager->getAsPass()->dumpPassStructure(1);
     777             : }
     778             : 
     779       57693 : void PMTopLevelManager::dumpArguments() const {
     780             : 
     781       57693 :   if (PassDebugging < Arguments)
     782             :     return;
     783             : 
     784         133 :   dbgs() << "Pass Arguments: ";
     785        1209 :   for (ImmutablePass *P : ImmutablePasses)
     786         538 :     if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) {
     787             :       assert(PI && "Expected all immutable passes to be initialized");
     788         538 :       if (!PI->isAnalysisGroup())
     789         538 :         dbgs() << " -" << PI->getPassArgument();
     790             :     }
     791         399 :   for (PMDataManager *PM : PassManagers)
     792         133 :     PM->dumpPassArguments();
     793         133 :   dbgs() << "\n";
     794             : }
     795             : 
     796      185431 : void PMTopLevelManager::initializeAllAnalysisInfo() {
     797      556293 :   for (PMDataManager *PM : PassManagers)
     798             :     PM->initializeAnalysisInfo();
     799             : 
     800             :   // Initailize other pass managers
     801      612867 :   for (PMDataManager *IPM : IndirectPassManagers)
     802             :     IPM->initializeAnalysisInfo();
     803             : 
     804     4248586 :   for (auto LU : LastUser) {
     805     3877724 :     SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
     806     3877722 :     L.insert(LU.first);
     807             :   }
     808      185431 : }
     809             : 
     810             : /// Destructor
     811      230737 : PMTopLevelManager::~PMTopLevelManager() {
     812      173053 :   for (PMDataManager *PM : PassManagers)
     813       57684 :     delete PM;
     814             : 
     815      638229 :   for (ImmutablePass *P : ImmutablePasses)
     816      290273 :     delete P;
     817       57684 : }
     818             : 
     819             : //===----------------------------------------------------------------------===//
     820             : // PMDataManager implementation
     821             : 
     822             : /// Augement AvailableAnalysis by adding analysis made available by pass P.
     823    34361839 : void PMDataManager::recordAvailableAnalysis(Pass *P) {
     824    34361839 :   AnalysisID PI = P->getPassID();
     825             : 
     826    68723677 :   AvailableAnalysis[PI] = P;
     827             : 
     828             :   assert(!AvailableAnalysis.empty());
     829             : 
     830             :   // This pass is the current implementation of all of the interfaces it
     831             :   // implements as well.
     832    34361838 :   const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
     833    36631159 :   if (!PInf) return;
     834             :   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     835    64185082 :   for (unsigned i = 0, e = II.size(); i != e; ++i)
     836           0 :     AvailableAnalysis[II[i]->getTypeInfo()] = P;
     837             : }
     838             : 
     839             : // Return true if P preserves high level analysis used by other
     840             : // passes managed by this manager
     841        9308 : bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
     842        9308 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     843        9308 :   if (AnUsage->getPreservesAll())
     844             :     return true;
     845             : 
     846             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     847      172716 :   for (Pass *P1 : HigherLevelAnalysis) {
     848      156211 :     if (P1->getAsImmutablePass() == nullptr &&
     849       73000 :         !is_contained(PreservedSet, P1->getPassID()))
     850             :       return false;
     851             :   }
     852             : 
     853             :   return true;
     854             : }
     855             : 
     856             : /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
     857    30822118 : void PMDataManager::verifyPreservedAnalysis(Pass *P) {
     858             :   // Don't do this unless assertions are enabled.
     859             : #ifdef NDEBUG
     860             :   return;
     861             : #endif
     862             :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     863             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     864             : 
     865             :   // Verify preserved analysis
     866             :   for (AnalysisID AID : PreservedSet) {
     867             :     if (Pass *AP = findAnalysisPass(AID, true)) {
     868             :       TimeRegion PassTimer(getPassTimer(AP));
     869             :       AP->verifyAnalysis();
     870             :     }
     871             :   }
     872             : }
     873             : 
     874             : /// Remove Analysis not preserved by Pass P
     875    34070193 : void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
     876    34070193 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     877    34070189 :   if (AnUsage->getPreservesAll())
     878             :     return;
     879             : 
     880             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     881    61684613 :   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
     882    61684579 :          E = AvailableAnalysis.end(); I != E; ) {
     883             :     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
     884    91547639 :     if (Info->second->getAsImmutablePass() == nullptr &&
     885    45773831 :         !is_contained(PreservedSet, Info->first)) {
     886             :       // Remove this analysis
     887     9712750 :       if (PassDebugging >= Details) {
     888           2 :         Pass *S = Info->second;
     889           2 :         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     890           2 :         dbgs() << S->getPassName() << "'\n";
     891             :       }
     892             :       AvailableAnalysis.erase(Info);
     893             :     }
     894             :   }
     895             : 
     896             :   // Check inherited analysis also. If P is not preserving analysis
     897             :   // provided by parent manager then remove it here.
     898   238661489 :   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
     899             : 
     900   111375360 :     if (!InheritedAnalysis[Index])
     901    80841541 :       continue;
     902             : 
     903    26515354 :     for (DenseMap<AnalysisID, Pass*>::iterator
     904    30533819 :            I = InheritedAnalysis[Index]->begin(),
     905    87582984 :            E = InheritedAnalysis[Index]->end(); I != E; ) {
     906             :       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
     907    53030705 :       if (Info->second->getAsImmutablePass() == nullptr &&
     908    26515354 :           !is_contained(PreservedSet, Info->first)) {
     909             :         // Remove this analysis
     910      250495 :         if (PassDebugging >= Details) {
     911           1 :           Pass *S = Info->second;
     912           1 :           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     913           1 :           dbgs() << S->getPassName() << "'\n";
     914             :         }
     915      250495 :         InheritedAnalysis[Index]->erase(Info);
     916             :       }
     917             :     }
     918             :   }
     919             : }
     920             : 
     921             : /// Remove analysis passes that are not used any longer
     922    30822546 : void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
     923             :                                      enum PassDebuggingString DBG_STR) {
     924             : 
     925             :   SmallVector<Pass *, 12> DeadPasses;
     926             : 
     927             :   // If this is a on the fly manager then it does not have TPM.
     928    30822546 :   if (!TPM)
     929             :     return;
     930             : 
     931    30822546 :   TPM->collectLastUses(DeadPasses, P);
     932             : 
     933    30822551 :   if (PassDebugging >= Details && !DeadPasses.empty()) {
     934           3 :     dbgs() << " -*- '" <<  P->getPassName();
     935           3 :     dbgs() << "' is the last user of following pass instances.";
     936           3 :     dbgs() << " Free these instances\n";
     937             :   }
     938             : 
     939    92433465 :   for (Pass *P : DeadPasses)
     940    30805457 :     freePass(P, Msg, DBG_STR);
     941             : }
     942             : 
     943    30806613 : void PMDataManager::freePass(Pass *P, StringRef Msg,
     944             :                              enum PassDebuggingString DBG_STR) {
     945    30806613 :   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
     946             : 
     947             :   {
     948             :     // If the pass crashes releasing memory, remember this.
     949             :     PassManagerPrettyStackEntry X(P);
     950    30806622 :     TimeRegion PassTimer(getPassTimer(P));
     951             : 
     952    30806623 :     P->releaseMemory();
     953             :   }
     954             : 
     955    30806612 :   AnalysisID PI = P->getPassID();
     956    30806612 :   if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
     957             :     // Remove the pass itself (if it is not already removed).
     958    29294437 :     AvailableAnalysis.erase(PI);
     959             : 
     960             :     // Remove all interfaces this pass implements, for which it is also
     961             :     // listed as the available implementation.
     962             :     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     963    58588868 :     for (unsigned i = 0, e = II.size(); i != e; ++i) {
     964             :       DenseMap<AnalysisID, Pass*>::iterator Pos =
     965           0 :         AvailableAnalysis.find(II[i]->getTypeInfo());
     966           0 :       if (Pos != AvailableAnalysis.end() && Pos->second == P)
     967             :         AvailableAnalysis.erase(Pos);
     968             :     }
     969             :   }
     970    30806615 : }
     971             : 
     972             : /// Add pass P into the PassVector. Update
     973             : /// AvailableAnalysis appropriately if ProcessAnalysis is true.
     974     3247666 : void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
     975             :   // This manager is going to manage pass P. Set up analysis resolver
     976             :   // to connect them.
     977     3247666 :   AnalysisResolver *AR = new AnalysisResolver(*this);
     978     3247673 :   P->setResolver(AR);
     979             : 
     980             :   // If a FunctionPass F is the last user of ModulePass info M
     981             :   // then the F's manager, not F, records itself as a last user of M.
     982             :   SmallVector<Pass *, 12> TransferLastUses;
     983             : 
     984     3247673 :   if (!ProcessAnalysis) {
     985             :     // Add pass
     986           0 :     PassVector.push_back(P);
     987             :     return;
     988             :   }
     989             : 
     990             :   // At the moment, this pass is the last user of all required passes.
     991             :   SmallVector<Pass *, 12> LastUses;
     992             :   SmallVector<Pass *, 8> UsedPasses;
     993             :   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
     994             : 
     995     3247673 :   unsigned PDepth = this->getDepth();
     996             : 
     997     3247673 :   collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
     998    17309315 :   for (Pass *PUsed : UsedPasses) {
     999             :     unsigned RDepth = 0;
    1000             : 
    1001             :     assert(PUsed->getResolver() && "Analysis Resolver is not set");
    1002     7030825 :     PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
    1003     7030825 :     RDepth = DM.getDepth();
    1004             : 
    1005     7030825 :     if (PDepth == RDepth)
    1006     3201258 :       LastUses.push_back(PUsed);
    1007     3829567 :     else if (PDepth > RDepth) {
    1008             :       // Let the parent claim responsibility of last use
    1009     3829567 :       TransferLastUses.push_back(PUsed);
    1010             :       // Keep track of higher level analysis used by this manager.
    1011     3829567 :       HigherLevelAnalysis.push_back(PUsed);
    1012             :     } else
    1013           0 :       llvm_unreachable("Unable to accommodate Used Pass");
    1014             :   }
    1015             : 
    1016             :   // Set P as P's last user until someone starts using P.
    1017             :   // However, if P is a Pass Manager then it does not need
    1018             :   // to record its last user.
    1019     3247672 :   if (!P->getAsPMDataManager())
    1020     3140685 :     LastUses.push_back(P);
    1021     6495348 :   TPM->setLastUser(LastUses, P);
    1022             : 
    1023     3247664 :   if (!TransferLastUses.empty()) {
    1024     2522809 :     Pass *My_PM = getAsPass();
    1025     5045618 :     TPM->setLastUser(TransferLastUses, My_PM);
    1026             :     TransferLastUses.clear();
    1027             :   }
    1028             : 
    1029             :   // Now, take care of required analyses that are not available.
    1030     3262367 :   for (AnalysisID ID : ReqAnalysisNotAvailable) {
    1031        7351 :     const PassInfo *PI = TPM->findAnalysisPassInfo(ID);
    1032        7351 :     Pass *AnalysisPass = PI->createPass();
    1033        7351 :     this->addLowerLevelRequiredPass(P, AnalysisPass);
    1034             :   }
    1035             : 
    1036             :   // Take a note of analysis required and made available by this pass.
    1037             :   // Remove the analysis not preserved by this pass
    1038     3247665 :   removeNotPreservedAnalysis(P);
    1039     3247670 :   recordAvailableAnalysis(P);
    1040             : 
    1041             :   // Add pass
    1042     3247665 :   PassVector.push_back(P);
    1043             : }
    1044             : 
    1045             : 
    1046             : /// Populate UP with analysis pass that are used or required by
    1047             : /// pass P and are available. Populate RP_NotAvail with analysis
    1048             : /// pass that are required by pass P but are not available.
    1049     3247672 : void PMDataManager::collectRequiredAndUsedAnalyses(
    1050             :     SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
    1051             :     Pass *P) {
    1052     3247672 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1053             : 
    1054     4266804 :   for (const auto &UsedID : AnUsage->getUsedSet())
    1055      509566 :     if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
    1056      171217 :       UP.push_back(AnalysisPass);
    1057             : 
    1058    16271088 :   for (const auto &RequiredID : AnUsage->getRequiredSet())
    1059     6511708 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1060     6504356 :       UP.push_back(AnalysisPass);
    1061             :     else
    1062        7351 :       RP_NotAvail.push_back(RequiredID);
    1063             : 
    1064     3958148 :   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
    1065      355238 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1066      355238 :       UP.push_back(AnalysisPass);
    1067             :     else
    1068           0 :       RP_NotAvail.push_back(RequiredID);
    1069     3247672 : }
    1070             : 
    1071             : // All Required analyses should be available to the pass as it runs!  Here
    1072             : // we fill in the AnalysisImpls member of the pass so that it can
    1073             : // successfully use the getAnalysis() method to retrieve the
    1074             : // implementations it needs.
    1075             : //
    1076    31114540 : void PMDataManager::initializeAnalysisImpl(Pass *P) {
    1077    31114540 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1078             : 
    1079   158896801 :   for (const AnalysisID ID : AnUsage->getRequiredSet()) {
    1080    63891120 :     Pass *Impl = findAnalysisPass(ID, true);
    1081    63891078 :     if (!Impl)
    1082             :       // This may be analysis pass that is initialized on the fly.
    1083             :       // If that is not the case then it will raise an assert when it is used.
    1084      145234 :       continue;
    1085    63745844 :     AnalysisResolver *AR = P->getResolver();
    1086             :     assert(AR && "Analysis Resolver is not set");
    1087    63745844 :     AR->addAnalysisImplsPair(ID, Impl);
    1088             :   }
    1089    31114549 : }
    1090             : 
    1091             : /// Find the pass that implements Analysis AID. If desired pass is not found
    1092             : /// then return NULL.
    1093   340009106 : Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
    1094             : 
    1095             :   // Check if AvailableAnalysis map has one entry.
    1096   680019518 :   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
    1097             : 
    1098   340010412 :   if (I != AvailableAnalysis.end())
    1099    39814703 :     return I->second;
    1100             : 
    1101             :   // Search Parents through TopLevelManager
    1102   300195709 :   if (SearchParent)
    1103    53708185 :     return TPM->findAnalysisPass(AID);
    1104             : 
    1105             :   return nullptr;
    1106             : }
    1107             : 
    1108             : // Print list of passes that are last used by P.
    1109        4147 : void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
    1110             : 
    1111             :   SmallVector<Pass *, 12> LUses;
    1112             : 
    1113             :   // If this is a on the fly manager then it does not have TPM.
    1114        4147 :   if (!TPM)
    1115             :     return;
    1116             : 
    1117        4147 :   TPM->collectLastUses(LUses, P);
    1118             : 
    1119        4147 :   for (Pass *P : LUses) {
    1120           0 :     dbgs() << "--" << std::string(Offset*2, ' ');
    1121           0 :     P->dumpPassStructure(0);
    1122             :   }
    1123             : }
    1124             : 
    1125         530 : void PMDataManager::dumpPassArguments() const {
    1126       17198 :   for (Pass *P : PassVector) {
    1127        8334 :     if (PMDataManager *PMD = P->getAsPMDataManager())
    1128         397 :       PMD->dumpPassArguments();
    1129             :     else
    1130        7937 :       if (const PassInfo *PI =
    1131        7937 :             TPM->findAnalysisPassInfo(P->getPassID()))
    1132        7732 :         if (!PI->isAnalysisGroup())
    1133        7732 :           dbgs() << " -" << PI->getPassArgument();
    1134             :   }
    1135         530 : }
    1136             : 
    1137    63921507 : void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
    1138             :                                  enum PassDebuggingString S2,
    1139             :                                  StringRef Msg) {
    1140    63921507 :   if (PassDebugging < Executions)
    1141             :     return;
    1142          42 :   dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this
    1143          84 :          << std::string(getDepth() * 2 + 1, ' ');
    1144          42 :   switch (S1) {
    1145          19 :   case EXECUTION_MSG:
    1146          19 :     dbgs() << "Executing Pass '" << P->getPassName();
    1147          19 :     break;
    1148           5 :   case MODIFICATION_MSG:
    1149           5 :     dbgs() << "Made Modification '" << P->getPassName();
    1150           5 :     break;
    1151          18 :   case FREEING_MSG:
    1152          18 :     dbgs() << " Freeing Pass '" << P->getPassName();
    1153          18 :     break;
    1154             :   default:
    1155             :     break;
    1156             :   }
    1157          42 :   switch (S2) {
    1158           0 :   case ON_BASICBLOCK_MSG:
    1159           0 :     dbgs() << "' on BasicBlock '" << Msg << "'...\n";
    1160           0 :     break;
    1161          22 :   case ON_FUNCTION_MSG:
    1162          22 :     dbgs() << "' on Function '" << Msg << "'...\n";
    1163          22 :     break;
    1164          12 :   case ON_MODULE_MSG:
    1165          12 :     dbgs() << "' on Module '"  << Msg << "'...\n";
    1166          12 :     break;
    1167           0 :   case ON_REGION_MSG:
    1168           0 :     dbgs() << "' on Region '"  << Msg << "'...\n";
    1169           0 :     break;
    1170           0 :   case ON_LOOP_MSG:
    1171           0 :     dbgs() << "' on Loop '" << Msg << "'...\n";
    1172           0 :     break;
    1173           8 :   case ON_CG_MSG:
    1174           8 :     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
    1175           8 :     break;
    1176             :   default:
    1177             :     break;
    1178             :   }
    1179             : }
    1180             : 
    1181    30776239 : void PMDataManager::dumpRequiredSet(const Pass *P) const {
    1182    30776239 :   if (PassDebugging < Details)
    1183    30776229 :     return;
    1184             : 
    1185          10 :   AnalysisUsage analysisUsage;
    1186          10 :   P->getAnalysisUsage(analysisUsage);
    1187          10 :   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
    1188             : }
    1189             : 
    1190    30775939 : void PMDataManager::dumpPreservedSet(const Pass *P) const {
    1191    30775939 :   if (PassDebugging < Details)
    1192    30775929 :     return;
    1193             : 
    1194          10 :   AnalysisUsage analysisUsage;
    1195          10 :   P->getAnalysisUsage(analysisUsage);
    1196          10 :   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
    1197             : }
    1198             : 
    1199    30293373 : void PMDataManager::dumpUsedSet(const Pass *P) const {
    1200    30293373 :   if (PassDebugging < Details)
    1201    30293363 :     return;
    1202             : 
    1203          10 :   AnalysisUsage analysisUsage;
    1204          10 :   P->getAnalysisUsage(analysisUsage);
    1205          10 :   dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
    1206             : }
    1207             : 
    1208          30 : void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
    1209             :                                    const AnalysisUsage::VectorType &Set) const {
    1210             :   assert(PassDebugging >= Details);
    1211          30 :   if (Set.empty())
    1212             :     return;
    1213          27 :   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
    1214         186 :   for (unsigned i = 0; i != Set.size(); ++i) {
    1215          56 :     if (i) dbgs() << ',';
    1216         112 :     const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
    1217          56 :     if (!PInf) {
    1218             :       // Some preserved passes, such as AliasAnalysis, may not be initialized by
    1219             :       // all drivers.
    1220           0 :       dbgs() << " Uninitialized Pass";
    1221           0 :       continue;
    1222             :     }
    1223         112 :     dbgs() << ' ' << PInf->getPassName();
    1224             :   }
    1225           9 :   dbgs() << '\n';
    1226             : }
    1227             : 
    1228             : /// Add RequiredPass into list of lower level passes required by pass P.
    1229             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1230             : /// through getAnalysis interface.
    1231             : /// This should be handled by specific pass manager.
    1232           0 : void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1233           0 :   if (TPM) {
    1234           0 :     TPM->dumpArguments();
    1235           0 :     TPM->dumpPasses();
    1236             :   }
    1237             : 
    1238             :   // Module Level pass may required Function Level analysis info
    1239             :   // (e.g. dominator info). Pass manager uses on the fly function pass manager
    1240             :   // to provide this on demand. In that case, in Pass manager terminology,
    1241             :   // module level pass is requiring lower level analysis info managed by
    1242             :   // lower level pass manager.
    1243             : 
    1244             :   // When Pass manager is not able to order required analysis info, Pass manager
    1245             :   // checks whether any lower level manager will be able to provide this
    1246             :   // analysis info on demand or not.
    1247             : #ifndef NDEBUG
    1248             :   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
    1249             :   dbgs() << "' required by '" << P->getPassName() << "'\n";
    1250             : #endif
    1251           0 :   llvm_unreachable("Unable to schedule pass");
    1252             : }
    1253             : 
    1254           0 : Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
    1255           0 :   llvm_unreachable("Unable to find on the fly pass");
    1256             : }
    1257             : 
    1258             : // Destructor
    1259      443643 : PMDataManager::~PMDataManager() {
    1260     6684981 :   for (Pass *P : PassVector)
    1261     3231581 :     delete P;
    1262      221820 : }
    1263             : 
    1264             : //===----------------------------------------------------------------------===//
    1265             : // NOTE: Is this the right place to define this method ?
    1266             : // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
    1267    17630436 : Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
    1268    17630436 :   return PM.findAnalysisPass(ID, dir);
    1269             : }
    1270             : 
    1271        5030 : Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
    1272             :                                      Function &F) {
    1273        5030 :   return PM.getOnTheFlyPass(P, AnalysisPI, F);
    1274             : }
    1275             : 
    1276             : //===----------------------------------------------------------------------===//
    1277             : // BBPassManager implementation
    1278             : 
    1279             : /// Execute all of the passes scheduled for execution by invoking
    1280             : /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
    1281             : /// the function, and if so, return true.
    1282        1121 : bool BBPassManager::runOnFunction(Function &F) {
    1283        1121 :   if (F.isDeclaration())
    1284             :     return false;
    1285             : 
    1286             :   bool Changed = doInitialization(F);
    1287             : 
    1288        2418 :   for (BasicBlock &BB : F)
    1289        3891 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1290             :       BasicBlockPass *BP = getContainedPass(Index);
    1291             :       bool LocalChanged = false;
    1292             : 
    1293        1297 :       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, BB.getName());
    1294        1297 :       dumpRequiredSet(BP);
    1295             : 
    1296        1297 :       initializeAnalysisImpl(BP);
    1297             : 
    1298             :       {
    1299             :         // If the pass crashes, remember this.
    1300             :         PassManagerPrettyStackEntry X(BP, BB);
    1301        1297 :         TimeRegion PassTimer(getPassTimer(BP));
    1302             : 
    1303        1297 :         LocalChanged |= BP->runOnBasicBlock(BB);
    1304             :       }
    1305             : 
    1306        1297 :       Changed |= LocalChanged;
    1307        1297 :       if (LocalChanged)
    1308          68 :         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
    1309             :                      BB.getName());
    1310        1297 :       dumpPreservedSet(BP);
    1311        1297 :       dumpUsedSet(BP);
    1312             : 
    1313        1297 :       verifyPreservedAnalysis(BP);
    1314        1297 :       removeNotPreservedAnalysis(BP);
    1315        1297 :       recordAvailableAnalysis(BP);
    1316        1297 :       removeDeadPasses(BP, BB.getName(), ON_BASICBLOCK_MSG);
    1317             :     }
    1318             : 
    1319        1121 :   return doFinalization(F) || Changed;
    1320             : }
    1321             : 
    1322             : // Implement doInitialization and doFinalization
    1323         241 : bool BBPassManager::doInitialization(Module &M) {
    1324             :   bool Changed = false;
    1325             : 
    1326         723 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1327         241 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1328             : 
    1329         241 :   return Changed;
    1330             : }
    1331             : 
    1332         234 : bool BBPassManager::doFinalization(Module &M) {
    1333             :   bool Changed = false;
    1334             : 
    1335         468 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1336         468 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1337             : 
    1338         234 :   return Changed;
    1339             : }
    1340             : 
    1341             : bool BBPassManager::doInitialization(Function &F) {
    1342             :   bool Changed = false;
    1343             : 
    1344        3363 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1345             :     BasicBlockPass *BP = getContainedPass(Index);
    1346        1121 :     Changed |= BP->doInitialization(F);
    1347             :   }
    1348             : 
    1349             :   return Changed;
    1350             : }
    1351             : 
    1352             : bool BBPassManager::doFinalization(Function &F) {
    1353             :   bool Changed = false;
    1354             : 
    1355        3363 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1356             :     BasicBlockPass *BP = getContainedPass(Index);
    1357        1121 :     Changed |= BP->doFinalization(F);
    1358             :   }
    1359             : 
    1360             :   return Changed;
    1361             : }
    1362             : 
    1363             : 
    1364             : //===----------------------------------------------------------------------===//
    1365             : // FunctionPassManager implementation
    1366             : 
    1367             : /// Create new Function pass manager
    1368        8439 : FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
    1369        8439 :   FPM = new FunctionPassManagerImpl();
    1370             :   // FPM is the top level manager.
    1371        8439 :   FPM->setTopLevelManager(FPM);
    1372             : 
    1373        8439 :   AnalysisResolver *AR = new AnalysisResolver(*FPM);
    1374        8439 :   FPM->setResolver(AR);
    1375        8439 : }
    1376             : 
    1377       17040 : FunctionPassManager::~FunctionPassManager() {
    1378        8436 :   delete FPM;
    1379        8604 : }
    1380             : 
    1381       37226 : void FunctionPassManager::add(Pass *P) {
    1382       37226 :   FPM->add(P);
    1383       37226 : }
    1384             : 
    1385             : /// run - Execute all of the passes scheduled for execution.  Keep
    1386             : /// track of whether any of the passes modifies the function, and if
    1387             : /// so, return true.
    1388             : ///
    1389      135467 : bool FunctionPassManager::run(Function &F) {
    1390      270934 :   handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) {
    1391           0 :     report_fatal_error("Error reading bitcode file: " + EIB.message());
    1392             :   });
    1393      135467 :   return FPM->run(F);
    1394             : }
    1395             : 
    1396             : 
    1397             : /// doInitialization - Run all of the initializers for the function passes.
    1398             : ///
    1399        8406 : bool FunctionPassManager::doInitialization() {
    1400        8406 :   return FPM->doInitialization(*M);
    1401             : }
    1402             : 
    1403             : /// doFinalization - Run all of the finalizers for the function passes.
    1404             : ///
    1405        8406 : bool FunctionPassManager::doFinalization() {
    1406        8406 :   return FPM->doFinalization(*M);
    1407             : }
    1408             : 
    1409             : //===----------------------------------------------------------------------===//
    1410             : // FunctionPassManagerImpl implementation
    1411             : //
    1412       12759 : bool FunctionPassManagerImpl::doInitialization(Module &M) {
    1413             :   bool Changed = false;
    1414             : 
    1415       12759 :   dumpArguments();
    1416       12759 :   dumpPasses();
    1417             : 
    1418       57287 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1419       22264 :     Changed |= ImPass->doInitialization(M);
    1420             : 
    1421       38277 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1422       12759 :     Changed |= getContainedManager(Index)->doInitialization(M);
    1423             : 
    1424       12759 :   return Changed;
    1425             : }
    1426             : 
    1427       12748 : bool FunctionPassManagerImpl::doFinalization(Module &M) {
    1428             :   bool Changed = false;
    1429             : 
    1430       25496 :   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
    1431       25496 :     Changed |= getContainedManager(Index)->doFinalization(M);
    1432             : 
    1433       57272 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1434       22262 :     Changed |= ImPass->doFinalization(M);
    1435             : 
    1436       12748 :   return Changed;
    1437             : }
    1438             : 
    1439             : /// cleanup - After running all passes, clean up pass manager cache.
    1440      140497 : void FPPassManager::cleanup() {
    1441     1001839 :  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1442             :     FunctionPass *FP = getContainedPass(Index);
    1443      430671 :     AnalysisResolver *AR = FP->getResolver();
    1444             :     assert(AR && "Analysis Resolver is not set");
    1445             :     AR->clearAnalysisImpls();
    1446             :  }
    1447      140497 : }
    1448             : 
    1449        9372 : void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
    1450        9372 :   if (!wasRun)
    1451             :     return;
    1452       15090 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1453             :     FPPassManager *FPPM = getContainedManager(Index);
    1454       43892 :     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
    1455       19431 :       FPPM->getContainedPass(Index)->releaseMemory();
    1456             :     }
    1457             :   }
    1458        5030 :   wasRun = false;
    1459             : }
    1460             : 
    1461             : // Execute all the passes managed by this top level manager.
    1462             : // Return true if any function is modified by a pass.
    1463      140497 : bool FunctionPassManagerImpl::run(Function &F) {
    1464             :   bool Changed = false;
    1465      140497 :   TimingInfo::createTheTimeInfo();
    1466             : 
    1467      140497 :   initializeAllAnalysisInfo();
    1468      421491 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1469      140497 :     Changed |= getContainedManager(Index)->runOnFunction(F);
    1470      140497 :     F.getContext().yield();
    1471             :   }
    1472             : 
    1473      421491 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1474      140497 :     getContainedManager(Index)->cleanup();
    1475             : 
    1476      140497 :   wasRun = true;
    1477      140497 :   return Changed;
    1478             : }
    1479             : 
    1480             : //===----------------------------------------------------------------------===//
    1481             : // FPPassManager implementation
    1482             : 
    1483             : char FPPassManager::ID = 0;
    1484             : /// Print passes managed by this manager
    1485         113 : void FPPassManager::dumpPassStructure(unsigned Offset) {
    1486         113 :   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
    1487        7557 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1488             :     FunctionPass *FP = getContainedPass(Index);
    1489        3722 :     FP->dumpPassStructure(Offset + 1);
    1490        3722 :     dumpLastUses(FP, Offset+1);
    1491             :   }
    1492         113 : }
    1493             : 
    1494             : 
    1495             : /// Execute all of the passes scheduled for execution by invoking
    1496             : /// runOnFunction method.  Keep track of whether any of the passes modifies
    1497             : /// the function, and if so, return true.
    1498      893409 : bool FPPassManager::runOnFunction(Function &F) {
    1499      893409 :   if (F.isDeclaration())
    1500             :     return false;
    1501             : 
    1502             :   bool Changed = false;
    1503             : 
    1504             :   // Collect inherited analysis from Module level pass manager.
    1505      715336 :   populateInheritedAnalysis(TPM->activeStack);
    1506             : 
    1507    60924266 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1508             :     FunctionPass *FP = getContainedPass(Index);
    1509             :     bool LocalChanged = false;
    1510             : 
    1511    30104606 :     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
    1512    30104605 :     dumpRequiredSet(FP);
    1513             : 
    1514    30104605 :     initializeAnalysisImpl(FP);
    1515             : 
    1516             :     {
    1517             :       PassManagerPrettyStackEntry X(FP, F);
    1518    30104622 :       TimeRegion PassTimer(getPassTimer(FP));
    1519             : 
    1520    30104622 :       LocalChanged |= FP->runOnFunction(F);
    1521             :     }
    1522             : 
    1523    30104453 :     Changed |= LocalChanged;
    1524    30104453 :     if (LocalChanged)
    1525     2490945 :       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
    1526    30104454 :     dumpPreservedSet(FP);
    1527    30104457 :     dumpUsedSet(FP);
    1528             : 
    1529    30104458 :     verifyPreservedAnalysis(FP);
    1530    30104460 :     removeNotPreservedAnalysis(FP);
    1531    30104466 :     recordAvailableAnalysis(FP);
    1532    30104468 :     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
    1533             :   }
    1534             :   return Changed;
    1535             : }
    1536             : 
    1537       56793 : bool FPPassManager::runOnModule(Module &M) {
    1538             :   bool Changed = false;
    1539             : 
    1540      727817 :   for (Function &F : M)
    1541      671157 :     Changed |= runOnFunction(F);
    1542             : 
    1543       56660 :   return Changed;
    1544             : }
    1545             : 
    1546       74521 : bool FPPassManager::doInitialization(Module &M) {
    1547             :   bool Changed = false;
    1548             : 
    1549     6029847 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1550     2977677 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1551             : 
    1552       74507 :   return Changed;
    1553             : }
    1554             : 
    1555       74225 : bool FPPassManager::doFinalization(Module &M) {
    1556             :   bool Changed = false;
    1557             : 
    1558     3037072 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1559     5925754 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1560             : 
    1561       74195 :   return Changed;
    1562             : }
    1563             : 
    1564             : //===----------------------------------------------------------------------===//
    1565             : // MPPassManager implementation
    1566             : 
    1567             : /// Execute all of the passes scheduled for execution by invoking
    1568             : /// runOnModule method.  Keep track of whether any of the passes modifies
    1569             : /// the module, and if so, return true.
    1570             : bool
    1571       44934 : MPPassManager::runOnModule(Module &M) {
    1572             :   bool Changed = false;
    1573             : 
    1574             :   // Initialize on-the-fly passes
    1575       49287 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1576        4353 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1577        4353 :     Changed |= FPP->doInitialization(M);
    1578             :   }
    1579             : 
    1580             :   // Initialize module passes
    1581      420582 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1582      187833 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1583             : 
    1584      420169 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1585             :     ModulePass *MP = getContainedPass(Index);
    1586             :     bool LocalChanged = false;
    1587             : 
    1588      375534 :     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
    1589      187767 :     dumpRequiredSet(MP);
    1590             : 
    1591      187767 :     initializeAnalysisImpl(MP);
    1592             : 
    1593             :     {
    1594             :       PassManagerPrettyStackEntry X(MP, M);
    1595      187767 :       TimeRegion PassTimer(getPassTimer(MP));
    1596             : 
    1597      187767 :       LocalChanged |= MP->runOnModule(M);
    1598             :     }
    1599             : 
    1600      187622 :     Changed |= LocalChanged;
    1601      187622 :     if (LocalChanged)
    1602       33267 :       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
    1603             :                    M.getModuleIdentifier());
    1604      187622 :     dumpPreservedSet(MP);
    1605      187622 :     dumpUsedSet(MP);
    1606             : 
    1607      187622 :     verifyPreservedAnalysis(MP);
    1608      187622 :     removeNotPreservedAnalysis(MP);
    1609      187622 :     recordAvailableAnalysis(MP);
    1610      187622 :     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
    1611             :   }
    1612             : 
    1613             :   // Finalize module passes
    1614      231964 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1615      374384 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1616             : 
    1617             :   // Finalize on-the-fly passes
    1618       49114 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1619        4342 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1620             :     // We don't know when is the last time an on-the-fly pass is run,
    1621             :     // so we need to releaseMemory / finalize here
    1622        4342 :     FPP->releaseMemoryOnTheFly();
    1623        4342 :     Changed |= FPP->doFinalization(M);
    1624             :   }
    1625             : 
    1626       44772 :   return Changed;
    1627             : }
    1628             : 
    1629             : /// Add RequiredPass into list of lower level passes required by pass P.
    1630             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1631             : /// through getAnalysis interface.
    1632        7351 : void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1633             :   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
    1634             :          "Unable to handle Pass that requires lower level Analysis pass");
    1635             :   assert((P->getPotentialPassManagerType() <
    1636             :           RequiredPass->getPotentialPassManagerType()) &&
    1637             :          "Unable to handle Pass that requires lower level Analysis pass");
    1638        7351 :   if (!RequiredPass)
    1639           0 :     return;
    1640             : 
    1641        7351 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
    1642        7351 :   if (!FPP) {
    1643        4353 :     FPP = new FunctionPassManagerImpl();
    1644             :     // FPP is the top level manager.
    1645        4353 :     FPP->setTopLevelManager(FPP);
    1646             : 
    1647        4353 :     OnTheFlyManagers[P] = FPP;
    1648             :   }
    1649             :   const PassInfo *RequiredPassPI =
    1650        7351 :       TPM->findAnalysisPassInfo(RequiredPass->getPassID());
    1651             : 
    1652        7351 :   Pass *FoundPass = nullptr;
    1653        7351 :   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
    1654        7350 :     FoundPass =
    1655        7350 :       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
    1656             :   }
    1657        7351 :   if (!FoundPass) {
    1658        7351 :     FoundPass = RequiredPass;
    1659             :     // This should be guaranteed to add RequiredPass to the passmanager given
    1660             :     // that we checked for an available analysis above.
    1661             :     FPP->add(RequiredPass);
    1662             :   }
    1663             :   // Register P as the last user of FoundPass or RequiredPass.
    1664             :   SmallVector<Pass *, 1> LU;
    1665        7351 :   LU.push_back(FoundPass);
    1666       14702 :   FPP->setLastUser(LU,  P);
    1667             : }
    1668             : 
    1669             : /// Return function pass corresponding to PassInfo PI, that is
    1670             : /// required by module pass MP. Instantiate analysis pass, by using
    1671             : /// its runOnFunction() for function F.
    1672        5030 : Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
    1673        5030 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
    1674             :   assert(FPP && "Unable to find on the fly pass");
    1675             : 
    1676        5030 :   FPP->releaseMemoryOnTheFly();
    1677        5030 :   FPP->run(F);
    1678        5030 :   return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
    1679             : }
    1680             : 
    1681             : 
    1682             : //===----------------------------------------------------------------------===//
    1683             : // PassManagerImpl implementation
    1684             : 
    1685             : //
    1686             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1687             : /// whether any of the passes modifies the module, and if so, return true.
    1688       44934 : bool PassManagerImpl::run(Module &M) {
    1689             :   bool Changed = false;
    1690       44934 :   TimingInfo::createTheTimeInfo();
    1691             : 
    1692       44934 :   dumpArguments();
    1693       44934 :   dumpPasses();
    1694             : 
    1695      582832 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1696      268949 :     Changed |= ImPass->doInitialization(M);
    1697             : 
    1698       44934 :   initializeAllAnalysisInfo();
    1699      134476 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1700       44934 :     Changed |= getContainedManager(Index)->runOnModule(M);
    1701       44772 :     M.getContext().yield();
    1702             :   }
    1703             : 
    1704      580137 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1705      267682 :     Changed |= ImPass->doFinalization(M);
    1706             : 
    1707       44772 :   return Changed;
    1708             : }
    1709             : 
    1710             : //===----------------------------------------------------------------------===//
    1711             : // PassManager implementation
    1712             : 
    1713             : /// Create new pass manager
    1714       45111 : PassManager::PassManager() {
    1715       45111 :   PM = new PassManagerImpl();
    1716             :   // PM is the top level manager
    1717       45111 :   PM->setTopLevelManager(PM);
    1718       45111 : }
    1719             : 
    1720       89820 : PassManager::~PassManager() {
    1721       44906 :   delete PM;
    1722       44914 : }
    1723             : 
    1724     1978742 : void PassManager::add(Pass *P) {
    1725     1978742 :   PM->add(P);
    1726     1978741 : }
    1727             : 
    1728             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1729             : /// whether any of the passes modifies the module, and if so, return true.
    1730       44934 : bool PassManager::run(Module &M) {
    1731       44934 :   return PM->run(M);
    1732             : }
    1733             : 
    1734             : //===----------------------------------------------------------------------===//
    1735             : // TimingInfo implementation
    1736             : 
    1737             : bool llvm::TimePassesIsEnabled = false;
    1738       81710 : static cl::opt<bool, true> EnableTiming(
    1739      163420 :     "time-passes", cl::location(TimePassesIsEnabled), cl::Hidden,
    1740      245130 :     cl::desc("Time each pass, printing elapsed time for each on exit"));
    1741             : 
    1742             : // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
    1743             : // a non-null value (if the -time-passes option is enabled) or it leaves it
    1744             : // null.  It may be called multiple times.
    1745      185431 : void TimingInfo::createTheTimeInfo() {
    1746      185431 :   if (!TimePassesIsEnabled || TheTimeInfo) return;
    1747             : 
    1748             :   // Constructed the first time this is called, iff -time-passes is enabled.
    1749             :   // This guarantees that the object will be constructed before static globals,
    1750             :   // thus it will be destroyed before them.
    1751          10 :   static ManagedStatic<TimingInfo> TTI;
    1752          10 :   TheTimeInfo = &*TTI;
    1753             : }
    1754             : 
    1755             : /// If TimingInfo is enabled then start pass timer.
    1756    61722285 : Timer *llvm::getPassTimer(Pass *P) {
    1757    61722285 :   if (TheTimeInfo)
    1758        2128 :     return TheTimeInfo->getPassTimer(P);
    1759             :   return nullptr;
    1760             : }
    1761             : 
    1762             : /// If timing is enabled, report the times collected up to now and then reset
    1763             : /// them.
    1764          64 : void llvm::reportAndResetTimings() {
    1765          64 :   if (TheTimeInfo)
    1766           0 :     TheTimeInfo->print();
    1767          64 : }
    1768             : 
    1769             : //===----------------------------------------------------------------------===//
    1770             : // PMStack implementation
    1771             : //
    1772             : 
    1773             : // Pop Pass Manager from the stack and clear its analysis info.
    1774       81986 : void PMStack::pop() {
    1775             : 
    1776             :   PMDataManager *Top = this->top();
    1777             :   Top->initializeAnalysisInfo();
    1778             : 
    1779             :   S.pop_back();
    1780       81986 : }
    1781             : 
    1782             : // Push PM on the stack and set its top level manager.
    1783      164890 : void PMStack::push(PMDataManager *PM) {
    1784             :   assert(PM && "Unable to push. Pass Manager expected");
    1785             :   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
    1786             : 
    1787      164890 :   if (!this->empty()) {
    1788             :     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
    1789             :            && "pushing bad pass manager to PMStack");
    1790      106987 :     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
    1791             : 
    1792             :     assert(TPM && "Unable to find top level manager");
    1793      106987 :     TPM->addIndirectPassManager(PM);
    1794      106987 :     PM->setTopLevelManager(TPM);
    1795      106987 :     PM->setDepth(this->top()->getDepth()+1);
    1796             :   } else {
    1797             :     assert((PM->getPassManagerType() == PMT_ModulePassManager
    1798             :            || PM->getPassManagerType() == PMT_FunctionPassManager)
    1799             :            && "pushing bad pass manager to PMStack");
    1800       57903 :     PM->setDepth(1);
    1801             :   }
    1802             : 
    1803      164890 :   S.push_back(PM);
    1804      164890 : }
    1805             : 
    1806             : // Dump content of the pass manager stack.
    1807           0 : LLVM_DUMP_METHOD void PMStack::dump() const {
    1808           0 :   for (PMDataManager *Manager : S)
    1809           0 :     dbgs() << Manager->getAsPass()->getPassName() << ' ';
    1810             : 
    1811           0 :   if (!S.empty())
    1812           0 :     dbgs() << '\n';
    1813           0 : }
    1814             : 
    1815             : /// Find appropriate Module Pass Manager in the PM Stack and
    1816             : /// add self into that manager.
    1817      192910 : void ModulePass::assignPassManager(PMStack &PMS,
    1818             :                                    PassManagerType PreferredType) {
    1819             :   // Find Module Pass Manager
    1820      290848 :   while (!PMS.empty()) {
    1821      241879 :     PassManagerType TopPMType = PMS.top()->getPassManagerType();
    1822      241879 :     if (TopPMType == PreferredType)
    1823             :       break; // We found desired pass manager
    1824       48969 :     else if (TopPMType > PMT_ModulePassManager)
    1825       48969 :       PMS.pop();    // Pop children pass managers
    1826             :     else
    1827             :       break;
    1828             :   }
    1829             :   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
    1830      192910 :   PMS.top()->add(this);
    1831      192911 : }
    1832             : 
    1833             : /// Find appropriate Function Pass Manager or Call Graph Pass Manager
    1834             : /// in the PM Stack and add self into that manager.
    1835     2977500 : void FunctionPass::assignPassManager(PMStack &PMS,
    1836             :                                      PassManagerType PreferredType) {
    1837             : 
    1838             :   // Find Function Pass Manager
    1839     3040124 :   while (!PMS.empty()) {
    1840     3008813 :     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
    1841       31312 :       PMS.pop();
    1842             :     else
    1843             :       break;
    1844             :   }
    1845             : 
    1846             :   // Create new Function Pass Manager if needed.
    1847             :   FPPassManager *FPP;
    1848     2977501 :   if (PMS.top()->getPassManagerType() == PMT_FunctionPassManager) {
    1849     2915612 :     FPP = (FPPassManager *)PMS.top();
    1850             :   } else {
    1851             :     assert(!PMS.empty() && "Unable to create Function Pass Manager");
    1852             :     PMDataManager *PMD = PMS.top();
    1853             : 
    1854             :     // [1] Create new Function Pass Manager
    1855       61890 :     FPP = new FPPassManager();
    1856             :     FPP->populateInheritedAnalysis(PMS);
    1857             : 
    1858             :     // [2] Set up new manager's top level manager
    1859       61890 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1860             :     TPM->addIndirectPassManager(FPP);
    1861             : 
    1862             :     // [3] Assign manager to manage this new manager. This may create
    1863             :     // and push new managers into PMS
    1864       61890 :     FPP->assignPassManager(PMS, PMD->getPassManagerType());
    1865             : 
    1866             :     // [4] Push new manager into PMS
    1867       61890 :     PMS.push(FPP);
    1868             :   }
    1869             : 
    1870             :   // Assign FPP as the manager of this pass.
    1871     2977502 :   FPP->add(this);
    1872     2977499 : }
    1873             : 
    1874             : /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
    1875             : /// in the PM Stack and add self into that manager.
    1876         241 : void BasicBlockPass::assignPassManager(PMStack &PMS,
    1877             :                                        PassManagerType PreferredType) {
    1878             :   BBPassManager *BBP;
    1879             : 
    1880             :   // Basic Pass Manager is a leaf pass manager. It does not handle
    1881             :   // any other pass manager.
    1882         482 :   if (!PMS.empty() &&
    1883         241 :       PMS.top()->getPassManagerType() == PMT_BasicBlockPassManager) {
    1884             :     BBP = (BBPassManager *)PMS.top();
    1885             :   } else {
    1886             :     // If leaf manager is not Basic Block Pass manager then create new
    1887             :     // basic Block Pass manager.
    1888             :     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
    1889             :     PMDataManager *PMD = PMS.top();
    1890             : 
    1891             :     // [1] Create new Basic Block Manager
    1892         241 :     BBP = new BBPassManager();
    1893             : 
    1894             :     // [2] Set up new manager's top level manager
    1895             :     // Basic Block Pass Manager does not live by itself
    1896         241 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1897             :     TPM->addIndirectPassManager(BBP);
    1898             : 
    1899             :     // [3] Assign manager to manage this new manager. This may create
    1900             :     // and push new managers into PMS
    1901         241 :     BBP->assignPassManager(PMS, PreferredType);
    1902             : 
    1903             :     // [4] Push new manager into PMS
    1904         241 :     PMS.push(BBP);
    1905             :   }
    1906             : 
    1907             :   // Assign BBP as the manager of this pass.
    1908         241 :   BBP->add(this);
    1909         241 : }
    1910             : 
    1911      298472 : PassManagerBase::~PassManagerBase() {}

Generated by: LCOV version 1.13