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