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