Add " Made Modification " messages in debug-pass=Executions output.
[oota-llvm.git] / lib / VMCore / PassManager.cpp
1 //===- PassManager.cpp - LLVM Pass Infrastructure Implementation ----------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file was developed by Devang Patel and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements the LLVM Pass Manager infrastructure. 
11 //
12 //===----------------------------------------------------------------------===//
13
14
15 #include "llvm/PassManager.h"
16 #include "llvm/Support/CommandLine.h"
17 #include "llvm/Module.h"
18 #include "llvm/ModuleProvider.h"
19 #include "llvm/Support/Streams.h"
20 #include <vector>
21 #include <map>
22 using namespace llvm;
23
24 //===----------------------------------------------------------------------===//
25 // Overview:
26 // The Pass Manager Infrastructure manages passes. It's responsibilities are:
27 // 
28 //   o Manage optimization pass execution order
29 //   o Make required Analysis information available before pass P is run
30 //   o Release memory occupied by dead passes
31 //   o If Analysis information is dirtied by a pass then regenerate Analysis 
32 //     information before it is consumed by another pass.
33 //
34 // Pass Manager Infrastructure uses multipe pass managers. They are PassManager,
35 // FunctionPassManager, ModulePassManager, BasicBlockPassManager. This class 
36 // hierarcy uses multiple inheritance but pass managers do not derive from
37 // another pass manager.
38 //
39 // PassManager and FunctionPassManager are two top level pass manager that
40 // represents the external interface of this entire pass manager infrastucture.
41 //
42 // Important classes :
43 //
44 // [o] class PMTopLevelManager;
45 //
46 // Two top level managers, PassManager and FunctionPassManager, derive from 
47 // PMTopLevelManager. PMTopLevelManager manages information used by top level 
48 // managers such as last user info.
49 //
50 // [o] class PMDataManager;
51 //
52 // PMDataManager manages information, e.g. list of available analysis info, 
53 // used by a pass manager to manage execution order of passes. It also provides
54 // a place to implement common pass manager APIs. All pass managers derive from
55 // PMDataManager.
56 //
57 // [o] class BasicBlockPassManager : public FunctionPass, public PMDataManager;
58 //
59 // BasicBlockPassManager manages BasicBlockPasses.
60 //
61 // [o] class FunctionPassManager;
62 //
63 // This is a external interface used by JIT to manage FunctionPasses. This
64 // interface relies on FunctionPassManagerImpl to do all the tasks.
65 //
66 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager,
67 //                                     public PMTopLevelManager;
68 //
69 // FunctionPassManagerImpl is a top level manager. It manages FunctionPasses
70 // and BasicBlockPassManagers.
71 //
72 // [o] class ModulePassManager : public Pass, public PMDataManager;
73 //
74 // ModulePassManager manages ModulePasses and FunctionPassManagerImpls.
75 //
76 // [o] class PassManager;
77 //
78 // This is a external interface used by various tools to manages passes. It
79 // relies on PassManagerImpl to do all the tasks.
80 //
81 // [o] class PassManagerImpl : public Pass, public PMDataManager,
82 //                             public PMDTopLevelManager
83 //
84 // PassManagerImpl is a top level pass manager responsible for managing
85 // ModulePassManagers.
86 //===----------------------------------------------------------------------===//
87
88 namespace llvm {
89
90 //===----------------------------------------------------------------------===//
91 // Pass debugging information.  Often it is useful to find out what pass is
92 // running when a crash occurs in a utility.  When this library is compiled with
93 // debugging on, a command line option (--debug-pass) is enabled that causes the
94 // pass name to be printed before it executes.
95 //
96
97 // Different debug levels that can be enabled...
98 enum PassDebugLevel {
99   None, Arguments, Structure, Executions, Details
100 };
101
102 static cl::opt<enum PassDebugLevel>
103 PassDebugging_New("debug-pass", cl::Hidden,
104                   cl::desc("Print PassManager debugging information"),
105                   cl::values(
106   clEnumVal(None      , "disable debug output"),
107   clEnumVal(Arguments , "print pass arguments to pass to 'opt'"),
108   clEnumVal(Structure , "print pass structure before run()"),
109   clEnumVal(Executions, "print pass name before it is executed"),
110   clEnumVal(Details   , "print pass details when it is executed"),
111                              clEnumValEnd));
112 } // End of llvm namespace
113
114 #ifndef USE_OLD_PASSMANAGER
115 namespace llvm {
116
117 class PMDataManager;
118
119 //===----------------------------------------------------------------------===//
120 // PMTopLevelManager
121 //
122 /// PMTopLevelManager manages LastUser info and collects common APIs used by
123 /// top level pass managers.
124 class PMTopLevelManager {
125
126 public:
127
128   inline std::vector<Pass *>::iterator passManagersBegin() { 
129     return PassManagers.begin(); 
130   }
131
132   inline std::vector<Pass *>::iterator passManagersEnd() { 
133     return PassManagers.end();
134   }
135
136   /// Schedule pass P for execution. Make sure that passes required by
137   /// P are run before P is run. Update analysis info maintained by
138   /// the manager. Remove dead passes. This is a recursive function.
139   void schedulePass(Pass *P);
140
141   /// This is implemented by top level pass manager and used by 
142   /// schedulePass() to add analysis info passes that are not available.
143   virtual void addTopLevelPass(Pass  *P) = 0;
144
145   /// Set pass P as the last user of the given analysis passes.
146   void setLastUser(std::vector<Pass *> &AnalysisPasses, Pass *P);
147
148   /// Collect passes whose last user is P
149   void collectLastUses(std::vector<Pass *> &LastUses, Pass *P);
150
151   /// Find the pass that implements Analysis AID. Search immutable
152   /// passes and all pass managers. If desired pass is not found
153   /// then return NULL.
154   Pass *findAnalysisPass(AnalysisID AID);
155
156   inline void clearManagers() { 
157     PassManagers.clear();
158   }
159
160   virtual ~PMTopLevelManager() {
161
162     for (std::vector<Pass *>::iterator I = PassManagers.begin(),
163            E = PassManagers.end(); I != E; ++I)
164       delete *I;
165
166     for (std::vector<ImmutablePass *>::iterator
167            I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
168       delete *I;
169
170     PassManagers.clear();
171   }
172
173   /// Add immutable pass and initialize it.
174   inline void addImmutablePass(ImmutablePass *P) {
175     P->initializePass();
176     ImmutablePasses.push_back(P);
177   }
178
179   inline std::vector<ImmutablePass *>& getImmutablePasses() {
180     return ImmutablePasses;
181   }
182
183   void addPassManager(Pass *Manager) {
184     PassManagers.push_back(Manager);
185   }
186
187   // Add Manager into the list of managers that are not directly
188   // maintained by this top level pass manager
189   inline void addIndirectPassManager(PMDataManager *Manager) {
190     IndirectPassManagers.push_back(Manager);
191   }
192
193   // Print passes managed by this top level manager.
194   void dumpPasses();
195   void dumpArguments();
196
197 private:
198   
199   /// Collection of pass managers
200   std::vector<Pass *> PassManagers;
201
202   /// Collection of pass managers that are not directly maintained
203   /// by this pass manager
204   std::vector<PMDataManager *> IndirectPassManagers;
205
206   // Map to keep track of last user of the analysis pass.
207   // LastUser->second is the last user of Lastuser->first.
208   std::map<Pass *, Pass *> LastUser;
209
210   /// Immutable passes are managed by top level manager.
211   std::vector<ImmutablePass *> ImmutablePasses;
212 };
213   
214 //===----------------------------------------------------------------------===//
215 // PMDataManager
216
217 /// PMDataManager provides the common place to manage the analysis data
218 /// used by pass managers.
219 class PMDataManager {
220
221 public:
222
223   PMDataManager(int D) : TPM(NULL), Depth(D) {
224     initializeAnalysisInfo();
225   }
226
227   virtual ~PMDataManager() {
228
229     for (std::vector<Pass *>::iterator I = PassVector.begin(),
230            E = PassVector.end(); I != E; ++I)
231       delete *I;
232
233     PassVector.clear();
234   }
235
236   /// Return true IFF pass P's required analysis set does not required new
237   /// manager.
238   bool manageablePass(Pass *P);
239
240   /// Augment AvailableAnalysis by adding analysis made available by pass P.
241   void recordAvailableAnalysis(Pass *P);
242
243   /// Remove Analysis that is not preserved by the pass
244   void removeNotPreservedAnalysis(Pass *P);
245   
246   /// Remove dead passes
247   void removeDeadPasses(Pass *P, std::string &Msg);
248
249   /// Add pass P into the PassVector. Update 
250   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
251   void addPassToManager (Pass *P, bool ProcessAnalysis = true);
252
253   /// Initialize available analysis information.
254   void initializeAnalysisInfo() { 
255     ForcedLastUses.clear();
256     AvailableAnalysis.clear();
257   }
258
259   /// Populate RequiredPasses with the analysis pass that are required by
260   /// pass P.
261   void collectRequiredAnalysisPasses(std::vector<Pass *> &RequiredPasses,
262                                      Pass *P);
263
264   /// All Required analyses should be available to the pass as it runs!  Here
265   /// we fill in the AnalysisImpls member of the pass so that it can
266   /// successfully use the getAnalysis() method to retrieve the
267   /// implementations it needs.
268   void initializeAnalysisImpl(Pass *P);
269
270   /// Find the pass that implements Analysis AID. If desired pass is not found
271   /// then return NULL.
272   Pass *findAnalysisPass(AnalysisID AID, bool Direction);
273
274   inline std::vector<Pass *>::iterator passVectorBegin() { 
275     return PassVector.begin(); 
276   }
277
278   inline std::vector<Pass *>::iterator passVectorEnd() { 
279     return PassVector.end();
280   }
281
282   // Access toplevel manager
283   PMTopLevelManager *getTopLevelManager() { return TPM; }
284   void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
285
286   unsigned getDepth() { return Depth; }
287
288   // Print list of passes that are last used by P.
289   void dumpLastUses(Pass *P, unsigned Offset) {
290     
291     std::vector<Pass *> LUses;
292
293     assert (TPM && "Top Level Manager is missing");
294     TPM->collectLastUses(LUses, P);
295     
296     for (std::vector<Pass *>::iterator I = LUses.begin(),
297            E = LUses.end(); I != E; ++I) {
298       llvm::cerr << "--" << std::string(Offset*2, ' ');
299       (*I)->dumpPassStructure(0);
300     }
301   }
302
303   void dumpPassArguments() {
304     for(std::vector<Pass *>::iterator I = PassVector.begin(),
305           E = PassVector.end(); I != E; ++I) {
306       if (PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I))
307         PMD->dumpPassArguments();
308       else
309         if (const PassInfo *PI = (*I)->getPassInfo())
310           if (!PI->isAnalysisGroup())
311             cerr << " -" << PI->getPassArgument();
312     }
313   }
314
315   void dumpPassInfo(Pass *P,  std::string &Msg1, std::string &Msg2) {
316     if (PassDebugging_New < Executions)
317       return;
318     cerr << (void*)this << std::string(getDepth()*2+1, ' ');
319     cerr << Msg1;
320     cerr << P->getPassName();
321     cerr << Msg2;
322   }
323
324 protected:
325
326   // Collection of pass whose last user asked this manager to claim
327   // last use. If a FunctionPass F is the last user of ModulePass info M
328   // then the F's manager, not F, records itself as a last user of M.
329   std::vector<Pass *> ForcedLastUses;
330
331   // Top level manager.
332   PMTopLevelManager *TPM;
333
334 private:
335   // Set of available Analysis. This information is used while scheduling 
336   // pass. If a pass requires an analysis which is not not available then 
337   // equired analysis pass is scheduled to run before the pass itself is 
338   // scheduled to run.
339   std::map<AnalysisID, Pass*> AvailableAnalysis;
340
341   // Collection of pass that are managed by this manager
342   std::vector<Pass *> PassVector;
343
344   unsigned Depth;
345 };
346
347 //===----------------------------------------------------------------------===//
348 // BasicBlockPassManager
349 //
350 /// BasicBlockPassManager manages BasicBlockPass. It batches all the
351 /// pass together and sequence them to process one basic block before
352 /// processing next basic block.
353 class BasicBlockPassManager : public PMDataManager, 
354                                   public FunctionPass {
355
356 public:
357   BasicBlockPassManager(int D) : PMDataManager(D) { }
358
359   /// Add a pass into a passmanager queue. 
360   bool addPass(Pass *p);
361   
362   /// Execute all of the passes scheduled for execution.  Keep track of
363   /// whether any of the passes modifies the function, and if so, return true.
364   bool runOnFunction(Function &F);
365
366   /// Pass Manager itself does not invalidate any analysis info.
367   void getAnalysisUsage(AnalysisUsage &Info) const {
368     Info.setPreservesAll();
369   }
370
371   bool doInitialization(Module &M);
372   bool doInitialization(Function &F);
373   bool doFinalization(Module &M);
374   bool doFinalization(Function &F);
375
376   // Print passes managed by this manager
377   void dumpPassStructure(unsigned Offset) {
378     llvm::cerr << std::string(Offset*2, ' ') << "BasicBLockPass Manager\n";
379     for (std::vector<Pass *>::iterator I = passVectorBegin(),
380            E = passVectorEnd(); I != E; ++I)  {
381       (*I)->dumpPassStructure(Offset + 1);
382       dumpLastUses(*I, Offset+1);
383     }
384   }
385 };
386
387 //===----------------------------------------------------------------------===//
388 // FunctionPassManagerImpl_New
389 //
390 /// FunctionPassManagerImpl_New manages FunctionPasses and
391 /// BasicBlockPassManagers.  It batches all function passes and basic block pass
392 /// managers together and sequence them to process one function at a time before
393 /// processing next function.
394 class FunctionPassManagerImpl_New : public ModulePass, 
395                                     public PMDataManager,
396                                     public PMTopLevelManager {
397 public:
398   FunctionPassManagerImpl_New(int D) : PMDataManager(D) { 
399     activeBBPassManager = NULL;
400   }
401   ~FunctionPassManagerImpl_New() { /* TODO */ };
402  
403   inline void addTopLevelPass(Pass *P) { 
404
405     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
406
407       // P is a immutable pass then it will be managed by this
408       // top level manager. Set up analysis resolver to connect them.
409       AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
410       P->setResolver(AR);
411       initializeAnalysisImpl(P);
412       addImmutablePass(IP);
413       recordAvailableAnalysis(IP);
414     } 
415     else 
416       addPass(P);
417   }
418
419   /// add - Add a pass to the queue of passes to run.  This passes
420   /// ownership of the Pass to the PassManager.  When the
421   /// PassManager_X is destroyed, the pass will be destroyed as well, so
422   /// there is no need to delete the pass. (TODO delete passes.)
423   /// This implies that all passes MUST be allocated with 'new'.
424   void add(Pass *P) { 
425     schedulePass(P);
426   }
427
428   /// Add pass into the pass manager queue.
429   bool addPass(Pass *P);
430
431   /// Execute all of the passes scheduled for execution.  Keep
432   /// track of whether any of the passes modifies the function, and if
433   /// so, return true.
434   bool runOnModule(Module &M);
435   bool runOnFunction(Function &F);
436   bool run(Function &F);
437
438   /// doInitialization - Run all of the initializers for the function passes.
439   ///
440   bool doInitialization(Module &M);
441   
442   /// doFinalization - Run all of the initializers for the function passes.
443   ///
444   bool doFinalization(Module &M);
445
446   /// Pass Manager itself does not invalidate any analysis info.
447   void getAnalysisUsage(AnalysisUsage &Info) const {
448     Info.setPreservesAll();
449   }
450
451   // Print passes managed by this manager
452   void dumpPassStructure(unsigned Offset) {
453     llvm::cerr << std::string(Offset*2, ' ') << "FunctionPass Manager\n";
454     for (std::vector<Pass *>::iterator I = passVectorBegin(),
455            E = passVectorEnd(); I != E; ++I)  {
456       (*I)->dumpPassStructure(Offset + 1);
457       dumpLastUses(*I, Offset+1);
458     }
459   }
460
461 private:
462   // Active Pass Managers
463   BasicBlockPassManager *activeBBPassManager;
464 };
465
466 //===----------------------------------------------------------------------===//
467 // ModulePassManager
468 //
469 /// ModulePassManager manages ModulePasses and function pass managers.
470 /// It batches all Module passes  passes and function pass managers together and
471 /// sequence them to process one module.
472 class ModulePassManager : public Pass,
473                               public PMDataManager {
474  
475 public:
476   ModulePassManager(int D) : PMDataManager(D) { 
477     activeFunctionPassManager = NULL; 
478   }
479   
480   /// Add a pass into a passmanager queue. 
481   bool addPass(Pass *p);
482   
483   /// run - Execute all of the passes scheduled for execution.  Keep track of
484   /// whether any of the passes modifies the module, and if so, return true.
485   bool runOnModule(Module &M);
486
487   /// Pass Manager itself does not invalidate any analysis info.
488   void getAnalysisUsage(AnalysisUsage &Info) const {
489     Info.setPreservesAll();
490   }
491
492   // Print passes managed by this manager
493   void dumpPassStructure(unsigned Offset) {
494     llvm::cerr << std::string(Offset*2, ' ') << "ModulePass Manager\n";
495     for (std::vector<Pass *>::iterator I = passVectorBegin(),
496            E = passVectorEnd(); I != E; ++I)  {
497       (*I)->dumpPassStructure(Offset + 1);
498       dumpLastUses(*I, Offset+1);
499     }
500   }
501
502 private:
503   // Active Pass Manager
504   FunctionPassManagerImpl_New *activeFunctionPassManager;
505 };
506
507 //===----------------------------------------------------------------------===//
508 // PassManagerImpl_New
509 //
510 /// PassManagerImpl_New manages ModulePassManagers
511 class PassManagerImpl_New : public Pass,
512                             public PMDataManager,
513                             public PMTopLevelManager {
514
515 public:
516
517   PassManagerImpl_New(int D) : PMDataManager(D) {
518     activeManager = NULL;
519   }
520
521   /// add - Add a pass to the queue of passes to run.  This passes ownership of
522   /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
523   /// will be destroyed as well, so there is no need to delete the pass.  This
524   /// implies that all passes MUST be allocated with 'new'.
525   void add(Pass *P) {
526     schedulePass(P);
527   }
528  
529   /// run - Execute all of the passes scheduled for execution.  Keep track of
530   /// whether any of the passes modifies the module, and if so, return true.
531   bool run(Module &M);
532
533   /// Pass Manager itself does not invalidate any analysis info.
534   void getAnalysisUsage(AnalysisUsage &Info) const {
535     Info.setPreservesAll();
536   }
537
538   inline void addTopLevelPass(Pass *P) {
539
540     if (ImmutablePass *IP = dynamic_cast<ImmutablePass *> (P)) {
541       
542       // P is a immutable pass and it will be managed by this
543       // top level manager. Set up analysis resolver to connect them.
544       AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
545       P->setResolver(AR);
546       initializeAnalysisImpl(P);
547       addImmutablePass(IP);
548       recordAvailableAnalysis(IP);
549     }
550     else 
551       addPass(P);
552   }
553
554 private:
555
556   /// Add a pass into a passmanager queue.
557   bool addPass(Pass *p);
558
559   // Active Pass Manager
560   ModulePassManager *activeManager;
561 };
562
563 } // End of llvm namespace
564
565 //===----------------------------------------------------------------------===//
566 // PMTopLevelManager implementation
567
568 /// Set pass P as the last user of the given analysis passes.
569 void PMTopLevelManager::setLastUser(std::vector<Pass *> &AnalysisPasses, 
570                                     Pass *P) {
571
572   for (std::vector<Pass *>::iterator I = AnalysisPasses.begin(),
573          E = AnalysisPasses.end(); I != E; ++I) {
574     Pass *AP = *I;
575     LastUser[AP] = P;
576     // If AP is the last user of other passes then make P last user of
577     // such passes.
578     for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
579            LUE = LastUser.end(); LUI != LUE; ++LUI) {
580       if (LUI->second == AP)
581         LastUser[LUI->first] = P;
582     }
583   }
584 }
585
586 /// Collect passes whose last user is P
587 void PMTopLevelManager::collectLastUses(std::vector<Pass *> &LastUses,
588                                             Pass *P) {
589    for (std::map<Pass *, Pass *>::iterator LUI = LastUser.begin(),
590           LUE = LastUser.end(); LUI != LUE; ++LUI)
591       if (LUI->second == P)
592         LastUses.push_back(LUI->first);
593 }
594
595 /// Schedule pass P for execution. Make sure that passes required by
596 /// P are run before P is run. Update analysis info maintained by
597 /// the manager. Remove dead passes. This is a recursive function.
598 void PMTopLevelManager::schedulePass(Pass *P) {
599
600   // TODO : Allocate function manager for this pass, other wise required set
601   // may be inserted into previous function manager
602
603   AnalysisUsage AnUsage;
604   P->getAnalysisUsage(AnUsage);
605   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
606   for (std::vector<AnalysisID>::const_iterator I = RequiredSet.begin(),
607          E = RequiredSet.end(); I != E; ++I) {
608
609     Pass *AnalysisPass = findAnalysisPass(*I);
610     if (!AnalysisPass) {
611       // Schedule this analysis run first.
612       AnalysisPass = (*I)->createPass();
613       schedulePass(AnalysisPass);
614     }
615   }
616
617   // Now all required passes are available.
618   addTopLevelPass(P);
619 }
620
621 /// Find the pass that implements Analysis AID. Search immutable
622 /// passes and all pass managers. If desired pass is not found
623 /// then return NULL.
624 Pass *PMTopLevelManager::findAnalysisPass(AnalysisID AID) {
625
626   Pass *P = NULL;
627   // Check pass managers
628   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
629          E = PassManagers.end(); P == NULL && I != E; ++I) {
630     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
631     assert(PMD && "This is not a PassManager");
632     P = PMD->findAnalysisPass(AID, false);
633   }
634
635   // Check other pass managers
636   for (std::vector<PMDataManager *>::iterator I = IndirectPassManagers.begin(),
637          E = IndirectPassManagers.end(); P == NULL && I != E; ++I)
638     P = (*I)->findAnalysisPass(AID, false);
639
640   for (std::vector<ImmutablePass *>::iterator I = ImmutablePasses.begin(),
641          E = ImmutablePasses.end(); P == NULL && I != E; ++I) {
642     const PassInfo *PI = (*I)->getPassInfo();
643     if (PI == AID)
644       P = *I;
645
646     // If Pass not found then check the interfaces implemented by Immutable Pass
647     if (!P) {
648       const std::vector<const PassInfo*> &ImmPI = 
649         PI->getInterfacesImplemented();
650       for (unsigned Index = 0, End = ImmPI.size(); 
651            P == NULL && Index != End; ++Index)
652         if (ImmPI[Index] == AID)
653           P = *I;
654     }
655   }
656
657   return P;
658 }
659
660 // Print passes managed by this top level manager.
661 void PMTopLevelManager::dumpPasses() {
662
663   // Print out the immutable passes
664   for (unsigned i = 0, e = ImmutablePasses.size(); i != e; ++i) {
665     ImmutablePasses[i]->dumpPassStructure(0);
666   }
667   
668   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
669          E = PassManagers.end(); I != E; ++I)
670     (*I)->dumpPassStructure(1);
671
672 }
673
674 void PMTopLevelManager::dumpArguments() {
675
676   if (PassDebugging_New < Arguments)
677     return;
678
679   cerr << "Pass Arguments: ";
680   for (std::vector<Pass *>::iterator I = PassManagers.begin(),
681          E = PassManagers.end(); I != E; ++I) {
682     PMDataManager *PMD = dynamic_cast<PMDataManager *>(*I);
683     assert(PMD && "This is not a PassManager");
684     PMD->dumpPassArguments();
685   }
686   cerr << "\n";
687 }
688
689 //===----------------------------------------------------------------------===//
690 // PMDataManager implementation
691
692 /// Return true IFF pass P's required analysis set does not required new
693 /// manager.
694 bool PMDataManager::manageablePass(Pass *P) {
695
696   // TODO 
697   // If this pass is not preserving information that is required by a
698   // pass maintained by higher level pass manager then do not insert
699   // this pass into current manager. Use new manager. For example,
700   // For example, If FunctionPass F is not preserving ModulePass Info M1
701   // that is used by another ModulePass M2 then do not insert F in
702   // current function pass manager.
703   return true;
704 }
705
706 /// Augement AvailableAnalysis by adding analysis made available by pass P.
707 void PMDataManager::recordAvailableAnalysis(Pass *P) {
708                                                 
709   if (const PassInfo *PI = P->getPassInfo()) {
710     AvailableAnalysis[PI] = P;
711
712     //This pass is the current implementation of all of the interfaces it
713     //implements as well.
714     const std::vector<const PassInfo*> &II = PI->getInterfacesImplemented();
715     for (unsigned i = 0, e = II.size(); i != e; ++i)
716       AvailableAnalysis[II[i]] = P;
717   }
718 }
719
720 /// Remove Analyss not preserved by Pass P
721 void PMDataManager::removeNotPreservedAnalysis(Pass *P) {
722   AnalysisUsage AnUsage;
723   P->getAnalysisUsage(AnUsage);
724
725   if (AnUsage.getPreservesAll())
726     return;
727
728   const std::vector<AnalysisID> &PreservedSet = AnUsage.getPreservedSet();
729   for (std::map<AnalysisID, Pass*>::iterator I = AvailableAnalysis.begin(),
730          E = AvailableAnalysis.end(); I != E; ) {
731     if (std::find(PreservedSet.begin(), PreservedSet.end(), I->first) == 
732         PreservedSet.end()) {
733       // Remove this analysis
734       if (!dynamic_cast<ImmutablePass*>(I->second)) {
735         std::map<AnalysisID, Pass*>::iterator J = I++;
736         AvailableAnalysis.erase(J);
737       } else
738         ++I;
739     } else
740       ++I;
741   }
742 }
743
744 /// Remove analysis passes that are not used any longer
745 void PMDataManager::removeDeadPasses(Pass *P, std::string &Msg) {
746
747   std::vector<Pass *> DeadPasses;
748   TPM->collectLastUses(DeadPasses, P);
749
750   for (std::vector<Pass *>::iterator I = DeadPasses.begin(),
751          E = DeadPasses.end(); I != E; ++I) {
752
753     std::string Msg1 = "  Freeing Pass '";
754     dumpPassInfo(*I, Msg1, Msg);
755
756     (*I)->releaseMemory();
757     
758     std::map<AnalysisID, Pass*>::iterator Pos = 
759       AvailableAnalysis.find((*I)->getPassInfo());
760     
761     // It is possible that pass is already removed from the AvailableAnalysis
762     if (Pos != AvailableAnalysis.end())
763       AvailableAnalysis.erase(Pos);
764   }
765 }
766
767 /// Add pass P into the PassVector. Update 
768 /// AvailableAnalysis appropriately if ProcessAnalysis is true.
769 void PMDataManager::addPassToManager(Pass *P, 
770                                      bool ProcessAnalysis) {
771
772   // This manager is going to manage pass P. Set up analysis resolver
773   // to connect them.
774   AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
775   P->setResolver(AR);
776
777   if (ProcessAnalysis) {
778
779     // At the moment, this pass is the last user of all required passes.
780     std::vector<Pass *> LastUses;
781     std::vector<Pass *> RequiredPasses;
782     unsigned PDepth = this->getDepth();
783
784     collectRequiredAnalysisPasses(RequiredPasses, P);
785     for (std::vector<Pass *>::iterator I = RequiredPasses.begin(),
786            E = RequiredPasses.end(); I != E; ++I) {
787       Pass *PRequired = *I;
788       unsigned RDepth = 0;
789
790       PMDataManager &DM = PRequired->getResolver()->getPMDataManager();
791       RDepth = DM.getDepth();
792
793       if (PDepth == RDepth)
794         LastUses.push_back(PRequired);
795       else if (PDepth >  RDepth) {
796         // Let the parent claim responsibility of last use
797         ForcedLastUses.push_back(PRequired);
798       } else {
799         // Note : This feature is not yet implemented
800         assert (0 && 
801                 "Unable to handle Pass that requires lower level Analysis pass");
802       }
803     }
804
805     if (!LastUses.empty())
806       TPM->setLastUser(LastUses, P);
807
808     // Take a note of analysis required and made available by this pass.
809     // Remove the analysis not preserved by this pass
810     removeNotPreservedAnalysis(P);
811     recordAvailableAnalysis(P);
812   }
813
814   // Add pass
815   PassVector.push_back(P);
816 }
817
818 /// Populate RequiredPasses with the analysis pass that are required by
819 /// pass P.
820 void PMDataManager::collectRequiredAnalysisPasses(std::vector<Pass *> &RP,
821                                                   Pass *P) {
822   AnalysisUsage AnUsage;
823   P->getAnalysisUsage(AnUsage);
824   const std::vector<AnalysisID> &RequiredSet = AnUsage.getRequiredSet();
825   for (std::vector<AnalysisID>::const_iterator 
826          I = RequiredSet.begin(), E = RequiredSet.end();
827        I != E; ++I) {
828     Pass *AnalysisPass = findAnalysisPass(*I, true);
829     assert (AnalysisPass && "Analysis pass is not available");
830     RP.push_back(AnalysisPass);
831   }
832
833   const std::vector<AnalysisID> &IDs = AnUsage.getRequiredTransitiveSet();
834   for (std::vector<AnalysisID>::const_iterator I = IDs.begin(),
835          E = IDs.end(); I != E; ++I) {
836     Pass *AnalysisPass = findAnalysisPass(*I, true);
837     assert (AnalysisPass && "Analysis pass is not available");
838     RP.push_back(AnalysisPass);
839   }
840 }
841
842 // All Required analyses should be available to the pass as it runs!  Here
843 // we fill in the AnalysisImpls member of the pass so that it can
844 // successfully use the getAnalysis() method to retrieve the
845 // implementations it needs.
846 //
847 void PMDataManager::initializeAnalysisImpl(Pass *P) {
848   AnalysisUsage AnUsage;
849   P->getAnalysisUsage(AnUsage);
850  
851   for (std::vector<const PassInfo *>::const_iterator
852          I = AnUsage.getRequiredSet().begin(),
853          E = AnUsage.getRequiredSet().end(); I != E; ++I) {
854     Pass *Impl = findAnalysisPass(*I, true);
855     if (Impl == 0)
856       assert(0 && "Analysis used but not available!");
857     AnalysisResolver_New *AR = P->getResolver();
858     AR->addAnalysisImplsPair(*I, Impl);
859   }
860 }
861
862 /// Find the pass that implements Analysis AID. If desired pass is not found
863 /// then return NULL.
864 Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
865
866   // Check if AvailableAnalysis map has one entry.
867   std::map<AnalysisID, Pass*>::const_iterator I =  AvailableAnalysis.find(AID);
868
869   if (I != AvailableAnalysis.end())
870     return I->second;
871
872   // Search Parents through TopLevelManager
873   if (SearchParent)
874     return TPM->findAnalysisPass(AID);
875   
876   return NULL;
877 }
878
879
880 //===----------------------------------------------------------------------===//
881 // NOTE: Is this the right place to define this method ?
882 // getAnalysisToUpdate - Return an analysis result or null if it doesn't exist
883 Pass *AnalysisResolver_New::getAnalysisToUpdate(AnalysisID ID, bool dir) const {
884   return PM.findAnalysisPass(ID, dir);
885 }
886
887 //===----------------------------------------------------------------------===//
888 // BasicBlockPassManager implementation
889
890 /// Add pass P into PassVector and return true. If this pass is not
891 /// manageable by this manager then return false.
892 bool
893 BasicBlockPassManager::addPass(Pass *P) {
894
895   BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
896   if (!BP)
897     return false;
898
899   // If this pass does not preserve anlysis that is used by other passes
900   // managed by this manager than it is not a suiable pass for this manager.
901   if (!manageablePass(P))
902     return false;
903
904   addPassToManager (BP);
905
906   return true;
907 }
908
909 /// Execute all of the passes scheduled for execution by invoking 
910 /// runOnBasicBlock method.  Keep track of whether any of the passes modifies 
911 /// the function, and if so, return true.
912 bool
913 BasicBlockPassManager::runOnFunction(Function &F) {
914
915   if (F.isExternal())
916     return false;
917
918   bool Changed = doInitialization(F);
919   initializeAnalysisInfo();
920
921   std::string Msg1 = "Executing Pass '";
922   std::string Msg3 = "' Made Modification '";
923
924   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
925     for (std::vector<Pass *>::iterator itr = passVectorBegin(),
926            e = passVectorEnd(); itr != e; ++itr) {
927       Pass *P = *itr;
928       std::string Msg2 = "' on BasicBlock '" + (*I).getName() + "'...\n";
929       dumpPassInfo(P, Msg1, Msg2);
930       initializeAnalysisImpl(P);
931
932       BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);
933       Changed |= BP->runOnBasicBlock(*I);
934
935       if (Changed)
936         dumpPassInfo(P, Msg3, Msg2);
937
938       removeNotPreservedAnalysis(P);
939       recordAvailableAnalysis(P);
940       removeDeadPasses(P, Msg2);
941     }
942   return Changed | doFinalization(F);
943 }
944
945 // Implement doInitialization and doFinalization
946 inline bool BasicBlockPassManager::doInitialization(Module &M) {
947   bool Changed = false;
948
949   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
950          e = passVectorEnd(); itr != e; ++itr) {
951     Pass *P = *itr;
952     BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);    
953     Changed |= BP->doInitialization(M);
954   }
955
956   return Changed;
957 }
958
959 inline bool BasicBlockPassManager::doFinalization(Module &M) {
960   bool Changed = false;
961
962   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
963          e = passVectorEnd(); itr != e; ++itr) {
964     Pass *P = *itr;
965     BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);    
966     Changed |= BP->doFinalization(M);
967   }
968
969   return Changed;
970 }
971
972 inline bool BasicBlockPassManager::doInitialization(Function &F) {
973   bool Changed = false;
974
975   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
976          e = passVectorEnd(); itr != e; ++itr) {
977     Pass *P = *itr;
978     BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);    
979     Changed |= BP->doInitialization(F);
980   }
981
982   return Changed;
983 }
984
985 inline bool BasicBlockPassManager::doFinalization(Function &F) {
986   bool Changed = false;
987
988   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
989          e = passVectorEnd(); itr != e; ++itr) {
990     Pass *P = *itr;
991     BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P);    
992     Changed |= BP->doFinalization(F);
993   }
994
995   return Changed;
996 }
997
998
999 //===----------------------------------------------------------------------===//
1000 // FunctionPassManager implementation
1001
1002 /// Create new Function pass manager
1003 FunctionPassManager::FunctionPassManager(ModuleProvider *P) {
1004   FPM = new FunctionPassManagerImpl_New(0);
1005   // FPM is the top level manager.
1006   FPM->setTopLevelManager(FPM);
1007
1008   PMDataManager *PMD = dynamic_cast<PMDataManager *>(FPM);
1009   AnalysisResolver_New *AR = new AnalysisResolver_New(*PMD);
1010   FPM->setResolver(AR);
1011   
1012   FPM->addPassManager(FPM);
1013   MP = P;
1014 }
1015
1016 FunctionPassManager::~FunctionPassManager() {
1017   // Note : FPM maintains one entry in PassManagers vector.
1018   // This one entry is FPM itself. This is not ideal. One
1019   // alternative is have one additional layer between
1020   // FunctionPassManager and FunctionPassManagerImpl.
1021   // Meanwhile, to avoid going into infinte loop, first
1022   // remove FPM from its PassMangers vector.
1023   FPM->clearManagers();
1024   delete FPM;
1025 }
1026
1027 /// add - Add a pass to the queue of passes to run.  This passes
1028 /// ownership of the Pass to the PassManager.  When the
1029 /// PassManager_X is destroyed, the pass will be destroyed as well, so
1030 /// there is no need to delete the pass. (TODO delete passes.)
1031 /// This implies that all passes MUST be allocated with 'new'.
1032 void FunctionPassManager::add(Pass *P) { 
1033   FPM->add(P);
1034 }
1035
1036 /// run - Execute all of the passes scheduled for execution.  Keep
1037 /// track of whether any of the passes modifies the function, and if
1038 /// so, return true.
1039 ///
1040 bool FunctionPassManager::run(Function &F) {
1041   std::string errstr;
1042   if (MP->materializeFunction(&F, &errstr)) {
1043     cerr << "Error reading bytecode file: " << errstr << "\n";
1044     abort();
1045   }
1046   return FPM->run(F);
1047 }
1048
1049
1050 /// doInitialization - Run all of the initializers for the function passes.
1051 ///
1052 bool FunctionPassManager::doInitialization() {
1053   return FPM->doInitialization(*MP->getModule());
1054 }
1055
1056 /// doFinalization - Run all of the initializers for the function passes.
1057 ///
1058 bool FunctionPassManager::doFinalization() {
1059   return FPM->doFinalization(*MP->getModule());
1060 }
1061
1062 //===----------------------------------------------------------------------===//
1063 // FunctionPassManagerImpl_New implementation
1064
1065 /// Add pass P into the pass manager queue. If P is a BasicBlockPass then
1066 /// either use it into active basic block pass manager or create new basic
1067 /// block pass manager to handle pass P.
1068 bool
1069 FunctionPassManagerImpl_New::addPass(Pass *P) {
1070
1071   // If P is a BasicBlockPass then use BasicBlockPassManager.
1072   if (BasicBlockPass *BP = dynamic_cast<BasicBlockPass*>(P)) {
1073
1074     if (!activeBBPassManager || !activeBBPassManager->addPass(BP)) {
1075
1076       // If active manager exists then clear its analysis info.
1077       if (activeBBPassManager)
1078         activeBBPassManager->initializeAnalysisInfo();
1079
1080       // Create and add new manager
1081       activeBBPassManager = 
1082         new BasicBlockPassManager(getDepth() + 1);
1083       // Inherit top level manager
1084       activeBBPassManager->setTopLevelManager(this->getTopLevelManager());
1085
1086       // Add new manager into current manager's list.
1087       addPassToManager(activeBBPassManager, false);
1088
1089       // Add new manager into top level manager's indirect passes list
1090       PMDataManager *PMD = dynamic_cast<PMDataManager *>(activeBBPassManager);
1091       assert (PMD && "Manager is not Pass Manager");
1092       TPM->addIndirectPassManager(PMD);
1093
1094       // Add pass into new manager. This time it must succeed.
1095       if (!activeBBPassManager->addPass(BP))
1096         assert(0 && "Unable to add Pass");
1097     }
1098
1099     if (!ForcedLastUses.empty())
1100       TPM->setLastUser(ForcedLastUses, this);
1101
1102     return true;
1103   }
1104
1105   FunctionPass *FP = dynamic_cast<FunctionPass *>(P);
1106   if (!FP)
1107     return false;
1108
1109   // If this pass does not preserve anlysis that is used by other passes
1110   // managed by this manager than it is not a suiable pass for this manager.
1111   if (!manageablePass(P))
1112     return false;
1113
1114   addPassToManager (FP);
1115
1116   // If active manager exists then clear its analysis info.
1117   if (activeBBPassManager) {
1118     activeBBPassManager->initializeAnalysisInfo();
1119     activeBBPassManager = NULL;
1120   }
1121
1122   return true;
1123 }
1124
1125 /// Execute all of the passes scheduled for execution by invoking 
1126 /// runOnFunction method.  Keep track of whether any of the passes modifies 
1127 /// the function, and if so, return true.
1128 bool FunctionPassManagerImpl_New::runOnModule(Module &M) {
1129
1130   bool Changed = doInitialization(M);
1131   initializeAnalysisInfo();
1132
1133   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
1134     this->runOnFunction(*I);
1135
1136   return Changed | doFinalization(M);
1137 }
1138
1139 /// Execute all of the passes scheduled for execution by invoking 
1140 /// runOnFunction method.  Keep track of whether any of the passes modifies 
1141 /// the function, and if so, return true.
1142 bool FunctionPassManagerImpl_New::runOnFunction(Function &F) {
1143
1144   bool Changed = false;
1145
1146   if (F.isExternal())
1147     return false;
1148
1149   initializeAnalysisInfo();
1150
1151   std::string Msg1 = "Executing Pass '";
1152   std::string Msg3 = "' Made Modification '";
1153
1154   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1155          e = passVectorEnd(); itr != e; ++itr) {
1156     Pass *P = *itr;
1157
1158     std::string Msg2 = "' on Function '" + F.getName() + "'...\n";
1159     dumpPassInfo(P, Msg1, Msg2);
1160
1161     initializeAnalysisImpl(P);    
1162     FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1163     Changed |= FP->runOnFunction(F);
1164
1165     if (Changed)
1166       dumpPassInfo(P, Msg3, Msg2);
1167
1168     removeNotPreservedAnalysis(P);
1169     recordAvailableAnalysis(P);
1170     removeDeadPasses(P, Msg2);
1171   }
1172   return Changed;
1173 }
1174
1175
1176 inline bool FunctionPassManagerImpl_New::doInitialization(Module &M) {
1177   bool Changed = false;
1178
1179   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1180          e = passVectorEnd(); itr != e; ++itr) {
1181     Pass *P = *itr;
1182     
1183     FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1184     Changed |= FP->doInitialization(M);
1185   }
1186
1187   return Changed;
1188 }
1189
1190 inline bool FunctionPassManagerImpl_New::doFinalization(Module &M) {
1191   bool Changed = false;
1192
1193   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1194          e = passVectorEnd(); itr != e; ++itr) {
1195     Pass *P = *itr;
1196     
1197     FunctionPass *FP = dynamic_cast<FunctionPass*>(P);
1198     Changed |= FP->doFinalization(M);
1199   }
1200
1201   return Changed;
1202 }
1203
1204 // Execute all the passes managed by this top level manager.
1205 // Return true if any function is modified by a pass.
1206 bool FunctionPassManagerImpl_New::run(Function &F) {
1207
1208   bool Changed = false;
1209   for (std::vector<Pass *>::iterator I = passManagersBegin(),
1210          E = passManagersEnd(); I != E; ++I) {
1211     FunctionPassManagerImpl_New *FP = 
1212       dynamic_cast<FunctionPassManagerImpl_New *>(*I);
1213     Changed |= FP->runOnFunction(F);
1214   }
1215   return Changed;
1216 }
1217
1218 //===----------------------------------------------------------------------===//
1219 // ModulePassManager implementation
1220
1221 /// Add P into pass vector if it is manageble. If P is a FunctionPass
1222 /// then use FunctionPassManagerImpl_New to manage it. Return false if P
1223 /// is not manageable by this manager.
1224 bool
1225 ModulePassManager::addPass(Pass *P) {
1226
1227   // If P is FunctionPass then use function pass maanager.
1228   if (FunctionPass *FP = dynamic_cast<FunctionPass*>(P)) {
1229
1230     if (!activeFunctionPassManager || !activeFunctionPassManager->addPass(P)) {
1231
1232       // If active manager exists then clear its analysis info.
1233       if (activeFunctionPassManager) 
1234         activeFunctionPassManager->initializeAnalysisInfo();
1235
1236       // Create and add new manager
1237       activeFunctionPassManager = 
1238         new FunctionPassManagerImpl_New(getDepth() + 1);
1239       
1240       // Add new manager into current manager's list
1241       addPassToManager(activeFunctionPassManager, false);
1242
1243       // Inherit top level manager
1244       activeFunctionPassManager->setTopLevelManager(this->getTopLevelManager());
1245
1246       // Add new manager into top level manager's indirect passes list
1247       PMDataManager *PMD =
1248         dynamic_cast<PMDataManager *>(activeFunctionPassManager);
1249       assert(PMD && "Manager is not Pass Manager");
1250       TPM->addIndirectPassManager(PMD);
1251       
1252       // Add pass into new manager. This time it must succeed.
1253       if (!activeFunctionPassManager->addPass(FP))
1254         assert(0 && "Unable to add pass");
1255     }
1256
1257     if (!ForcedLastUses.empty())
1258       TPM->setLastUser(ForcedLastUses, this);
1259
1260     return true;
1261   }
1262
1263   ModulePass *MP = dynamic_cast<ModulePass *>(P);
1264   if (!MP)
1265     return false;
1266
1267   // If this pass does not preserve anlysis that is used by other passes
1268   // managed by this manager than it is not a suiable pass for this manager.
1269   if (!manageablePass(P))
1270     return false;
1271
1272   addPassToManager(MP);
1273   // If active manager exists then clear its analysis info.
1274   if (activeFunctionPassManager) {
1275     activeFunctionPassManager->initializeAnalysisInfo();
1276     activeFunctionPassManager = NULL;
1277   }
1278
1279   return true;
1280 }
1281
1282
1283 /// Execute all of the passes scheduled for execution by invoking 
1284 /// runOnModule method.  Keep track of whether any of the passes modifies 
1285 /// the module, and if so, return true.
1286 bool
1287 ModulePassManager::runOnModule(Module &M) {
1288   bool Changed = false;
1289   initializeAnalysisInfo();
1290
1291   std::string Msg1 = "Executing Pass '";
1292   std::string Msg3 = "' Made Modification '";
1293
1294   for (std::vector<Pass *>::iterator itr = passVectorBegin(),
1295          e = passVectorEnd(); itr != e; ++itr) {
1296     Pass *P = *itr;
1297
1298     std::string Msg2 = "' on Module '" + M.getModuleIdentifier() + "'...\n";
1299     dumpPassInfo(P, Msg1, Msg2);
1300
1301     initializeAnalysisImpl(P);
1302     ModulePass *MP = dynamic_cast<ModulePass*>(P);
1303     Changed |= MP->runOnModule(M);
1304
1305     if (Changed)
1306       dumpPassInfo(P, Msg3, Msg2);
1307
1308     removeNotPreservedAnalysis(P);
1309     recordAvailableAnalysis(P);
1310     removeDeadPasses(P, Msg2);
1311   }
1312   return Changed;
1313 }
1314
1315 //===----------------------------------------------------------------------===//
1316 // PassManagerImpl implementation
1317 //
1318 /// Add P into active pass manager or use new module pass manager to
1319 /// manage it.
1320 bool PassManagerImpl_New::addPass(Pass *P) {
1321
1322   if (!activeManager || !activeManager->addPass(P)) {
1323     activeManager = new ModulePassManager(getDepth() + 1);
1324     // Inherit top level manager
1325     activeManager->setTopLevelManager(this->getTopLevelManager());
1326
1327     // This top level manager is going to manage activeManager. 
1328     // Set up analysis resolver to connect them.
1329     AnalysisResolver_New *AR = new AnalysisResolver_New(*this);
1330     activeManager->setResolver(AR);
1331
1332     addPassManager(activeManager);
1333     return activeManager->addPass(P);
1334   }
1335   return true;
1336 }
1337
1338 /// run - Execute all of the passes scheduled for execution.  Keep track of
1339 /// whether any of the passes modifies the module, and if so, return true.
1340 bool PassManagerImpl_New::run(Module &M) {
1341
1342   bool Changed = false;
1343
1344   dumpArguments();
1345   if (PassDebugging_New >= Structure)
1346     dumpPasses();
1347
1348   for (std::vector<Pass *>::iterator I = passManagersBegin(),
1349          E = passManagersEnd(); I != E; ++I) {
1350     ModulePassManager *MP = dynamic_cast<ModulePassManager *>(*I);
1351     Changed |= MP->runOnModule(M);
1352   }
1353   return Changed;
1354 }
1355
1356 //===----------------------------------------------------------------------===//
1357 // PassManager implementation
1358
1359 /// Create new pass manager
1360 PassManager::PassManager() {
1361   PM = new PassManagerImpl_New(0);
1362   // PM is the top level manager
1363   PM->setTopLevelManager(PM);
1364 }
1365
1366 PassManager::~PassManager() {
1367   delete PM;
1368 }
1369
1370 /// add - Add a pass to the queue of passes to run.  This passes ownership of
1371 /// the Pass to the PassManager.  When the PassManager is destroyed, the pass
1372 /// will be destroyed as well, so there is no need to delete the pass.  This
1373 /// implies that all passes MUST be allocated with 'new'.
1374 void 
1375 PassManager::add(Pass *P) {
1376   PM->add(P);
1377 }
1378
1379 /// run - Execute all of the passes scheduled for execution.  Keep track of
1380 /// whether any of the passes modifies the module, and if so, return true.
1381 bool
1382 PassManager::run(Module &M) {
1383   return PM->run(M);
1384 }
1385
1386 #endif