1 //===- llvm/PassManager.h - Container for Passes -----------------*- C++ -*--=//
3 // This file defines the PassManager class. This class is used to hold,
4 // maintain, and optimize execution of Pass's. The PassManager class ensures
5 // that analysis results are available before a pass runs, and that Pass's are
6 // destroyed when the PassManager is destroyed.
8 // The PassManagerT template is instantiated three times to do its job.
10 //===----------------------------------------------------------------------===//
12 #ifndef LLVM_PASSMANAGER_H
13 #define LLVM_PASSMANAGER_H
15 #include "llvm/Pass.h"
19 //===----------------------------------------------------------------------===//
20 // PMDebug class - a set of debugging functions, that are not to be
21 // instantiated by the template.
24 // If compiled in debug mode, these functions can be enabled by setting
25 // -debug-pass on the command line of the tool being used.
27 static void PrintPassStructure(Pass *P);
28 static void PrintPassInformation(unsigned,const char*,Pass *, Value *);
29 static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P,
30 const std::vector<AnalysisID> &);
35 //===----------------------------------------------------------------------===//
36 // Declare the PassManagerTraits which will be specialized...
38 template<class UnitType> class PassManagerTraits; // Do not define.
41 //===----------------------------------------------------------------------===//
42 // PassManagerT - Container object for passes. The PassManagerT destructor
43 // deletes all passes contained inside of the PassManagerT, so you shouldn't
44 // delete passes manually, and all passes should be dynamically allocated.
46 template<typename UnitType>
47 class PassManagerT : public PassManagerTraits<UnitType>,public AnalysisResolver{
48 typedef typename PassManagerTraits<UnitType>::PassClass PassClass;
49 typedef typename PassManagerTraits<UnitType>::SubPassClass SubPassClass;
50 typedef typename PassManagerTraits<UnitType>::BatcherClass BatcherClass;
51 typedef typename PassManagerTraits<UnitType>::ParentClass ParentClass;
52 typedef PassManagerTraits<UnitType> Traits;
54 friend typename PassManagerTraits<UnitType>::PassClass;
55 friend typename PassManagerTraits<UnitType>::SubPassClass;
56 friend class PassManagerTraits<UnitType>;
58 std::vector<PassClass*> Passes; // List of pass's to run
60 // The parent of this pass manager...
61 ParentClass * const Parent;
63 // The current batcher if one is in use, or null
64 BatcherClass *Batcher;
66 // CurrentAnalyses - As the passes are being run, this map contains the
67 // analyses that are available to the current pass for use. This is accessed
68 // through the getAnalysis() function in this class and in Pass.
70 std::map<AnalysisID, Pass*> CurrentAnalyses;
72 // LastUseOf - This map keeps track of the last usage in our pipeline of a
73 // particular pass. When executing passes, the memory for .first is free'd
74 // after .second is run.
76 std::map<Pass*, Pass*> LastUseOf;
79 PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {}
81 // Delete all of the contained passes...
82 for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
87 // run - Run all of the queued passes on the specified module in an optimal
89 virtual bool runOnUnit(UnitType *M) {
90 bool MadeChanges = false;
92 CurrentAnalyses.clear();
94 // LastUserOf - This contains the inverted LastUseOfMap...
95 std::map<Pass *, std::vector<Pass*> > LastUserOf;
96 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
97 E = LastUseOf.end(); I != E; ++I)
98 LastUserOf[I->second].push_back(I->first);
101 // Output debug information...
102 if (Parent == 0) PMDebug::PrintPassStructure(this);
104 // Run all of the passes
105 for (unsigned i = 0, e = Passes.size(); i < e; ++i) {
106 PassClass *P = Passes[i];
108 PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, (Value*)M);
110 // Get information about what analyses the pass uses...
111 AnalysisUsage AnUsage;
112 P->getAnalysisUsage(AnUsage);
113 PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P,
114 AnUsage.getRequiredSet());
117 // All Required analyses should be available to the pass as it runs!
118 for (vector<AnalysisID>::const_iterator
119 I = AnUsage.getRequiredSet().begin(),
120 E = AnUsage.getRequiredSet().end(); I != E; ++I) {
121 assert(getAnalysisOrNullUp(*I) && "Analysis used but not available!");
126 bool Changed = Traits::runPass(P, M);
127 MadeChanges |= Changed;
130 PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P,
132 PMDebug::PrintAnalysisSetInfo(getDepth(), "Preserved", P,
133 AnUsage.getPreservedSet());
134 PMDebug::PrintAnalysisSetInfo(getDepth(), "Provided", P,
135 AnUsage.getProvidedSet());
138 // Erase all analyses not in the preserved set...
139 if (!AnUsage.preservesAll()) {
140 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
141 for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin(),
142 E = CurrentAnalyses.end(); I != E; )
143 if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) !=
145 ++I; // This analysis is preserved, leave it in the available set...
147 #if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER
148 I = CurrentAnalyses.erase(I); // Analysis not preserved!
150 // GCC 2.95.3 STL doesn't have correct erase member!
151 CurrentAnalyses.erase(I);
152 I = CurrentAnalyses.begin();
157 // Add all analyses in the provided set...
158 for (std::vector<AnalysisID>::const_iterator
159 I = AnUsage.getProvidedSet().begin(),
160 E = AnUsage.getProvidedSet().end(); I != E; ++I)
161 CurrentAnalyses[*I] = P;
163 // Free memory for any passes that we are the last use of...
164 std::vector<Pass*> &DeadPass = LastUserOf[P];
165 for (std::vector<Pass*>::iterator I = DeadPass.begin(),E = DeadPass.end();
167 PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I,
169 (*I)->releaseMemory();
175 // dumpPassStructure - Implement the -debug-passes=PassStructure option
176 virtual void dumpPassStructure(unsigned Offset = 0) {
177 std::cerr << std::string(Offset*2, ' ') << Traits::getPMName()
178 << " Pass Manager\n";
179 for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
182 P->dumpPassStructure(Offset+1);
184 // Loop through and see which classes are destroyed after this one...
185 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
186 E = LastUseOf.end(); I != E; ++I) {
187 if (P == I->second) {
188 std::cerr << "Fr" << std::string(Offset*2, ' ');
189 I->first->dumpPassStructure(0);
195 Pass *getAnalysisOrNullDown(AnalysisID ID) const {
196 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
197 if (I == CurrentAnalyses.end()) {
199 return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID);
205 Pass *getAnalysisOrNullUp(AnalysisID ID) const {
206 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
207 if (I == CurrentAnalyses.end()) {
209 return Parent->getAnalysisOrNullUp(ID);
215 // markPassUsed - Inform higher level pass managers (and ourselves)
216 // that these analyses are being used by this pass. This is used to
217 // make sure that analyses are not free'd before we have to use
220 void markPassUsed(AnalysisID P, Pass *User) {
221 std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.find(P);
222 if (I != CurrentAnalyses.end()) {
223 LastUseOf[I->second] = User; // Local pass, extend the lifetime
225 // Pass not in current available set, must be a higher level pass
226 // available to us, propogate to parent pass manager... We tell the
227 // parent that we (the passmanager) are using the analysis so that it
228 // frees the analysis AFTER this pass manager runs.
230 assert(Parent != 0 && "Pass available but not found! "
231 "Did your analysis pass 'Provide' itself?");
232 Parent->markPassUsed(P, this);
236 // Return the number of parent PassManagers that exist
237 virtual unsigned getDepth() const {
238 if (Parent == 0) return 0;
239 return 1 + Parent->getDepth();
242 // add - Add a pass to the queue of passes to run. This passes ownership of
243 // the Pass to the PassManager. When the PassManager is destroyed, the pass
244 // will be destroyed as well, so there is no need to delete the pass. This
245 // implies that all passes MUST be new'd.
247 void add(PassClass *P) {
248 // Get information about what analyses the pass uses...
249 AnalysisUsage AnUsage;
250 P->getAnalysisUsage(AnUsage);
251 const std::vector<AnalysisID> &Required = AnUsage.getRequiredSet();
253 // Loop over all of the analyses used by this pass,
254 for (std::vector<AnalysisID>::const_iterator I = Required.begin(),
255 E = Required.end(); I != E; ++I) {
256 if (getAnalysisOrNullDown(*I) == 0)
257 add((PassClass*)I->createPass());
260 // Tell the pass to add itself to this PassManager... the way it does so
261 // depends on the class of the pass, and is critical to laying out passes in
262 // an optimal order..
264 P->addToPassManager(this, AnUsage);
269 // addPass - These functions are used to implement the subclass specific
270 // behaviors present in PassManager. Basically the add(Pass*) method ends up
271 // reflecting its behavior into a Pass::addToPassManager call. Subclasses of
272 // Pass override it specifically so that they can reflect the type
273 // information inherent in "this" back to the PassManager.
275 // For generic Pass subclasses (which are interprocedural passes), we simply
276 // add the pass to the end of the pass list and terminate any accumulation of
277 // FunctionPass's that are present.
279 void addPass(PassClass *P, AnalysisUsage &AnUsage) {
280 const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
281 const std::vector<AnalysisID> &ProvidedSet = AnUsage.getProvidedSet();
283 // Providers are analysis classes which are forbidden to modify the module
284 // they are operating on, so they are allowed to be reordered to before the
287 if (Batcher && ProvidedSet.empty())
288 closeBatcher(); // This pass cannot be batched!
290 // Set the Resolver instance variable in the Pass so that it knows where to
291 // find this object...
293 setAnalysisResolver(P, this);
296 // Inform higher level pass managers (and ourselves) that these analyses are
297 // being used by this pass. This is used to make sure that analyses are not
298 // free'd before we have to use them...
300 for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
301 E = RequiredSet.end(); I != E; ++I)
302 markPassUsed(*I, P); // Mark *I as used by P
304 // Erase all analyses not in the preserved set...
305 if (!AnUsage.preservesAll()) {
306 const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
307 for (std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.begin(),
308 E = CurrentAnalyses.end(); I != E; )
309 if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) !=
311 ++I; // This analysis is preserved, leave it in the available set...
313 #if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER
314 I = CurrentAnalyses.erase(I); // Analysis not preserved!
316 CurrentAnalyses.erase(I);// GCC 2.95.3 STL doesn't have correct erase!
317 I = CurrentAnalyses.begin();
322 // Add all analyses in the provided set...
323 for (std::vector<AnalysisID>::const_iterator I = ProvidedSet.begin(),
324 E = ProvidedSet.end(); I != E; ++I)
325 CurrentAnalyses[*I] = P;
327 // For now assume that our results are never used...
331 // For FunctionPass subclasses, we must be sure to batch the FunctionPass's
332 // together in a BatcherClass object so that all of the analyses are run
333 // together a function at a time.
335 void addPass(SubPassClass *MP, AnalysisUsage &AnUsage) {
336 if (Batcher == 0) // If we don't have a batcher yet, make one now.
337 Batcher = new BatcherClass(this);
338 // The Batcher will queue them passes up
339 MP->addToPassManager(Batcher, AnUsage);
342 // closeBatcher - Terminate the batcher that is being worked on.
343 void closeBatcher() {
345 Passes.push_back(Batcher);
353 //===----------------------------------------------------------------------===//
354 // PassManagerTraits<BasicBlock> Specialization
356 // This pass manager is used to group together all of the BasicBlockPass's
357 // into a single unit.
359 template<> struct PassManagerTraits<BasicBlock> : public BasicBlockPass {
360 // PassClass - The type of passes tracked by this PassManager
361 typedef BasicBlockPass PassClass;
363 // SubPassClass - The types of classes that should be collated together
364 // This is impossible to match, so BasicBlock instantiations of PassManagerT
367 typedef PassManagerT<Module> SubPassClass;
369 // BatcherClass - The type to use for collation of subtypes... This class is
370 // never instantiated for the PassManager<BasicBlock>, but it must be an
371 // instance of PassClass to typecheck.
373 typedef PassClass BatcherClass;
375 // ParentClass - The type of the parent PassManager...
376 typedef PassManagerT<Function> ParentClass;
378 // PMType - The type of the passmanager that subclasses this class
379 typedef PassManagerT<BasicBlock> PMType;
381 // runPass - Specify how the pass should be run on the UnitType
382 static bool runPass(PassClass *P, BasicBlock *M) {
383 // todo, init and finalize
384 return P->runOnBasicBlock(M);
387 // getPMName() - Return the name of the unit the PassManager operates on for
389 const char *getPMName() const { return "BasicBlock"; }
391 // Implement the BasicBlockPass interface...
392 virtual bool doInitialization(Module *M);
393 virtual bool runOnBasicBlock(BasicBlock *BB);
394 virtual bool doFinalization(Module *M);
399 //===----------------------------------------------------------------------===//
400 // PassManagerTraits<Function> Specialization
402 // This pass manager is used to group together all of the FunctionPass's
403 // into a single unit.
405 template<> struct PassManagerTraits<Function> : public FunctionPass {
406 // PassClass - The type of passes tracked by this PassManager
407 typedef FunctionPass PassClass;
409 // SubPassClass - The types of classes that should be collated together
410 typedef BasicBlockPass SubPassClass;
412 // BatcherClass - The type to use for collation of subtypes...
413 typedef PassManagerT<BasicBlock> BatcherClass;
415 // ParentClass - The type of the parent PassManager...
416 typedef PassManagerT<Module> ParentClass;
418 // PMType - The type of the passmanager that subclasses this class
419 typedef PassManagerT<Function> PMType;
421 // runPass - Specify how the pass should be run on the UnitType
422 static bool runPass(PassClass *P, Function *F) {
423 return P->runOnFunction(F);
426 // getPMName() - Return the name of the unit the PassManager operates on for
428 const char *getPMName() const { return "Function"; }
430 // Implement the FunctionPass interface...
431 virtual bool doInitialization(Module *M);
432 virtual bool runOnFunction(Function *F);
433 virtual bool doFinalization(Module *M);
438 //===----------------------------------------------------------------------===//
439 // PassManagerTraits<Module> Specialization
441 // This is the top level PassManager implementation that holds generic passes.
443 template<> struct PassManagerTraits<Module> : public Pass {
444 // PassClass - The type of passes tracked by this PassManager
445 typedef Pass PassClass;
447 // SubPassClass - The types of classes that should be collated together
448 typedef FunctionPass SubPassClass;
450 // BatcherClass - The type to use for collation of subtypes...
451 typedef PassManagerT<Function> BatcherClass;
453 // ParentClass - The type of the parent PassManager...
454 typedef AnalysisResolver ParentClass;
456 // runPass - Specify how the pass should be run on the UnitType
457 static bool runPass(PassClass *P, Module *M) { return P->run(M); }
459 // getPMName() - Return the name of the unit the PassManager operates on for
461 const char *getPMName() const { return "Module"; }
463 // run - Implement the Pass interface...
464 virtual bool run(Module *M) {
465 return ((PassManagerT<Module>*)this)->runOnUnit(M);
471 //===----------------------------------------------------------------------===//
472 // PassManagerTraits Method Implementations
475 // PassManagerTraits<BasicBlock> Implementations
477 inline bool PassManagerTraits<BasicBlock>::doInitialization(Module *M) {
478 bool Changed = false;
479 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
480 ((PMType*)this)->Passes[i]->doInitialization(M);
484 inline bool PassManagerTraits<BasicBlock>::runOnBasicBlock(BasicBlock *BB) {
485 return ((PMType*)this)->runOnUnit(BB);
488 inline bool PassManagerTraits<BasicBlock>::doFinalization(Module *M) {
489 bool Changed = false;
490 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
491 ((PMType*)this)->Passes[i]->doFinalization(M);
496 // PassManagerTraits<Function> Implementations
498 inline bool PassManagerTraits<Function>::doInitialization(Module *M) {
499 bool Changed = false;
500 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
501 ((PMType*)this)->Passes[i]->doInitialization(M);
505 inline bool PassManagerTraits<Function>::runOnFunction(Function *F) {
506 return ((PMType*)this)->runOnUnit(F);
509 inline bool PassManagerTraits<Function>::doFinalization(Module *M) {
510 bool Changed = false;
511 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
512 ((PMType*)this)->Passes[i]->doFinalization(M);