lib/VMCore/PassManagerT.h

   1 //===- llvm/PassManager.h - Container for Passes -----------------*- C++ -*--=//
   2 //
   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.
   7 //
   8 // The PassManagerT template is instantiated three times to do its job.
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #ifndef LLVM_PASSMANAGER_H
  13 #define LLVM_PASSMANAGER_H
  14
  15 #include "llvm/Pass.h"
  16 #include <string>
  17
  18 // PassManager - Top level PassManagerT instantiation intended to be used.
  19 typedef PassManagerT<Module> PassManager;
  20
  21
  22 //===----------------------------------------------------------------------===//
  23 // PMDebug class - a set of debugging functions that are enabled when compiling
  24 // with -g on.  If compiling at -O, all functions are inlined noops.
  25 //
  26 struct PMDebug {
  27 #ifdef NDEBUG
  28   inline static void PrintPassStructure(Pass *) {}
  29   inline static void PrintPassInformation(unsigned,const char*,Pass*,Value*) {}
  30   inline static void PrintAnalysisSetInfo(unsigned,const char*,
  31                                           const Pass::AnalysisSet &) {}
  32 #else
  33   // If compiled in debug mode, these functions can be enabled by setting
  34   // -debug-pass on the command line of the tool being used.
  35   //
  36   static void PrintPassStructure(Pass *P);
  37   static void PrintPassInformation(unsigned,const char*,Pass *, Value *);
  38   static void PrintAnalysisSetInfo(unsigned,const char*,const Pass::AnalysisSet&);
  39 #endif
  40 };
  41
  42
  43
  44 //===----------------------------------------------------------------------===//
  45 // Declare the PassManagerTraits which will be specialized...
  46 //
  47 template<class UnitType> class PassManagerTraits;   // Do not define.
  48
  49
  50 //===----------------------------------------------------------------------===//
  51 // PassManagerT - Container object for passes.  The PassManagerT destructor
  52 // deletes all passes contained inside of the PassManagerT, so you shouldn't
  53 // delete passes manually, and all passes should be dynamically allocated.
  54 //
  55 template<typename UnitType>
  56 class PassManagerT : public PassManagerTraits<UnitType>,public AnalysisResolver{
  57   typedef typename PassManagerTraits<UnitType>::PassClass       PassClass;
  58   typedef typename PassManagerTraits<UnitType>::SubPassClass SubPassClass;
  59   typedef typename PassManagerTraits<UnitType>::BatcherClass BatcherClass;
  60   typedef typename PassManagerTraits<UnitType>::ParentClass   ParentClass;
  61   typedef          PassManagerTraits<UnitType>                     Traits;
  62
  63   friend typename PassManagerTraits<UnitType>::PassClass;
  64   friend typename PassManagerTraits<UnitType>::SubPassClass;
  65   friend class PassManagerTraits<UnitType>;
  66
  67   std::vector<PassClass*> Passes;    // List of pass's to run
  68
  69   // The parent of this pass manager...
  70   const ParentClass *Parent;
  71
  72   // The current batcher if one is in use, or null
  73   BatcherClass *Batcher;
  74
  75   // CurrentAnalyses - As the passes are being run, this map contains the
  76   // analyses that are available to the current pass for use.  This is accessed
  77   // through the getAnalysis() function in this class and in Pass.
  78   //
  79   std::map<AnalysisID, Pass*> CurrentAnalyses;
  80
  81 public:
  82   PassManagerT(ParentClass *Par = 0) : Parent(Par), Batcher(0) {}
  83   ~PassManagerT() {
  84     // Delete all of the contained passes...
  85     for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
  86          I != E; ++I)
  87       delete *I;
  88   }
  89
  90   // run - Run all of the queued passes on the specified module in an optimal
  91   // way.
  92   virtual bool runOnUnit(UnitType *M) {
  93     bool MadeChanges = false;
  94     closeBatcher();
  95     CurrentAnalyses.clear();
  96
  97     // Output debug information...
  98     if (Parent == 0) PMDebug::PrintPassStructure(this);
  99
 100     // Run all of the passes
 101     for (unsigned i = 0, e = Passes.size(); i < e; ++i) {
 102       PassClass *P = Passes[i];
 103
 104       PMDebug::PrintPassInformation(getDepth(), "Executing Pass", P, (Value*)M);
 105
 106       // Get information about what analyses the pass uses...
 107       std::vector<AnalysisID> Required, Destroyed, Provided;
 108       P->getAnalysisUsageInfo(Required, Destroyed, Provided);
 109
 110       PMDebug::PrintAnalysisSetInfo(getDepth(), "Required", Required);
 111
 112 #ifndef NDEBUG
 113       // All Required analyses should be available to the pass as it runs!
 114       for (Pass::AnalysisSet::iterator I = Required.begin(),
 115                                        E = Required.end(); I != E; ++I) {
 116         assert(getAnalysisOrNullUp(*I) && "Analysis used but not available!");
 117       }
 118 #endif
 119
 120       // Run the sub pass!
 121       MadeChanges |= Traits::runPass(P, M);
 122
 123       PMDebug::PrintAnalysisSetInfo(getDepth(), "Destroyed", Destroyed);
 124       PMDebug::PrintAnalysisSetInfo(getDepth(), "Provided", Provided);
 125
 126       // Erase all analyses in the destroyed set...
 127       for (Pass::AnalysisSet::iterator I = Destroyed.begin(),
 128              E = Destroyed.end(); I != E; ++I)
 129         CurrentAnalyses.erase(*I);
 130
 131       // Add all analyses in the provided set...
 132       for (Pass::AnalysisSet::iterator I = Provided.begin(),
 133              E = Provided.end(); I != E; ++I)
 134         CurrentAnalyses[*I] = P;
 135     }
 136     return MadeChanges;
 137   }
 138
 139   // add - Add a pass to the queue of passes to run.  This passes ownership of
 140   // the Pass to the PassManager.  When the PassManager is destroyed, the pass
 141   // will be destroyed as well, so there is no need to delete the pass.  Also,
 142   // all passes MUST be new'd.
 143   //
 144   void add(PassClass *P) {
 145     // Get information about what analyses the pass uses...
 146     std::vector<AnalysisID> Required, Destroyed, Provided;
 147     P->getAnalysisUsageInfo(Required, Destroyed, Provided);
 148
 149     // Loop over all of the analyses used by this pass,
 150     for (std::vector<AnalysisID>::iterator I = Required.begin(),
 151                                            E = Required.end(); I != E; ++I) {
 152       if (getAnalysisOrNullDown(*I) == 0)
 153         add(I->createPass());
 154     }
 155
 156     // Tell the pass to add itself to this PassManager... the way it does so
 157     // depends on the class of the pass, and is critical to laying out passes in
 158     // an optimal order..
 159     //
 160     P->addToPassManager(this, Destroyed, Provided);
 161   }
 162
 163 #ifndef NDEBUG
 164   // dumpPassStructure - Implement the -debug-passes=PassStructure option
 165   virtual void dumpPassStructure(unsigned Offset = 0) {
 166     std::cerr << std::string(Offset*2, ' ') << "Pass Manager\n";
 167     for (std::vector<PassClass*>::iterator I = Passes.begin(), E = Passes.end();
 168          I != E; ++I)
 169       (*I)->dumpPassStructure(Offset+1);
 170   }
 171 #endif
 172
 173 public:
 174   Pass *getAnalysisOrNullDown(AnalysisID ID) {
 175     std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.find(ID);
 176     if (I == CurrentAnalyses.end()) {
 177       if (Batcher)
 178         return ((AnalysisResolver*)Batcher)->getAnalysisOrNullDown(ID);
 179       return 0;
 180     }
 181     return I->second;
 182   }
 183
 184   Pass *getAnalysisOrNullUp(AnalysisID ID) {
 185     std::map<AnalysisID, Pass*>::iterator I = CurrentAnalyses.find(ID);
 186     if (I == CurrentAnalyses.end()) {
 187       if (Parent)
 188         return ((AnalysisResolver*)Parent)->getAnalysisOrNullUp(ID);
 189       return 0;
 190     }
 191     return I->second;
 192   }
 193
 194   virtual unsigned getDepth() const {
 195     if (Parent == 0) return 0;
 196     return 1 + ((AnalysisResolver*)Parent)->getDepth();
 197   }
 198
 199 private:
 200
 201   // addPass - These functions are used to implement the subclass specific
 202   // behaviors present in PassManager.  Basically the add(Pass*) method ends up
 203   // reflecting its behavior into a Pass::addToPassManager call.  Subclasses of
 204   // Pass override it specifically so that they can reflect the type
 205   // information inherent in "this" back to the PassManager.
 206   //
 207   // For generic Pass subclasses (which are interprocedural passes), we simply
 208   // add the pass to the end of the pass list and terminate any accumulation of
 209   // MethodPasses that are present.
 210   //
 211   void addPass(PassClass *P, Pass::AnalysisSet &Destroyed,
 212                Pass::AnalysisSet &Provided) {
 213     // Providers are analysis classes which are forbidden to modify the module
 214     // they are operating on, so they are allowed to be reordered to before the
 215     // batcher...
 216     //
 217     if (Batcher && Provided.empty())
 218       closeBatcher();                     // This pass cannot be batched!
 219
 220     // Set the Resolver instance variable in the Pass so that it knows where to
 221     // find this object...
 222     //
 223     setAnalysisResolver(P, this);
 224     Passes.push_back(P);
 225
 226     // Erase all analyses in the destroyed set...
 227     for (std::vector<AnalysisID>::iterator I = Destroyed.begin(),
 228            E = Destroyed.end(); I != E; ++I)
 229       CurrentAnalyses.erase(*I);
 230
 231     // Add all analyses in the provided set...
 232     for (std::vector<AnalysisID>::iterator I = Provided.begin(),
 233            E = Provided.end(); I != E; ++I)
 234       CurrentAnalyses[*I] = P;
 235   }
 236
 237   // For MethodPass subclasses, we must be sure to batch the MethodPasses
 238   // together in a MethodPassBatcher object so that all of the analyses are run
 239   // together a method at a time.
 240   //
 241   void addPass(SubPassClass *MP, Pass::AnalysisSet &Destroyed,
 242                Pass::AnalysisSet &Provided) {
 243     if (Batcher == 0) // If we don't have a batcher yet, make one now.
 244       Batcher = new BatcherClass(this);
 245     // The Batcher will queue them passes up
 246     MP->addToPassManager(Batcher, Destroyed, Provided);
 247   }
 248
 249   // closeBatcher - Terminate the batcher that is being worked on.
 250   void closeBatcher() {
 251     if (Batcher) {
 252       Passes.push_back(Batcher);
 253       Batcher = 0;
 254     }
 255   }
 256 };
 257
 258
 259
 260 //===----------------------------------------------------------------------===//
 261 // PassManagerTraits<BasicBlock> Specialization
 262 //
 263 // This pass manager is used to group together all of the BasicBlockPass's
 264 // into a single unit.
 265 //
 266 template<> struct PassManagerTraits<BasicBlock> : public BasicBlockPass {
 267   // PassClass - The type of passes tracked by this PassManager
 268   typedef BasicBlockPass PassClass;
 269
 270   // SubPassClass - The types of classes that should be collated together
 271   // This is impossible to match, so BasicBlock instantiations of PassManagerT
 272   // do not collate.
 273   //
 274   typedef PassManagerT<Module> SubPassClass;
 275
 276   // BatcherClass - The type to use for collation of subtypes... This class is
 277   // never instantiated for the PassManager<BasicBlock>, but it must be an
 278   // instance of PassClass to typecheck.
 279   //
 280   typedef PassClass BatcherClass;
 281
 282   // ParentClass - The type of the parent PassManager...
 283   typedef PassManagerT<Method> ParentClass;
 284
 285   // runPass - Specify how the pass should be run on the UnitType
 286   static bool runPass(PassClass *P, BasicBlock *M) {
 287     // todo, init and finalize
 288     return P->runOnBasicBlock(M);
 289   }
 290
 291   // run - Implement the Pass interface...
 292   virtual bool runOnBasicBlock(BasicBlock *BB);
 293 };
 294
 295
 296
 297 //===----------------------------------------------------------------------===//
 298 // PassManagerTraits<Method> Specialization
 299 //
 300 // This pass manager is used to group together all of the MethodPass's
 301 // into a single unit.
 302 //
 303 template<> struct PassManagerTraits<Method> : public MethodPass {
 304   // PassClass - The type of passes tracked by this PassManager
 305   typedef MethodPass PassClass;
 306
 307   // SubPassClass - The types of classes that should be collated together
 308   typedef BasicBlockPass SubPassClass;
 309
 310   // BatcherClass - The type to use for collation of subtypes...
 311   typedef PassManagerT<BasicBlock> BatcherClass;
 312
 313   // ParentClass - The type of the parent PassManager...
 314   typedef PassManagerT<Module> ParentClass;
 315
 316   // PMType - The type of the passmanager that subclasses this class
 317   typedef PassManagerT<Method> PMType;
 318
 319   // runPass - Specify how the pass should be run on the UnitType
 320   static bool runPass(PassClass *P, Method *M) {
 321     return P->runOnMethod(M);
 322   }
 323
 324   // Implement the MethodPass interface...
 325   virtual bool doInitialization(Module *M);
 326   virtual bool runOnMethod(Method *M);
 327   virtual bool doFinalization(Module *M);
 328 };
 329
 330
 331
 332 //===----------------------------------------------------------------------===//
 333 // PassManagerTraits<Module> Specialization
 334 //
 335 // This is the top level PassManager implementation that holds generic passes.
 336 //
 337 template<> struct PassManagerTraits<Module> : public Pass {
 338   // PassClass - The type of passes tracked by this PassManager
 339   typedef Pass PassClass;
 340
 341   // SubPassClass - The types of classes that should be collated together
 342   typedef MethodPass SubPassClass;
 343
 344   // BatcherClass - The type to use for collation of subtypes...
 345   typedef PassManagerT<Method> BatcherClass;
 346
 347   // ParentClass - The type of the parent PassManager...
 348   typedef void ParentClass;
 349
 350   // runPass - Specify how the pass should be run on the UnitType
 351   static bool runPass(PassClass *P, Module *M) { return P->run(M); }
 352
 353   // run - Implement the Pass interface...
 354   virtual bool run(Module *M) {
 355     return ((PassManagerT<Module>*)this)->runOnUnit(M);
 356   }
 357 };
 358
 359
 360
 361 //===----------------------------------------------------------------------===//
 362 // PassManagerTraits Method Implementations
 363 //
 364
 365 // PassManagerTraits<BasicBlock> Implementations
 366 //
 367 inline bool PassManagerTraits<BasicBlock>::runOnBasicBlock(BasicBlock *BB) {
 368   return ((PassManagerT<BasicBlock>*)this)->runOnUnit(BB);
 369 }
 370
 371
 372 // PassManagerTraits<Method> Implementations
 373 //
 374 inline bool PassManagerTraits<Method>::doInitialization(Module *M) {
 375   bool Changed = false;
 376   for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
 377     ((PMType*)this)->Passes[i]->doInitialization(M);
 378   return Changed;
 379 }
 380
 381 inline bool PassManagerTraits<Method>::runOnMethod(Method *M) {
 382   return ((PMType*)this)->runOnUnit(M);
 383 }
 384
 385
 386 // PassManagerTraits<Module> Implementations
 387 //
 388 inline bool PassManagerTraits<Method>::doFinalization(Module *M) {
 389   bool Changed = false;
 390   for (unsigned i = 0, e = ((PMType*)this)->Passes.size(); i != e; ++i)
 391     ((PMType*)this)->Passes[i]->doFinalization(M);
 392   return Changed;
 393 }
 394
 395 #endif