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