lib/IR/PassManager.cpp

   1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LLVM Pass Manager infrastructure.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14
  15 #include "llvm/PassManagers.h"
  16 #include "llvm/Assembly/PrintModulePass.h"
  17 #include "llvm/Assembly/Writer.h"
  18 #include "llvm/IR/Module.h"
  19 #include "llvm/PassManager.h"
  20 #include "llvm/Support/CommandLine.h"
  21 #include "llvm/Support/Debug.h"
  22 #include "llvm/Support/ErrorHandling.h"
  23 #include "llvm/Support/ManagedStatic.h"
  24 #include "llvm/Support/Mutex.h"
  25 #include "llvm/Support/PassNameParser.h"
  26 #include "llvm/Support/Timer.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <algorithm>
  29 #include <map>
  30 using namespace llvm;
  31
  32 // See PassManagers.h for Pass Manager infrastructure overview.
  33
  34 namespace llvm {
  35
  36 //===----------------------------------------------------------------------===//
  37 // Pass debugging information.  Often it is useful to find out what pass is
  38 // running when a crash occurs in a utility.  When this library is compiled with
  39 // debugging on, a command line option (--debug-pass) is enabled that causes the
  40 // pass name to be printed before it executes.
  41 //
  42
  43 // Different debug levels that can be enabled...
  44 enum PassDebugLevel {
  45   Disabled, Arguments, Structure, Executions, Details
  46 };
  47
  48 bool TimePassesIsEnabled = false;
  49
  50 /// Encapsulate PassManager debug options. These are convenient options that
  51 /// should be available to any LLVM-based tool. They exist purely as
  52 /// command-line debug options, therefore don't need to be local to an LLVM
  53 /// context or captured by a formal API. In all respects they are handled like
  54 /// global variables, but being defined in the LLVMCore library cannot have
  55 /// static initializers and must be destroyed only at llvm_shutdown.
  56 struct PassDebugOpts {
  57   cl::opt<enum PassDebugLevel> PassDebugging;
  58
  59   typedef llvm::cl::list<const llvm::PassInfo *, bool, PassNameParser>
  60   PassOptionList;
  61
  62   // Print IR out before/after specified passes.
  63   PassOptionList PrintBefore;
  64
  65   PassOptionList PrintAfter;
  66
  67   cl::opt<bool> PrintBeforeAll;
  68   cl::opt<bool> PrintAfterAll;
  69
  70   cl::opt<bool,true> EnableTiming;
  71
  72   PassDebugOpts():
  73     PassDebugging("debug-pass", cl::Hidden,
  74                   cl::desc("Print PassManager debugging information"),
  75                   cl::values(
  76                     clEnumVal(Disabled , "disable debug output"),
  77                     clEnumVal(Arguments,
  78                               "print pass arguments to pass to 'opt'"),
  79                     clEnumVal(Structure, "print pass structure before run()"),
  80                     clEnumVal(Executions,
  81                               "print pass name before it is executed"),
  82                     clEnumVal(Details,
  83                               "print pass details when it is executed"),
  84                     clEnumValEnd)),
  85     PrintBefore("print-before",
  86                 llvm::cl::desc("Print IR before specified passes"),
  87                 cl::Hidden),
  88     PrintAfter("print-after",
  89                llvm::cl::desc("Print IR after specified passes"),
  90                cl::Hidden),
  91     PrintBeforeAll("print-before-all",
  92                    llvm::cl::desc("Print IR before each pass"),
  93                    cl::init(false)),
  94     PrintAfterAll("print-after-all",
  95                   llvm::cl::desc("Print IR after each pass"),
  96                   cl::init(false)),
  97     EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
  98                  cl::desc(
  99                    "Time each pass, printing elapsed time for each on exit"))
 100   {}
 101
 102   /// This is a helper to determine whether to print IR before or
 103   /// after a pass.
 104   bool ShouldPrintBeforeOrAfterPass(const PassInfo *PI,
 105                                     PassOptionList &PassesToPrint) {
 106     for (unsigned i = 0, ie = PassesToPrint.size(); i < ie; ++i) {
 107       const llvm::PassInfo *PassInf = PassesToPrint[i];
 108       if (PassInf)
 109         if (PassInf->getPassArgument() == PI->getPassArgument()) {
 110           return true;
 111         }
 112     }
 113     return false;
 114   }
 115
 116   /// This is a utility to check whether a pass should have IR dumped
 117   /// before it.
 118   bool ShouldPrintBeforePass(const PassInfo *PI) {
 119     return PrintBeforeAll || ShouldPrintBeforeOrAfterPass(PI, PrintBefore);
 120   }
 121
 122   /// This is a utility to check whether a pass should have IR dumped
 123   /// after it.
 124   bool ShouldPrintAfterPass(const PassInfo *PI) {
 125     return PrintAfterAll || ShouldPrintBeforeOrAfterPass(PI, PrintAfter);
 126   }
 127 };
 128
 129 static ManagedStatic<PassDebugOpts> GlobalPassDebugOpts;
 130
 131 /// This is called by tools to force registration of debugging options and
 132 /// ensure they appear in the tool's -help usage.
 133 void initializePassManager() {
 134   // Force instantiation of PassDebugOpts.
 135   *GlobalPassDebugOpts;
 136 }
 137
 138 } // End of llvm namespace
 139
 140 /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
 141 /// or higher is specified.
 142 bool PMDataManager::isPassDebuggingExecutionsOrMore() const {
 143   return GlobalPassDebugOpts->PassDebugging >= Executions;
 144 }
 145
 146 void PassManagerPrettyStackEntry::print(raw_ostream &OS) const {
 147   if (V == 0 && M == 0)
 148     OS << "Releasing pass '";
 149   else
 150     OS << "Running pass '";
 151
 152   OS << P->getPassName() << "'";
 153
 154   if (M) {
 155     OS << " on module '" << M->getModuleIdentifier() << "'.\n";
 156     return;
 157   }
 158   if (V == 0) {
 159     OS << '\n';
 160     return;
 161   }
 162
 163   OS << " on ";
 164   if (isa<Function>(V))
 165     OS << "function";
 166   else if (isa<BasicBlock>(V))
 167     OS << "basic block";
 168   else
 169     OS << "value";
 170
 171   OS << " '";
 172   WriteAsOperand(OS, V, /*PrintTy=*/false, M);
 173   OS << "'\n";
 174 }
 175
 176
 177 namespace {
 178
 179 //===----------------------------------------------------------------------===//
 180 // BBPassManager
 181 //
 182 /// BBPassManager manages BasicBlockPass. It batches all the
 183 /// pass together and sequence them to process one basic block before
 184 /// processing next basic block.
 185 class BBPassManager : public PMDataManager, public FunctionPass {
 186
 187 public:
 188   static char ID;
 189   explicit BBPassManager()
 190     : PMDataManager(), FunctionPass(ID) {}
 191
 192   /// Execute all of the passes scheduled for execution.  Keep track of
 193   /// whether any of the passes modifies the function, and if so, return true.
 194   bool runOnFunction(Function &F);
 195
 196   /// Pass Manager itself does not invalidate any analysis info.
 197   void getAnalysisUsage(AnalysisUsage &Info) const {
 198     Info.setPreservesAll();
 199   }
 200
 201   bool doInitialization(Module &M);
 202   bool doInitialization(Function &F);
 203   bool doFinalization(Module &M);
 204   bool doFinalization(Function &F);
 205
 206   virtual PMDataManager *getAsPMDataManager() { return this; }
 207   virtual Pass *getAsPass() { return this; }
 208
 209   virtual const char *getPassName() const {
 210     return "BasicBlock Pass Manager";
 211   }
 212
 213   // Print passes managed by this manager
 214   void dumpPassStructure(unsigned Offset) {
 215     llvm::dbgs().indent(Offset*2) << "BasicBlockPass Manager\n";
 216     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 217       BasicBlockPass *BP = getContainedPass(Index);
 218       BP->dumpPassStructure(Offset + 1);
 219       dumpLastUses(BP, Offset+1);
 220     }
 221   }
 222
 223   BasicBlockPass *getContainedPass(unsigned N) {
 224     assert(N < PassVector.size() && "Pass number out of range!");
 225     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
 226     return BP;
 227   }
 228
 229   virtual PassManagerType getPassManagerType() const {
 230     return PMT_BasicBlockPassManager;
 231   }
 232 };
 233
 234 char BBPassManager::ID = 0;
 235 }
 236
 237 namespace llvm {
 238
 239 //===----------------------------------------------------------------------===//
 240 // FunctionPassManagerImpl
 241 //
 242 /// FunctionPassManagerImpl manages FPPassManagers
 243 class FunctionPassManagerImpl : public Pass,
 244                                 public PMDataManager,
 245                                 public PMTopLevelManager {
 246   virtual void anchor();
 247 private:
 248   bool wasRun;
 249 public:
 250   static char ID;
 251   explicit FunctionPassManagerImpl() :
 252     Pass(PT_PassManager, ID), PMDataManager(),
 253     PMTopLevelManager(new FPPassManager()), wasRun(false) {}
 254
 255   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 256   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 257   /// will be destroyed as well, so there is no need to delete the pass.  This
 258   /// implies that all passes MUST be allocated with 'new'.
 259   void add(Pass *P) {
 260     schedulePass(P);
 261   }
 262
 263   /// createPrinterPass - Get a function printer pass.
 264   Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const {
 265     return createPrintFunctionPass(Banner, &O);
 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);
 279
 280   /// doFinalization - Run all of the finalizers for the function passes.
 281   ///
 282   bool doFinalization(Module &M);
 283
 284
 285   virtual PMDataManager *getAsPMDataManager() { return this; }
 286   virtual Pass *getAsPass() { return this; }
 287   virtual PassManagerType getTopLevelPassManagerType() {
 288     return PMT_FunctionPassManager;
 289   }
 290
 291   /// Pass Manager itself does not invalidate any analysis info.
 292   void getAnalysisUsage(AnalysisUsage &Info) const {
 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
 303 void FunctionPassManagerImpl::anchor() {}
 304
 305 char FunctionPassManagerImpl::ID = 0;
 306
 307 //===----------------------------------------------------------------------===//
 308 // MPPassManager
 309 //
 310 /// MPPassManager manages ModulePasses and function pass managers.
 311 /// It batches all Module passes and function pass managers together and
 312 /// sequences them to process one module.
 313 class MPPassManager : public Pass, public PMDataManager {
 314 public:
 315   static char ID;
 316   explicit MPPassManager() :
 317     Pass(PT_PassManager, ID), PMDataManager() { }
 318
 319   // Delete on the fly managers.
 320   virtual ~MPPassManager() {
 321     for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
 322            I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
 323          I != E; ++I) {
 324       FunctionPassManagerImpl *FPP = I->second;
 325       delete FPP;
 326     }
 327   }
 328
 329   /// createPrinterPass - Get a module printer pass.
 330   Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const {
 331     return createPrintModulePass(&O, false, Banner);
 332   }
 333
 334   /// run - Execute all of the passes scheduled for execution.  Keep track of
 335   /// whether any of the passes modifies the module, and if so, return true.
 336   bool runOnModule(Module &M);
 337
 338   using llvm::Pass::doInitialization;
 339   using llvm::Pass::doFinalization;
 340
 341   /// doInitialization - Run all of the initializers for the module passes.
 342   ///
 343   bool doInitialization();
 344
 345   /// doFinalization - Run all of the finalizers for the module passes.
 346   ///
 347   bool doFinalization();
 348
 349   /// Pass Manager itself does not invalidate any analysis info.
 350   void getAnalysisUsage(AnalysisUsage &Info) const {
 351     Info.setPreservesAll();
 352   }
 353
 354   /// Add RequiredPass into list of lower level passes required by pass P.
 355   /// RequiredPass is run on the fly by Pass Manager when P requests it
 356   /// through getAnalysis interface.
 357   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
 358
 359   /// Return function pass corresponding to PassInfo PI, that is
 360   /// required by module pass MP. Instantiate analysis pass, by using
 361   /// its runOnFunction() for function F.
 362   virtual Pass* getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F);
 363
 364   virtual const char *getPassName() const {
 365     return "Module Pass Manager";
 366   }
 367
 368   virtual PMDataManager *getAsPMDataManager() { return this; }
 369   virtual Pass *getAsPass() { return this; }
 370
 371   // Print passes managed by this manager
 372   void dumpPassStructure(unsigned Offset) {
 373     llvm::dbgs().indent(Offset*2) << "ModulePass Manager\n";
 374     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 375       ModulePass *MP = getContainedPass(Index);
 376       MP->dumpPassStructure(Offset + 1);
 377       std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I =
 378         OnTheFlyManagers.find(MP);
 379       if (I != OnTheFlyManagers.end())
 380         I->second->dumpPassStructure(Offset + 2);
 381       dumpLastUses(MP, Offset+1);
 382     }
 383   }
 384
 385   ModulePass *getContainedPass(unsigned N) {
 386     assert(N < PassVector.size() && "Pass number out of range!");
 387     return static_cast<ModulePass *>(PassVector[N]);
 388   }
 389
 390   virtual PassManagerType getPassManagerType() const {
 391     return PMT_ModulePassManager;
 392   }
 393
 394  private:
 395   /// Collection of on the fly FPPassManagers. These managers manage
 396   /// function passes that are required by module passes.
 397   std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers;
 398 };
 399
 400 char MPPassManager::ID = 0;
 401 //===----------------------------------------------------------------------===//
 402 // PassManagerImpl
 403 //
 404
 405 /// PassManagerImpl manages MPPassManagers
 406 class PassManagerImpl : public Pass,
 407                         public PMDataManager,
 408                         public PMTopLevelManager {
 409   virtual void anchor();
 410
 411 public:
 412   static char ID;
 413   explicit PassManagerImpl() :
 414     Pass(PT_PassManager, ID), PMDataManager(),
 415                               PMTopLevelManager(new MPPassManager()) {}
 416
 417   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 418   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 419   /// will be destroyed as well, so there is no need to delete the pass.  This
 420   /// implies that all passes MUST be allocated with 'new'.
 421   void add(Pass *P) {
 422     schedulePass(P);
 423   }
 424
 425   /// createPrinterPass - Get a module printer pass.
 426   Pass *createPrinterPass(raw_ostream &O, const std::string &Banner) const {
 427     return createPrintModulePass(&O, false, Banner);
 428   }
 429
 430   /// run - Execute all of the passes scheduled for execution.  Keep track of
 431   /// whether any of the passes modifies the module, and if so, return true.
 432   bool run(Module &M);
 433
 434   using llvm::Pass::doInitialization;
 435   using llvm::Pass::doFinalization;
 436
 437   /// doInitialization - Run all of the initializers for the module passes.
 438   ///
 439   bool doInitialization();
 440
 441   /// doFinalization - Run all of the finalizers for the module passes.
 442   ///
 443   bool doFinalization();
 444
 445   /// Pass Manager itself does not invalidate any analysis info.
 446   void getAnalysisUsage(AnalysisUsage &Info) const {
 447     Info.setPreservesAll();
 448   }
 449
 450   virtual PMDataManager *getAsPMDataManager() { return this; }
 451   virtual Pass *getAsPass() { return this; }
 452   virtual PassManagerType getTopLevelPassManagerType() {
 453     return PMT_ModulePassManager;
 454   }
 455
 456   MPPassManager *getContainedManager(unsigned N) {
 457     assert(N < PassManagers.size() && "Pass number out of range!");
 458     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
 459     return MP;
 460   }
 461 };
 462
 463 void PassManagerImpl::anchor() {}
 464
 465 char PassManagerImpl::ID = 0;
 466 } // End of llvm namespace
 467
 468 namespace {
 469
 470 //===----------------------------------------------------------------------===//
 471 /// TimingInfo Class - This class is used to calculate information about the
 472 /// amount of time each pass takes to execute.  This only happens when
 473 /// -time-passes is enabled on the command line.
 474 ///
 475
 476 static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex;
 477
 478 class TimingInfo {
 479   DenseMap<Pass*, Timer*> TimingData;
 480   TimerGroup TG;
 481 public:
 482   // Use 'create' member to get this.
 483   TimingInfo() : TG("... Pass execution timing report ...") {}
 484
 485   // TimingDtor - Print out information about timing information
 486   ~TimingInfo() {
 487     // Delete all of the timers, which accumulate their info into the
 488     // TimerGroup.
 489     for (DenseMap<Pass*, Timer*>::iterator I = TimingData.begin(),
 490          E = TimingData.end(); I != E; ++I)
 491       delete I->second;
 492     // TimerGroup is deleted next, printing the report.
 493   }
 494
 495   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
 496   // to a non null value (if the -time-passes option is enabled) or it leaves it
 497   // null.  It may be called multiple times.
 498   static void createTheTimeInfo();
 499
 500   /// getPassTimer - Return the timer for the specified pass if it exists.
 501   Timer *getPassTimer(Pass *P) {
 502     if (P->getAsPMDataManager())
 503       return 0;
 504
 505     sys::SmartScopedLock<true> Lock(*TimingInfoMutex);
 506     Timer *&T = TimingData[P];
 507     if (T == 0)
 508       T = new Timer(P->getPassName(), TG);
 509     return T;
 510   }
 511 };
 512
 513 } // End of anon namespace
 514
 515 static TimingInfo *TheTimeInfo;
 516
 517 //===----------------------------------------------------------------------===//
 518 // PMTopLevelManager implementation
 519
 520 /// Initialize top level manager. Create first pass manager.
 521 PMTopLevelManager::PMTopLevelManager(PMDataManager *PMDM) {
 522   PMDM->setTopLevelManager(this);
 523   addPassManager(PMDM);
 524   activeStack.push(PMDM);
 525 }
 526
 527 /// Set pass P as the last user of the given analysis passes.
 528 void
 529 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
 530   unsigned PDepth = 0;
 531   if (P->getResolver())
 532     PDepth = P->getResolver()->getPMDataManager().getDepth();
 533
 534   for (SmallVectorImpl<Pass *>::const_iterator I = AnalysisPasses.begin(),
 535          E = AnalysisPasses.end(); I != E; ++I) {
 536     Pass *AP = *I;
 537     LastUser[AP] = P;
 538
 539     if (P == AP)
 540       continue;
 541
 542     // Update the last users of passes that are required transitive by AP.
 543     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
 544     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
 545     SmallVector<Pass *, 12> LastUses;
 546     SmallVector<Pass *, 12> LastPMUses;
 547     for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(),
 548          E = IDs.end(); I != E; ++I) {
 549       Pass *AnalysisPass = findAnalysisPass(*I);
 550       assert(AnalysisPass && "Expected analysis pass to exist.");
 551       AnalysisResolver *AR = AnalysisPass->getResolver();
 552       assert(AR && "Expected analysis resolver to exist.");
 553       unsigned APDepth = AR->getPMDataManager().getDepth();
 554
 555       if (PDepth == APDepth)
 556         LastUses.push_back(AnalysisPass);
 557       else if (PDepth > APDepth)
 558         LastPMUses.push_back(AnalysisPass);
 559     }
 560
 561     setLastUser(LastUses, P);
 562
 563     // If this pass has a corresponding pass manager, push higher level
 564     // analysis to this pass manager.
 565     if (P->getResolver())
 566       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
 567
 568
 569     // If AP is the last user of other passes then make P last user of
 570     // such passes.
 571     for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(),
 572            LUE = LastUser.end(); LUI != LUE; ++LUI) {
 573       if (LUI->second == AP)
 574         // DenseMap iterator is not invalidated here because
 575         // this is just updating existing entries.
 576         LastUser[LUI->first] = P;
 577     }
 578   }
 579 }
 580
 581 /// Collect passes whose last user is P
 582 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
 583                                         Pass *P) {
 584   DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI =
 585     InversedLastUser.find(P);
 586   if (DMI == InversedLastUser.end())
 587     return;
 588
 589   SmallPtrSet<Pass *, 8> &LU = DMI->second;
 590   for (SmallPtrSet<Pass *, 8>::iterator I = LU.begin(),
 591          E = LU.end(); I != E; ++I) {
 592     LastUses.push_back(*I);
 593   }
 594
 595 }
 596
 597 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
 598   AnalysisUsage *AnUsage = NULL;
 599   DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.find(P);
 600   if (DMI != AnUsageMap.end())
 601     AnUsage = DMI->second;
 602   else {
 603     AnUsage = new AnalysisUsage();
 604     P->getAnalysisUsage(*AnUsage);
 605     AnUsageMap[P] = AnUsage;
 606   }
 607   return AnUsage;
 608 }
 609
 610 /// Schedule pass P for execution. Make sure that passes required by
 611 /// P are run before P is run. Update analysis info maintained by
 612 /// the manager. Remove dead passes. This is a recursive function.
 613 void PMTopLevelManager::schedulePass(Pass *P) {
 614
 615   // TODO : Allocate function manager for this pass, other wise required set
 616   // may be inserted into previous function manager
 617
 618   // Give pass a chance to prepare the stage.
 619   P->preparePassManager(activeStack);
 620
 621   // If P is an analysis pass and it is available then do not
 622   // generate the analysis again. Stale analysis info should not be
 623   // available at this point.
 624   const PassInfo *PI =
 625     PassRegistry::getPassRegistry()->getPassInfo(P->getPassID());
 626   if (PI && PI->isAnalysis() && findAnalysisPass(P->getPassID())) {
 627     delete P;
 628     return;
 629   }
 630
 631   AnalysisUsage *AnUsage = findAnalysisUsage(P);
 632
 633   bool checkAnalysis = true;
 634   while (checkAnalysis) {
 635     checkAnalysis = false;
 636
 637     const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
 638     for (AnalysisUsage::VectorType::const_iterator I = RequiredSet.begin(),
 639            E = RequiredSet.end(); I != E; ++I) {
 640
 641       Pass *AnalysisPass = findAnalysisPass(*I);
 642       if (!AnalysisPass) {
 643         const PassInfo *PI = PassRegistry::getPassRegistry()->getPassInfo(*I);
 644
 645         if (PI == NULL) {
 646           // Pass P is not in the global PassRegistry
 647           dbgs() << "Pass '"  << P->getPassName() << "' is not initialized." << "\n";
 648           dbgs() << "Verify if there is a pass dependency cycle." << "\n";
 649           dbgs() << "Required Passes:" << "\n";
 650           for (AnalysisUsage::VectorType::const_iterator I2 = RequiredSet.begin(),
 651                  E = RequiredSet.end(); I2 != E && I2 != I; ++I2) {
 652             Pass *AnalysisPass2 = findAnalysisPass(*I2);
 653             if (AnalysisPass2) {
 654               dbgs() << "\t" << AnalysisPass2->getPassName() << "\n";
 655             } else {
 656               dbgs() << "\t"   << "Error: Required pass not found! Possible causes:"  << "\n";
 657               dbgs() << "\t\t" << "- Pass misconfiguration (e.g.: missing macros)"    << "\n";
 658               dbgs() << "\t\t" << "- Corruption of the global PassRegistry"           << "\n";
 659             }
 660           }
 661         }
 662
 663         assert(PI && "Expected required passes to be initialized");
 664         AnalysisPass = PI->createPass();
 665         if (P->getPotentialPassManagerType () ==
 666             AnalysisPass->getPotentialPassManagerType())
 667           // Schedule analysis pass that is managed by the same pass manager.
 668           schedulePass(AnalysisPass);
 669         else if (P->getPotentialPassManagerType () >
 670                  AnalysisPass->getPotentialPassManagerType()) {
 671           // Schedule analysis pass that is managed by a new manager.
 672           schedulePass(AnalysisPass);
 673           // Recheck analysis passes to ensure that required analyses that
 674           // are already checked are still available.
 675           checkAnalysis = true;
 676         } else
 677           // Do not schedule this analysis. Lower level analsyis
 678           // passes are run on the fly.
 679           delete AnalysisPass;
 680       }
 681     }
 682   }
 683
 684   // Now all required passes are available.
 685   if (ImmutablePass *IP = P->getAsImmutablePass()) {
 686     // P is a immutable pass and it will be managed by this
 687     // top level manager. Set up analysis resolver to connect them.
 688     PMDataManager *DM = getAsPMDataManager();
 689     AnalysisResolver *AR = new AnalysisResolver(*DM);
 690     P->setResolver(AR);
 691     DM->initializeAnalysisImpl(P);
 692     addImmutablePass(IP);
 693     DM->recordAvailableAnalysis(IP);
 694     return;
 695   }
 696
 697   if (PI && !PI->isAnalysis() &&
 698       GlobalPassDebugOpts->ShouldPrintBeforePass(PI)) {
 699     Pass *PP = P->createPrinterPass(
 700       dbgs(), std::string("*** IR Dump Before ") + P->getPassName() + " ***");
 701     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
 702   }
 703
 704   // Add the requested pass to the best available pass manager.
 705   P->assignPassManager(activeStack, getTopLevelPassManagerType());
 706
 707   if (PI && !PI->isAnalysis() &&
 708       GlobalPassDebugOpts->ShouldPrintAfterPass(PI)) {
 709     Pass *PP = P->createPrinterPass(
 710       dbgs(), std::string("*** IR Dump After ") + P->getPassName() + " ***");
 711     PP->assignPassManager(activeStack, getTopLevelPassManagerType());
 712   }
 713 }
 714
 715 /// Find the pass that implements Analysis AID. Search immutable
 716 /// passes and all pass managers. If desired pass is not found
 717 /// then return NULL.
 718 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
 719
 720   // Check pass managers
 721   for (SmallVectorImpl<PMDataManager *>::iterator I = PassManagers.begin(),
 722          E = PassManagers.end(); I != E; ++I)
 723     if (Pass *P = (*I)->findAnalysisPass(AID, false))
 724       return P;
 725
 726   // Check other pass managers
 727   for (SmallVectorImpl<PMDataManager *>::iterator
 728          I = IndirectPassManagers.begin(),
 729          E = IndirectPassManagers.end(); I != E; ++I)
 730     if (Pass *P = (*I)->findAnalysisPass(AID, false))
 731       return P;
 732
 733   // Check the immutable passes. Iterate in reverse order so that we find
 734   // the most recently registered passes first.
 735   for (SmallVectorImpl<ImmutablePass *>::reverse_iterator I =
 736        ImmutablePasses.rbegin(), E = ImmutablePasses.rend(); I != E; ++I) {
 737     AnalysisID PI = (*I)->getPassID();
 738     if (PI == AID)
 739       return *I;
 740
 741     // If Pass not found then check the interfaces implemented by Immutable Pass
 742     const PassInfo *PassInf =
 743       PassRegistry::getPassRegistry()->getPassInfo(PI);
 744     assert(PassInf && "Expected all immutable passes to be initialized");
 745     const std::vector<const PassInfo*> &ImmPI =
 746       PassInf->getInterfacesImplemented();
 747     for (std::vector<const PassInfo*>::const_iterator II = ImmPI.begin(),
 748          EE = ImmPI.end(); II != EE; ++II) {
 749       if ((*II)->getTypeInfo() == AID)
 750         return *I;
 751     }
 752   }
 753
 754   return 0;
 755 }
 756
 757 // Print passes managed by this top level manager.
 758 void PMTopLevelManager::dumpPasses() const {
 759
 760   if (GlobalPassDebugOpts->PassDebugging < Structure)
 761     return;
 762
 763   // Print out the immutable passes
 764   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
 765     ImmutablePasses[i]->dumpPassStructure(0);
 766   }
 767
 768   // Every class that derives from PMDataManager also derives from Pass
 769   // (sometimes indirectly), but there's no inheritance relationship
 770   // between PMDataManager and Pass, so we have to getAsPass to get
 771   // from a PMDataManager* to a Pass*.
 772   for (SmallVectorImpl<PMDataManager *>::const_iterator I =
 773        PassManagers.begin(), E = PassManagers.end(); I != E; ++I)
 774     (*I)->getAsPass()->dumpPassStructure(1);
 775 }
 776
 777 void PMTopLevelManager::dumpArguments() const {
 778
 779   if (GlobalPassDebugOpts->PassDebugging < Arguments)
 780     return;
 781
 782   dbgs() << "Pass Arguments: ";
 783   for (SmallVectorImpl<ImmutablePass *>::const_iterator I =
 784        ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
 785     if (const PassInfo *PI =
 786         PassRegistry::getPassRegistry()->getPassInfo((*I)->getPassID())) {
 787       assert(PI && "Expected all immutable passes to be initialized");
 788       if (!PI->isAnalysisGroup())
 789         dbgs() << " -" << PI->getPassArgument();
 790     }
 791   for (SmallVectorImpl<PMDataManager *>::const_iterator I =
 792        PassManagers.begin(), E = PassManagers.end(); I != E; ++I)
 793     (*I)->dumpPassArguments();
 794   dbgs() << "\n";
 795 }
 796
 797 void PMTopLevelManager::initializeAllAnalysisInfo() {
 798   for (SmallVectorImpl<PMDataManager *>::iterator I = PassManagers.begin(),
 799          E = PassManagers.end(); I != E; ++I)
 800     (*I)->initializeAnalysisInfo();
 801
 802   // Initailize other pass managers
 803   for (SmallVectorImpl<PMDataManager *>::iterator
 804        I = IndirectPassManagers.begin(), E = IndirectPassManagers.end();
 805        I != E; ++I)
 806     (*I)->initializeAnalysisInfo();
 807
 808   for (DenseMap<Pass *, Pass *>::iterator DMI = LastUser.begin(),
 809         DME = LastUser.end(); DMI != DME; ++DMI) {
 810     DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator InvDMI =
 811       InversedLastUser.find(DMI->second);
 812     if (InvDMI != InversedLastUser.end()) {
 813       SmallPtrSet<Pass *, 8> &L = InvDMI->second;
 814       L.insert(DMI->first);
 815     } else {
 816       SmallPtrSet<Pass *, 8> L; L.insert(DMI->first);
 817       InversedLastUser[DMI->second] = L;
 818     }
 819   }
 820 }
 821
 822 /// Destructor
 823 PMTopLevelManager::~PMTopLevelManager() {
 824   for (SmallVectorImpl<PMDataManager *>::iterator I = PassManagers.begin(),
 825          E = PassManagers.end(); I != E; ++I)
 826     delete *I;
 827
 828   for (SmallVectorImpl<ImmutablePass *>::iterator
 829          I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
 830     delete *I;
 831
 832   for (DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.begin(),
 833          DME = AnUsageMap.end(); DMI != DME; ++DMI)
 834     delete DMI->second;
 835 }
 836
 837 //===----------------------------------------------------------------------===//
 838 // PMDataManager implementation
 839
 840 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 841 void PMDataManager::recordAvailableAnalysis(Pass *P) {
 842   AnalysisID PI = P->getPassID();
 843
 844   AvailableAnalysis[PI] = P;
 845
 846   assert(!AvailableAnalysis.empty());
 847
 848   // This pass is the current implementation of all of the interfaces it
 849   // implements as well.
 850   const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(PI);
 851   if (PInf == 0) return;
 852   const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
 853   for (unsigned i = 0, e = II.size(); i != e; ++i)
 854     AvailableAnalysis[II[i]->getTypeInfo()] = P;
 855 }
 856
 857 // Return true if P preserves high level analysis used by other
 858 // passes managed by this manager
 859 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) {
 860   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
 861   if (AnUsage->getPreservesAll())
 862     return true;
 863
 864   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
 865   for (SmallVectorImpl<Pass *>::iterator I = HigherLevelAnalysis.begin(),
 866          E = HigherLevelAnalysis.end(); I  != E; ++I) {
 867     Pass *P1 = *I;
 868     if (P1->getAsImmutablePass() == 0 &&
 869         std::find(PreservedSet.begin(), PreservedSet.end(),
 870                   P1->getPassID()) ==
 871            PreservedSet.end())
 872       return false;
 873   }
 874
 875   return true;
 876 }
 877
 878 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P.
 879 void PMDataManager::verifyPreservedAnalysis(Pass *P) {
 880   // Don't do this unless assertions are enabled.
 881 #ifdef NDEBUG
 882   return;
 883 #endif
 884   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
 885   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
 886
 887   // Verify preserved analysis
 888   for (AnalysisUsage::VectorType::const_iterator I = PreservedSet.begin(),
 889          E = PreservedSet.end(); I != E; ++I) {
 890     AnalysisID AID = *I;
 891     if (Pass *AP = findAnalysisPass(AID, true)) {
 892       TimeRegion PassTimer(getPassTimer(AP));
 893       AP->verifyAnalysis();
 894     }
 895   }
 896 }
 897
 898 /// Remove Analysis not preserved by Pass P
 899 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
 900   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
 901   if (AnUsage->getPreservesAll())
 902     return;
 903
 904   const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet();
 905   for (DenseMap<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
 906          E = AvailableAnalysis.end(); I != E; ) {
 907     DenseMap<AnalysisID, Pass*>::iterator Info = I++;
 908     if (Info->second->getAsImmutablePass() == 0 &&
 909         std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
 910         PreservedSet.end()) {
 911       // Remove this analysis
 912       if (GlobalPassDebugOpts->PassDebugging >= Details) {
 913         Pass *S = Info->second;
 914         dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
 915         dbgs() << S->getPassName() << "'\n";
 916       }
 917       AvailableAnalysis.erase(Info);
 918     }
 919   }
 920
 921   // Check inherited analysis also. If P is not preserving analysis
 922   // provided by parent manager then remove it here.
 923   for (unsigned Index = 0; Index < PMT_Last; ++Index) {
 924
 925     if (!InheritedAnalysis[Index])
 926       continue;
 927
 928     for (DenseMap<AnalysisID, Pass*>::iterator
 929            I = InheritedAnalysis[Index]->begin(),
 930            E = InheritedAnalysis[Index]->end(); I != E; ) {
 931       DenseMap<AnalysisID, Pass *>::iterator Info = I++;
 932       if (Info->second->getAsImmutablePass() == 0 &&
 933           std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
 934              PreservedSet.end()) {
 935         // Remove this analysis
 936         if (GlobalPassDebugOpts->PassDebugging >= Details) {
 937           Pass *S = Info->second;
 938           dbgs() << " -- '" <<  P->getPassName() << "' is not preserving '";
 939           dbgs() << S->getPassName() << "'\n";
 940         }
 941         InheritedAnalysis[Index]->erase(Info);
 942       }
 943     }
 944   }
 945 }
 946
 947 /// Remove analysis passes that are not used any longer
 948 void PMDataManager::removeDeadPasses(Pass *P, StringRef Msg,
 949                                      enum PassDebuggingString DBG_STR) {
 950
 951   SmallVector<Pass *, 12> DeadPasses;
 952
 953   // If this is a on the fly manager then it does not have TPM.
 954   if (!TPM)
 955     return;
 956
 957   TPM->collectLastUses(DeadPasses, P);
 958
 959   if (GlobalPassDebugOpts->PassDebugging >= Details && !DeadPasses.empty()) {
 960     dbgs() << " -*- '" <<  P->getPassName();
 961     dbgs() << "' is the last user of following pass instances.";
 962     dbgs() << " Free these instances\n";
 963   }
 964
 965   for (SmallVectorImpl<Pass *>::iterator I = DeadPasses.begin(),
 966          E = DeadPasses.end(); I != E; ++I)
 967     freePass(*I, Msg, DBG_STR);
 968 }
 969
 970 void PMDataManager::freePass(Pass *P, StringRef Msg,
 971                              enum PassDebuggingString DBG_STR) {
 972   dumpPassInfo(P, FREEING_MSG, DBG_STR, Msg);
 973
 974   {
 975     // If the pass crashes releasing memory, remember this.
 976     PassManagerPrettyStackEntry X(P);
 977     TimeRegion PassTimer(getPassTimer(P));
 978
 979     P->releaseMemory();
 980   }
 981
 982   AnalysisID PI = P->getPassID();
 983   if (const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(PI)) {
 984     // Remove the pass itself (if it is not already removed).
 985     AvailableAnalysis.erase(PI);
 986
 987     // Remove all interfaces this pass implements, for which it is also
 988     // listed as the available implementation.
 989     const std::vector<const PassInfo*> &II = PInf->getInterfacesImplemented();
 990     for (unsigned i = 0, e = II.size(); i != e; ++i) {
 991       DenseMap<AnalysisID, Pass*>::iterator Pos =
 992         AvailableAnalysis.find(II[i]->getTypeInfo());
 993       if (Pos != AvailableAnalysis.end() && Pos->second == P)
 994         AvailableAnalysis.erase(Pos);
 995     }
 996   }
 997 }
 998
 999 /// Add pass P into the PassVector. Update
