lib/VMCore/PassManager.cpp

   1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source 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/Support/CommandLine.h"
  17 #include "llvm/Support/Timer.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/ModuleProvider.h"
  20 #include "llvm/Support/Streams.h"
  21 #include "llvm/Support/ManagedStatic.h"
  22 #include <vector>
  23 #include <map>
  24
  25 // See PassManagers.h for Pass Manager infrastructure overview.
  26
  27 namespace llvm {
  28
  29 //===----------------------------------------------------------------------===//
  30 // Pass debugging information.  Often it is useful to find out what pass is
  31 // running when a crash occurs in a utility.  When this library is compiled with
  32 // debugging on, a command line option (--debug-pass) is enabled that causes the
  33 // pass name to be printed before it executes.
  34 //
  35
  36 // Different debug levels that can be enabled...
  37 enum PassDebugLevel {
  38   None, Arguments, Structure, Executions, Details
  39 };
  40
  41 static cl::opt<enum PassDebugLevel>
  42 PassDebugging("debug-pass", cl::Hidden,
  43                   cl::desc("Print PassManager debugging information"),
  44                   cl::values(
  45   clEnumVal(None      , "disable debug output"),
  46   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
  47   clEnumVal(Structure , "print pass structure before run()"),
  48   clEnumVal(Executions, "print pass name before it is executed"),
  49   clEnumVal(Details   , "print pass details when it is executed"),
  50                              clEnumValEnd));
  51 } // End of llvm namespace
  52
  53 namespace {
  54
  55 //===----------------------------------------------------------------------===//
  56 // BBPassManager
  57 //
  58 /// BBPassManager manages BasicBlockPass. It batches all the
  59 /// pass together and sequence them to process one basic block before
  60 /// processing next basic block.
  61 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager,
  62                                         public FunctionPass {
  63
  64 public:
  65   BBPassManager(int Depth) : PMDataManager(Depth) { }
  66
  67   /// Execute all of the passes scheduled for execution.  Keep track of
  68   /// whether any of the passes modifies the function, and if so, return true.
  69   bool runOnFunction(Function &F);
  70
  71   /// Pass Manager itself does not invalidate any analysis info.
  72   void getAnalysisUsage(AnalysisUsage &Info) const {
  73     Info.setPreservesAll();
  74   }
  75
  76   bool doInitialization(Module &M);
  77   bool doInitialization(Function &F);
  78   bool doFinalization(Module &M);
  79   bool doFinalization(Function &F);
  80
  81   virtual const char *getPassName() const {
  82     return "BasicBlock Pass  Manager";
  83   }
  84
  85   // Print passes managed by this manager
  86   void dumpPassStructure(unsigned Offset) {
  87     llvm::cerr << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n";
  88     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
  89       BasicBlockPass *BP = getContainedPass(Index);
  90       BP->dumpPassStructure(Offset + 1);
  91       dumpLastUses(BP, Offset+1);
  92     }
  93   }
  94
  95   BasicBlockPass *getContainedPass(unsigned N) {
  96     assert ( N < PassVector.size() && "Pass number out of range!");
  97     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
  98     return BP;
  99   }
 100
 101   virtual PassManagerType getPassManagerType() {
 102     return PMT_BasicBlockPassManager;
 103   }
 104 };
 105
 106 }
 107
 108 namespace llvm {
 109
 110 //===----------------------------------------------------------------------===//
 111 // FunctionPassManagerImpl
 112 //
 113 /// FunctionPassManagerImpl manages FPPassManagers
 114 class FunctionPassManagerImpl : public Pass,
 115                                 public PMDataManager,
 116                                 public PMTopLevelManager {
 117 public:
 118
 119   FunctionPassManagerImpl(int Depth) : PMDataManager(Depth),
 120                                        PMTopLevelManager(TLM_Function) { }
 121
 122   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 123   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 124   /// will be destroyed as well, so there is no need to delete the pass.  This
 125   /// implies that all passes MUST be allocated with 'new'.
 126   void add(Pass *P) {
 127     schedulePass(P);
 128   }
 129
 130   /// run - Execute all of the passes scheduled for execution.  Keep track of
 131   /// whether any of the passes modifies the module, and if so, return true.
 132   bool run(Function &F);
 133
 134   /// doInitialization - Run all of the initializers for the function passes.
 135   ///
 136   bool doInitialization(Module &M);
 137
 138   /// doFinalization - Run all of the initializers for the function passes.
 139   ///
 140   bool doFinalization(Module &M);
 141
 142   /// Pass Manager itself does not invalidate any analysis info.
 143   void getAnalysisUsage(AnalysisUsage &Info) const {
 144     Info.setPreservesAll();
 145   }
 146
 147   inline void addTopLevelPass(Pass *P) {
 148
 149     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
 150
 151       // P is a immutable pass and it will be managed by this
 152       // top level manager. Set up analysis resolver to connect them.
 153       AnalysisResolver *AR = new AnalysisResolver(*this);
 154       P->setResolver(AR);
 155       initializeAnalysisImpl(P);
 156       addImmutablePass(IP);
 157       recordAvailableAnalysis(IP);
 158     } else {
 159       P->assignPassManager(activeStack);
 160     }
 161
 162   }
 163
 164   FPPassManager *getContainedManager(unsigned N) {
 165     assert ( N < PassManagers.size() && "Pass number out of range!");
 166     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
 167     return FP;
 168   }
 169
 170 };
 171
 172 //===----------------------------------------------------------------------===//
 173 // MPPassManager
 174 //
 175 /// MPPassManager manages ModulePasses and function pass managers.
 176 /// It batches all Module passes  passes and function pass managers together and
 177 /// sequence them to process one module.
 178 class MPPassManager : public Pass, public PMDataManager {
 179
 180 public:
 181   MPPassManager(int Depth) : PMDataManager(Depth) { }
 182
 183   /// run - Execute all of the passes scheduled for execution.  Keep track of
 184   /// whether any of the passes modifies the module, and if so, return true.
 185   bool runOnModule(Module &M);
 186
 187   /// Pass Manager itself does not invalidate any analysis info.
 188   void getAnalysisUsage(AnalysisUsage &Info) const {
 189     Info.setPreservesAll();
 190   }
 191
 192   virtual const char *getPassName() const {
 193     return "Module Pass Manager";
 194   }
 195
 196   // Print passes managed by this manager
 197   void dumpPassStructure(unsigned Offset) {
 198     llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
 199     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 200       ModulePass *MP = getContainedPass(Index);
 201       MP->dumpPassStructure(Offset + 1);
 202       dumpLastUses(MP, Offset+1);
 203     }
 204   }
 205
 206   ModulePass *getContainedPass(unsigned N) {
 207     assert ( N < PassVector.size() && "Pass number out of range!");
 208     ModulePass *MP = static_cast<ModulePass *>(PassVector[N]);
 209     return MP;
 210   }
 211
 212   virtual PassManagerType getPassManagerType() { return PMT_ModulePassManager; }
 213 };
 214
 215 //===----------------------------------------------------------------------===//
 216 // PassManagerImpl
 217 //
 218 /// PassManagerImpl manages MPPassManagers
 219 class PassManagerImpl : public Pass,
 220                         public PMDataManager,
 221                         public PMTopLevelManager {
 222
 223 public:
 224
 225   PassManagerImpl(int Depth) : PMDataManager(Depth),
 226                                PMTopLevelManager(TLM_Pass) { }
 227
 228   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 229   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 230   /// will be destroyed as well, so there is no need to delete the pass.  This
 231   /// implies that all passes MUST be allocated with 'new'.
 232   void add(Pass *P) {
 233     schedulePass(P);
 234   }
 235
 236   /// run - Execute all of the passes scheduled for execution.  Keep track of
 237   /// whether any of the passes modifies the module, and if so, return true.
 238   bool run(Module &M);
 239
 240   /// Pass Manager itself does not invalidate any analysis info.
 241   void getAnalysisUsage(AnalysisUsage &Info) const {
 242     Info.setPreservesAll();
 243   }
 244
 245   inline void addTopLevelPass(Pass *P) {
 246
 247     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
 248
 249       // P is a immutable pass and it will be managed by this
 250       // top level manager. Set up analysis resolver to connect them.
 251       AnalysisResolver *AR = new AnalysisResolver(*this);
 252       P->setResolver(AR);
 253       initializeAnalysisImpl(P);
 254       addImmutablePass(IP);
 255       recordAvailableAnalysis(IP);
 256     } else {
 257       P->assignPassManager(activeStack);
 258     }
 259
 260   }
 261
 262   MPPassManager *getContainedManager(unsigned N) {
 263     assert ( N < PassManagers.size() && "Pass number out of range!");
 264     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
 265     return MP;
 266   }
 267
 268 };
 269
 270 } // End of llvm namespace
 271
 272 namespace {
 273
 274 //===----------------------------------------------------------------------===//
 275 // TimingInfo Class - This class is used to calculate information about the
 276 // amount of time each pass takes to execute.  This only happens when
 277 // -time-passes is enabled on the command line.
 278 //
 279
 280 class VISIBILITY_HIDDEN TimingInfo {
 281   std::map<Pass*, Timer> TimingData;
 282   TimerGroup TG;
 283
 284 public:
 285   // Use 'create' member to get this.
 286   TimingInfo() : TG("... Pass execution timing report ...") {}
 287
 288   // TimingDtor - Print out information about timing information
 289   ~TimingInfo() {
 290     // Delete all of the timers...
 291     TimingData.clear();
 292     // TimerGroup is deleted next, printing the report.
 293   }
 294
 295   // createTheTimeInfo - This method either initializes the TheTimeInfo pointer
 296   // to a non null value (if the -time-passes option is enabled) or it leaves it
 297   // null.  It may be called multiple times.
 298   static void createTheTimeInfo();
 299
 300   void passStarted(Pass *P) {
 301
 302     if (dynamic_cast<PMDataManager *>(P))
 303       return;
 304
 305     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
 306     if (I == TimingData.end())
 307       I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first;
 308     I->second.startTimer();
 309   }
 310   void passEnded(Pass *P) {
 311
 312     if (dynamic_cast<PMDataManager *>(P))
 313       return;
 314
 315     std::map<Pass*, Timer>::iterator I = TimingData.find(P);
 316     assert (I != TimingData.end() && "passStarted/passEnded not nested right!");
 317     I->second.stopTimer();
 318   }
 319 };
 320
 321 static TimingInfo *TheTimeInfo;
 322
 323 } // End of anon namespace
 324
 325 //===----------------------------------------------------------------------===//
 326 // PMTopLevelManager implementation
 327
 328 /// Initialize top level manager. Create first pass manager.
 329 PMTopLevelManager::PMTopLevelManager (enum TopLevelManagerType t) {
 330
 331   if (t == TLM_Pass) {
 332     MPPassManager *MPP = new MPPassManager(1);
 333     MPP->setTopLevelManager(this);
 334     addPassManager(MPP);
 335     activeStack.push(MPP);
 336   }
 337   else if (t == TLM_Function) {
 338     FPPassManager *FPP = new FPPassManager(1);
 339     FPP->setTopLevelManager(this);
 340     addPassManager(FPP);
 341     activeStack.push(FPP);
 342   }
 343 }
 344
 345 /// Set pass P as the last user of the given analysis passes.
 346 void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses,
 347                                     Pass *P) {
 348
 349   for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(),
 350          E = AnalysisPasses.end(); I != E; ++I) {
 351     Pass *AP = *I;
 352     LastUser[AP] = P;
 353     // If AP is the last user of other passes then make P last user of
 354     // such passes.
 355     for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
 356            LUE = LastUser.end(); LUI != LUE; ++LUI) {
 357       if (LUI->second == AP)
 358         LastUser[LUI->first] = P;
 359     }
 360   }
 361 }
 362
 363 /// Collect passes whose last user is P
 364 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses,
 365                                             Pass *P) {
 366    for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
 367           LUE = LastUser.end(); LUI != LUE; ++LUI)
 368       if (LUI->second == P)
 369         LastUses.push_back(LUI->first);
 370 }
 371
 372 /// Schedule pass P for execution. Make sure that passes required by
 373 /// P are run before P is run. Update analysis info maintained by
 374 /// the manager. Remove dead passes. This is a recursive function.
 375 void PMTopLevelManager::schedulePass(Pass *P) {
 376
 377   // TODO : Allocate function manager for this pass, other wise required set
 378   // may be inserted into previous function manager
 379
 380   AnalysisUsage AnUsage;
 381   P->getAnalysisUsage(AnUsage);
 382   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 383   for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
 384          E = RequiredSet.end(); I != E; ++I) {
 385
 386     Pass *AnalysisPass = findAnalysisPass(*I);
 387     if (!AnalysisPass) {
 388       // Schedule this analysis run first.
 389       AnalysisPass = (*I)->createPass();
 390       schedulePass(AnalysisPass);
 391     }
 392   }
 393
 394   // Now all required passes are available.
 395   addTopLevelPass(P);
 396 }
 397
 398 /// Find the pass that implements Analysis AID. Search immutable
 399 /// passes and all pass managers. If desired pass is not found
 400 /// then return NULL.
 401 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
 402
 403   Pass *P = NULL;
 404   // Check pass managers
 405   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 406          E = PassManagers.end(); P == NULL && I != E; ++I) {
 407     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 408     assert(PMD && "This is not a PassManager");
 409     P = PMD->findAnalysisPass(AID, false);
 410   }
 411
 412   // Check other pass managers
 413   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
 414          E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
 415     P = (*I)->findAnalysisPass(AID, false);
 416
 417   for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(),
 418          E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
 419     const PassInfo *PI = (*I)->getPassInfo();
 420     if (PI == AID)
 421       P = *I;
 422
 423     // If Pass not found then check the interfaces implemented by Immutable Pass
 424     if (!P) {
 425       const std::vector<const PassInfo*> &ImmPI = PI->getInterfacesImplemented();
 426       if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end())
 427         P = *I;
 428     }
 429   }
 430
 431   return P;
 432 }
 433
 434 // Print passes managed by this top level manager.
 435 void PMTopLevelManager::dumpPasses() const {
 436
 437   if (PassDebugging < Structure)
 438     return;
 439
 440   // Print out the immutable passes
 441   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
 442     ImmutablePasses[i]->dumpPassStructure(0);
 443   }
 444
 445   for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
 446          E = PassManagers.end(); I != E; ++I)
 447     (*I)->dumpPassStructure(1);
 448 }
 449
 450 void PMTopLevelManager::dumpArguments() const {
 451
 452   if (PassDebugging < Arguments)
 453     return;
 454
 455   cerr << "Pass Arguments: ";
 456   for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
 457          E = PassManagers.end(); I != E; ++I) {
 458     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 459     assert(PMD && "This is not a PassManager");
 460     PMD->dumpPassArguments();
 461   }
 462   cerr << "\n";
 463 }
 464
 465 void PMTopLevelManager::initializeAllAnalysisInfo() {
 466
 467   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 468          E = PassManagers.end(); I != E; ++I) {
 469     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 470     assert(PMD && "This is not a PassManager");
 471     PMD->initializeAnalysisInfo();
 472   }
 473
 474   // Initailize other pass managers
 475   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
 476          E = IndirectPassManagers.end(); I != E; ++I)
 477     (*I)->initializeAnalysisInfo();
 478 }
 479
 480 /// Destructor
 481 PMTopLevelManager::~PMTopLevelManager() {
 482   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 483          E = PassManagers.end(); I != E; ++I)
 484     delete *I;
 485
 486   for (std::vector<ImmutablePass *>::iterator
 487          I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
 488     delete *I;
 489
 490   PassManagers.clear();
 491 }
 492
 493 //===----------------------------------------------------------------------===//
 494 // PMDataManager implementation
 495
 496 /// Return true IFF pass P's required analysis set does not required new
 497 /// manager.
 498 bool PMDataManager::manageablePass(Pass *P) {
 499
 500   // TODO
 501   // If this pass is not preserving information that is required by a
 502   // pass maintained by higher level pass manager then do not insert
 503   // this pass into current manager. Use new manager. For example,
 504   // For example, If FunctionPass F is not preserving ModulePass Info M1
 505   // that is used by another ModulePass M2 then do not insert F in
 506   // current function pass manager.
 507   return true;
 508 }
 509
 510 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 511 void PMDataManager::recordAvailableAnalysis(Pass *P) {
 512
 513   if (const PassInfo *PI = P->getPassInfo()) {
 514     AvailableAnalysis[PI] = P;
 515
 516     //This pass is the current implementation of all of the interfaces it
 517     //implements as well.
 518     const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
 519     for (unsigned i = 0, e = II.size(); i != e; ++i)
 520       AvailableAnalysis[II[i]] = P;
 521   }
 522 }
 523
 524 /// Remove Analyss not preserved by Pass P
 525 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
 526   AnalysisUsage AnUsage;
 527   P->getAnalysisUsage(AnUsage);
 528
 529   if (AnUsage.getPreservesAll())
 530     return;
 531
 532   const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 533   for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
 534          E = AvailableAnalysis.end(); I != E; ) {
 535     std::map<AnalysisID, Pass*>::iterator Info = I++;
 536     if (std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
 537         PreservedSet.end()) {
 538       // Remove this analysis
 539       if (!dynamic_cast<ImmutablePass*>(Info->second))
 540         AvailableAnalysis.erase(Info);
 541     }
 542   }
 543 }
 544
 545 /// Remove analysis passes that are not used any longer
 546 void PMDataManager::removeDeadPasses(Pass *P, std::string &Msg) {
 547
 548   std::vector<Pass *> DeadPasses;
 549   TPM->collectLastUses(DeadPasses, P);
 550
 551   for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
 552          E = DeadPasses.end(); I != E; ++I) {
 553
 554     std::string Msg1 = "  Freeing Pass '";
 555     dumpPassInfo(*I, Msg1, Msg);
 556
 557     if (TheTimeInfo) TheTimeInfo->passStarted(P);
 558     (*I)->releaseMemory();
 559     if (TheTimeInfo) TheTimeInfo->passEnded(P);
 560
 561     std::map<AnalysisID, Pass*>::iterator Pos =
 562       AvailableAnalysis.find((*I)->getPassInfo());
 563
 564     // It is possible that pass is already removed from the AvailableAnalysis
 565     if (Pos != AvailableAnalysis.end())
 566       AvailableAnalysis.erase(Pos);
 567   }
 568 }
 569
 570 /// Add pass P into the PassVector. Update
 571 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 572 void PMDataManager::add(Pass *P,
 573                         bool ProcessAnalysis) {
 574
 575   // This manager is going to manage pass P. Set up analysis resolver
 576   // to connect them.
 577   AnalysisResolver *AR = new AnalysisResolver(*this);
 578   P->setResolver(AR);
 579
 580   if (ProcessAnalysis) {
 581
 582     // At the moment, this pass is the last user of all required passes.
 583     std::vector<Pass *> LastUses;
 584     std::vector<Pass *> RequiredPasses;
 585     unsigned PDepth = this->getDepth();
 586
 587     collectRequiredAnalysisPasses(RequiredPasses, P);
 588     for (std::vector<Pass *>::iterator I = RequiredPasses.begin(),
 589            E = RequiredPasses.end(); I != E; ++I) {
 590       Pass *PRequired = *I;
 591       unsigned RDepth = 0;
 592
 593       PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
 594       RDepth = DM.getDepth();
 595
 596       if (PDepth == RDepth)
 597         LastUses.push_back(PRequired);
 598       else if (PDepth >  RDepth) {
 599         // Let the parent claim responsibility of last use
 600         TransferLastUses.push_back(PRequired);
 601       } else {
 602         // Note : This feature is not yet implemented
 603         assert (0 &&
 604                 "Unable to handle Pass that requires lower level Analysis pass");
 605       }
 606     }
 607
 608     // Set P as P's last user until someone starts using P.
 609     // However, if P is a Pass Manager then it does not need
 610     // to record its last user.
 611     if (!dynamic_cast<PMDataManager *>(P))
 612       LastUses.push_back(P);
 613     TPM->setLastUser(LastUses, P);
 614
 615     // Take a note of analysis required and made available by this pass.
 616     // Remove the analysis not preserved by this pass
 617     removeNotPreservedAnalysis(P);
 618     recordAvailableAnalysis(P);
 619   }
 620
 621   // Add pass
 622   PassVector.push_back(P);
 623 }
 624
 625 /// Populate RequiredPasses with the analysis pass that are required by
 626 /// pass P.
 627 void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP,
 628                                                   Pass *P) {
 629   AnalysisUsage AnUsage;
 630   P->getAnalysisUsage(AnUsage);
 631   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 632   for (std::vector<AnalysisID>::const_iterator
 633          I = RequiredSet.begin(), E = RequiredSet.end();
 634        I != E; ++I) {
 635     Pass *AnalysisPass = findAnalysisPass(*I, true);
 636     assert (AnalysisPass && "Analysis pass is not available");
 637     RP.push_back(AnalysisPass);
 638   }
 639
 640   const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
 641   for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
 642          E = IDs.end(); I != E; ++I) {
 643     Pass *AnalysisPass = findAnalysisPass(*I, true);
 644     assert (AnalysisPass && "Analysis pass is not available");
 645     RP.push_back(AnalysisPass);
 646   }
 647 }
 648
 649 // All Required analyses should be available to the pass as it runs!  Here
 650 // we fill in the AnalysisImpls member of the pass so that it can
 651 // successfully use the getAnalysis() method to retrieve the
 652 // implementations it needs.
 653 //
 654 void PMDataManager::initializeAnalysisImpl(Pass *P) {
 655   AnalysisUsage AnUsage;
 656   P->getAnalysisUsage(AnUsage);
 657
 658   for (std::vector<const PassInfo *>::const_iterator
 659          I = AnUsage.getRequiredSet().begin(),
 660          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
 661     Pass *Impl = findAnalysisPass(*I, true);
 662     if (Impl == 0)
 663       assert(0 && "Analysis used but not available!");
 664     AnalysisResolver *AR = P->getResolver();
 665     AR->addAnalysisImplsPair(*I, Impl);
 666   }
 667 }
 668
 669 /// Find the pass that implements Analysis AID. If desired pass is not found
 670 /// then return NULL.
 671 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
 672
 673   // Check if AvailableAnalysis map has one entry.
 674   std::map<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
 675
 676   if (I != AvailableAnalysis.end())
 677     return I->second;
 678
 679   // Search Parents through TopLevelManager
 680   if (SearchParent)
 681     return TPM->findAnalysisPass(AID);
 682
 683   return NULL;
 684 }
 685
 686 // Print list of passes that are last used by P.
 687 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
 688
 689   std::vector<Pass *> LUses;
 690
 691   assert (TPM && "Top Level Manager is missing");
 692   TPM->collectLastUses(LUses, P);
 693
 694   for (std::vector<Pass *>::iterator I = LUses.begin(),
 695          E = LUses.end(); I != E; ++I) {
 696     llvm::cerr << "--" << std::string(Offset*2, ' ');
 697     (*I)->dumpPassStructure(0);
 698   }
 699 }
 700
 701 void PMDataManager::dumpPassArguments() const {
 702   for(std::vector<Pass *>::const_iterator I = PassVector.begin(),
 703         E = PassVector.end(); I != E; ++I) {
 704     if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
 705       PMD->dumpPassArguments();
 706     else
 707       if (const PassInfo *PI = (*I)->getPassInfo())
 708         if (!PI->isAnalysisGroup())
 709           cerr << " -" << PI->getPassArgument();
 710   }
 711 }
 712
 713 void PMDataManager:: dumpPassInfo(Pass *P,  std::string &Msg1,
 714                                   std::string &Msg2) const {
 715   if (PassDebugging < Executions)
 716     return;
 717   cerr << (void*)this << std::string(getDepth()*2+1, ' ');
 718   cerr << Msg1;
 719   cerr << P->getPassName();
 720   cerr << Msg2;
 721 }
 722
 723 void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P,
 724                                         const std::vector<AnalysisID> &Set)
 725   const {
 726   if (PassDebugging >= Details && !Set.empty()) {
 727     cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
 728       for (unsigned i = 0; i != Set.size(); ++i) {
 729         if (i) cerr << ",";
 730         cerr << " " << Set[i]->getPassName();
 731       }
 732       cerr << "\n";
 733   }
 734 }
 735
 736 // Destructor
 737 PMDataManager::~PMDataManager() {
 738
 739   for (std::vector<Pass *>::iterator I = PassVector.begin(),
 740          E = PassVector.end(); I != E; ++I)
 741     delete *I;
 742
 743   PassVector.clear();
 744 }
 745
 746 //===----------------------------------------------------------------------===//
 747 // NOTE: Is this the right place to define this method ?
 748 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
 749 Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
 750   return PM.findAnalysisPass(ID, dir);
 751 }
 752
 753 //===----------------------------------------------------------------------===//
 754 // BBPassManager implementation
 755
 756 /// Execute all of the passes scheduled for execution by invoking
 757 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 758 /// the function, and if so, return true.
 759 bool
 760 BBPassManager::runOnFunction(Function &F) {
 761
 762   if (F.isDeclaration())
 763     return false;
 764
 765   bool Changed = doInitialization(F);
 766
 767   std::string Msg1 = "Executing Pass '";
 768   std::string Msg3 = "' Made Modification '";
 769
 770   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 771     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 772       BasicBlockPass *BP = getContainedPass(Index);
 773       AnalysisUsage AnUsage;
 774       BP->getAnalysisUsage(AnUsage);
 775
 776       std::string Msg2 = "' on BasicBlock '" + (*I).getName() + "'...\n";
 777       dumpPassInfo(BP, Msg1, Msg2);
 778       dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet());
 779
 780       initializeAnalysisImpl(BP);
 781
 782       if (TheTimeInfo) TheTimeInfo->passStarted(BP);
 783       Changed |= BP->runOnBasicBlock(*I);
 784       if (TheTimeInfo) TheTimeInfo->passEnded(BP);
 785
 786       if (Changed)
 787         dumpPassInfo(BP, Msg3, Msg2);
 788       dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet());
 789
 790       removeNotPreservedAnalysis(BP);
 791       recordAvailableAnalysis(BP);
 792       removeDeadPasses(BP, Msg2);
 793     }
 794   return Changed |= doFinalization(F);
 795 }
 796
 797 // Implement doInitialization and doFinalization
 798 inline bool BBPassManager::doInitialization(Module &M) {
 799   bool Changed = false;
 800
 801   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 802     BasicBlockPass *BP = getContainedPass(Index);
 803     Changed |= BP->doInitialization(M);
 804   }
 805
 806   return Changed;
 807 }
 808
 809 inline bool BBPassManager::doFinalization(Module &M) {
 810   bool Changed = false;
 811
 812   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 813     BasicBlockPass *BP = getContainedPass(Index);
 814     Changed |= BP->doFinalization(M);
 815   }
 816
 817   return Changed;
 818 }
 819
 820 inline bool BBPassManager::doInitialization(Function &F) {
 821   bool Changed = false;
 822
 823   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 824     BasicBlockPass *BP = getContainedPass(Index);
 825     Changed |= BP->doInitialization(F);
 826   }
 827
 828   return Changed;
 829 }
 830
 831 inline bool BBPassManager::doFinalization(Function &F) {
 832   bool Changed = false;
 833
 834   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 835     BasicBlockPass *BP = getContainedPass(Index);
 836     Changed |= BP->doFinalization(F);
 837   }
 838
 839   return Changed;
 840 }
 841
 842
 843 //===----------------------------------------------------------------------===//
 844 // FunctionPassManager implementation
 845
 846 /// Create new Function pass manager
 847 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
 848   FPM = new FunctionPassManagerImpl(0);
 849   // FPM is the top level manager.
 850   FPM->setTopLevelManager(FPM);
 851
 852   PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
 853   AnalysisResolver *AR = new AnalysisResolver(*PMD);
 854   FPM->setResolver(AR);
 855
 856   MP = P;
 857 }
 858
 859 FunctionPassManager::~FunctionPassManager() {
 860   delete FPM;
 861 }
 862
 863 /// add - Add a pass to the queue of passes to run.  This passes
 864 /// ownership of the Pass to the PassManager.  When the
 865 /// PassManager_X is destroyed, the pass will be destroyed as well, so
 866 /// there is no need to delete the pass. (TODO delete passes.)
 867 /// This implies that all passes MUST be allocated with 'new'.
 868 void FunctionPassManager::add(Pass *P) {
 869   FPM->add(P);
 870 }
 871
 872 /// run - Execute all of the passes scheduled for execution.  Keep
 873 /// track of whether any of the passes modifies the function, and if
 874 /// so, return true.
 875 ///
 876 bool FunctionPassManager::run(Function &F) {
 877   std::string errstr;
 878   if (MP->materializeFunction(&F, &errstr)) {
 879     cerr << "Error reading bytecode file: " << errstr << "\n";
 880     abort();
 881   }
 882   return FPM->run(F);
 883 }
 884
 885
 886 /// doInitialization - Run all of the initializers for the function passes.
 887 ///
 888 bool FunctionPassManager::doInitialization() {
 889   return FPM->doInitialization(*MP->getModule());
 890 }
 891
 892 /// doFinalization - Run all of the initializers for the function passes.
 893 ///
 894 bool FunctionPassManager::doFinalization() {
 895   return FPM->doFinalization(*MP->getModule());
 896 }
 897
 898 //===----------------------------------------------------------------------===//
 899 // FunctionPassManagerImpl implementation
 900 //
 901 inline bool FunctionPassManagerImpl::doInitialization(Module &M) {
 902   bool Changed = false;
 903
 904   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 905     FPPassManager *FP = getContainedManager(Index);
 906     Changed |= FP->doInitialization(M);
 907   }
 908
 909   return Changed;
 910 }
 911
 912 inline bool FunctionPassManagerImpl::doFinalization(Module &M) {
 913   bool Changed = false;
 914
 915   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 916     FPPassManager *FP = getContainedManager(Index);
 917     Changed |= FP->doFinalization(M);
 918   }
 919
 920   return Changed;
 921 }
 922
 923 // Execute all the passes managed by this top level manager.
 924 // Return true if any function is modified by a pass.
 925 bool FunctionPassManagerImpl::run(Function &F) {
 926
 927   bool Changed = false;
 928
 929   TimingInfo::createTheTimeInfo();
 930
 931   dumpArguments();
 932   dumpPasses();
 933
 934   initializeAllAnalysisInfo();
 935   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 936     FPPassManager *FP = getContainedManager(Index);
 937     Changed |= FP->runOnFunction(F);
 938   }
 939   return Changed;
 940 }
 941
 942 //===----------------------------------------------------------------------===//
 943 // FPPassManager implementation
 944
 945 /// Print passes managed by this manager
 946 void FPPassManager::dumpPassStructure(unsigned Offset) {
 947   llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
 948   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 949     FunctionPass *FP = getContainedPass(Index);
 950     FP->dumpPassStructure(Offset + 1);
 951     dumpLastUses(FP, Offset+1);
 952   }
 953 }
 954
 955
 956 /// Execute all of the passes scheduled for execution by invoking
 957 /// runOnFunction method.  Keep track of whether any of the passes modifies
 958 /// the function, and if so, return true.
 959 bool FPPassManager::runOnFunction(Function &F) {
 960
 961   bool Changed = false;
 962
 963   if (F.isDeclaration())
 964     return false;
 965
 966   std::string Msg1 = "Executing Pass '";
 967   std::string Msg3 = "' Made Modification '";
 968
 969   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 970     FunctionPass *FP = getContainedPass(Index);
 971
 972     AnalysisUsage AnUsage;
 973     FP->getAnalysisUsage(AnUsage);
 974
 975     std::string Msg2 = "' on Function '" + F.getName() + "'...\n";
 976     dumpPassInfo(FP, Msg1, Msg2);
 977     dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet());
 978
 979     initializeAnalysisImpl(FP);
 980
 981     if (TheTimeInfo) TheTimeInfo->passStarted(FP);
 982     Changed |= FP->runOnFunction(F);
 983     if (TheTimeInfo) TheTimeInfo->passEnded(FP);
 984
 985     if (Changed)
 986       dumpPassInfo(FP, Msg3, Msg2);
 987     dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet());
 988
 989     removeNotPreservedAnalysis(FP);
 990     recordAvailableAnalysis(FP);
 991     removeDeadPasses(FP, Msg2);
 992   }
 993   return Changed;
 994 }
 995
 996 bool FPPassManager::runOnModule(Module &M) {
 997
 998   bool Changed = doInitialization(M);
 999
1000   for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1001     this->runOnFunction(*I);
1002
1003   return Changed |= doFinalization(M);
1004 }
1005
1006 inline bool FPPassManager::doInitialization(Module &M) {
1007   bool Changed = false;
1008
1009   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1010     FunctionPass *FP = getContainedPass(Index);
1011     Changed |= FP->doInitialization(M);
1012   }
1013
1014   return Changed;
1015 }
1016
1017 inline bool FPPassManager::doFinalization(Module &M) {
1018   bool Changed = false;
1019
1020   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1021     FunctionPass *FP = getContainedPass(Index);
1022     Changed |= FP->doFinalization(M);
1023   }
1024
1025   return Changed;
1026 }
1027
1028 //===----------------------------------------------------------------------===//
1029 // MPPassManager implementation
1030
1031 /// Execute all of the passes scheduled for execution by invoking
1032 /// runOnModule method.  Keep track of whether any of the passes modifies
1033 /// the module, and if so, return true.
1034 bool
1035 MPPassManager::runOnModule(Module &M) {
1036   bool Changed = false;
1037
1038   std::string Msg1 = "Executing Pass '";
1039   std::string Msg3 = "' Made Modification '";
1040
1041   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1042     ModulePass *MP = getContainedPass(Index);
1043
1044     AnalysisUsage AnUsage;
1045     MP->getAnalysisUsage(AnUsage);
1046
1047     std::string Msg2 = "' on Module '" + M.getModuleIdentifier() + "'...\n";
1048     dumpPassInfo(MP, Msg1, Msg2);
1049     dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet());
1050
1051     initializeAnalysisImpl(MP);
1052
1053     if (TheTimeInfo) TheTimeInfo->passStarted(MP);
1054     Changed |= MP->runOnModule(M);
1055     if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1056
1057     if (Changed)
1058       dumpPassInfo(MP, Msg3, Msg2);
1059     dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet());
1060
1061     removeNotPreservedAnalysis(MP);
1062     recordAvailableAnalysis(MP);
1063     removeDeadPasses(MP, Msg2);
1064   }
1065   return Changed;
1066 }
1067
1068 //===----------------------------------------------------------------------===//
1069 // PassManagerImpl implementation
1070 //
1071 /// run - Execute all of the passes scheduled for execution.  Keep track of
1072 /// whether any of the passes modifies the module, and if so, return true.
1073 bool PassManagerImpl::run(Module &M) {
1074
1075   bool Changed = false;
1076
1077   TimingInfo::createTheTimeInfo();
1078
1079   dumpArguments();
1080   dumpPasses();
1081
1082   initializeAllAnalysisInfo();
1083   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1084     MPPassManager *MP = getContainedManager(Index);
1085     Changed |= MP->runOnModule(M);
1086   }
1087   return Changed;
1088 }
1089
1090 //===----------------------------------------------------------------------===//
1091 // PassManager implementation
1092
1093 /// Create new pass manager
1094 PassManager::PassManager() {
1095   PM = new PassManagerImpl(0);
1096   // PM is the top level manager
1097   PM->setTopLevelManager(PM);
1098 }
1099
1100 PassManager::~PassManager() {
1101   delete PM;
1102 }
1103
1104 /// add - Add a pass to the queue of passes to run.  This passes ownership of
1105 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
1106 /// will be destroyed as well, so there is no need to delete the pass.  This
1107 /// implies that all passes MUST be allocated with 'new'.
1108 void
1109 PassManager::add(Pass *P) {
1110   PM->add(P);
1111 }
1112
1113 /// run - Execute all of the passes scheduled for execution.  Keep track of
1114 /// whether any of the passes modifies the module, and if so, return true.
1115 bool
1116 PassManager::run(Module &M) {
1117   return PM->run(M);
1118 }
1119
1120 //===----------------------------------------------------------------------===//
1121 // TimingInfo Class - This class is used to calculate information about the
1122 // amount of time each pass takes to execute.  This only happens with
1123 // -time-passes is enabled on the command line.
1124 //
1125 bool llvm::TimePassesIsEnabled = false;
1126 static cl::opt<bool,true>
1127 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1128             cl::desc("Time each pass, printing elapsed time for each on exit"));
1129
1130 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1131 // a non null value (if the -time-passes option is enabled) or it leaves it
1132 // null.  It may be called multiple times.
1133 void TimingInfo::createTheTimeInfo() {
1134   if (!TimePassesIsEnabled || TheTimeInfo) return;
1135
1136   // Constructed the first time this is called, iff -time-passes is enabled.
1137   // This guarantees that the object will be constructed before static globals,
1138   // thus it will be destroyed before them.
1139   static ManagedStatic<TimingInfo> TTI;
1140   TheTimeInfo = &*TTI;
1141 }
1142
1143 /// If TimingInfo is enabled then start pass timer.
1144 void StartPassTimer(Pass *P) {
1145   if (TheTimeInfo)
1146     TheTimeInfo->passStarted(P);
1147 }
1148
1149 /// If TimingInfo is enabled then stop pass timer.
1150 void StopPassTimer(Pass *P) {
1151   if (TheTimeInfo)
1152     TheTimeInfo->passEnded(P);
1153 }
1154
1155 //===----------------------------------------------------------------------===//
1156 // PMStack implementation
1157 //
1158
1159 // Pop Pass Manager from the stack and clear its analysis info.
1160 void PMStack::pop() {
1161
1162   PMDataManager *Top = this->top();
1163   Top->initializeAnalysisInfo();
1164
1165   S.pop_back();
1166 }
1167
1168 // Push PM on the stack and set its top level manager.
1169 void PMStack::push(Pass *P) {
1170
1171   PMDataManager *Top = NULL;
1172   PMDataManager *PM = dynamic_cast<PMDataManager *>(P);
1173   assert (PM && "Unable to push. Pass Manager expected");
1174
1175   if (this->empty()) {
1176     Top = PM;
1177   }
1178   else {
1179     Top = this->top();
1180     PMTopLevelManager *TPM = Top->getTopLevelManager();
1181
1182     assert (TPM && "Unable to find top level manager");
1183     TPM->addIndirectPassManager(PM);
1184     PM->setTopLevelManager(TPM);
1185   }
1186
1187   AnalysisResolver *AR = new AnalysisResolver(*Top);
1188   P->setResolver(AR);
1189
1190   S.push_back(PM);
1191 }
1192
1193 // Dump content of the pass manager stack.
1194 void PMStack::dump() {
1195   for(std::deque<PMDataManager *>::iterator I = S.begin(),
1196         E = S.end(); I != E; ++I) {
1197     Pass *P = dynamic_cast<Pass *>(*I);
1198     printf ("%s ", P->getPassName());
1199   }
1200   if (!S.empty())
1201     printf ("\n");
1202 }
1203
1204 // Walk Pass Manager stack and set LastUse markers if any
1205 // manager is transfering this priviledge to its parent manager
1206 void PMStack::handleLastUserOverflow() {
1207
1208   for(PMStack::iterator I = this->begin(), E = this->end(); I != E;) {
1209
1210     PMDataManager *Child = *I++;
1211     if (I != E) {
1212       PMDataManager *Parent = *I++;
1213       PMTopLevelManager *TPM = Parent->getTopLevelManager();
1214       std::vector<Pass *> &TLU = Child->getTransferredLastUses();
1215       if (!TLU.empty()) {
1216         Pass *P = dynamic_cast<Pass *>(Parent);
1217         TPM->setLastUser(TLU, P);
1218       }
1219     }
1220   }
1221 }
1222
1223 /// Find appropriate Module Pass Manager in the PM Stack and
1224 /// add self into that manager.
1225 void ModulePass::assignPassManager(PMStack &PMS,
1226                                    PassManagerType PreferredType) {
1227
1228   // Find Module Pass Manager
1229   while(!PMS.empty()) {
1230     PassManagerType TopPMType = PMS.top()->getPassManagerType();
1231     if (TopPMType == PreferredType)
1232       break; // We found desired pass manager
1233     else if (TopPMType > PMT_ModulePassManager)
1234       PMS.pop();    // Pop children pass managers
1235     else
1236       break;
1237   }
1238
1239   PMS.top()->add(this);
1240 }
1241
1242 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1243 /// in the PM Stack and add self into that manager.
1244 void FunctionPass::assignPassManager(PMStack &PMS,
1245                                      PassManagerType PreferredType) {
1246
1247   // Find Module Pass Manager (TODO : Or Call Graph Pass Manager)
1248   while(!PMS.empty()) {
1249     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1250       PMS.pop();
1251     else
1252       break;
1253   }
1254   FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1255
1256   // Create new Function Pass Manager
1257   if (!FPP) {
1258     assert(!PMS.empty() && "Unable to create Function Pass Manager");
1259     PMDataManager *PMD = PMS.top();
1260
1261     // [1] Create new Function Pass Manager
1262     FPP = new FPPassManager(PMD->getDepth() + 1);
1263
1264     // [2] Set up new manager's top level manager
1265     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1266     TPM->addIndirectPassManager(FPP);
1267
1268     // [3] Assign manager to manage this new manager. This may create
1269     // and push new managers into PMS
1270     Pass *P = dynamic_cast<Pass *>(FPP);
1271
1272     // If Call Graph Pass Manager is active then use it to manage
1273     // this new Function Pass manager.
1274     if (PMD->getPassManagerType() == PMT_CallGraphPassManager)
1275       P->assignPassManager(PMS, PMT_CallGraphPassManager);
1276     else
1277       P->assignPassManager(PMS);
1278
1279     // [4] Push new manager into PMS
1280     PMS.push(FPP);
1281   }
1282
1283   // Assign FPP as the manager of this pass.
1284   FPP->add(this);
1285 }
1286
1287 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1288 /// in the PM Stack and add self into that manager.
1289 void BasicBlockPass::assignPassManager(PMStack &PMS,
1290                                        PassManagerType PreferredType) {
1291
1292   BBPassManager *BBP = NULL;
1293
1294   // Basic Pass Manager is a leaf pass manager. It does not handle
1295   // any other pass manager.
1296   if (!PMS.empty()) {
1297     BBP = dynamic_cast<BBPassManager *>(PMS.top());
1298   }
1299
1300   // If leaf manager is not Basic Block Pass manager then create new
1301   // basic Block Pass manager.
1302
1303   if (!BBP) {
1304     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1305     PMDataManager *PMD = PMS.top();
1306
1307     // [1] Create new Basic Block Manager
1308     BBP = new BBPassManager(PMD->getDepth() + 1);
1309
1310     // [2] Set up new manager's top level manager
1311     // Basic Block Pass Manager does not live by itself
1312     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1313     TPM->addIndirectPassManager(BBP);
1314
1315     // [3] Assign manager to manage this new manager. This may create
1316     // and push new managers into PMS
1317     Pass *P = dynamic_cast<Pass *>(BBP);
1318     P->assignPassManager(PMS);
1319
1320     // [4] Push new manager into PMS
1321     PMS.push(BBP);
1322   }
1323
1324   // Assign BBP as the manager of this pass.
1325   BBP->add(this);
1326 }
1327
1328