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"
18 //===----------------------------------------------------------------------===//
19 // PMDebug class - a set of debugging functions that are enabled when compiling
20 // with -g on. If compiling at -O, all functions are inlined noops.
24 inline static void PrintPassStructure(Pass *) {}
25 inline static void PrintPassInformation(unsigned,const char*,Pass*,Value*) {}
26 inline static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P,
27 const Pass::AnalysisSet &) {}
29 // If compiled in debug mode, these functions can be enabled by setting
30 // -debug-pass on the command line of the tool being used.
32 static void PrintPassStructure(Pass *P);
33 static void PrintPassInformation(unsigned,const char*,Pass *, Value *);
34 static void PrintAnalysisSetInfo(unsigned,const char*,Pass *P,
35 const Pass::AnalysisSet&);
41 //===----------------------------------------------------------------------===//
42 // Declare the PassManagerTraits which will be specialized...
44 template<class UnitType> class PassManagerTraits; // Do not define.
47 //===----------------------------------------------------------------------===//
48 // PassManagerT - Container object for passes. The PassManagerT destructor
49 // deletes all passes contained inside of the PassManagerT, so you shouldn't
50 // delete passes manually, and all passes should be dynamically allocated.
52 template<typename UnitType>
53 class PassManagerT : public PassManagerTraits<UnitType>,public AnalysisResolver{
54 typedef typename PassManagerTraits<UnitType>::PassClass PassClass;
55 typedef typename PassManagerTraits<UnitType>::SubPassClass SubPassClass;
56 typedef typename PassManagerTraits<UnitType>::BatcherClass BatcherClass;
57 typedef typename PassManagerTraits<UnitType>::ParentClass ParentClass;
58 typedef PassManagerTraits<UnitType> Traits;
60 friend typename PassManagerTraits<UnitType>::PassClass;
61 friend typename PassManagerTraits<UnitType>::SubPassClass;
62 friend class PassManagerTraits<UnitType>;
64 std::vector<PassClass*> Passes; // List of pass's to run
66 // The parent of this pass manager...
67 ParentClass * const Parent;
69 // The current batcher if one is in use, or null
70 BatcherClass *Batcher;
72 // CurrentAnalyses - As the passes are being run, this map contains the
73 // analyses that are available to the current pass for use. This is accessed
74 // through the getAnalysis() function in this class and in Pass.
76 std::map<AnalysisID, Pass*> CurrentAnalyses;
78 // LastUseOf - This map keeps track of the last usage in our pipeline of a
79 // particular pass. When executing passes, the memory for .first is free'd
80 // after .second is run.
82 std::map<Pass*, Pass*> LastUseOf;
85 PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {}
87 // Delete all of the contained passes...
88 for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
93 // run - Run all of the queued passes on the specified module in an optimal
95 virtual bool runOnUnit(UnitType *M) {
96 bool MadeChanges = false;
98 CurrentAnalyses.clear();
100 // LastUserOf - This contains the inverted LastUseOfMap...
101 std::map<Pass *, std::vector<Pass*> > LastUserOf;
102 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
103 E = LastUseOf.end(); I != E; ++I)
104 LastUserOf[I->second].push_back(I->first);
107 // Output debug information...
108 if (Parent == 0) PMDebug::PrintPassStructure(this);
110 // Run all of the passes
111 for (unsigned i = 0, e = Passes.size(); i < e; ++i) {
112 PassClass *P = Passes[i];
114 PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, (Value*)M);
116 // Get information about what analyses the pass uses...
117 std::vector<AnalysisID> Required, Destroyed, Provided;
118 P->getAnalysisUsageInfo(Required, Destroyed, Provided);
120 PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", P, Required);
123 // All Required analyses should be available to the pass as it runs!
124 for (Pass::AnalysisSet::iterator I = Required.begin(),
125 E = Required.end(); I != E; ++I) {
126 assert(getAnalysisOrNullUp(*I) && "Analysis used but not available!");
131 bool Changed = Traits::runPass(P, M);
132 MadeChanges |= Changed;
135 PMDebug::PrintPassInformation(getDepth()+1, "Made Modification", P,
137 PMDebug::PrintAnalysisSetInfo(getDepth(), "Destroyed", P, Destroyed);
138 PMDebug::PrintAnalysisSetInfo(getDepth(), "Provided", P, Provided);
140 // Erase all analyses in the destroyed set...
141 for (Pass::AnalysisSet::iterator I = Destroyed.begin(),
142 E = Destroyed.end(); I != E; ++I)
143 CurrentAnalyses.erase(*I);
145 // Add all analyses in the provided set...
146 for (Pass::AnalysisSet::iterator I = Provided.begin(),
147 E = Provided.end(); I != E; ++I)
148 CurrentAnalyses[*I] = P;
150 // Free memory for any passes that we are the last use of...
151 std::vector<Pass*> &DeadPass = LastUserOf[P];
152 for (std::vector<Pass*>::iterator I = DeadPass.begin(),E = DeadPass.end();
154 PMDebug::PrintPassInformation(getDepth()+1, "Freeing Pass", *I,
156 (*I)->releaseMemory();
163 // dumpPassStructure - Implement the -debug-passes=PassStructure option
164 virtual void dumpPassStructure(unsigned Offset = 0) {
165 std::cerr << std::string(Offset*2, ' ') << Traits::getPMName()
166 << " Pass Manager\n";
167 for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
170 P->dumpPassStructure(Offset+1);
172 // Loop through and see which classes are destroyed after this one...
173 for (std::map<Pass*, Pass*>::iterator I = LastUseOf.begin(),
174 E = LastUseOf.end(); I != E; ++I) {
175 if (P == I->second) {
176 std::cerr << "Fr" << std::string(Offset*2, ' ');
177 I->first->dumpPassStructure(0);
184 Pass *getAnalysisOrNullDown(AnalysisID ID) const {
185 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
186 if (I == CurrentAnalyses.end()) {
188 return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID);
194 Pass *getAnalysisOrNullUp(AnalysisID ID) const {
195 std::map<AnalysisID, Pass*>::const_iterator I = CurrentAnalyses.find(ID);
196 if (I == CurrentAnalyses.end()) {
198 return Parent->getAnalysisOrNullUp(ID);
204 // markPassUsed - Inform higher level pass managers (and ourselves)
205 // that these analyses are being used by this pass. This is used to
206 // make sure that analyses are not free'd before we have to use
209 void markPassUsed(AnalysisID P, Pass *User) {
210 std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.find(P);
211 if (I != CurrentAnalyses.end()) {
212 LastUseOf[I->second] = User; // Local pass, extend the lifetime
214 // Pass not in current available set, must be a higher level pass
215 // available to us, propogate to parent pass manager... We tell the
216 // parent that we (the passmanager) are using the analysis so that it
217 // frees the analysis AFTER this pass manager runs.
219 assert(Parent != 0 && "Pass available but not found! "
220 "Did your analysis pass 'Provide' itself?");
221 Parent->markPassUsed(P, this);
225 // Return the number of parent PassManagers that exist
226 virtual unsigned getDepth() const {
227 if (Parent == 0) return 0;
228 return 1 + Parent->getDepth();
231 // add - Add a pass to the queue of passes to run. This passes ownership of
232 // the Pass to the PassManager. When the PassManager is destroyed, the pass
233 // will be destroyed as well, so there is no need to delete the pass. This
234 // implies that all passes MUST be new'd.
236 void add(PassClass *P) {
237 // Get information about what analyses the pass uses...
238 std::vector<AnalysisID> Required, Destroyed, Provided;
239 P->getAnalysisUsageInfo(Required, Destroyed, Provided);
241 // Loop over all of the analyses used by this pass,
242 for (std::vector<AnalysisID>::iterator I = Required.begin(),
243 E = Required.end(); I != E; ++I) {
244 if (getAnalysisOrNullDown(*I) == 0)
245 add((PassClass*)I->createPass());
248 // Tell the pass to add itself to this PassManager... the way it does so
249 // depends on the class of the pass, and is critical to laying out passes in
250 // an optimal order..
252 P->addToPassManager(this, Required, Destroyed, Provided);
257 // addPass - These functions are used to implement the subclass specific
258 // behaviors present in PassManager. Basically the add(Pass*) method ends up
259 // reflecting its behavior into a Pass::addToPassManager call. Subclasses of
260 // Pass override it specifically so that they can reflect the type
261 // information inherent in "this" back to the PassManager.
263 // For generic Pass subclasses (which are interprocedural passes), we simply
264 // add the pass to the end of the pass list and terminate any accumulation of
265 // MethodPasses that are present.
267 void addPass(PassClass *P, Pass::AnalysisSet &Required,
268 Pass::AnalysisSet &Destroyed, Pass::AnalysisSet &Provided) {
269 // Providers are analysis classes which are forbidden to modify the module
270 // they are operating on, so they are allowed to be reordered to before the
273 if (Batcher && Provided.empty())
274 closeBatcher(); // This pass cannot be batched!
276 // Set the Resolver instance variable in the Pass so that it knows where to
277 // find this object...
279 setAnalysisResolver(P, this);
282 // Inform higher level pass managers (and ourselves) that these analyses are
283 // being used by this pass. This is used to make sure that analyses are not
284 // free'd before we have to use them...
286 for (std::vector<AnalysisID>::iterator I = Required.begin(),
287 E = Required.end(); I != E; ++I)
288 markPassUsed(*I, P); // Mark *I as used by P
290 // Erase all analyses in the destroyed set...
291 for (std::vector<AnalysisID>::iterator I = Destroyed.begin(),
292 E = Destroyed.end(); I != E; ++I)
293 CurrentAnalyses.erase(*I);
295 // Add all analyses in the provided set...
296 for (std::vector<AnalysisID>::iterator I = Provided.begin(),
297 E = Provided.end(); I != E; ++I)
298 CurrentAnalyses[*I] = P;
300 // For now assume that our results are never used...
304 // For MethodPass subclasses, we must be sure to batch the MethodPasses
305 // together in a MethodPassBatcher object so that all of the analyses are run
306 // together a method at a time.
308 void addPass(SubPassClass *MP, Pass::AnalysisSet &Required,
309 Pass::AnalysisSet &Destroyed, Pass::AnalysisSet &Provided) {
310 if (Batcher == 0) // If we don't have a batcher yet, make one now.
311 Batcher = new BatcherClass(this);
312 // The Batcher will queue them passes up
313 MP->addToPassManager(Batcher, Required, Destroyed, Provided);
316 // closeBatcher - Terminate the batcher that is being worked on.
317 void closeBatcher() {
319 Passes.push_back(Batcher);
327 //===----------------------------------------------------------------------===//
328 // PassManagerTraits<BasicBlock> Specialization
330 // This pass manager is used to group together all of the BasicBlockPass's
331 // into a single unit.
333 template<> struct PassManagerTraits<BasicBlock> : public BasicBlockPass {
334 // PassClass - The type of passes tracked by this PassManager
335 typedef BasicBlockPass PassClass;
337 // SubPassClass - The types of classes that should be collated together
338 // This is impossible to match, so BasicBlock instantiations of PassManagerT
341 typedef PassManagerT<Module> SubPassClass;
343 // BatcherClass - The type to use for collation of subtypes... This class is
344 // never instantiated for the PassManager<BasicBlock>, but it must be an
345 // instance of PassClass to typecheck.
347 typedef PassClass BatcherClass;
349 // ParentClass - The type of the parent PassManager...
350 typedef PassManagerT<Function> ParentClass;
352 // PMType - The type of the passmanager that subclasses this class
353 typedef PassManagerT<BasicBlock> PMType;
355 // runPass - Specify how the pass should be run on the UnitType
356 static bool runPass(PassClass *P, BasicBlock *M) {
357 // todo, init and finalize
358 return P->runOnBasicBlock(M);
361 // getPMName() - Return the name of the unit the PassManager operates on for
363 const char *getPMName() const { return "BasicBlock"; }
365 // Implement the BasicBlockPass interface...
366 virtual bool doInitialization(Module *M);
367 virtual bool runOnBasicBlock(BasicBlock *BB);
368 virtual bool doFinalization(Module *M);
373 //===----------------------------------------------------------------------===//
374 // PassManagerTraits<Function> Specialization
376 // This pass manager is used to group together all of the MethodPass's
377 // into a single unit.
379 template<> struct PassManagerTraits<Function> : public MethodPass {
380 // PassClass - The type of passes tracked by this PassManager
381 typedef MethodPass PassClass;
383 // SubPassClass - The types of classes that should be collated together
384 typedef BasicBlockPass SubPassClass;
386 // BatcherClass - The type to use for collation of subtypes...
387 typedef PassManagerT<BasicBlock> BatcherClass;
389 // ParentClass - The type of the parent PassManager...
390 typedef PassManagerT<Module> ParentClass;
392 // PMType - The type of the passmanager that subclasses this class
393 typedef PassManagerT<Function> PMType;
395 // runPass - Specify how the pass should be run on the UnitType
396 static bool runPass(PassClass *P, Function *M) {
397 return P->runOnMethod(M);
400 // getPMName() - Return the name of the unit the PassManager operates on for
402 const char *getPMName() const { return "Function"; }
404 // Implement the MethodPass interface...
405 virtual bool doInitialization(Module *M);
406 virtual bool runOnMethod(Function *M);
407 virtual bool doFinalization(Module *M);
412 //===----------------------------------------------------------------------===//
413 // PassManagerTraits<Module> Specialization
415 // This is the top level PassManager implementation that holds generic passes.
417 template<> struct PassManagerTraits<Module> : public Pass {
418 // PassClass - The type of passes tracked by this PassManager
419 typedef Pass PassClass;
421 // SubPassClass - The types of classes that should be collated together
422 typedef MethodPass SubPassClass;
424 // BatcherClass - The type to use for collation of subtypes...
425 typedef PassManagerT<Function> BatcherClass;
427 // ParentClass - The type of the parent PassManager...
428 typedef AnalysisResolver ParentClass;
430 // runPass - Specify how the pass should be run on the UnitType
431 static bool runPass(PassClass *P, Module *M) { return P->run(M); }
433 // getPMName() - Return the name of the unit the PassManager operates on for
435 const char *getPMName() const { return "Module"; }
437 // run - Implement the Pass interface...
438 virtual bool run(Module *M) {
439 return ((PassManagerT<Module>*)this)->runOnUnit(M);
445 //===----------------------------------------------------------------------===//
446 // PassManagerTraits Method Implementations
449 // PassManagerTraits<BasicBlock> Implementations
451 inline bool PassManagerTraits<BasicBlock>::doInitialization(Module *M) {
452 bool Changed = false;
453 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
454 ((PMType*)this)->Passes[i]->doInitialization(M);
458 inline bool PassManagerTraits<BasicBlock>::runOnBasicBlock(BasicBlock *BB) {
459 return ((PMType*)this)->runOnUnit(BB);
462 inline bool PassManagerTraits<BasicBlock>::doFinalization(Module *M) {
463 bool Changed = false;
464 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
465 ((PMType*)this)->Passes[i]->doFinalization(M);
470 // PassManagerTraits<Function> Implementations
472 inline bool PassManagerTraits<Function>::doInitialization(Module *M) {
473 bool Changed = false;
474 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
475 ((PMType*)this)->Passes[i]->doInitialization(M);
479 inline bool PassManagerTraits<Function>::runOnMethod(Function *M) {
480 return ((PMType*)this)->runOnUnit(M);
483 inline bool PassManagerTraits<Function>::doFinalization(Module *M) {
484 bool Changed = false;
485 for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
486 ((PMType*)this)->Passes[i]->doFinalization(M);