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