contrib/llvm/lib/Analysis/LoopAnalysisManager.cpp

   1 //===- LoopAnalysisManager.cpp - Loop analysis management -----------------===//
   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/Analysis/LoopAnalysisManager.h"
  11 #include "llvm/Analysis/BasicAliasAnalysis.h"
  12 #include "llvm/Analysis/GlobalsModRef.h"
  13 #include "llvm/Analysis/LoopInfo.h"
  14 #include "llvm/Analysis/ScalarEvolution.h"
  15 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
  16 #include "llvm/IR/Dominators.h"
  17
  18 using namespace llvm;
  19
  20 // Explicit template instantiations and specialization defininitions for core
  21 // template typedefs.
  22 namespace llvm {
  23 template class AllAnalysesOn<Loop>;
  24 template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
  25 template class InnerAnalysisManagerProxy<LoopAnalysisManager, Function>;
  26 template class OuterAnalysisManagerProxy<FunctionAnalysisManager, Loop,
  27                                          LoopStandardAnalysisResults &>;
  28
  29 bool LoopAnalysisManagerFunctionProxy::Result::invalidate(
  30     Function &F, const PreservedAnalyses &PA,
  31     FunctionAnalysisManager::Invalidator &Inv) {
  32   // First compute the sequence of IR units covered by this proxy. We will want
  33   // to visit this in postorder, but because this is a tree structure we can do
  34   // this by building a preorder sequence and walking it in reverse.
  35   SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
  36   // Note that we want to walk the roots in reverse order because we will end
  37   // up reversing the preorder sequence. However, it happens that the loop nest
  38   // roots are in reverse order within the LoopInfo object. So we just walk
  39   // forward here.
  40   // FIXME: If we change the order of LoopInfo we will want to add a reverse
  41   // here.
  42   for (Loop *RootL : *LI) {
  43     assert(PreOrderWorklist.empty() &&
  44            "Must start with an empty preorder walk worklist.");
  45     PreOrderWorklist.push_back(RootL);
  46     do {
  47       Loop *L = PreOrderWorklist.pop_back_val();
  48       PreOrderWorklist.append(L->begin(), L->end());
  49       PreOrderLoops.push_back(L);
  50     } while (!PreOrderWorklist.empty());
  51   }
  52
  53   // If this proxy or the loop info is going to be invalidated, we also need
  54   // to clear all the keys coming from that analysis. We also completely blow
  55   // away the loop analyses if any of the standard analyses provided by the
  56   // loop pass manager go away so that loop analyses can freely use these
  57   // without worrying about declaring dependencies on them etc.
  58   // FIXME: It isn't clear if this is the right tradeoff. We could instead make
  59   // loop analyses declare any dependencies on these and use the more general
  60   // invalidation logic below to act on that.
  61   auto PAC = PA.getChecker<LoopAnalysisManagerFunctionProxy>();
  62   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
  63       Inv.invalidate<AAManager>(F, PA) ||
  64       Inv.invalidate<AssumptionAnalysis>(F, PA) ||
  65       Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
  66       Inv.invalidate<LoopAnalysis>(F, PA) ||
  67       Inv.invalidate<ScalarEvolutionAnalysis>(F, PA)) {
  68     // Note that the LoopInfo may be stale at this point, however the loop
  69     // objects themselves remain the only viable keys that could be in the
  70     // analysis manager's cache. So we just walk the keys and forcibly clear
  71     // those results. Note that the order doesn't matter here as this will just
  72     // directly destroy the results without calling methods on them.
  73     for (Loop *L : PreOrderLoops)
  74       InnerAM->clear(*L);
  75
  76     // We also need to null out the inner AM so that when the object gets
  77     // destroyed as invalid we don't try to clear the inner AM again. At that
  78     // point we won't be able to reliably walk the loops for this function and
  79     // only clear results associated with those loops the way we do here.
  80     // FIXME: Making InnerAM null at this point isn't very nice. Most analyses
  81     // try to remain valid during invalidation. Maybe we should add an
  82     // `IsClean` flag?
  83     InnerAM = nullptr;
  84
  85     // Now return true to indicate this *is* invalid and a fresh proxy result
  86     // needs to be built. This is especially important given the null InnerAM.
  87     return true;
  88   }
  89
  90   // Directly check if the relevant set is preserved so we can short circuit
  91   // invalidating loops.
  92   bool AreLoopAnalysesPreserved =
  93       PA.allAnalysesInSetPreserved<AllAnalysesOn<Loop>>();
  94
  95   // Since we have a valid LoopInfo we can actually leave the cached results in
  96   // the analysis manager associated with the Loop keys, but we need to
  97   // propagate any necessary invalidation logic into them. We'd like to
  98   // invalidate things in roughly the same order as they were put into the
  99   // cache and so we walk the preorder list in reverse to form a valid
 100   // postorder.
 101   for (Loop *L : reverse(PreOrderLoops)) {
 102     Optional<PreservedAnalyses> InnerPA;
 103
 104     // Check to see whether the preserved set needs to be adjusted based on
 105     // function-level analysis invalidation triggering deferred invalidation
 106     // for this loop.
 107     if (auto *OuterProxy =
 108             InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))
 109       for (const auto &OuterInvalidationPair :
 110            OuterProxy->getOuterInvalidations()) {
 111         AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
 112         const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
 113         if (Inv.invalidate(OuterAnalysisID, F, PA)) {
 114           if (!InnerPA)
 115             InnerPA = PA;
 116           for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
 117             InnerPA->abandon(InnerAnalysisID);
 118         }
 119       }
 120
 121     // Check if we needed a custom PA set. If so we'll need to run the inner
 122     // invalidation.
 123     if (InnerPA) {
 124       InnerAM->invalidate(*L, *InnerPA);
 125       continue;
 126     }
 127
 128     // Otherwise we only need to do invalidation if the original PA set didn't
 129     // preserve all Loop analyses.
 130     if (!AreLoopAnalysesPreserved)
 131       InnerAM->invalidate(*L, PA);
 132   }
 133
 134   // Return false to indicate that this result is still a valid proxy.
 135   return false;
 136 }
 137
 138 template <>
 139 LoopAnalysisManagerFunctionProxy::Result
 140 LoopAnalysisManagerFunctionProxy::run(Function &F,
 141                                       FunctionAnalysisManager &AM) {
 142   return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
 143 }
 144 }
 145
 146 PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
 147   PreservedAnalyses PA;
 148   PA.preserve<AssumptionAnalysis>();
 149   PA.preserve<DominatorTreeAnalysis>();
 150   PA.preserve<LoopAnalysis>();
 151   PA.preserve<LoopAnalysisManagerFunctionProxy>();
 152   PA.preserve<ScalarEvolutionAnalysis>();
 153   // TODO: What we really want to do here is preserve an AA category, but that
 154   // concept doesn't exist yet.
 155   PA.preserve<AAManager>();
 156   PA.preserve<BasicAA>();
 157   PA.preserve<GlobalsAA>();
 158   PA.preserve<SCEVAA>();
 159   return PA;
 160 }