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