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   // 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 < 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 < 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     // Take a note of analysis required and made available by this pass.
 608     // Remove the analysis not preserved by this pass
 609     removeNotPreservedAnalysis(P);
 610     recordAvailableAnalysis(P);
 611   }
 612
 613   // Add pass
 614   PassVector.push_back(P);
 615 }
 616
 617 /// Populate RequiredPasses with the analysis pass that are required by
 618 /// pass P.
 619 void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP,
 620                                                   Pass *P) {
 621   AnalysisUsage AnUsage;
 622   P->getAnalysisUsage(AnUsage);
 623   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 624   for (std::vector<AnalysisID>::const_iterator
 625          I = RequiredSet.begin(), E = RequiredSet.end();
 626        I != E; ++I) {
 627     Pass *AnalysisPass = findAnalysisPass(*I, true);
 628     assert (AnalysisPass && "Analysis pass is not available");
 629     RP.push_back(AnalysisPass);
 630   }
 631
 632   const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
 633   for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
 634          E = IDs.end(); I != E; ++I) {
 635     Pass *AnalysisPass = findAnalysisPass(*I, true);
 636     assert (AnalysisPass && "Analysis pass is not available");
 637     RP.push_back(AnalysisPass);
 638   }
 639 }
 640
 641 // All Required analyses should be available to the pass as it runs!  Here
 642 // we fill in the AnalysisImpls member of the pass so that it can
 643 // successfully use the getAnalysis() method to retrieve the
 644 // implementations it needs.
 645 //
 646 void PMDataManager::initializeAnalysisImpl(Pass *P) {
 647   AnalysisUsage AnUsage;
 648   P->getAnalysisUsage(AnUsage);
 649
 650   for (std::vector<const PassInfo *>::const_iterator
 651          I = AnUsage.getRequiredSet().begin(),
 652          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
 653     Pass *Impl = findAnalysisPass(*I, true);
 654     if (Impl == 0)
 655       assert(0 && "Analysis used but not available!");
 656     AnalysisResolver *AR = P->getResolver();
 657     AR->addAnalysisImplsPair(*I, Impl);
 658   }
 659 }
 660
 661 /// Find the pass that implements Analysis AID. If desired pass is not found
 662 /// then return NULL.
 663 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
 664
 665   // Check if AvailableAnalysis map has one entry.
 666   std::map<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
 667
 668   if (I != AvailableAnalysis.end())
 669     return I->second;
 670
 671   // Search Parents through TopLevelManager
 672   if (SearchParent)
 673     return TPM->findAnalysisPass(AID);
 674
 675   return NULL;
 676 }
 677
 678 // Print list of passes that are last used by P.
 679 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
 680
 681   std::vector<Pass *> LUses;
 682
 683   assert (TPM && "Top Level Manager is missing");
 684   TPM->collectLastUses(LUses, P);
 685
 686   for (std::vector<Pass *>::iterator I = LUses.begin(),
 687          E = LUses.end(); I != E; ++I) {
 688     llvm::cerr << "--" << std::string(Offset*2, ' ');
 689     (*I)->dumpPassStructure(0);
 690   }
 691 }
 692
 693 void PMDataManager::dumpPassArguments() const {
 694   for(std::vector<Pass *>::const_iterator I = PassVector.begin(),
 695         E = PassVector.end(); I != E; ++I) {
 696     if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
 697       PMD->dumpPassArguments();
 698     else
 699       if (const PassInfo *PI = (*I)->getPassInfo())
 700         if (!PI->isAnalysisGroup())
 701           cerr << " -" << PI->getPassArgument();
 702   }
 703 }
 704
 705 void PMDataManager:: dumpPassInfo(Pass *P,  std::string &Msg1,
 706                                   std::string &Msg2) const {
 707   if (PassDebugging < Executions)
 708     return;
 709   cerr << (void*)this << std::string(getDepth()*2+1, ' ');
 710   cerr << Msg1;
 711   cerr << P->getPassName();
 712   cerr << Msg2;
 713 }
 714
 715 void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P,
 716                                         const std::vector<AnalysisID> &Set)
 717   const {
 718   if (PassDebugging >= Details && !Set.empty()) {
 719     cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
 720       for (unsigned i = 0; i != Set.size(); ++i) {
 721         if (i) cerr << ",";
 722         cerr << " " << Set[i]->getPassName();
 723       }
 724       cerr << "\n";
 725   }
 726 }
 727
 728 // Destructor
 729 PMDataManager::~PMDataManager() {
 730
 731   for (std::vector<Pass *>::iterator I = PassVector.begin(),
 732          E = PassVector.end(); I != E; ++I)
 733     delete *I;
 734
 735   PassVector.clear();
 736 }
 737
 738 //===----------------------------------------------------------------------===//
 739 // NOTE: Is this the right place to define this method ?
 740 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
 741 Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
 742   return PM.findAnalysisPass(ID, dir);
 743 }
 744
 745 //===----------------------------------------------------------------------===//
 746 // BBPassManager implementation
 747
 748 /// Execute all of the passes scheduled for execution by invoking
 749 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 750 /// the function, and if so, return true.
 751 bool
 752 BBPassManager::runOnFunction(Function &F) {
 753
 754   if (F.isExternal())
 755     return false;
 756
 757   bool Changed = doInitialization(F);
 758
 759   std::string Msg1 = "Executing Pass '";
 760   std::string Msg3 = "' Made Modification '";
 761
 762   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 763     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 764       BasicBlockPass *BP = getContainedPass(Index);
 765       AnalysisUsage AnUsage;
 766       BP->getAnalysisUsage(AnUsage);
 767
 768       std::string Msg2 = "' on BasicBlock '" + (*I).getName() + "'...\n";
 769       dumpPassInfo(BP, Msg1, Msg2);
 770       dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet());
 771
 772       initializeAnalysisImpl(BP);
 773
 774       if (TheTimeInfo) TheTimeInfo->passStarted(BP);
 775       Changed |= BP->runOnBasicBlock(*I);
 776       if (TheTimeInfo) TheTimeInfo->passEnded(BP);
 777
 778       if (Changed)
 779         dumpPassInfo(BP, Msg3, Msg2);
 780       dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet());
 781
 782       removeNotPreservedAnalysis(BP);
 783       recordAvailableAnalysis(BP);
 784       removeDeadPasses(BP, Msg2);
 785     }
 786   return Changed |= doFinalization(F);
 787 }
 788
 789 // Implement doInitialization and doFinalization
 790 inline bool BBPassManager::doInitialization(Module &M) {
 791   bool Changed = false;
 792
 793   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 794     BasicBlockPass *BP = getContainedPass(Index);
 795     Changed |= BP->doInitialization(M);
 796   }
 797
 798   return Changed;
 799 }
 800
 801 inline bool BBPassManager::doFinalization(Module &M) {
 802   bool Changed = false;
 803
 804   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 805     BasicBlockPass *BP = getContainedPass(Index);
 806     Changed |= BP->doFinalization(M);
 807   }
 808
 809   return Changed;
 810 }
 811
 812 inline bool BBPassManager::doInitialization(Function &F) {
 813   bool Changed = false;
 814
 815   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 816     BasicBlockPass *BP = getContainedPass(Index);
 817     Changed |= BP->doInitialization(F);
 818   }
 819
 820   return Changed;
 821 }
 822
 823 inline bool BBPassManager::doFinalization(Function &F) {
 824   bool Changed = false;
 825
 826   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 827     BasicBlockPass *BP = getContainedPass(Index);
 828     Changed |= BP->doFinalization(F);
 829   }
 830
 831   return Changed;
 832 }
 833
 834
 835 //===----------------------------------------------------------------------===//
 836 // FunctionPassManager implementation
 837
 838 /// Create new Function pass manager
 839 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
 840   FPM = new FunctionPassManagerImpl(0);
 841   // FPM is the top level manager.
 842   FPM->setTopLevelManager(FPM);
 843
 844   PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
 845   AnalysisResolver *AR = new AnalysisResolver(*PMD);
 846   FPM->setResolver(AR);
 847
 848   MP = P;
 849 }
 850
 851 FunctionPassManager::~FunctionPassManager() {
 852   delete FPM;
 853 }
 854
 855 /// add - Add a pass to the queue of passes to run.  This passes
 856 /// ownership of the Pass to the PassManager.  When the
 857 /// PassManager_X is destroyed, the pass will be destroyed as well, so
 858 /// there is no need to delete the pass. (TODO delete passes.)
 859 /// This implies that all passes MUST be allocated with 'new'.
 860 void FunctionPassManager::add(Pass *P) {
 861   FPM->add(P);
 862 }
 863
 864 /// run - Execute all of the passes scheduled for execution.  Keep
 865 /// track of whether any of the passes modifies the function, and if
 866 /// so, return true.
 867 ///
 868 bool FunctionPassManager::run(Function &F) {
 869   std::string errstr;
 870   if (MP->materializeFunction(&F, &errstr)) {
 871     cerr << "Error reading bytecode file: " << errstr << "\n";
 872     abort();
 873   }
 874   return FPM->run(F);
 875 }
 876
 877
 878 /// doInitialization - Run all of the initializers for the function passes.
 879 ///
 880 bool FunctionPassManager::doInitialization() {
 881   return FPM->doInitialization(*MP->getModule());
 882 }
 883
 884 /// doFinalization - Run all of the initializers for the function passes.
 885 ///
 886 bool FunctionPassManager::doFinalization() {
 887   return FPM->doFinalization(*MP->getModule());
 888 }
 889
 890 //===----------------------------------------------------------------------===//
 891 // FunctionPassManagerImpl implementation
 892 //
 893 inline bool FunctionPassManagerImpl::doInitialization(Module &M) {
 894   bool Changed = false;
 895
 896   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 897     FPPassManager *FP = getContainedManager(Index);
 898     Changed |= FP->doInitialization(M);
 899   }
 900
 901   return Changed;
 902 }
 903
 904 inline bool FunctionPassManagerImpl::doFinalization(Module &M) {
 905   bool Changed = false;
 906
 907   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 908     FPPassManager *FP = getContainedManager(Index);
 909     Changed |= FP->doFinalization(M);
 910   }
 911
 912   return Changed;
 913 }
 914
 915 // Execute all the passes managed by this top level manager.
 916 // Return true if any function is modified by a pass.
 917 bool FunctionPassManagerImpl::run(Function &F) {
 918
 919   bool Changed = false;
 920
 921   TimingInfo::createTheTimeInfo();
 922
 923   dumpArguments();
 924   dumpPasses();
 925
 926   initializeAllAnalysisInfo();
 927   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 928     FPPassManager *FP = getContainedManager(Index);
 929     Changed |= FP->runOnFunction(F);
 930   }
 931   return Changed;
 932 }
 933
 934 //===----------------------------------------------------------------------===//
 935 // FPPassManager implementation
 936
 937 /// Print passes managed by this manager
 938 void FPPassManager::dumpPassStructure(unsigned Offset) {
 939   llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
 940   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 941     FunctionPass *FP = getContainedPass(Index);
 942     FP->dumpPassStructure(Offset + 1);
 943     dumpLastUses(FP, Offset+1);
 944   }
 945 }
 946
 947
 948 /// Execute all of the passes scheduled for execution by invoking
 949 /// runOnFunction method.  Keep track of whether any of the passes modifies
 950 /// the function, and if so, return true.
 951 bool FPPassManager::runOnFunction(Function &F) {
 952
 953   bool Changed = false;
 954
 955   if (F.isExternal())
 956     return false;
 957
 958   std::string Msg1 = "Executing Pass '";
 959   std::string Msg3 = "' Made Modification '";
 960
 961   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 962     FunctionPass *FP = getContainedPass(Index);
 963
 964     AnalysisUsage AnUsage;
 965     FP->getAnalysisUsage(AnUsage);
 966
 967     std::string Msg2 = "' on Function '" + F.getName() + "'...\n";
 968     dumpPassInfo(FP, Msg1, Msg2);
 969     dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet());
 970
 971     initializeAnalysisImpl(FP);
 972
 973     if (TheTimeInfo) TheTimeInfo->passStarted(FP);
 974     Changed |= FP->runOnFunction(F);
 975     if (TheTimeInfo) TheTimeInfo->passEnded(FP);
 976
 977     if (Changed)
 978       dumpPassInfo(FP, Msg3, Msg2);
 979     dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet());
 980
 981     removeNotPreservedAnalysis(FP);
 982     recordAvailableAnalysis(FP);
 983     removeDeadPasses(FP, Msg2);
 984   }
 985   return Changed;
 986 }
 987
 988 bool FPPassManager::runOnModule(Module &M) {
 989
 990   bool Changed = doInitialization(M);
 991
 992   for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 993     this->runOnFunction(*I);
 994
 995   return Changed |= doFinalization(M);
 996 }
 997
 998 inline bool FPPassManager::doInitialization(Module &M) {
 999   bool Changed = false;
1000
1001   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1002     FunctionPass *FP = getContainedPass(Index);
1003     Changed |= FP->doInitialization(M);
1004   }
1005
1006   return Changed;
1007 }
1008
1009 inline bool FPPassManager::doFinalization(Module &M) {
1010   bool Changed = false;
1011
1012   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1013     FunctionPass *FP = getContainedPass(Index);
1014     Changed |= FP->doFinalization(M);
1015   }
1016
1017   return Changed;
1018 }
1019
1020 //===----------------------------------------------------------------------===//
1021 // MPPassManager implementation
1022
1023 /// Execute all of the passes scheduled for execution by invoking
1024 /// runOnModule method.  Keep track of whether any of the passes modifies
1025 /// the module, and if so, return true.
1026 bool
1027 MPPassManager::runOnModule(Module &M) {
1028   bool Changed = false;
1029
1030   std::string Msg1 = "Executing Pass '";
1031   std::string Msg3 = "' Made Modification '";
1032
1033   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
1034     ModulePass *MP = getContainedPass(Index);
1035
1036     AnalysisUsage AnUsage;
1037     MP->getAnalysisUsage(AnUsage);
1038
1039     std::string Msg2 = "' on Module '" + M.getModuleIdentifier() + "'...\n";
1040     dumpPassInfo(MP, Msg1, Msg2);
1041     dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet());
1042
1043     initializeAnalysisImpl(MP);
1044
1045     if (TheTimeInfo) TheTimeInfo->passStarted(MP);
1046     Changed |= MP->runOnModule(M);
1047     if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1048
1049     if (Changed)
1050       dumpPassInfo(MP, Msg3, Msg2);
1051     dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet());
1052
1053     removeNotPreservedAnalysis(MP);
1054     recordAvailableAnalysis(MP);
1055     removeDeadPasses(MP, Msg2);
1056   }
1057   return Changed;
1058 }
1059
1060 //===----------------------------------------------------------------------===//
1061 // PassManagerImpl implementation
1062 //
1063 /// run - Execute all of the passes scheduled for execution.  Keep track of
1064 /// whether any of the passes modifies the module, and if so, return true.
1065 bool PassManagerImpl::run(Module &M) {
1066
1067   bool Changed = false;
1068
1069   TimingInfo::createTheTimeInfo();
1070
1071   dumpArguments();
1072   dumpPasses();
1073
1074   initializeAllAnalysisInfo();
1075   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1076     MPPassManager *MP = getContainedManager(Index);
1077     Changed |= MP->runOnModule(M);
1078   }
1079   return Changed;
1080 }
1081
1082 //===----------------------------------------------------------------------===//
1083 // PassManager implementation
1084
1085 /// Create new pass manager
1086 PassManager::PassManager() {
1087   PM = new PassManagerImpl(0);
1088   // PM is the top level manager
1089   PM->setTopLevelManager(PM);
1090 }
1091
1092 PassManager::~PassManager() {
1093   delete PM;
1094 }
1095
1096 /// add - Add a pass to the queue of passes to run.  This passes ownership of
1097 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
1098 /// will be destroyed as well, so there is no need to delete the pass.  This
1099 /// implies that all passes MUST be allocated with 'new'.
1100 void
1101 PassManager::add(Pass *P) {
1102   PM->add(P);
1103 }
1104
1105 /// run - Execute all of the passes scheduled for execution.  Keep track of
1106 /// whether any of the passes modifies the module, and if so, return true.
1107 bool
1108 PassManager::run(Module &M) {
1109   return PM->run(M);
1110 }
1111
1112 //===----------------------------------------------------------------------===//
1113 // TimingInfo Class - This class is used to calculate information about the
1114 // amount of time each pass takes to execute.  This only happens with
1115 // -time-passes is enabled on the command line.
1116 //
1117 bool llvm::TimePassesIsEnabled = false;
1118 static cl::opt<bool,true>
1119 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1120             cl::desc("Time each pass, printing elapsed time for each on exit"));
1121
1122 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1123 // a non null value (if the -time-passes option is enabled) or it leaves it
1124 // null.  It may be called multiple times.
1125 void TimingInfo::createTheTimeInfo() {
1126   if (!TimePassesIsEnabled || TheTimeInfo) return;
1127
1128   // Constructed the first time this is called, iff -time-passes is enabled.
1129   // This guarantees that the object will be constructed before static globals,
1130   // thus it will be destroyed before them.
1131   static ManagedStatic<TimingInfo> TTI;
1132   TheTimeInfo = &*TTI;
1133 }
1134
1135 /// If TimingInfo is enabled then start pass timer.
1136 void StartPassTimer(Pass *P) {
1137   if (TheTimeInfo)
1138     TheTimeInfo->passStarted(P);
1139 }
1140
1141 /// If TimingInfo is enabled then stop pass timer.
1142 void StopPassTimer(Pass *P) {
1143   if (TheTimeInfo)
1144     TheTimeInfo->passEnded(P);
1145 }
1146
1147 //===----------------------------------------------------------------------===//
1148 // PMStack implementation
1149 //
1150
1151 // Pop Pass Manager from the stack and clear its analysis info.
1152 void PMStack::pop() {
1153
1154   PMDataManager *Top = this->top();
1155   Top->initializeAnalysisInfo();
1156
1157   S.pop_back();
1158 }
1159
1160 // Push PM on the stack and set its top level manager.
1161 void PMStack::push(Pass *P) {
1162
1163   PMDataManager *Top = NULL;
1164   PMDataManager *PM = dynamic_cast<PMDataManager *>(P);
1165   assert (PM && "Unable to push. Pass Manager expected");
1166
1167   if (this->empty()) {
1168     Top = PM;
1169   }
1170   else {
1171     Top = this->top();
1172     PMTopLevelManager *TPM = Top->getTopLevelManager();
1173
1174     assert (TPM && "Unable to find top level manager");
1175     TPM->addIndirectPassManager(PM);
1176     PM->setTopLevelManager(TPM);
1177   }
1178
1179   AnalysisResolver *AR = new AnalysisResolver(*Top);
1180   P->setResolver(AR);
1181
1182   S.push_back(PM);
1183 }
1184
1185 // Dump content of the pass manager stack.
1186 void PMStack::dump() {
1187   for(std::deque<PMDataManager *>::iterator I = S.begin(),
1188         E = S.end(); I != E; ++I) {
1189     Pass *P = dynamic_cast<Pass *>(*I);
1190     printf ("%s ", P->getPassName());
1191   }
1192   if (!S.empty())
1193     printf ("\n");
1194 }
1195
1196 // Walk Pass Manager stack and set LastUse markers if any
1197 // manager is transfering this priviledge to its parent manager
1198 void PMStack::handleLastUserOverflow() {
1199
1200   for(PMStack::iterator I = this->begin(), E = this->end(); I != E;) {
1201
1202     PMDataManager *Child = *I++;
1203     if (I != E) {
1204       PMDataManager *Parent = *I++;
1205       PMTopLevelManager *TPM = Parent->getTopLevelManager();
1206       std::vector<Pass *> &TLU = Child->getTransferredLastUses();
1207       if (!TLU.empty()) {
1208         Pass *P = dynamic_cast<Pass *>(Parent);
1209         TPM->setLastUser(TLU, P);
1210       }
1211     }
1212   }
1213 }
1214
1215 /// Find appropriate Module Pass Manager in the PM Stack and
1216 /// add self into that manager.
1217 void ModulePass::assignPassManager(PMStack &PMS,
1218                                    PassManagerType PreferredType) {
1219
1220   // Find Module Pass Manager
1221   while(!PMS.empty()) {
1222     PassManagerType TopPMType = PMS.top()->getPassManagerType();
1223     if (TopPMType == PreferredType)
1224       break; // We found desired pass manager
1225     else if (TopPMType > PMT_ModulePassManager)
1226       PMS.pop();    // Pop children pass managers
1227     else
1228       break;
1229   }
1230
1231   PMS.top()->add(this);
1232 }
1233
1234 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1235 /// in the PM Stack and add self into that manager.
1236 void FunctionPass::assignPassManager(PMStack &PMS,
1237                                      PassManagerType PreferredType) {
1238
1239   // Find Module Pass Manager (TODO : Or Call Graph Pass Manager)
1240   while(!PMS.empty()) {
1241     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1242       PMS.pop();
1243     else
1244       break;
1245   }
1246   FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1247
1248   // Create new Function Pass Manager
1249   if (!FPP) {
1250     assert(!PMS.empty() && "Unable to create Function Pass Manager");
1251     PMDataManager *PMD = PMS.top();
1252
1253     // [1] Create new Function Pass Manager
1254     FPP = new FPPassManager(PMD->getDepth() + 1);
1255
1256     // [2] Set up new manager's top level manager
1257     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1258     TPM->addIndirectPassManager(FPP);
1259
1260     // [3] Assign manager to manage this new manager. This may create
1261     // and push new managers into PMS
1262     Pass *P = dynamic_cast<Pass *>(FPP);
1263
1264     // If Call Graph Pass Manager is active then use it to manage
1265     // this new Function Pass manager.
1266     if (PMD->getPassManagerType() == PMT_CallGraphPassManager)
1267       P->assignPassManager(PMS, PMT_CallGraphPassManager);
1268     else
1269       P->assignPassManager(PMS);
1270
1271     // [4] Push new manager into PMS
1272     PMS.push(FPP);
1273   }
1274
1275   // Assign FPP as the manager of this pass.
1276   FPP->add(this);
1277 }
1278
1279 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1280 /// in the PM Stack and add self into that manager.
1281 void BasicBlockPass::assignPassManager(PMStack &PMS,
1282                                        PassManagerType PreferredType) {
1283
1284   BBPassManager *BBP = NULL;
1285
1286   // Basic Pass Manager is a leaf pass manager. It does not handle
1287   // any other pass manager.
1288   if (!PMS.empty()) {
1289     BBP = dynamic_cast<BBPassManager *>(PMS.top());
1290   }
1291
1292   // If leaf manager is not Basic Block Pass manager then create new
1293   // basic Block Pass manager.
1294
1295   if (!BBP) {
1296     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1297     PMDataManager *PMD = PMS.top();
1298
1299     // [1] Create new Basic Block Manager
1300     BBP = new BBPassManager(PMD->getDepth() + 1);
1301
1302     // [2] Set up new manager's top level manager
1303     // Basic Block Pass Manager does not live by itself
1304     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1305     TPM->addIndirectPassManager(BBP);
1306
1307     // [3] Assign manager to manage this new manager. This may create
1308     // and push new managers into PMS
1309     Pass *P = dynamic_cast<Pass *>(BBP);
1310     P->assignPassManager(PMS);
1311
1312     // [4] Push new manager into PMS
1313     PMS.push(BBP);
1314   }
1315
1316   // Assign BBP as the manager of this pass.
1317   BBP->add(this);
1318 }
1319
1320