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