LLVM API Documentation
00001 //===- PassManagerT.h - Container for Passes --------------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the PassManagerT class. This class is used to hold, 00011 // maintain, and optimize execution of Pass's. The PassManager class ensures 00012 // that analysis results are available before a pass runs, and that Pass's are 00013 // destroyed when the PassManager is destroyed. 00014 // 00015 // The PassManagerT template is instantiated three times to do its job. The 00016 // public PassManager class is a Pimpl around the PassManagerT<Module> interface 00017 // to avoid having all of the PassManager clients being exposed to the 00018 // implementation details herein. 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #ifndef LLVM_PASSMANAGER_T_H 00023 #define LLVM_PASSMANAGER_T_H 00024 00025 #include "llvm/Pass.h" 00026 #include "llvm/Support/CommandLine.h" 00027 #include "llvm/Support/LeakDetector.h" 00028 #include "llvm/Support/Timer.h" 00029 #include <algorithm> 00030 #include <iostream> 00031 00032 namespace llvm { 00033 00034 //===----------------------------------------------------------------------===// 00035 // Pass debugging information. Often it is useful to find out what pass is 00036 // running when a crash occurs in a utility. When this library is compiled with 00037 // debugging on, a command line option (--debug-pass) is enabled that causes the 00038 // pass name to be printed before it executes. 00039 // 00040 00041 // Different debug levels that can be enabled... 00042 enum PassDebugLevel { 00043 None, Arguments, Structure, Executions, Details 00044 }; 00045 00046 static cl::opt<enum PassDebugLevel> 00047 PassDebugging("debug-pass", cl::Hidden, 00048 cl::desc("Print PassManager debugging information"), 00049 cl::values( 00050 clEnumVal(None , "disable debug output"), 00051 clEnumVal(Arguments , "print pass arguments to pass to 'opt'"), 00052 clEnumVal(Structure , "print pass structure before run()"), 00053 clEnumVal(Executions, "print pass name before it is executed"), 00054 clEnumVal(Details , "print pass details when it is executed"), 00055 clEnumValEnd)); 00056 00057 //===----------------------------------------------------------------------===// 00058 // PMDebug class - a set of debugging functions, that are not to be 00059 // instantiated by the template. 00060 // 00061 struct PMDebug { 00062 static void PerformPassStartupStuff(Pass *P) { 00063 // If debugging is enabled, print out argument information... 00064 if (PassDebugging >= Arguments) { 00065 std::cerr << "Pass Arguments: "; 00066 PrintArgumentInformation(P); 00067 std::cerr << "\n"; 00068 00069 // Print the pass execution structure 00070 if (PassDebugging >= Structure) 00071 P->dumpPassStructure(); 00072 } 00073 } 00074 00075 static void PrintArgumentInformation(const Pass *P); 00076 static void PrintPassInformation(unsigned,const char*,Pass *, Module *); 00077 static void PrintPassInformation(unsigned,const char*,Pass *, Function *); 00078 static void PrintPassInformation(unsigned,const char*,Pass *, BasicBlock *); 00079 static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P, 00080 const std::vector<AnalysisID> &); 00081 }; 00082 00083 00084 //===----------------------------------------------------------------------===// 00085 // TimingInfo Class - This class is used to calculate information about the 00086 // amount of time each pass takes to execute. This only happens when 00087 // -time-passes is enabled on the command line. 00088 // 00089 00090 class TimingInfo { 00091 std::map<Pass*, Timer> TimingData; 00092 TimerGroup TG; 00093 00094 // Private ctor, must use 'create' member 00095 TimingInfo() : TG("... Pass execution timing report ...") {} 00096 public: 00097 // TimingDtor - Print out information about timing information 00098 ~TimingInfo() { 00099 // Delete all of the timers... 00100 TimingData.clear(); 00101 // TimerGroup is deleted next, printing the report. 00102 } 00103 00104 // createTheTimeInfo - This method either initializes the TheTimeInfo pointer 00105 // to a non null value (if the -time-passes option is enabled) or it leaves it 00106 // null. It may be called multiple times. 00107 static void createTheTimeInfo(); 00108 00109 void passStarted(Pass *P) { 00110 if (dynamic_cast<AnalysisResolver*>(P)) return; 00111 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 00112 if (I == TimingData.end()) 00113 I=TimingData.insert(std::make_pair(P, Timer(P->getPassName(), TG))).first; 00114 I->second.startTimer(); 00115 } 00116 void passEnded(Pass *P) { 00117 if (dynamic_cast<AnalysisResolver*>(P)) return; 00118 std::map<Pass*, Timer>::iterator I = TimingData.find(P); 00119 assert (I != TimingData.end() && "passStarted/passEnded not nested right!"); 00120 I->second.stopTimer(); 00121 } 00122 }; 00123 00124 static TimingInfo *TheTimeInfo; 00125 00126 struct BBTraits { 00127 typedef BasicBlock UnitType; 00128 00129 // PassClass - The type of passes tracked by this PassManager 00130 typedef BasicBlockPass PassClass; 00131 00132 // SubPassClass - The types of classes that should be collated together 00133 // This is impossible to match, so BasicBlock instantiations of PassManagerT 00134 // do not collate. 00135 // 00136 typedef BasicBlockPassManager SubPassClass; 00137 00138 // BatcherClass - The type to use for collation of subtypes... This class is 00139 // never instantiated for the BasicBlockPassManager, but it must be an 00140 // instance of PassClass to typecheck. 00141 // 00142 typedef PassClass BatcherClass; 00143 00144 // ParentClass - The type of the parent PassManager... 00145 typedef FunctionPassManagerT ParentClass; 00146 00147 // PMType - The type of this passmanager 00148 typedef BasicBlockPassManager PMType; 00149 }; 00150 00151 struct FTraits { 00152 typedef Function UnitType; 00153 00154 // PassClass - The type of passes tracked by this PassManager 00155 typedef FunctionPass PassClass; 00156 00157 // SubPassClass - The types of classes that should be collated together 00158 typedef BasicBlockPass SubPassClass; 00159 00160 // BatcherClass - The type to use for collation of subtypes... 00161 typedef BasicBlockPassManager BatcherClass; 00162 00163 // ParentClass - The type of the parent PassManager... 00164 typedef ModulePassManager ParentClass; 00165 00166 // PMType - The type of this passmanager 00167 typedef FunctionPassManagerT PMType; 00168 }; 00169 00170 struct MTraits { 00171 typedef Module UnitType; 00172 00173 // PassClass - The type of passes tracked by this PassManager 00174 typedef ModulePass PassClass; 00175 00176 // SubPassClass - The types of classes that should be collated together 00177 typedef FunctionPass SubPassClass; 00178 00179 // BatcherClass - The type to use for collation of subtypes... 00180 typedef FunctionPassManagerT BatcherClass; 00181 00182 // ParentClass - The type of the parent PassManager... 00183 typedef AnalysisResolver ParentClass; 00184 00185 // PMType - The type of this passmanager 00186 typedef ModulePassManager PMType; 00187 }; 00188 00189 00190 //===----------------------------------------------------------------------===// 00191 // PassManagerT - Container object for passes. The PassManagerT destructor 00192 // deletes all passes contained inside of the PassManagerT, so you shouldn't 00193 // delete passes manually, and all passes should be dynamically allocated. 00194 // 00195 template<typename Trait> class PassManagerT : public AnalysisResolver { 00196 00197 typedef typename Trait::PassClass PassClass; 00198 typedef typename Trait::UnitType UnitType; 00199 typedef typename Trait::ParentClass ParentClass; 00200 typedef typename Trait::SubPassClass SubPassClass; 00201 typedef typename Trait::BatcherClass BatcherClass; 00202 typedef typename Trait::PMType PMType; 00203 00204 friend class ModulePass; 00205 friend class FunctionPass; 00206 friend class BasicBlockPass; 00207 00208 friend class ImmutablePass; 00209 00210 friend class BasicBlockPassManager; 00211 friend class FunctionPassManagerT; 00212 friend class ModulePassManager; 00213 00214 std::vector<PassClass*> Passes; // List of passes to run 00215 std::vector<ImmutablePass*> ImmutablePasses; // List of immutable passes 00216 00217 // The parent of this pass manager... 00218 ParentClass * const Parent; 00219 00220 // The current batcher if one is in use, or null 00221 BatcherClass *Batcher; 00222 00223 // CurrentAnalyses - As the passes are being run, this map contains the 00224 // analyses that are available to the current pass for use. This is accessed 00225 // through the getAnalysis() function in this class and in Pass. 00226 // 00227 std::map<AnalysisID, Pass*> CurrentAnalyses; 00228 00229 // LastUseOf - This map keeps track of the last usage in our pipeline of a 00230 // particular pass. When executing passes, the memory for .first is free'd 00231 // after .second is run. 00232 // 00233 std::map<Pass*, Pass*> LastUseOf; 00234 00235 public: 00236 00237 // getPMName() - Return the name of the unit the PassManager operates on for 00238 // debugging. 00239 virtual const char *getPMName() const =0; 00240 00241 virtual const char *getPassName() const =0; 00242 00243 virtual bool runPass(PassClass *P, UnitType *M) =0; 00244 00245 // TODO:Figure out what pure virtuals remain. 00246 00247 00248 PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {} 00249 virtual ~PassManagerT() { 00250 // Delete all of the contained passes... 00251 for (typename std::vector<PassClass*>::iterator 00252 I = Passes.begin(), E = Passes.end(); I != E; ++I) 00253 delete *I; 00254 00255 for (std::vector<ImmutablePass*>::iterator 00256 I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I) 00257 delete *I; 00258 } 00259 00260 // run - Run all of the queued passes on the specified module in an optimal 00261 // way. 00262 virtual bool runOnUnit(UnitType *M) { 00263 closeBatcher(); 00264 CurrentAnalyses.clear(); 00265 00266 TimingInfo::createTheTimeInfo(); 00267 00268 addImmutablePasses(); 00269 00270 // LastUserOf - This contains the inverted LastUseOfMap... 00271 std::map<Pass *, std::vector<Pass*> > LastUserOf; 00272 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(), 00273 E = LastUseOf.end(); I != E; ++I) 00274 LastUserOf[I->second].push_back(I->first); 00275 00276 // Output debug information... 00277 assert(dynamic_cast<PassClass*>(this) && 00278 "It wasn't the PassClass I thought it was"); 00279 if (Parent == 0) 00280 PMDebug::PerformPassStartupStuff((dynamic_cast<PMType*>(this))); 00281 00282 return runPasses(M, LastUserOf); 00283 } 00284 00285 // dumpPassStructure - Implement the -debug-passes=PassStructure option 00286 inline void dumpPassStructure(unsigned Offset = 0) { 00287 // Print out the immutable passes... 00288 00289 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) 00290 ImmutablePasses[i]->dumpPassStructure(0); 00291 00292 std::cerr << std::string(Offset*2, ' ') << this->getPMName() 00293 << " Pass Manager\n"; 00294 for (typename std::vector<PassClass*>::iterator 00295 I = Passes.begin(), E = Passes.end(); I != E; ++I) { 00296 PassClass *P = *I; 00297 P->dumpPassStructure(Offset+1); 00298 00299 // Loop through and see which classes are destroyed after this one... 00300 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(), 00301 E = LastUseOf.end(); I != E; ++I) { 00302 if (P == I->second) { 00303 std::cerr << "--" << std::string(Offset*2, ' '); 00304 I->first->dumpPassStructure(0); 00305 } 00306 } 00307 } 00308 } 00309 00310 Pass *getImmutablePassOrNull(const PassInfo *ID) const { 00311 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 00312 const PassInfo *IPID = ImmutablePasses[i]->getPassInfo(); 00313 if (IPID == ID) 00314 return ImmutablePasses[i]; 00315 00316 // This pass is the current implementation of all of the interfaces it 00317 // implements as well. 00318 // 00319 const std::vector<const PassInfo*> &II = 00320 IPID->getInterfacesImplemented(); 00321 for (unsigned j = 0, e = II.size(); j != e; ++j) 00322 if (II[j] == ID) return ImmutablePasses[i]; 00323 } 00324 return 0; 00325 } 00326 00327 Pass *getAnalysisOrNullDown(const PassInfo *ID) const { 00328 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID); 00329 00330 if (I != CurrentAnalyses.end()) 00331 return I->second; // Found it. 00332 00333 if (Pass *P = getImmutablePassOrNull(ID)) 00334 return P; 00335 00336 if (Batcher) 00337 return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID); 00338 return 0; 00339 } 00340 00341 Pass *getAnalysisOrNullUp(const PassInfo *ID) const { 00342 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID); 00343 if (I != CurrentAnalyses.end()) 00344 return I->second; // Found it. 00345 00346 if (Parent) // Try scanning... 00347 return Parent->getAnalysisOrNullUp(ID); 00348 else if (!ImmutablePasses.empty()) 00349 return getImmutablePassOrNull(ID); 00350 return 0; 00351 } 00352 00353 // markPassUsed - Inform higher level pass managers (and ourselves) 00354 // that these analyses are being used by this pass. This is used to 00355 // make sure that analyses are not free'd before we have to use 00356 // them... 00357 // 00358 void markPassUsed(const PassInfo *P, Pass *User) { 00359 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(P); 00360 00361 if (I != CurrentAnalyses.end()) { 00362 LastUseOf[I->second] = User; // Local pass, extend the lifetime 00363 00364 // Prolong live range of analyses that are needed after an analysis pass 00365 // is destroyed, for querying by subsequent passes 00366 AnalysisUsage AnUsage; 00367 I->second->getAnalysisUsage(AnUsage); 00368 const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet(); 00369 for (std::vector<AnalysisID>::const_iterator i = IDs.begin(), 00370 e = IDs.end(); i != e; ++i) 00371 markPassUsed(*i, User); 00372 00373 } else { 00374 // Pass not in current available set, must be a higher level pass 00375 // available to us, propagate to parent pass manager... We tell the 00376 // parent that we (the passmanager) are using the analysis so that it 00377 // frees the analysis AFTER this pass manager runs. 00378 // 00379 if (Parent) { 00380 assert(dynamic_cast<Pass*>(this) && 00381 "It wasn't the Pass type I thought it was."); 00382 Parent->markPassUsed(P, dynamic_cast<Pass*>(this)); 00383 } else { 00384 assert(getAnalysisOrNullUp(P) && 00385 dynamic_cast<ImmutablePass*>(getAnalysisOrNullUp(P)) && 00386 "Pass available but not found! " 00387 "Perhaps this is a module pass requiring a function pass?"); 00388 } 00389 } 00390 } 00391 00392 // Return the number of parent PassManagers that exist 00393 virtual unsigned getDepth() const { 00394 if (Parent == 0) return 0; 00395 return 1 + Parent->getDepth(); 00396 } 00397 00398 virtual unsigned getNumContainedPasses() const { return Passes.size(); } 00399 00400 virtual const Pass *getContainedPass(unsigned N) const { 00401 assert(N < Passes.size() && "Pass number out of range!"); 00402 return Passes[N]; 00403 } 00404 00405 // add - Add a pass to the queue of passes to run. This gives ownership of 00406 // the Pass to the PassManager. When the PassManager is destroyed, the pass 00407 // will be destroyed as well, so there is no need to delete the pass. This 00408 // implies that all passes MUST be new'd. 00409 // 00410 void add(PassClass *P) { 00411 // Get information about what analyses the pass uses... 00412 AnalysisUsage AnUsage; 00413 P->getAnalysisUsage(AnUsage); 00414 00415 addRequiredPasses(AnUsage.getRequiredSet()); 00416 00417 // Tell the pass to add itself to this PassManager... the way it does so 00418 // depends on the class of the pass, and is critical to laying out passes in 00419 // an optimal order.. 00420 // 00421 assert(dynamic_cast<PMType*>(this) && 00422 "It wasn't the right passmanager type."); 00423 P->addToPassManager(static_cast<PMType*>(this), AnUsage); 00424 } 00425 00426 // add - H4x0r an ImmutablePass into a PassManager that might not be 00427 // expecting one. 00428 // 00429 void add(ImmutablePass *P) { 00430 // Get information about what analyses the pass uses... 00431 AnalysisUsage AnUsage; 00432 P->getAnalysisUsage(AnUsage); 00433 00434 addRequiredPasses(AnUsage.getRequiredSet()); 00435 00436 // Add the ImmutablePass to this PassManager. 00437 addPass(P, AnUsage); 00438 } 00439 00440 private: 00441 // addPass - These functions are used to implement the subclass specific 00442 // behaviors present in PassManager. Basically the add(Pass*) method ends up 00443 // reflecting its behavior into a Pass::addToPassManager call. Subclasses of 00444 // Pass override it specifically so that they can reflect the type 00445 // information inherent in "this" back to the PassManager. 00446 // 00447 // For generic Pass subclasses (which are interprocedural passes), we simply 00448 // add the pass to the end of the pass list and terminate any accumulation of 00449 // FunctionPass's that are present. 00450 // 00451 void addPass(PassClass *P, AnalysisUsage &AnUsage) { 00452 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet(); 00453 00454 // FIXME: If this pass being added isn't killed by any of the passes in the 00455 // batcher class then we can reorder the pass to execute before the batcher 00456 // does, which will potentially allow us to batch more passes! 00457 // 00458 if (Batcher) 00459 closeBatcher(); // This pass cannot be batched! 00460 00461 // Set the Resolver instance variable in the Pass so that it knows where to 00462 // find this object... 00463 // 00464 setAnalysisResolver(P, this); 00465 Passes.push_back(P); 00466 00467 // Inform higher level pass managers (and ourselves) that these analyses are 00468 // being used by this pass. This is used to make sure that analyses are not 00469 // free'd before we have to use them... 00470 // 00471 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(), 00472 E = RequiredSet.end(); I != E; ++I) 00473 markPassUsed(*I, P); // Mark *I as used by P 00474 00475 removeNonPreservedAnalyses(AnUsage); 00476 00477 makeCurrentlyAvailable(P); 00478 00479 // For now assume that our results are never used... 00480 LastUseOf[P] = P; 00481 } 00482 00483 // For FunctionPass subclasses, we must be sure to batch the FunctionPass's 00484 // together in a BatcherClass object so that all of the analyses are run 00485 // together a function at a time. 00486 // 00487 void addPass(SubPassClass *MP, AnalysisUsage &AnUsage) { 00488 00489 if (Batcher == 0) { // If we don't have a batcher yet, make one now. 00490 assert(dynamic_cast<PMType*>(this) && 00491 "It wasn't the PassManager type I thought it was"); 00492 Batcher = new BatcherClass((static_cast<PMType*>(this))); 00493 } 00494 00495 // The Batcher will queue the passes up 00496 MP->addToPassManager(Batcher, AnUsage); 00497 } 00498 00499 // closeBatcher - Terminate the batcher that is being worked on. 00500 void closeBatcher() { 00501 if (Batcher) { 00502 Passes.push_back(Batcher); 00503 Batcher = 0; 00504 } 00505 } 00506 00507 void addRequiredPasses(const std::vector<AnalysisID> &Required) { 00508 for (std::vector<AnalysisID>::const_iterator I = Required.begin(), 00509 E = Required.end(); I != E; ++I) { 00510 if (getAnalysisOrNullDown(*I) == 0) { 00511 Pass *AP = (*I)->createPass(); 00512 if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (AP)) add(IP); 00513 else if (PassClass *RP = dynamic_cast<PassClass *> (AP)) add(RP); 00514 else assert (0 && "Wrong kind of pass for this PassManager"); 00515 } 00516 } 00517 } 00518 00519 public: 00520 // When an ImmutablePass is added, it gets added to the top level pass 00521 // manager. 00522 void addPass(ImmutablePass *IP, AnalysisUsage &AU) { 00523 if (Parent) { // Make sure this request goes to the top level passmanager... 00524 Parent->addPass(IP, AU); 00525 return; 00526 } 00527 00528 // Set the Resolver instance variable in the Pass so that it knows where to 00529 // find this object... 00530 // 00531 setAnalysisResolver(IP, this); 00532 ImmutablePasses.push_back(IP); 00533 00534 // All Required analyses should be available to the pass as it initializes! 00535 // Here we fill in the AnalysisImpls member of the pass so that it can 00536 // successfully use the getAnalysis() method to retrieve the implementations 00537 // it needs. 00538 // 00539 IP->AnalysisImpls.clear(); 00540 IP->AnalysisImpls.reserve(AU.getRequiredSet().size()); 00541 for (std::vector<const PassInfo *>::const_iterator 00542 I = AU.getRequiredSet().begin(), 00543 E = AU.getRequiredSet().end(); I != E; ++I) { 00544 Pass *Impl = getAnalysisOrNullUp(*I); 00545 if (Impl == 0) { 00546 std::cerr << "Analysis '" << (*I)->getPassName() 00547 << "' used but not available!"; 00548 assert(0 && "Analysis used but not available!"); 00549 } else if (PassDebugging == Details) { 00550 if ((*I)->getPassName() != std::string(Impl->getPassName())) 00551 std::cerr << " Interface '" << (*I)->getPassName() 00552 << "' implemented by '" << Impl->getPassName() << "'\n"; 00553 } 00554 IP->AnalysisImpls.push_back(std::make_pair(*I, Impl)); 00555 } 00556 00557 // Initialize the immutable pass... 00558 IP->initializePass(); 00559 } 00560 private: 00561 00562 // Add any immutable passes to the CurrentAnalyses set... 00563 inline void addImmutablePasses() { 00564 for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) { 00565 ImmutablePass *IPass = ImmutablePasses[i]; 00566 if (const PassInfo *PI = IPass->getPassInfo()) { 00567 CurrentAnalyses[PI] = IPass; 00568 00569 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 00570 for (unsigned i = 0, e = II.size(); i != e; ++i) 00571 CurrentAnalyses[II[i]] = IPass; 00572 } 00573 } 00574 } 00575 00576 // Run all of the passes 00577 inline bool runPasses(UnitType *M, 00578 std::map<Pass *, std::vector<Pass*> > &LastUserOf) { 00579 bool MadeChanges = false; 00580 00581 for (unsigned i = 0, e = Passes.size(); i < e; ++i) { 00582 PassClass *P = Passes[i]; 00583 00584 PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, M); 00585 00586 // Get information about what analyses the pass uses... 00587 AnalysisUsage AnUsage; 00588 P->getAnalysisUsage(AnUsage); 00589 PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P, 00590 AnUsage.getRequiredSet()); 00591 00592 initialiseAnalysisImpl(P, AnUsage); 00593 00594 // Run the sub pass! 00595 if (TheTimeInfo) TheTimeInfo->passStarted(P); 00596 bool Changed = runPass(P, M); 00597 if (TheTimeInfo) TheTimeInfo->passEnded(P); 00598 MadeChanges |= Changed; 00599 00600 // Check for memory leaks by the pass... 00601 LeakDetector::checkForGarbage(std::string("after running pass '") + 00602 P->getPassName() + "'"); 00603 00604 if (Changed) 00605 PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P, M); 00606 PMDebug::PrintAnalysisSetInfo(getDepth(), "Preserved", P, 00607 AnUsage.getPreservedSet()); 00608 00609 // Erase all analyses not in the preserved set 00610 removeNonPreservedAnalyses(AnUsage); 00611 00612 makeCurrentlyAvailable(P); 00613 00614 // free memory and remove dead passes from the CurrentAnalyses list... 00615 removeDeadPasses(P, M, LastUserOf); 00616 } 00617 00618 return MadeChanges; 00619 } 00620 00621 // All Required analyses should be available to the pass as it runs! Here 00622 // we fill in the AnalysisImpls member of the pass so that it can 00623 // successfully use the getAnalysis() method to retrieve the 00624 // implementations it needs. 00625 // 00626 inline void initialiseAnalysisImpl(PassClass *P, AnalysisUsage &AnUsage) { 00627 P->AnalysisImpls.clear(); 00628 P->AnalysisImpls.reserve(AnUsage.getRequiredSet().size()); 00629 00630 for (std::vector<const PassInfo *>::const_iterator 00631 I = AnUsage.getRequiredSet().begin(), 00632 E = AnUsage.getRequiredSet().end(); I != E; ++I) { 00633 Pass *Impl = getAnalysisOrNullUp(*I); 00634 if (Impl == 0) { 00635 std::cerr << "Analysis '" << (*I)->getPassName() 00636 << "' used but not available!"; 00637 assert(0 && "Analysis used but not available!"); 00638 } else if (PassDebugging == Details) { 00639 if ((*I)->getPassName() != std::string(Impl->getPassName())) 00640 std::cerr << " Interface '" << (*I)->getPassName() 00641 << "' implemented by '" << Impl->getPassName() << "'\n"; 00642 } 00643 00644 P->AnalysisImpls.push_back(std::make_pair(*I, Impl)); 00645 } 00646 } 00647 00648 inline void removeNonPreservedAnalyses(AnalysisUsage &AnUsage) { 00649 if (!AnUsage.getPreservesAll()) { 00650 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet(); 00651 for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin(), 00652 E = CurrentAnalyses.end(); I != E; ) 00653 if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) != 00654 PreservedSet.end()) 00655 ++I; // This analysis is preserved, leave it in the available set... 00656 else { 00657 if (!dynamic_cast<ImmutablePass*>(I->second)) { 00658 std::map<AnalysisID, Pass*>::iterator J = I++; 00659 CurrentAnalyses.erase(J); // Analysis not preserved! 00660 } else { 00661 ++I; 00662 } 00663 } 00664 } 00665 } 00666 00667 inline void removeDeadPasses(Pass* P, UnitType *M, 00668 std::map<Pass *, std::vector<Pass*> > &LastUserOf) { 00669 std::vector<Pass*> &DeadPass = LastUserOf[P]; 00670 for (std::vector<Pass*>::iterator I = DeadPass.begin(),E = DeadPass.end(); 00671 I != E; ++I) { 00672 PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I, M); 00673 (*I)->releaseMemory(); 00674 } 00675 00676 for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin(); 00677 I != CurrentAnalyses.end(); ) { 00678 std::vector<Pass*>::iterator DPI = std::find(DeadPass.begin(), 00679 DeadPass.end(), I->second); 00680 if (DPI != DeadPass.end()) { // This pass is dead now... remove it 00681 std::map<AnalysisID, Pass*>::iterator IDead = I++; 00682 CurrentAnalyses.erase(IDead); 00683 } else { 00684 ++I; // Move on to the next element... 00685 } 00686 } 00687 } 00688 00689 inline void makeCurrentlyAvailable(Pass* P) { 00690 if (const PassInfo *PI = P->getPassInfo()) { 00691 CurrentAnalyses[PI] = P; 00692 00693 // This pass is the current implementation of all of the interfaces it 00694 // implements as well. 00695 // 00696 const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented(); 00697 for (unsigned i = 0, e = II.size(); i != e; ++i) 00698 CurrentAnalyses[II[i]] = P; 00699 } 00700 } 00701 }; 00702 00703 00704 00705 //===----------------------------------------------------------------------===// 00706 // BasicBlockPassManager 00707 // 00708 // This pass manager is used to group together all of the BasicBlockPass's 00709 // into a single unit. 00710 // 00711 class BasicBlockPassManager : public BasicBlockPass, 00712 public BBTraits, 00713 public PassManagerT<BBTraits> { 00714 public: 00715 BasicBlockPassManager(BBTraits::ParentClass* PC) : 00716 PassManagerT<BBTraits>(PC) { 00717 } 00718 00719 BasicBlockPassManager(BasicBlockPassManager* BBPM) : 00720 PassManagerT<BBTraits>(BBPM->Parent) { 00721 } 00722 00723 // runPass - Specify how the pass should be run on the UnitType 00724 virtual bool runPass(BBTraits::PassClass *P, BasicBlock *M) { 00725 // TODO: init and finalize 00726 return P->runOnBasicBlock(*M); 00727 } 00728 00729 virtual ~BasicBlockPassManager() {} 00730 00731 virtual void dumpPassStructure(unsigned Offset = 0) { 00732 PassManagerT<BBTraits>::dumpPassStructure(Offset); 00733 } 00734 00735 // getPMName() - Return the name of the unit the PassManager operates on for 00736 // debugging. 00737 virtual const char *getPMName() const { return "BasicBlock"; } 00738 00739 virtual const char *getPassName() const { return "BasicBlock Pass Manager"; } 00740 00741 virtual bool doInitialization(Module &M); 00742 virtual bool doInitialization(Function &F); 00743 virtual bool runOnBasicBlock(BasicBlock &BB); 00744 virtual bool doFinalization(Function &F); 00745 virtual bool doFinalization(Module &M); 00746 00747 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00748 AU.setPreservesAll(); 00749 } 00750 }; 00751 00752 //===----------------------------------------------------------------------===// 00753 // FunctionPassManager 00754 // 00755 // This pass manager is used to group together all of the FunctionPass's 00756 // into a single unit. 00757 // 00758 class FunctionPassManagerT : public FunctionPass, 00759 public FTraits, 00760 public PassManagerT<FTraits> { 00761 public: 00762 FunctionPassManagerT() : PassManagerT<FTraits>(0) {} 00763 00764 // Parent constructor 00765 FunctionPassManagerT(FTraits::ParentClass* PC) : PassManagerT<FTraits>(PC) {} 00766 00767 FunctionPassManagerT(FunctionPassManagerT* FPM) : 00768 PassManagerT<FTraits>(FPM->Parent) { 00769 } 00770 00771 virtual ~FunctionPassManagerT() {} 00772 00773 virtual void dumpPassStructure(unsigned Offset = 0) { 00774 PassManagerT<FTraits>::dumpPassStructure(Offset); 00775 } 00776 00777 // getPMName() - Return the name of the unit the PassManager operates on for 00778 // debugging. 00779 virtual const char *getPMName() const { return "Function"; } 00780 00781 virtual const char *getPassName() const { return "Function Pass Manager"; } 00782 00783 virtual bool runOnFunction(Function &F); 00784 00785 virtual bool doInitialization(Module &M); 00786 00787 virtual bool doFinalization(Module &M); 00788 00789 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00790 AU.setPreservesAll(); 00791 } 00792 00793 // runPass - Specify how the pass should be run on the UnitType 00794 virtual bool runPass(FTraits::PassClass *P, Function *F) { 00795 return P->runOnFunction(*F); 00796 } 00797 }; 00798 00799 00800 //===----------------------------------------------------------------------===// 00801 // ModulePassManager 00802 // 00803 // This is the top level PassManager implementation that holds generic passes. 00804 // 00805 class ModulePassManager : public ModulePass, 00806 public MTraits, 00807 public PassManagerT<MTraits> { 00808 public: 00809 ModulePassManager() : PassManagerT<MTraits>(0) {} 00810 00811 // Batcher Constructor 00812 ModulePassManager(MTraits::ParentClass* PC) : PassManagerT<MTraits>(PC) {} 00813 00814 ModulePassManager(ModulePassManager* MPM) : 00815 PassManagerT<MTraits>((MPM->Parent)) { 00816 } 00817 00818 virtual ~ModulePassManager() {} 00819 00820 virtual void dumpPassStructure(unsigned Offset = 0) { 00821 PassManagerT<MTraits>::dumpPassStructure(Offset); 00822 } 00823 00824 // getPMName() - Return the name of the unit the PassManager operates on for 00825 // debugging. 00826 virtual const char *getPassName() const { return "Module Pass Manager"; } 00827 00828 // getPMName() - Return the name of the unit the PassManager operates on for 00829 // debugging. 00830 virtual const char *getPMName() const { return "Module"; } 00831 00832 // runOnModule - Implement the PassManager interface. 00833 virtual bool runOnModule(Module &M); 00834 00835 // runPass - Specify how the pass should be run on the UnitType 00836 virtual bool runPass(MTraits::PassClass *P, Module *M) { 00837 return P->runOnModule(*M); 00838 } 00839 }; 00840 00841 //===----------------------------------------------------------------------===// 00842 // PassManager Method Implementations 00843 // 00844 00845 // BasicBlockPassManager Implementations 00846 // 00847 00848 inline bool BasicBlockPassManager::runOnBasicBlock(BasicBlock &BB) { 00849 return ((BBTraits::PMType*)this)->runOnUnit(&BB); 00850 } 00851 00852 inline bool BasicBlockPassManager::doInitialization(Module &M) { 00853 bool Changed = false; 00854 for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) 00855 ((BBTraits::PMType*)this)->Passes[i]->doInitialization(M); 00856 return Changed; 00857 } 00858 00859 inline bool BasicBlockPassManager::doInitialization(Function &F) { 00860 bool Changed = false; 00861 for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) 00862 ((BBTraits::PMType*)this)->Passes[i]->doInitialization(F); 00863 return Changed; 00864 } 00865 00866 inline bool BasicBlockPassManager::doFinalization(Function &F) { 00867 bool Changed = false; 00868 for (unsigned i = 0, e =((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) 00869 ((BBTraits::PMType*)this)->Passes[i]->doFinalization(F); 00870 return Changed; 00871 } 00872 00873 inline bool BasicBlockPassManager::doFinalization(Module &M) { 00874 bool Changed = false; 00875 for (unsigned i=0, e = ((BBTraits::PMType*)this)->Passes.size(); i != e; ++i) 00876 ((BBTraits::PMType*)this)->Passes[i]->doFinalization(M); 00877 return Changed; 00878 } 00879 00880 // FunctionPassManagerT Implementations 00881 // 00882 00883 inline bool FunctionPassManagerT::runOnFunction(Function &F) { 00884 return ((FTraits::PMType*)this)->runOnUnit(&F); 00885 } 00886 00887 inline bool FunctionPassManagerT::doInitialization(Module &M) { 00888 bool Changed = false; 00889 for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i) 00890 ((FTraits::PMType*)this)->Passes[i]->doInitialization(M); 00891 return Changed; 00892 } 00893 00894 inline bool FunctionPassManagerT::doFinalization(Module &M) { 00895 bool Changed = false; 00896 for (unsigned i=0, e = ((FTraits::PMType*)this)->Passes.size(); i != e; ++i) 00897 ((FTraits::PMType*)this)->Passes[i]->doFinalization(M); 00898 return Changed; 00899 } 00900 00901 // ModulePassManager Implementations 00902 // 00903 00904 bool ModulePassManager::runOnModule(Module &M) { 00905 return ((PassManagerT<MTraits>*)this)->runOnUnit(&M); 00906 } 00907 00908 } // End llvm namespace 00909 00910 #endif