llvm/lib/IR/LegacyPassManager.cpp

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