LLVM  9.0.0svn
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 //===----------------------------------------------------------------------===//
12 #include "llvm/Analysis/LoopInfo.h"
16 #include "llvm/IR/Dominators.h"
18 using namespace llvm;
20 namespace llvm {
21 /// Enables memory ssa as a dependency for loop passes in legacy pass manager.
23  "enable-mssa-loop-dependency", cl::Hidden, cl::init(false),
24  cl::desc("Enable MemorySSA dependency for loop pass manager"));
26 // Explicit template instantiations and specialization definitions for core
27 // template typedefs.
28 template class AllAnalysesOn<Loop>;
35  Function &F, const PreservedAnalyses &PA,
37  // First compute the sequence of IR units covered by this proxy. We will want
38  // to visit this in postorder, but because this is a tree structure we can do
39  // this by building a preorder sequence and walking it backwards. We also
40  // want siblings in forward program order to match the LoopPassManager so we
41  // get the preorder with siblings reversed.
42  SmallVector<Loop *, 4> PreOrderLoops = LI->getLoopsInReverseSiblingPreorder();
44  // If this proxy or the loop info is going to be invalidated, we also need
45  // to clear all the keys coming from that analysis. We also completely blow
46  // away the loop analyses if any of the standard analyses provided by the
47  // loop pass manager go away so that loop analyses can freely use these
48  // without worrying about declaring dependencies on them etc.
49  // FIXME: It isn't clear if this is the right tradeoff. We could instead make
50  // loop analyses declare any dependencies on these and use the more general
51  // invalidation logic below to act on that.
53  bool invalidateMemorySSAAnalysis = false;
55  invalidateMemorySSAAnalysis = Inv.invalidate<MemorySSAAnalysis>(F, PA);
56  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||
57  Inv.invalidate<AAManager>(F, PA) ||
58  Inv.invalidate<AssumptionAnalysis>(F, PA) ||
60  Inv.invalidate<LoopAnalysis>(F, PA) ||
62  invalidateMemorySSAAnalysis) {
63  // Note that the LoopInfo may be stale at this point, however the loop
64  // objects themselves remain the only viable keys that could be in the
65  // analysis manager's cache. So we just walk the keys and forcibly clear
66  // those results. Note that the order doesn't matter here as this will just
67  // directly destroy the results without calling methods on them.
68  for (Loop *L : PreOrderLoops) {
69  // NB! `L` may not be in a good enough state to run Loop::getName.
70  InnerAM->clear(*L, "<possibly invalidated loop>");
71  }
73  // We also need to null out the inner AM so that when the object gets
74  // destroyed as invalid we don't try to clear the inner AM again. At that
75  // point we won't be able to reliably walk the loops for this function and
76  // only clear results associated with those loops the way we do here.
77  // FIXME: Making InnerAM null at this point isn't very nice. Most analyses
78  // try to remain valid during invalidation. Maybe we should add an
79  // `IsClean` flag?
80  InnerAM = nullptr;
82  // Now return true to indicate this *is* invalid and a fresh proxy result
83  // needs to be built. This is especially important given the null InnerAM.
84  return true;
85  }
87  // Directly check if the relevant set is preserved so we can short circuit
88  // invalidating loops.
89  bool AreLoopAnalysesPreserved =
92  // Since we have a valid LoopInfo we can actually leave the cached results in
93  // the analysis manager associated with the Loop keys, but we need to
94  // propagate any necessary invalidation logic into them. We'd like to
95  // invalidate things in roughly the same order as they were put into the
96  // cache and so we walk the preorder list in reverse to form a valid
97  // postorder.
98  for (Loop *L : reverse(PreOrderLoops)) {
101  // Check to see whether the preserved set needs to be adjusted based on
102  // function-level analysis invalidation triggering deferred invalidation
103  // for this loop.
104  if (auto *OuterProxy =
105  InnerAM->getCachedResult<FunctionAnalysisManagerLoopProxy>(*L))
106  for (const auto &OuterInvalidationPair :
107  OuterProxy->getOuterInvalidations()) {
108  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
109  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
110  if (Inv.invalidate(OuterAnalysisID, F, PA)) {
111  if (!InnerPA)
112  InnerPA = PA;
113  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
114  InnerPA->abandon(InnerAnalysisID);
115  }
116  }
118  // Check if we needed a custom PA set. If so we'll need to run the inner
119  // invalidation.
120  if (InnerPA) {
121  InnerAM->invalidate(*L, *InnerPA);
122  continue;
123  }
125  // Otherwise we only need to do invalidation if the original PA set didn't
126  // preserve all Loop analyses.
127  if (!AreLoopAnalysesPreserved)
128  InnerAM->invalidate(*L, PA);
129  }
131  // Return false to indicate that this result is still a valid proxy.
132  return false;
133 }
135 template <>
138  FunctionAnalysisManager &AM) {
139  return Result(*InnerAM, AM.getResult<LoopAnalysis>(F));
140 }
141 }
146  PA.preserve<LoopAnalysis>();
151  // FIXME: What we really want to do here is preserve an AA category, but that
152  // concept doesn't exist yet.
153  PA.preserve<AAManager>();
154  PA.preserve<BasicAA>();
155  PA.preserve<GlobalsAA>();
156  PA.preserve<SCEVAA>();
157  return PA;
158 }
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:207
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:659
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:304
This is the interface for a SCEV-based alias analysis.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:949
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:266
This header provides classes for managing per-loop analyses.
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:427
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
A manager for alias analyses.
Analysis pass providing a never-invalidated alias analysis result.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
Definition: PassManager.h:1018
Analysis pass providing a never-invalidated alias analysis result.
A function analysis which provides an AssumptionCache.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1153
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1100
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:921
Result(AnalysisManagerT &InnerAM)
Definition: PassManager.h:1043
Analysis pass that exposes the ScalarEvolution for a function.
Analysis pass providing a never-invalidated alias analysis result.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:464
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:641
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:329
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1037
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.