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 all passes collected in pass queue using add(). Add all the
 164   /// schedule passes into various manager's queue using addPass().
 165   void schedulePasses();
 166
 167   // Collection of pass managers
 168   std::vector<ModulePassManager_New *> PassManagers;
 169
 170   // Active Pass Manager
 171   ModulePassManager_New *activeManager;
 172 };
 173
 174 } // End of llvm namespace
 175
 176 // CommonPassManagerImpl implementation
 177
 178 /// Return true IFF pass P's required analysis set does not required new
 179 /// manager.
 180 bool CommonPassManagerImpl::manageablePass(Pass *P) {
 181
 182   AnalysisUsage AnUsage;
 183   P->getAnalysisUsage(AnUsage);
 184
 185   // If this pass is not preserving information that is required by the other
 186   // passes managed by this manager then use new manager
 187   if (!AnUsage.getPreservesAll()) {
 188     const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 189     for (std::vector<AnalysisID>::iterator I = RequiredAnalysis.begin(),
 190            E = RequiredAnalysis.end(); I != E; ++I) {
 191       if (std::find(PreservedSet.begin(), PreservedSet.end(), *I) ==
 192           PreservedSet.end())
 193         // This analysis is not preserved. Need new manager.
 194         return false;
 195     }
 196   }
 197   return true;
 198 }
 199
 200 /// Return true IFF AnalysisID AID is currently available.
 201 bool CommonPassManagerImpl::analysisCurrentlyAvailable(AnalysisID AID) {
 202
 203   // TODO
 204   return false;
 205 }
 206
 207 /// Augment RequiredAnalysis by adding analysis required by pass P.
 208 void CommonPassManagerImpl::noteDownRequiredAnalysis(Pass *P) {
 209   AnalysisUsage AnUsage;
 210   P->getAnalysisUsage(AnUsage);
 211   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
 212
 213   // FIXME: What about duplicates ?
 214   RequiredAnalysis.insert(RequiredAnalysis.end(), RequiredSet.begin(),
 215                           RequiredSet.end());
 216 }
 217
 218 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 219 void CommonPassManagerImpl::noteDownAvailableAnalysis(Pass *P) {
 220
 221   if (const PassInfo *PI = P->getPassInfo()) {
 222     AvailableAnalysis.insert(PI);
 223
 224     //TODO This pass is the current implementation of all of the interfaces it
 225     //TODO implements as well.
 226     //TODO
 227     //TODO const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
 228     //TODO for (unsigned i = 0, e = II.size(); i != e; ++i)
 229     //TODO CurrentAnalyses[II[i]] = P;
 230   }
 231 }
 232
 233 /// Remove Analyss not preserved by Pass P
 234 void CommonPassManagerImpl::removeNotPreservedAnalysis(Pass *P) {
 235   AnalysisUsage AnUsage;
 236   P->getAnalysisUsage(AnUsage);
 237   const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
 238
 239   for (std::set<AnalysisID>::iterator I = AvailableAnalysis.begin(),
 240          E = AvailableAnalysis.end(); I != E; ++I ) {
 241     if (std::find(PreservedSet.begin(), PreservedSet.end(), *I) ==
 242         PreservedSet.end()) {
 243       // Remove this analysis
 244       std::set<AnalysisID>::iterator J = I++;
 245       AvailableAnalysis.erase(J);
 246     }
 247   }
 248 }
 249
 250 /// Add pass P into the PassVector. Update RequiredAnalysis and
 251 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 252 void CommonPassManagerImpl::addPassToManager (Pass *P,
 253                                               bool ProcessAnalysis) {
 254
 255   if (ProcessAnalysis) {
 256     // Take a note of analysis required and made available by this pass
 257     noteDownRequiredAnalysis(P);
 258     noteDownAvailableAnalysis(P);
 259
 260     // Remove the analysis not preserved by this pass
 261     removeNotPreservedAnalysis(P);
 262   }
 263
 264   // Add pass
 265   PassVector.push_back(P);
 266 }
 267
 268 /// BasicBlockPassManager implementation
 269
 270 /// Add pass P into PassVector and return true. If this pass is not
 271 /// manageable by this manager then return false.
 272 bool
 273 BasicBlockPassManager_New::addPass(Pass *P) {
 274
 275   BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
 276   if (!BP)
 277     return false;
 278
 279   // If this pass does not preserve anlysis that is used by other passes
 280   // managed by this manager than it is not a suiable pass for this manager.
 281   if (!manageablePass(P))
 282     return false;
 283
 284   addPassToManager (BP);
 285
 286   return true;
 287 }
 288
 289 /// Execute all of the passes scheduled for execution by invoking
 290 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies
 291 /// the function, and if so, return true.
 292 bool
 293 BasicBlockPassManager_New::runOnFunction(Function &F) {
 294
 295   bool Changed = false;
 296   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 297     for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 298            e = passVectorEnd(); itr != e; ++itr) {
 299       Pass *P = *itr;
 300       BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
 301       Changed |= BP->runOnBasicBlock(*I);
 302     }
 303   return Changed;
 304 }
 305
 306 // FunctionPassManager_New implementation
 307 /// Create new Function pass manager
 308 FunctionPassManager_New::FunctionPassManager_New() {
 309   FPM = new FunctionPassManagerImpl_New();
 310 }
 311
 312 /// add - Add a pass to the queue of passes to run.  This passes
 313 /// ownership of the Pass to the PassManager.  When the
 314 /// PassManager_X is destroyed, the pass will be destroyed as well, so
 315 /// there is no need to delete the pass. (TODO delete passes.)
 316 /// This implies that all passes MUST be allocated with 'new'.
 317 void
 318 FunctionPassManager_New::add(Pass *P) {
 319   FPM->add(P);
 320 }
 321
 322 /// Execute all of the passes scheduled for execution.  Keep
 323 /// track of whether any of the passes modifies the function, and if
 324 /// so, return true.
 325 bool
 326 FunctionPassManager_New::runOnModule(Module &M) {
 327   return FPM->runOnModule(M);
 328 }
 329
 330 // FunctionPassManagerImpl_New implementation
 331
 332 // FunctionPassManager
 333
 334 /// Add pass P into the pass manager queue. If P is a BasicBlockPass then
 335 /// either use it into active basic block pass manager or create new basic
 336 /// block pass manager to handle pass P.
 337 bool
 338 FunctionPassManagerImpl_New::addPass(Pass *P) {
 339
 340   // If P is a BasicBlockPass then use BasicBlockPassManager_New.
 341   if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) {
 342
 343     if (!activeBBPassManager
 344         || !activeBBPassManager->addPass(BP)) {
 345
 346       activeBBPassManager = new BasicBlockPassManager_New();
 347       addPassToManager(activeBBPassManager, false);
 348       if (!activeBBPassManager->addPass(BP))
 349         assert(0 && "Unable to add Pass");
 350     }
 351     return true;
 352   }
 353
 354   FunctionPass *FP = dynamic_cast<FunctionPass *>(P);
 355   if (!FP)
 356     return false;
 357
 358   // If this pass does not preserve anlysis that is used by other passes
 359   // managed by this manager than it is not a suiable pass for this manager.
 360   if (!manageablePass(P))
 361     return false;
 362
 363   addPassToManager (FP);
 364   activeBBPassManager = NULL;
 365   return true;
 366 }
 367
 368 /// Execute all of the passes scheduled for execution by invoking
 369 /// runOnFunction method.  Keep track of whether any of the passes modifies
 370 /// the function, and if so, return true.
 371 bool
 372 FunctionPassManagerImpl_New::runOnModule(Module &M) {
 373
 374   bool Changed = false;
 375   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 376     for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 377            e = passVectorEnd(); itr != e; ++itr) {
 378       Pass *P = *itr;
 379       FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
 380       Changed |= FP->runOnFunction(*I);
 381     }
 382   return Changed;
 383 }
 384
 385
 386 // ModulePassManager implementation
 387
 388 /// Add P into pass vector if it is manageble. If P is a FunctionPass
 389 /// then use FunctionPassManagerImpl_New to manage it. Return false if P
 390 /// is not manageable by this manager.
 391 bool
 392 ModulePassManager_New::addPass(Pass *P) {
 393
 394   // If P is FunctionPass then use function pass maanager.
 395   if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) {
 396
 397     activeFunctionPassManager = NULL;
 398
 399     if (!activeFunctionPassManager
 400         || !activeFunctionPassManager->addPass(P)) {
 401
 402       activeFunctionPassManager = new FunctionPassManagerImpl_New();
 403       addPassToManager(activeFunctionPassManager, false);
 404       if (!activeFunctionPassManager->addPass(FP))
 405         assert(0 && "Unable to add pass");
 406     }
 407     return true;
 408   }
 409
 410   ModulePass *MP = dynamic_cast<ModulePass *>(P);
 411   if (!MP)
 412     return false;
 413
 414   // If this pass does not preserve anlysis that is used by other passes
 415   // managed by this manager than it is not a suiable pass for this manager.
 416   if (!manageablePass(P))
 417     return false;
 418
 419   addPassToManager(MP);
 420   activeFunctionPassManager = NULL;
 421   return true;
 422 }
 423
 424
 425 /// Execute all of the passes scheduled for execution by invoking
 426 /// runOnModule method.  Keep track of whether any of the passes modifies
 427 /// the module, and if so, return true.
 428 bool
 429 ModulePassManager_New::runOnModule(Module &M) {
 430   bool Changed = false;
 431   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
 432          e = passVectorEnd(); itr != e; ++itr) {
 433     Pass *P = *itr;
 434     ModulePass *MP = dynamic_cast<ModulePass*>(P);
 435     Changed |= MP->runOnModule(M);
 436   }
 437   return Changed;
 438 }
 439
 440 /// Schedule all passes from the queue by adding them in their
 441 /// respective manager's queue.
 442 void
 443 PassManagerImpl_New::schedulePasses() {
 444   /* TODO */
 445 }
 446
 447 /// Add pass P to the queue of passes to run.
 448 void
 449 PassManagerImpl_New::add(Pass *P) {
 450   /* TODO */
 451 }
 452
 453 // PassManager_New implementation
 454 /// Add P into active pass manager or use new module pass manager to
 455 /// manage it.
 456 bool
 457 PassManagerImpl_New::addPass(Pass *P) {
 458
 459   if (!activeManager || !activeManager->addPass(P)) {
 460     activeManager = new ModulePassManager_New();
 461     PassManagers.push_back(activeManager);
 462   }
 463
 464   return activeManager->addPass(P);
 465 }
 466
 467 /// run - Execute all of the passes scheduled for execution.  Keep track of
 468 /// whether any of the passes modifies the module, and if so, return true.
 469 bool
 470 PassManagerImpl_New::run(Module &M) {
 471
 472   schedulePasses();
 473   bool Changed = false;
 474   for (std::vector<ModulePassManager_New *>::iterator itr = PassManagers.begin(),
 475          e = PassManagers.end(); itr != e; ++itr) {
 476     ModulePassManager_New *pm = *itr;
 477     Changed |= pm->runOnModule(M);
 478   }
 479   return Changed;
 480 }
 481
 482 /// Create new pass manager
 483 PassManager_New::PassManager_New() {
 484   PM = new PassManagerImpl_New();
 485 }
 486
 487 /// add - Add a pass to the queue of passes to run.  This passes ownership of
 488 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
 489 /// will be destroyed as well, so there is no need to delete the pass.  This
 490 /// implies that all passes MUST be allocated with 'new'.
 491 void
 492 PassManager_New::add(Pass *P) {
 493   PM->add(P);
 494 }
 495
 496 /// run - Execute all of the passes scheduled for execution.  Keep track of
 497 /// whether any of the passes modifies the module, and if so, return true.
 498 bool
 499 PassManager_New::run(Module &M) {
 500   return PM->run(M);
 501 }
 502