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