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