lib/IR/PassManager.cpp

   1 //===- PassManager.cpp - Infrastructure for managing & running IR passes --===//
   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 #include "llvm/ADT/STLExtras.h"
  11 #include "llvm/IR/LLVMContext.h"
  12 #include "llvm/IR/PassManager.h"
  13 #include "llvm/Support/CommandLine.h"
  14 #include "llvm/Support/Debug.h"
  15
  16 using namespace llvm;
  17
  18 static cl::opt<bool>
  19     DebugPM("debug-pass-manager", cl::Hidden,
  20             cl::desc("Print pass management debugging information"));
  21
  22 PreservedAnalyses ModulePassManager::run(Module &M, ModuleAnalysisManager *AM) {
  23   PreservedAnalyses PA = PreservedAnalyses::all();
  24
  25   if (DebugPM)
  26     dbgs() << "Starting module pass manager run.\n";
  27
  28   for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
  29     if (DebugPM)
  30       dbgs() << "Running module pass: " << Passes[Idx]->name() << "\n";
  31
  32     PreservedAnalyses PassPA = Passes[Idx]->run(M, AM);
  33
  34     // If we have an active analysis manager at this level we want to ensure we
  35     // update it as each pass runs and potentially invalidates analyses. We
  36     // also update the preserved set of analyses based on what analyses we have
  37     // already handled the invalidation for here and don't need to invalidate
  38     // when finished.
  39     if (AM)
  40       PassPA = AM->invalidate(M, std::move(PassPA));
  41
  42     // Finally, we intersect the final preserved analyses to compute the
  43     // aggregate preserved set for this pass manager.
  44     PA.intersect(std::move(PassPA));
  45
  46     M.getContext().yield();
  47   }
  48
  49   if (DebugPM)
  50     dbgs() << "Finished module pass manager run.\n";
  51
  52   return PA;
  53 }
  54
  55 ModuleAnalysisManager::ResultConceptT &
  56 ModuleAnalysisManager::getResultImpl(void *PassID, Module &M) {
  57   ModuleAnalysisResultMapT::iterator RI;
  58   bool Inserted;
  59   std::tie(RI, Inserted) = ModuleAnalysisResults.insert(std::make_pair(
  60       PassID, std::unique_ptr<detail::AnalysisResultConcept<Module &>>()));
  61
  62   // If we don't have a cached result for this module, look up the pass and run
  63   // it to produce a result, which we then add to the cache.
  64   if (Inserted) {
  65     auto &P = lookupPass(PassID);
  66     if (DebugPM)
  67       dbgs() << "Running module analysis: " << P.name() << "\n";
  68     RI->second = P.run(M, this);
  69   }
  70
  71   return *RI->second;
  72 }
  73
  74 ModuleAnalysisManager::ResultConceptT *
  75 ModuleAnalysisManager::getCachedResultImpl(void *PassID, Module &M) const {
  76   ModuleAnalysisResultMapT::const_iterator RI =
  77       ModuleAnalysisResults.find(PassID);
  78   return RI == ModuleAnalysisResults.end() ? nullptr : &*RI->second;
  79 }
  80
  81 void ModuleAnalysisManager::invalidateImpl(void *PassID, Module &M) {
  82   if (DebugPM)
  83     dbgs() << "Invalidating module analysis: " << lookupPass(PassID).name()
  84            << "\n";
  85   ModuleAnalysisResults.erase(PassID);
  86 }
  87
  88 PreservedAnalyses ModuleAnalysisManager::invalidateImpl(Module &M,
  89                                                         PreservedAnalyses PA) {
  90   // Short circuit for a common case of all analyses being preserved.
  91   if (PA.areAllPreserved())
  92     return std::move(PA);
  93
  94   if (DebugPM)
  95     dbgs() << "Invalidating all non-preserved analyses for module: "
  96            << M.getModuleIdentifier() << "\n";
  97
  98   // FIXME: This is a total hack based on the fact that erasure doesn't
  99   // invalidate iteration for DenseMap.
 100   for (ModuleAnalysisResultMapT::iterator I = ModuleAnalysisResults.begin(),
 101                                           E = ModuleAnalysisResults.end();
 102        I != E; ++I) {
 103     void *PassID = I->first;
 104
 105     // Pass the invalidation down to the pass itself to see if it thinks it is
 106     // necessary. The analysis pass can return false if no action on the part
 107     // of the analysis manager is required for this invalidation event.
 108     if (I->second->invalidate(M, PA)) {
 109       if (DebugPM)
 110         dbgs() << "Invalidating module analysis: "
 111                << lookupPass(PassID).name() << "\n";
 112
 113       ModuleAnalysisResults.erase(I);
 114     }
 115
 116     // After handling each pass, we mark it as preserved. Once we've
 117     // invalidated any stale results, the rest of the system is allowed to
 118     // start preserving this analysis again.
 119     PA.preserve(PassID);
 120   }
 121
 122   return std::move(PA);
 123 }
 124
 125 PreservedAnalyses FunctionPassManager::run(Function &F,
 126                                            FunctionAnalysisManager *AM) {
 127   PreservedAnalyses PA = PreservedAnalyses::all();
 128
 129   if (DebugPM)
 130     dbgs() << "Starting function pass manager run.\n";
 131
 132   for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
 133     if (DebugPM)
 134       dbgs() << "Running function pass: " << Passes[Idx]->name() << "\n";
 135
 136     PreservedAnalyses PassPA = Passes[Idx]->run(F, AM);
 137
 138     // If we have an active analysis manager at this level we want to ensure we
 139     // update it as each pass runs and potentially invalidates analyses. We
 140     // also update the preserved set of analyses based on what analyses we have
 141     // already handled the invalidation for here and don't need to invalidate
 142     // when finished.
 143     if (AM)
 144       PassPA = AM->invalidate(F, std::move(PassPA));
 145
 146     // Finally, we intersect the final preserved analyses to compute the
 147     // aggregate preserved set for this pass manager.
 148     PA.intersect(std::move(PassPA));
 149
 150     F.getContext().yield();
 151   }
 152
 153   if (DebugPM)
 154     dbgs() << "Finished function pass manager run.\n";
 155
 156   return PA;
 157 }
 158
 159 bool FunctionAnalysisManager::empty() const {
 160   assert(FunctionAnalysisResults.empty() ==
 161              FunctionAnalysisResultLists.empty() &&
 162          "The storage and index of analysis results disagree on how many there "
 163          "are!");
 164   return FunctionAnalysisResults.empty();
 165 }
 166
 167 void FunctionAnalysisManager::clear() {
 168   FunctionAnalysisResults.clear();
 169   FunctionAnalysisResultLists.clear();
 170 }
 171
 172 FunctionAnalysisManager::ResultConceptT &
 173 FunctionAnalysisManager::getResultImpl(void *PassID, Function &F) {
 174   FunctionAnalysisResultMapT::iterator RI;
 175   bool Inserted;
 176   std::tie(RI, Inserted) = FunctionAnalysisResults.insert(std::make_pair(
 177       std::make_pair(PassID, &F), FunctionAnalysisResultListT::iterator()));
 178
 179   // If we don't have a cached result for this function, look up the pass and
 180   // run it to produce a result, which we then add to the cache.
 181   if (Inserted) {
 182     auto &P = lookupPass(PassID);
 183     if (DebugPM)
 184       dbgs() << "Running function analysis: " << P.name() << "\n";
 185     FunctionAnalysisResultListT &ResultList = FunctionAnalysisResultLists[&F];
 186     ResultList.emplace_back(PassID, P.run(F, this));
 187     RI->second = std::prev(ResultList.end());
 188   }
 189
 190   return *RI->second->second;
 191 }
 192
 193 FunctionAnalysisManager::ResultConceptT *
 194 FunctionAnalysisManager::getCachedResultImpl(void *PassID, Function &F) const {
 195   FunctionAnalysisResultMapT::const_iterator RI =
 196       FunctionAnalysisResults.find(std::make_pair(PassID, &F));
 197   return RI == FunctionAnalysisResults.end() ? nullptr : &*RI->second->second;
 198 }
 199
 200 void FunctionAnalysisManager::invalidateImpl(void *PassID, Function &F) {
 201   FunctionAnalysisResultMapT::iterator RI =
 202       FunctionAnalysisResults.find(std::make_pair(PassID, &F));
 203   if (RI == FunctionAnalysisResults.end())
 204     return;
 205
 206   if (DebugPM)
 207     dbgs() << "Invalidating function analysis: " << lookupPass(PassID).name()
 208            << "\n";
 209   FunctionAnalysisResultLists[&F].erase(RI->second);
 210   FunctionAnalysisResults.erase(RI);
 211 }
 212
 213 PreservedAnalyses
 214 FunctionAnalysisManager::invalidateImpl(Function &F, PreservedAnalyses PA) {
 215   // Short circuit for a common case of all analyses being preserved.
 216   if (PA.areAllPreserved())
 217     return std::move(PA);
 218
 219   if (DebugPM)
 220     dbgs() << "Invalidating all non-preserved analyses for function: "
 221            << F.getName() << "\n";
 222
 223   // Clear all the invalidated results associated specifically with this
 224   // function.
 225   SmallVector<void *, 8> InvalidatedPassIDs;
 226   FunctionAnalysisResultListT &ResultsList = FunctionAnalysisResultLists[&F];
 227   for (FunctionAnalysisResultListT::iterator I = ResultsList.begin(),
 228                                              E = ResultsList.end();
 229        I != E;) {
 230     void *PassID = I->first;
 231
 232     // Pass the invalidation down to the pass itself to see if it thinks it is
 233     // necessary. The analysis pass can return false if no action on the part
 234     // of the analysis manager is required for this invalidation event.
 235     if (I->second->invalidate(F, PA)) {
 236       if (DebugPM)
 237         dbgs() << "Invalidating function analysis: "
 238                << lookupPass(PassID).name() << "\n";
 239
 240       InvalidatedPassIDs.push_back(I->first);
 241       I = ResultsList.erase(I);
 242     } else {
 243       ++I;
 244     }
 245
 246     // After handling each pass, we mark it as preserved. Once we've
 247     // invalidated any stale results, the rest of the system is allowed to
 248     // start preserving this analysis again.
 249     PA.preserve(PassID);
 250   }
 251   while (!InvalidatedPassIDs.empty())
 252     FunctionAnalysisResults.erase(
 253         std::make_pair(InvalidatedPassIDs.pop_back_val(), &F));
 254   if (ResultsList.empty())
 255     FunctionAnalysisResultLists.erase(&F);
 256
 257   return std::move(PA);
 258 }
 259
 260 char FunctionAnalysisManagerModuleProxy::PassID;
 261
 262 FunctionAnalysisManagerModuleProxy::Result
 263 FunctionAnalysisManagerModuleProxy::run(Module &M) {
 264   assert(FAM->empty() && "Function analyses ran prior to the module proxy!");
 265   return Result(*FAM);
 266 }
 267
 268 FunctionAnalysisManagerModuleProxy::Result::~Result() {
 269   // Clear out the analysis manager if we're being destroyed -- it means we
 270   // didn't even see an invalidate call when we got invalidated.
 271   FAM->clear();
 272 }
 273
 274 bool FunctionAnalysisManagerModuleProxy::Result::invalidate(
 275     Module &M, const PreservedAnalyses &PA) {
 276   // If this proxy isn't marked as preserved, then we can't even invalidate
 277   // individual function analyses, there may be an invalid set of Function
 278   // objects in the cache making it impossible to incrementally preserve them.
 279   // Just clear the entire manager.
 280   if (!PA.preserved(ID()))
 281     FAM->clear();
 282
 283   // Return false to indicate that this result is still a valid proxy.
 284   return false;
 285 }
 286
 287 char ModuleAnalysisManagerFunctionProxy::PassID;