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