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