lib/IR/LegacyPassManager.cpp

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