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