lib/VMCore/Pass.cpp

   1 //===- Pass.cpp - LLVM Pass Infrastructure Implementation -----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // 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/Pass.h"
  17 #include "llvm/PassManager.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/ModuleProvider.h"
  20 #include "llvm/ADT/STLExtras.h"
  21 #include "llvm/Support/ManagedStatic.h"
  22 #include "llvm/System/Atomic.h"
  23 #include "llvm/System/Mutex.h"
  24 #include "llvm/System/Threading.h"
  25 #include <algorithm>
  26 #include <map>
  27 #include <set>
  28 using namespace llvm;
  29
  30 //===----------------------------------------------------------------------===//
  31 // Pass Implementation
  32 //
  33
  34 // Force out-of-line virtual method.
  35 Pass::~Pass() {
  36   delete Resolver;
  37 }
  38
  39 // Force out-of-line virtual method.
  40 ModulePass::~ModulePass() { }
  41
  42 bool Pass::mustPreserveAnalysisID(const PassInfo *AnalysisID) const {
  43   return Resolver->getAnalysisIfAvailable(AnalysisID, true) != 0;
  44 }
  45
  46 // dumpPassStructure - Implement the -debug-passes=Structure option
  47 void Pass::dumpPassStructure(unsigned Offset) {
  48   cerr << std::string(Offset*2, ' ') << getPassName() << "\n";
  49 }
  50
  51 /// getPassName - Return a nice clean name for a pass.  This usually
  52 /// implemented in terms of the name that is registered by one of the
  53 /// Registration templates, but can be overloaded directly.
  54 ///
  55 const char *Pass::getPassName() const {
  56   if (const PassInfo *PI = getPassInfo())
  57     return PI->getPassName();
  58   return "Unnamed pass: implement Pass::getPassName()";
  59 }
  60
  61 // print - Print out the internal state of the pass.  This is called by Analyze
  62 // to print out the contents of an analysis.  Otherwise it is not necessary to
  63 // implement this method.
  64 //
  65 void Pass::print(std::ostream &O,const Module*) const {
  66   O << "Pass::print not implemented for pass: '" << getPassName() << "'!\n";
  67 }
  68
  69 // dump - call print(cerr);
  70 void Pass::dump() const {
  71   print(*cerr.stream(), 0);
  72 }
  73
  74 //===----------------------------------------------------------------------===//
  75 // ImmutablePass Implementation
  76 //
  77 // Force out-of-line virtual method.
  78 ImmutablePass::~ImmutablePass() { }
  79
  80 //===----------------------------------------------------------------------===//
  81 // FunctionPass Implementation
  82 //
  83
  84 // run - On a module, we run this pass by initializing, runOnFunction'ing once
  85 // for every function in the module, then by finalizing.
  86 //
  87 bool FunctionPass::runOnModule(Module &M) {
  88   bool Changed = doInitialization(M);
  89
  90   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  91     if (!I->isDeclaration())      // Passes are not run on external functions!
  92     Changed |= runOnFunction(*I);
  93
  94   return Changed | doFinalization(M);
  95 }
  96
  97 // run - On a function, we simply initialize, run the function, then finalize.
  98 //
  99 bool FunctionPass::run(Function &F) {
 100   // Passes are not run on external functions!
 101   if (F.isDeclaration()) return false;
 102
 103   bool Changed = doInitialization(*F.getParent());
 104   Changed |= runOnFunction(F);
 105   return Changed | doFinalization(*F.getParent());
 106 }
 107
 108 //===----------------------------------------------------------------------===//
 109 // BasicBlockPass Implementation
 110 //
 111
 112 // To run this pass on a function, we simply call runOnBasicBlock once for each
 113 // function.
 114 //
 115 bool BasicBlockPass::runOnFunction(Function &F) {
 116   bool Changed = doInitialization(F);
 117   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
 118     Changed |= runOnBasicBlock(*I);
 119   return Changed | doFinalization(F);
 120 }
 121
 122 //===----------------------------------------------------------------------===//
 123 // Pass Registration mechanism
 124 //
 125 namespace {
 126 class PassRegistrar {
 127   /// PassInfoMap - Keep track of the passinfo object for each registered llvm
 128   /// pass.
 129   typedef std::map<intptr_t, const PassInfo*> MapType;
 130   MapType PassInfoMap;
 131
 132   /// AnalysisGroupInfo - Keep track of information for each analysis group.
 133   struct AnalysisGroupInfo {
 134     const PassInfo *DefaultImpl;
 135     std::set<const PassInfo *> Implementations;
 136     AnalysisGroupInfo() : DefaultImpl(0) {}
 137   };
 138
 139   /// AnalysisGroupInfoMap - Information for each analysis group.
 140   std::map<const PassInfo *, AnalysisGroupInfo> AnalysisGroupInfoMap;
 141
 142 public:
 143
 144   const PassInfo *GetPassInfo(intptr_t TI) const {
 145     MapType::const_iterator I = PassInfoMap.find(TI);
 146     return I != PassInfoMap.end() ? I->second : 0;
 147   }
 148
 149   void RegisterPass(const PassInfo &PI) {
 150     bool Inserted =
 151       PassInfoMap.insert(std::make_pair(PI.getTypeInfo(),&PI)).second;
 152     assert(Inserted && "Pass registered multiple times!"); Inserted=Inserted;
 153   }
 154
 155   void UnregisterPass(const PassInfo &PI) {
 156     MapType::iterator I = PassInfoMap.find(PI.getTypeInfo());
 157     assert(I != PassInfoMap.end() && "Pass registered but not in map!");
 158
 159     // Remove pass from the map.
 160     PassInfoMap.erase(I);
 161   }
 162
 163   void EnumerateWith(PassRegistrationListener *L) {
 164     for (MapType::const_iterator I = PassInfoMap.begin(),
 165          E = PassInfoMap.end(); I != E; ++I)
 166       L->passEnumerate(I->second);
 167   }
 168
 169
 170   /// Analysis Group Mechanisms.
 171   void RegisterAnalysisGroup(PassInfo *InterfaceInfo,
 172                              const PassInfo *ImplementationInfo,
 173                              bool isDefault) {
 174     AnalysisGroupInfo &AGI = AnalysisGroupInfoMap[InterfaceInfo];
 175     assert(AGI.Implementations.count(ImplementationInfo) == 0 &&
 176            "Cannot add a pass to the same analysis group more than once!");
 177     AGI.Implementations.insert(ImplementationInfo);
 178     if (isDefault) {
 179       assert(AGI.DefaultImpl == 0 && InterfaceInfo->getNormalCtor() == 0 &&
 180              "Default implementation for analysis group already specified!");
 181       assert(ImplementationInfo->getNormalCtor() &&
 182            "Cannot specify pass as default if it does not have a default ctor");
 183       AGI.DefaultImpl = ImplementationInfo;
 184       InterfaceInfo->setNormalCtor(ImplementationInfo->getNormalCtor());
 185     }
 186   }
 187 };
 188 }
 189
 190 static std::vector<PassRegistrationListener*> *Listeners = 0;
 191 static sys::SmartMutex<true> ListenersLock;
 192
 193 // FIXME: This should use ManagedStatic to manage the pass registrar.
 194 // Unfortunately, we can't do this, because passes are registered with static
 195 // ctors, and having llvm_shutdown clear this map prevents successful
 196 // ressurection after llvm_shutdown is run.
 197 static PassRegistrar *getPassRegistrar() {
 198   static PassRegistrar *PassRegistrarObj = 0;
 199
 200   // Use double-checked locking to safely initialize the registrar when
 201   // we're running in multithreaded mode.
 202   PassRegistrar* tmp = PassRegistrarObj;
 203   if (llvm_is_multithreaded()) {
 204     sys::MemoryFence();
 205     if (!tmp) {
 206       llvm_acquire_global_lock();
 207       tmp = PassRegistrarObj;
 208       if (!tmp) {
 209         tmp = new PassRegistrar();
 210         sys::MemoryFence();
 211         PassRegistrarObj = tmp;
 212       }
 213       llvm_release_global_lock();
 214     }
 215   } else if (!tmp) {
 216     PassRegistrarObj = new PassRegistrar();
 217   }
 218
 219   return PassRegistrarObj;
 220 }
 221
 222 // getPassInfo - Return the PassInfo data structure that corresponds to this
 223 // pass...
 224 const PassInfo *Pass::getPassInfo() const {
 225   return lookupPassInfo(PassID);
 226 }
 227
 228 const PassInfo *Pass::lookupPassInfo(intptr_t TI) {
 229   return getPassRegistrar()->GetPassInfo(TI);
 230 }
 231
 232 void PassInfo::registerPass() {
 233   getPassRegistrar()->RegisterPass(*this);
 234
 235   // Notify any listeners.
 236   sys::SmartScopedLock<true> Lock(&ListenersLock);
 237   if (Listeners)
 238     for (std::vector<PassRegistrationListener*>::iterator
 239            I = Listeners->begin(), E = Listeners->end(); I != E; ++I)
 240       (*I)->passRegistered(this);
 241 }
 242
 243 void PassInfo::unregisterPass() {
 244   getPassRegistrar()->UnregisterPass(*this);
 245 }
 246
 247 //===----------------------------------------------------------------------===//
 248 //                  Analysis Group Implementation Code
 249 //===----------------------------------------------------------------------===//
 250
 251 // RegisterAGBase implementation
 252 //
 253 RegisterAGBase::RegisterAGBase(const char *Name, intptr_t InterfaceID,
 254                                intptr_t PassID, bool isDefault)
 255   : PassInfo(Name, InterfaceID),
 256     ImplementationInfo(0), isDefaultImplementation(isDefault) {
 257
 258   InterfaceInfo = const_cast<PassInfo*>(Pass::lookupPassInfo(InterfaceID));
 259   if (InterfaceInfo == 0) {
 260     // First reference to Interface, register it now.
 261     registerPass();
 262     InterfaceInfo = this;
 263   }
 264   assert(isAnalysisGroup() &&
 265          "Trying to join an analysis group that is a normal pass!");
 266
 267   if (PassID) {
 268     ImplementationInfo = Pass::lookupPassInfo(PassID);
 269     assert(ImplementationInfo &&
 270            "Must register pass before adding to AnalysisGroup!");
 271
 272     // Make sure we keep track of the fact that the implementation implements
 273     // the interface.
 274     PassInfo *IIPI = const_cast<PassInfo*>(ImplementationInfo);
 275     IIPI->addInterfaceImplemented(InterfaceInfo);
 276
 277     getPassRegistrar()->RegisterAnalysisGroup(InterfaceInfo, IIPI, isDefault);
 278   }
 279 }
 280
 281
 282 //===----------------------------------------------------------------------===//
 283 // PassRegistrationListener implementation
 284 //
 285
 286 // PassRegistrationListener ctor - Add the current object to the list of
 287 // PassRegistrationListeners...
 288 PassRegistrationListener::PassRegistrationListener() {
 289   sys::SmartScopedLock<true> Lock(&ListenersLock);
 290   if (!Listeners) Listeners = new std::vector<PassRegistrationListener*>();
 291   Listeners->push_back(this);
 292 }
 293
 294 // dtor - Remove object from list of listeners...
 295 PassRegistrationListener::~PassRegistrationListener() {
 296   sys::SmartScopedLock<true> Lock(&ListenersLock);
 297   std::vector<PassRegistrationListener*>::iterator I =
 298     std::find(Listeners->begin(), Listeners->end(), this);
 299   assert(Listeners && I != Listeners->end() &&
 300          "PassRegistrationListener not registered!");
 301   Listeners->erase(I);
 302
 303   if (Listeners->empty()) {
 304     delete Listeners;
 305     Listeners = 0;
 306   }
 307 }
 308
 309 // enumeratePasses - Iterate over the registered passes, calling the
 310 // passEnumerate callback on each PassInfo object.
 311 //
 312 void PassRegistrationListener::enumeratePasses() {
 313   getPassRegistrar()->EnumerateWith(this);
 314 }
 315
 316 //===----------------------------------------------------------------------===//
 317 //   AnalysisUsage Class Implementation
 318 //
 319
 320 namespace {
 321   struct GetCFGOnlyPasses : public PassRegistrationListener {
 322     typedef AnalysisUsage::VectorType VectorType;
 323     VectorType &CFGOnlyList;
 324     GetCFGOnlyPasses(VectorType &L) : CFGOnlyList(L) {}
 325
 326     void passEnumerate(const PassInfo *P) {
 327       if (P->isCFGOnlyPass())
 328         CFGOnlyList.push_back(P);
 329     }
 330   };
 331 }
 332
 333 // setPreservesCFG - This function should be called to by the pass, iff they do
 334 // not:
 335 //
 336 //  1. Add or remove basic blocks from the function
 337 //  2. Modify terminator instructions in any way.
 338 //
 339 // This function annotates the AnalysisUsage info object to say that analyses
 340 // that only depend on the CFG are preserved by this pass.
 341 //
 342 void AnalysisUsage::setPreservesCFG() {
 343   // Since this transformation doesn't modify the CFG, it preserves all analyses
 344   // that only depend on the CFG (like dominators, loop info, etc...)
 345   GetCFGOnlyPasses(Preserved).enumeratePasses();
 346 }
 347
 348