LCOV - code coverage report
Current view: top level - lib/IR - LegacyPassManager.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 659 773 85.3 %
Date: 2018-06-17 00:07:59 Functions: 98 126 77.8 %
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/MapVector.h"
      16             : #include "llvm/ADT/Statistic.h"
      17             : #include "llvm/IR/DiagnosticInfo.h"
      18             : #include "llvm/IR/IRPrintingPasses.h"
      19             : #include "llvm/IR/LLVMContext.h"
      20             : #include "llvm/IR/LegacyPassManagers.h"
      21             : #include "llvm/IR/LegacyPassNameParser.h"
      22             : #include "llvm/IR/Module.h"
      23             : #include "llvm/Support/Chrono.h"
      24             : #include "llvm/Support/CommandLine.h"
      25             : #include "llvm/Support/Debug.h"
      26             : #include "llvm/Support/Error.h"
      27             : #include "llvm/Support/ErrorHandling.h"
      28             : #include "llvm/Support/ManagedStatic.h"
      29             : #include "llvm/Support/Mutex.h"
      30             : #include "llvm/Support/Timer.h"
      31             : #include "llvm/Support/raw_ostream.h"
      32             : #include <algorithm>
      33             : #include <unordered_set>
      34             : using namespace llvm;
      35             : using namespace llvm::legacy;
      36             : 
      37             : // See PassManagers.h for Pass Manager infrastructure overview.
      38             : 
      39             : //===----------------------------------------------------------------------===//
      40             : // Pass debugging information.  Often it is useful to find out what pass is
      41             : // running when a crash occurs in a utility.  When this library is compiled with
      42             : // debugging on, a command line option (--debug-pass) is enabled that causes the
      43             : // pass name to be printed before it executes.
      44             : //
      45             : 
      46             : namespace {
      47             : // Different debug levels that can be enabled...
      48             : enum PassDebugLevel {
      49             :   Disabled, Arguments, Structure, Executions, Details
      50             : };
      51             : }
      52             : 
      53             : static cl::opt<enum PassDebugLevel>
      54      101193 : PassDebugging("debug-pass", cl::Hidden,
      55      101193 :                   cl::desc("Print PassManager debugging information"),
      56      708351 :                   cl::values(
      57             :   clEnumVal(Disabled  , "disable debug output"),
      58             :   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
      59             :   clEnumVal(Structure , "print pass structure before run()"),
      60             :   clEnumVal(Executions, "print pass name before it is executed"),
      61      101193 :   clEnumVal(Details   , "print pass details when it is executed")));
      62             : 
      63             : namespace {
      64             : typedef llvm::cl::list<const llvm::PassInfo *, bool, PassNameParser>
      65             : PassOptionList;
      66             : }
      67             : 
      68             : // Print IR out before/after specified passes.
      69             : static PassOptionList
      70      101193 : PrintBefore("print-before",
      71      101193 :             llvm::cl::desc("Print IR before specified passes"),
      72      303579 :             cl::Hidden);
      73             : 
      74             : static PassOptionList
      75      101193 : PrintAfter("print-after",
      76      101193 :            llvm::cl::desc("Print IR after specified passes"),
      77      303579 :            cl::Hidden);
      78             : 
      79      101193 : static cl::opt<bool> PrintBeforeAll("print-before-all",
      80      101193 :                                     llvm::cl::desc("Print IR before each pass"),
      81      303579 :                                     cl::init(false), cl::Hidden);
      82      101193 : static cl::opt<bool> PrintAfterAll("print-after-all",
      83      101193 :                                    llvm::cl::desc("Print IR after each pass"),
      84      303579 :                                    cl::init(false), cl::Hidden);
      85             : 
      86             : static cl::opt<bool>
      87      101193 :     PrintModuleScope("print-module-scope",
      88      101193 :                      cl::desc("When printing IR for print-[before|after]{-all} "
      89             :                               "always print a module IR"),
      90      303579 :                      cl::init(false), cl::Hidden);
      91             : 
      92             : static cl::list<std::string>
      93      202386 :     PrintFuncsList("filter-print-funcs", cl::value_desc("function names"),
      94      101193 :                    cl::desc("Only print IR for functions whose name "
      95             :                             "match this for all print-[before|after][-all] "
      96             :                             "options"),
      97      303579 :                    cl::CommaSeparated, cl::Hidden);
      98             : 
      99             : /// This is a helper to determine whether to print IR before or
     100             : /// after a pass.
     101             : 
     102     4279619 : static bool ShouldPrintBeforeOrAfterPass(const PassInfo *PI,
     103             :                                          PassOptionList &PassesToPrint) {
     104     4281648 :   for (auto *PassInf : PassesToPrint) {
     105        2055 :     if (PassInf)
     106             :       if (PassInf->getPassArgument() == PI->getPassArgument()) {
     107             :         return true;
     108             :       }
     109             :   }
     110             :   return false;
     111             : }
     112             : 
     113             : /// This is a utility to check whether a pass should have IR dumped
     114             : /// before it.
     115             : static bool ShouldPrintBeforePass(const PassInfo *PI) {
     116     2140032 :   return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PI, PrintBefore);
     117             : }
     118             : 
     119             : /// This is a utility to check whether a pass should have IR dumped
     120             : /// after it.
     121             : static bool ShouldPrintAfterPass(const PassInfo *PI) {
     122     2140034 :   return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PI, PrintAfter);
     123             : }
     124             : 
     125         458 : bool llvm::forcePrintModuleIR() { return PrintModuleScope; }
     126             : 
     127       15732 : bool llvm::isFunctionInPrintList(StringRef FunctionName) {
     128             :   static std::unordered_set<std::string> PrintFuncNames(PrintFuncsList.begin(),
     129       29513 :                                                         PrintFuncsList.end());
     130       31642 :   return PrintFuncNames.empty() || PrintFuncNames.count(FunctionName);
     131             : }
     132             : /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
     133             : /// or higher is specified.
     134      652785 : bool PMDataManager::isPassDebuggingExecutionsOrMore() const {
     135      652785 :   return PassDebugging >= Executions;
     136             : }
     137             : 
     138    36301015 : unsigned PMDataManager::initSizeRemarkInfo(Module &M) {
     139             :   // Only calculate getInstructionCount if the size-info remark is requested.
     140    72602031 :   if (M.getContext().getDiagHandlerPtr()->isAnalysisRemarkEnabled("size-info"))
     141         147 :     return M.getInstructionCount();
     142             :   return 0;
     143             : }
     144             : 
     145    36300694 : void PMDataManager::emitInstrCountChangedRemark(Pass *P, Module &M,
     146             :                                                 unsigned CountBefore) {
     147             :   // Did the user request the remark? If not, quit.
     148    72601394 :   if (!M.getContext().getDiagHandlerPtr()->isAnalysisRemarkEnabled("size-info"))
     149    36300687 :     return;
     150             : 
     151             :   // We need a function containing at least one basic block in order to output
     152             :   // remarks. Since it's possible that the first function in the module doesn't
     153             :   // actually contain a basic block, we have to go and find one that's suitable
     154             :   // for emitting remarks.
     155             :   auto It = std::find_if(M.begin(), M.end(),
     156             :                          [](const Function &Fn) { return !Fn.empty(); });
     157             : 
     158             :   // Didn't find a function. Quit.
     159         147 :   if (It == M.end())
     160             :     return;
     161             : 
     162             :   // We found a function containing at least one basic block.
     163             :   Function *F = &*It;
     164             : 
     165             :   // How many instructions are in the module now?
     166         147 :   unsigned CountAfter = M.getInstructionCount();
     167             : 
     168             :   // If there was no change, don't emit a remark.
     169         147 :   if (CountBefore == CountAfter)
     170             :     return;
     171             : 
     172             :   // If it's a pass manager, don't emit a remark. (This hinges on the assumption
     173             :   // that the only passes that return non-null with getAsPMDataManager are pass
     174             :   // managers.) The reason we have to do this is to avoid emitting remarks for
     175             :   // CGSCC passes.
     176          17 :   if (P->getAsPMDataManager())
     177             :     return;
     178             : 
     179             :   // Compute a possibly negative delta between the instruction count before
     180             :   // running P, and after running P.
     181          11 :   int64_t Delta =
     182          11 :       static_cast<int64_t>(CountAfter) - static_cast<int64_t>(CountBefore);
     183             : 
     184             :   BasicBlock &BB = *F->begin();
     185             :   OptimizationRemarkAnalysis R("size-info", "IRSizeChange",
     186          22 :                                DiagnosticLocation(), &BB);
     187             :   // FIXME: Move ore namespace to DiagnosticInfo so that we can use it. This
     188             :   // would let us use NV instead of DiagnosticInfoOptimizationBase::Argument.
     189          33 :   R << DiagnosticInfoOptimizationBase::Argument("Pass", P->getPassName())
     190             :     << ": IR instruction count changed from "
     191          22 :     << DiagnosticInfoOptimizationBase::Argument("IRInstrsBefore", CountBefore)
     192             :     << " to "
     193          22 :     << DiagnosticInfoOptimizationBase::Argument("IRInstrsAfter", CountAfter)
     194             :     << "; Delta: "
     195          44 :     << DiagnosticInfoOptimizationBase::Argument("DeltaInstrCount", Delta);
     196          11 :   F->getContext().diagnose(R); // Not using ORE for layering reasons.
     197             : }
     198             : 
     199           0 : void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
     200           0 :   if (!V && !M)
     201           0 :     OS << "Releasing pass '";
     202             :   else
     203           0 :     OS << "Running pass '";
     204             : 
     205           0 :   OS << P->getPassName() << "'";
     206             : 
     207           0 :   if (M) {
     208           0 :     OS << " on module '" << M->getModuleIdentifier() << "'.\n";
     209           0 :     return;
     210             :   }
     211           0 :   if (!V) {
     212             :     OS << '\n';
     213             :     return;
     214             :   }
     215             : 
     216           0 :   OS << " on ";
     217           0 :   if (isa<Function>(V))
     218           0 :     OS << "function";
     219           0 :   else if (isa<BasicBlock>(V))
     220           0 :     OS << "basic block";
     221             :   else
     222           0 :     OS << "value";
     223             : 
     224           0 :   OS << " '";
     225           0 :   V->printAsOperand(OS, /*PrintTy=*/false, M);
     226           0 :   OS << "'\n";
     227             : }
     228             : 
     229             : 
     230             : namespace {
     231             : //===----------------------------------------------------------------------===//
     232             : // BBPassManager
     233             : //
     234             : /// BBPassManager manages BasicBlockPass. It batches all the
     235             : /// pass together and sequence them to process one basic block before
     236             : /// processing next basic block.
     237         480 : class BBPassManager : public PMDataManager, public FunctionPass {
     238             : 
     239             : public:
     240             :   static char ID;
     241             :   explicit BBPassManager()
     242         494 :     : PMDataManager(), FunctionPass(ID) {}
     243             : 
     244             :   /// Execute all of the passes scheduled for execution.  Keep track of
     245             :   /// whether any of the passes modifies the function, and if so, return true.
     246             :   bool runOnFunction(Function &F) override;
     247             : 
     248             :   /// Pass Manager itself does not invalidate any analysis info.
     249         247 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     250             :     Info.setPreservesAll();
     251         247 :   }
     252             : 
     253             :   bool doInitialization(Module &M) override;
     254             :   bool doInitialization(Function &F);
     255             :   bool doFinalization(Module &M) override;
     256             :   bool doFinalization(Function &F);
     257             : 
     258         247 :   PMDataManager *getAsPMDataManager() override { return this; }
     259           0 :   Pass *getAsPass() override { return this; }
     260             : 
     261           0 :   StringRef getPassName() const override { return "BasicBlock Pass Manager"; }
     262             : 
     263             :   // Print passes managed by this manager
     264           0 :   void dumpPassStructure(unsigned Offset) override {
     265           0 :     dbgs().indent(Offset*2) << "BasicBlockPass Manager\n";
     266           0 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     267             :       BasicBlockPass *BP = getContainedPass(Index);
     268           0 :       BP->dumpPassStructure(Offset + 1);
     269           0 :       dumpLastUses(BP, Offset+1);
     270             :     }
     271           0 :   }
     272             : 
     273             :   BasicBlockPass *getContainedPass(unsigned N) {
     274             :     assert(N < PassVector.size() && "Pass number out of range!");
     275        8328 :     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
     276             :     return BP;
     277             :   }
     278             : 
     279         246 :   PassManagerType getPassManagerType() const override {
     280         246 :     return PMT_BasicBlockPassManager;
     281             :   }
     282             : };
     283             : 
     284             : char BBPassManager::ID = 0;
     285             : } // End anonymous namespace
     286             : 
     287             : namespace llvm {
     288             : namespace legacy {
     289             : //===----------------------------------------------------------------------===//
     290             : // FunctionPassManagerImpl
     291             : //
     292             : /// FunctionPassManagerImpl manages FPPassManagers
     293       31606 : class FunctionPassManagerImpl : public Pass,
     294             :                                 public PMDataManager,
     295             :                                 public PMTopLevelManager {
     296             :   virtual void anchor();
     297             : private:
     298             :   bool wasRun;
     299             : public:
     300             :   static char ID;
     301       15815 :   explicit FunctionPassManagerImpl() :
     302             :     Pass(PT_PassManager, ID), PMDataManager(),
     303       31630 :     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
     304             : 
     305             :   /// \copydoc FunctionPassManager::add()
     306             :   void add(Pass *P) {
     307       53926 :     schedulePass(P);
     308             :   }
     309             : 
     310             :   /// createPrinterPass - Get a function printer pass.
     311           0 :   Pass *createPrinterPass(raw_ostream &O,
     312             :                           const std::string &Banner) const override {
     313           0 :     return createPrintFunctionPass(O, Banner);
     314             :   }
     315             : 
     316             :   // Prepare for running an on the fly pass, freeing memory if needed
     317             :   // from a previous run.
     318             :   void releaseMemoryOnTheFly();
     319             : 
     320             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     321             :   /// whether any of the passes modifies the module, and if so, return true.
     322             :   bool run(Function &F);
     323             : 
     324             :   /// doInitialization - Run all of the initializers for the function passes.
     325             :   ///
     326             :   bool doInitialization(Module &M) override;
     327             : 
     328             :   /// doFinalization - Run all of the finalizers for the function passes.
     329             :   ///
     330             :   bool doFinalization(Module &M) override;
     331             : 
     332             : 
     333       28029 :   PMDataManager *getAsPMDataManager() override { return this; }
     334           0 :   Pass *getAsPass() override { return this; }
     335       39684 :   PassManagerType getTopLevelPassManagerType() override {
     336       39684 :     return PMT_FunctionPassManager;
     337             :   }
     338             : 
     339             :   /// Pass Manager itself does not invalidate any analysis info.
     340           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     341             :     Info.setPreservesAll();
     342           0 :   }
     343             : 
     344             :   FPPassManager *getContainedManager(unsigned N) {
     345             :     assert(N < PassManagers.size() && "Pass number out of range!");
     346      809368 :     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
     347             :     return FP;
     348             :   }
     349             : };
     350             : 
     351           0 : void FunctionPassManagerImpl::anchor() {}
     352             : 
     353             : char FunctionPassManagerImpl::ID = 0;
     354             : } // End of legacy namespace
     355             : } // End of llvm namespace
     356             : 
     357             : namespace {
     358             : //===----------------------------------------------------------------------===//
     359             : // MPPassManager
     360             : //
     361             : /// MPPassManager manages ModulePasses and function pass managers.
     362             : /// It batches all Module passes and function pass managers together and
     363             : /// sequences them to process one module.
     364             : class MPPassManager : public Pass, public PMDataManager {
     365             : public:
     366             :   static char ID;
     367       52854 :   explicit MPPassManager() :
     368      105708 :     Pass(PT_PassManager, ID), PMDataManager() { }
     369             : 
     370             :   // Delete on the fly managers.
     371      157923 :   ~MPPassManager() override {
     372       57380 :     for (auto &OnTheFlyManager : OnTheFlyManagers) {
     373        4739 :       FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
     374        4739 :       delete FPP;
     375             :     }
     376      105282 :   }
     377             : 
     378             :   /// createPrinterPass - Get a module printer pass.
     379           0 :   Pass *createPrinterPass(raw_ostream &O,
     380             :                           const std::string &Banner) const override {
     381           0 :     return createPrintModulePass(O, Banner);
     382             :   }
     383             : 
     384             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     385             :   /// whether any of the passes modifies the module, and if so, return true.
     386             :   bool runOnModule(Module &M);
     387             : 
     388             :   using llvm::Pass::doInitialization;
     389             :   using llvm::Pass::doFinalization;
     390             : 
     391             :   /// Pass Manager itself does not invalidate any analysis info.
     392           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     393             :     Info.setPreservesAll();
     394           0 :   }
     395             : 
     396             :   /// Add RequiredPass into list of lower level passes required by pass P.
     397             :   /// RequiredPass is run on the fly by Pass Manager when P requests it
     398             :   /// through getAnalysis interface.
     399             :   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
     400             : 
     401             :   /// Return function pass corresponding to PassInfo PI, that is
     402             :   /// required by module pass MP. Instantiate analysis pass, by using
     403             :   /// its runOnFunction() for function F.
     404             :   Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F) override;
     405             : 
     406           0 :   StringRef getPassName() const override { return "Module Pass Manager"; }
     407             : 
     408           0 :   PMDataManager *getAsPMDataManager() override { return this; }
     409     3739564 :   Pass *getAsPass() override { return this; }
     410             : 
     411             :   // Print passes managed by this manager
     412          34 :   void dumpPassStructure(unsigned Offset) override {
     413          34 :     dbgs().indent(Offset*2) << "ModulePass Manager\n";
     414         602 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     415             :       ModulePass *MP = getContainedPass(Index);
     416         284 :       MP->dumpPassStructure(Offset + 1);
     417             :       MapVector<Pass *, FunctionPassManagerImpl *>::const_iterator I =
     418         568 :           OnTheFlyManagers.find(MP);
     419         284 :       if (I != OnTheFlyManagers.end())
     420          23 :         I->second->dumpPassStructure(Offset + 2);
     421         284 :       dumpLastUses(MP, Offset+1);
     422             :     }
     423          34 :   }
     424             : 
     425             :   ModulePass *getContainedPass(unsigned N) {
     426             :     assert(N < PassVector.size() && "Pass number out of range!");
     427     1317552 :     return static_cast<ModulePass *>(PassVector[N]);
     428             :   }
     429             : 
     430      464382 :   PassManagerType getPassManagerType() const override {
     431      464382 :     return PMT_ModulePassManager;
     432             :   }
     433             : 
     434             :  private:
     435             :   /// Collection of on the fly FPPassManagers. These managers manage
     436             :   /// function passes that are required by module passes.
     437             :    MapVector<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
     438             : };
     439             : 
     440             : char MPPassManager::ID = 0;
     441             : } // End anonymous namespace
     442             : 
     443             : namespace llvm {
     444             : namespace legacy {
     445             : //===----------------------------------------------------------------------===//
     446             : // PassManagerImpl
     447             : //
     448             : 
     449             : /// PassManagerImpl manages MPPassManagers
     450      105282 : class PassManagerImpl : public Pass,
     451             :                         public PMDataManager,
     452             :                         public PMTopLevelManager {
     453             :   virtual void anchor();
     454             : 
     455             : public:
     456             :   static char ID;
     457       52854 :   explicit PassManagerImpl() :
     458             :     Pass(PT_PassManager, ID), PMDataManager(),
     459       52854 :                               PMTopLevelManager(new MPPassManager()) {}
     460             : 
     461             :   /// \copydoc PassManager::add()
     462             :   void add(Pass *P) {
     463     2352298 :     schedulePass(P);
     464             :   }
     465             : 
     466             :   /// createPrinterPass - Get a module printer pass.
     467           0 :   Pass *createPrinterPass(raw_ostream &O,
     468             :                           const std::string &Banner) const override {
     469           0 :     return createPrintModulePass(O, Banner);
     470             :   }
     471             : 
     472             :   /// run - Execute all of the passes scheduled for execution.  Keep track of
     473             :   /// whether any of the passes modifies the module, and if so, return true.
     474             :   bool run(Module &M);
     475             : 
     476             :   using llvm::Pass::doInitialization;
     477             :   using llvm::Pass::doFinalization;
     478             : 
     479             :   /// Pass Manager itself does not invalidate any analysis info.
     480           0 :   void getAnalysisUsage(AnalysisUsage &Info) const override {
     481             :     Info.setPreservesAll();
     482           0 :   }
     483             : 
     484      320794 :   PMDataManager *getAsPMDataManager() override { return this; }
     485           0 :   Pass *getAsPass() override { return this; }
     486     3562615 :   PassManagerType getTopLevelPassManagerType() override {
     487     3562615 :     return PMT_ModulePassManager;
     488             :   }
     489             : 
     490             :   MPPassManager *getContainedManager(unsigned N) {
     491             :     assert(N < PassManagers.size() && "Pass number out of range!");
     492      105342 :     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
     493             :     return MP;
     494             :   }
     495             : };
     496             : 
     497           0 : void PassManagerImpl::anchor() {}
     498             : 
     499             : char PassManagerImpl::ID = 0;
     500             : } // End of legacy namespace
     501             : } // End of llvm namespace
     502             : 
     503             : namespace {
     504             : 
     505             : //===----------------------------------------------------------------------===//
     506             : /// TimingInfo Class - This class is used to calculate information about the
     507             : /// amount of time each pass takes to execute.  This only happens when
     508             : /// -time-passes is enabled on the command line.
     509             : ///
     510             : 
     511             : static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex;
     512             : 
     513             : class TimingInfo {
     514             :   DenseMap<Pass*, Timer*> TimingData;
     515             :   TimerGroup TG;
     516             : public:
     517             :   // Use 'create' member to get this.
     518           0 :   TimingInfo() : TG("pass", "... Pass execution timing report ...") {}
     519             : 
     520             :   // TimingDtor - Print out information about timing information
     521           0 :   ~TimingInfo() {
     522             :     // Delete all of the timers, which accumulate their info into the
     523             :     // TimerGroup.
     524           0 :     for (auto &I : TimingData)
     525           0 :       delete I.second;
     526             :     // TimerGroup is deleted next, printing the report.
     527           0 :   }
     528             : 
     529             :   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
     530             :   // to a non-null value (if the -time-passes option is enabled) or it leaves it
     531             :   // null.  It may be called multiple times.
     532             :   static void createTheTimeInfo();
     533             : 
     534             :   // print - Prints out timing information and then resets the timers.
     535           0 :   void print() {
     536           0 :     TG.print(*CreateInfoOutputFile());
     537           0 :   }
     538             : 
     539             :   /// getPassTimer - Return the timer for the specified pass if it exists.
     540           0 :   Timer *getPassTimer(Pass *P) {
     541           0 :     if (P->getAsPMDataManager())
     542             :       return nullptr;
     543             : 
     544           0 :     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
     545           0 :     Timer *&T = TimingData[P];
     546           0 :     if (!T) {
     547           0 :       StringRef PassName = P->getPassName();
     548           0 :       StringRef PassArgument;
     549           0 :       if (const PassInfo *PI = Pass::lookupPassInfo(P->getPassID()))
     550           0 :         PassArgument = PI->getPassArgument();
     551           0 :       T = new Timer(PassArgument.empty() ? PassName : PassArgument, PassName,
     552           0 :                     TG);
     553             :     }
     554           0 :     return T;
     555             :   }
     556             : };
     557             : 
     558             : } // End of anon namespace
     559             : 
     560             : static TimingInfo *TheTimeInfo;
     561             : 
     562             : //===----------------------------------------------------------------------===//
     563             : // PMTopLevelManager implementation
     564             : 
     565             : /// Initialize top level manager. Create first pass manager.
     566      274676 : PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
     567             :   PMDM->setTopLevelManager(this);
     568             :   addPassManager(PMDM);
     569       68669 :   activeStack.push(PMDM);
     570       68669 : }
     571             : 
     572             : /// Set pass P as the last user of the given analysis passes.
     573             : void
     574    24788915 : PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
     575             :   unsigned PDepth = 0;
     576    24788915 :   if (P->getResolver())
     577    20996020 :     PDepth = P->getResolver()->getPMDataManager().getDepth();
     578             : 
     579    50173875 :   for (Pass *AP : AnalysisPasses) {
     580    25384923 :     LastUser[AP] = P;
     581             : 
     582    12692437 :     if (P == AP)
     583     3551773 :       continue;
     584             : 
     585             :     // Update the last users of passes that are required transitive by AP.
     586     9140664 :     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
     587             :     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
     588             :     SmallVector<Pass *, 12> LastUses;
     589             :     SmallVector<Pass *, 12> LastPMUses;
     590    11603754 :     for (AnalysisID ID : IDs) {
     591     1231544 :       Pass *AnalysisPass = findAnalysisPass(ID);
     592             :       assert(AnalysisPass && "Expected analysis pass to exist.");
     593     1231546 :       AnalysisResolver *AR = AnalysisPass->getResolver();
     594             :       assert(AR && "Expected analysis resolver to exist.");
     595     1231546 :       unsigned APDepth = AR->getPMDataManager().getDepth();
     596             : 
     597     1231546 :       if (PDepth == APDepth)
     598      964822 :         LastUses.push_back(AnalysisPass);
     599      266724 :       else if (PDepth > APDepth)
     600      266724 :         LastPMUses.push_back(AnalysisPass);
     601             :     }
     602             : 
     603     9140664 :     setLastUser(LastUses, P);
     604             : 
     605             :     // If this pass has a corresponding pass manager, push higher level
     606             :     // analysis to this pass manager.
     607     9140674 :     if (P->getResolver())
     608    18228095 :       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
     609             : 
     610             : 
     611             :     // If AP is the last user of other passes then make P last user of
     612             :     // such passes.
     613   800439856 :     for (auto LU : LastUser) {
     614   782158472 :       if (LU.second == AP)
     615             :         // DenseMap iterator is not invalidated here because
     616             :         // this is just updating existing entries.
     617      716391 :         LastUser[LU.first] = P;
     618             :     }
     619             :   }
     620    24788909 : }
     621             : 
     622             : /// Collect passes whose last user is P
     623    36446400 : void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
     624             :                                         Pass *P) {
     625             :   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
     626    36446400 :     InversedLastUser.find(P);
     627    36446407 :   if (DMI == InversedLastUser.end())
     628    15271098 :     return;
     629             : 
     630             :   SmallPtrSet<Pass *, 8> &LU = DMI->second;
     631    57611984 :   for (Pass *LUP : LU) {
     632    36436675 :     LastUses.push_back(LUP);
     633             :   }
     634             : 
     635             : }
     636             : 
     637    93683370 : AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
     638             :   AnalysisUsage *AnUsage = nullptr;
     639    93683370 :   auto DMI = AnUsageMap.find(P);
     640    93683570 :   if (DMI != AnUsageMap.end())
     641    89660140 :     AnUsage = DMI->second;
     642             :   else {
     643             :     // Look up the analysis usage from the pass instance (different instances
     644             :     // of the same pass can produce different results), but unique the
     645             :     // resulting object to reduce memory usage.  This helps to greatly reduce
     646             :     // memory usage when we have many instances of only a few pass types
     647             :     // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
     648             :     // of dependencies.
     649     4023428 :     AnalysisUsage AU;
     650     4023430 :     P->getAnalysisUsage(AU);
     651             :     
     652             :     AUFoldingSetNode* Node = nullptr;
     653             :     FoldingSetNodeID ID;
     654     4023428 :     AUFoldingSetNode::Profile(ID, AU);
     655     4023435 :     void *IP = nullptr;
     656     4023433 :     if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
     657             :       Node = N;
     658             :     else {
     659             :       Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
     660     1790562 :       UniqueAnalysisUsages.InsertNode(Node, IP);
     661             :     }
     662             :     assert(Node && "cached analysis usage must be non null");
     663             : 
     664     4023428 :     AnUsageMap[P] = &Node->AU;
     665             :     AnUsage = &Node->AU;
     666             :   }
     667    93683567 :   return AnUsage;
     668             : }
     669             : 
     670             : /// Schedule pass P for execution. Make sure that passes required by
     671             : /// P are run before P is run. Update analysis info maintained by
     672             : /// the manager. Remove dead passes. This is a recursive function.
     673     3959733 : void PMTopLevelManager::schedulePass(Pass *P) {
     674             : 
     675             :   // TODO : Allocate function manager for this pass, other wise required set
     676             :   // may be inserted into previous function manager
     677             : 
     678             :   // Give pass a chance to prepare the stage.
     679     3959733 :   P->preparePassManager(activeStack);
     680             : 
     681             :   // If P is an analysis pass and it is available then do not
     682             :   // generate the analysis again. Stale analysis info should not be
     683             :   // available at this point.
     684     3959735 :   const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
     685     3959729 :   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
     686        9077 :     delete P;
     687             :     return;
     688             :   }
     689             : 
     690     3950653 :   AnalysisUsage *AnUsage = findAnalysisUsage(P);
     691             : 
     692             :   bool checkAnalysis = true;
     693     8052022 :   while (checkAnalysis) {
     694             :     checkAnalysis = false;
     695             : 
     696             :     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
     697    19961341 :     for (const AnalysisID ID : RequiredSet) {
     698             : 
     699     7929977 :       Pass *AnalysisPass = findAnalysisPass(ID);
     700     7929987 :       if (!AnalysisPass) {
     701     1511069 :         const PassInfo *PI = findAnalysisPassInfo(ID);
     702             : 
     703     1511067 :         if (!PI) {
     704             :           // Pass P is not in the global PassRegistry
     705           0 :           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
     706           0 :           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
     707           0 :           dbgs() << "Required Passes:" << "\n";
     708           0 :           for (const AnalysisID ID2 : RequiredSet) {
     709           0 :             if (ID == ID2)
     710             :               break;
     711           0 :             Pass *AnalysisPass2 = findAnalysisPass(ID2);
     712           0 :             if (AnalysisPass2) {
     713           0 :               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
     714             :             } else {
     715           0 :               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
     716           0 :               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
     717           0 :               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
     718             :             }
     719             :           }
     720             :         }
     721             : 
     722             :         assert(PI && "Expected required passes to be initialized");
     723     1511067 :         AnalysisPass = PI->createPass();
     724     3022128 :         if (P->getPotentialPassManagerType () ==
     725     1511064 :             AnalysisPass->getPotentialPassManagerType())
     726             :           // Schedule analysis pass that is managed by the same pass manager.
     727     1249575 :           schedulePass(AnalysisPass);
     728      522978 :         else if (P->getPotentialPassManagerType () >
     729      261489 :                  AnalysisPass->getPotentialPassManagerType()) {
     730             :           // Schedule analysis pass that is managed by a new manager.
     731      253464 :           schedulePass(AnalysisPass);
     732             :           // Recheck analysis passes to ensure that required analyses that
     733             :           // are already checked are still available.
     734             :           checkAnalysis = true;
     735             :         } else
     736             :           // Do not schedule this analysis. Lower level analysis
     737             :           // passes are run on the fly.
     738        8025 :           delete AnalysisPass;
     739             :       }
     740             :     }
     741             :   }
     742             : 
     743             :   // Now all required passes are available.
     744     3950653 :   if (ImmutablePass *IP = P->getAsImmutablePass()) {
     745             :     // P is a immutable pass and it will be managed by this
     746             :     // top level manager. Set up analysis resolver to connect them.
     747      348823 :     PMDataManager *DM = getAsPMDataManager();
     748      348823 :     AnalysisResolver *AR = new AnalysisResolver(*DM);
     749      348823 :     P->setResolver(AR);
     750      348823 :     DM->initializeAnalysisImpl(P);
     751      348823 :     addImmutablePass(IP);
     752      348823 :     DM->recordAvailableAnalysis(IP);
     753      348823 :     return;
     754             :   }
     755             : 
     756     3601830 :   if (PI && !PI->isAnalysis() && ShouldPrintBeforePass(PI)) {
     757           6 :     Pass *PP = P->createPrinterPass(
     758          30 :         dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str());
     759           6 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     760             :   }
     761             : 
     762             :   // Add the requested pass to the best available pass manager.
     763     3601830 :   P->assignPassManager(activeStack, getTopLevelPassManagerType());
     764             : 
     765     3601834 :   if (PI && !PI->isAnalysis() && ShouldPrintAfterPass(PI)) {
     766         463 :     Pass *PP = P->createPrinterPass(
     767        2315 :         dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str());
     768         463 :     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
     769             :   }
     770             : }
     771             : 
     772             : /// Find the pass that implements Analysis AID. Search immutable
     773             : /// passes and all pass managers. If desired pass is not found
     774             : /// then return NULL.
     775    74008606 : Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
     776             :   // For immutable passes we have a direct mapping from ID to pass, so check
     777             :   // that first.
     778   125625901 :   if (Pass *P = ImmutablePassMap.lookup(AID))
     779             :     return P;
     780             : 
     781             :   // Check pass managers
     782    65315552 :   for (PMDataManager *PassManager : PassManagers)
     783    22391539 :     if (Pass *P = PassManager->findAnalysisPass(AID, false))
     784             :       return P;
     785             : 
     786             :   // Check other pass managers
     787   524754581 :   for (PMDataManager *IndirectPassManager : IndirectPassManagers)
     788   255911869 :     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
     789             :       return P;
     790             : 
     791             :   return nullptr;
     792             : }
     793             : 
     794    82747994 : const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
     795    82747994 :   const PassInfo *&PI = AnalysisPassInfos[AID];
     796    82747990 :   if (!PI)
     797     7810329 :     PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
     798             :   else
     799             :     assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
     800             :            "The pass info pointer changed for an analysis ID!");
     801             : 
     802    82747993 :   return PI;
     803             : }
     804             : 
     805      348823 : void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
     806      348823 :   P->initializePass();
     807      348823 :   ImmutablePasses.push_back(P);
     808             : 
     809             :   // Add this pass to the map from its analysis ID. We clobber any prior runs
     810             :   // of the pass in the map so that the last one added is the one found when
     811             :   // doing lookups.
     812      348823 :   AnalysisID AID = P->getPassID();
     813      697646 :   ImmutablePassMap[AID] = P;
     814             : 
     815             :   // Also add any interfaces implemented by the immutable pass to the map for
     816             :   // fast lookup.
     817      348823 :   const PassInfo *PassInf = findAnalysisPassInfo(AID);
     818             :   assert(PassInf && "Expected all immutable passes to be initialized");
     819      348823 :   for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented())
     820           0 :     ImmutablePassMap[ImmPI->getTypeInfo()] = P;
     821      348823 : }
     822             : 
     823             : // Print passes managed by this top level manager.
     824       68453 : void PMTopLevelManager::dumpPasses() const {
     825             : 
     826       68453 :   if (PassDebugging < Structure)
     827             :     return;
     828             : 
     829             :   // Print out the immutable passes
     830         349 :   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
     831         568 :     ImmutablePasses[i]->dumpPassStructure(0);
     832             :   }
     833             : 
     834             :   // Every class that derives from PMDataManager also derives from Pass
     835             :   // (sometimes indirectly), but there's no inheritance relationship
     836             :   // between PMDataManager and Pass, so we have to getAsPass to get
     837             :   // from a PMDataManager* to a Pass*.
     838         195 :   for (PMDataManager *Manager : PassManagers)
     839          65 :     Manager->getAsPass()->dumpPassStructure(1);
     840             : }
     841             : 
     842       68453 : void PMTopLevelManager::dumpArguments() const {
     843             : 
     844       68453 :   if (PassDebugging < Arguments)
     845             :     return;
     846             : 
     847         142 :   dbgs() << "Pass Arguments: ";
     848        1296 :   for (ImmutablePass *P : ImmutablePasses)
     849         577 :     if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) {
     850             :       assert(PI && "Expected all immutable passes to be initialized");
     851         577 :       if (!PI->isAnalysisGroup())
     852         577 :         dbgs() << " -" << PI->getPassArgument();
     853             :     }
     854         426 :   for (PMDataManager *PM : PassManagers)
     855         142 :     PM->dumpPassArguments();
     856         142 :   dbgs() << "\n";
     857             : }
     858             : 
     859      236631 : void PMTopLevelManager::initializeAllAnalysisInfo() {
     860      709893 :   for (PMDataManager *PM : PassManagers)
     861             :     PM->initializeAnalysisInfo();
     862             : 
     863             :   // Initailize other pass managers
     864      727211 :   for (PMDataManager *IPM : IndirectPassManagers)
     865             :     IPM->initializeAnalysisInfo();
     866             : 
     867     4863895 :   for (auto LU : LastUser) {
     868     4390633 :     SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
     869     4390633 :     L.insert(LU.first);
     870             :   }
     871      236631 : }
     872             : 
     873             : /// Destructor
     874      273776 : PMTopLevelManager::~PMTopLevelManager() {
     875      205332 :   for (PMDataManager *PM : PassManagers)
     876       68444 :     delete PM;
     877             : 
     878      763238 :   for (ImmutablePass *P : ImmutablePasses)
     879      347397 :     delete P;
     880       68444 : }
     881             : 
     882             : //===----------------------------------------------------------------------===//
     883             : // PMDataManager implementation
     884             : 
     885             : /// Augement AvailableAnalysis by adding analysis made available by pass P.
     886    40465636 : void PMDataManager::recordAvailableAnalysis(Pass *P) {
     887    40465636 :   AnalysisID PI = P->getPassID();
     888             : 
     889    80931284 :   AvailableAnalysis[PI] = P;
     890             : 
     891             :   assert(!AvailableAnalysis.empty());
     892             : 
     893             :   // This pass is the current implementation of all of the interfaces it
     894             :   // implements as well.
     895    40465648 :   const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
     896    43339233 :   if (!PInf) return;
     897             :   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
     898    75184178 :   for (unsigned i = 0, e = II.size(); i != e; ++i)
     899           0 :     AvailableAnalysis[II[i]->getTypeInfo()] = P;
     900             : }
     901             : 
     902             : // Return true if P preserves high level analysis used by other
     903             : // passes managed by this manager
     904        9814 : bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
     905        9814 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     906        9814 :   if (AnUsage->getPreservesAll())
     907             :     return true;
     908             : 
     909             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     910      186204 :   for (Pass *P1 : HigherLevelAnalysis) {
     911      168452 :     if (P1->getAsImmutablePass() == nullptr &&
     912       78742 :         !is_contained(PreservedSet, P1->getPassID()))
     913             :       return false;
     914             :   }
     915             : 
     916             :   return true;
     917             : }
     918             : 
     919             : /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
     920    36441810 : void PMDataManager::verifyPreservedAnalysis(Pass *P) {
     921             :   // Don't do this unless assertions are enabled.
     922             : #ifdef NDEBUG
     923             :   return;
     924             : #endif
     925             :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     926             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     927             : 
     928             :   // Verify preserved analysis
     929             :   for (AnalysisID AID : PreservedSet) {
     930             :     if (Pass *AP = findAnalysisPass(AID, true)) {
     931             :       TimeRegion PassTimer(getPassTimer(AP));
     932             :       AP->verifyAnalysis();
     933             :     }
     934             :   }
     935             : }
     936             : 
     937             : /// Remove Analysis not preserved by Pass P
     938    40116805 : void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
     939    40116805 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
     940    40116806 :   if (AnUsage->getPreservesAll())
     941             :     return;
     942             : 
     943             :   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
     944    74233702 :   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
     945    74233660 :          E = AvailableAnalysis.end(); I != E; ) {
     946             :     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
     947   108387896 :     if (Info->second->getAsImmutablePass() == nullptr &&
     948    54193965 :         !is_contained(PreservedSet, Info->first)) {
     949             :       // Remove this analysis
     950    11435268 :       if (PassDebugging >= Details) {
     951           2 :         Pass *S = Info->second;
     952           2 :         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     953           2 :         dbgs() << S->getPassName() << "'\n";
     954             :       }
     955             :       AvailableAnalysis.erase(Info);
     956             :     }
     957             :   }
     958             : 
     959             :   // Check inherited analysis also. If P is not preserving analysis
     960             :   // provided by parent manager then remove it here.
     961   300595907 :   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
     962             : 
     963   140278091 :     if (!InheritedAnalysis[Index])
     964   101858312 :       continue;
     965             : 
     966    31725678 :     for (DenseMap<AnalysisID, Pass*>::iterator
     967    38419779 :            I = InheritedAnalysis[Index]->begin(),
     968   108565232 :            E = InheritedAnalysis[Index]->end(); I != E; ) {
     969             :       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
     970    63451356 :       if (Info->second->getAsImmutablePass() == nullptr &&
     971    31725678 :           !is_contained(PreservedSet, Info->first)) {
     972             :         // Remove this analysis
     973      279776 :         if (PassDebugging >= Details) {
     974           1 :           Pass *S = Info->second;
     975           1 :           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
     976           1 :           dbgs() << S->getPassName() << "'\n";
     977             :         }
     978      279776 :         InheritedAnalysis[Index]->erase(Info);
     979             :       }
     980             :     }
     981             :   }
     982             : }
     983             : 
     984             : /// Remove analysis passes that are not used any longer
     985    36442246 : void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
     986             :                                      enum PassDebuggingString DBG_STR) {
     987             : 
     988             :   SmallVector<Pass *, 12> DeadPasses;
     989             : 
     990             :   // If this is a on the fly manager then it does not have TPM.
     991    36442246 :   if (!TPM)
     992             :     return;
     993             : 
     994    36442246 :   TPM->collectLastUses(DeadPasses, P);
     995             : 
     996    36442239 :   if (PassDebugging >= Details && !DeadPasses.empty()) {
     997           3 :     dbgs() << " -*- '" <<  P->getPassName();
     998           3 :     dbgs() << "' is the last user of following pass instances.";
     999           3 :     dbgs() << " Free these instances\n";
    1000             :   }
    1001             : 
    1002   109315553 :   for (Pass *P : DeadPasses)
    1003    36436650 :     freePass(P, Msg, DBG_STR);
    1004             : }
    1005             : 
    1006    36437806 : void PMDataManager::freePass(Pass *P, StringRef Msg,
    1007             :                              enum PassDebuggingString DBG_STR) {
    1008    36437806 :   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
    1009             : 
    1010             :   {
    1011             :     // If the pass crashes releasing memory, remember this.
    1012             :     PassManagerPrettyStackEntry X(P);
    1013    36437814 :     TimeRegion PassTimer(getPassTimer(P));
    1014             : 
    1015    36437814 :     P->releaseMemory();
    1016             :   }
    1017             : 
    1018    36437823 :   AnalysisID PI = P->getPassID();
    1019    36437823 :   if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
    1020             :     // Remove the pass itself (if it is not already removed).
    1021    34411623 :     AvailableAnalysis.erase(PI);
    1022             : 
    1023             :     // Remove all interfaces this pass implements, for which it is also
    1024             :     // listed as the available implementation.
    1025             :     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
    1026    68823246 :     for (unsigned i = 0, e = II.size(); i != e; ++i) {
    1027             :       DenseMap<AnalysisID, Pass*>::iterator Pos =
    1028           0 :         AvailableAnalysis.find(II[i]->getTypeInfo());
    1029           0 :       if (Pos != AvailableAnalysis.end() && Pos->second == P)
    1030             :         AvailableAnalysis.erase(Pos);
    1031             :     }
    1032             :   }
    1033    36437820 : }
    1034             : 
    1035             : /// Add pass P into the PassVector. Update
    1036             : /// AvailableAnalysis appropriately if ProcessAnalysis is true.
    1037     3674605 : void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
    1038             :   // This manager is going to manage pass P. Set up analysis resolver
    1039             :   // to connect them.
    1040     3674605 :   AnalysisResolver *AR = new AnalysisResolver(*this);
    1041     3674609 :   P->setResolver(AR);
    1042             : 
    1043             :   // If a FunctionPass F is the last user of ModulePass info M
    1044             :   // then the F's manager, not F, records itself as a last user of M.
    1045             :   SmallVector<Pass *, 12> TransferLastUses;
    1046             : 
    1047     3674607 :   if (!ProcessAnalysis) {
    1048             :     // Add pass
    1049           0 :     PassVector.push_back(P);
    1050             :     return;
    1051             :   }
    1052             : 
    1053             :   // At the moment, this pass is the last user of all required passes.
    1054             :   SmallVector<Pass *, 12> LastUses;
    1055             :   SmallVector<Pass *, 8> UsedPasses;
    1056             :   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
    1057             : 
    1058     3674607 :   unsigned PDepth = this->getDepth();
    1059             : 
    1060     3674607 :   collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
    1061    19476857 :   for (Pass *PUsed : UsedPasses) {
    1062             :     unsigned RDepth = 0;
    1063             : 
    1064             :     assert(PUsed->getResolver() && "Analysis Resolver is not set");
    1065     7901126 :     PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
    1066     7901126 :     RDepth = DM.getDepth();
    1067             : 
    1068     7901126 :     if (PDepth == RDepth)
    1069     3569458 :       LastUses.push_back(PUsed);
    1070     4331668 :     else if (PDepth > RDepth) {
    1071             :       // Let the parent claim responsibility of last use
    1072     4331668 :       TransferLastUses.push_back(PUsed);
    1073             :       // Keep track of higher level analysis used by this manager.
    1074     4331670 :       HigherLevelAnalysis.push_back(PUsed);
    1075             :     } else
    1076           0 :       llvm_unreachable("Unable to accommodate Used Pass");
    1077             :   }
    1078             : 
    1079             :   // Set P as P's last user until someone starts using P.
    1080             :   // However, if P is a Pass Manager then it does not need
    1081             :   // to record its last user.
    1082     3674607 :   if (!P->getAsPMDataManager())
    1083     3551833 :     LastUses.push_back(P);
    1084     7349218 :   TPM->setLastUser(LastUses, P);
    1085             : 
    1086     3674604 :   if (!TransferLastUses.empty()) {
    1087     2851746 :     Pass *My_PM = getAsPass();
    1088     5703492 :     TPM->setLastUser(TransferLastUses, My_PM);
    1089             :     TransferLastUses.clear();
    1090             :   }
    1091             : 
    1092             :   // Now, take care of required analyses that are not available.
    1093     3690670 :   for (AnalysisID ID : ReqAnalysisNotAvailable) {
    1094        8032 :     const PassInfo *PI = TPM->findAnalysisPassInfo(ID);
    1095        8032 :     Pass *AnalysisPass = PI->createPass();
    1096        8032 :     this->addLowerLevelRequiredPass(P, AnalysisPass);
    1097             :   }
    1098             : 
    1099             :   // Take a note of analysis required and made available by this pass.
    1100             :   // Remove the analysis not preserved by this pass
    1101     3674606 :   removeNotPreservedAnalysis(P);
    1102     3674607 :   recordAvailableAnalysis(P);
    1103             : 
    1104             :   // Add pass
    1105     3674607 :   PassVector.push_back(P);
    1106             : }
    1107             : 
    1108             : 
    1109             : /// Populate UP with analysis pass that are used or required by
    1110             : /// pass P and are available. Populate RP_NotAvail with analysis
    1111             : /// pass that are required by pass P but are not available.
    1112     3674610 : void PMDataManager::collectRequiredAndUsedAnalyses(
    1113             :     SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
    1114             :     Pass *P) {
    1115     3674610 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1116             : 
    1117     4813541 :   for (const auto &UsedID : AnUsage->getUsedSet())
    1118      569470 :     if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
    1119      186826 :       UP.push_back(AnalysisPass);
    1120             : 
    1121    18353085 :   for (const auto &RequiredID : AnUsage->getRequiredSet())
    1122     7339235 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1123     7331209 :       UP.push_back(AnalysisPass);
    1124             :     else
    1125        8032 :       RP_NotAvail.push_back(RequiredID);
    1126             : 
    1127     4440760 :   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
    1128      383075 :     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
    1129      383076 :       UP.push_back(AnalysisPass);
    1130             :     else
    1131           0 :       RP_NotAvail.push_back(RequiredID);
    1132     3674609 : }
    1133             : 
    1134             : // All Required analyses should be available to the pass as it runs!  Here
    1135             : // we fill in the AnalysisImpls member of the pass so that it can
    1136             : // successfully use the getAnalysis() method to retrieve the
    1137             : // implementations it needs.
    1138             : //
    1139    36791409 : void PMDataManager::initializeAnalysisImpl(Pass *P) {
    1140    36791409 :   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
    1141             : 
    1142   187000069 :   for (const AnalysisID ID : AnUsage->getRequiredSet()) {
    1143    75104322 :     Pass *Impl = findAnalysisPass(ID, true);
    1144    75104308 :     if (!Impl)
    1145             :       // This may be analysis pass that is initialized on the fly.
    1146             :       // If that is not the case then it will raise an assert when it is used.
    1147      154440 :       continue;
    1148    74949868 :     AnalysisResolver *AR = P->getResolver();
    1149             :     assert(AR && "Analysis Resolver is not set");
    1150    74949868 :     AR->addAnalysisImplsPair(ID, Impl);
    1151             :   }
    1152    36791419 : }
    1153             : 
    1154             : /// Find the pass that implements Analysis AID. If desired pass is not found
    1155             : /// then return NULL.
    1156   382074368 : Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
    1157             : 
    1158             :   // Check if AvailableAnalysis map has one entry.
    1159   764150340 :   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
    1160             : 
    1161   382075972 :   if (I != AvailableAnalysis.end())
    1162    45645811 :     return I->second;
    1163             : 
    1164             :   // Search Parents through TopLevelManager
    1165   336430161 :   if (SearchParent)
    1166    63323564 :     return TPM->findAnalysisPass(AID);
    1167             : 
    1168             :   return nullptr;
    1169             : }
    1170             : 
    1171             : // Print list of passes that are last used by P.
    1172        4155 : void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
    1173             : 
    1174             :   SmallVector<Pass *, 12> LUses;
    1175             : 
    1176             :   // If this is a on the fly manager then it does not have TPM.
    1177        4155 :   if (!TPM)
    1178             :     return;
    1179             : 
    1180        4155 :   TPM->collectLastUses(LUses, P);
    1181             : 
    1182        4155 :   for (Pass *P : LUses) {
    1183           0 :     dbgs() << "--" << std::string(Offset*2, ' ');
    1184           0 :     P->dumpPassStructure(0);
    1185             :   }
    1186             : }
    1187             : 
    1188         579 : void PMDataManager::dumpPassArguments() const {
    1189       18319 :   for (Pass *P : PassVector) {
    1190        8870 :     if (PMDataManager *PMD = P->getAsPMDataManager())
    1191         437 :       PMD->dumpPassArguments();
    1192             :     else
    1193        8433 :       if (const PassInfo *PI =
    1194        8433 :             TPM->findAnalysisPassInfo(P->getPassID()))
    1195        8224 :         if (!PI->isAnalysisGroup())
    1196        8224 :           dbgs() << " -" << PI->getPassArgument();
    1197             :   }
    1198         579 : }
    1199             : 
    1200    75803830 : void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
    1201             :                                  enum PassDebuggingString S2,
    1202             :                                  StringRef Msg) {
    1203    75803830 :   if (PassDebugging < Executions)
    1204             :     return;
    1205          42 :   dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this
    1206          84 :          << std::string(getDepth() * 2 + 1, ' ');
    1207          42 :   switch (S1) {
    1208          19 :   case EXECUTION_MSG:
    1209          19 :     dbgs() << "Executing Pass '" << P->getPassName();
    1210          19 :     break;
    1211           5 :   case MODIFICATION_MSG:
    1212           5 :     dbgs() << "Made Modification '" << P->getPassName();
    1213           5 :     break;
    1214          18 :   case FREEING_MSG:
    1215          18 :     dbgs() << " Freeing Pass '" << P->getPassName();
    1216          18 :     break;
    1217             :   default:
    1218             :     break;
    1219             :   }
    1220          42 :   switch (S2) {
    1221           0 :   case ON_BASICBLOCK_MSG:
    1222           0 :     dbgs() << "' on BasicBlock '" << Msg << "'...\n";
    1223           0 :     break;
    1224          22 :   case ON_FUNCTION_MSG:
    1225          22 :     dbgs() << "' on Function '" << Msg << "'...\n";
    1226          22 :     break;
    1227          12 :   case ON_MODULE_MSG:
    1228          12 :     dbgs() << "' on Module '"  << Msg << "'...\n";
    1229          12 :     break;
    1230           0 :   case ON_REGION_MSG:
    1231           0 :     dbgs() << "' on Region '"  << Msg << "'...\n";
    1232           0 :     break;
    1233           0 :   case ON_LOOP_MSG:
    1234           0 :     dbgs() << "' on Loop '" << Msg << "'...\n";
    1235           0 :     break;
    1236           8 :   case ON_CG_MSG:
    1237           8 :     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
    1238           8 :     break;
    1239             :   default:
    1240             :     break;
    1241             :   }
    1242             : }
    1243             : 
    1244    36394455 : void PMDataManager::dumpRequiredSet(const Pass *P) const {
    1245    36394455 :   if (PassDebugging < Details)
    1246    36394445 :     return;
    1247             : 
    1248          10 :   AnalysisUsage analysisUsage;
    1249          10 :   P->getAnalysisUsage(analysisUsage);
    1250          10 :   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
    1251             : }
    1252             : 
    1253    36394149 : void PMDataManager::dumpPreservedSet(const Pass *P) const {
    1254    36394149 :   if (PassDebugging < Details)
    1255    36394139 :     return;
    1256             : 
    1257          10 :   AnalysisUsage analysisUsage;
    1258          10 :   P->getAnalysisUsage(analysisUsage);
    1259          10 :   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
    1260             : }
    1261             : 
    1262    35830922 : void PMDataManager::dumpUsedSet(const Pass *P) const {
    1263    35830922 :   if (PassDebugging < Details)
    1264    35830912 :     return;
    1265             : 
    1266          10 :   AnalysisUsage analysisUsage;
    1267          10 :   P->getAnalysisUsage(analysisUsage);
    1268          10 :   dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
    1269             : }
    1270             : 
    1271          30 : void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
    1272             :                                    const AnalysisUsage::VectorType &Set) const {
    1273             :   assert(PassDebugging >= Details);
    1274          30 :   if (Set.empty())
    1275             :     return;
    1276          27 :   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
    1277         195 :   for (unsigned i = 0; i != Set.size(); ++i) {
    1278          59 :     if (i) dbgs() << ',';
    1279         118 :     const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
    1280          59 :     if (!PInf) {
    1281             :       // Some preserved passes, such as AliasAnalysis, may not be initialized by
    1282             :       // all drivers.
    1283           0 :       dbgs() << " Uninitialized Pass";
    1284           0 :       continue;
    1285             :     }
    1286         118 :     dbgs() << ' ' << PInf->getPassName();
    1287             :   }
    1288           9 :   dbgs() << '\n';
    1289             : }
    1290             : 
    1291             : /// Add RequiredPass into list of lower level passes required by pass P.
    1292             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1293             : /// through getAnalysis interface.
    1294             : /// This should be handled by specific pass manager.
    1295           0 : void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1296           0 :   if (TPM) {
    1297           0 :     TPM->dumpArguments();
    1298           0 :     TPM->dumpPasses();
    1299             :   }
    1300             : 
    1301             :   // Module Level pass may required Function Level analysis info
    1302             :   // (e.g. dominator info). Pass manager uses on the fly function pass manager
    1303             :   // to provide this on demand. In that case, in Pass manager terminology,
    1304             :   // module level pass is requiring lower level analysis info managed by
    1305             :   // lower level pass manager.
    1306             : 
    1307             :   // When Pass manager is not able to order required analysis info, Pass manager
    1308             :   // checks whether any lower level manager will be able to provide this
    1309             :   // analysis info on demand or not.
    1310             : #ifndef NDEBUG
    1311             :   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
    1312             :   dbgs() << "' required by '" << P->getPassName() << "'\n";
    1313             : #endif
    1314           0 :   llvm_unreachable("Unable to schedule pass");
    1315             : }
    1316             : 
    1317           0 : Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
    1318           0 :   llvm_unreachable("Unable to find on the fly pass");
    1319             : }
    1320             : 
    1321             : // Destructor
    1322      518235 : PMDataManager::~PMDataManager() {
    1323     7575883 :   for (Pass *P : PassVector)
    1324     3658383 :     delete P;
    1325      259118 : }
    1326             : 
    1327             : //===----------------------------------------------------------------------===//
    1328             : // NOTE: Is this the right place to define this method ?
    1329             : // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
    1330    20377824 : Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
    1331    20377824 :   return PM.findAnalysisPass(ID, dir);
    1332             : }
    1333             : 
    1334        5209 : Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
    1335             :                                      Function &F) {
    1336        5209 :   return PM.getOnTheFlyPass(P, AnalysisPI, F);
    1337             : }
    1338             : 
    1339             : //===----------------------------------------------------------------------===//
    1340             : // BBPassManager implementation
    1341             : 
    1342             : /// Execute all of the passes scheduled for execution by invoking
    1343             : /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
    1344             : /// the function, and if so, return true.
    1345        1167 : bool BBPassManager::runOnFunction(Function &F) {
    1346        1167 :   if (F.isDeclaration())
    1347             :     return false;
    1348             : 
    1349             :   bool Changed = doInitialization(F);
    1350        1167 :   Module &M = *F.getParent();
    1351             : 
    1352        2510 :   for (BasicBlock &BB : F)
    1353        4029 :     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1354             :       BasicBlockPass *BP = getContainedPass(Index);
    1355             :       bool LocalChanged = false;
    1356             : 
    1357        1343 :       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, BB.getName());
    1358        1343 :       dumpRequiredSet(BP);
    1359             : 
    1360        1343 :       initializeAnalysisImpl(BP);
    1361             : 
    1362             :       {
    1363             :         // If the pass crashes, remember this.
    1364             :         PassManagerPrettyStackEntry X(BP, BB);
    1365        1343 :         TimeRegion PassTimer(getPassTimer(BP));
    1366        1343 :         unsigned InstrCount = initSizeRemarkInfo(M);
    1367        1343 :         LocalChanged |= BP->runOnBasicBlock(BB);
    1368        1343 :         emitInstrCountChangedRemark(BP, M, InstrCount);
    1369             :       }
    1370             : 
    1371        1343 :       Changed |= LocalChanged;
    1372        1343 :       if (LocalChanged)
    1373          69 :         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
    1374             :                      BB.getName());
    1375        1343 :       dumpPreservedSet(BP);
    1376        1343 :       dumpUsedSet(BP);
    1377             : 
    1378        1343 :       verifyPreservedAnalysis(BP);
    1379        1343 :       removeNotPreservedAnalysis(BP);
    1380        1343 :       recordAvailableAnalysis(BP);
    1381        1343 :       removeDeadPasses(BP, BB.getName(), ON_BASICBLOCK_MSG);
    1382             :     }
    1383             : 
    1384        1167 :   return doFinalization(F) || Changed;
    1385             : }
    1386             : 
    1387             : // Implement doInitialization and doFinalization
    1388         247 : bool BBPassManager::doInitialization(Module &M) {
    1389             :   bool Changed = false;
    1390             : 
    1391         741 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1392         247 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1393             : 
    1394         247 :   return Changed;
    1395             : }
    1396             : 
    1397         240 : bool BBPassManager::doFinalization(Module &M) {
    1398             :   bool Changed = false;
    1399             : 
    1400         480 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1401         480 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1402             : 
    1403         240 :   return Changed;
    1404             : }
    1405             : 
    1406             : bool BBPassManager::doInitialization(Function &F) {
    1407             :   bool Changed = false;
    1408             : 
    1409        3501 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1410             :     BasicBlockPass *BP = getContainedPass(Index);
    1411        1167 :     Changed |= BP->doInitialization(F);
    1412             :   }
    1413             : 
    1414             :   return Changed;
    1415             : }
    1416             : 
    1417             : bool BBPassManager::doFinalization(Function &F) {
    1418             :   bool Changed = false;
    1419             : 
    1420        3501 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1421             :     BasicBlockPass *BP = getContainedPass(Index);
    1422        1167 :     Changed |= BP->doFinalization(F);
    1423             :   }
    1424             : 
    1425             :   return Changed;
    1426             : }
    1427             : 
    1428             : 
    1429             : //===----------------------------------------------------------------------===//
    1430             : // FunctionPassManager implementation
    1431             : 
    1432             : /// Create new Function pass manager
    1433       11067 : FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
    1434       11067 :   FPM = new FunctionPassManagerImpl();
    1435             :   // FPM is the top level manager.
    1436       11067 :   FPM->setTopLevelManager(FPM);
    1437             : 
    1438       11067 :   AnalysisResolver *AR = new AnalysisResolver(*FPM);
    1439       11067 :   FPM->setResolver(AR);
    1440       11067 : }
    1441             : 
    1442       22312 : FunctionPassManager::~FunctionPassManager() {
    1443       11064 :   delete FPM;
    1444       11248 : }
    1445             : 
    1446       45894 : void FunctionPassManager::add(Pass *P) {
    1447       45894 :   FPM->add(P);
    1448       45894 : }
    1449             : 
    1450             : /// run - Execute all of the passes scheduled for execution.  Keep
    1451             : /// track of whether any of the passes modifies the function, and if
    1452             : /// so, return true.
    1453             : ///
    1454      178751 : bool FunctionPassManager::run(Function &F) {
    1455      357502 :   handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) {
    1456           0 :     report_fatal_error("Error reading bitcode file: " + EIB.message());
    1457             :   });
    1458      178751 :   return FPM->run(F);
    1459             : }
    1460             : 
    1461             : 
    1462             : /// doInitialization - Run all of the initializers for the function passes.
    1463             : ///
    1464       11034 : bool FunctionPassManager::doInitialization() {
    1465       11034 :   return FPM->doInitialization(*M);
    1466             : }
    1467             : 
    1468             : /// doFinalization - Run all of the finalizers for the function passes.
    1469             : ///
    1470       11034 : bool FunctionPassManager::doFinalization() {
    1471       11034 :   return FPM->doFinalization(*M);
    1472             : }
    1473             : 
    1474             : //===----------------------------------------------------------------------===//
    1475             : // FunctionPassManagerImpl implementation
    1476             : //
    1477       15782 : bool FunctionPassManagerImpl::doInitialization(Module &M) {
    1478             :   bool Changed = false;
    1479             : 
    1480       15782 :   dumpArguments();
    1481       15782 :   dumpPasses();
    1482             : 
    1483       71752 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1484       27985 :     Changed |= ImPass->doInitialization(M);
    1485             : 
    1486       47346 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1487       15782 :     Changed |= getContainedManager(Index)->doInitialization(M);
    1488             : 
    1489       15782 :   return Changed;
    1490             : }
    1491             : 
    1492       15773 : bool FunctionPassManagerImpl::doFinalization(Module &M) {
    1493             :   bool Changed = false;
    1494             : 
    1495       31546 :   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
    1496       31546 :     Changed |= getContainedManager(Index)->doFinalization(M);
    1497             : 
    1498       71739 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1499       27983 :     Changed |= ImPass->doFinalization(M);
    1500             : 
    1501       15773 :   return Changed;
    1502             : }
    1503             : 
    1504             : /// cleanup - After running all passes, clean up pass manager cache.
    1505      183960 : void FPPassManager::cleanup() {
    1506     1160580 :  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1507             :     FunctionPass *FP = getContainedPass(Index);
    1508      488310 :     AnalysisResolver *AR = FP->getResolver();
    1509             :     assert(AR && "Analysis Resolver is not set");
    1510             :     AR->clearAnalysisImpls();
    1511             :  }
    1512      183960 : }
    1513             : 
    1514        9948 : void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
    1515        9948 :   if (!wasRun)
    1516             :     return;
    1517       15627 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1518             :     FPPassManager *FPPM = getContainedManager(Index);
    1519       45483 :     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
    1520       20137 :       FPPM->getContainedPass(Index)->releaseMemory();
    1521             :     }
    1522             :   }
    1523        5209 :   wasRun = false;
    1524             : }
    1525             : 
    1526             : // Execute all the passes managed by this top level manager.
    1527             : // Return true if any function is modified by a pass.
    1528      183960 : bool FunctionPassManagerImpl::run(Function &F) {
    1529             :   bool Changed = false;
    1530      183960 :   TimingInfo::createTheTimeInfo();
    1531             : 
    1532      183960 :   initializeAllAnalysisInfo();
    1533      551880 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1534      183960 :     Changed |= getContainedManager(Index)->runOnFunction(F);
    1535      183960 :     F.getContext().yield();
    1536             :   }
    1537             : 
    1538      551880 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
    1539      183960 :     getContainedManager(Index)->cleanup();
    1540             : 
    1541      183960 :   wasRun = true;
    1542      183960 :   return Changed;
    1543             : }
    1544             : 
    1545             : //===----------------------------------------------------------------------===//
    1546             : // FPPassManager implementation
    1547             : 
    1548             : char FPPassManager::ID = 0;
    1549             : /// Print passes managed by this manager
    1550         115 : void FPPassManager::dumpPassStructure(unsigned Offset) {
    1551         115 :   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
    1552        7561 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1553             :     FunctionPass *FP = getContainedPass(Index);
    1554        3723 :     FP->dumpPassStructure(Offset + 1);
    1555        3723 :     dumpLastUses(FP, Offset+1);
    1556             :   }
    1557         115 : }
    1558             : 
    1559             : 
    1560             : /// Execute all of the passes scheduled for execution by invoking
    1561             : /// runOnFunction method.  Keep track of whether any of the passes modifies
    1562             : /// the function, and if so, return true.
    1563     1127788 : bool FPPassManager::runOnFunction(Function &F) {
    1564     1127788 :   if (F.isDeclaration())
    1565             :     return false;
    1566             : 
    1567             :   bool Changed = false;
    1568      897990 :   Module &M = *F.getParent();
    1569             :   // Collect inherited analysis from Module level pass manager.
    1570      897990 :   populateInheritedAnalysis(TPM->activeStack);
    1571             : 
    1572    72118114 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1573             :     FunctionPass *FP = getContainedPass(Index);
    1574             :     bool LocalChanged = false;
    1575             : 
    1576    35610209 :     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
    1577    35610214 :     dumpRequiredSet(FP);
    1578             : 
    1579    35610213 :     initializeAnalysisImpl(FP);
    1580             : 
    1581             :     {
    1582             :       PassManagerPrettyStackEntry X(FP, F);
    1583    35610219 :       TimeRegion PassTimer(getPassTimer(FP));
    1584    35610222 :       unsigned InstrCount = initSizeRemarkInfo(M);
    1585    35610224 :       LocalChanged |= FP->runOnFunction(F);
    1586    35610049 :       emitInstrCountChangedRemark(FP, M, InstrCount);
    1587             :     }
    1588             : 
    1589    35610065 :     Changed |= LocalChanged;
    1590    35610065 :     if (LocalChanged)
    1591     3180197 :       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
    1592    35610065 :     dumpPreservedSet(FP);
    1593    35610064 :     dumpUsedSet(FP);
    1594             : 
    1595    35610063 :     verifyPreservedAnalysis(FP);
    1596    35610059 :     removeNotPreservedAnalysis(FP);
    1597    35610068 :     recordAvailableAnalysis(FP);
    1598    35610067 :     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
    1599             :   }
    1600             :   return Changed;
    1601             : }
    1602             : 
    1603       66606 : bool FPPassManager::runOnModule(Module &M) {
    1604             :   bool Changed = false;
    1605             : 
    1606      922854 :   for (Function &F : M)
    1607      856384 :     Changed |= runOnFunction(F);
    1608             : 
    1609       66470 :   return Changed;
    1610             : }
    1611             : 
    1612       87697 : bool FPPassManager::doInitialization(Module &M) {
    1613             :   bool Changed = false;
    1614             : 
    1615     6816359 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1616     3364334 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1617             : 
    1618       87694 :   return Changed;
    1619             : }
    1620             : 
    1621       87387 : bool FPPassManager::doFinalization(Module &M) {
    1622             :   bool Changed = false;
    1623             : 
    1624     3436797 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1625     6698840 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1626             : 
    1627       87377 :   return Changed;
    1628             : }
    1629             : 
    1630             : //===----------------------------------------------------------------------===//
    1631             : // MPPassManager implementation
    1632             : 
    1633             : /// Execute all of the passes scheduled for execution by invoking
    1634             : /// runOnModule method.  Keep track of whether any of the passes modifies
    1635             : /// the module, and if so, return true.
    1636             : bool
    1637       52671 : MPPassManager::runOnModule(Module &M) {
    1638             :   bool Changed = false;
    1639             : 
    1640             :   // Initialize on-the-fly passes
    1641       57419 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1642        4748 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1643        4748 :     Changed |= FPP->doInitialization(M);
    1644             :   }
    1645             : 
    1646             :   // Initialize module passes
    1647      492121 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
    1648      219734 :     Changed |= getContainedPass(Index)->doInitialization(M);
    1649             : 
    1650      491702 :   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
    1651             :     ModulePass *MP = getContainedPass(Index);
    1652             :     bool LocalChanged = false;
    1653             : 
    1654      439336 :     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
    1655      219668 :     dumpRequiredSet(MP);
    1656             : 
    1657      219668 :     initializeAnalysisImpl(MP);
    1658             : 
    1659             :     {
    1660             :       PassManagerPrettyStackEntry X(MP, M);
    1661      219668 :       TimeRegion PassTimer(getPassTimer(MP));
    1662             : 
    1663      219668 :       unsigned InstrCount = initSizeRemarkInfo(M);
    1664      219668 :       LocalChanged |= MP->runOnModule(M);
    1665      219520 :       emitInstrCountChangedRemark(MP, M, InstrCount);
    1666             :     }
    1667             : 
    1668      219520 :     Changed |= LocalChanged;
    1669      219520 :     if (LocalChanged)
    1670       39396 :       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
    1671             :                    M.getModuleIdentifier());
    1672      219520 :     dumpPreservedSet(MP);
    1673      219520 :     dumpUsedSet(MP);
    1674             : 
    1675      219520 :     verifyPreservedAnalysis(MP);
    1676      219520 :     removeNotPreservedAnalysis(MP);
    1677      219520 :     recordAvailableAnalysis(MP);
    1678      219520 :     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
    1679             :   }
    1680             : 
    1681             :   // Finalize module passes
    1682      271594 :   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
    1683      438180 :     Changed |= getContainedPass(Index)->doFinalization(M);
    1684             : 
    1685             :   // Finalize on-the-fly passes
    1686       57243 :   for (auto &OnTheFlyManager : OnTheFlyManagers) {
    1687        4739 :     FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
    1688             :     // We don't know when is the last time an on-the-fly pass is run,
    1689             :     // so we need to releaseMemory / finalize here
    1690        4739 :     FPP->releaseMemoryOnTheFly();
    1691        4739 :     Changed |= FPP->doFinalization(M);
    1692             :   }
    1693             : 
    1694       52504 :   return Changed;
    1695             : }
    1696             : 
    1697             : /// Add RequiredPass into list of lower level passes required by pass P.
    1698             : /// RequiredPass is run on the fly by Pass Manager when P requests it
    1699             : /// through getAnalysis interface.
    1700        8032 : void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
    1701             :   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
    1702             :          "Unable to handle Pass that requires lower level Analysis pass");
    1703             :   assert((P->getPotentialPassManagerType() <
    1704             :           RequiredPass->getPotentialPassManagerType()) &&
    1705             :          "Unable to handle Pass that requires lower level Analysis pass");
    1706        8032 :   if (!RequiredPass)
    1707           0 :     return;
    1708             : 
    1709        8032 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
    1710        8032 :   if (!FPP) {
    1711        4748 :     FPP = new FunctionPassManagerImpl();
    1712             :     // FPP is the top level manager.
    1713        4748 :     FPP->setTopLevelManager(FPP);
    1714             : 
    1715        4748 :     OnTheFlyManagers[P] = FPP;
    1716             :   }
    1717             :   const PassInfo *RequiredPassPI =
    1718        8032 :       TPM->findAnalysisPassInfo(RequiredPass->getPassID());
    1719             : 
    1720        8032 :   Pass *FoundPass = nullptr;
    1721        8032 :   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
    1722        8031 :     FoundPass =
    1723        8031 :       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
    1724             :   }
    1725        8032 :   if (!FoundPass) {
    1726        8032 :     FoundPass = RequiredPass;
    1727             :     // This should be guaranteed to add RequiredPass to the passmanager given
    1728             :     // that we checked for an available analysis above.
    1729             :     FPP->add(RequiredPass);
    1730             :   }
    1731             :   // Register P as the last user of FoundPass or RequiredPass.
    1732             :   SmallVector<Pass *, 1> LU;
    1733        8032 :   LU.push_back(FoundPass);
    1734       16064 :   FPP->setLastUser(LU,  P);
    1735             : }
    1736             : 
    1737             : /// Return function pass corresponding to PassInfo PI, that is
    1738             : /// required by module pass MP. Instantiate analysis pass, by using
    1739             : /// its runOnFunction() for function F.
    1740        5209 : Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
    1741        5209 :   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
    1742             :   assert(FPP && "Unable to find on the fly pass");
    1743             : 
    1744        5209 :   FPP->releaseMemoryOnTheFly();
    1745        5209 :   FPP->run(F);
    1746        5209 :   return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
    1747             : }
    1748             : 
    1749             : 
    1750             : //===----------------------------------------------------------------------===//
    1751             : // PassManagerImpl implementation
    1752             : 
    1753             : //
    1754             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1755             : /// whether any of the passes modifies the module, and if so, return true.
    1756       52671 : bool PassManagerImpl::run(Module &M) {
    1757             :   bool Changed = false;
    1758       52671 :   TimingInfo::createTheTimeInfo();
    1759             : 
    1760       52671 :   dumpArguments();
    1761       52671 :   dumpPasses();
    1762             : 
    1763      693439 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1764      320384 :     Changed |= ImPass->doInitialization(M);
    1765             : 
    1766       52671 :   initializeAllAnalysisInfo();
    1767      157679 :   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
    1768       52671 :     Changed |= getContainedManager(Index)->runOnModule(M);
    1769       52504 :     M.getContext().yield();
    1770             :   }
    1771             : 
    1772      690676 :   for (ImmutablePass *ImPass : getImmutablePasses())
    1773      319086 :     Changed |= ImPass->doFinalization(M);
    1774             : 
    1775       52504 :   return Changed;
    1776             : }
    1777             : 
    1778             : //===----------------------------------------------------------------------===//
    1779             : // PassManager implementation
    1780             : 
    1781             : /// Create new pass manager
    1782       52854 : PassManager::PassManager() {
    1783       52854 :   PM = new PassManagerImpl();
    1784             :   // PM is the top level manager
    1785       52854 :   PM->setTopLevelManager(PM);
    1786       52854 : }
    1787             : 
    1788      105290 : PassManager::~PassManager() {
    1789       52641 :   delete PM;
    1790       52649 : }
    1791             : 
    1792     2352298 : void PassManager::add(Pass *P) {
    1793     2352298 :   PM->add(P);
    1794     2352297 : }
    1795             : 
    1796             : /// run - Execute all of the passes scheduled for execution.  Keep track of
    1797             : /// whether any of the passes modifies the module, and if so, return true.
    1798       52671 : bool PassManager::run(Module &M) {
    1799       52671 :   return PM->run(M);
    1800             : }
    1801             : 
    1802             : //===----------------------------------------------------------------------===//
    1803             : // TimingInfo implementation
    1804             : 
    1805             : bool llvm::TimePassesIsEnabled = false;
    1806      101193 : static cl::opt<bool, true> EnableTiming(
    1807      202386 :     "time-passes", cl::location(TimePassesIsEnabled), cl::Hidden,
    1808      303579 :     cl::desc("Time each pass, printing elapsed time for each on exit"));
    1809             : 
    1810             : // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
    1811             : // a non-null value (if the -time-passes option is enabled) or it leaves it
    1812             : // null.  It may be called multiple times.
    1813      236631 : void TimingInfo::createTheTimeInfo() {
    1814      236631 :   if (!TimePassesIsEnabled || TheTimeInfo) return;
    1815             : 
    1816             :   // Constructed the first time this is called, iff -time-passes is enabled.
    1817             :   // This guarantees that the object will be constructed before static globals,
    1818             :   // thus it will be destroyed before them.
    1819           0 :   static ManagedStatic<TimingInfo> TTI;
    1820           0 :   TheTimeInfo = &*TTI;
    1821             : }
    1822             : 
    1823             : /// If TimingInfo is enabled then start pass timer.
    1824    72976772 : Timer *llvm::getPassTimer(Pass *P) {
    1825    72976772 :   if (TheTimeInfo)
    1826           0 :     return TheTimeInfo->getPassTimer(P);
    1827             :   return nullptr;
    1828             : }
    1829             : 
    1830             : /// If timing is enabled, report the times collected up to now and then reset
    1831             : /// them.
    1832          66 : void llvm::reportAndResetTimings() {
    1833          66 :   if (TheTimeInfo)
    1834           0 :     TheTimeInfo->print();
    1835          66 : }
    1836             : 
    1837             : //===----------------------------------------------------------------------===//
    1838             : // PMStack implementation
    1839             : //
    1840             : 
    1841             : // Pop Pass Manager from the stack and clear its analysis info.
    1842       93234 : void PMStack::pop() {
    1843             : 
    1844             :   PMDataManager *Top = this->top();
    1845             :   Top->initializeAnalysisInfo();
    1846             : 
    1847             :   S.pop_back();
    1848       93234 : }
    1849             : 
    1850             : // Push PM on the stack and set its top level manager.
    1851      191445 : void PMStack::push(PMDataManager *PM) {
    1852             :   assert(PM && "Unable to push. Pass Manager expected");
    1853             :   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
    1854             : 
    1855      191445 :   if (!this->empty()) {
    1856             :     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
    1857             :            && "pushing bad pass manager to PMStack");
    1858      122776 :     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
    1859             : 
    1860             :     assert(TPM && "Unable to find top level manager");
    1861      122776 :     TPM->addIndirectPassManager(PM);
    1862      122776 :     PM->setTopLevelManager(TPM);
    1863      122776 :     PM->setDepth(this->top()->getDepth()+1);
    1864             :   } else {
    1865             :     assert((PM->getPassManagerType() == PMT_ModulePassManager
    1866             :            || PM->getPassManagerType() == PMT_FunctionPassManager)
    1867             :            && "pushing bad pass manager to PMStack");
    1868       68669 :     PM->setDepth(1);
    1869             :   }
    1870             : 
    1871      191445 :   S.push_back(PM);
    1872      191445 : }
    1873             : 
    1874             : // Dump content of the pass manager stack.
    1875           0 : LLVM_DUMP_METHOD void PMStack::dump() const {
    1876           0 :   for (PMDataManager *Manager : S)
    1877           0 :     dbgs() << Manager->getAsPass()->getPassName() << ' ';
    1878             : 
    1879           0 :   if (!S.empty())
    1880           0 :     dbgs() << '\n';
    1881           0 : }
    1882             : 
    1883             : /// Find appropriate Module Pass Manager in the PM Stack and
    1884             : /// add self into that manager.
    1885      225161 : void ModulePass::assignPassManager(PMStack &PMS,
    1886             :                                    PassManagerType PreferredType) {
    1887             :   // Find Module Pass Manager
    1888      340257 :   while (!PMS.empty()) {
    1889      282709 :     PassManagerType TopPMType = PMS.top()->getPassManagerType();
    1890      282709 :     if (TopPMType == PreferredType)
    1891             :       break; // We found desired pass manager
    1892       57548 :     else if (TopPMType > PMT_ModulePassManager)
    1893       57548 :       PMS.pop();    // Pop children pass managers
    1894             :     else
    1895             :       break;
    1896             :   }
    1897             :   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
    1898      225161 :   PMS.top()->add(this);
    1899      225161 : }
    1900             : 
    1901             : /// Find appropriate Function Pass Manager or Call Graph Pass Manager
    1902             : /// in the PM Stack and add self into that manager.
    1903     3364050 : void FunctionPass::assignPassManager(PMStack &PMS,
    1904             :                                      PassManagerType PreferredType) {
    1905             : 
    1906             :   // Find Function Pass Manager
    1907     3431780 :   while (!PMS.empty()) {
    1908     3397915 :     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
    1909       33865 :       PMS.pop();
    1910             :     else
    1911             :       break;
    1912             :   }
    1913             : 
    1914             :   // Create new Function Pass Manager if needed.
    1915             :   FPPassManager *FPP;
    1916     3364050 :   if (PMS.top()->getPassManagerType() == PMT_FunctionPassManager) {
    1917     3291994 :     FPP = (FPPassManager *)PMS.top();
    1918             :   } else {
    1919             :     assert(!PMS.empty() && "Unable to create Function Pass Manager");
    1920             :     PMDataManager *PMD = PMS.top();
    1921             : 
    1922             :     // [1] Create new Function Pass Manager
    1923       72058 :     FPP = new FPPassManager();
    1924             :     FPP->populateInheritedAnalysis(PMS);
    1925             : 
    1926             :     // [2] Set up new manager's top level manager
    1927       72058 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1928             :     TPM->addIndirectPassManager(FPP);
    1929             : 
    1930             :     // [3] Assign manager to manage this new manager. This may create
    1931             :     // and push new managers into PMS
    1932       72058 :     FPP->assignPassManager(PMS, PMD->getPassManagerType());
    1933             : 
    1934             :     // [4] Push new manager into PMS
    1935       72058 :     PMS.push(FPP);
    1936             :   }
    1937             : 
    1938             :   // Assign FPP as the manager of this pass.
    1939     3364052 :   FPP->add(this);
    1940     3364051 : }
    1941             : 
    1942             : /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
    1943             : /// in the PM Stack and add self into that manager.
    1944         247 : void BasicBlockPass::assignPassManager(PMStack &PMS,
    1945             :                                        PassManagerType PreferredType) {
    1946             :   BBPassManager *BBP;
    1947             : 
    1948             :   // Basic Pass Manager is a leaf pass manager. It does not handle
    1949             :   // any other pass manager.
    1950         494 :   if (!PMS.empty() &&
    1951         247 :       PMS.top()->getPassManagerType() == PMT_BasicBlockPassManager) {
    1952             :     BBP = (BBPassManager *)PMS.top();
    1953             :   } else {
    1954             :     // If leaf manager is not Basic Block Pass manager then create new
    1955             :     // basic Block Pass manager.
    1956             :     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
    1957             :     PMDataManager *PMD = PMS.top();
    1958             : 
    1959             :     // [1] Create new Basic Block Manager
    1960         247 :     BBP = new BBPassManager();
    1961             : 
    1962             :     // [2] Set up new manager's top level manager
    1963             :     // Basic Block Pass Manager does not live by itself
    1964         247 :     PMTopLevelManager *TPM = PMD->getTopLevelManager();
    1965             :     TPM->addIndirectPassManager(BBP);
    1966             : 
    1967             :     // [3] Assign manager to manage this new manager. This may create
    1968             :     // and push new managers into PMS
    1969         247 :     BBP->assignPassManager(PMS, PreferredType);
    1970             : 
    1971             :     // [4] Push new manager into PMS
    1972         247 :     PMS.push(BBP);
    1973             :   }
    1974             : 
    1975             :   // Assign BBP as the manager of this pass.
    1976         247 :   BBP->add(this);
    1977         247 : }
    1978             : 
    1979      367284 : PassManagerBase::~PassManagerBase() {}

Generated by: LCOV version 1.13