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>(L, 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(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(*OuterMostLoop, AR.SE);
109        IsLoopNestPtrValid = true;
110        U.markLoopNestChanged(false);
111      }
112
113      PassPA = runSinglePass(*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(std::move(*PassPA));
125      break;
126    }
127
128    // Update the analysis manager as each pass runs and potentially
129    // invalidates analyses.
130    AM.invalidate(IsLoopNestPass[I] ? *OuterMostLoop : L, *PassPA);
131
132    // Finally, we intersect the final preserved analyses to compute the
133    // aggregate preserved set for this pass manager.
134    PA.intersect(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>(L, AR);
159  for (auto &Pass : LoopPasses) {
160    std::optional<PreservedAnalyses> PassPA =
161        runSinglePass(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(std::move(*PassPA));
172      break;
173    }
174
175    // Update the analysis manager as each pass runs and potentially
176    // invalidates analyses.
177    AM.invalidate(L, *PassPA);
178
179    // Finally, we intersect the final preserved analyses to compute the
180    // aggregate preserved set for this pass manager.
181    PA.intersect(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>(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>(LoopCanonicalizationFPM, F)) {
210    PA = LoopCanonicalizationFPM.run(F, AM);
211    PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
212  }
213
214  // Get the loop structure for this function
215  LoopInfo &LI = AM.getResult<LoopAnalysis>(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>(F).getMSSA()) : nullptr;
224  BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
225                                ? (&AM.getResult<BlockFrequencyAnalysis>(F))
226                                : nullptr;
227  BranchProbabilityInfo *BPI =
228      UseBranchProbabilityInfo && F.hasProfileData()
229          ? (&AM.getResult<BranchProbabilityAnalysis>(F))
230          : nullptr;
231  LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
232                                     AM.getResult<AssumptionAnalysis>(F),
233                                     AM.getResult<DominatorTreeAnalysis>(F),
234                                     AM.getResult<LoopAnalysis>(F),
235                                     AM.getResult<ScalarEvolutionAnalysis>(F),
236                                     AM.getResult<TargetLibraryAnalysis>(F),
237                                     AM.getResult<TargetIRAnalysis>(F),
238                                     BFI,
239                                     BPI,
240                                     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>(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(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, *L))
304      continue;
305
306    PreservedAnalyses PassPA = Pass->run(*L, LAM, LAR, Updater);
307
308    // Do not pass deleted Loop into the instrumentation.
309    if (Updater.skipCurrentLoop())
310      PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
311    else
312      PI.runAfterPass<Loop>(*Pass, *L, PassPA);
313
314    if (LAR.MSSA && !PassPA.getChecker<MemorySSAAnalysis>().preserved())
315      report_fatal_error("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(*L, 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(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