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