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 | |
18 | using namespace llvm; |
19 | |
20 | namespace llvm { |
21 | |
22 | /// Explicitly specialize the pass manager's run method to handle loop nest |
23 | /// structure updates. |
24 | PreservedAnalyses |
25 | PassManager<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 | |
45 | void 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. |
66 | PreservedAnalyses |
67 | LoopPassManager::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. |
149 | PreservedAnalyses |
150 | LoopPassManager::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 | |
191 | void 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 | } |
197 | PreservedAnalyses 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 | |
361 | PrintLoopPass::PrintLoopPass() : OS(dbgs()) {} |
362 | PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner) |
363 | : OS(OS), Banner(Banner) {} |
364 | |
365 | PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &, |
366 | LoopStandardAnalysisResults &, |
367 | LPMUpdater &) { |
368 | printLoop(L, OS, Banner); |
369 | return PreservedAnalyses::all(); |
370 | } |
371 | |