LLVM  15.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 
11 #include "llvm/Analysis/LoopInfo.h"
14 #include "llvm/IR/Dominators.h"
16 
17 using namespace llvm;
18 
19 namespace llvm {
20 // Explicit template instantiations and specialization definitions for core
21 // template typedefs.
22 template class AllAnalysesOn<Loop>;
27 
29  Function &F, const PreservedAnalyses &PA,
31  // First compute the sequence of IR units covered by this proxy. We will want
32  // to visit this in postorder, but because this is a tree structure we can do
33  // this by building a preorder sequence and walking it backwards. We also
34  // want siblings in forward program order to match the LoopPassManager so we
35  // get the preorder with siblings reversed.
36  SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder();
37 
38  // If this proxy or the loop info is going to be invalidated, we also need
39  // to clear all the keys coming from that analysis. We also completely blow
40  // away the loop analyses if any of the standard analyses provided by the
41  // loop pass manager go away so that loop analyses can freely use these
42  // without worrying about declaring dependencies on them etc.
43  // FIXME: It isn't clear if this is the right tradeoff. We could instead make
44  // loop analyses declare any dependencies on these and use the more general
45  // invalidation logic below to act on that.
47  bool invalidateMemorySSAAnalysis = false;
48  if (MSSAUsed)
49  invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
50  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
51  Inv.invalidate<AAManager>(F, PA) ||
52  Inv.invalidate<AssumptionAnalysis>(F, PA) ||
54  Inv.invalidate<LoopAnalysis>(F, PA) ||
56  invalidateMemorySSAAnalysis) {
57  // Note that the LoopInfo may be stale at this point, however the loop
58  // objects themselves remain the only viable keys that could be in the
59  // analysis manager's cache. So we just walk the keys and forcibly clear
60  // those results. Note that the order doesn't matter here as this will just
61  // directly destroy the results without calling methods on them.
62  for (Loop *L : PreOrderLoops) {
63  // NB! `L` may not be in a good enough state to run Loop::getName.
64  InnerAM->clear(*L, "<possibly invalidated loop>");
65  }
66 
67  // We also need to null out the inner AM so that when the object gets
68  // destroyed as invalid we don't try to clear the inner AM again. At that
69  // point we won't be able to reliably walk the loops for this function and
70  // only clear results associated with those loops the way we do here.
71  // FIXME: Making InnerAM null at this point isn't very nice. Most analyses
72  // try to remain valid during invalidation. Maybe we should add an
73  // `IsClean` flag?
74  InnerAM = nullptr;
75 
76  // Now return true to indicate this *is* invalid and a fresh proxy result
77  // needs to be built. This is especially important given the null InnerAM.
78  return true;
79  }
80 
81  // Directly check if the relevant set is preserved so we can short circuit
82  // invalidating loops.
83  bool AreLoopAnalysesPreserved =
85 
86  // Since we have a valid LoopInfo we can actually leave the cached results in
87  // the analysis manager associated with the Loop keys, but we need to
88  // propagate any necessary invalidation logic into them. We'd like to
89  // invalidate things in roughly the same order as they were put into the
90  // cache and so we walk the preorder list in reverse to form a valid
91  // postorder.
92  for (Loop *L : reverse(PreOrderLoops)) {
94 
95  // Check to see whether the preserved set needs to be adjusted based on
96  // function-level analysis invalidation triggering deferred invalidation
97  // for this loop.
98  if (auto *OuterProxy =
99  InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))
100  for (const auto &OuterInvalidationPair :
101  OuterProxy->getOuterInvalidations()) {
102  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
103  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
104  if (Inv.invalidate(OuterAnalysisID, F, PA)) {
105  if (!InnerPA)
106  InnerPA = PA;
107  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
108  InnerPA->abandon(InnerAnalysisID);
109  }
110  }
111 
112  // Check if we needed a custom PA set. If so we'll need to run the inner
113  // invalidation.
114  if (InnerPA) {
115  InnerAM->invalidate(*L, *InnerPA);
116  continue;
117  }
118 
119  // Otherwise we only need to do invalidation if the original PA set didn't
120  // preserve all Loop analyses.
121  if (!AreLoopAnalysesPreserved)
122  InnerAM->invalidate(*L, PA);
123  }
124 
125  // Return false to indicate that this result is still a valid proxy.
126  return false;
127 }
128 
129 template <>
133  return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
134 }
135 }
136 
140  PA.preserve<LoopAnalysis>();
143  return PA;
144 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1062
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1303
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2123
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
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:780
llvm::Function
Definition: Function.h:60
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:685
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::InnerAnalysisManagerProxy::Result
Definition: PassManager.h:941
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::PreservedAnalyses::abandon
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:206
ScalarEvolution.h
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::Optional
Definition: APInt.h:33
F
#define F(x, y, z)
Definition: MD5.cpp:55
LoopAnalysisManager.h
PassManagerImpl.h
llvm::MemorySSAAnalysis::Result
Definition: MemorySSA.h:957
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:667
LoopInfo.h
llvm::getLoopPassPreservedAnalyses
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
Definition: LoopAnalysisManager.cpp:137
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:173
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
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:335
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:948
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
MemorySSA.h
llvm::FunctionAnalysisManager
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:918
Dominators.h
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:937
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:1000
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262