• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
invalidate(Function & F,const PreservedAnalyses & PA,FunctionAnalysisManager::Invalidator & Inv)35 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   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   if (EnableMSSALoopDependency)
56     invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
57   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
58       Inv.invalidate<AAManager>(F, PA) ||
59       Inv.invalidate<AssumptionAnalysis>(F, PA) ||
60       Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||
61       Inv.invalidate<LoopAnalysis>(F, PA) ||
62       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     for (Loop *L : PreOrderLoops) {
70       // NB! `L` may not be in a good enough state to run Loop::getName.
71       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     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     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   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             InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))
107       for (const auto &OuterInvalidationPair :
108            OuterProxy->getOuterInvalidations()) {
109         AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
110         const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
111         if (Inv.invalidate(OuterAnalysisID, F, PA)) {
112           if (!InnerPA)
113             InnerPA = PA;
114           for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
115             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     if (InnerPA) {
122       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     if (!AreLoopAnalysesPreserved)
129       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
run(Function & F,FunctionAnalysisManager & AM)138 LoopAnalysisManagerFunctionProxy::run(Function &F,
139                                       FunctionAnalysisManager &AM) {
140   return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
141 }
142 }
143 
getLoopPassPreservedAnalyses()144 PreservedAnalyses llvm::getLoopPassPreservedAnalyses() {
145   PreservedAnalyses PA;
146   PA.preserve<DominatorTreeAnalysis>();
147   PA.preserve<LoopAnalysis>();
148   PA.preserve<LoopAnalysisManagerFunctionProxy>();
149   PA.preserve<ScalarEvolutionAnalysis>();
150   // FIXME: Uncomment this when all loop passes preserve MemorySSA
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   return PA;
159 }
160