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