lib/VMCore/Pass.cpp

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