lib/Analysis/LoopAnalysisManager.cpp

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