lib/VMCore/Pass.cpp

   1 //===- Pass.cpp - LLVM Pass Infrastructure Impementation ------------------===//
   2 //
   3 // This file implements the LLVM Pass infrastructure.  It is primarily
   4 // responsible with ensuring that passes are executed and batched together
   5 // optimally.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/PassManager.h"
  10 #include "PassManagerT.h"         // PassManagerT implementation
  11 #include "llvm/Module.h"
  12 #include "Support/STLExtras.h"
  13 #include "Support/TypeInfo.h"
  14 #include <stdio.h>
  15 #include <sys/resource.h>
  16 #include <sys/time.h>
  17 #include <sys/unistd.h>
  18 #include <set>
  19
  20 // IncludeFile - Stub function used to help linking out.
  21 IncludeFile::IncludeFile(void*) {}
  22
  23 //===----------------------------------------------------------------------===//
  24 //   AnalysisID Class Implementation
  25 //
  26
  27 static std::vector<const PassInfo*> CFGOnlyAnalyses;
  28
  29 void RegisterPassBase::setPreservesCFG() {
  30   CFGOnlyAnalyses.push_back(PIObj);
  31 }
  32
  33 //===----------------------------------------------------------------------===//
  34 //   AnalysisResolver Class Implementation
  35 //
  36
  37 void AnalysisResolver::setAnalysisResolver(Pass *P, AnalysisResolver *AR) {
  38   assert(P->Resolver == 0 && "Pass already in a PassManager!");
  39   P->Resolver = AR;
  40 }
  41
  42 //===----------------------------------------------------------------------===//
  43 //   AnalysisUsage Class Implementation
  44 //
  45
  46 // setPreservesCFG - This function should be called to by the pass, iff they do
  47 // not:
  48 //
  49 //  1. Add or remove basic blocks from the function
  50 //  2. Modify terminator instructions in any way.
  51 //
  52 // This function annotates the AnalysisUsage info object to say that analyses
  53 // that only depend on the CFG are preserved by this pass.
  54 //
  55 void AnalysisUsage::setPreservesCFG() {
  56   // Since this transformation doesn't modify the CFG, it preserves all analyses
  57   // that only depend on the CFG (like dominators, loop info, etc...)
  58   //
  59   Preserved.insert(Preserved.end(),
  60                    CFGOnlyAnalyses.begin(), CFGOnlyAnalyses.end());
  61 }
  62
  63
  64 //===----------------------------------------------------------------------===//
  65 // PassManager implementation - The PassManager class is a simple Pimpl class
  66 // that wraps the PassManagerT template.
  67 //
  68 PassManager::PassManager() : PM(new PassManagerT<Module>()) {}
  69 PassManager::~PassManager() { delete PM; }
  70 void PassManager::add(Pass *P) { PM->add(P); }
  71 bool PassManager::run(Module &M) { return PM->run(M); }
  72
  73
  74 //===----------------------------------------------------------------------===//
  75 // TimingInfo Class - This class is used to calculate information about the
  76 // amount of time each pass takes to execute.  This only happens with
  77 // -time-passes is enabled on the command line.
  78 //
  79 static cl::opt<bool>
  80 EnableTiming("time-passes",
  81             cl::desc("Time each pass, printing elapsed time for each on exit"));
  82
  83 // Create method.  If Timing is enabled, this creates and returns a new timing
  84 // object, otherwise it returns null.
  85 //
  86 TimingInfo *TimingInfo::create() {
  87   return EnableTiming ? new TimingInfo() : 0;
  88 }
  89
  90 void PMDebug::PrintArgumentInformation(const Pass *P) {
  91   // Print out passes in pass manager...
  92   if (const AnalysisResolver *PM = dynamic_cast<const AnalysisResolver*>(P)) {
  93     for (unsigned i = 0, e = PM->getNumContainedPasses(); i != e; ++i)
  94       PrintArgumentInformation(PM->getContainedPass(i));
  95
  96   } else {  // Normal pass.  Print argument information...
  97     // Print out arguments for registered passes that are _optimizations_
  98     if (const PassInfo *PI = P->getPassInfo())
  99       if (PI->getPassType() & PassInfo::Optimization)
 100         std::cerr << " -" << PI->getPassArgument();
 101   }
 102 }
 103
 104 void PMDebug::PrintPassInformation(unsigned Depth, const char *Action,
 105                                    Pass *P, Annotable *V) {
 106   if (PassDebugging >= Executions) {
 107     std::cerr << (void*)P << std::string(Depth*2+1, ' ') << Action << " '"
 108               << P->getPassName();
 109     if (V) {
 110       std::cerr << "' on ";
 111
 112       if (dynamic_cast<Module*>(V)) {
 113         std::cerr << "Module\n"; return;
 114       } else if (Function *F = dynamic_cast<Function*>(V))
 115         std::cerr << "Function '" << F->getName();
 116       else if (BasicBlock *BB = dynamic_cast<BasicBlock*>(V))
 117         std::cerr << "BasicBlock '" << BB->getName();
 118       else if (Value *Val = dynamic_cast<Value*>(V))
 119         std::cerr << typeid(*Val).name() << " '" << Val->getName();
 120     }
 121     std::cerr << "'...\n";
 122   }
 123 }
 124
 125 void PMDebug::PrintAnalysisSetInfo(unsigned Depth, const char *Msg,
 126                                    Pass *P, const std::vector<AnalysisID> &Set){
 127   if (PassDebugging >= Details && !Set.empty()) {
 128     std::cerr << (void*)P << std::string(Depth*2+3, ' ') << Msg << " Analyses:";
 129     for (unsigned i = 0; i != Set.size(); ++i) {
 130       if (i) std::cerr << ",";
 131       std::cerr << " " << Set[i]->getPassName();
 132     }
 133     std::cerr << "\n";
 134   }
 135 }
 136
 137 //===----------------------------------------------------------------------===//
 138 // Pass Implementation
 139 //
 140
 141 void Pass::addToPassManager(PassManagerT<Module> *PM, AnalysisUsage &AU) {
 142   PM->addPass(this, AU);
 143 }
 144
 145 // dumpPassStructure - Implement the -debug-passes=Structure option
 146 void Pass::dumpPassStructure(unsigned Offset) {
 147   std::cerr << std::string(Offset*2, ' ') << getPassName() << "\n";
 148 }
 149
 150 // getPassName - Use C++ RTTI to get a SOMEWHAT intelligable name for the pass.
 151 //
 152 const char *Pass::getPassName() const {
 153   if (const PassInfo *PI = getPassInfo())
 154     return PI->getPassName();
 155   return typeid(*this).name();
 156 }
 157
 158 // print - Print out the internal state of the pass.  This is called by Analyse
 159 // to print out the contents of an analysis.  Otherwise it is not neccesary to
 160 // implement this method.
 161 //
 162 void Pass::print(std::ostream &O) const {
 163   O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n";
 164 }
 165
 166 // dump - call print(std::cerr);
 167 void Pass::dump() const {
 168   print(std::cerr, 0);
 169 }
 170
 171 //===----------------------------------------------------------------------===//
 172 // ImmutablePass Implementation
 173 //
 174 void ImmutablePass::addToPassManager(PassManagerT<Module> *PM,
 175                                      AnalysisUsage &AU) {
 176   PM->addPass(this, AU);
 177 }
 178
 179
 180 //===----------------------------------------------------------------------===//
 181 // FunctionPass Implementation
 182 //
 183
 184 // run - On a module, we run this pass by initializing, runOnFunction'ing once
 185 // for every function in the module, then by finalizing.
 186 //
 187 bool FunctionPass::run(Module &M) {
 188   bool Changed = doInitialization(M);
 189
 190   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
 191     if (!I->isExternal())      // Passes are not run on external functions!
 192     Changed |= runOnFunction(*I);
 193
 194   return Changed | doFinalization(M);
 195 }
 196
 197 // run - On a function, we simply initialize, run the function, then finalize.
 198 //
 199 bool FunctionPass::run(Function &F) {
 200   if (F.isExternal()) return false;// Passes are not run on external functions!
 201
 202   return doInitialization(*F.getParent()) | runOnFunction(F)
 203        | doFinalization(*F.getParent());
 204 }
 205
 206 void FunctionPass::addToPassManager(PassManagerT<Module> *PM,
 207                                     AnalysisUsage &AU) {
 208   PM->addPass(this, AU);
 209 }
 210
 211 void FunctionPass::addToPassManager(PassManagerT<Function> *PM,
 212                                     AnalysisUsage &AU) {
 213   PM->addPass(this, AU);
 214 }
 215
 216 //===----------------------------------------------------------------------===//
 217 // BasicBlockPass Implementation
 218 //
 219
 220 // To run this pass on a function, we simply call runOnBasicBlock once for each
 221 // function.
 222 //
 223 bool BasicBlockPass::runOnFunction(Function &F) {
 224   bool Changed = doInitialization(F);
 225   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 226     Changed |= runOnBasicBlock(*I);
 227   return Changed | doFinalization(F);
 228 }
 229
 230 // To run directly on the basic block, we initialize, runOnBasicBlock, then
 231 // finalize.
 232 //
 233 bool BasicBlockPass::run(BasicBlock &BB) {
 234   Function &F = *BB.getParent();
 235   Module &M = *F.getParent();
 236   return doInitialization(M) | doInitialization(F) | runOnBasicBlock(BB) |
 237          doFinalization(F) | doFinalization(M);
 238 }
 239
 240 void BasicBlockPass::addToPassManager(PassManagerT<Function> *PM,
 241                                       AnalysisUsage &AU) {
 242   PM->addPass(this, AU);
 243 }
 244
 245 void BasicBlockPass::addToPassManager(PassManagerT<BasicBlock> *PM,
 246                                       AnalysisUsage &AU) {
 247   PM->addPass(this, AU);
 248 }
 249
 250
 251 //===----------------------------------------------------------------------===//
 252 // Pass Registration mechanism
 253 //
 254 static std::map<TypeInfo, PassInfo*> *PassInfoMap = 0;
 255 static std::vector<PassRegistrationListener*> *Listeners = 0;
 256
 257 // getPassInfo - Return the PassInfo data structure that corresponds to this
 258 // pass...
 259 const PassInfo *Pass::getPassInfo() const {
 260   if (PassInfoCache) return PassInfoCache;
 261   return lookupPassInfo(typeid(*this));
 262 }
 263
 264 const PassInfo *Pass::lookupPassInfo(const std::type_info &TI) {
 265   if (PassInfoMap == 0) return 0;
 266   std::map<TypeInfo, PassInfo*>::iterator I = PassInfoMap->find(TI);
 267   return (I != PassInfoMap->end()) ? I->second : 0;
 268 }
 269
 270 void RegisterPassBase::registerPass(PassInfo *PI) {
 271   if (PassInfoMap == 0)
 272     PassInfoMap = new std::map<TypeInfo, PassInfo*>();
 273
 274   assert(PassInfoMap->find(PI->getTypeInfo()) == PassInfoMap->end() &&
 275          "Pass already registered!");
 276   PIObj = PI;
 277   PassInfoMap->insert(std::make_pair(TypeInfo(PI->getTypeInfo()), PI));
 278
 279   // Notify any listeners...
 280   if (Listeners)
 281     for (std::vector<PassRegistrationListener*>::iterator
 282            I = Listeners->begin(), E = Listeners->end(); I != E; ++I)
 283       (*I)->passRegistered(PI);
 284 }
 285
 286 void RegisterPassBase::unregisterPass(PassInfo *PI) {
 287   assert(PassInfoMap && "Pass registered but not in map!");
 288   std::map<TypeInfo, PassInfo*>::iterator I =
 289     PassInfoMap->find(PI->getTypeInfo());
 290   assert(I != PassInfoMap->end() && "Pass registered but not in map!");
 291
 292   // Remove pass from the map...
 293   PassInfoMap->erase(I);
 294   if (PassInfoMap->empty()) {
 295     delete PassInfoMap;
 296     PassInfoMap = 0;
 297   }
 298
 299   // Notify any listeners...
 300   if (Listeners)
 301     for (std::vector<PassRegistrationListener*>::iterator
 302            I = Listeners->begin(), E = Listeners->end(); I != E; ++I)
 303       (*I)->passUnregistered(PI);
 304
 305   // Delete the PassInfo object itself...
 306   delete PI;
 307 }
 308
 309 //===----------------------------------------------------------------------===//
 310 //                  Analysis Group Implementation Code
 311 //===----------------------------------------------------------------------===//
 312
 313 struct AnalysisGroupInfo {
 314   const PassInfo *DefaultImpl;
 315   std::set<const PassInfo *> Implementations;
 316   AnalysisGroupInfo() : DefaultImpl(0) {}
 317 };
 318
 319 static std::map<const PassInfo *, AnalysisGroupInfo> *AnalysisGroupInfoMap = 0;
 320
 321 // RegisterAGBase implementation
 322 //
 323 RegisterAGBase::RegisterAGBase(const std::type_info &Interface,
 324                                const std::type_info *Pass, bool isDefault)
 325   : ImplementationInfo(0), isDefaultImplementation(isDefault) {
 326
 327   InterfaceInfo = const_cast<PassInfo*>(Pass::lookupPassInfo(Interface));
 328   if (InterfaceInfo == 0) {   // First reference to Interface, add it now.
 329     InterfaceInfo =   // Create the new PassInfo for the interface...
 330       new PassInfo("", "", Interface, PassInfo::AnalysisGroup, 0, 0);
 331     registerPass(InterfaceInfo);
 332     PIObj = 0;
 333   }
 334   assert(InterfaceInfo->getPassType() == PassInfo::AnalysisGroup &&
 335          "Trying to join an analysis group that is a normal pass!");
 336
 337   if (Pass) {
 338     ImplementationInfo = Pass::lookupPassInfo(*Pass);
 339     assert(ImplementationInfo &&
 340            "Must register pass before adding to AnalysisGroup!");
 341
 342     // Make sure we keep track of the fact that the implementation implements
 343     // the interface.
 344     PassInfo *IIPI = const_cast<PassInfo*>(ImplementationInfo);
 345     IIPI->addInterfaceImplemented(InterfaceInfo);
 346
 347     // Lazily allocate to avoid nasty initialization order dependencies
 348     if (AnalysisGroupInfoMap == 0)
 349       AnalysisGroupInfoMap = new std::map<const PassInfo *,AnalysisGroupInfo>();
 350
 351     AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo];
 352     assert(AGI.Implementations.count(ImplementationInfo) == 0 &&
 353            "Cannot add a pass to the same analysis group more than once!");
 354     AGI.Implementations.insert(ImplementationInfo);
 355     if (isDefault) {
 356       assert(AGI.DefaultImpl == 0 && InterfaceInfo->getNormalCtor() == 0 &&
 357              "Default implementation for analysis group already specified!");
 358       assert(ImplementationInfo->getNormalCtor() &&
 359            "Cannot specify pass as default if it does not have a default ctor");
 360       AGI.DefaultImpl = ImplementationInfo;
 361       InterfaceInfo->setNormalCtor(ImplementationInfo->getNormalCtor());
 362     }
 363   }
 364 }
 365
 366 void RegisterAGBase::setGroupName(const char *Name) {
 367   assert(InterfaceInfo->getPassName()[0] == 0 && "Interface Name already set!");
 368   InterfaceInfo->setPassName(Name);
 369 }
 370
 371 RegisterAGBase::~RegisterAGBase() {
 372   if (ImplementationInfo) {
 373     assert(AnalysisGroupInfoMap && "Inserted into map, but map doesn't exist?");
 374     AnalysisGroupInfo &AGI = (*AnalysisGroupInfoMap)[InterfaceInfo];
 375
 376     assert(AGI.Implementations.count(ImplementationInfo) &&
 377            "Pass not a member of analysis group?");
 378
 379     if (AGI.DefaultImpl == ImplementationInfo)
 380       AGI.DefaultImpl = 0;
 381
 382     AGI.Implementations.erase(ImplementationInfo);
 383
 384     // Last member of this analysis group? Unregister PassInfo, delete map entry
 385     if (AGI.Implementations.empty()) {
 386       assert(AGI.DefaultImpl == 0 &&
 387              "Default implementation didn't unregister?");
 388       AnalysisGroupInfoMap->erase(InterfaceInfo);
 389       if (AnalysisGroupInfoMap->empty()) {  // Delete map if empty
 390         delete AnalysisGroupInfoMap;
 391         AnalysisGroupInfoMap = 0;
 392       }
 393
 394       unregisterPass(InterfaceInfo);
 395     }
 396   }
 397 }
 398
 399
 400 //===----------------------------------------------------------------------===//
 401 // PassRegistrationListener implementation
 402 //
 403
 404 // PassRegistrationListener ctor - Add the current object to the list of
 405 // PassRegistrationListeners...
 406 PassRegistrationListener::PassRegistrationListener() {
 407   if (!Listeners) Listeners = new std::vector<PassRegistrationListener*>();
 408   Listeners->push_back(this);
 409 }
 410
 411 // dtor - Remove object from list of listeners...
 412 PassRegistrationListener::~PassRegistrationListener() {
 413   std::vector<PassRegistrationListener*>::iterator I =
 414     std::find(Listeners->begin(), Listeners->end(), this);
 415   assert(Listeners && I != Listeners->end() &&
 416          "PassRegistrationListener not registered!");
 417   Listeners->erase(I);
 418
 419   if (Listeners->empty()) {
 420     delete Listeners;
 421     Listeners = 0;
 422   }
 423 }
 424
 425 // enumeratePasses - Iterate over the registered passes, calling the
 426 // passEnumerate callback on each PassInfo object.
 427 //
 428 void PassRegistrationListener::enumeratePasses() {
 429   if (PassInfoMap)
 430     for (std::map<TypeInfo, PassInfo*>::iterator I = PassInfoMap->begin(),
 431            E = PassInfoMap->end(); I != E; ++I)
 432       passEnumerate(I->second);
 433 }