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