lib/VMCore/PassManager.cpp

   1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the LLVM Pass Manager infrastructure.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14
  15 #include "llvm/PassManagers.h"
  16 #include "llvm/Support/CommandLine.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/ModuleProvider.h"
  19 #include "llvm/Support/Streams.h"
  20 #include "llvm/Support/ManagedStatic.h"
  21 #include <vector>
  22 #include <map>
  23
  24 // See PassManagers.h for Pass Manager infrastructure overview.
  25
  26 namespace llvm {
  27
  28 //===----------------------------------------------------------------------===//
  29 // Pass debugging information.  Often it is useful to find out what pass is
  30 // running when a crash occurs in a utility.  When this library is compiled with
  31 // debugging on, a command line option (--debug-pass) is enabled that causes the
  32 // pass name to be printed before it executes.
  33 //
  34
  35 // Different debug levels that can be enabled...
  36 enum PassDebugLevel {
  37   None, Arguments, Structure, Executions, Details
  38 };
  39
  40 static cl::opt<enum PassDebugLevel>
  41 PassDebugging("debug-pass", cl::Hidden,
  42                   cl::desc("Print PassManager debugging information"),
  43                   cl::values(
  44   clEnumVal(None      , "disable debug output"),
  45   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
  46   clEnumVal(Structure , "print pass structure before run()"),
  47   clEnumVal(Executions, "print pass name before it is executed"),
  48   clEnumVal(Details   , "print pass details when it is executed"),
  49                              clEnumValEnd));
  50 } // End of llvm namespace
  51
  52 namespace {
  53
  54 //===----------------------------------------------------------------------===//
  55 // BBPassManager
  56 //
  57 /// BBPassManager manages BasicBlockPass. It batches all the
  58 /// pass together and sequence them to process one basic block before
  59 /// processing next basic block.
  60 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager,
  61                                         public FunctionPass {
  62
  63 public:
  64   BBPassManager(int Depth) : PMDataManager(Depth) { }
  65
  66   /// Execute all of the passes scheduled for execution.  Keep track of
  67   /// whether any of the passes modifies the function, and if so, return true.
  68   bool runOnFunction(Function &F);
  69
  70   /// Pass Manager itself does not invalidate any analysis info.
  71   void getAnalysisUsage(AnalysisUsage &Info) const {
  72     Info.setPreservesAll();
  73   }
  74
  75   bool doInitialization(Module &M);
  76   bool doInitialization(Function &F);
  77   bool doFinalization(Module &M);
  78   bool doFinalization(Function &F);
  79
  80   // Print passes managed by this manager
  81   void dumpPassStructure(unsigned Offset) {
  82     llvm::cerr << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n";
  83     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
  84       BasicBlockPass *BP = getContainedPass(Index);
  85       BP->dumpPassStructure(Offset + 1);
  86       dumpLastUses(BP, Offset+1);
  87     }
  88   }
  89
  90   BasicBlockPass *getContainedPass(unsigned N) {
  91     assert ( N < PassVector.size() && "Pass number out of range!");
  92     BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]);
  93     return BP;
  94   }
  95
  96   virtual PassManagerType getPassManagerType() {
  97     return PMT_BasicBlockPassManager;
  98   }
  99 };
 100
 101 }
 102
 103 namespace llvm {
 104
 105 //===----------------------------------------------------------------------===//
 106 // FunctionPassManagerImpl
 107 //
 108 /// FunctionPassManagerImpl manages FPPassManagers
 109 class FunctionPassManagerImpl : public Pass,
 110                                 public PMDataManager,
 111                                 public PMTopLevelManager {
 112 public:
 113
 114   FunctionPassManagerImpl(int Depth) : PMDataManager(Depth),
 115                                        PMTopLevelManager(TLM_Function) { }
 116
 117   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 118   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 119   /// will be destroyed as well, so there is no need to delete the pass.  This
 120   /// implies that all passes MUST be allocated with 'new'.
 121   void add(Pass *P) {
 122     schedulePass(P);
 123   }
 124
 125   /// run - Execute all of the passes scheduled for execution.  Keep track of
 126   /// whether any of the passes modifies the module, and if so, return true.
 127   bool run(Function &F);
 128
 129   /// doInitialization - Run all of the initializers for the function passes.
 130   ///
 131   bool doInitialization(Module &M);
 132
 133   /// doFinalization - Run all of the initializers for the function passes.
 134   ///
 135   bool doFinalization(Module &M);
 136
 137   /// Pass Manager itself does not invalidate any analysis info.
 138   void getAnalysisUsage(AnalysisUsage &Info) const {
 139     Info.setPreservesAll();
 140   }
 141
 142   inline void addTopLevelPass(Pass *P) {
 143
 144     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
 145
 146       // P is a immutable pass and it will be managed by this
 147       // top level manager. Set up analysis resolver to connect them.
 148       AnalysisResolver *AR = new AnalysisResolver(*this);
 149       P->setResolver(AR);
 150       initializeAnalysisImpl(P);
 151       addImmutablePass(IP);
 152       recordAvailableAnalysis(IP);
 153     } else {
 154       P->assignPassManager(activeStack);
 155     }
 156
 157   }
 158
 159   FPPassManager *getContainedManager(unsigned N) {
 160     assert ( N < PassManagers.size() && "Pass number out of range!");
 161     FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]);
 162     return FP;
 163   }
 164
 165 };
 166
 167 //===----------------------------------------------------------------------===//
 168 // MPPassManager
 169 //
 170 /// MPPassManager manages ModulePasses and function pass managers.
 171 /// It batches all Module passes  passes and function pass managers together and
 172 /// sequence them to process one module.
 173 class MPPassManager : public Pass, public PMDataManager {
 174
 175 public:
 176   MPPassManager(int Depth) : PMDataManager(Depth) { }
 177
 178   /// run - Execute all of the passes scheduled for execution.  Keep track of
 179   /// whether any of the passes modifies the module, and if so, return true.
 180   bool runOnModule(Module &M);
 181
 182   /// Pass Manager itself does not invalidate any analysis info.
 183   void getAnalysisUsage(AnalysisUsage &Info) const {
 184     Info.setPreservesAll();
 185   }
 186
 187   // Print passes managed by this manager
 188   void dumpPassStructure(unsigned Offset) {
 189     llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
 190     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 191       ModulePass *MP = getContainedPass(Index);
 192       MP->dumpPassStructure(Offset + 1);
 193       dumpLastUses(MP, Offset+1);
 194     }
 195   }
 196
 197   ModulePass *getContainedPass(unsigned N) {
 198     assert ( N < PassVector.size() && "Pass number out of range!");
 199     ModulePass *MP = static_cast<ModulePass *>(PassVector[N]);
 200     return MP;
 201   }
 202
 203   virtual PassManagerType getPassManagerType() { return PMT_ModulePassManager; }
 204 };
 205
 206 //===----------------------------------------------------------------------===//
 207 // PassManagerImpl
 208 //
 209 /// PassManagerImpl manages MPPassManagers
 210 class PassManagerImpl : public Pass,
 211                         public PMDataManager,
 212                         public PMTopLevelManager {
 213
 214 public:
 215
 216   PassManagerImpl(int Depth) : PMDataManager(Depth),
 217                                PMTopLevelManager(TLM_Pass) { }
 218
 219   /// add - Add a pass to the queue of passes to run.  This passes ownership of
 220   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 221   /// will be destroyed as well, so there is no need to delete the pass.  This
 222   /// implies that all passes MUST be allocated with 'new'.
 223   void add(Pass *P) {
 224     schedulePass(P);
 225   }
 226
 227   /// run - Execute all of the passes scheduled for execution.  Keep track of
 228   /// whether any of the passes modifies the module, and if so, return true.
 229   bool run(Module &M);
 230
 231   /// Pass Manager itself does not invalidate any analysis info.
 232   void getAnalysisUsage(AnalysisUsage &Info) const {
 233     Info.setPreservesAll();
 234   }
 235
 236   inline void addTopLevelPass(Pass *P) {
 237
 238     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
 239
 240       // P is a immutable pass and it will be managed by this
 241       // top level manager. Set up analysis resolver to connect them.
 242       AnalysisResolver *AR = new AnalysisResolver(*this);
 243       P->setResolver(AR);
 244       initializeAnalysisImpl(P);
 245       addImmutablePass(IP);
 246       recordAvailableAnalysis(IP);
 247     } else {
 248       P->assignPassManager(activeStack);
 249     }
 250
 251   }
 252
 253   MPPassManager *getContainedManager(unsigned N) {
 254     assert ( N < PassManagers.size() && "Pass number out of range!");
 255     MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]);
 256     return MP;
 257   }
 258
 259 };
 260
 261 static TimingInfo *TheTimeInfo;
 262
 263 TimingInfo *getTheTimeInfo() {
 264   return TheTimeInfo;
 265 }
 266
 267 } // End of llvm namespace
 268
 269 //===----------------------------------------------------------------------===//
 270 // PMTopLevelManager implementation
 271
 272 /// Initialize top level manager. Create first pass manager.
 273 PMTopLevelManager::PMTopLevelManager (enum TopLevelManagerType t) {
 274
 275   if (t == TLM_Pass) {
 276     MPPassManager *MPP = new MPPassManager(1);
 277     MPP->setTopLevelManager(this);
 278     addPassManager(MPP);
 279     activeStack.push(MPP);
 280   }
 281   else if (t == TLM_Function) {
 282     FPPassManager *FPP = new FPPassManager(1);
 283     FPP->setTopLevelManager(this);
 284     addPassManager(FPP);
 285     activeStack.push(FPP);
 286   }
 287 }
 288
 289 /// Set pass P as the last user of the given analysis passes.
 290 void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses,
 291                                     Pass *P) {
 292
 293   for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(),
 294          E = AnalysisPasses.end(); I != E; ++I) {
 295     Pass *AP = *I;
 296     LastUser[AP] = P;
 297     // If AP is the last user of other passes then make P last user of
 298     // such passes.
 299     for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
 300            LUE = LastUser.end(); LUI != LUE; ++LUI) {
 301       if (LUI->second == AP)
 302         LastUser[LUI->first] = P;
 303     }
 304   }
 305 }
 306
 307 /// Collect passes whose last user is P
 308 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses,
 309                                             Pass *P) {
 310    for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
 311           LUE = LastUser.end(); LUI != LUE; ++LUI)
 312       if (LUI->second == P)
 313         LastUses.push_back(LUI->first);
 314 }
 315
 316 /// Schedule pass P for execution. Make sure that passes required by
 317 /// P are run before P is run. Update analysis info maintained by
 318 /// the manager. Remove dead passes. This is a recursive function.
 319 void PMTopLevelManager::schedulePass(Pass *P) {
 320
 321   // TODO : Allocate function manager for this pass, other wise required set
 322   // may be inserted into previous function manager
 323
 324   AnalysisUsage AnUsage;
 325   P->getAnalysisUsage(AnUsage);
 326   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 327   for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
 328          E = RequiredSet.end(); I != E; ++I) {
 329
 330     Pass *AnalysisPass = findAnalysisPass(*I);
 331     if (!AnalysisPass) {
 332       // Schedule this analysis run first.
 333       AnalysisPass = (*I)->createPass();
 334       schedulePass(AnalysisPass);
 335     }
 336   }
 337
 338   // Now all required passes are available.
 339   addTopLevelPass(P);
 340 }
 341
 342 /// Find the pass that implements Analysis AID. Search immutable
 343 /// passes and all pass managers. If desired pass is not found
 344 /// then return NULL.
 345 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
 346
 347   Pass *P = NULL;
 348   // Check pass managers
 349   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 350          E = PassManagers.end(); P == NULL && I != E; ++I) {
 351     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 352     assert(PMD && "This is not a PassManager");
 353     P = PMD->findAnalysisPass(AID, false);
 354   }
 355
 356   // Check other pass managers
 357   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
 358          E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
 359     P = (*I)->findAnalysisPass(AID, false);
 360
 361   for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(),
 362          E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
 363     const PassInfo *PI = (*I)->getPassInfo();
 364     if (PI == AID)
 365       P = *I;
 366
 367     // If Pass not found then check the interfaces implemented by Immutable Pass
 368     if (!P) {
 369       const std::vector<const PassInfo*> &ImmPI = PI->getInterfacesImplemented();
 370       if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end())
 371         P = *I;
 372     }
 373   }
 374
 375   return P;
 376 }
 377
 378 // Print passes managed by this top level manager.
 379 void PMTopLevelManager::dumpPasses() const {
 380
 381   if (PassDebugging < Structure)
 382     return;
 383
 384   // Print out the immutable passes
 385   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
 386     ImmutablePasses[i]->dumpPassStructure(0);
 387   }
 388
 389   for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
 390          E = PassManagers.end(); I != E; ++I)
 391     (*I)->dumpPassStructure(1);
 392 }
 393
 394 void PMTopLevelManager::dumpArguments() const {
 395
 396   if (PassDebugging < Arguments)
 397     return;
 398
 399   cerr << "Pass Arguments: ";
 400   for (std::vector<Pass *>::const_iterator I = PassManagers.begin(),
 401          E = PassManagers.end(); I != E; ++I) {
 402     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 403     assert(PMD && "This is not a PassManager");
 404     PMD->dumpPassArguments();
 405   }
 406   cerr << "\n";
 407 }
 408
 409 void PMTopLevelManager::initializeAllAnalysisInfo() {
 410
 411   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 412          E = PassManagers.end(); I != E; ++I) {
 413     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
 414     assert(PMD && "This is not a PassManager");
 415     PMD->initializeAnalysisInfo();
 416   }
 417
 418   // Initailize other pass managers
 419   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
 420          E = IndirectPassManagers.end(); I != E; ++I)
 421     (*I)->initializeAnalysisInfo();
 422 }
 423
 424 /// Destructor
 425 PMTopLevelManager::~PMTopLevelManager() {
 426   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
 427          E = PassManagers.end(); I != E; ++I)
 428     delete *I;
 429
 430   for (std::vector<ImmutablePass *>::iterator
 431          I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
 432     delete *I;
 433
 434   PassManagers.clear();
 435 }
 436
 437 //===----------------------------------------------------------------------===//
 438 // PMDataManager implementation
 439
 440 /// Return true IFF pass P's required analysis set does not required new
 441 /// manager.
 442 bool PMDataManager::manageablePass(Pass *P) {
 443
 444   // TODO
 445   // If this pass is not preserving information that is required by a
 446   // pass maintained by higher level pass manager then do not insert
 447   // this pass into current manager. Use new manager. For example,
 448   // For example, If FunctionPass F is not preserving ModulePass Info M1
 449   // that is used by another ModulePass M2 then do not insert F in
 450   // current function pass manager.
 451   return true;
 452 }
 453
 454 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 455 void PMDataManager::recordAvailableAnalysis(Pass *P) {
 456
 457   if (const PassInfo *PI = P->getPassInfo()) {
 458     AvailableAnalysis[PI] = P;
 459
 460     //This pass is the current implementation of all of the interfaces it
 461     //implements as well.
 462     const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
 463     for (unsigned i = 0, e = II.size(); i != e; ++i)
 464       AvailableAnalysis[II[i]] = P;
 465   }
 466 }
 467
 468 /// Remove Analyss not preserved by Pass P
 469 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
 470   AnalysisUsage AnUsage;
 471   P->getAnalysisUsage(AnUsage);
 472
 473   if (AnUsage.getPreservesAll())
 474     return;
 475
 476   const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 477   for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
 478          E = AvailableAnalysis.end(); I != E; ) {
 479     std::map<AnalysisID, Pass*>::iterator Info = I++;
 480     if (std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) ==
 481         PreservedSet.end()) {
 482       // Remove this analysis
 483       if (!dynamic_cast<ImmutablePass*>(Info->second))
 484         AvailableAnalysis.erase(Info);
 485     }
 486   }
 487 }
 488
 489 /// Remove analysis passes that are not used any longer
 490 void PMDataManager::removeDeadPasses(Pass *P, std::string &Msg) {
 491
 492   std::vector<Pass *> DeadPasses;
 493   TPM->collectLastUses(DeadPasses, P);
 494
 495   for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
 496          E = DeadPasses.end(); I != E; ++I) {
 497
 498     std::string Msg1 = "  Freeing Pass '";
 499     dumpPassInfo(*I, Msg1, Msg);
 500
 501     if (TheTimeInfo) TheTimeInfo->passStarted(P);
 502     (*I)->releaseMemory();
 503     if (TheTimeInfo) TheTimeInfo->passEnded(P);
 504
 505     std::map<AnalysisID, Pass*>::iterator Pos =
 506       AvailableAnalysis.find((*I)->getPassInfo());
 507
 508     // It is possible that pass is already removed from the AvailableAnalysis
 509     if (Pos != AvailableAnalysis.end())
 510       AvailableAnalysis.erase(Pos);
 511   }
 512 }
 513
 514 /// Add pass P into the PassVector. Update
 515 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 516 void PMDataManager::add(Pass *P,
 517                         bool ProcessAnalysis) {
 518
 519   // This manager is going to manage pass P. Set up analysis resolver
 520   // to connect them.
 521   AnalysisResolver *AR = new AnalysisResolver(*this);
 522   P->setResolver(AR);
 523
 524   if (ProcessAnalysis) {
 525
 526     // At the moment, this pass is the last user of all required passes.
 527     std::vector<Pass *> LastUses;
 528     std::vector<Pass *> RequiredPasses;
 529     unsigned PDepth = this->getDepth();
 530
 531     collectRequiredAnalysisPasses(RequiredPasses, P);
 532     for (std::vector<Pass *>::iterator I = RequiredPasses.begin(),
 533            E = RequiredPasses.end(); I != E; ++I) {
 534       Pass *PRequired = *I;
 535       unsigned RDepth = 0;
 536
 537       PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
 538       RDepth = DM.getDepth();
 539
 540       if (PDepth == RDepth)
 541         LastUses.push_back(PRequired);
 542       else if (PDepth >  RDepth) {
 543         // Let the parent claim responsibility of last use
 544         TransferLastUses.push_back(PRequired);
 545       } else {
 546         // Note : This feature is not yet implemented
 547         assert (0 &&
 548                 "Unable to handle Pass that requires lower level Analysis pass");
 549       }
 550     }
 551
 552     // Set P as P's last user until someone starts using P.
 553     // However, if P is a Pass Manager then it does not need
 554     // to record its last user.
 555     if (!dynamic_cast<PMDataManager *>(P))
 556       LastUses.push_back(P);
 557     TPM->setLastUser(LastUses, P);
 558
 559     // Take a note of analysis required and made available by this pass.
 560     // Remove the analysis not preserved by this pass
 561     removeNotPreservedAnalysis(P);
 562     recordAvailableAnalysis(P);
 563   }
 564
 565   // Add pass
 566   PassVector.push_back(P);
 567 }
 568
 569 /// Populate RequiredPasses with the analysis pass that are required by
 570 /// pass P.
 571 void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP,
 572                                                   Pass *P) {
 573   AnalysisUsage AnUsage;
 574   P->getAnalysisUsage(AnUsage);
 575   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 576   for (std::vector<AnalysisID>::const_iterator
 577          I = RequiredSet.begin(), E = RequiredSet.end();
 578        I != E; ++I) {
 579     Pass *AnalysisPass = findAnalysisPass(*I, true);
 580     assert (AnalysisPass && "Analysis pass is not available");
 581     RP.push_back(AnalysisPass);
 582   }
 583
 584   const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
 585   for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
 586          E = IDs.end(); I != E; ++I) {
 587     Pass *AnalysisPass = findAnalysisPass(*I, true);
 588     assert (AnalysisPass && "Analysis pass is not available");
 589     RP.push_back(AnalysisPass);
 590   }
 591 }
 592
 593 // All Required analyses should be available to the pass as it runs!  Here
 594 // we fill in the AnalysisImpls member of the pass so that it can
 595 // successfully use the getAnalysis() method to retrieve the
 596 // implementations it needs.
 597 //
 598 void PMDataManager::initializeAnalysisImpl(Pass *P) {
 599   AnalysisUsage AnUsage;
 600   P->getAnalysisUsage(AnUsage);
 601
 602   for (std::vector<const PassInfo *>::const_iterator
 603          I = AnUsage.getRequiredSet().begin(),
 604          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
 605     Pass *Impl = findAnalysisPass(*I, true);
 606     if (Impl == 0)
 607       assert(0 && "Analysis used but not available!");
 608     AnalysisResolver *AR = P->getResolver();
 609     AR->addAnalysisImplsPair(*I, Impl);
 610   }
 611 }
 612
 613 /// Find the pass that implements Analysis AID. If desired pass is not found
 614 /// then return NULL.
 615 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
 616
 617   // Check if AvailableAnalysis map has one entry.
 618   std::map<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
 619
 620   if (I != AvailableAnalysis.end())
 621     return I->second;
 622
 623   // Search Parents through TopLevelManager
 624   if (SearchParent)
 625     return TPM->findAnalysisPass(AID);
 626
 627   return NULL;
 628 }
 629
 630 // Print list of passes that are last used by P.
 631 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
 632
 633   std::vector<Pass *> LUses;
 634
 635   assert (TPM && "Top Level Manager is missing");
 636   TPM->collectLastUses(LUses, P);
 637
 638   for (std::vector<Pass *>::iterator I = LUses.begin(),
 639          E = LUses.end(); I != E; ++I) {
 640     llvm::cerr << "--" << std::string(Offset*2, ' ');
 641     (*I)->dumpPassStructure(0);
 642   }
 643 }
 644
 645 void PMDataManager::dumpPassArguments() const {
 646   for(std::vector<Pass *>::const_iterator I = PassVector.begin(),
 647         E = PassVector.end(); I != E; ++I) {
 648     if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
 649       PMD->dumpPassArguments();
 650     else
 651       if (const PassInfo *PI = (*I)->getPassInfo())
 652         if (!PI->isAnalysisGroup())
 653           cerr << " -" << PI->getPassArgument();
 654   }
 655 }
 656
 657 void PMDataManager:: dumpPassInfo(Pass *P,  std::string &Msg1,
 658                                   std::string &Msg2) const {
 659   if (PassDebugging < Executions)
 660     return;
 661   cerr << (void*)this << std::string(getDepth()*2+1, ' ');
 662   cerr << Msg1;
 663   cerr << P->getPassName();
 664   cerr << Msg2;
 665 }
 666
 667 void PMDataManager::dumpAnalysisSetInfo(const char *Msg, Pass *P,
 668                                         const std::vector<AnalysisID> &Set)
 669   const {
 670   if (PassDebugging >= Details && !Set.empty()) {
 671     cerr << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:";
 672       for (unsigned i = 0; i != Set.size(); ++i) {
 673         if (i) cerr << ",";
 674         cerr << " " << Set[i]->getPassName();
 675       }
 676       cerr << "\n";
 677   }
 678 }
 679
 680 // Destructor
 681 PMDataManager::~PMDataManager() {
 682
 683   for (std::vector<Pass *>::iterator I = PassVector.begin(),
 684          E = PassVector.end(); I != E; ++I)
 685     delete *I;
 686
 687   PassVector.clear();
 688 }
 689
 690 //===----------------------------------------------------------------------===//
 691 // NOTE: Is this the right place to define this method ?
 692 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
 693 Pass *AnalysisResolver::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
 694   return PM.findAnalysisPass(ID, dir);
 695 }
 696
 697 //===----------------------------------------------------------------------===//
 698 // BBPassManager implementation
 699
 700 /// Execute all of the passes scheduled for execution by invoking
 701 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 702 /// the function, and if so, return true.
 703 bool
 704 BBPassManager::runOnFunction(Function &F) {
 705
 706   if (F.isExternal())
 707     return false;
 708
 709   bool Changed = doInitialization(F);
 710
 711   std::string Msg1 = "Executing Pass '";
 712   std::string Msg3 = "' Made Modification '";
 713
 714   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 715     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 716       BasicBlockPass *BP = getContainedPass(Index);
 717       AnalysisUsage AnUsage;
 718       BP->getAnalysisUsage(AnUsage);
 719
 720       std::string Msg2 = "' on BasicBlock '" + (*I).getName() + "'...\n";
 721       dumpPassInfo(BP, Msg1, Msg2);
 722       dumpAnalysisSetInfo("Required", BP, AnUsage.getRequiredSet());
 723
 724       initializeAnalysisImpl(BP);
 725
 726       if (TheTimeInfo) TheTimeInfo->passStarted(BP);
 727       Changed |= BP->runOnBasicBlock(*I);
 728       if (TheTimeInfo) TheTimeInfo->passEnded(BP);
 729
 730       if (Changed)
 731         dumpPassInfo(BP, Msg3, Msg2);
 732       dumpAnalysisSetInfo("Preserved", BP, AnUsage.getPreservedSet());
 733
 734       removeNotPreservedAnalysis(BP);
 735       recordAvailableAnalysis(BP);
 736       removeDeadPasses(BP, Msg2);
 737     }
 738   return Changed |= doFinalization(F);
 739 }
 740
 741 // Implement doInitialization and doFinalization
 742 inline bool BBPassManager::doInitialization(Module &M) {
 743   bool Changed = false;
 744
 745   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 746     BasicBlockPass *BP = getContainedPass(Index);
 747     Changed |= BP->doInitialization(M);
 748   }
 749
 750   return Changed;
 751 }
 752
 753 inline bool BBPassManager::doFinalization(Module &M) {
 754   bool Changed = false;
 755
 756   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 757     BasicBlockPass *BP = getContainedPass(Index);
 758     Changed |= BP->doFinalization(M);
 759   }
 760
 761   return Changed;
 762 }
 763
 764 inline bool BBPassManager::doInitialization(Function &F) {
 765   bool Changed = false;
 766
 767   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 768     BasicBlockPass *BP = getContainedPass(Index);
 769     Changed |= BP->doInitialization(F);
 770   }
 771
 772   return Changed;
 773 }
 774
 775 inline bool BBPassManager::doFinalization(Function &F) {
 776   bool Changed = false;
 777
 778   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 779     BasicBlockPass *BP = getContainedPass(Index);
 780     Changed |= BP->doFinalization(F);
 781   }
 782
 783   return Changed;
 784 }
 785
 786
 787 //===----------------------------------------------------------------------===//
 788 // FunctionPassManager implementation
 789
 790 /// Create new Function pass manager
 791 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
 792   FPM = new FunctionPassManagerImpl(0);
 793   // FPM is the top level manager.
 794   FPM->setTopLevelManager(FPM);
 795
 796   PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
 797   AnalysisResolver *AR = new AnalysisResolver(*PMD);
 798   FPM->setResolver(AR);
 799
 800   MP = P;
 801 }
 802
 803 FunctionPassManager::~FunctionPassManager() {
 804   delete FPM;
 805 }
 806
 807 /// add - Add a pass to the queue of passes to run.  This passes
 808 /// ownership of the Pass to the PassManager.  When the
 809 /// PassManager_X is destroyed, the pass will be destroyed as well, so
 810 /// there is no need to delete the pass. (TODO delete passes.)
 811 /// This implies that all passes MUST be allocated with 'new'.
 812 void FunctionPassManager::add(Pass *P) {
 813   FPM->add(P);
 814 }
 815
 816 /// run - Execute all of the passes scheduled for execution.  Keep
 817 /// track of whether any of the passes modifies the function, and if
 818 /// so, return true.
 819 ///
 820 bool FunctionPassManager::run(Function &F) {
 821   std::string errstr;
 822   if (MP->materializeFunction(&F, &errstr)) {
 823     cerr << "Error reading bytecode file: " << errstr << "\n";
 824     abort();
 825   }
 826   return FPM->run(F);
 827 }
 828
 829
 830 /// doInitialization - Run all of the initializers for the function passes.
 831 ///
 832 bool FunctionPassManager::doInitialization() {
 833   return FPM->doInitialization(*MP->getModule());
 834 }
 835
 836 /// doFinalization - Run all of the initializers for the function passes.
 837 ///
 838 bool FunctionPassManager::doFinalization() {
 839   return FPM->doFinalization(*MP->getModule());
 840 }
 841
 842 //===----------------------------------------------------------------------===//
 843 // FunctionPassManagerImpl implementation
 844 //
 845 inline bool FunctionPassManagerImpl::doInitialization(Module &M) {
 846   bool Changed = false;
 847
 848   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 849     FPPassManager *FP = getContainedManager(Index);
 850     Changed |= FP->doInitialization(M);
 851   }
 852
 853   return Changed;
 854 }
 855
 856 inline bool FunctionPassManagerImpl::doFinalization(Module &M) {
 857   bool Changed = false;
 858
 859   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 860     FPPassManager *FP = getContainedManager(Index);
 861     Changed |= FP->doFinalization(M);
 862   }
 863
 864   return Changed;
 865 }
 866
 867 // Execute all the passes managed by this top level manager.
 868 // Return true if any function is modified by a pass.
 869 bool FunctionPassManagerImpl::run(Function &F) {
 870
 871   bool Changed = false;
 872
 873   TimingInfo::createTheTimeInfo();
 874
 875   dumpArguments();
 876   dumpPasses();
 877
 878   initializeAllAnalysisInfo();
 879   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
 880     FPPassManager *FP = getContainedManager(Index);
 881     Changed |= FP->runOnFunction(F);
 882   }
 883   return Changed;
 884 }
 885
 886 //===----------------------------------------------------------------------===//
 887 // FPPassManager implementation
 888
 889 /// Print passes managed by this manager
 890 void FPPassManager::dumpPassStructure(unsigned Offset) {
 891   llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
 892   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 893     FunctionPass *FP = getContainedPass(Index);
 894     FP->dumpPassStructure(Offset + 1);
 895     dumpLastUses(FP, Offset+1);
 896   }
 897 }
 898
 899
 900 /// Execute all of the passes scheduled for execution by invoking
 901 /// runOnFunction method.  Keep track of whether any of the passes modifies
 902 /// the function, and if so, return true.
 903 bool FPPassManager::runOnFunction(Function &F) {
 904
 905   bool Changed = false;
 906
 907   if (F.isExternal())
 908     return false;
 909
 910   std::string Msg1 = "Executing Pass '";
 911   std::string Msg3 = "' Made Modification '";
 912
 913   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 914     FunctionPass *FP = getContainedPass(Index);
 915
 916     AnalysisUsage AnUsage;
 917     FP->getAnalysisUsage(AnUsage);
 918
 919     std::string Msg2 = "' on Function '" + F.getName() + "'...\n";
 920     dumpPassInfo(FP, Msg1, Msg2);
 921     dumpAnalysisSetInfo("Required", FP, AnUsage.getRequiredSet());
 922
 923     initializeAnalysisImpl(FP);
 924
 925     if (TheTimeInfo) TheTimeInfo->passStarted(FP);
 926     Changed |= FP->runOnFunction(F);
 927     if (TheTimeInfo) TheTimeInfo->passEnded(FP);
 928
 929     if (Changed)
 930       dumpPassInfo(FP, Msg3, Msg2);
 931     dumpAnalysisSetInfo("Preserved", FP, AnUsage.getPreservedSet());
 932
 933     removeNotPreservedAnalysis(FP);
 934     recordAvailableAnalysis(FP);
 935     removeDeadPasses(FP, Msg2);
 936   }
 937   return Changed;
 938 }
 939
 940 bool FPPassManager::runOnModule(Module &M) {
 941
 942   bool Changed = doInitialization(M);
 943
 944   for(Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 945     this->runOnFunction(*I);
 946
 947   return Changed |= doFinalization(M);
 948 }
 949
 950 inline bool FPPassManager::doInitialization(Module &M) {
 951   bool Changed = false;
 952
 953   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 954     FunctionPass *FP = getContainedPass(Index);
 955     Changed |= FP->doInitialization(M);
 956   }
 957
 958   return Changed;
 959 }
 960
 961 inline bool FPPassManager::doFinalization(Module &M) {
 962   bool Changed = false;
 963
 964   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 965     FunctionPass *FP = getContainedPass(Index);
 966     Changed |= FP->doFinalization(M);
 967   }
 968
 969   return Changed;
 970 }
 971
 972 //===----------------------------------------------------------------------===//
 973 // MPPassManager implementation
 974
 975 /// Execute all of the passes scheduled for execution by invoking
 976 /// runOnModule method.  Keep track of whether any of the passes modifies
 977 /// the module, and if so, return true.
 978 bool
 979 MPPassManager::runOnModule(Module &M) {
 980   bool Changed = false;
 981
 982   std::string Msg1 = "Executing Pass '";
 983   std::string Msg3 = "' Made Modification '";
 984
 985   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
 986     ModulePass *MP = getContainedPass(Index);
 987
 988     AnalysisUsage AnUsage;
 989     MP->getAnalysisUsage(AnUsage);
 990
 991     std::string Msg2 = "' on Module '" + M.getModuleIdentifier() + "'...\n";
 992     dumpPassInfo(MP, Msg1, Msg2);
 993     dumpAnalysisSetInfo("Required", MP, AnUsage.getRequiredSet());
 994
 995     initializeAnalysisImpl(MP);
 996
 997     if (TheTimeInfo) TheTimeInfo->passStarted(MP);
 998     Changed |= MP->runOnModule(M);
 999     if (TheTimeInfo) TheTimeInfo->passEnded(MP);
1000
1001     if (Changed)
1002       dumpPassInfo(MP, Msg3, Msg2);
1003     dumpAnalysisSetInfo("Preserved", MP, AnUsage.getPreservedSet());
1004
1005     removeNotPreservedAnalysis(MP);
1006     recordAvailableAnalysis(MP);
1007     removeDeadPasses(MP, Msg2);
1008   }
1009   return Changed;
1010 }
1011
1012 //===----------------------------------------------------------------------===//
1013 // PassManagerImpl implementation
1014 //
1015 /// run - Execute all of the passes scheduled for execution.  Keep track of
1016 /// whether any of the passes modifies the module, and if so, return true.
1017 bool PassManagerImpl::run(Module &M) {
1018
1019   bool Changed = false;
1020
1021   TimingInfo::createTheTimeInfo();
1022
1023   dumpArguments();
1024   dumpPasses();
1025
1026   initializeAllAnalysisInfo();
1027   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
1028     MPPassManager *MP = getContainedManager(Index);
1029     Changed |= MP->runOnModule(M);
1030   }
1031   return Changed;
1032 }
1033
1034 //===----------------------------------------------------------------------===//
1035 // PassManager implementation
1036
1037 /// Create new pass manager
1038 PassManager::PassManager() {
1039   PM = new PassManagerImpl(0);
1040   // PM is the top level manager
1041   PM->setTopLevelManager(PM);
1042 }
1043
1044 PassManager::~PassManager() {
1045   delete PM;
1046 }
1047
1048 /// add - Add a pass to the queue of passes to run.  This passes ownership of
1049 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
1050 /// will be destroyed as well, so there is no need to delete the pass.  This
1051 /// implies that all passes MUST be allocated with 'new'.
1052 void
1053 PassManager::add(Pass *P) {
1054   PM->add(P);
1055 }
1056
1057 /// run - Execute all of the passes scheduled for execution.  Keep track of
1058 /// whether any of the passes modifies the module, and if so, return true.
1059 bool
1060 PassManager::run(Module &M) {
1061   return PM->run(M);
1062 }
1063
1064 //===----------------------------------------------------------------------===//
1065 // TimingInfo Class - This class is used to calculate information about the
1066 // amount of time each pass takes to execute.  This only happens with
1067 // -time-passes is enabled on the command line.
1068 //
1069 bool llvm::TimePassesIsEnabled = false;
1070 static cl::opt<bool,true>
1071 EnableTiming("time-passes", cl::location(TimePassesIsEnabled),
1072             cl::desc("Time each pass, printing elapsed time for each on exit"));
1073
1074 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to
1075 // a non null value (if the -time-passes option is enabled) or it leaves it
1076 // null.  It may be called multiple times.
1077 void TimingInfo::createTheTimeInfo() {
1078   if (!TimePassesIsEnabled || TheTimeInfo) return;
1079
1080   // Constructed the first time this is called, iff -time-passes is enabled.
1081   // This guarantees that the object will be constructed before static globals,
1082   // thus it will be destroyed before them.
1083   static ManagedStatic<TimingInfo> TTI;
1084   TheTimeInfo = &*TTI;
1085 }
1086
1087 //===----------------------------------------------------------------------===//
1088 // PMStack implementation
1089 //
1090
1091 // Pop Pass Manager from the stack and clear its analysis info.
1092 void PMStack::pop() {
1093
1094   PMDataManager *Top = this->top();
1095   Top->initializeAnalysisInfo();
1096
1097   S.pop_back();
1098 }
1099
1100 // Push PM on the stack and set its top level manager.
1101 void PMStack::push(Pass *P) {
1102
1103   PMDataManager *Top = NULL;
1104   PMDataManager *PM = dynamic_cast<PMDataManager *>(P);
1105   assert (PM && "Unable to push. Pass Manager expected");
1106
1107   if (this->empty()) {
1108     Top = PM;
1109   }
1110   else {
1111     Top = this->top();
1112     PMTopLevelManager *TPM = Top->getTopLevelManager();
1113
1114     assert (TPM && "Unable to find top level manager");
1115     TPM->addIndirectPassManager(PM);
1116     PM->setTopLevelManager(TPM);
1117   }
1118
1119   AnalysisResolver *AR = new AnalysisResolver(*Top);
1120   P->setResolver(AR);
1121
1122   S.push_back(PM);
1123 }
1124
1125 // Dump content of the pass manager stack.
1126 void PMStack::dump() {
1127   for(std::deque<PMDataManager *>::iterator I = S.begin(),
1128         E = S.end(); I != E; ++I) {
1129     Pass *P = dynamic_cast<Pass *>(*I);
1130     printf ("%s ", P->getPassName());
1131   }
1132   if (!S.empty())
1133     printf ("\n");
1134 }
1135
1136 // Walk Pass Manager stack and set LastUse markers if any
1137 // manager is transfering this priviledge to its parent manager
1138 void PMStack::handleLastUserOverflow() {
1139
1140   for(PMStack::iterator I = this->begin(), E = this->end(); I != E;) {
1141
1142     PMDataManager *Child = *I++;
1143     if (I != E) {
1144       PMDataManager *Parent = *I++;
1145       PMTopLevelManager *TPM = Parent->getTopLevelManager();
1146       std::vector<Pass *> &TLU = Child->getTransferredLastUses();
1147       if (!TLU.empty()) {
1148         Pass *P = dynamic_cast<Pass *>(Parent);
1149         TPM->setLastUser(TLU, P);
1150       }
1151     }
1152   }
1153 }
1154
1155 /// Find appropriate Module Pass Manager in the PM Stack and
1156 /// add self into that manager.
1157 void ModulePass::assignPassManager(PMStack &PMS,
1158                                    PassManagerType PreferredType) {
1159
1160   // Find Module Pass Manager
1161   while(!PMS.empty()) {
1162     PassManagerType TopPMType = PMS.top()->getPassManagerType();
1163     if (TopPMType == PreferredType)
1164       break; // We found desired pass manager
1165     else if (TopPMType > PMT_ModulePassManager)
1166       PMS.pop();    // Pop children pass managers
1167     else
1168       break;
1169   }
1170
1171   PMS.top()->add(this);
1172 }
1173
1174 /// Find appropriate Function Pass Manager or Call Graph Pass Manager
1175 /// in the PM Stack and add self into that manager.
1176 void FunctionPass::assignPassManager(PMStack &PMS,
1177                                      PassManagerType PreferredType) {
1178
1179   // Find Module Pass Manager (TODO : Or Call Graph Pass Manager)
1180   while(!PMS.empty()) {
1181     if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager)
1182       PMS.pop();
1183     else
1184       break;
1185   }
1186   FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top());
1187
1188   // Create new Function Pass Manager
1189   if (!FPP) {
1190     assert(!PMS.empty() && "Unable to create Function Pass Manager");
1191     PMDataManager *PMD = PMS.top();
1192
1193     // [1] Create new Function Pass Manager
1194     FPP = new FPPassManager(PMD->getDepth() + 1);
1195
1196     // [2] Set up new manager's top level manager
1197     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1198     TPM->addIndirectPassManager(FPP);
1199
1200     // [3] Assign manager to manage this new manager. This may create
1201     // and push new managers into PMS
1202     Pass *P = dynamic_cast<Pass *>(FPP);
1203
1204     // If Call Graph Pass Manager is active then use it to manage
1205     // this new Function Pass manager.
1206     if (PMD->getPassManagerType() == PMT_CallGraphPassManager)
1207       P->assignPassManager(PMS, PMT_CallGraphPassManager);
1208     else
1209       P->assignPassManager(PMS);
1210
1211     // [4] Push new manager into PMS
1212     PMS.push(FPP);
1213   }
1214
1215   // Assign FPP as the manager of this pass.
1216   FPP->add(this);
1217 }
1218
1219 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager
1220 /// in the PM Stack and add self into that manager.
1221 void BasicBlockPass::assignPassManager(PMStack &PMS,
1222                                        PassManagerType PreferredType) {
1223
1224   BBPassManager *BBP = NULL;
1225
1226   // Basic Pass Manager is a leaf pass manager. It does not handle
1227   // any other pass manager.
1228   if (!PMS.empty()) {
1229     BBP = dynamic_cast<BBPassManager *>(PMS.top());
1230   }
1231
1232   // If leaf manager is not Basic Block Pass manager then create new
1233   // basic Block Pass manager.
1234
1235   if (!BBP) {
1236     assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager");
1237     PMDataManager *PMD = PMS.top();
1238
1239     // [1] Create new Basic Block Manager
1240     BBP = new BBPassManager(PMD->getDepth() + 1);
1241
1242     // [2] Set up new manager's top level manager
1243     // Basic Block Pass Manager does not live by itself
1244     PMTopLevelManager *TPM = PMD->getTopLevelManager();
1245     TPM->addIndirectPassManager(BBP);
1246
1247     // [3] Assign manager to manage this new manager. This may create
1248     // and push new managers into PMS
1249     Pass *P = dynamic_cast<Pass *>(BBP);
1250     P->assignPassManager(PMS);
1251
1252     // [4] Push new manager into PMS
1253     PMS.push(BBP);
1254   }
1255
1256   // Assign BBP as the manager of this pass.
1257   BBP->add(this);
1258 }
1259
1260