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