LLVM  13.0.0git
LoopAnalysisManager.cpp
Go to the documentation of this file.
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 
13 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/IR/Dominators.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>;
30 
32  Function &F, const PreservedAnalyses &PA,
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.
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) ||
57  Inv.invalidate<LoopAnalysis>(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 =
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)) {
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 <>
136  return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
137 }
138 }
139 
143  PA.preserve<LoopAnalysis>();
146  return PA;
147 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1051
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2105
llvm
Definition: AllocatorList.h:23
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
llvm::Function
Definition: Function.h:61
llvm::AnalysisManager::Invalidator::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:674
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
llvm::InnerAnalysisManagerProxy::Result
Definition: PassManager.h:930
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
llvm::PreservedAnalyses::abandon
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:209
GlobalsModRef.h
ScalarEvolution.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::Optional
Definition: APInt.h:33
BasicAliasAnalysis.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
LoopAnalysisManager.h
PassManagerImpl.h
llvm::MemorySSAAnalysis::Result
Definition: MemorySSA.h:931
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:656
LoopInfo.h
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:140
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:72
llvm::InnerAnalysisManagerProxy::Result::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
llvm::PreservedAnalyses::allAnalysesInSetPreserved
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:338
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:922
ScalarEvolutionAliasAnalysis.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
MemorySSA.h
llvm::FunctionAnalysisManager
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:907
Dominators.h
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:926
llvm::InnerAnalysisManagerProxy::run
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:989
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1233