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