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