contrib/llvm-project/llvm/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
  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 PassDebugging("debug-pass", cl::Hidden,
  55                   cl::desc("Print PassManager debugging information"),
  56                   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   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 PrintBefore("print-before",
  71             llvm::cl::desc("Print IR before specified passes"),
  72             cl::Hidden);
  73
  74 static PassOptionList
  75 PrintAfter("print-after",
  76            llvm::cl::desc("Print IR after specified passes"),
  77            cl::Hidden);
  78
  79 static cl::opt<bool> PrintBeforeAll("print-before-all",
  80                                     llvm::cl::desc("Print IR before each pass"),
  81                                     cl::init(false), cl::Hidden);
  82 static cl::opt<bool> PrintAfterAll("print-after-all",
  83                                    llvm::cl::desc("Print IR after each pass"),
  84                                    cl::init(false), cl::Hidden);
  85
  86 static cl::opt<bool>
  87     PrintModuleScope("print-module-scope",
  88                      cl::desc("When printing IR for print-[before|after]{-all} "
  89                               "always print a module IR"),
  90                      cl::init(false), cl::Hidden);
  91
  92 static cl::list<std::string>
  93     PrintFuncsList("filter-print-funcs", cl::value_desc("function names"),
  94                    cl::desc("Only print IR for functions whose name "
  95                             "match this for all print-[before|after][-all] "
  96                             "options"),
  97                    cl::CommaSeparated, cl::Hidden);
  98
  99 /// This is a helper to determine whether to print IR before or
 100 /// after a pass.
 101
 102 bool llvm::shouldPrintBeforePass() {
 103   return PrintBeforeAll || !PrintBefore.empty();
 104 }
 105
 106 bool llvm::shouldPrintAfterPass() {
 107   return PrintAfterAll || !PrintAfter.empty();
 108 }
 109
 110 static bool ShouldPrintBeforeOrAfterPass(StringRef PassID,
 111                                          PassOptionList &PassesToPrint) {
 112   for (auto *PassInf : PassesToPrint) {
 113     if (PassInf)
 114       if (PassInf->getPassArgument() == PassID) {
 115         return true;
 116       }
 117   }
 118   return false;
 119 }
 120
 121 bool llvm::shouldPrintBeforePass(StringRef PassID) {
 122   return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PassID, PrintBefore);
 123 }
 124
 125 bool llvm::shouldPrintAfterPass(StringRef PassID) {
 126   return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PassID, PrintAfter);
 127 }
 128
 129 bool llvm::forcePrintModuleIR() { return PrintModuleScope; }
 130
 131 bool llvm::isFunctionInPrintList(StringRef FunctionName) {
 132   static std::unordered_set<std::string> PrintFuncNames(PrintFuncsList.begin(),
 133                                                         PrintFuncsList.end());
 134   return PrintFuncNames.empty() ||
 135          PrintFuncNames.count(std::string(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](StringRef 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 namespace llvm {
 318 namespace legacy {
 319 //===----------------------------------------------------------------------===//
 320 // FunctionPassManagerImpl
 321 //
 322 /// FunctionPassManagerImpl manages FPPassManagers
 323 class FunctionPassManagerImpl : public Pass,
 324                                 public PMDataManager,
 325                                 public PMTopLevelManager {
 326   virtual void anchor();
 327 private:
 328   bool wasRun;
 329 public:
 330   static char ID;
 331   explicit FunctionPassManagerImpl() :
 332     Pass(PT_PassManager, ID), PMDataManager(),
 333     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
 334
 335   /// \copydoc FunctionPassManager::add()
 336   void add(Pass *P) {
 337     schedulePass(P);
 338   }
 339
 340   /// createPrinterPass - Get a function printer pass.
 341   Pass *createPrinterPass(raw_ostream &O,
 342                           const std::string &Banner) const override {
 343     return createPrintFunctionPass(O, Banner);
 344   }
 345
 346   // Prepare for running an on the fly pass, freeing memory if needed
 347   // from a previous run.
 348   void releaseMemoryOnTheFly();
 349
 350   /// run - Execute all of the passes scheduled for execution.  Keep track of
 351   /// whether any of the passes modifies the module, and if so, return true.
 352   bool run(Function &F);
 353
 354   /// doInitialization - Run all of the initializers for the function passes.
 355   ///
 356   bool doInitialization(Module &M) override;
 357
 358   /// doFinalization - Run all of the finalizers for the function passes.
 359   ///
 360   bool doFinalization(Module &M) override;
 361
 362
 363   PMDataManager *getAsPMDataManager() override { return this; }
 364   Pass *getAsPass() override { return this; }
 365   PassManagerType getTopLevelPassManagerType() override {
 366     return PMT_FunctionPassManager;
 367   }
 368
 369   /// Pass Manager itself does not invalidate any analysis info.
 370   void getAnalysisUsage(AnalysisUsage &Info) const override {
 371     Info.setPreservesAll();
 372   }
 373
 374   FPPassManager *getContainedManager(unsigned N) {
 375     assert(N < PassManagers.size() && "Pass number out of range!");
 376     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
 377     return FP;
 378   }
 379
 380   void dumpPassStructure(unsigned Offset) override {
 381     for (unsigned I = 0; I < getNumContainedManagers(); ++I)
 382       getContainedManager(I)->dumpPassStructure(Offset);
 383   }
 384 };
 385
 386 void FunctionPassManagerImpl::anchor() {}
 387
 388 char FunctionPassManagerImpl::ID = 0;
 389
 390 //===----------------------------------------------------------------------===//
 391 // FunctionPassManagerImpl implementation
 392 //
 393 bool FunctionPassManagerImpl::doInitialization(Module &M) {
 394   bool Changed = false;
 395
 396   dumpArguments();
 397   dumpPasses();
 398
 399   for (ImmutablePass *ImPass : getImmutablePasses())
 400     Changed |= ImPass->doInitialization(M);
 401
 402   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
 403     Changed |= getContainedManager(Index)->doInitialization(M);
 404
 405   return Changed;
 406 }
 407
 408 bool FunctionPassManagerImpl::doFinalization(Module &M) {
 409   bool Changed = false;
 410
 411   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
 412     Changed |= getContainedManager(Index)->doFinalization(M);
 413
 414   for (ImmutablePass *ImPass : getImmutablePasses())
 415     Changed |= ImPass->doFinalization(M);
 416
 417   return Changed;
 418 }
 419
 420 void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
 421   if (!wasRun)
 422     return;
 423   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 424     FPPassManager *FPPM = getContainedManager(Index);
 425     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
 426       FPPM->getContainedPass(Index)->releaseMemory();
 427     }
 428   }
 429   wasRun = false;
 430 }
 431
 432 // Execute all the passes managed by this top level manager.
 433 // Return true if any function is modified by a pass.
 434 bool FunctionPassManagerImpl::run(Function &F) {
 435   bool Changed = false;
 436
 437   initializeAllAnalysisInfo();
 438   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 439     Changed |= getContainedManager(Index)->runOnFunction(F);
 440     F.getContext().yield();
 441   }
 442
 443   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
 444     getContainedManager(Index)->cleanup();
 445
 446   wasRun = true;
 447   return Changed;
 448 }
 449 } // namespace legacy
 450 } // namespace llvm
 451
 452 namespace {
 453 //===----------------------------------------------------------------------===//
 454 // MPPassManager
 455 //
 456 /// MPPassManager manages ModulePasses and function pass managers.
 457 /// It batches all Module passes and function pass managers together and
 458 /// sequences them to process one module.
 459 class MPPassManager : public Pass, public PMDataManager {
 460 public:
 461   static char ID;
 462   explicit MPPassManager() :
 463     Pass(PT_PassManager, ID), PMDataManager() { }
 464
 465   // Delete on the fly managers.
 466   ~MPPassManager() override {
 467     for (auto &OnTheFlyManager : OnTheFlyManagers) {
 468       legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
 469       delete FPP;
 470     }
 471   }
 472
 473   /// createPrinterPass - Get a module printer pass.
 474   Pass *createPrinterPass(raw_ostream &O,
 475                           const std::string &Banner) const override {
 476     return createPrintModulePass(O, Banner);
 477   }
 478
 479   /// run - Execute all of the passes scheduled for execution.  Keep track of
 480   /// whether any of the passes modifies the module, and if so, return true.
 481   bool runOnModule(Module &M);
 482
 483   using llvm::Pass::doInitialization;
 484   using llvm::Pass::doFinalization;
 485
 486   /// Pass Manager itself does not invalidate any analysis info.
 487   void getAnalysisUsage(AnalysisUsage &Info) const override {
 488     Info.setPreservesAll();
 489   }
 490
 491   /// Add RequiredPass into list of lower level passes required by pass P.
 492   /// RequiredPass is run on the fly by Pass Manager when P requests it
 493   /// through getAnalysis interface.
 494   void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) override;
 495
 496   /// Return function pass corresponding to PassInfo PI, that is
 497   /// required by module pass MP. Instantiate analysis pass, by using
 498   /// its runOnFunction() for function F.
 499   std::tuple<Pass *, bool> getOnTheFlyPass(Pass *MP, AnalysisID PI,
 500                                            Function &F) override;
 501
 502   StringRef getPassName() const override { return "Module Pass Manager"; }
 503
 504   PMDataManager *getAsPMDataManager() override { return this; }
 505   Pass *getAsPass() override { return this; }
 506
 507   // Print passes managed by this manager
 508   void dumpPassStructure(unsigned Offset) override {
 509     dbgs().indent(Offset*2) << "ModulePass Manager\n";
 510     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 511       ModulePass *MP = getContainedPass(Index);
 512       MP->dumpPassStructure(Offset + 1);
 513       MapVector<Pass *, legacy::FunctionPassManagerImpl *>::const_iterator I =
 514           OnTheFlyManagers.find(MP);
 515       if (I != OnTheFlyManagers.end())
 516         I->second->dumpPassStructure(Offset + 2);
 517       dumpLastUses(MP, Offset+1);
 518     }
 519   }
 520
 521   ModulePass *getContainedPass(unsigned N) {
 522     assert(N < PassVector.size() && "Pass number out of range!");
 523     return static_cast<ModulePass *>(PassVector[N]);
 524   }
 525
 526   PassManagerType getPassManagerType() const override {
 527     return PMT_ModulePassManager;
 528   }
 529
 530  private:
 531   /// Collection of on the fly FPPassManagers. These managers manage
 532   /// function passes that are required by module passes.
 533    MapVector<Pass *, legacy::FunctionPassManagerImpl *> OnTheFlyManagers;
 534 };
 535
 536 char MPPassManager::ID = 0;
 537 } // End anonymous namespace
 538
 539 namespace llvm {
 540 namespace legacy {
 541 //===----------------------------------------------------------------------===//
 542 // PassManagerImpl
 543 //
 544
 545 /// PassManagerImpl manages MPPassManagers
 546 class PassManagerImpl : public Pass,
 547                         public PMDataManager,
 548                         public PMTopLevelManager {
 549   virtual void anchor();
 550
 551 public:
 552   static char ID;
 553   explicit PassManagerImpl() :
 554     Pass(PT_PassManager, ID), PMDataManager(),
 555                               PMTopLevelManager(new MPPassManager()) {}
 556
 557   /// \copydoc PassManager::add()
 558   void add(Pass *P) {
 559     schedulePass(P);
 560   }
 561
 562   /// createPrinterPass - Get a module printer pass.
 563   Pass *createPrinterPass(raw_ostream &O,
 564                           const std::string &Banner) const override {
 565     return createPrintModulePass(O, Banner);
 566   }
 567
 568   /// run - Execute all of the passes scheduled for execution.  Keep track of
 569   /// whether any of the passes modifies the module, and if so, return true.
 570   bool run(Module &M);
 571
 572   using llvm::Pass::doInitialization;
 573   using llvm::Pass::doFinalization;
 574
 575   /// Pass Manager itself does not invalidate any analysis info.
 576   void getAnalysisUsage(AnalysisUsage &Info) const override {
 577     Info.setPreservesAll();
 578   }
 579
 580   PMDataManager *getAsPMDataManager() override { return this; }
 581   Pass *getAsPass() override { return this; }
 582   PassManagerType getTopLevelPassManagerType() override {
 583     return PMT_ModulePassManager;
 584   }
 585
 586   MPPassManager *getContainedManager(unsigned N) {
 587     assert(N < PassManagers.size() && "Pass number out of range!");
 588     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
 589     return MP;
 590   }
 591 };
 592
 593 void PassManagerImpl::anchor() {}
 594
 595 char PassManagerImpl::ID = 0;
 596
 597 //===----------------------------------------------------------------------===//
 598 // PassManagerImpl implementation
 599
 600 //
 601 /// run - Execute all of the passes scheduled for execution.  Keep track of
 602 /// whether any of the passes modifies the module, and if so, return true.
 603 bool PassManagerImpl::run(Module &M) {
 604   bool Changed = false;
 605
 606   dumpArguments();
 607   dumpPasses();
 608
 609   for (ImmutablePass *ImPass : getImmutablePasses())
 610     Changed |= ImPass->doInitialization(M);
 611
 612   initializeAllAnalysisInfo();
 613   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 614     Changed |= getContainedManager(Index)->runOnModule(M);
 615     M.getContext().yield();
 616   }
 617
 618   for (ImmutablePass *ImPass : getImmutablePasses())
 619     Changed |= ImPass->doFinalization(M);
 620
 621   return Changed;
 622 }
 623 } // namespace legacy
 624 } // namespace llvm
 625
 626 //===----------------------------------------------------------------------===//
 627 // PMTopLevelManager implementation
 628
 629 /// Initialize top level manager. Create first pass manager.
 630 PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
 631   PMDM->setTopLevelManager(this);
 632   addPassManager(PMDM);
 633   activeStack.push(PMDM);
 634 }
 635
 636 /// Set pass P as the last user of the given analysis passes.
 637 void
 638 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
 639   unsigned PDepth = 0;
 640   if (P->getResolver())
 641     PDepth = P->getResolver()->getPMDataManager().getDepth();
 642
 643   for (Pass *AP : AnalysisPasses) {
 644     LastUser[AP] = P;
 645
 646     if (P == AP)
 647       continue;
 648
 649     // Update the last users of passes that are required transitive by AP.
 650     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
 651     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
 652     SmallVector<Pass *, 12> LastUses;
 653     SmallVector<Pass *, 12> LastPMUses;
 654     for (AnalysisID ID : IDs) {
 655       Pass *AnalysisPass = findAnalysisPass(ID);
 656       assert(AnalysisPass && "Expected analysis pass to exist.");
 657       AnalysisResolver *AR = AnalysisPass->getResolver();
 658       assert(AR && "Expected analysis resolver to exist.");
 659       unsigned APDepth = AR->getPMDataManager().getDepth();
 660
 661       if (PDepth == APDepth)
 662         LastUses.push_back(AnalysisPass);
 663       else if (PDepth > APDepth)
 664         LastPMUses.push_back(AnalysisPass);
 665     }
 666
 667     setLastUser(LastUses, P);
 668
 669     // If this pass has a corresponding pass manager, push higher level
 670     // analysis to this pass manager.
 671     if (P->getResolver())
 672       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
 673
 674
 675     // If AP is the last user of other passes then make P last user of
 676     // such passes.
 677     for (auto LU : LastUser) {
 678       if (LU.second == AP)
 679         // DenseMap iterator is not invalidated here because
 680         // this is just updating existing entries.
 681         LastUser[LU.first] = P;
 682     }
 683   }
 684 }
 685
 686 /// Collect passes whose last user is P
 687 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
 688                                         Pass *P) {
 689   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
 690     InversedLastUser.find(P);
 691   if (DMI == InversedLastUser.end())
 692     return;
 693
 694   SmallPtrSet<Pass *, 8> &LU = DMI->second;
 695   for (Pass *LUP : LU) {
 696     LastUses.push_back(LUP);
 697   }
 698
 699 }
 700
 701 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
 702   AnalysisUsage *AnUsage = nullptr;
 703   auto DMI = AnUsageMap.find(P);
 704   if (DMI != AnUsageMap.end())
 705     AnUsage = DMI->second;
 706   else {
 707     // Look up the analysis usage from the pass instance (different instances
 708     // of the same pass can produce different results), but unique the
 709     // resulting object to reduce memory usage.  This helps to greatly reduce
 710     // memory usage when we have many instances of only a few pass types
 711     // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
 712     // of dependencies.
 713     AnalysisUsage AU;
 714     P->getAnalysisUsage(AU);
 715
 716     AUFoldingSetNode* Node = nullptr;
 717     FoldingSetNodeID ID;
 718     AUFoldingSetNode::Profile(ID, AU);
 719     void *IP = nullptr;
 720     if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
 721       Node = N;
 722     else {
 723       Node = new (AUFoldingSetNodeAllocator.Allocate()) AUFoldingSetNode(AU);
 724       UniqueAnalysisUsages.InsertNode(Node, IP);
 725     }
 726     assert(Node && "cached analysis usage must be non null");
 727
 728     AnUsageMap[P] = &Node->AU;
 729     AnUsage = &Node->AU;
 730   }
 731   return AnUsage;
 732 }
 733
 734 /// Schedule pass P for execution. Make sure that passes required by
 735 /// P are run before P is run. Update analysis info maintained by
 736 /// the manager. Remove dead passes. This is a recursive function.
 737 void PMTopLevelManager::schedulePass(Pass *P) {
 738
 739   // TODO : Allocate function manager for this pass, other wise required set
 740   // may be inserted into previous function manager
 741
 742   // Give pass a chance to prepare the stage.
 743   P->preparePassManager(activeStack);
 744
 745   // If P is an analysis pass and it is available then do not
 746   // generate the analysis again. Stale analysis info should not be
 747   // available at this point.
 748   const PassInfo *PI = findAnalysisPassInfo(P->getPassID());
 749   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
 750     // Remove any cached AnalysisUsage information.
 751     AnUsageMap.erase(P);
 752     delete P;
 753     return;
 754   }
 755
 756   AnalysisUsage *AnUsage = findAnalysisUsage(P);
 757
 758   bool checkAnalysis = true;
 759   while (checkAnalysis) {
 760     checkAnalysis = false;
 761
 762     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
 763     for (const AnalysisID ID : RequiredSet) {
 764
 765       Pass *AnalysisPass = findAnalysisPass(ID);
 766       if (!AnalysisPass) {
 767         const PassInfo *PI = findAnalysisPassInfo(ID);
 768
 769         if (!PI) {
 770           // Pass P is not in the global PassRegistry
 771           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
 772           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
 773           dbgs() << "Required Passes:" << "\n";
 774           for (const AnalysisID ID2 : RequiredSet) {
 775             if (ID == ID2)
 776               break;
 777             Pass *AnalysisPass2 = findAnalysisPass(ID2);
 778             if (AnalysisPass2) {
 779               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
 780             } else {
 781               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
 782               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
 783               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
 784             }
 785           }
 786         }
 787
 788         assert(PI && "Expected required passes to be initialized");
 789         AnalysisPass = PI->createPass();
 790         if (P->getPotentialPassManagerType () ==
 791             AnalysisPass->getPotentialPassManagerType())
 792           // Schedule analysis pass that is managed by the same pass manager.
 793           schedulePass(AnalysisPass);
 794         else if (P->getPotentialPassManagerType () >
 795                  AnalysisPass->getPotentialPassManagerType()) {
 796           // Schedule analysis pass that is managed by a new manager.
 797           schedulePass(AnalysisPass);
 798           // Recheck analysis passes to ensure that required analyses that
 799           // are already checked are still available.
 800           checkAnalysis = true;
 801         } else
 802           // Do not schedule this analysis. Lower level analysis
 803           // passes are run on the fly.
 804           delete AnalysisPass;
 805       }
 806     }
 807   }
 808
 809   // Now all required passes are available.
 810   if (ImmutablePass *IP = P->getAsImmutablePass()) {
 811     // P is a immutable pass and it will be managed by this
 812     // top level manager. Set up analysis resolver to connect them.
 813     PMDataManager *DM = getAsPMDataManager();
 814     AnalysisResolver *AR = new AnalysisResolver(*DM);
 815     P->setResolver(AR);
 816     DM->initializeAnalysisImpl(P);
 817     addImmutablePass(IP);
 818     DM->recordAvailableAnalysis(IP);
 819     return;
 820   }
 821
 822   if (PI && !PI->isAnalysis() && shouldPrintBeforePass(PI->getPassArgument())) {
 823     Pass *PP = P->createPrinterPass(
 824         dbgs(), ("*** IR Dump Before " + P->getPassName() + " ***").str());
 825     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
 826   }
 827
 828   // Add the requested pass to the best available pass manager.
 829   P->assignPassManager(activeStack, getTopLevelPassManagerType());
 830
 831   if (PI && !PI->isAnalysis() && shouldPrintAfterPass(PI->getPassArgument())) {
 832     Pass *PP = P->createPrinterPass(
 833         dbgs(), ("*** IR Dump After " + P->getPassName() + " ***").str());
 834     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
 835   }
 836 }
 837
 838 /// Find the pass that implements Analysis AID. Search immutable
 839 /// passes and all pass managers. If desired pass is not found
 840 /// then return NULL.
 841 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
 842   // For immutable passes we have a direct mapping from ID to pass, so check
 843   // that first.
 844   if (Pass *P = ImmutablePassMap.lookup(AID))
 845     return P;
 846
 847   // Check pass managers
 848   for (PMDataManager *PassManager : PassManagers)
 849     if (Pass *P = PassManager->findAnalysisPass(AID, false))
 850       return P;
 851
 852   // Check other pass managers
 853   for (PMDataManager *IndirectPassManager : IndirectPassManagers)
 854     if (Pass *P = IndirectPassManager->findAnalysisPass(AID, false))
 855       return P;
 856
 857   return nullptr;
 858 }
 859
 860 const PassInfo *PMTopLevelManager::findAnalysisPassInfo(AnalysisID AID) const {
 861   const PassInfo *&PI = AnalysisPassInfos[AID];
 862   if (!PI)
 863     PI = PassRegistry::getPassRegistry()->getPassInfo(AID);
 864   else
 865     assert(PI == PassRegistry::getPassRegistry()->getPassInfo(AID) &&
 866            "The pass info pointer changed for an analysis ID!");
 867
 868   return PI;
 869 }
 870
 871 void PMTopLevelManager::addImmutablePass(ImmutablePass *P) {
 872   P->initializePass();
 873   ImmutablePasses.push_back(P);
 874
 875   // Add this pass to the map from its analysis ID. We clobber any prior runs
 876   // of the pass in the map so that the last one added is the one found when
 877   // doing lookups.
 878   AnalysisID AID = P->getPassID();
 879   ImmutablePassMap[AID] = P;
 880
 881   // Also add any interfaces implemented by the immutable pass to the map for
 882   // fast lookup.
 883   const PassInfo *PassInf = findAnalysisPassInfo(AID);
 884   assert(PassInf && "Expected all immutable passes to be initialized");
 885   for (const PassInfo *ImmPI : PassInf->getInterfacesImplemented())
 886     ImmutablePassMap[ImmPI->getTypeInfo()] = P;
 887 }
 888
 889 // Print passes managed by this top level manager.
 890 void PMTopLevelManager::dumpPasses() const {
 891
 892   if (PassDebugging < Structure)
 893     return;
 894
 895   // Print out the immutable passes
 896   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
 897     ImmutablePasses[i]->dumpPassStructure(0);
 898   }
 899
 900   // Every class that derives from PMDataManager also derives from Pass
 901   // (sometimes indirectly), but there's no inheritance relationship
 902   // between PMDataManager and Pass, so we have to getAsPass to get
 903   // from a PMDataManager* to a Pass*.
 904   for (PMDataManager *Manager : PassManagers)
 905     Manager->getAsPass()->dumpPassStructure(1);
 906 }
 907
 908 void PMTopLevelManager::dumpArguments() const {
 909
 910   if (PassDebugging < Arguments)
 911     return;
 912
 913   dbgs() << "Pass Arguments: ";
 914   for (ImmutablePass *P : ImmutablePasses)
 915     if (const PassInfo *PI = findAnalysisPassInfo(P->getPassID())) {
 916       assert(PI && "Expected all immutable passes to be initialized");
 917       if (!PI->isAnalysisGroup())
 918         dbgs() << " -" << PI->getPassArgument();
 919     }
 920   for (PMDataManager *PM : PassManagers)
 921     PM->dumpPassArguments();
 922   dbgs() << "\n";
 923 }
 924
 925 void PMTopLevelManager::initializeAllAnalysisInfo() {
 926   for (PMDataManager *PM : PassManagers)
 927     PM->initializeAnalysisInfo();
 928
 929   // Initailize other pass managers
 930   for (PMDataManager *IPM : IndirectPassManagers)
 931     IPM->initializeAnalysisInfo();
 932
 933   for (auto LU : LastUser) {
 934     SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
 935     L.insert(LU.first);
 936   }
 937 }
 938
 939 /// Destructor
 940 PMTopLevelManager::~PMTopLevelManager() {
 941   for (PMDataManager *PM : PassManagers)
 942     delete PM;
 943
 944   for (ImmutablePass *P : ImmutablePasses)
 945     delete P;
 946 }
 947
 948 //===----------------------------------------------------------------------===//
 949 // PMDataManager implementation
 950
 951 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 952 void PMDataManager::recordAvailableAnalysis(Pass *P) {
 953   AnalysisID PI = P->getPassID();
 954
 955   AvailableAnalysis[PI] = P;
 956
 957   assert(!AvailableAnalysis.empty());
 958
 959   // This pass is the current implementation of all of the interfaces it
 960   // implements as well.
 961   const PassInfo *PInf = TPM->findAnalysisPassInfo(PI);
 962   if (!PInf) return;
 963   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
 964   for (unsigned i = 0, e = II.size(); i != e; ++i)
 965     AvailableAnalysis[II[i]->getTypeInfo()] = P;
 966 }
 967
 968 // Return true if P preserves high level analysis used by other
 969 // passes managed by this manager
 970 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
 971   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
 972   if (AnUsage->getPreservesAll())
 973     return true;
 974
 975   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
 976   for (Pass *P1 : HigherLevelAnalysis) {
 977     if (P1->getAsImmutablePass() == nullptr &&
 978         !is_contained(PreservedSet, P1->getPassID()))
 979       return false;
 980   }
 981
 982   return true;
 983 }
 984
 985 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
 986 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
 987   // Don't do this unless assertions are enabled.
 988 #ifdef NDEBUG
 989   return;
 990 #endif
 991   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
 992   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
 993
 994   // Verify preserved analysis
 995   for (AnalysisID AID : PreservedSet) {
 996     if (Pass *AP = findAnalysisPass(AID, true)) {
 997       TimeRegion PassTimer(getPassTimer(AP));
 998       AP->verifyAnalysis();
 999     }
1000   }
1001 }
1002
1003 /// Remove Analysis not preserved by Pass P
1004 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
1005   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1006   if (AnUsage->getPreservesAll())
1007     return;
1008
1009   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
1010   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
1011          E = AvailableAnalysis.end(); I != E; ) {
1012     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
1013     if (Info->second->getAsImmutablePass() == nullptr &&
1014         !is_contained(PreservedSet, Info->first)) {
1015       // Remove this analysis
1016       if (PassDebugging >= Details) {
1017         Pass *S = Info->second;
1018         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
1019         dbgs() << S->getPassName() << "'\n";
1020       }
1021       AvailableAnalysis.erase(Info);
1022     }
1023   }
1024
1025   // Check inherited analysis also. If P is not preserving analysis
1026   // provided by parent manager then remove it here.
1027   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
1028
1029     if (!InheritedAnalysis[Index])
1030       continue;
1031
1032     for (DenseMap<AnalysisID, Pass*>::iterator
1033            I = InheritedAnalysis[Index]->begin(),
1034            E = InheritedAnalysis[Index]->end(); I != E; ) {
1035       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
1036       if (Info->second->getAsImmutablePass() == nullptr &&
1037           !is_contained(PreservedSet, Info->first)) {
1038         // Remove this analysis
1039         if (PassDebugging >= Details) {
1040           Pass *S = Info->second;
1041           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
1042           dbgs() << S->getPassName() << "'\n";
1043         }
1044         InheritedAnalysis[Index]->erase(Info);
1045       }
1046     }
1047   }
1048 }
1049
1050 /// Remove analysis passes that are not used any longer
1051 void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
1052                                      enum PassDebuggingString DBG_STR) {
1053
1054   SmallVector<Pass *, 12> DeadPasses;
1055
1056   // If this is a on the fly manager then it does not have TPM.
1057   if (!TPM)
1058     return;
1059
1060   TPM->collectLastUses(DeadPasses, P);
1061
1062   if (PassDebugging >= Details && !DeadPasses.empty()) {
1063     dbgs() << " -*- '" <<  P->getPassName();
1064     dbgs() << "' is the last user of following pass instances.";
1065     dbgs() << " Free these instances\n";
1066   }
1067
1068   for (Pass *P : DeadPasses)
1069     freePass(P, Msg, DBG_STR);
1070 }
1071
1072 void PMDataManager::freePass(Pass *P, StringRef Msg,
1073                              enum PassDebuggingString DBG_STR) {
1074   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
1075
1076   {
1077     // If the pass crashes releasing memory, remember this.
1078     PassManagerPrettyStackEntry X(P);
1079     TimeRegion PassTimer(getPassTimer(P));
1080
1081     P->releaseMemory();
1082   }
1083
1084   AnalysisID PI = P->getPassID();
1085   if (const PassInfo *PInf = TPM->findAnalysisPassInfo(PI)) {
1086     // Remove the pass itself (if it is not already removed).
1087     AvailableAnalysis.erase(PI);
1088
1089     // Remove all interfaces this pass implements, for which it is also
1090     // listed as the available implementation.
1091     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
1092     for (unsigned i = 0, e = II.size(); i != e; ++i) {
1093       DenseMap<AnalysisID, Pass*>::iterator Pos =
1094         AvailableAnalysis.find(II[i]->getTypeInfo());
1095       if (Pos != AvailableAnalysis.end() && Pos->second == P)
1096         AvailableAnalysis.erase(Pos);
1097     }
1098   }
1099 }
1100
1101 /// Add pass P into the PassVector. Update
1102 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
1103 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
1104   // This manager is going to manage pass P. Set up analysis resolver
1105   // to connect them.
1106   AnalysisResolver *AR = new AnalysisResolver(*this);
1107   P->setResolver(AR);
1108
1109   // If a FunctionPass F is the last user of ModulePass info M
1110   // then the F's manager, not F, records itself as a last user of M.
1111   SmallVector<Pass *, 12> TransferLastUses;
1112
1113   if (!ProcessAnalysis) {
1114     // Add pass
1115     PassVector.push_back(P);
1116     return;
1117   }
1118
1119   // At the moment, this pass is the last user of all required passes.
1120   SmallVector<Pass *, 12> LastUses;
1121   SmallVector<Pass *, 8> UsedPasses;
1122   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
1123
1124   unsigned PDepth = this->getDepth();
1125
1126   collectRequiredAndUsedAnalyses(UsedPasses, ReqAnalysisNotAvailable, P);
1127   for (Pass *PUsed : UsedPasses) {
1128     unsigned RDepth = 0;
1129
1130     assert(PUsed->getResolver() && "Analysis Resolver is not set");
1131     PMDataManager &DM = PUsed->getResolver()->getPMDataManager();
1132     RDepth = DM.getDepth();
1133
1134     if (PDepth == RDepth)
1135       LastUses.push_back(PUsed);
1136     else if (PDepth > RDepth) {
1137       // Let the parent claim responsibility of last use
1138       TransferLastUses.push_back(PUsed);
1139       // Keep track of higher level analysis used by this manager.
1140       HigherLevelAnalysis.push_back(PUsed);
1141     } else
1142       llvm_unreachable("Unable to accommodate Used Pass");
1143   }
1144
1145   // Set P as P's last user until someone starts using P.
1146   // However, if P is a Pass Manager then it does not need
1147   // to record its last user.
1148   if (!P->getAsPMDataManager())
1149     LastUses.push_back(P);
1150   TPM->setLastUser(LastUses, P);
1151
1152   if (!TransferLastUses.empty()) {
1153     Pass *My_PM = getAsPass();
1154     TPM->setLastUser(TransferLastUses, My_PM);
1155     TransferLastUses.clear();
1156   }
1157
1158   // Now, take care of required analyses that are not available.
1159   for (AnalysisID ID : ReqAnalysisNotAvailable) {
1160     const PassInfo *PI = TPM->findAnalysisPassInfo(ID);
1161     Pass *AnalysisPass = PI->createPass();
1162     this->addLowerLevelRequiredPass(P, AnalysisPass);
1163   }
1164
1165   // Take a note of analysis required and made available by this pass.
1166   // Remove the analysis not preserved by this pass
1167   removeNotPreservedAnalysis(P);
1168   recordAvailableAnalysis(P);
1169
1170   // Add pass
1171   PassVector.push_back(P);
1172 }
1173
1174
1175 /// Populate UP with analysis pass that are used or required by
1176 /// pass P and are available. Populate RP_NotAvail with analysis
1177 /// pass that are required by pass P but are not available.
1178 void PMDataManager::collectRequiredAndUsedAnalyses(
1179     SmallVectorImpl<Pass *> &UP, SmallVectorImpl<AnalysisID> &RP_NotAvail,
1180     Pass *P) {
1181   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1182
1183   for (const auto &UsedID : AnUsage->getUsedSet())
1184     if (Pass *AnalysisPass = findAnalysisPass(UsedID, true))
1185       UP.push_back(AnalysisPass);
1186
1187   for (const auto &RequiredID : AnUsage->getRequiredSet())
1188     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
1189       UP.push_back(AnalysisPass);
1190     else
1191       RP_NotAvail.push_back(RequiredID);
1192
1193   for (const auto &RequiredID : AnUsage->getRequiredTransitiveSet())
1194     if (Pass *AnalysisPass = findAnalysisPass(RequiredID, true))
1195       UP.push_back(AnalysisPass);
1196     else
1197       RP_NotAvail.push_back(RequiredID);
1198 }
1199
1200 // All Required analyses should be available to the pass as it runs!  Here
1201 // we fill in the AnalysisImpls member of the pass so that it can
1202 // successfully use the getAnalysis() method to retrieve the
1203 // implementations it needs.
1204 //
1205 void PMDataManager::initializeAnalysisImpl(Pass *P) {
1206   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1207
1208   for (const AnalysisID ID : AnUsage->getRequiredSet()) {
1209     Pass *Impl = findAnalysisPass(ID, true);
1210     if (!Impl)
1211       // This may be analysis pass that is initialized on the fly.
1212       // If that is not the case then it will raise an assert when it is used.
1213       continue;
1214     AnalysisResolver *AR = P->getResolver();
1215     assert(AR && "Analysis Resolver is not set");
1216     AR->addAnalysisImplsPair(ID, Impl);
1217   }
1218 }
1219
1220 /// Find the pass that implements Analysis AID. If desired pass is not found
1221 /// then return NULL.
1222 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
1223
1224   // Check if AvailableAnalysis map has one entry.
1225   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
1226
1227   if (I != AvailableAnalysis.end())
1228     return I->second;
1229
1230   // Search Parents through TopLevelManager
1231   if (SearchParent)
1232     return TPM->findAnalysisPass(AID);
1233
1234   return nullptr;
1235 }
1236
1237 // Print list of passes that are last used by P.
1238 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
1239
1240   SmallVector<Pass *, 12> LUses;
1241
1242   // If this is a on the fly manager then it does not have TPM.
1243   if (!TPM)
1244     return;
1245
1246   TPM->collectLastUses(LUses, P);
1247
1248   for (Pass *P : LUses) {
1249     dbgs() << "--" << std::string(Offset*2, ' ');
1250     P->dumpPassStructure(0);
1251   }
1252 }
1253
1254 void PMDataManager::dumpPassArguments() const {
1255   for (Pass *P : PassVector) {
1256     if (PMDataManager *PMD = P->getAsPMDataManager())
1257       PMD->dumpPassArguments();
1258     else
1259       if (const PassInfo *PI =
1260             TPM->findAnalysisPassInfo(P->getPassID()))
1261         if (!PI->isAnalysisGroup())
1262           dbgs() << " -" << PI->getPassArgument();
1263   }
1264 }
1265
1266 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
1267                                  enum PassDebuggingString S2,
1268                                  StringRef Msg) {
1269   if (PassDebugging < Executions)
1270     return;
1271   dbgs() << "[" << std::chrono::system_clock::now() << "] " << (void *)this
1272          << std::string(getDepth() * 2 + 1, ' ');
1273   switch (S1) {
1274   case EXECUTION_MSG:
1275     dbgs() << "Executing Pass '" << P->getPassName();
1276     break;
1277   case MODIFICATION_MSG:
1278     dbgs() << "Made Modification '" << P->getPassName();
1279     break;
1280   case FREEING_MSG:
1281     dbgs() << " Freeing Pass '" << P->getPassName();
1282     break;
1283   default:
1284     break;
1285   }
1286   switch (S2) {
1287   case ON_FUNCTION_MSG:
1288     dbgs() << "' on Function '" << Msg << "'...\n";
1289     break;
1290   case ON_MODULE_MSG:
1291     dbgs() << "' on Module '"  << Msg << "'...\n";
1292     break;
1293   case ON_REGION_MSG:
1294     dbgs() << "' on Region '"  << Msg << "'...\n";
1295     break;
1296   case ON_LOOP_MSG:
1297     dbgs() << "' on Loop '" << Msg << "'...\n";
1298     break;
1299   case ON_CG_MSG:
1300     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
1301     break;
1302   default:
1303     break;
1304   }
1305 }
1306
1307 void PMDataManager::dumpRequiredSet(const Pass *P) const {
1308   if (PassDebugging < Details)
1309     return;
1310
1311   AnalysisUsage analysisUsage;
1312   P->getAnalysisUsage(analysisUsage);
1313   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
1314 }
1315
1316 void PMDataManager::dumpPreservedSet(const Pass *P) const {
1317   if (PassDebugging < Details)
1318     return;
1319
1320   AnalysisUsage analysisUsage;
1321   P->getAnalysisUsage(analysisUsage);
1322   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
1323 }
1324
1325 void PMDataManager::dumpUsedSet(const Pass *P) const {
1326   if (PassDebugging < Details)
1327     return;
1328
1329   AnalysisUsage analysisUsage;
1330   P->getAnalysisUsage(analysisUsage);
1331   dumpAnalysisUsage("Used", P, analysisUsage.getUsedSet());
1332 }
1333
1334 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
1335                                    const AnalysisUsage::VectorType &Set) const {
1336   assert(PassDebugging >= Details);
1337   if (Set.empty())
1338     return;
1339   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
1340   for (unsigned i = 0; i != Set.size(); ++i) {
1341     if (i) dbgs() << ',';
1342     const PassInfo *PInf = TPM->findAnalysisPassInfo(Set[i]);
1343     if (!PInf) {
1344       // Some preserved passes, such as AliasAnalysis, may not be initialized by
1345       // all drivers.
1346       dbgs() << " Uninitialized Pass";
1347       continue;
1348     }
1349     dbgs() << ' ' << PInf->getPassName();
1350   }
1351   dbgs() << '\n';
1352 }
1353
1354 /// Add RequiredPass into list of lower level passes required by pass P.
1355 /// RequiredPass is run on the fly by Pass Manager when P requests it
1356 /// through getAnalysis interface.
1357 /// This should be handled by specific pass manager.
1358 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1359   if (TPM) {
1360     TPM->dumpArguments();
1361     TPM->dumpPasses();
1362   }
1363
1364   // Module Level pass may required Function Level analysis info
1365   // (e.g. dominator info). Pass manager uses on the fly function pass manager
1366   // to provide this on demand. In that case, in Pass manager terminology,
1367   // module level pass is requiring lower level analysis info managed by
1368   // lower level pass manager.
1369
1370   // When Pass manager is not able to order required analysis info, Pass manager
1371   // checks whether any lower level manager will be able to provide this
1372   // analysis info on demand or not.
1373 #ifndef NDEBUG
1374   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
1375   dbgs() << "' required by '" << P->getPassName() << "'\n";
1376 #endif
1377   llvm_unreachable("Unable to schedule pass");
1378 }
1379
1380 std::tuple<Pass *, bool> PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI,
1381                                                         Function &F) {
1382   llvm_unreachable("Unable to find on the fly pass");
1383 }
1384
1385 // Destructor
1386 PMDataManager::~PMDataManager() {
1387   for (Pass *P : PassVector)
1388     delete P;
1389 }
1390
1391 //===----------------------------------------------------------------------===//
1392 // NOTE: Is this the right place to define this method ?
1393 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
1394 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
1395   return PM.findAnalysisPass(ID, dir);
1396 }
1397
1398 std::tuple<Pass *, bool>
1399 AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI, Function &F) {
1400   return PM.getOnTheFlyPass(P, AnalysisPI, F);
1401 }
1402
1403 namespace llvm {
1404 namespace legacy {
1405
1406 //===----------------------------------------------------------------------===//
1407 // FunctionPassManager implementation
1408
1409 /// Create new Function pass manager
1410 FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
1411   FPM = new legacy::FunctionPassManagerImpl();
1412   // FPM is the top level manager.
1413   FPM->setTopLevelManager(FPM);
1414
1415   AnalysisResolver *AR = new AnalysisResolver(*FPM);
1416   FPM->setResolver(AR);
1417 }
1418
1419 FunctionPassManager::~FunctionPassManager() {
1420   delete FPM;
1421 }
1422
1423 void FunctionPassManager::add(Pass *P) {
1424   FPM->add(P);
1425 }
1426
1427 /// run - Execute all of the passes scheduled for execution.  Keep
1428 /// track of whether any of the passes modifies the function, and if
1429 /// so, return true.
1430 ///
1431 bool FunctionPassManager::run(Function &F) {
1432   handleAllErrors(F.materialize(), [&](ErrorInfoBase &EIB) {
1433     report_fatal_error("Error reading bitcode file: " + EIB.message());
1434   });
1435   return FPM->run(F);
1436 }
1437
1438
1439 /// doInitialization - Run all of the initializers for the function passes.
1440 ///
1441 bool FunctionPassManager::doInitialization() {
1442   return FPM->doInitialization(*M);
1443 }
1444
1445 /// doFinalization - Run all of the finalizers for the function passes.
1446 ///
1447 bool FunctionPassManager::doFinalization() {
1448   return FPM->doFinalization(*M);
1449 }
1450 } // namespace legacy
1451 } // namespace llvm
1452
1453 /// cleanup - After running all passes, clean up pass manager cache.
1454 void FPPassManager::cleanup() {
1455  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1456     FunctionPass *FP = getContainedPass(Index);
1457     AnalysisResolver *AR = FP->getResolver();
1458     assert(AR && "Analysis Resolver is not set");
1459     AR->clearAnalysisImpls();
1460  }
1461 }
1462
1463
1464 //===----------------------------------------------------------------------===//
1465 // FPPassManager implementation
1466
1467 char FPPassManager::ID = 0;
1468 /// Print passes managed by this manager
1469 void FPPassManager::dumpPassStructure(unsigned Offset) {
1470   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
1471   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1472     FunctionPass *FP = getContainedPass(Index);
1473     FP->dumpPassStructure(Offset + 1);
1474     dumpLastUses(FP, Offset+1);
1475   }
1476 }
1477
1478
1479 /// Execute all of the passes scheduled for execution by invoking
1480 /// runOnFunction method.  Keep track of whether any of the passes modifies
1481 /// the function, and if so, return true.
1482 bool FPPassManager::runOnFunction(Function &F) {
1483   if (F.isDeclaration())
1484     return false;
1485
1486   bool Changed = false;
1487   Module &M = *F.getParent();
1488   // Collect inherited analysis from Module level pass manager.
1489   populateInheritedAnalysis(TPM->activeStack);
1490
1491   unsigned InstrCount, FunctionSize = 0;
1492   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1493   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1494   // Collect the initial size of the module.
1495   if (EmitICRemark) {
1496     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1497     FunctionSize = F.getInstructionCount();
1498   }
1499
1500   llvm::TimeTraceScope FunctionScope("OptFunction", F.getName());
1501
1502   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1503     FunctionPass *FP = getContainedPass(Index);
1504     bool LocalChanged = false;
1505
1506     llvm::TimeTraceScope PassScope("RunPass", FP->getPassName());
1507
1508     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
1509     dumpRequiredSet(FP);
1510
1511     initializeAnalysisImpl(FP);
1512
1513     {
1514       PassManagerPrettyStackEntry X(FP, F);
1515       TimeRegion PassTimer(getPassTimer(FP));
1516       LocalChanged |= FP->runOnFunction(F);
1517       if (EmitICRemark) {
1518         unsigned NewSize = F.getInstructionCount();
1519
1520         // Update the size of the function, emit a remark, and update the size
1521         // of the module.
1522         if (NewSize != FunctionSize) {
1523           int64_t Delta = static_cast<int64_t>(NewSize) -
1524                           static_cast<int64_t>(FunctionSize);
1525           emitInstrCountChangedRemark(FP, M, Delta, InstrCount,
1526                                       FunctionToInstrCount, &F);
1527           InstrCount = static_cast<int64_t>(InstrCount) + Delta;
1528           FunctionSize = NewSize;
1529         }
1530       }
1531     }
1532
1533     Changed |= LocalChanged;
1534     if (LocalChanged)
1535       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
1536     dumpPreservedSet(FP);
1537     dumpUsedSet(FP);
1538
1539     verifyPreservedAnalysis(FP);
1540     removeNotPreservedAnalysis(FP);
1541     recordAvailableAnalysis(FP);
1542     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
1543   }
1544
1545   return Changed;
1546 }
1547
1548 bool FPPassManager::runOnModule(Module &M) {
1549   bool Changed = false;
1550
1551   for (Function &F : M)
1552     Changed |= runOnFunction(F);
1553
1554   return Changed;
1555 }
1556
1557 bool FPPassManager::doInitialization(Module &M) {
1558   bool Changed = false;
1559
1560   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1561     Changed |= getContainedPass(Index)->doInitialization(M);
1562
1563   return Changed;
1564 }
1565
1566 bool FPPassManager::doFinalization(Module &M) {
1567   bool Changed = false;
1568
1569   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1570     Changed |= getContainedPass(Index)->doFinalization(M);
1571
1572   return Changed;
1573 }
1574
1575 //===----------------------------------------------------------------------===//
1576 // MPPassManager implementation
1577
1578 /// Execute all of the passes scheduled for execution by invoking
1579 /// runOnModule method.  Keep track of whether any of the passes modifies
1580 /// the module, and if so, return true.
1581 bool
1582 MPPassManager::runOnModule(Module &M) {
1583   llvm::TimeTraceScope TimeScope("OptModule", M.getName());
1584
1585   bool Changed = false;
1586
1587   // Initialize on-the-fly passes
1588   for (auto &OnTheFlyManager : OnTheFlyManagers) {
1589     legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1590     Changed |= FPP->doInitialization(M);
1591   }
1592
1593   // Initialize module passes
1594   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1595     Changed |= getContainedPass(Index)->doInitialization(M);
1596
1597   unsigned InstrCount;
1598   StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount;
1599   bool EmitICRemark = M.shouldEmitInstrCountChangedRemark();
1600   // Collect the initial size of the module.
1601   if (EmitICRemark)
1602     InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount);
1603
1604   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1605     ModulePass *MP = getContainedPass(Index);
1606     bool LocalChanged = false;
1607
1608     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
1609     dumpRequiredSet(MP);
1610
1611     initializeAnalysisImpl(MP);
1612
1613     {
1614       PassManagerPrettyStackEntry X(MP, M);
1615       TimeRegion PassTimer(getPassTimer(MP));
1616
1617       LocalChanged |= MP->runOnModule(M);
1618       if (EmitICRemark) {
1619         // Update the size of the module.
1620         unsigned ModuleCount = M.getInstructionCount();
1621         if (ModuleCount != InstrCount) {
1622           int64_t Delta = static_cast<int64_t>(ModuleCount) -
1623                           static_cast<int64_t>(InstrCount);
1624           emitInstrCountChangedRemark(MP, M, Delta, InstrCount,
1625                                       FunctionToInstrCount);
1626           InstrCount = ModuleCount;
1627         }
1628       }
1629     }
1630
1631     Changed |= LocalChanged;
1632     if (LocalChanged)
1633       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1634                    M.getModuleIdentifier());
1635     dumpPreservedSet(MP);
1636     dumpUsedSet(MP);
1637
1638     verifyPreservedAnalysis(MP);
1639     removeNotPreservedAnalysis(MP);
1640     recordAvailableAnalysis(MP);
1641     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
1642   }
1643
1644   // Finalize module passes
1645   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1646     Changed |= getContainedPass(Index)->doFinalization(M);
1647
1648   // Finalize on-the-fly passes
1649   for (auto &OnTheFlyManager : OnTheFlyManagers) {
1650     legacy::FunctionPassManagerImpl *FPP = OnTheFlyManager.second;
1651     // We don't know when is the last time an on-the-fly pass is run,
1652     // so we need to releaseMemory / finalize here
1653     FPP->releaseMemoryOnTheFly();
1654     Changed |= FPP->doFinalization(M);
1655   }
1656
1657   return Changed;
1658 }
1659
1660 /// Add RequiredPass into list of lower level passes required by pass P.
1661 /// RequiredPass is run on the fly by Pass Manager when P requests it
1662 /// through getAnalysis interface.
1663 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1664   assert(RequiredPass && "No required pass?");
1665   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
1666          "Unable to handle Pass that requires lower level Analysis pass");
1667   assert((P->getPotentialPassManagerType() <
1668           RequiredPass->getPotentialPassManagerType()) &&
1669          "Unable to handle Pass that requires lower level Analysis pass");
1670
1671   legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1672   if (!FPP) {
1673     FPP = new legacy::FunctionPassManagerImpl();
1674     // FPP is the top level manager.
1675     FPP->setTopLevelManager(FPP);
1676
1677     OnTheFlyManagers[P] = FPP;
1678   }
1679   const PassInfo *RequiredPassPI =
1680       TPM->findAnalysisPassInfo(RequiredPass->getPassID());
1681
1682   Pass *FoundPass = nullptr;
1683   if (RequiredPassPI && RequiredPassPI->isAnalysis()) {
1684     FoundPass =
1685       ((PMTopLevelManager*)FPP)->findAnalysisPass(RequiredPass->getPassID());
1686   }
1687   if (!FoundPass) {
1688     FoundPass = RequiredPass;
1689     // This should be guaranteed to add RequiredPass to the passmanager given
1690     // that we checked for an available analysis above.
1691     FPP->add(RequiredPass);
1692   }
1693   // Register P as the last user of FoundPass or RequiredPass.
1694   SmallVector<Pass *, 1> LU;
1695   LU.push_back(FoundPass);
1696   FPP->setLastUser(LU,  P);
1697 }
1698
1699 /// Return function pass corresponding to PassInfo PI, that is
1700 /// required by module pass MP. Instantiate analysis pass, by using
1701 /// its runOnFunction() for function F.
1702 std::tuple<Pass *, bool> MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI,
1703                                                         Function &F) {
1704   legacy::FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1705   assert(FPP && "Unable to find on the fly pass");
1706
1707   FPP->releaseMemoryOnTheFly();
1708   bool Changed = FPP->run(F);
1709   return std::make_tuple(((PMTopLevelManager *)FPP)->findAnalysisPass(PI),
1710                          Changed);
1711 }
1712
1713 namespace llvm {
1714 namespace legacy {
1715
1716 //===----------------------------------------------------------------------===//
1717 // PassManager implementation
1718
1719 /// Create new pass manager
1720 PassManager::PassManager() {
1721   PM = new PassManagerImpl();
1722   // PM is the top level manager
1723   PM->setTopLevelManager(PM);
1724 }
1725
1726 PassManager::~PassManager() {
1727   delete PM;
1728 }
1729
1730 void PassManager::add(Pass *P) {
1731   PM->add(P);
1732 }
1733
1734 /// run - Execute all of the passes scheduled for execution.  Keep track of
1735 /// whether any of the passes modifies the module, and if so, return true.
1736 bool PassManager::run(Module &M) {
1737   return PM->run(M);
1738 }
1739 } // namespace legacy
1740 } // namespace llvm
1741
1742 //===----------------------------------------------------------------------===//
1743 // PMStack implementation
1744 //
1745
1746 // Pop Pass Manager from the stack and clear its analysis info.
1747 void PMStack::pop() {
1748
1749   PMDataManager *Top = this->top();
1750   Top->initializeAnalysisInfo();
1751
1752   S.pop_back();
1753 }
1754
1755 // Push PM on the stack and set its top level manager.
1756 void PMStack::push(PMDataManager *PM) {
1757   assert(PM && "Unable to push. Pass Manager expected");
1758   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
1759
1760   if (!this->empty()) {
1761     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
1762            && "pushing bad pass manager to PMStack");
1763     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
1764
1765     assert(TPM && "Unable to find top level manager");
1766     TPM->addIndirectPassManager(PM);
1767     PM->setTopLevelManager(TPM);
1768     PM->setDepth(this->top()->getDepth()+1);
1769   } else {
1770     assert((PM->getPassManagerType() == PMT_ModulePassManager
1771            || PM->getPassManagerType() == PMT_FunctionPassManager)
1772            && "pushing bad pass manager to PMStack");
1773     PM->setDepth(1);
1774   }
1775
1776   S.push_back(PM);
1777 }
1778
1779 // Dump content of the pass manager stack.
1780 LLVM_DUMP_METHOD void PMStack::dump() const {
1781   for (PMDataManager *Manager : S)
1782     dbgs() << Manager->getAsPass()->getPassName() << ' ';
1783
1784   if (!S.empty())
1785     dbgs() << '\n';
1786 }
1787
1788 /// Find appropriate Module Pass Manager in the PM Stack and
1789 /// add self into that manager.
1790 void ModulePass::assignPassManager(PMStack &PMS,
1791                                    PassManagerType PreferredType) {
1792   // Find Module Pass Manager
1793   PassManagerType T;
1794   while ((T = PMS.top()->getPassManagerType()) > PMT_ModulePassManager &&
1795          T != PreferredType)
1796     PMS.pop();
1797   PMS.top()->add(this);
1798 }
1799
1800 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1801 /// in the PM Stack and add self into that manager.
1802 void FunctionPass::assignPassManager(PMStack &PMS,
1803                                      PassManagerType /*PreferredType*/) {
1804   // Find Function Pass Manager
1805   PMDataManager *PM;
1806   while (PM = PMS.top(), PM->getPassManagerType() > PMT_FunctionPassManager)
1807     PMS.pop();
1808
1809   // Create new Function Pass Manager if needed.
1810   if (PM->getPassManagerType() != PMT_FunctionPassManager) {
1811     // [1] Create new Function Pass Manager
1812     auto *FPP = new FPPassManager;
1813     FPP->populateInheritedAnalysis(PMS);
1814
1815     // [2] Set up new manager's top level manager
1816     PM->getTopLevelManager()->addIndirectPassManager(FPP);
1817
1818     // [3] Assign manager to manage this new manager. This may create
1819     // and push new managers into PMS
1820     FPP->assignPassManager(PMS, PM->getPassManagerType());
1821
1822     // [4] Push new manager into PMS
1823     PMS.push(FPP);
1824     PM = FPP;
1825   }
1826
1827   // Assign FPP as the manager of this pass.
1828   PM->add(this);
1829 }
1830
1831 legacy::PassManagerBase::~PassManagerBase() {}