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