1//===- LoopPassManager.cpp - Loop pass 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/Transforms/Scalar/LoopPassManager.h"
10#include "llvm/Analysis/AssumptionCache.h"
11#include "llvm/Analysis/BlockFrequencyInfo.h"
12#include "llvm/Analysis/BranchProbabilityInfo.h"
13#include "llvm/Analysis/MemorySSA.h"
14#include "llvm/Analysis/ScalarEvolution.h"
15#include "llvm/Analysis/TargetLibraryInfo.h"
16#include "llvm/Analysis/TargetTransformInfo.h"
17
18using namespace llvm;
19
20namespace llvm {
21
22/// Explicitly specialize the pass manager's run method to handle loop nest
23/// structure updates.
24PreservedAnalyses
25PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
26 LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,
27 LoopStandardAnalysisResults &AR, LPMUpdater &U) {
28 // Runs loop-nest passes only when the current loop is a top-level one.
29 PreservedAnalyses PA = (L.isOutermost() && !LoopNestPasses.empty())
30 ? runWithLoopNestPasses(L, AM, AR, U)
31 : runWithoutLoopNestPasses(L, AM, AR, U);
32
33 // Invalidation for the current loop should be handled above, and other loop
34 // analysis results shouldn't be impacted by runs over this loop. Therefore,
35 // the remaining analysis results in the AnalysisManager are preserved. We
36 // mark this with a set so that we don't need to inspect each one
37 // individually.
38 // FIXME: This isn't correct! This loop and all nested loops' analyses should
39 // be preserved, but unrolling should invalidate the parent loop's analyses.
40 PA.preserveSet<AllAnalysesOn<Loop>>();
41
42 return PA;
43}
44
45void PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
46 LPMUpdater &>::printPipeline(raw_ostream &OS,
47 function_ref<StringRef(StringRef)>
48 MapClassName2PassName) {
49 assert(LoopPasses.size() + LoopNestPasses.size() == IsLoopNestPass.size());
50
51 unsigned IdxLP = 0, IdxLNP = 0;
52 for (unsigned Idx = 0, Size = IsLoopNestPass.size(); Idx != Size; ++Idx) {
53 if (IsLoopNestPass[Idx]) {
54 auto *P = LoopNestPasses[IdxLNP++].get();
55 P->printPipeline(OS, MapClassName2PassName);
56 } else {
57 auto *P = LoopPasses[IdxLP++].get();
58 P->printPipeline(OS, MapClassName2PassName);
59 }
60 if (Idx + 1 < Size)
61 OS << ',';
62 }
63}
64
65// Run both loop passes and loop-nest passes on top-level loop \p L.
66PreservedAnalyses
67LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
68 LoopStandardAnalysisResults &AR,
69 LPMUpdater &U) {
70 assert(L.isOutermost() &&
71 "Loop-nest passes should only run on top-level loops.");
72 PreservedAnalyses PA = PreservedAnalyses::all();
73
74 // Request PassInstrumentation from analysis manager, will use it to run
75 // instrumenting callbacks for the passes later.
76 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(IR&: L, ExtraArgs&: AR);
77
78 unsigned LoopPassIndex = 0, LoopNestPassIndex = 0;
79
80 // `LoopNestPtr` points to the `LoopNest` object for the current top-level
81 // loop and `IsLoopNestPtrValid` indicates whether the pointer is still valid.
82 // The `LoopNest` object will have to be re-constructed if the pointer is
83 // invalid when encountering a loop-nest pass.
84 std::unique_ptr<LoopNest> LoopNestPtr;
85 bool IsLoopNestPtrValid = false;
86 Loop *OuterMostLoop = &L;
87
88 for (size_t I = 0, E = IsLoopNestPass.size(); I != E; ++I) {
89 std::optional<PreservedAnalyses> PassPA;
90 if (!IsLoopNestPass[I]) {
91 // The `I`-th pass is a loop pass.
92 auto &Pass = LoopPasses[LoopPassIndex++];
93 PassPA = runSinglePass(IR&: L, Pass, AM, AR, U, PI);
94 } else {
95 // The `I`-th pass is a loop-nest pass.
96 auto &Pass = LoopNestPasses[LoopNestPassIndex++];
97
98 // If the loop-nest object calculated before is no longer valid,
99 // re-calculate it here before running the loop-nest pass.
100 //
101 // FIXME: PreservedAnalysis should not be abused to tell if the
102 // status of loopnest has been changed. We should use and only
103 // use LPMUpdater for this purpose.
104 if (!IsLoopNestPtrValid || U.isLoopNestChanged()) {
105 while (auto *ParentLoop = OuterMostLoop->getParentLoop())
106 OuterMostLoop = ParentLoop;
107 LoopNestPtr = LoopNest::getLoopNest(Root&: *OuterMostLoop, SE&: AR.SE);
108 IsLoopNestPtrValid = true;
109 U.markLoopNestChanged(Changed: false);
110 }
111
112 PassPA = runSinglePass(IR&: *LoopNestPtr, Pass, AM, AR, U, PI);
113 }
114
115 // `PassPA` is `None` means that the before-pass callbacks in
116 // `PassInstrumentation` return false. The pass does not run in this case,
117 // so we can skip the following procedure.
118 if (!PassPA)
119 continue;
120
121 // If the loop was deleted, abort the run and return to the outer walk.
122 if (U.skipCurrentLoop()) {
123 PA.intersect(Arg: std::move(*PassPA));
124 break;
125 }
126
127 // Update the analysis manager as each pass runs and potentially
128 // invalidates analyses.
129 AM.invalidate(IR&: IsLoopNestPass[I] ? *OuterMostLoop : L, PA: *PassPA);
130
131 // Finally, we intersect the final preserved analyses to compute the
132 // aggregate preserved set for this pass manager.
133 PA.intersect(Arg: std::move(*PassPA));
134
135 // Check if the current pass preserved the loop-nest object or not.
136 IsLoopNestPtrValid &= PassPA->getChecker<LoopNestAnalysis>().preserved();
137
138 // After running the loop pass, the parent loop might change and we need to
139 // notify the updater, otherwise U.ParentL might gets outdated and triggers
140 // assertion failures in addSiblingLoops and addChildLoops.
141 U.setParentLoop((IsLoopNestPass[I] ? *OuterMostLoop : L).getParentLoop());
142 }
143 return PA;
144}
145
146// Run all loop passes on loop \p L. Loop-nest passes don't run either because
147// \p L is not a top-level one or simply because there are no loop-nest passes
148// in the pass manager at all.
149PreservedAnalyses
150LoopPassManager::runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM,
151 LoopStandardAnalysisResults &AR,
152 LPMUpdater &U) {
153 PreservedAnalyses PA = PreservedAnalyses::all();
154
155 // Request PassInstrumentation from analysis manager, will use it to run
156 // instrumenting callbacks for the passes later.
157 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(IR&: L, ExtraArgs&: AR);
158 for (auto &Pass : LoopPasses) {
159 std::optional<PreservedAnalyses> PassPA =
160 runSinglePass(IR&: L, Pass, AM, AR, U, PI);
161
162 // `PassPA` is `None` means that the before-pass callbacks in
163 // `PassInstrumentation` return false. The pass does not run in this case,
164 // so we can skip the following procedure.
165 if (!PassPA)
166 continue;
167
168 // If the loop was deleted, abort the run and return to the outer walk.
169 if (U.skipCurrentLoop()) {
170 PA.intersect(Arg: std::move(*PassPA));
171 break;
172 }
173
174 // Update the analysis manager as each pass runs and potentially
175 // invalidates analyses.
176 AM.invalidate(IR&: L, PA: *PassPA);
177
178 // Finally, we intersect the final preserved analyses to compute the
179 // aggregate preserved set for this pass manager.
180 PA.intersect(Arg: std::move(*PassPA));
181
182 // After running the loop pass, the parent loop might change and we need to
183 // notify the updater, otherwise U.ParentL might gets outdated and triggers
184 // assertion failures in addSiblingLoops and addChildLoops.
185 U.setParentLoop(L.getParentLoop());
186 }
187 return PA;
188}
189} // namespace llvm
190
191void FunctionToLoopPassAdaptor::printPipeline(
192 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
193 OS << (UseMemorySSA ? "loop-mssa(" : "loop(");
194 Pass->printPipeline(OS, MapClassName2PassName);
195 OS << ')';
196}
197PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
198 FunctionAnalysisManager &AM) {
199 // Before we even compute any loop analyses, first run a miniature function
200 // pass pipeline to put loops into their canonical form. Note that we can
201 // directly build up function analyses after this as the function pass
202 // manager handles all the invalidation at that layer.
203 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(IR&: F);
204
205 PreservedAnalyses PA = PreservedAnalyses::all();
206 // Check the PassInstrumentation's BeforePass callbacks before running the
207 // canonicalization pipeline.
208 if (PI.runBeforePass<Function>(Pass: LoopCanonicalizationFPM, IR: F)) {
209 PA = LoopCanonicalizationFPM.run(IR&: F, AM);
210 PI.runAfterPass<Function>(Pass: LoopCanonicalizationFPM, IR: F, PA);
211 }
212
213 // Get the loop structure for this function
214 LoopInfo &LI = AM.getResult<LoopAnalysis>(IR&: F);
215
216 // If there are no loops, there is nothing to do here.
217 if (LI.empty())
218 return PA;
219
220 // Get the analysis results needed by loop passes.
221 MemorySSA *MSSA =
222 UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(IR&: F).getMSSA()) : nullptr;
223 BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
224 ? (&AM.getResult<BlockFrequencyAnalysis>(IR&: F))
225 : nullptr;
226 BranchProbabilityInfo *BPI =
227 UseBranchProbabilityInfo && F.hasProfileData()
228 ? (&AM.getResult<BranchProbabilityAnalysis>(IR&: F))
229 : nullptr;
230 LoopStandardAnalysisResults LAR = {.AA: AM.getResult<AAManager>(IR&: F),
231 .AC: AM.getResult<AssumptionAnalysis>(IR&: F),
232 .DT: AM.getResult<DominatorTreeAnalysis>(IR&: F),
233 .LI: AM.getResult<LoopAnalysis>(IR&: F),
234 .SE: AM.getResult<ScalarEvolutionAnalysis>(IR&: F),
235 .TLI: AM.getResult<TargetLibraryAnalysis>(IR&: F),
236 .TTI: AM.getResult<TargetIRAnalysis>(IR&: F),
237 .BFI: BFI,
238 .BPI: BPI,
239 .MSSA: MSSA};
240
241 // Setup the loop analysis manager from its proxy. It is important that
242 // this is only done when there are loops to process and we have built the
243 // LoopStandardAnalysisResults object. The loop analyses cached in this
244 // manager have access to those analysis results and so it must invalidate
245 // itself when they go away.
246 auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(IR&: F);
247 if (UseMemorySSA)
248 LAMFP.markMSSAUsed();
249 LoopAnalysisManager &LAM = LAMFP.getManager();
250
251 // A postorder worklist of loops to process.
252 SmallPriorityWorklist<Loop *, 4> Worklist;
253
254 // Register the worklist and loop analysis manager so that loop passes can
255 // update them when they mutate the loop nest structure.
256 LPMUpdater Updater(Worklist, LAM, LoopNestMode);
257
258 // Add the loop nests in the reverse order of LoopInfo. See method
259 // declaration.
260 if (!LoopNestMode) {
261 appendLoopsToWorklist(LI, Worklist);
262 } else {
263 for (Loop *L : LI)
264 Worklist.insert(X: L);
265 }
266
267#ifndef NDEBUG
268 PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
269 if (isSpecialPass(PassID, {"PassManager"}))
270 return;
271 assert(llvm::any_cast<const Loop *>(&IR));
272 const Loop **LPtr = llvm::any_cast<const Loop *>(&IR);
273 const Loop *L = LPtr ? *LPtr : nullptr;
274 assert(L && "Loop should be valid for printing");
275
276 // Verify the loop structure and LCSSA form before visiting the loop.
277 L->verifyLoop();
278 assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
279 "Loops must remain in LCSSA form!");
280 });
281#endif
282
283 do {
284 Loop *L = Worklist.pop_back_val();
285 assert(!(LoopNestMode && L->getParentLoop()) &&
286 "L should be a top-level loop in loop-nest mode.");
287
288 // Reset the update structure for this loop.
289 Updater.CurrentL = L;
290 Updater.SkipCurrentLoop = false;
291
292#if LLVM_ENABLE_ABI_BREAKING_CHECKS
293 // Save a parent loop pointer for asserts.
294 Updater.ParentL = L->getParentLoop();
295#endif
296 // Check the PassInstrumentation's BeforePass callbacks before running the
297 // pass, skip its execution completely if asked to (callback returns
298 // false).
299 if (!PI.runBeforePass<Loop>(Pass: *Pass, IR: *L))
300 continue;
301
302 PreservedAnalyses PassPA = Pass->run(IR&: *L, AM&: LAM, ExtraArgs&: LAR, ExtraArgs&: Updater);
303
304 // Do not pass deleted Loop into the instrumentation.
305 if (Updater.skipCurrentLoop())
306 PI.runAfterPassInvalidated<Loop>(Pass: *Pass, PA: PassPA);
307 else
308 PI.runAfterPass<Loop>(Pass: *Pass, IR: *L, PA: PassPA);
309
310 if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())
311 reportFatalUsageError(reason: "Loop pass manager using MemorySSA contains a pass "
312 "that does not preserve MemorySSA");
313
314#ifndef NDEBUG
315 // LoopAnalysisResults should always be valid.
316 if (VerifyDomInfo)
317 LAR.DT.verify();
318 if (VerifyLoopInfo)
319 LAR.LI.verify(LAR.DT);
320 if (VerifySCEV)
321 LAR.SE.verify();
322 if (LAR.MSSA && VerifyMemorySSA)
323 LAR.MSSA->verifyMemorySSA();
324#endif
325
326 // If the loop hasn't been deleted, we need to handle invalidation here.
327 if (!Updater.skipCurrentLoop())
328 // We know that the loop pass couldn't have invalidated any other
329 // loop's analyses (that's the contract of a loop pass), so directly
330 // handle the loop analysis manager's invalidation here.
331 LAM.invalidate(IR&: *L, PA: PassPA);
332
333 // Then intersect the preserved set so that invalidation of module
334 // analyses will eventually occur when the module pass completes.
335 PA.intersect(Arg: std::move(PassPA));
336 } while (!Worklist.empty());
337
338#ifndef NDEBUG
339 PI.popBeforeNonSkippedPassCallback();
340#endif
341
342 // By definition we preserve the proxy. We also preserve all analyses on
343 // Loops. This precludes *any* invalidation of loop analyses by the proxy,
344 // but that's OK because we've taken care to invalidate analyses in the
345 // loop analysis manager incrementally above.
346 PA.preserveSet<AllAnalysesOn<Loop>>();
347 PA.preserve<LoopAnalysisManagerFunctionProxy>();
348 // We also preserve the set of standard analyses.
349 PA.preserve<DominatorTreeAnalysis>();
350 PA.preserve<LoopAnalysis>();
351 PA.preserve<ScalarEvolutionAnalysis>();
352 if (UseBlockFrequencyInfo && F.hasProfileData())
353 PA.preserve<BlockFrequencyAnalysis>();
354 if (UseBranchProbabilityInfo && F.hasProfileData())
355 PA.preserve<BranchProbabilityAnalysis>();
356 if (UseMemorySSA)
357 PA.preserve<MemorySSAAnalysis>();
358 return PA;
359}
360
361PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
362PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
363 : OS(OS), Banner(Banner) {}
364
365PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
366 LoopStandardAnalysisResults &,
367 LPMUpdater &) {
368 printLoop(L, OS, Banner);
369 return PreservedAnalyses::all();
370}
371