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