1000 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
1001 void PMDataManager::add(Pass *P, bool ProcessAnalysis) {
1002   // This manager is going to manage pass P. Set up analysis resolver
1003   // to connect them.
1004   AnalysisResolver *AR = new AnalysisResolver(*this);
1005   P->setResolver(AR);
1006
1007   // If a FunctionPass F is the last user of ModulePass info M
1008   // then the F's manager, not F, records itself as a last user of M.
1009   SmallVector<Pass *, 12> TransferLastUses;
1010
1011   if (!ProcessAnalysis) {
1012     // Add pass
1013     PassVector.push_back(P);
1014     return;
1015   }
1016
1017   // At the moment, this pass is the last user of all required passes.
1018   SmallVector<Pass *, 12> LastUses;
1019   SmallVector<Pass *, 8> RequiredPasses;
1020   SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable;
1021
1022   unsigned PDepth = this->getDepth();
1023
1024   collectRequiredAnalysis(RequiredPasses,
1025                           ReqAnalysisNotAvailable, P);
1026   for (SmallVectorImpl<Pass *>::iterator I = RequiredPasses.begin(),
1027          E = RequiredPasses.end(); I != E; ++I) {
1028     Pass *PRequired = *I;
1029     unsigned RDepth = 0;
1030
1031     assert(PRequired->getResolver() && "Analysis Resolver is not set");
1032     PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
1033     RDepth = DM.getDepth();
1034
1035     if (PDepth == RDepth)
1036       LastUses.push_back(PRequired);
1037     else if (PDepth > RDepth) {
1038       // Let the parent claim responsibility of last use
1039       TransferLastUses.push_back(PRequired);
1040       // Keep track of higher level analysis used by this manager.
1041       HigherLevelAnalysis.push_back(PRequired);
1042     } else
1043       llvm_unreachable("Unable to accommodate Required Pass");
1044   }
1045
1046   // Set P as P's last user until someone starts using P.
1047   // However, if P is a Pass Manager then it does not need
1048   // to record its last user.
1049   if (P->getAsPMDataManager() == 0)
1050     LastUses.push_back(P);
1051   TPM->setLastUser(LastUses, P);
1052
1053   if (!TransferLastUses.empty()) {
1054     Pass *My_PM = getAsPass();
1055     TPM->setLastUser(TransferLastUses, My_PM);
1056     TransferLastUses.clear();
1057   }
1058
1059   // Now, take care of required analyses that are not available.
1060   for (SmallVectorImpl<AnalysisID>::iterator
1061          I = ReqAnalysisNotAvailable.begin(),
1062          E = ReqAnalysisNotAvailable.end() ;I != E; ++I) {
1063     const PassInfo *PI = PassRegistry::getPassRegistry()->getPassInfo(*I);
1064     Pass *AnalysisPass = PI->createPass();
1065     this->addLowerLevelRequiredPass(P, AnalysisPass);
1066   }
1067
1068   // Take a note of analysis required and made available by this pass.
1069   // Remove the analysis not preserved by this pass
1070   removeNotPreservedAnalysis(P);
1071   recordAvailableAnalysis(P);
1072
1073   // Add pass
1074   PassVector.push_back(P);
1075 }
1076
1077
1078 /// Populate RP with analysis pass that are required by
1079 /// pass P and are available. Populate RP_NotAvail with analysis
1080 /// pass that are required by pass P but are not available.
1081 void PMDataManager::collectRequiredAnalysis(SmallVectorImpl<Pass *> &RP,
1082                                        SmallVectorImpl<AnalysisID> &RP_NotAvail,
1083                                             Pass *P) {
1084   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1085   const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet();
1086   for (AnalysisUsage::VectorType::const_iterator
1087          I = RequiredSet.begin(), E = RequiredSet.end(); I != E; ++I) {
1088     if (Pass *AnalysisPass = findAnalysisPass(*I, true))
1089       RP.push_back(AnalysisPass);
1090     else
1091       RP_NotAvail.push_back(*I);
1092   }
1093
1094   const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
1095   for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(),
1096          E = IDs.end(); I != E; ++I) {
1097     if (Pass *AnalysisPass = findAnalysisPass(*I, true))
1098       RP.push_back(AnalysisPass);
1099     else
1100       RP_NotAvail.push_back(*I);
1101   }
1102 }
1103
1104 // All Required analyses should be available to the pass as it runs!  Here
1105 // we fill in the AnalysisImpls member of the pass so that it can
1106 // successfully use the getAnalysis() method to retrieve the
1107 // implementations it needs.
1108 //
1109 void PMDataManager::initializeAnalysisImpl(Pass *P) {
1110   AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P);
1111
1112   for (AnalysisUsage::VectorType::const_iterator
1113          I = AnUsage->getRequiredSet().begin(),
1114          E = AnUsage->getRequiredSet().end(); I != E; ++I) {
1115     Pass *Impl = findAnalysisPass(*I, true);
1116     if (Impl == 0)
1117       // This may be analysis pass that is initialized on the fly.
1118       // If that is not the case then it will raise an assert when it is used.
1119       continue;
1120     AnalysisResolver *AR = P->getResolver();
1121     assert(AR && "Analysis Resolver is not set");
1122     AR->addAnalysisImplsPair(*I, Impl);
1123   }
1124 }
1125
1126 /// Find the pass that implements Analysis AID. If desired pass is not found
1127 /// then return NULL.
1128 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
1129
1130   // Check if AvailableAnalysis map has one entry.
1131   DenseMap<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
1132
1133   if (I != AvailableAnalysis.end())
1134     return I->second;
1135
1136   // Search Parents through TopLevelManager
1137   if (SearchParent)
1138     return TPM->findAnalysisPass(AID);
1139
1140   return NULL;
1141 }
1142
1143 // Print list of passes that are last used by P.
1144 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
1145
1146   SmallVector<Pass *, 12> LUses;
1147
1148   // If this is a on the fly manager then it does not have TPM.
1149   if (!TPM)
1150     return;
1151
1152   TPM->collectLastUses(LUses, P);
1153
1154   for (SmallVectorImpl<Pass *>::iterator I = LUses.begin(),
1155          E = LUses.end(); I != E; ++I) {
1156     llvm::dbgs() << "--" << std::string(Offset*2, ' ');
1157     (*I)->dumpPassStructure(0);
1158   }
1159 }
1160
1161 void PMDataManager::dumpPassArguments() const {
1162   for (SmallVectorImpl<Pass *>::const_iterator I = PassVector.begin(),
1163         E = PassVector.end(); I != E; ++I) {
1164     if (PMDataManager *PMD = (*I)->getAsPMDataManager())
1165       PMD->dumpPassArguments();
1166     else
1167       if (const PassInfo *PI =
1168             PassRegistry::getPassRegistry()->getPassInfo((*I)->getPassID()))
1169         if (!PI->isAnalysisGroup())
1170           dbgs() << " -" << PI->getPassArgument();
1171   }
1172 }
1173
1174 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1,
1175                                  enum PassDebuggingString S2,
1176                                  StringRef Msg) {
1177   if (GlobalPassDebugOpts->PassDebugging < Executions)
1178     return;
1179   dbgs() << (void*)this << std::string(getDepth()*2+1, ' ');
1180   switch (S1) {
1181   case EXECUTION_MSG:
1182     dbgs() << "Executing Pass '" << P->getPassName();
1183     break;
1184   case MODIFICATION_MSG:
1185     dbgs() << "Made Modification '" << P->getPassName();
1186     break;
1187   case FREEING_MSG:
1188     dbgs() << " Freeing Pass '" << P->getPassName();
1189     break;
1190   default:
1191     break;
1192   }
1193   switch (S2) {
1194   case ON_BASICBLOCK_MSG:
1195     dbgs() << "' on BasicBlock '" << Msg << "'...\n";
1196     break;
1197   case ON_FUNCTION_MSG:
1198     dbgs() << "' on Function '" << Msg << "'...\n";
1199     break;
1200   case ON_MODULE_MSG:
1201     dbgs() << "' on Module '"  << Msg << "'...\n";
1202     break;
1203   case ON_REGION_MSG:
1204     dbgs() << "' on Region '"  << Msg << "'...\n";
1205     break;
1206   case ON_LOOP_MSG:
1207     dbgs() << "' on Loop '" << Msg << "'...\n";
1208     break;
1209   case ON_CG_MSG:
1210     dbgs() << "' on Call Graph Nodes '" << Msg << "'...\n";
1211     break;
1212   default:
1213     break;
1214   }
1215 }
1216
1217 void PMDataManager::dumpRequiredSet(const Pass *P) const {
1218   if (GlobalPassDebugOpts->PassDebugging < Details)
1219     return;
1220
1221   AnalysisUsage analysisUsage;
1222   P->getAnalysisUsage(analysisUsage);
1223   dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet());
1224 }
1225
1226 void PMDataManager::dumpPreservedSet(const Pass *P) const {
1227   if (GlobalPassDebugOpts->PassDebugging < Details)
1228     return;
1229
1230   AnalysisUsage analysisUsage;
1231   P->getAnalysisUsage(analysisUsage);
1232   dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet());
1233 }
1234
1235 void PMDataManager::dumpAnalysisUsage(StringRef Msg, const Pass *P,
1236                                    const AnalysisUsage::VectorType &Set) const {
1237   assert(GlobalPassDebugOpts->PassDebugging >= Details);
1238   if (Set.empty())
1239     return;
1240   dbgs() << (const void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
1241   for (unsigned i = 0; i != Set.size(); ++i) {
1242     if (i) dbgs() << ',';
1243     const PassInfo *PInf = PassRegistry::getPassRegistry()->getPassInfo(Set[i]);
1244     if (!PInf) {
1245       // Some preserved passes, such as AliasAnalysis, may not be initialized by
1246       // all drivers.
1247       dbgs() << " Uninitialized Pass";
1248       continue;
1249     }
1250     dbgs() << ' ' << PInf->getPassName();
1251   }
1252   dbgs() << '\n';
1253 }
1254
1255 /// Add RequiredPass into list of lower level passes required by pass P.
1256 /// RequiredPass is run on the fly by Pass Manager when P requests it
1257 /// through getAnalysis interface.
1258 /// This should be handled by specific pass manager.
1259 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1260   if (TPM) {
1261     TPM->dumpArguments();
1262     TPM->dumpPasses();
1263   }
1264
1265   // Module Level pass may required Function Level analysis info
1266   // (e.g. dominator info). Pass manager uses on the fly function pass manager
1267   // to provide this on demand. In that case, in Pass manager terminology,
1268   // module level pass is requiring lower level analysis info managed by
1269   // lower level pass manager.
1270
1271   // When Pass manager is not able to order required analysis info, Pass manager
1272   // checks whether any lower level manager will be able to provide this
1273   // analysis info on demand or not.
1274 #ifndef NDEBUG
1275   dbgs() << "Unable to schedule '" << RequiredPass->getPassName();
1276   dbgs() << "' required by '" << P->getPassName() << "'\n";
1277 #endif
1278   llvm_unreachable("Unable to schedule pass");
1279 }
1280
1281 Pass *PMDataManager::getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F) {
1282   llvm_unreachable("Unable to find on the fly pass");
1283 }
1284
1285 // Destructor
1286 PMDataManager::~PMDataManager() {
1287   for (SmallVectorImpl<Pass *>::iterator I = PassVector.begin(),
1288          E = PassVector.end(); I != E; ++I)
1289     delete *I;
1290 }
1291
1292 //===----------------------------------------------------------------------===//
1293 // NOTE: Is this the right place to define this method ?
1294 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist.
1295 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const {
1296   return PM.findAnalysisPass(ID, dir);
1297 }
1298
1299 Pass *AnalysisResolver::findImplPass(Pass *P, AnalysisID AnalysisPI,
1300                                      Function &F) {
1301   return PM.getOnTheFlyPass(P, AnalysisPI, F);
1302 }
1303
1304 //===----------------------------------------------------------------------===//
1305 // BBPassManager implementation
1306
1307 /// Execute all of the passes scheduled for execution by invoking
1308 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
1309 /// the function, and if so, return true.
1310 bool BBPassManager::runOnFunction(Function &F) {
1311   if (F.isDeclaration())
1312     return false;
1313
1314   bool Changed = doInitialization(F);
1315
1316   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
1317     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1318       BasicBlockPass *BP = getContainedPass(Index);
1319       bool LocalChanged = false;
1320
1321       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getName());
1322       dumpRequiredSet(BP);
1323
1324       initializeAnalysisImpl(BP);
1325
1326       {
1327         // If the pass crashes, remember this.
1328         PassManagerPrettyStackEntry X(BP, *I);
1329         TimeRegion PassTimer(getPassTimer(BP));
1330
1331         LocalChanged |= BP->runOnBasicBlock(*I);
1332       }
1333
1334       Changed |= LocalChanged;
1335       if (LocalChanged)
1336         dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG,
1337                      I->getName());
1338       dumpPreservedSet(BP);
1339
1340       verifyPreservedAnalysis(BP);
1341       removeNotPreservedAnalysis(BP);
1342       recordAvailableAnalysis(BP);
1343       removeDeadPasses(BP, I->getName(), ON_BASICBLOCK_MSG);
1344     }
1345
1346   return doFinalization(F) || Changed;
1347 }
1348
1349 // Implement doInitialization and doFinalization
1350 bool BBPassManager::doInitialization(Module &M) {
1351   bool Changed = false;
1352
1353   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1354     Changed |= getContainedPass(Index)->doInitialization(M);
1355
1356   return Changed;
1357 }
1358
1359 bool BBPassManager::doFinalization(Module &M) {
1360   bool Changed = false;
1361
1362   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1363     Changed |= getContainedPass(Index)->doFinalization(M);
1364
1365   return Changed;
1366 }
1367
1368 bool BBPassManager::doInitialization(Function &F) {
1369   bool Changed = false;
1370
1371   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1372     BasicBlockPass *BP = getContainedPass(Index);
1373     Changed |= BP->doInitialization(F);
1374   }
1375
1376   return Changed;
1377 }
1378
1379 bool BBPassManager::doFinalization(Function &F) {
1380   bool Changed = false;
1381
1382   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1383     BasicBlockPass *BP = getContainedPass(Index);
1384     Changed |= BP->doFinalization(F);
1385   }
1386
1387   return Changed;
1388 }
1389
1390
1391 //===----------------------------------------------------------------------===//
1392 // FunctionPassManager implementation
1393
1394 /// Create new Function pass manager
1395 FunctionPassManager::FunctionPassManager(Module *m) : M(m) {
1396   FPM = new FunctionPassManagerImpl();
1397   // FPM is the top level manager.
1398   FPM->setTopLevelManager(FPM);
1399
1400   AnalysisResolver *AR = new AnalysisResolver(*FPM);
1401   FPM->setResolver(AR);
1402 }
1403
1404 FunctionPassManager::~FunctionPassManager() {
1405   delete FPM;
1406 }
1407
1408 /// add - Add a pass to the queue of passes to run.  This passes
1409 /// ownership of the Pass to the PassManager.  When the
1410 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1411 /// there is no need to delete the pass. (TODO delete passes.)
1412 /// This implies that all passes MUST be allocated with 'new'.
1413 void FunctionPassManager::add(Pass *P) {
1414   FPM->add(P);
1415 }
1416
1417 /// run - Execute all of the passes scheduled for execution.  Keep
1418 /// track of whether any of the passes modifies the function, and if
1419 /// so, return true.
1420 ///
1421 bool FunctionPassManager::run(Function &F) {
1422   if (F.isMaterializable()) {
1423     std::string errstr;
1424     if (F.Materialize(&errstr))
1425       report_fatal_error("Error reading bitcode file: " + Twine(errstr));
1426   }
1427   return FPM->run(F);
1428 }
1429
1430
1431 /// doInitialization - Run all of the initializers for the function passes.
1432 ///
1433 bool FunctionPassManager::doInitialization() {
1434   return FPM->doInitialization(*M);
1435 }
1436
1437 /// doFinalization - Run all of the finalizers for the function passes.
1438 ///
1439 bool FunctionPassManager::doFinalization() {
1440   return FPM->doFinalization(*M);
1441 }
1442
1443 //===----------------------------------------------------------------------===//
1444 // FunctionPassManagerImpl implementation
1445 //
1446 bool FunctionPassManagerImpl::doInitialization(Module &M) {
1447   bool Changed = false;
1448
1449   dumpArguments();
1450   dumpPasses();
1451
1452   SmallVectorImpl<ImmutablePass *>& IPV = getImmutablePasses();
1453   for (SmallVectorImpl<ImmutablePass *>::const_iterator I = IPV.begin(),
1454        E = IPV.end(); I != E; ++I) {
1455     Changed |= (*I)->doInitialization(M);
1456   }
1457
1458   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1459     Changed |= getContainedManager(Index)->doInitialization(M);
1460
1461   return Changed;
1462 }
1463
1464 bool FunctionPassManagerImpl::doFinalization(Module &M) {
1465   bool Changed = false;
1466
1467   for (int Index = getNumContainedManagers() - 1; Index >= 0; --Index)
1468     Changed |= getContainedManager(Index)->doFinalization(M);
1469
1470   SmallVectorImpl<ImmutablePass *>& IPV = getImmutablePasses();
1471   for (SmallVectorImpl<ImmutablePass *>::const_iterator I = IPV.begin(),
1472        E = IPV.end(); I != E; ++I) {
1473     Changed |= (*I)->doFinalization(M);
1474   }
1475
1476   return Changed;
1477 }
1478
1479 /// cleanup - After running all passes, clean up pass manager cache.
1480 void FPPassManager::cleanup() {
1481  for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1482     FunctionPass *FP = getContainedPass(Index);
1483     AnalysisResolver *AR = FP->getResolver();
1484     assert(AR && "Analysis Resolver is not set");
1485     AR->clearAnalysisImpls();
1486  }
1487 }
1488
1489 void FunctionPassManagerImpl::releaseMemoryOnTheFly() {
1490   if (!wasRun)
1491     return;
1492   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1493     FPPassManager *FPPM = getContainedManager(Index);
1494     for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) {
1495       FPPM->getContainedPass(Index)->releaseMemory();
1496     }
1497   }
1498   wasRun = false;
1499 }
1500
1501 // Execute all the passes managed by this top level manager.
1502 // Return true if any function is modified by a pass.
1503 bool FunctionPassManagerImpl::run(Function &F) {
1504   bool Changed = false;
1505   TimingInfo::createTheTimeInfo();
1506
1507   initializeAllAnalysisInfo();
1508   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1509     Changed |= getContainedManager(Index)->runOnFunction(F);
1510
1511   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1512     getContainedManager(Index)->cleanup();
1513
1514   wasRun = true;
1515   return Changed;
1516 }
1517
1518 //===----------------------------------------------------------------------===//
1519 // FPPassManager implementation
1520
1521 char FPPassManager::ID = 0;
1522 /// Print passes managed by this manager
1523 void FPPassManager::dumpPassStructure(unsigned Offset) {
1524   dbgs().indent(Offset*2) << "FunctionPass Manager\n";
1525   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1526     FunctionPass *FP = getContainedPass(Index);
1527     FP->dumpPassStructure(Offset + 1);
1528     dumpLastUses(FP, Offset+1);
1529   }
1530 }
1531
1532
1533 /// Execute all of the passes scheduled for execution by invoking
1534 /// runOnFunction method.  Keep track of whether any of the passes modifies
1535 /// the function, and if so, return true.
1536 bool FPPassManager::runOnFunction(Function &F) {
1537   if (F.isDeclaration())
1538     return false;
1539
1540   bool Changed = false;
1541
1542   // Collect inherited analysis from Module level pass manager.
1543   populateInheritedAnalysis(TPM->activeStack);
1544
1545   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1546     FunctionPass *FP = getContainedPass(Index);
1547     bool LocalChanged = false;
1548
1549     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
1550     dumpRequiredSet(FP);
1551
1552     initializeAnalysisImpl(FP);
1553
1554     {
1555       PassManagerPrettyStackEntry X(FP, F);
1556       TimeRegion PassTimer(getPassTimer(FP));
1557
1558       LocalChanged |= FP->runOnFunction(F);
1559     }
1560
1561     Changed |= LocalChanged;
1562     if (LocalChanged)
1563       dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName());
1564     dumpPreservedSet(FP);
1565
1566     verifyPreservedAnalysis(FP);
1567     removeNotPreservedAnalysis(FP);
1568     recordAvailableAnalysis(FP);
1569     removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG);
1570   }
1571   return Changed;
1572 }
1573
1574 bool FPPassManager::runOnModule(Module &M) {
1575   bool Changed = false;
1576
1577   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1578     Changed |= runOnFunction(*I);
1579
1580   return Changed;
1581 }
1582
1583 bool FPPassManager::doInitialization(Module &M) {
1584   bool Changed = false;
1585
1586   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1587     Changed |= getContainedPass(Index)->doInitialization(M);
1588
1589   return Changed;
1590 }
1591
1592 bool FPPassManager::doFinalization(Module &M) {
1593   bool Changed = false;
1594
1595   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1596     Changed |= getContainedPass(Index)->doFinalization(M);
1597
1598   return Changed;
1599 }
1600
1601 //===----------------------------------------------------------------------===//
1602 // MPPassManager implementation
1603
1604 /// Execute all of the passes scheduled for execution by invoking
1605 /// runOnModule method.  Keep track of whether any of the passes modifies
1606 /// the module, and if so, return true.
1607 bool
1608 MPPassManager::runOnModule(Module &M) {
1609   bool Changed = false;
1610
1611   // Initialize on-the-fly passes
1612   for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
1613        I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
1614        I != E; ++I) {
1615     FunctionPassManagerImpl *FPP = I->second;
1616     Changed |= FPP->doInitialization(M);
1617   }
1618
1619   // Initialize module passes
1620   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
1621     Changed |= getContainedPass(Index)->doInitialization(M);
1622
1623   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1624     ModulePass *MP = getContainedPass(Index);
1625     bool LocalChanged = false;
1626
1627     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
1628     dumpRequiredSet(MP);
1629
1630     initializeAnalysisImpl(MP);
1631
1632     {
1633       PassManagerPrettyStackEntry X(MP, M);
1634       TimeRegion PassTimer(getPassTimer(MP));
1635
1636       LocalChanged |= MP->runOnModule(M);
1637     }
1638
1639     Changed |= LocalChanged;
1640     if (LocalChanged)
1641       dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG,
1642                    M.getModuleIdentifier());
1643     dumpPreservedSet(MP);
1644
1645     verifyPreservedAnalysis(MP);
1646     removeNotPreservedAnalysis(MP);
1647     recordAvailableAnalysis(MP);
1648     removeDeadPasses(MP, M.getModuleIdentifier(), ON_MODULE_MSG);
1649   }
1650
1651   // Finalize module passes
1652   for (int Index = getNumContainedPasses() - 1; Index >= 0; --Index)
1653     Changed |= getContainedPass(Index)->doFinalization(M);
1654
1655   // Finalize on-the-fly passes
1656   for (std::map<Pass *, FunctionPassManagerImpl *>::iterator
1657        I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end();
1658        I != E; ++I) {
1659     FunctionPassManagerImpl *FPP = I->second;
1660     // We don't know when is the last time an on-the-fly pass is run,
1661     // so we need to releaseMemory / finalize here
1662     FPP->releaseMemoryOnTheFly();
1663     Changed |= FPP->doFinalization(M);
1664   }
1665
1666   return Changed;
1667 }
1668
1669 /// Add RequiredPass into list of lower level passes required by pass P.
1670 /// RequiredPass is run on the fly by Pass Manager when P requests it
1671 /// through getAnalysis interface.
1672 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
1673   assert(P->getPotentialPassManagerType() == PMT_ModulePassManager &&
1674          "Unable to handle Pass that requires lower level Analysis pass");
1675   assert((P->getPotentialPassManagerType() <
1676           RequiredPass->getPotentialPassManagerType()) &&
1677          "Unable to handle Pass that requires lower level Analysis pass");
1678
1679   FunctionPassManagerImpl *FPP = OnTheFlyManagers[P];
1680   if (!FPP) {
1681     FPP = new FunctionPassManagerImpl();
1682     // FPP is the top level manager.
1683     FPP->setTopLevelManager(FPP);
1684
1685     OnTheFlyManagers[P] = FPP;
1686   }
1687   FPP->add(RequiredPass);
1688
1689   // Register P as the last user of RequiredPass.
1690   if (RequiredPass) {
1691     SmallVector<Pass *, 1> LU;
1692     LU.push_back(RequiredPass);
1693     FPP->setLastUser(LU,  P);
1694   }
1695 }
1696
1697 /// Return function pass corresponding to PassInfo PI, that is
1698 /// required by module pass MP. Instantiate analysis pass, by using
1699 /// its runOnFunction() for function F.
1700 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, AnalysisID PI, Function &F){
1701   FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP];
1702   assert(FPP && "Unable to find on the fly pass");
1703
1704   FPP->releaseMemoryOnTheFly();
1705   FPP->run(F);
1706   return ((PMTopLevelManager*)FPP)->findAnalysisPass(PI);
1707 }
1708
1709
1710 //===----------------------------------------------------------------------===//
1711 // PassManagerImpl implementation
1712
1713 //
1714 /// run - Execute all of the passes scheduled for execution.  Keep track of
1715 /// whether any of the passes modifies the module, and if so, return true.
1716 bool PassManagerImpl::run(Module &M) {
1717   bool Changed = false;
1718   TimingInfo::createTheTimeInfo();
1719
1720   dumpArguments();
1721   dumpPasses();
1722
1723   SmallVectorImpl<ImmutablePass *>& IPV = getImmutablePasses();
1724   for (SmallVectorImpl<ImmutablePass *>::const_iterator I = IPV.begin(),
1725        E = IPV.end(); I != E; ++I) {
1726     Changed |= (*I)->doInitialization(M);
1727   }
1728
1729   initializeAllAnalysisInfo();
1730   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
1731     Changed |= getContainedManager(Index)->runOnModule(M);
1732
1733   for (SmallVectorImpl<ImmutablePass *>::const_iterator I = IPV.begin(),
1734        E = IPV.end(); I != E; ++I) {
1735     Changed |= (*I)->doFinalization(M);
1736   }
1737
1738   return Changed;
1739 }
1740
1741 //===----------------------------------------------------------------------===//
1742 // PassManager implementation
1743
1744 /// Create new pass manager
1745 PassManager::PassManager() {
1746   PM = new PassManagerImpl();
1747   // PM is the top level manager
1748   PM->setTopLevelManager(PM);
1749 }
1750
1751 PassManager::~PassManager() {
1752   delete PM;
1753 }
1754
1755 /// add - Add a pass to the queue of passes to run.  This passes ownership of
1756 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
1757 /// will be destroyed as well, so there is no need to delete the pass.  This
1758 /// implies that all passes MUST be allocated with 'new'.
1759 void PassManager::add(Pass *P) {
1760   PM->add(P);
1761 }
1762
1763 /// run - Execute all of the passes scheduled for execution.  Keep track of
1764 /// whether any of the passes modifies the module, and if so, return true.
1765 bool PassManager::run(Module &M) {
1766   return PM->run(M);
1767 }
1768
1769 //===----------------------------------------------------------------------===//
1770 // TimingInfo implementation
1771
1772 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1773 // a non null value (if the -time-passes option is enabled) or it leaves it
1774 // null.  It may be called multiple times.
1775 void TimingInfo::createTheTimeInfo() {
1776   if (!TimePassesIsEnabled || TheTimeInfo) return;
1777
1778   // Constructed the first time this is called, iff -time-passes is enabled.
1779   // This guarantees that the object will be constructed before static globals,
1780   // thus it will be destroyed before them.
1781   static ManagedStatic<TimingInfo> TTI;
1782   TheTimeInfo = &*TTI;
1783 }
1784
1785 /// If TimingInfo is enabled then start pass timer.
1786 Timer *llvm::getPassTimer(Pass *P) {
1787   if (TheTimeInfo)
1788     return TheTimeInfo->getPassTimer(P);
1789   return 0;
1790 }
1791
1792 //===----------------------------------------------------------------------===//
1793 // PMStack implementation
1794 //
1795
1796 // Pop Pass Manager from the stack and clear its analysis info.
1797 void PMStack::pop() {
1798
1799   PMDataManager *Top = this->top();
1800   Top->initializeAnalysisInfo();
1801
1802   S.pop_back();
1803 }
1804
1805 // Push PM on the stack and set its top level manager.
1806 void PMStack::push(PMDataManager *PM) {
1807   assert(PM && "Unable to push. Pass Manager expected");
1808   assert(PM->getDepth()==0 && "Pass Manager depth set too early");
1809
1810   if (!this->empty()) {
1811     assert(PM->getPassManagerType() > this->top()->getPassManagerType()
1812            && "pushing bad pass manager to PMStack");
1813     PMTopLevelManager *TPM = this->top()->getTopLevelManager();
1814
1815     assert(TPM && "Unable to find top level manager");
1816     TPM->addIndirectPassManager(PM);
1817     PM->setTopLevelManager(TPM);
1818     PM->setDepth(this->top()->getDepth()+1);
1819   } else {
1820     assert((PM->getPassManagerType() == PMT_ModulePassManager
1821            || PM->getPassManagerType() == PMT_FunctionPassManager)
1822            && "pushing bad pass manager to PMStack");
1823     PM->setDepth(1);
1824   }
1825
1826   S.push_back(PM);
1827 }
1828
1829 // Dump content of the pass manager stack.
1830 void PMStack::dump() const {
1831   for (std::vector<PMDataManager *>::const_iterator I = S.begin(),
1832          E = S.end(); I != E; ++I)
1833     dbgs() << (*I)->getAsPass()->getPassName() << ' ';
1834
1835   if (!S.empty())
1836     dbgs() << '\n';
1837 }
1838
1839 /// Find appropriate Module Pass Manager in the PM Stack and
1840 /// add self into that manager.
1841 void ModulePass::assignPassManager(PMStack &PMS,
1842                                    PassManagerType PreferredType) {
1843   // Find Module Pass Manager
1844   while (!PMS.empty()) {
1845     PassManagerType TopPMType = PMS.top()->getPassManagerType();
1846     if (TopPMType == PreferredType)
1847       break; // We found desired pass manager
1848     else if (TopPMType > PMT_ModulePassManager)
1849       PMS.pop();    // Pop children pass managers
1850     else
1851       break;
1852   }
1853   assert(!PMS.empty() && "Unable to find appropriate Pass Manager");
1854   PMS.top()->add(this);
1855 }
1856
1857 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1858 /// in the PM Stack and add self into that manager.
1859 void FunctionPass::assignPassManager(PMStack &PMS,
1860                                      PassManagerType PreferredType) {
1861
1862   // Find Function Pass Manager
1863   while (!PMS.empty()) {
1864     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1865       PMS.pop();
1866     else
1867       break;
1868   }
1869
1870   // Create new Function Pass Manager if needed.
1871   FPPassManager *FPP;
1872   if (PMS.top()->getPassManagerType() == PMT_FunctionPassManager) {
1873     FPP = (FPPassManager *)PMS.top();
1874   } else {
1875     assert(!PMS.empty() && "Unable to create Function Pass Manager");
1876     PMDataManager *PMD = PMS.top();
1877
1878     // [1] Create new Function Pass Manager
1879     FPP = new FPPassManager();
1880     FPP->populateInheritedAnalysis(PMS);
1881
1882     // [2] Set up new manager's top level manager
1883     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1884     TPM->addIndirectPassManager(FPP);
1885
1886     // [3] Assign manager to manage this new manager. This may create
1887     // and push new managers into PMS
1888     FPP->assignPassManager(PMS, PMD->getPassManagerType());
1889
1890     // [4] Push new manager into PMS
1891     PMS.push(FPP);
1892   }
1893
1894   // Assign FPP as the manager of this pass.
1895   FPP->add(this);
1896 }
1897
1898 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1899 /// in the PM Stack and add self into that manager.
1900 void BasicBlockPass::assignPassManager(PMStack &PMS,
1901                                        PassManagerType PreferredType) {
1902   BBPassManager *BBP;
1903
1904   // Basic Pass Manager is a leaf pass manager. It does not handle
1905   // any other pass manager.
1906   if (!PMS.empty() &&
1907       PMS.top()->getPassManagerType() == PMT_BasicBlockPassManager) {
1908     BBP = (BBPassManager *)PMS.top();
1909   } else {
1910     // If leaf manager is not Basic Block Pass manager then create new
1911     // basic Block Pass manager.
1912     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1913     PMDataManager *PMD = PMS.top();
1914
1915     // [1] Create new Basic Block Manager
1916     BBP = new BBPassManager();
1917
1918     // [2] Set up new manager's top level manager
1919     // Basic Block Pass Manager does not live by itself
1920     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1921     TPM->addIndirectPassManager(BBP);
1922
1923     // [3] Assign manager to manage this new manager. This may create
1924     // and push new managers into PMS
1925     BBP->assignPassManager(PMS, PreferredType);
1926
1927     // [4] Push new manager into PMS
1928     PMS.push(BBP);
1929   }
1930
1931   // Assign BBP as the manager of this pass.
1932   BBP->add(this);
1933 }
1934
1935 PassManagerBase::~PassManagerBase() {}