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