LLVM API Documentation
00001 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LLVM Pass Manager infrastructure. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 00015 #include "llvm/PassManagers.h" 00016 #include "llvm/Support/CommandLine.h" 00017 #include "llvm/Support/Timer.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/ModuleProvider.h" 00020 #include "llvm/Support/ErrorHandling.h" 00021 #include "llvm/Support/Streams.h" 00022 #include "llvm/Support/ManagedStatic.h" 00023 #include "llvm/Support/raw_ostream.h" 00024 #include "llvm/System/Mutex.h" 00025 #include "llvm/System/Threading.h" 00026 #include "llvm/Analysis/Dominators.h" 00027 #include "llvm-c/Core.h" 00028 #include <algorithm> 00029 #include <cstdio> 00030 #include <map> 00031 using namespace llvm; 00032 00033 // See PassManagers.h for Pass Manager infrastructure overview. 00034 00035 namespace llvm { 00036 00037 //===----------------------------------------------------------------------===// 00038 // Pass debugging information. Often it is useful to find out what pass is 00039 // running when a crash occurs in a utility. When this library is compiled with 00040 // debugging on, a command line option (--debug-pass) is enabled that causes the 00041 // pass name to be printed before it executes. 00042 // 00043 00044 // Different debug levels that can be enabled... 00045 enum PassDebugLevel { 00046 None, Arguments, Structure, Executions, Details 00047 }; 00048 00049 // Always verify dominfo if expensive checking is enabled. 00050 #ifdef XDEBUG 00051 bool VerifyDomInfo = true; 00052 #else 00053 bool VerifyDomInfo = false; 00054 #endif 00055 static cl::opt<bool,true> 00056 VerifyDomInfoX("verify-dom-info", cl::location(VerifyDomInfo), 00057 cl::desc("Verify dominator info (time consuming)")); 00058 00059 static cl::opt<enum PassDebugLevel> 00060 PassDebugging("debug-pass", cl::Hidden, 00061 cl::desc("Print PassManager debugging information"), 00062 cl::values( 00063 clEnumVal(None , "disable debug output"), 00064 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"), 00065 clEnumVal(Structure , "print pass structure before run()"), 00066 clEnumVal(Executions, "print pass name before it is executed"), 00067 clEnumVal(Details , "print pass details when it is executed"), 00068 clEnumValEnd)); 00069 } // End of llvm namespace 00070 00071 void PassManagerPrettyStackEntry::print(raw_ostream &OS) const { 00072 if (V == 0 && M == 0) 00073 OS << "Releasing pass '"; 00074 else 00075 OS << "Running pass '"; 00076 00077 OS << P->getPassName() << "'"; 00078 00079 if (M) { 00080 OS << " on module '" << M->getModuleIdentifier() << "'.\n"; 00081 return; 00082 } 00083 if (V == 0) { 00084 OS << '\n'; 00085 return; 00086 } 00087 00088 OS << " on "; 00089 if (isa<Function>(V)) 00090 OS << "function"; 00091 else if (isa<BasicBlock>(V)) 00092 OS << "basic block"; 00093 else 00094 OS << "value"; 00095 00096 OS << " '"; 00097 WriteAsOperand(OS, V, /*PrintTy=*/false, M); 00098 OS << "'\n"; 00099 } 00100 00101 00102 namespace { 00103 00104 //===----------------------------------------------------------------------===// 00105 // BBPassManager 00106 // 00107 /// BBPassManager manages BasicBlockPass. It batches all the 00108 /// pass together and sequence them to process one basic block before 00109 /// processing next basic block. 00110 class VISIBILITY_HIDDEN BBPassManager : public PMDataManager, 00111 public FunctionPass { 00112 00113 public: 00114 static char ID; 00115 explicit BBPassManager(int Depth) 00116 : PMDataManager(Depth), FunctionPass(&ID) {} 00117 00118 /// Execute all of the passes scheduled for execution. Keep track of 00119 /// whether any of the passes modifies the function, and if so, return true. 00120 bool runOnFunction(Function &F); 00121 00122 /// Pass Manager itself does not invalidate any analysis info. 00123 void getAnalysisUsage(AnalysisUsage &Info) const { 00124 Info.setPreservesAll(); 00125 } 00126 00127 bool doInitialization(Module &M); 00128 bool doInitialization(Function &F); 00129 bool doFinalization(Module &M); 00130 bool doFinalization(Function &F); 00131 00132 virtual const char *getPassName() const { 00133 return "BasicBlock Pass Manager"; 00134 } 00135 00136 // Print passes managed by this manager 00137 void dumpPassStructure(unsigned Offset) { 00138 llvm::errs() << std::string(Offset*2, ' ') << "BasicBlockPass Manager\n"; 00139 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 00140 BasicBlockPass *BP = getContainedPass(Index); 00141 BP->dumpPassStructure(Offset + 1); 00142 dumpLastUses(BP, Offset+1); 00143 } 00144 } 00145 00146 BasicBlockPass *getContainedPass(unsigned N) { 00147 assert(N < PassVector.size() && "Pass number out of range!"); 00148 BasicBlockPass *BP = static_cast<BasicBlockPass *>(PassVector[N]); 00149 return BP; 00150 } 00151 00152 virtual PassManagerType getPassManagerType() const { 00153 return PMT_BasicBlockPassManager; 00154 } 00155 }; 00156 00157 char BBPassManager::ID = 0; 00158 } 00159 00160 namespace llvm { 00161 00162 //===----------------------------------------------------------------------===// 00163 // FunctionPassManagerImpl 00164 // 00165 /// FunctionPassManagerImpl manages FPPassManagers 00166 class FunctionPassManagerImpl : public Pass, 00167 public PMDataManager, 00168 public PMTopLevelManager { 00169 private: 00170 bool wasRun; 00171 public: 00172 static char ID; 00173 explicit FunctionPassManagerImpl(int Depth) : 00174 Pass(&ID), PMDataManager(Depth), 00175 PMTopLevelManager(TLM_Function), wasRun(false) { } 00176 00177 /// add - Add a pass to the queue of passes to run. This passes ownership of 00178 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 00179 /// will be destroyed as well, so there is no need to delete the pass. This 00180 /// implies that all passes MUST be allocated with 'new'. 00181 void add(Pass *P) { 00182 schedulePass(P); 00183 } 00184 00185 // Prepare for running an on the fly pass, freeing memory if needed 00186 // from a previous run. 00187 void releaseMemoryOnTheFly(); 00188 00189 /// run - Execute all of the passes scheduled for execution. Keep track of 00190 /// whether any of the passes modifies the module, and if so, return true. 00191 bool run(Function &F); 00192 00193 /// doInitialization - Run all of the initializers for the function passes. 00194 /// 00195 bool doInitialization(Module &M); 00196 00197 /// doFinalization - Run all of the finalizers for the function passes. 00198 /// 00199 bool doFinalization(Module &M); 00200 00201 /// Pass Manager itself does not invalidate any analysis info. 00202 void getAnalysisUsage(AnalysisUsage &Info) const { 00203 Info.setPreservesAll(); 00204 } 00205 00206 inline void addTopLevelPass(Pass *P) { 00207 00208 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 00209 00210 // P is a immutable pass and it will be managed by this 00211 // top level manager. Set up analysis resolver to connect them. 00212 AnalysisResolver *AR = new AnalysisResolver(*this); 00213 P->setResolver(AR); 00214 initializeAnalysisImpl(P); 00215 addImmutablePass(IP); 00216 recordAvailableAnalysis(IP); 00217 } else { 00218 P->assignPassManager(activeStack); 00219 } 00220 00221 } 00222 00223 FPPassManager *getContainedManager(unsigned N) { 00224 assert(N < PassManagers.size() && "Pass number out of range!"); 00225 FPPassManager *FP = static_cast<FPPassManager *>(PassManagers[N]); 00226 return FP; 00227 } 00228 }; 00229 00230 char FunctionPassManagerImpl::ID = 0; 00231 //===----------------------------------------------------------------------===// 00232 // MPPassManager 00233 // 00234 /// MPPassManager manages ModulePasses and function pass managers. 00235 /// It batches all Module passes and function pass managers together and 00236 /// sequences them to process one module. 00237 class MPPassManager : public Pass, public PMDataManager { 00238 public: 00239 static char ID; 00240 explicit MPPassManager(int Depth) : 00241 Pass(&ID), PMDataManager(Depth) { } 00242 00243 // Delete on the fly managers. 00244 virtual ~MPPassManager() { 00245 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator 00246 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end(); 00247 I != E; ++I) { 00248 FunctionPassManagerImpl *FPP = I->second; 00249 delete FPP; 00250 } 00251 } 00252 00253 /// run - Execute all of the passes scheduled for execution. Keep track of 00254 /// whether any of the passes modifies the module, and if so, return true. 00255 bool runOnModule(Module &M); 00256 00257 /// Pass Manager itself does not invalidate any analysis info. 00258 void getAnalysisUsage(AnalysisUsage &Info) const { 00259 Info.setPreservesAll(); 00260 } 00261 00262 /// Add RequiredPass into list of lower level passes required by pass P. 00263 /// RequiredPass is run on the fly by Pass Manager when P requests it 00264 /// through getAnalysis interface. 00265 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); 00266 00267 /// Return function pass corresponding to PassInfo PI, that is 00268 /// required by module pass MP. Instantiate analysis pass, by using 00269 /// its runOnFunction() for function F. 00270 virtual Pass* getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F); 00271 00272 virtual const char *getPassName() const { 00273 return "Module Pass Manager"; 00274 } 00275 00276 // Print passes managed by this manager 00277 void dumpPassStructure(unsigned Offset) { 00278 llvm::errs() << std::string(Offset*2, ' ') << "ModulePass Manager\n"; 00279 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 00280 ModulePass *MP = getContainedPass(Index); 00281 MP->dumpPassStructure(Offset + 1); 00282 std::map<Pass *, FunctionPassManagerImpl *>::const_iterator I = 00283 OnTheFlyManagers.find(MP); 00284 if (I != OnTheFlyManagers.end()) 00285 I->second->dumpPassStructure(Offset + 2); 00286 dumpLastUses(MP, Offset+1); 00287 } 00288 } 00289 00290 ModulePass *getContainedPass(unsigned N) { 00291 assert(N < PassVector.size() && "Pass number out of range!"); 00292 return static_cast<ModulePass *>(PassVector[N]); 00293 } 00294 00295 virtual PassManagerType getPassManagerType() const { 00296 return PMT_ModulePassManager; 00297 } 00298 00299 private: 00300 /// Collection of on the fly FPPassManagers. These managers manage 00301 /// function passes that are required by module passes. 00302 std::map<Pass *, FunctionPassManagerImpl *> OnTheFlyManagers; 00303 }; 00304 00305 char MPPassManager::ID = 0; 00306 //===----------------------------------------------------------------------===// 00307 // PassManagerImpl 00308 // 00309 00310 /// PassManagerImpl manages MPPassManagers 00311 class PassManagerImpl : public Pass, 00312 public PMDataManager, 00313 public PMTopLevelManager { 00314 00315 public: 00316 static char ID; 00317 explicit PassManagerImpl(int Depth) : 00318 Pass(&ID), PMDataManager(Depth), PMTopLevelManager(TLM_Pass) { } 00319 00320 /// add - Add a pass to the queue of passes to run. This passes ownership of 00321 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 00322 /// will be destroyed as well, so there is no need to delete the pass. This 00323 /// implies that all passes MUST be allocated with 'new'. 00324 void add(Pass *P) { 00325 schedulePass(P); 00326 } 00327 00328 /// run - Execute all of the passes scheduled for execution. Keep track of 00329 /// whether any of the passes modifies the module, and if so, return true. 00330 bool run(Module &M); 00331 00332 /// Pass Manager itself does not invalidate any analysis info. 00333 void getAnalysisUsage(AnalysisUsage &Info) const { 00334 Info.setPreservesAll(); 00335 } 00336 00337 inline void addTopLevelPass(Pass *P) { 00338 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) { 00339 00340 // P is a immutable pass and it will be managed by this 00341 // top level manager. Set up analysis resolver to connect them. 00342 AnalysisResolver *AR = new AnalysisResolver(*this); 00343 P->setResolver(AR); 00344 initializeAnalysisImpl(P); 00345 addImmutablePass(IP); 00346 recordAvailableAnalysis(IP); 00347 } else { 00348 P->assignPassManager(activeStack); 00349 } 00350 } 00351 00352 MPPassManager *getContainedManager(unsigned N) { 00353 assert(N < PassManagers.size() && "Pass number out of range!"); 00354 MPPassManager *MP = static_cast<MPPassManager *>(PassManagers[N]); 00355 return MP; 00356 } 00357 }; 00358 00359 char PassManagerImpl::ID = 0; 00360 } // End of llvm namespace 00361 00362 namespace { 00363 00364 //===----------------------------------------------------------------------===// 00365 /// TimingInfo Class - This class is used to calculate information about the 00366 /// amount of time each pass takes to execute. This only happens when 00367 /// -time-passes is enabled on the command line. 00368 /// 00369 00370 static ManagedStatic<sys::SmartMutex<true> > TimingInfoMutex; 00371 00372 class VISIBILITY_HIDDEN TimingInfo { 00373 std::map<Pass*, Timer> TimingData; 00374 TimerGroup TG; 00375 00376 public: 00377 // Use 'create' member to get this. 00378 TimingInfo() : TG("... Pass execution timing report ...") {} 00379 00380 // TimingDtor - Print out information about timing information 00381 ~TimingInfo() { 00382 // Delete all of the timers... 00383 TimingData.clear(); 00384 // TimerGroup is deleted next, printing the report. 00385 } 00386 00387 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer 00388 // to a non null value (if the -time-passes option is enabled) or it leaves it 00389 // null. It may be called multiple times. 00390 static void createTheTimeInfo(); 00391 00392 void passStarted(Pass *P) { 00393 if (dynamic_cast<PMDataManager *>(P)) 00394 return; 00395 00396 sys::SmartScopedLock<true> Lock(*TimingInfoMutex); 00397 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 00398 if (I == TimingData.end()) 00399 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first; 00400 I->second.startTimer(); 00401 } 00402 00403 void passEnded(Pass *P) { 00404 if (dynamic_cast<PMDataManager *>(P)) 00405 return; 00406 00407 sys::SmartScopedLock<true> Lock(*TimingInfoMutex); 00408 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 00409 assert(I != TimingData.end() && "passStarted/passEnded not nested right!"); 00410 I->second.stopTimer(); 00411 } 00412 }; 00413 00414 } // End of anon namespace 00415 00416 static TimingInfo *TheTimeInfo; 00417 00418 //===----------------------------------------------------------------------===// 00419 // PMTopLevelManager implementation 00420 00421 /// Initialize top level manager. Create first pass manager. 00422 PMTopLevelManager::PMTopLevelManager(enum TopLevelManagerType t) { 00423 if (t == TLM_Pass) { 00424 MPPassManager *MPP = new MPPassManager(1); 00425 MPP->setTopLevelManager(this); 00426 addPassManager(MPP); 00427 activeStack.push(MPP); 00428 } else if (t == TLM_Function) { 00429 FPPassManager *FPP = new FPPassManager(1); 00430 FPP->setTopLevelManager(this); 00431 addPassManager(FPP); 00432 activeStack.push(FPP); 00433 } 00434 } 00435 00436 /// Set pass P as the last user of the given analysis passes. 00437 void PMTopLevelManager::setLastUser(SmallVector<Pass *, 12> &AnalysisPasses, 00438 Pass *P) { 00439 for (SmallVector<Pass *, 12>::iterator I = AnalysisPasses.begin(), 00440 E = AnalysisPasses.end(); I != E; ++I) { 00441 Pass *AP = *I; 00442 LastUser[AP] = P; 00443 00444 if (P == AP) 00445 continue; 00446 00447 // If AP is the last user of other passes then make P last user of 00448 // such passes. 00449 for (DenseMap<Pass *, Pass *>::iterator LUI = LastUser.begin(), 00450 LUE = LastUser.end(); LUI != LUE; ++LUI) { 00451 if (LUI->second == AP) 00452 // DenseMap iterator is not invalidated here because 00453 // this is just updating exisitng entry. 00454 LastUser[LUI->first] = P; 00455 } 00456 } 00457 } 00458 00459 /// Collect passes whose last user is P 00460 void PMTopLevelManager::collectLastUses(SmallVector<Pass *, 12> &LastUses, 00461 Pass *P) { 00462 DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator DMI = 00463 InversedLastUser.find(P); 00464 if (DMI == InversedLastUser.end()) 00465 return; 00466 00467 SmallPtrSet<Pass *, 8> &LU = DMI->second; 00468 for (SmallPtrSet<Pass *, 8>::iterator I = LU.begin(), 00469 E = LU.end(); I != E; ++I) { 00470 LastUses.push_back(*I); 00471 } 00472 00473 } 00474 00475 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) { 00476 AnalysisUsage *AnUsage = NULL; 00477 DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.find(P); 00478 if (DMI != AnUsageMap.end()) 00479 AnUsage = DMI->second; 00480 else { 00481 AnUsage = new AnalysisUsage(); 00482 P->getAnalysisUsage(*AnUsage); 00483 AnUsageMap[P] = AnUsage; 00484 } 00485 return AnUsage; 00486 } 00487 00488 /// Schedule pass P for execution. Make sure that passes required by 00489 /// P are run before P is run. Update analysis info maintained by 00490 /// the manager. Remove dead passes. This is a recursive function. 00491 void PMTopLevelManager::schedulePass(Pass *P) { 00492 00493 // TODO : Allocate function manager for this pass, other wise required set 00494 // may be inserted into previous function manager 00495 00496 // Give pass a chance to prepare the stage. 00497 P->preparePassManager(activeStack); 00498 00499 // If P is an analysis pass and it is available then do not 00500 // generate the analysis again. Stale analysis info should not be 00501 // available at this point. 00502 if (P->getPassInfo() && 00503 P->getPassInfo()->isAnalysis() && findAnalysisPass(P->getPassInfo())) { 00504 delete P; 00505 return; 00506 } 00507 00508 AnalysisUsage *AnUsage = findAnalysisUsage(P); 00509 00510 bool checkAnalysis = true; 00511 while (checkAnalysis) { 00512 checkAnalysis = false; 00513 00514 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet(); 00515 for (AnalysisUsage::VectorType::const_iterator I = RequiredSet.begin(), 00516 E = RequiredSet.end(); I != E; ++I) { 00517 00518 Pass *AnalysisPass = findAnalysisPass(*I); 00519 if (!AnalysisPass) { 00520 AnalysisPass = (*I)->createPass(); 00521 if (P->getPotentialPassManagerType () == 00522 AnalysisPass->getPotentialPassManagerType()) 00523 // Schedule analysis pass that is managed by the same pass manager. 00524 schedulePass(AnalysisPass); 00525 else if (P->getPotentialPassManagerType () > 00526 AnalysisPass->getPotentialPassManagerType()) { 00527 // Schedule analysis pass that is managed by a new manager. 00528 schedulePass(AnalysisPass); 00529 // Recheck analysis passes to ensure that required analysises that 00530 // are already checked are still available. 00531 checkAnalysis = true; 00532 } 00533 else 00534 // Do not schedule this analysis. Lower level analsyis 00535 // passes are run on the fly. 00536 delete AnalysisPass; 00537 } 00538 } 00539 } 00540 00541 // Now all required passes are available. 00542 addTopLevelPass(P); 00543 } 00544 00545 /// Find the pass that implements Analysis AID. Search immutable 00546 /// passes and all pass managers. If desired pass is not found 00547 /// then return NULL. 00548 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) { 00549 00550 Pass *P = NULL; 00551 // Check pass managers 00552 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(), 00553 E = PassManagers.end(); P == NULL && I != E; ++I) { 00554 PMDataManager *PMD = *I; 00555 P = PMD->findAnalysisPass(AID, false); 00556 } 00557 00558 // Check other pass managers 00559 for (SmallVector<PMDataManager *, 8>::iterator 00560 I = IndirectPassManagers.begin(), 00561 E = IndirectPassManagers.end(); P == NULL && I != E; ++I) 00562 P = (*I)->findAnalysisPass(AID, false); 00563 00564 for (SmallVector<ImmutablePass *, 8>::iterator I = ImmutablePasses.begin(), 00565 E = ImmutablePasses.end(); P == NULL && I != E; ++I) { 00566 const PassInfo *PI = (*I)->getPassInfo(); 00567 if (PI == AID) 00568 P = *I; 00569 00570 // If Pass not found then check the interfaces implemented by Immutable Pass 00571 if (!P) { 00572 const std::vector<const PassInfo*> &ImmPI = 00573 PI->getInterfacesImplemented(); 00574 if (std::find(ImmPI.begin(), ImmPI.end(), AID) != ImmPI.end()) 00575 P = *I; 00576 } 00577 } 00578 00579 return P; 00580 } 00581 00582 // Print passes managed by this top level manager. 00583 void PMTopLevelManager::dumpPasses() const { 00584 00585 if (PassDebugging < Structure) 00586 return; 00587 00588 // Print out the immutable passes 00589 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 00590 ImmutablePasses[i]->dumpPassStructure(0); 00591 } 00592 00593 // Every class that derives from PMDataManager also derives from Pass 00594 // (sometimes indirectly), but there's no inheritance relationship 00595 // between PMDataManager and Pass, so we have to dynamic_cast to get 00596 // from a PMDataManager* to a Pass*. 00597 for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(), 00598 E = PassManagers.end(); I != E; ++I) 00599 dynamic_cast<Pass *>(*I)->dumpPassStructure(1); 00600 } 00601 00602 void PMTopLevelManager::dumpArguments() const { 00603 00604 if (PassDebugging < Arguments) 00605 return; 00606 00607 errs() << "Pass Arguments: "; 00608 for (SmallVector<PMDataManager *, 8>::const_iterator I = PassManagers.begin(), 00609 E = PassManagers.end(); I != E; ++I) 00610 (*I)->dumpPassArguments(); 00611 errs() << "\n"; 00612 } 00613 00614 void PMTopLevelManager::initializeAllAnalysisInfo() { 00615 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(), 00616 E = PassManagers.end(); I != E; ++I) 00617 (*I)->initializeAnalysisInfo(); 00618 00619 // Initailize other pass managers 00620 for (SmallVector<PMDataManager *, 8>::iterator I = IndirectPassManagers.begin(), 00621 E = IndirectPassManagers.end(); I != E; ++I) 00622 (*I)->initializeAnalysisInfo(); 00623 00624 for (DenseMap<Pass *, Pass *>::iterator DMI = LastUser.begin(), 00625 DME = LastUser.end(); DMI != DME; ++DMI) { 00626 DenseMap<Pass *, SmallPtrSet<Pass *, 8> >::iterator InvDMI = 00627 InversedLastUser.find(DMI->second); 00628 if (InvDMI != InversedLastUser.end()) { 00629 SmallPtrSet<Pass *, 8> &L = InvDMI->second; 00630 L.insert(DMI->first); 00631 } else { 00632 SmallPtrSet<Pass *, 8> L; L.insert(DMI->first); 00633 InversedLastUser[DMI->second] = L; 00634 } 00635 } 00636 } 00637 00638 /// Destructor 00639 PMTopLevelManager::~PMTopLevelManager() { 00640 for (SmallVector<PMDataManager *, 8>::iterator I = PassManagers.begin(), 00641 E = PassManagers.end(); I != E; ++I) 00642 delete *I; 00643 00644 for (SmallVector<ImmutablePass *, 8>::iterator 00645 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I) 00646 delete *I; 00647 00648 for (DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.begin(), 00649 DME = AnUsageMap.end(); DMI != DME; ++DMI) 00650 delete DMI->second; 00651 } 00652 00653 //===----------------------------------------------------------------------===// 00654 // PMDataManager implementation 00655 00656 /// Augement AvailableAnalysis by adding analysis made available by pass P. 00657 void PMDataManager::recordAvailableAnalysis(Pass *P) { 00658 const PassInfo *PI = P->getPassInfo(); 00659 if (PI == 0) return; 00660 00661 AvailableAnalysis[PI] = P; 00662 00663 //This pass is the current implementation of all of the interfaces it 00664 //implements as well. 00665 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 00666 for (unsigned i = 0, e = II.size(); i != e; ++i) 00667 AvailableAnalysis[II[i]] = P; 00668 } 00669 00670 // Return true if P preserves high level analysis used by other 00671 // passes managed by this manager 00672 bool PMDataManager::preserveHigherLevelAnalysis(Pass *P) { 00673 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 00674 if (AnUsage->getPreservesAll()) 00675 return true; 00676 00677 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 00678 for (SmallVector<Pass *, 8>::iterator I = HigherLevelAnalysis.begin(), 00679 E = HigherLevelAnalysis.end(); I != E; ++I) { 00680 Pass *P1 = *I; 00681 if (!dynamic_cast<ImmutablePass*>(P1) && 00682 std::find(PreservedSet.begin(), PreservedSet.end(), 00683 P1->getPassInfo()) == 00684 PreservedSet.end()) 00685 return false; 00686 } 00687 00688 return true; 00689 } 00690 00691 /// verifyPreservedAnalysis -- Verify analysis preserved by pass P. 00692 void PMDataManager::verifyPreservedAnalysis(Pass *P) { 00693 // Don't do this unless assertions are enabled. 00694 #ifdef NDEBUG 00695 return; 00696 #endif 00697 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 00698 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 00699 00700 // Verify preserved analysis 00701 for (AnalysisUsage::VectorType::const_iterator I = PreservedSet.begin(), 00702 E = PreservedSet.end(); I != E; ++I) { 00703 AnalysisID AID = *I; 00704 if (Pass *AP = findAnalysisPass(AID, true)) 00705 AP->verifyAnalysis(); 00706 } 00707 } 00708 00709 /// verifyDomInfo - Verify dominator information if it is available. 00710 void PMDataManager::verifyDomInfo(Pass &P, Function &F) { 00711 if (!VerifyDomInfo || !P.getResolver()) 00712 return; 00713 00714 DominatorTree *DT = P.getAnalysisIfAvailable<DominatorTree>(); 00715 if (!DT) 00716 return; 00717 00718 DominatorTree OtherDT; 00719 OtherDT.getBase().recalculate(F); 00720 if (DT->compare(OtherDT)) { 00721 errs() << "Dominator Information for " << F.getName() << "\n"; 00722 errs() << "Pass '" << P.getPassName() << "'\n"; 00723 errs() << "----- Valid -----\n"; 00724 OtherDT.dump(); 00725 errs() << "----- Invalid -----\n"; 00726 DT->dump(); 00727 llvm_unreachable("Invalid dominator info"); 00728 } 00729 00730 DominanceFrontier *DF = P.getAnalysisIfAvailable<DominanceFrontier>(); 00731 if (!DF) 00732 return; 00733 00734 DominanceFrontier OtherDF; 00735 std::vector<BasicBlock*> DTRoots = DT->getRoots(); 00736 OtherDF.calculate(*DT, DT->getNode(DTRoots[0])); 00737 if (DF->compare(OtherDF)) { 00738 errs() << "Dominator Information for " << F.getName() << "\n"; 00739 errs() << "Pass '" << P.getPassName() << "'\n"; 00740 errs() << "----- Valid -----\n"; 00741 OtherDF.dump(); 00742 errs() << "----- Invalid -----\n"; 00743 DF->dump(); 00744 llvm_unreachable("Invalid dominator info"); 00745 } 00746 } 00747 00748 /// Remove Analysis not preserved by Pass P 00749 void PMDataManager::removeNotPreservedAnalysis(Pass *P) { 00750 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 00751 if (AnUsage->getPreservesAll()) 00752 return; 00753 00754 const AnalysisUsage::VectorType &PreservedSet = AnUsage->getPreservedSet(); 00755 for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(), 00756 E = AvailableAnalysis.end(); I != E; ) { 00757 std::map<AnalysisID, Pass*>::iterator Info = I++; 00758 if (!dynamic_cast<ImmutablePass*>(Info->second) 00759 && std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 00760 PreservedSet.end()) { 00761 // Remove this analysis 00762 if (PassDebugging >= Details) { 00763 Pass *S = Info->second; 00764 errs() << " -- '" << P->getPassName() << "' is not preserving '"; 00765 errs() << S->getPassName() << "'\n"; 00766 } 00767 AvailableAnalysis.erase(Info); 00768 } 00769 } 00770 00771 // Check inherited analysis also. If P is not preserving analysis 00772 // provided by parent manager then remove it here. 00773 for (unsigned Index = 0; Index < PMT_Last; ++Index) { 00774 00775 if (!InheritedAnalysis[Index]) 00776 continue; 00777 00778 for (std::map<AnalysisID, Pass*>::iterator 00779 I = InheritedAnalysis[Index]->begin(), 00780 E = InheritedAnalysis[Index]->end(); I != E; ) { 00781 std::map<AnalysisID, Pass *>::iterator Info = I++; 00782 if (!dynamic_cast<ImmutablePass*>(Info->second) && 00783 std::find(PreservedSet.begin(), PreservedSet.end(), Info->first) == 00784 PreservedSet.end()) 00785 // Remove this analysis 00786 InheritedAnalysis[Index]->erase(Info); 00787 } 00788 } 00789 } 00790 00791 /// Remove analysis passes that are not used any longer 00792 void PMDataManager::removeDeadPasses(Pass *P, const StringRef &Msg, 00793 enum PassDebuggingString DBG_STR) { 00794 00795 SmallVector<Pass *, 12> DeadPasses; 00796 00797 // If this is a on the fly manager then it does not have TPM. 00798 if (!TPM) 00799 return; 00800 00801 TPM->collectLastUses(DeadPasses, P); 00802 00803 if (PassDebugging >= Details && !DeadPasses.empty()) { 00804 errs() << " -*- '" << P->getPassName(); 00805 errs() << "' is the last user of following pass instances."; 00806 errs() << " Free these instances\n"; 00807 } 00808 00809 for (SmallVector<Pass *, 12>::iterator I = DeadPasses.begin(), 00810 E = DeadPasses.end(); I != E; ++I) { 00811 00812 dumpPassInfo(*I, FREEING_MSG, DBG_STR, Msg); 00813 00814 { 00815 // If the pass crashes releasing memory, remember this. 00816 PassManagerPrettyStackEntry X(*I); 00817 00818 if (TheTimeInfo) TheTimeInfo->passStarted(*I); 00819 (*I)->releaseMemory(); 00820 if (TheTimeInfo) TheTimeInfo->passEnded(*I); 00821 } 00822 if (const PassInfo *PI = (*I)->getPassInfo()) { 00823 std::map<AnalysisID, Pass*>::iterator Pos = 00824 AvailableAnalysis.find(PI); 00825 00826 // It is possible that pass is already removed from the AvailableAnalysis 00827 if (Pos != AvailableAnalysis.end()) 00828 AvailableAnalysis.erase(Pos); 00829 00830 // Remove all interfaces this pass implements, for which it is also 00831 // listed as the available implementation. 00832 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 00833 for (unsigned i = 0, e = II.size(); i != e; ++i) { 00834 Pos = AvailableAnalysis.find(II[i]); 00835 if (Pos != AvailableAnalysis.end() && Pos->second == *I) 00836 AvailableAnalysis.erase(Pos); 00837 } 00838 } 00839 } 00840 } 00841 00842 /// Add pass P into the PassVector. Update 00843 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 00844 void PMDataManager::add(Pass *P, bool ProcessAnalysis) { 00845 // This manager is going to manage pass P. Set up analysis resolver 00846 // to connect them. 00847 AnalysisResolver *AR = new AnalysisResolver(*this); 00848 P->setResolver(AR); 00849 00850 // If a FunctionPass F is the last user of ModulePass info M 00851 // then the F's manager, not F, records itself as a last user of M. 00852 SmallVector<Pass *, 12> TransferLastUses; 00853 00854 if (!ProcessAnalysis) { 00855 // Add pass 00856 PassVector.push_back(P); 00857 return; 00858 } 00859 00860 // At the moment, this pass is the last user of all required passes. 00861 SmallVector<Pass *, 12> LastUses; 00862 SmallVector<Pass *, 8> RequiredPasses; 00863 SmallVector<AnalysisID, 8> ReqAnalysisNotAvailable; 00864 00865 unsigned PDepth = this->getDepth(); 00866 00867 collectRequiredAnalysis(RequiredPasses, 00868 ReqAnalysisNotAvailable, P); 00869 for (SmallVector<Pass *, 8>::iterator I = RequiredPasses.begin(), 00870 E = RequiredPasses.end(); I != E; ++I) { 00871 Pass *PRequired = *I; 00872 unsigned RDepth = 0; 00873 00874 assert(PRequired->getResolver() && "Analysis Resolver is not set"); 00875 PMDataManager &DM = PRequired->getResolver()->getPMDataManager(); 00876 RDepth = DM.getDepth(); 00877 00878 if (PDepth == RDepth) 00879 LastUses.push_back(PRequired); 00880 else if (PDepth > RDepth) { 00881 // Let the parent claim responsibility of last use 00882 TransferLastUses.push_back(PRequired); 00883 // Keep track of higher level analysis used by this manager. 00884 HigherLevelAnalysis.push_back(PRequired); 00885 } else 00886 llvm_unreachable("Unable to accomodate Required Pass"); 00887 } 00888 00889 // Set P as P's last user until someone starts using P. 00890 // However, if P is a Pass Manager then it does not need 00891 // to record its last user. 00892 if (!dynamic_cast<PMDataManager *>(P)) 00893 LastUses.push_back(P); 00894 TPM->setLastUser(LastUses, P); 00895 00896 if (!TransferLastUses.empty()) { 00897 Pass *My_PM = dynamic_cast<Pass *>(this); 00898 TPM->setLastUser(TransferLastUses, My_PM); 00899 TransferLastUses.clear(); 00900 } 00901 00902 // Now, take care of required analysises that are not available. 00903 for (SmallVector<AnalysisID, 8>::iterator 00904 I = ReqAnalysisNotAvailable.begin(), 00905 E = ReqAnalysisNotAvailable.end() ;I != E; ++I) { 00906 Pass *AnalysisPass = (*I)->createPass(); 00907 this->addLowerLevelRequiredPass(P, AnalysisPass); 00908 } 00909 00910 // Take a note of analysis required and made available by this pass. 00911 // Remove the analysis not preserved by this pass 00912 removeNotPreservedAnalysis(P); 00913 recordAvailableAnalysis(P); 00914 00915 // Add pass 00916 PassVector.push_back(P); 00917 } 00918 00919 00920 /// Populate RP with analysis pass that are required by 00921 /// pass P and are available. Populate RP_NotAvail with analysis 00922 /// pass that are required by pass P but are not available. 00923 void PMDataManager::collectRequiredAnalysis(SmallVector<Pass *, 8>&RP, 00924 SmallVector<AnalysisID, 8> &RP_NotAvail, 00925 Pass *P) { 00926 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 00927 const AnalysisUsage::VectorType &RequiredSet = AnUsage->getRequiredSet(); 00928 for (AnalysisUsage::VectorType::const_iterator 00929 I = RequiredSet.begin(), E = RequiredSet.end(); I != E; ++I) { 00930 if (Pass *AnalysisPass = findAnalysisPass(*I, true)) 00931 RP.push_back(AnalysisPass); 00932 else 00933 RP_NotAvail.push_back(*I); 00934 } 00935 00936 const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet(); 00937 for (AnalysisUsage::VectorType::const_iterator I = IDs.begin(), 00938 E = IDs.end(); I != E; ++I) { 00939 if (Pass *AnalysisPass = findAnalysisPass(*I, true)) 00940 RP.push_back(AnalysisPass); 00941 else 00942 RP_NotAvail.push_back(*I); 00943 } 00944 } 00945 00946 // All Required analyses should be available to the pass as it runs! Here 00947 // we fill in the AnalysisImpls member of the pass so that it can 00948 // successfully use the getAnalysis() method to retrieve the 00949 // implementations it needs. 00950 // 00951 void PMDataManager::initializeAnalysisImpl(Pass *P) { 00952 AnalysisUsage *AnUsage = TPM->findAnalysisUsage(P); 00953 00954 for (AnalysisUsage::VectorType::const_iterator 00955 I = AnUsage->getRequiredSet().begin(), 00956 E = AnUsage->getRequiredSet().end(); I != E; ++I) { 00957 Pass *Impl = findAnalysisPass(*I, true); 00958 if (Impl == 0) 00959 // This may be analysis pass that is initialized on the fly. 00960 // If that is not the case then it will raise an assert when it is used. 00961 continue; 00962 AnalysisResolver *AR = P->getResolver(); 00963 assert(AR && "Analysis Resolver is not set"); 00964 AR->addAnalysisImplsPair(*I, Impl); 00965 } 00966 } 00967 00968 /// Find the pass that implements Analysis AID. If desired pass is not found 00969 /// then return NULL. 00970 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) { 00971 00972 // Check if AvailableAnalysis map has one entry. 00973 std::map<AnalysisID, Pass*>::const_iterator I = AvailableAnalysis.find(AID); 00974 00975 if (I != AvailableAnalysis.end()) 00976 return I->second; 00977 00978 // Search Parents through TopLevelManager 00979 if (SearchParent) 00980 return TPM->findAnalysisPass(AID); 00981 00982 return NULL; 00983 } 00984 00985 // Print list of passes that are last used by P. 00986 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{ 00987 00988 SmallVector<Pass *, 12> LUses; 00989 00990 // If this is a on the fly manager then it does not have TPM. 00991 if (!TPM) 00992 return; 00993 00994 TPM->collectLastUses(LUses, P); 00995 00996 for (SmallVector<Pass *, 12>::iterator I = LUses.begin(), 00997 E = LUses.end(); I != E; ++I) { 00998 llvm::errs() << "--" << std::string(Offset*2, ' '); 00999 (*I)->dumpPassStructure(0); 01000 } 01001 } 01002 01003 void PMDataManager::dumpPassArguments() const { 01004 for (SmallVector<Pass *, 8>::const_iterator I = PassVector.begin(), 01005 E = PassVector.end(); I != E; ++I) { 01006 if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I)) 01007 PMD->dumpPassArguments(); 01008 else 01009 if (const PassInfo *PI = (*I)->getPassInfo()) 01010 if (!PI->isAnalysisGroup()) 01011 errs() << " -" << PI->getPassArgument(); 01012 } 01013 } 01014 01015 void PMDataManager::dumpPassInfo(Pass *P, enum PassDebuggingString S1, 01016 enum PassDebuggingString S2, 01017 const StringRef &Msg) { 01018 if (PassDebugging < Executions) 01019 return; 01020 errs() << (void*)this << std::string(getDepth()*2+1, ' '); 01021 switch (S1) { 01022 case EXECUTION_MSG: 01023 errs() << "Executing Pass '" << P->getPassName(); 01024 break; 01025 case MODIFICATION_MSG: 01026 errs() << "Made Modification '" << P->getPassName(); 01027 break; 01028 case FREEING_MSG: 01029 errs() << " Freeing Pass '" << P->getPassName(); 01030 break; 01031 default: 01032 break; 01033 } 01034 switch (S2) { 01035 case ON_BASICBLOCK_MSG: 01036 errs() << "' on BasicBlock '" << Msg << "'...\n"; 01037 break; 01038 case ON_FUNCTION_MSG: 01039 errs() << "' on Function '" << Msg << "'...\n"; 01040 break; 01041 case ON_MODULE_MSG: 01042 errs() << "' on Module '" << Msg << "'...\n"; 01043 break; 01044 case ON_LOOP_MSG: 01045 errs() << "' on Loop " << Msg << "'...\n"; 01046 break; 01047 case ON_CG_MSG: 01048 errs() << "' on Call Graph " << Msg << "'...\n"; 01049 break; 01050 default: 01051 break; 01052 } 01053 } 01054 01055 void PMDataManager::dumpRequiredSet(const Pass *P) const { 01056 if (PassDebugging < Details) 01057 return; 01058 01059 AnalysisUsage analysisUsage; 01060 P->getAnalysisUsage(analysisUsage); 01061 dumpAnalysisUsage("Required", P, analysisUsage.getRequiredSet()); 01062 } 01063 01064 void PMDataManager::dumpPreservedSet(const Pass *P) const { 01065 if (PassDebugging < Details) 01066 return; 01067 01068 AnalysisUsage analysisUsage; 01069 P->getAnalysisUsage(analysisUsage); 01070 dumpAnalysisUsage("Preserved", P, analysisUsage.getPreservedSet()); 01071 } 01072 01073 void PMDataManager::dumpAnalysisUsage(const StringRef &Msg, const Pass *P, 01074 const AnalysisUsage::VectorType &Set) const { 01075 assert(PassDebugging >= Details); 01076 if (Set.empty()) 01077 return; 01078 errs() << (void*)P << std::string(getDepth()*2+3, ' ') << Msg << " Analyses:"; 01079 for (unsigned i = 0; i != Set.size(); ++i) { 01080 if (i) errs() << ","; 01081 errs() << " " << Set[i]->getPassName(); 01082 } 01083 errs() << "\n"; 01084 } 01085 01086 /// Add RequiredPass into list of lower level passes required by pass P. 01087 /// RequiredPass is run on the fly by Pass Manager when P requests it 01088 /// through getAnalysis interface. 01089 /// This should be handled by specific pass manager. 01090 void PMDataManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 01091 if (TPM) { 01092 TPM->dumpArguments(); 01093 TPM->dumpPasses(); 01094 } 01095 01096 // Module Level pass may required Function Level analysis info 01097 // (e.g. dominator info). Pass manager uses on the fly function pass manager 01098 // to provide this on demand. In that case, in Pass manager terminology, 01099 // module level pass is requiring lower level analysis info managed by 01100 // lower level pass manager. 01101 01102 // When Pass manager is not able to order required analysis info, Pass manager 01103 // checks whether any lower level manager will be able to provide this 01104 // analysis info on demand or not. 01105 #ifndef NDEBUG 01106 errs() << "Unable to schedule '" << RequiredPass->getPassName(); 01107 errs() << "' required by '" << P->getPassName() << "'\n"; 01108 #endif 01109 llvm_unreachable("Unable to schedule pass"); 01110 } 01111 01112 // Destructor 01113 PMDataManager::~PMDataManager() { 01114 for (SmallVector<Pass *, 8>::iterator I = PassVector.begin(), 01115 E = PassVector.end(); I != E; ++I) 01116 delete *I; 01117 } 01118 01119 //===----------------------------------------------------------------------===// 01120 // NOTE: Is this the right place to define this method ? 01121 // getAnalysisIfAvailable - Return analysis result or null if it doesn't exist. 01122 Pass *AnalysisResolver::getAnalysisIfAvailable(AnalysisID ID, bool dir) const { 01123 return PM.findAnalysisPass(ID, dir); 01124 } 01125 01126 Pass *AnalysisResolver::findImplPass(Pass *P, const PassInfo *AnalysisPI, 01127 Function &F) { 01128 return PM.getOnTheFlyPass(P, AnalysisPI, F); 01129 } 01130 01131 //===----------------------------------------------------------------------===// 01132 // BBPassManager implementation 01133 01134 /// Execute all of the passes scheduled for execution by invoking 01135 /// runOnBasicBlock method. Keep track of whether any of the passes modifies 01136 /// the function, and if so, return true. 01137 bool BBPassManager::runOnFunction(Function &F) { 01138 if (F.isDeclaration()) 01139 return false; 01140 01141 bool Changed = doInitialization(F); 01142 01143 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 01144 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01145 BasicBlockPass *BP = getContainedPass(Index); 01146 01147 dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getName()); 01148 dumpRequiredSet(BP); 01149 01150 initializeAnalysisImpl(BP); 01151 01152 { 01153 // If the pass crashes, remember this. 01154 PassManagerPrettyStackEntry X(BP, *I); 01155 01156 if (TheTimeInfo) TheTimeInfo->passStarted(BP); 01157 Changed |= BP->runOnBasicBlock(*I); 01158 if (TheTimeInfo) TheTimeInfo->passEnded(BP); 01159 } 01160 01161 if (Changed) 01162 dumpPassInfo(BP, MODIFICATION_MSG, ON_BASICBLOCK_MSG, 01163 I->getName()); 01164 dumpPreservedSet(BP); 01165 01166 verifyPreservedAnalysis(BP); 01167 removeNotPreservedAnalysis(BP); 01168 recordAvailableAnalysis(BP); 01169 removeDeadPasses(BP, I->getName(), ON_BASICBLOCK_MSG); 01170 } 01171 01172 return Changed |= doFinalization(F); 01173 } 01174 01175 // Implement doInitialization and doFinalization 01176 bool BBPassManager::doInitialization(Module &M) { 01177 bool Changed = false; 01178 01179 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 01180 Changed |= getContainedPass(Index)->doInitialization(M); 01181 01182 return Changed; 01183 } 01184 01185 bool BBPassManager::doFinalization(Module &M) { 01186 bool Changed = false; 01187 01188 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 01189 Changed |= getContainedPass(Index)->doFinalization(M); 01190 01191 return Changed; 01192 } 01193 01194 bool BBPassManager::doInitialization(Function &F) { 01195 bool Changed = false; 01196 01197 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01198 BasicBlockPass *BP = getContainedPass(Index); 01199 Changed |= BP->doInitialization(F); 01200 } 01201 01202 return Changed; 01203 } 01204 01205 bool BBPassManager::doFinalization(Function &F) { 01206 bool Changed = false; 01207 01208 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01209 BasicBlockPass *BP = getContainedPass(Index); 01210 Changed |= BP->doFinalization(F); 01211 } 01212 01213 return Changed; 01214 } 01215 01216 01217 //===----------------------------------------------------------------------===// 01218 // FunctionPassManager implementation 01219 01220 /// Create new Function pass manager 01221 FunctionPassManager::FunctionPassManager(ModuleProvider *P) { 01222 FPM = new FunctionPassManagerImpl(0); 01223 // FPM is the top level manager. 01224 FPM->setTopLevelManager(FPM); 01225 01226 AnalysisResolver *AR = new AnalysisResolver(*FPM); 01227 FPM->setResolver(AR); 01228 01229 MP = P; 01230 } 01231 01232 FunctionPassManager::~FunctionPassManager() { 01233 delete FPM; 01234 } 01235 01236 /// add - Add a pass to the queue of passes to run. This passes 01237 /// ownership of the Pass to the PassManager. When the 01238 /// PassManager_X is destroyed, the pass will be destroyed as well, so 01239 /// there is no need to delete the pass. (TODO delete passes.) 01240 /// This implies that all passes MUST be allocated with 'new'. 01241 void FunctionPassManager::add(Pass *P) { 01242 FPM->add(P); 01243 } 01244 01245 /// run - Execute all of the passes scheduled for execution. Keep 01246 /// track of whether any of the passes modifies the function, and if 01247 /// so, return true. 01248 /// 01249 bool FunctionPassManager::run(Function &F) { 01250 std::string errstr; 01251 if (MP->materializeFunction(&F, &errstr)) { 01252 llvm_report_error("Error reading bitcode file: " + errstr); 01253 } 01254 return FPM->run(F); 01255 } 01256 01257 01258 /// doInitialization - Run all of the initializers for the function passes. 01259 /// 01260 bool FunctionPassManager::doInitialization() { 01261 return FPM->doInitialization(*MP->getModule()); 01262 } 01263 01264 /// doFinalization - Run all of the finalizers for the function passes. 01265 /// 01266 bool FunctionPassManager::doFinalization() { 01267 return FPM->doFinalization(*MP->getModule()); 01268 } 01269 01270 //===----------------------------------------------------------------------===// 01271 // FunctionPassManagerImpl implementation 01272 // 01273 bool FunctionPassManagerImpl::doInitialization(Module &M) { 01274 bool Changed = false; 01275 01276 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 01277 Changed |= getContainedManager(Index)->doInitialization(M); 01278 01279 return Changed; 01280 } 01281 01282 bool FunctionPassManagerImpl::doFinalization(Module &M) { 01283 bool Changed = false; 01284 01285 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 01286 Changed |= getContainedManager(Index)->doFinalization(M); 01287 01288 return Changed; 01289 } 01290 01291 /// cleanup - After running all passes, clean up pass manager cache. 01292 void FPPassManager::cleanup() { 01293 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01294 FunctionPass *FP = getContainedPass(Index); 01295 AnalysisResolver *AR = FP->getResolver(); 01296 assert(AR && "Analysis Resolver is not set"); 01297 AR->clearAnalysisImpls(); 01298 } 01299 } 01300 01301 void FunctionPassManagerImpl::releaseMemoryOnTheFly() { 01302 if (!wasRun) 01303 return; 01304 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { 01305 FPPassManager *FPPM = getContainedManager(Index); 01306 for (unsigned Index = 0; Index < FPPM->getNumContainedPasses(); ++Index) { 01307 FPPM->getContainedPass(Index)->releaseMemory(); 01308 } 01309 } 01310 wasRun = false; 01311 } 01312 01313 // Execute all the passes managed by this top level manager. 01314 // Return true if any function is modified by a pass. 01315 bool FunctionPassManagerImpl::run(Function &F) { 01316 bool Changed = false; 01317 TimingInfo::createTheTimeInfo(); 01318 01319 dumpArguments(); 01320 dumpPasses(); 01321 01322 initializeAllAnalysisInfo(); 01323 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 01324 Changed |= getContainedManager(Index)->runOnFunction(F); 01325 01326 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 01327 getContainedManager(Index)->cleanup(); 01328 01329 wasRun = true; 01330 return Changed; 01331 } 01332 01333 //===----------------------------------------------------------------------===// 01334 // FPPassManager implementation 01335 01336 char FPPassManager::ID = 0; 01337 /// Print passes managed by this manager 01338 void FPPassManager::dumpPassStructure(unsigned Offset) { 01339 llvm::errs() << std::string(Offset*2, ' ') << "FunctionPass Manager\n"; 01340 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01341 FunctionPass *FP = getContainedPass(Index); 01342 FP->dumpPassStructure(Offset + 1); 01343 dumpLastUses(FP, Offset+1); 01344 } 01345 } 01346 01347 01348 /// Execute all of the passes scheduled for execution by invoking 01349 /// runOnFunction method. Keep track of whether any of the passes modifies 01350 /// the function, and if so, return true. 01351 bool FPPassManager::runOnFunction(Function &F) { 01352 if (F.isDeclaration()) 01353 return false; 01354 01355 bool Changed = false; 01356 01357 // Collect inherited analysis from Module level pass manager. 01358 populateInheritedAnalysis(TPM->activeStack); 01359 01360 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01361 FunctionPass *FP = getContainedPass(Index); 01362 01363 dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName()); 01364 dumpRequiredSet(FP); 01365 01366 initializeAnalysisImpl(FP); 01367 01368 { 01369 PassManagerPrettyStackEntry X(FP, F); 01370 01371 if (TheTimeInfo) TheTimeInfo->passStarted(FP); 01372 Changed |= FP->runOnFunction(F); 01373 if (TheTimeInfo) TheTimeInfo->passEnded(FP); 01374 } 01375 01376 if (Changed) 01377 dumpPassInfo(FP, MODIFICATION_MSG, ON_FUNCTION_MSG, F.getName()); 01378 dumpPreservedSet(FP); 01379 01380 verifyPreservedAnalysis(FP); 01381 removeNotPreservedAnalysis(FP); 01382 recordAvailableAnalysis(FP); 01383 removeDeadPasses(FP, F.getName(), ON_FUNCTION_MSG); 01384 01385 // If dominator information is available then verify the info if requested. 01386 verifyDomInfo(*FP, F); 01387 } 01388 return Changed; 01389 } 01390 01391 bool FPPassManager::runOnModule(Module &M) { 01392 bool Changed = doInitialization(M); 01393 01394 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 01395 runOnFunction(*I); 01396 01397 return Changed |= doFinalization(M); 01398 } 01399 01400 bool FPPassManager::doInitialization(Module &M) { 01401 bool Changed = false; 01402 01403 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 01404 Changed |= getContainedPass(Index)->doInitialization(M); 01405 01406 return Changed; 01407 } 01408 01409 bool FPPassManager::doFinalization(Module &M) { 01410 bool Changed = false; 01411 01412 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) 01413 Changed |= getContainedPass(Index)->doFinalization(M); 01414 01415 return Changed; 01416 } 01417 01418 //===----------------------------------------------------------------------===// 01419 // MPPassManager implementation 01420 01421 /// Execute all of the passes scheduled for execution by invoking 01422 /// runOnModule method. Keep track of whether any of the passes modifies 01423 /// the module, and if so, return true. 01424 bool 01425 MPPassManager::runOnModule(Module &M) { 01426 bool Changed = false; 01427 01428 // Initialize on-the-fly passes 01429 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator 01430 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end(); 01431 I != E; ++I) { 01432 FunctionPassManagerImpl *FPP = I->second; 01433 Changed |= FPP->doInitialization(M); 01434 } 01435 01436 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 01437 ModulePass *MP = getContainedPass(Index); 01438 01439 dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, 01440 M.getModuleIdentifier().c_str()); 01441 dumpRequiredSet(MP); 01442 01443 initializeAnalysisImpl(MP); 01444 01445 { 01446 PassManagerPrettyStackEntry X(MP, M); 01447 if (TheTimeInfo) TheTimeInfo->passStarted(MP); 01448 Changed |= MP->runOnModule(M); 01449 if (TheTimeInfo) TheTimeInfo->passEnded(MP); 01450 } 01451 01452 if (Changed) 01453 dumpPassInfo(MP, MODIFICATION_MSG, ON_MODULE_MSG, 01454 M.getModuleIdentifier().c_str()); 01455 dumpPreservedSet(MP); 01456 01457 verifyPreservedAnalysis(MP); 01458 removeNotPreservedAnalysis(MP); 01459 recordAvailableAnalysis(MP); 01460 removeDeadPasses(MP, M.getModuleIdentifier().c_str(), ON_MODULE_MSG); 01461 } 01462 01463 // Finalize on-the-fly passes 01464 for (std::map<Pass *, FunctionPassManagerImpl *>::iterator 01465 I = OnTheFlyManagers.begin(), E = OnTheFlyManagers.end(); 01466 I != E; ++I) { 01467 FunctionPassManagerImpl *FPP = I->second; 01468 // We don't know when is the last time an on-the-fly pass is run, 01469 // so we need to releaseMemory / finalize here 01470 FPP->releaseMemoryOnTheFly(); 01471 Changed |= FPP->doFinalization(M); 01472 } 01473 return Changed; 01474 } 01475 01476 /// Add RequiredPass into list of lower level passes required by pass P. 01477 /// RequiredPass is run on the fly by Pass Manager when P requests it 01478 /// through getAnalysis interface. 01479 void MPPassManager::addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) { 01480 assert(P->getPotentialPassManagerType() == PMT_ModulePassManager && 01481 "Unable to handle Pass that requires lower level Analysis pass"); 01482 assert((P->getPotentialPassManagerType() < 01483 RequiredPass->getPotentialPassManagerType()) && 01484 "Unable to handle Pass that requires lower level Analysis pass"); 01485 01486 FunctionPassManagerImpl *FPP = OnTheFlyManagers[P]; 01487 if (!FPP) { 01488 FPP = new FunctionPassManagerImpl(0); 01489 // FPP is the top level manager. 01490 FPP->setTopLevelManager(FPP); 01491 01492 OnTheFlyManagers[P] = FPP; 01493 } 01494 FPP->add(RequiredPass); 01495 01496 // Register P as the last user of RequiredPass. 01497 SmallVector<Pass *, 12> LU; 01498 LU.push_back(RequiredPass); 01499 FPP->setLastUser(LU, P); 01500 } 01501 01502 /// Return function pass corresponding to PassInfo PI, that is 01503 /// required by module pass MP. Instantiate analysis pass, by using 01504 /// its runOnFunction() for function F. 01505 Pass* MPPassManager::getOnTheFlyPass(Pass *MP, const PassInfo *PI, Function &F){ 01506 FunctionPassManagerImpl *FPP = OnTheFlyManagers[MP]; 01507 assert(FPP && "Unable to find on the fly pass"); 01508 01509 FPP->releaseMemoryOnTheFly(); 01510 FPP->run(F); 01511 return (dynamic_cast<PMTopLevelManager *>(FPP))->findAnalysisPass(PI); 01512 } 01513 01514 01515 //===----------------------------------------------------------------------===// 01516 // PassManagerImpl implementation 01517 // 01518 /// run - Execute all of the passes scheduled for execution. Keep track of 01519 /// whether any of the passes modifies the module, and if so, return true. 01520 bool PassManagerImpl::run(Module &M) { 01521 bool Changed = false; 01522 TimingInfo::createTheTimeInfo(); 01523 01524 dumpArguments(); 01525 dumpPasses(); 01526 01527 initializeAllAnalysisInfo(); 01528 for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) 01529 Changed |= getContainedManager(Index)->runOnModule(M); 01530 return Changed; 01531 } 01532 01533 //===----------------------------------------------------------------------===// 01534 // PassManager implementation 01535 01536 /// Create new pass manager 01537 PassManager::PassManager() { 01538 PM = new PassManagerImpl(0); 01539 // PM is the top level manager 01540 PM->setTopLevelManager(PM); 01541 } 01542 01543 PassManager::~PassManager() { 01544 delete PM; 01545 } 01546 01547 /// add - Add a pass to the queue of passes to run. This passes ownership of 01548 /// the Pass to the PassManager. When the PassManager is destroyed, the pass 01549 /// will be destroyed as well, so there is no need to delete the pass. This 01550 /// implies that all passes MUST be allocated with 'new'. 01551 void PassManager::add(Pass *P) { 01552 PM->add(P); 01553 } 01554 01555 /// run - Execute all of the passes scheduled for execution. Keep track of 01556 /// whether any of the passes modifies the module, and if so, return true. 01557 bool PassManager::run(Module &M) { 01558 return PM->run(M); 01559 } 01560 01561 //===----------------------------------------------------------------------===// 01562 // TimingInfo Class - This class is used to calculate information about the 01563 // amount of time each pass takes to execute. This only happens with 01564 // -time-passes is enabled on the command line. 01565 // 01566 bool llvm::TimePassesIsEnabled = false; 01567 static cl::opt<bool,true> 01568 EnableTiming("time-passes", cl::location(TimePassesIsEnabled), 01569 cl::desc("Time each pass, printing elapsed time for each on exit")); 01570 01571 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer to 01572 // a non null value (if the -time-passes option is enabled) or it leaves it 01573 // null. It may be called multiple times. 01574 void TimingInfo::createTheTimeInfo() { 01575 if (!TimePassesIsEnabled || TheTimeInfo) return; 01576 01577 // Constructed the first time this is called, iff -time-passes is enabled. 01578 // This guarantees that the object will be constructed before static globals, 01579 // thus it will be destroyed before them. 01580 static ManagedStatic<TimingInfo> TTI; 01581 TheTimeInfo = &*TTI; 01582 } 01583 01584 /// If TimingInfo is enabled then start pass timer. 01585 void llvm::StartPassTimer(Pass *P) { 01586 if (TheTimeInfo) 01587 TheTimeInfo->passStarted(P); 01588 } 01589 01590 /// If TimingInfo is enabled then stop pass timer. 01591 void llvm::StopPassTimer(Pass *P) { 01592 if (TheTimeInfo) 01593 TheTimeInfo->passEnded(P); 01594 } 01595 01596 //===----------------------------------------------------------------------===// 01597 // PMStack implementation 01598 // 01599 01600 // Pop Pass Manager from the stack and clear its analysis info. 01601 void PMStack::pop() { 01602 01603 PMDataManager *Top = this->top(); 01604 Top->initializeAnalysisInfo(); 01605 01606 S.pop_back(); 01607 } 01608 01609 // Push PM on the stack and set its top level manager. 01610 void PMStack::push(PMDataManager *PM) { 01611 assert(PM && "Unable to push. Pass Manager expected"); 01612 01613 if (!this->empty()) { 01614 PMTopLevelManager *TPM = this->top()->getTopLevelManager(); 01615 01616 assert(TPM && "Unable to find top level manager"); 01617 TPM->addIndirectPassManager(PM); 01618 PM->setTopLevelManager(TPM); 01619 } 01620 01621 S.push_back(PM); 01622 } 01623 01624 // Dump content of the pass manager stack. 01625 void PMStack::dump() { 01626 for (std::deque<PMDataManager *>::iterator I = S.begin(), 01627 E = S.end(); I != E; ++I) 01628 printf("%s ", dynamic_cast<Pass *>(*I)->getPassName()); 01629 01630 if (!S.empty()) 01631 printf("\n"); 01632 } 01633 01634 /// Find appropriate Module Pass Manager in the PM Stack and 01635 /// add self into that manager. 01636 void ModulePass::assignPassManager(PMStack &PMS, 01637 PassManagerType PreferredType) { 01638 // Find Module Pass Manager 01639 while(!PMS.empty()) { 01640 PassManagerType TopPMType = PMS.top()->getPassManagerType(); 01641 if (TopPMType == PreferredType) 01642 break; // We found desired pass manager 01643 else if (TopPMType > PMT_ModulePassManager) 01644 PMS.pop(); // Pop children pass managers 01645 else 01646 break; 01647 } 01648 assert(!PMS.empty() && "Unable to find appropriate Pass Manager"); 01649 PMS.top()->add(this); 01650 } 01651 01652 /// Find appropriate Function Pass Manager or Call Graph Pass Manager 01653 /// in the PM Stack and add self into that manager. 01654 void FunctionPass::assignPassManager(PMStack &PMS, 01655 PassManagerType PreferredType) { 01656 01657 // Find Module Pass Manager 01658 while(!PMS.empty()) { 01659 if (PMS.top()->getPassManagerType() > PMT_FunctionPassManager) 01660 PMS.pop(); 01661 else 01662 break; 01663 } 01664 FPPassManager *FPP = dynamic_cast<FPPassManager *>(PMS.top()); 01665 01666 // Create new Function Pass Manager 01667 if (!FPP) { 01668 assert(!PMS.empty() && "Unable to create Function Pass Manager"); 01669 PMDataManager *PMD = PMS.top(); 01670 01671 // [1] Create new Function Pass Manager 01672 FPP = new FPPassManager(PMD->getDepth() + 1); 01673 FPP->populateInheritedAnalysis(PMS); 01674 01675 // [2] Set up new manager's top level manager 01676 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 01677 TPM->addIndirectPassManager(FPP); 01678 01679 // [3] Assign manager to manage this new manager. This may create 01680 // and push new managers into PMS 01681 FPP->assignPassManager(PMS, PMD->getPassManagerType()); 01682 01683 // [4] Push new manager into PMS 01684 PMS.push(FPP); 01685 } 01686 01687 // Assign FPP as the manager of this pass. 01688 FPP->add(this); 01689 } 01690 01691 /// Find appropriate Basic Pass Manager or Call Graph Pass Manager 01692 /// in the PM Stack and add self into that manager. 01693 void BasicBlockPass::assignPassManager(PMStack &PMS, 01694 PassManagerType PreferredType) { 01695 BBPassManager *BBP = NULL; 01696 01697 // Basic Pass Manager is a leaf pass manager. It does not handle 01698 // any other pass manager. 01699 if (!PMS.empty()) 01700 BBP = dynamic_cast<BBPassManager *>(PMS.top()); 01701 01702 // If leaf manager is not Basic Block Pass manager then create new 01703 // basic Block Pass manager. 01704 01705 if (!BBP) { 01706 assert(!PMS.empty() && "Unable to create BasicBlock Pass Manager"); 01707 PMDataManager *PMD = PMS.top(); 01708 01709 // [1] Create new Basic Block Manager 01710 BBP = new BBPassManager(PMD->getDepth() + 1); 01711 01712 // [2] Set up new manager's top level manager 01713 // Basic Block Pass Manager does not live by itself 01714 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 01715 TPM->addIndirectPassManager(BBP); 01716 01717 // [3] Assign manager to manage this new manager. This may create 01718 // and push new managers into PMS 01719 BBP->assignPassManager(PMS); 01720 01721 // [4] Push new manager into PMS 01722 PMS.push(BBP); 01723 } 01724 01725 // Assign BBP as the manager of this pass. 01726 BBP->add(this); 01727 } 01728 01729 PassManagerBase::~PassManagerBase() {} 01730 01731 /*===-- C Bindings --------------------------------------------------------===*/ 01732 01733 LLVMPassManagerRef LLVMCreatePassManager() { 01734 return wrap(new PassManager()); 01735 } 01736 01737 LLVMPassManagerRef LLVMCreateFunctionPassManager(LLVMModuleProviderRef P) { 01738 return wrap(new FunctionPassManager(unwrap(P))); 01739 } 01740 01741 int LLVMRunPassManager(LLVMPassManagerRef PM, LLVMModuleRef M) { 01742 return unwrap<PassManager>(PM)->run(*unwrap(M)); 01743 } 01744 01745 int LLVMInitializeFunctionPassManager(LLVMPassManagerRef FPM) { 01746 return unwrap<FunctionPassManager>(FPM)->doInitialization(); 01747 } 01748 01749 int LLVMRunFunctionPassManager(LLVMPassManagerRef FPM, LLVMValueRef F) { 01750 return unwrap<FunctionPassManager>(FPM)->run(*unwrap<Function>(F)); 01751 } 01752 01753 int LLVMFinalizeFunctionPassManager(LLVMPassManagerRef FPM) { 01754 return unwrap<FunctionPassManager>(FPM)->doFinalization(); 01755 } 01756 01757 void LLVMDisposePassManager(LLVMPassManagerRef PM) { 01758 delete unwrap(PM); 01759 }