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