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