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/PassManager.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/ModuleProvider.h"
  18 #include <vector>
  19 #include <map>
  20
  21 using namespace llvm;
  22
  23 namespace llvm {
  24
  25 /// CommonPassManagerImpl helps pass manager analysis required by
  26 /// the managed passes. It provides methods to add/remove analysis
  27 /// available and query if certain analysis is available or not.
  28 class CommonPassManagerImpl {
  29
  30 public:
  31
  32   /// Return true IFF pass P's required analysis set does not required new
  33   /// manager.
  34   bool manageablePass(Pass *P);
  35
  36   Pass *getAnalysisPass(AnalysisID AID) const {
  37
  38     std::map<AnalysisID, Pass*>::const_iterator I =
  39       AvailableAnalysis.find(AID);
  40
  41     if (I != AvailableAnalysis.end())
  42       return NULL;
  43     else
  44       return I->second;
  45   }
  46
  47   /// Augment RequiredAnalysis by adding analysis required by pass P.
  48   void noteDownRequiredAnalysis(Pass *P);
  49
  50   /// Augment AvailableAnalysis by adding analysis made available by pass P.
  51   void noteDownAvailableAnalysis(Pass *P);
  52
  53   /// Remove Analysis that is not preserved by the pass
  54   void removeNotPreservedAnalysis(Pass *P);
  55
  56   /// Remove dead passes
  57   void removeDeadPasses(Pass *P);
  58
  59   /// Add pass P into the PassVector. Update RequiredAnalysis and
  60   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
  61   void addPassToManager (Pass *P, bool ProcessAnalysis = true);
  62
  63   /// Clear analysis vectors RequiredAnalysis and AvailableAnalysis.
  64   /// This is used before running passes managed by the manager.
  65   void clearAnalysis() {
  66     RequiredAnalysis.clear();
  67     AvailableAnalysis.clear();
  68     LastUser.clear();
  69   }
  70
  71   // All Required analyses should be available to the pass as it runs!  Here
  72   // we fill in the AnalysisImpls member of the pass so that it can
  73   // successfully use the getAnalysis() method to retrieve the
  74   // implementations it needs.
  75   //
  76  void initializeAnalysisImpl(Pass *P);
  77
  78   inline std::vector<Pass *>::iterator passVectorBegin() {
  79     return PassVector.begin();
  80   }
  81
  82   inline std::vector<Pass *>::iterator passVectorEnd() {
  83     return PassVector.end();
  84   }
  85
  86   inline void setLastUser(Pass *P, Pass *LU) {
  87     LastUser[P] = LU;
  88     // TODO : Check if pass P is available.
  89
  90     // Prolong live range of analyses that are needed after an analysis pass
  91     // is destroyed, for querying by subsequent passes
  92     AnalysisUsage AnUsage;
  93     P->getAnalysisUsage(AnUsage);
  94     const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
  95     for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
  96            E = IDs.end(); I != E; ++I) {
  97       Pass *AnalysisPass = getAnalysisPass(*I); // getAnalysisPassFromManager(*I);
  98       assert (AnalysisPass && "Analysis pass is not available");
  99       setLastUser(AnalysisPass, LU);
 100     }
 101
 102   }
 103
 104 private:
 105   // Analysis required by the passes managed by this manager. This information
 106   // used while selecting pass manager during addPass. If a pass does not
 107   // preserve any analysis required by other passes managed by current
 108   // pass manager then new pass manager is used.
 109   std::vector<AnalysisID> RequiredAnalysis;
 110
 111   // Set of available Analysis. This information is used while scheduling
 112   // pass. If a pass requires an analysis which is not not available then
 113   // equired analysis pass is scheduled to run before the pass itself is
 114   // scheduled to run.
 115   std::map<AnalysisID, Pass*> AvailableAnalysis;
 116
 117   // Map to keep track of last user of the analysis pass.
 118   // LastUser->second is the last user of Lastuser->first.
 119   std::map<Pass *, Pass *> LastUser;
 120
 121   // Collection of pass that are managed by this manager
 122   std::vector<Pass *> PassVector;
 123 };
 124
 125 /// BasicBlockPassManager_New manages BasicBlockPass. It batches all the
 126 /// pass together and sequence them to process one basic block before
 127 /// processing next basic block.
 128 class BasicBlockPassManager_New : public CommonPassManagerImpl,
 129                                   public FunctionPass {
 130
 131 public:
 132   BasicBlockPassManager_New() { }
 133
 134   /// Add a pass into a passmanager queue.
 135   bool addPass(Pass *p);
 136
 137   /// Execute all of the passes scheduled for execution.  Keep track of
 138   /// whether any of the passes modifies the function, and if so, return true.
 139   bool runOnFunction(Function &F);
 140
 141   /// Return true IFF AnalysisID AID is currently available.
 142   Pass *getAnalysisPassFromManager(AnalysisID AID);
 143
 144 private:
 145 };
 146
 147 /// FunctionPassManagerImpl_New manages FunctionPasses and BasicBlockPassManagers.
 148 /// It batches all function passes and basic block pass managers together and
 149 /// sequence them to process one function at a time before processing next
 150 /// function.
 151 class FunctionPassManagerImpl_New : public CommonPassManagerImpl,
 152                                     public ModulePass {
 153 public:
 154   FunctionPassManagerImpl_New(ModuleProvider *P) { /* TODO */ }
 155   FunctionPassManagerImpl_New() {
 156     activeBBPassManager = NULL;
 157   }
 158   ~FunctionPassManagerImpl_New() { /* TODO */ };
 159
 160   /// add - Add a pass to the queue of passes to run.  This passes
 161   /// ownership of the Pass to the PassManager.  When the
 162   /// PassManager_X is destroyed, the pass will be destroyed as well, so
 163   /// there is no need to delete the pass. (TODO delete passes.)
 164   /// This implies that all passes MUST be allocated with 'new'.
 165   void add(Pass *P) { /* TODO*/  }
 166
 167   /// Add pass into the pass manager queue.
 168   bool addPass(Pass *P);
 169
 170   /// Execute all of the passes scheduled for execution.  Keep
 171   /// track of whether any of the passes modifies the function, and if
 172   /// so, return true.
 173   bool runOnModule(Module &M);
 174
 175   /// Return true IFF AnalysisID AID is currently available.
 176   Pass *getAnalysisPassFromManager(AnalysisID AID);
 177
 178   /// doInitialization - Run all of the initializers for the function passes.
 179   ///
 180   bool doInitialization(Module &M);
 181
 182   /// doFinalization - Run all of the initializers for the function passes.
 183   ///
 184   bool doFinalization(Module &M);
 185 private:
 186   // Active Pass Managers
 187   BasicBlockPassManager_New *activeBBPassManager;
 188 };
 189
 190 /// ModulePassManager_New manages ModulePasses and function pass managers.
 191 /// It batches all Module passes  passes and function pass managers together and
 192 /// sequence them to process one module.
 193 class ModulePassManager_New : public CommonPassManagerImpl {
 194
 195 public:
 196   ModulePassManager_New() { activeFunctionPassManager = NULL; }
 197
 198   /// Add a pass into a passmanager queue.
 199   bool addPass(Pass *p);
 200
 201   /// run - Execute all of the passes scheduled for execution.  Keep track of
 202   /// whether any of the passes modifies the module, and if so, return true.
 203   bool runOnModule(Module &M);
 204
 205   /// Return true IFF AnalysisID AID is currently available.
 206   Pass *getAnalysisPassFromManager(AnalysisID AID);
 207
 208 private:
 209   // Active Pass Manager
 210   FunctionPassManagerImpl_New *activeFunctionPassManager;
 211 };
 212
 213 /// PassManager_New manages ModulePassManagers
 214 class PassManagerImpl_New : public CommonPassManagerImpl {
 215
 216 public:
 217
 218   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 219   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 220   /// will be destroyed as well, so there is no need to delete the pass.  This
 221   /// implies that all passes MUST be allocated with 'new'.
 222   void add(Pass *P);
 223
 224   /// run - Execute all of the passes scheduled for execution.  Keep track of
 225   /// whether any of the passes modifies the module, and if so, return true.
 226   bool run(Module &M);
 227
 228   /// Return true IFF AnalysisID AID is currently available.
 229   Pass *getAnalysisPassFromManager(AnalysisID AID);
 230
 231 private:
 232
 233   /// Add a pass into a passmanager queue. This is used by schedulePasses
 234   bool addPass(Pass *p);
 235
 236   /// Schedule pass P for execution. Make sure that passes required by
 237   /// P are run before P is run. Update analysis info maintained by
 238   /// the manager. Remove dead passes. This is a recursive function.
 239   void schedulePass(Pass *P);
 240
 241   /// Schedule all passes collected in pass queue using add(). Add all the
 242   /// schedule passes into various manager's queue using addPass().
 243   void schedulePasses();
 244
 245   // Collection of pass managers
 246   std::vector<ModulePassManager_New *> PassManagers;
 247
 248   // Active Pass Manager
 249   ModulePassManager_New *activeManager;
 250 };
 251
 252 } // End of llvm namespace
 253
 254 // CommonPassManagerImpl implementation
 255
 256 /// Return true IFF pass P's required analysis set does not required new
 257 /// manager.
 258 bool CommonPassManagerImpl::manageablePass(Pass *P) {
 259
 260   AnalysisUsage AnUsage;
 261   P->getAnalysisUsage(AnUsage);
 262
 263   // If this pass is not preserving information that is required by the other
 264   // passes managed by this manager then use new manager
 265   if (!AnUsage.getPreservesAll()) {
 266     const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 267     for (std::vector<AnalysisID>::iterator I = RequiredAnalysis.begin(),
 268            E = RequiredAnalysis.end(); I != E; ++I) {
 269       if (std::find(PreservedSet.begin(), PreservedSet.end(), *I) ==
 270           PreservedSet.end())
 271         // This analysis is not preserved. Need new manager.
 272         return false;
 273     }
 274   }
 275   return true;
 276 }
 277
 278 /// Augment RequiredAnalysis by adding analysis required by pass P.
 279 void CommonPassManagerImpl::noteDownRequiredAnalysis(Pass *P) {
 280   AnalysisUsage AnUsage;
 281   P->getAnalysisUsage(AnUsage);
 282   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 283
 284   // FIXME: What about duplicates ?
 285   RequiredAnalysis.insert(RequiredAnalysis.end(), RequiredSet.begin(),
 286                           RequiredSet.end());
 287
 288   initializeAnalysisImpl(P);
 289 }
 290
 291 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 292 void CommonPassManagerImpl::noteDownAvailableAnalysis(Pass *P) {
 293
 294   if (const PassInfo *PI = P->getPassInfo()) {
 295     AvailableAnalysis[PI] = P;
 296
 297     //TODO This pass is the current implementation of all of the interfaces it
 298     //TODO implements as well.
 299     //TODO
 300     //TODO const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
 301     //TODO for (unsigned i = 0, e = II.size(); i != e; ++i)
 302     //TODO CurrentAnalyses[II[i]] = P;
 303   }
 304 }
 305
 306 /// Remove Analyss not preserved by Pass P
 307 void CommonPassManagerImpl::removeNotPreservedAnalysis(Pass *P) {
 308   AnalysisUsage AnUsage;
 309   P->getAnalysisUsage(AnUsage);
 310   const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 311
 312   for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
 313          E = AvailableAnalysis.end(); I != E; ++I ) {
 314     if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) ==
 315         PreservedSet.end()) {
 316       // Remove this analysis
 317       std::map<AnalysisID, Pass*>::iterator J = I++;
 318       AvailableAnalysis.erase(J);
 319     }
 320   }
 321 }
 322
 323 /// Remove analysis passes that are not used any longer
 324 void CommonPassManagerImpl::removeDeadPasses(Pass *P) {
 325
 326   for (std::map<Pass *, Pass *>::iterator I = LastUser.begin(),
 327          E = LastUser.end(); I !=E; ++I) {
 328     if (I->second == P) {
 329       Pass *deadPass = I->first;
 330       deadPass->releaseMemory();
 331
 332       std::map<AnalysisID, Pass*>::iterator Pos =
 333         AvailableAnalysis.find(deadPass->getPassInfo());
 334
 335       assert (Pos != AvailableAnalysis.end() &&
 336               "Pass is not available");
 337       AvailableAnalysis.erase(Pos);
 338     }
 339   }
 340 }
 341
 342 /// Add pass P into the PassVector. Update RequiredAnalysis and
 343 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 344 void CommonPassManagerImpl::addPassToManager (Pass *P,
 345                                               bool ProcessAnalysis) {
 346
 347   if (ProcessAnalysis) {
 348     // Take a note of analysis required and made available by this pass
 349     noteDownRequiredAnalysis(P);
 350     noteDownAvailableAnalysis(P);
 351
 352     // Remove the analysis not preserved by this pass
 353     removeNotPreservedAnalysis(P);
 354   }
 355
 356   // Add pass
 357   PassVector.push_back(P);
 358 }
 359
 360 // All Required analyses should be available to the pass as it runs!  Here
 361 // we fill in the AnalysisImpls member of the pass so that it can
 362 // successfully use the getAnalysis() method to retrieve the
 363 // implementations it needs.
 364 //
 365 void CommonPassManagerImpl::initializeAnalysisImpl(Pass *P) {
 366   AnalysisUsage AnUsage;
 367   P->getAnalysisUsage(AnUsage);
 368
 369   for (std::vector<const PassInfo *>::const_iterator
 370          I = AnUsage.getRequiredSet().begin(),
 371          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
 372     Pass *Impl = getAnalysisPass(*I);
 373     if (Impl == 0)
 374       assert(0 && "Analysis used but not available!");
 375     // TODO:  P->AnalysisImpls.push_back(std::make_pair(*I, Impl));
 376   }
 377 }
 378
 379 /// BasicBlockPassManager implementation
 380
 381 /// Add pass P into PassVector and return true. If this pass is not
 382 /// manageable by this manager then return false.
 383 bool
 384 BasicBlockPassManager_New::addPass(Pass *P) {
 385
 386   BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
 387   if (!BP)
 388     return false;
 389
 390   // If this pass does not preserve anlysis that is used by other passes
 391   // managed by this manager than it is not a suiable pass for this manager.
 392   if (!manageablePass(P))
 393     return false;
 394
 395   addPassToManager (BP);
 396
 397   return true;
 398 }
 399
 400 /// Execute all of the passes scheduled for execution by invoking
 401 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 402 /// the function, and if so, return true.
 403 bool
 404 BasicBlockPassManager_New::runOnFunction(Function &F) {
 405
 406   bool Changed = false;
 407   clearAnalysis();
 408
 409   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 410     for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 411            e = passVectorEnd(); itr != e; ++itr) {
 412       Pass *P = *itr;
 413
 414       noteDownAvailableAnalysis(P);
 415       BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
 416       Changed |= BP->runOnBasicBlock(*I);
 417       removeNotPreservedAnalysis(P);
 418       removeDeadPasses(P);
 419     }
 420   return Changed;
 421 }
 422
 423 /// Return true IFF AnalysisID AID is currently available.
 424 Pass * BasicBlockPassManager_New::getAnalysisPassFromManager(AnalysisID AID) {
 425   return getAnalysisPass(AID);
 426 }
 427
 428 // FunctionPassManager_New implementation
 429 /// Create new Function pass manager
 430 FunctionPassManager_New::FunctionPassManager_New() {
 431   FPM = new FunctionPassManagerImpl_New();
 432 }
 433
 434 /// add - Add a pass to the queue of passes to run.  This passes
 435 /// ownership of the Pass to the PassManager.  When the
 436 /// PassManager_X is destroyed, the pass will be destroyed as well, so
 437 /// there is no need to delete the pass. (TODO delete passes.)
 438 /// This implies that all passes MUST be allocated with 'new'.
 439 void
 440 FunctionPassManager_New::add(Pass *P) {
 441   FPM->add(P);
 442 }
 443
 444 /// Execute all of the passes scheduled for execution.  Keep
 445 /// track of whether any of the passes modifies the function, and if
 446 /// so, return true.
 447 bool
 448 FunctionPassManager_New::runOnModule(Module &M) {
 449   return FPM->runOnModule(M);
 450 }
 451
 452 /// doInitialization - Run all of the initializers for the function passes.
 453 ///
 454 bool FunctionPassManager_New::doInitialization() {
 455   return FPM->doInitialization(*MP->getModule());
 456 }
 457
 458 /// doFinalization - Run all of the initializers for the function passes.
 459 ///
 460 bool FunctionPassManager_New::doFinalization() {
 461   return FPM->doFinalization(*MP->getModule());
 462 }
 463
 464 // FunctionPassManagerImpl_New implementation
 465
 466 // FunctionPassManager
 467
 468 /// Add pass P into the pass manager queue. If P is a BasicBlockPass then
 469 /// either use it into active basic block pass manager or create new basic
 470 /// block pass manager to handle pass P.
 471 bool
 472 FunctionPassManagerImpl_New::addPass(Pass *P) {
 473
 474   // If P is a BasicBlockPass then use BasicBlockPassManager_New.
 475   if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) {
 476
 477     if (!activeBBPassManager
 478         || !activeBBPassManager->addPass(BP)) {
 479
 480       activeBBPassManager = new BasicBlockPassManager_New();
 481       addPassToManager(activeBBPassManager, false);
 482       if (!activeBBPassManager->addPass(BP))
 483         assert(0 && "Unable to add Pass");
 484     }
 485     return true;
 486   }
 487
 488   FunctionPass *FP = dynamic_cast<FunctionPass *>(P);
 489   if (!FP)
 490     return false;
 491
 492   // If this pass does not preserve anlysis that is used by other passes
 493   // managed by this manager than it is not a suiable pass for this manager.
 494   if (!manageablePass(P))
 495     return false;
 496
 497   addPassToManager (FP);
 498   activeBBPassManager = NULL;
 499   return true;
 500 }
 501
 502 /// Execute all of the passes scheduled for execution by invoking
 503 /// runOnFunction method.  Keep track of whether any of the passes modifies
 504 /// the function, and if so, return true.
 505 bool
 506 FunctionPassManagerImpl_New::runOnModule(Module &M) {
 507
 508   bool Changed = false;
 509   clearAnalysis();
 510
 511   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 512     for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 513            e = passVectorEnd(); itr != e; ++itr) {
 514       Pass *P = *itr;
 515
 516       noteDownAvailableAnalysis(P);
 517       FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
 518       Changed |= FP->runOnFunction(*I);
 519       removeNotPreservedAnalysis(P);
 520       removeDeadPasses(P);
 521     }
 522   return Changed;
 523 }
 524
 525 /// Return true IFF AnalysisID AID is currently available.
 526 Pass *FunctionPassManagerImpl_New::getAnalysisPassFromManager(AnalysisID AID) {
 527
 528   Pass *P = getAnalysisPass(AID);
 529   if (P)
 530     return P;
 531
 532   if (activeBBPassManager &&
 533       activeBBPassManager->getAnalysisPass(AID) != 0)
 534     return activeBBPassManager->getAnalysisPass(AID);
 535
 536   // TODO : Check inactive managers
 537   return NULL;
 538 }
 539
 540 inline bool FunctionPassManagerImpl_New::doInitialization(Module &M) {
 541   bool Changed = false;
 542
 543   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 544          e = passVectorEnd(); itr != e; ++itr) {
 545     Pass *P = *itr;
 546
 547     FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
 548     Changed |= FP->doInitialization(M);
 549   }
 550
 551   return Changed;
 552 }
 553
 554 inline bool FunctionPassManagerImpl_New::doFinalization(Module &M) {
 555   bool Changed = false;
 556
 557   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 558          e = passVectorEnd(); itr != e; ++itr) {
 559     Pass *P = *itr;
 560
 561     FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
 562     Changed |= FP->doFinalization(M);
 563   }
 564
 565
 566   return Changed;
 567 }
 568
 569
 570 // ModulePassManager implementation
 571
 572 /// Add P into pass vector if it is manageble. If P is a FunctionPass
 573 /// then use FunctionPassManagerImpl_New to manage it. Return false if P
 574 /// is not manageable by this manager.
 575 bool
 576 ModulePassManager_New::addPass(Pass *P) {
 577
 578   // If P is FunctionPass then use function pass maanager.
 579   if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) {
 580
 581     activeFunctionPassManager = NULL;
 582
 583     if (!activeFunctionPassManager
 584         || !activeFunctionPassManager->addPass(P)) {
 585
 586       activeFunctionPassManager = new FunctionPassManagerImpl_New();
 587       addPassToManager(activeFunctionPassManager, false);
 588       if (!activeFunctionPassManager->addPass(FP))
 589         assert(0 && "Unable to add pass");
 590     }
 591     return true;
 592   }
 593
 594   ModulePass *MP = dynamic_cast<ModulePass *>(P);
 595   if (!MP)
 596     return false;
 597
 598   // If this pass does not preserve anlysis that is used by other passes
 599   // managed by this manager than it is not a suiable pass for this manager.
 600   if (!manageablePass(P))
 601     return false;
 602
 603   addPassToManager(MP);
 604   activeFunctionPassManager = NULL;
 605   return true;
 606 }
 607
 608
 609 /// Execute all of the passes scheduled for execution by invoking
 610 /// runOnModule method.  Keep track of whether any of the passes modifies
 611 /// the module, and if so, return true.
 612 bool
 613 ModulePassManager_New::runOnModule(Module &M) {
 614   bool Changed = false;
 615   clearAnalysis();
 616
 617   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 618          e = passVectorEnd(); itr != e; ++itr) {
 619     Pass *P = *itr;
 620
 621     noteDownAvailableAnalysis(P);
 622     ModulePass *MP = dynamic_cast<ModulePass*>(P);
 623     Changed |= MP->runOnModule(M);
 624     removeNotPreservedAnalysis(P);
 625     removeDeadPasses(P);
 626   }
 627   return Changed;
 628 }
 629
 630 /// Return true IFF AnalysisID AID is currently available.
 631 Pass *ModulePassManager_New::getAnalysisPassFromManager(AnalysisID AID) {
 632
 633
 634   Pass *P = getAnalysisPass(AID);
 635   if (P)
 636     return P;
 637
 638   if (activeFunctionPassManager &&
 639       activeFunctionPassManager->getAnalysisPass(AID) != 0)
 640     return activeFunctionPassManager->getAnalysisPass(AID);
 641
 642   // TODO : Check inactive managers
 643   return NULL;
 644 }
 645
 646 /// Return true IFF AnalysisID AID is currently available.
 647 Pass *PassManagerImpl_New::getAnalysisPassFromManager(AnalysisID AID) {
 648
 649   Pass *P = NULL;
 650   for (std::vector<ModulePassManager_New *>::iterator itr = PassManagers.begin(),
 651          e = PassManagers.end(); !P && itr != e; ++itr)
 652     P  = (*itr)->getAnalysisPassFromManager(AID);
 653   return P;
 654 }
 655
 656 /// Schedule pass P for execution. Make sure that passes required by
 657 /// P are run before P is run. Update analysis info maintained by
 658 /// the manager. Remove dead passes. This is a recursive function.
 659 void PassManagerImpl_New::schedulePass(Pass *P) {
 660
 661   AnalysisUsage AnUsage;
 662   P->getAnalysisUsage(AnUsage);
 663   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 664   for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
 665          E = RequiredSet.end(); I != E; ++I) {
 666
 667     Pass *AnalysisPass = getAnalysisPassFromManager(*I);
 668     if (!AnalysisPass) {
 669       // Schedule this analysis run first.
 670       AnalysisPass = (*I)->createPass();
 671       schedulePass(AnalysisPass);
 672     }
 673     setLastUser (AnalysisPass, P);
 674   }
 675
 676   addPass(P);
 677 }
 678
 679 /// Schedule all passes from the queue by adding them in their
 680 /// respective manager's queue.
 681 void PassManagerImpl_New::schedulePasses() {
 682   for (std::vector<Pass *>::iterator I = passVectorBegin(),
 683          E = passVectorEnd(); I != E; ++I)
 684     schedulePass (*I);
 685 }
 686
 687 /// Add pass P to the queue of passes to run.
 688 void PassManagerImpl_New::add(Pass *P) {
 689   // Do not process Analysis now. Analysis is process while scheduling
 690   // the pass vector.
 691   addPassToManager(P, false);
 692 }
 693
 694 // PassManager_New implementation
 695 /// Add P into active pass manager or use new module pass manager to
 696 /// manage it.
 697 bool PassManagerImpl_New::addPass(Pass *P) {
 698
 699   if (!activeManager || !activeManager->addPass(P)) {
 700     activeManager = new ModulePassManager_New();
 701     PassManagers.push_back(activeManager);
 702   }
 703
 704   return activeManager->addPass(P);
 705 }
 706
 707 /// run - Execute all of the passes scheduled for execution.  Keep track of
 708 /// whether any of the passes modifies the module, and if so, return true.
 709 bool PassManagerImpl_New::run(Module &M) {
 710
 711   schedulePasses();
 712   bool Changed = false;
 713   for (std::vector<ModulePassManager_New *>::iterator itr = PassManagers.begin(),
 714          e = PassManagers.end(); itr != e; ++itr) {
 715     ModulePassManager_New *pm = *itr;
 716     Changed |= pm->runOnModule(M);
 717   }
 718   return Changed;
 719 }
 720
 721 /// Create new pass manager
 722 PassManager_New::PassManager_New() {
 723   PM = new PassManagerImpl_New();
 724 }
 725
 726 /// add - Add a pass to the queue of passes to run.  This passes ownership of
 727 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 728 /// will be destroyed as well, so there is no need to delete the pass.  This
 729 /// implies that all passes MUST be allocated with 'new'.
 730 void
 731 PassManager_New::add(Pass *P) {
 732   PM->add(P);
 733 }
 734
 735 /// run - Execute all of the passes scheduled for execution.  Keep track of
 736 /// whether any of the passes modifies the module, and if so, return true.
 737 bool
 738 PassManager_New::run(Module &M) {
 739   return PM->run(M);
 740 }
 741