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/Support/TimeProfiler.h"
10 #include "llvm/Transforms/Scalar/LoopPassManager.h"
11 #include "llvm/Analysis/LoopInfo.h"
12 
13 using namespace llvm;
14 
15 // Explicit template instantiations and specialization defininitions for core
16 // template typedefs.
17 namespace llvm {
18 template class PassManager<Loop, LoopAnalysisManager,
19                            LoopStandardAnalysisResults &, LPMUpdater &>;
20 
21 /// Explicitly specialize the pass manager's run method to handle loop nest
22 /// structure updates.
23 template <>
24 PreservedAnalyses
25 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
26             LPMUpdater &>::run(Loop &L, LoopAnalysisManager &AM,
27                                LoopStandardAnalysisResults &AR, LPMUpdater &U) {
28   PreservedAnalyses PA = PreservedAnalyses::all();
29 
30   if (DebugLogging)
31     dbgs() << "Starting Loop pass manager run.\n";
32 
33   // Request PassInstrumentation from analysis manager, will use it to run
34   // instrumenting callbacks for the passes later.
35   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(L, AR);
36   for (auto &Pass : Passes) {
37     // Check the PassInstrumentation's BeforePass callbacks before running the
38     // pass, skip its execution completely if asked to (callback returns false).
39     if (!PI.runBeforePass<Loop>(*Pass, L))
40       continue;
41 
42     PreservedAnalyses PassPA;
43     {
44       TimeTraceScope TimeScope(Pass->name(), L.getName());
45       PassPA = Pass->run(L, AM, AR, U);
46     }
47 
48     // do not pass deleted Loop into the instrumentation
49     if (U.skipCurrentLoop())
50       PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
51     else
52       PI.runAfterPass<Loop>(*Pass, L, PassPA);
53 
54     // If the loop was deleted, abort the run and return to the outer walk.
55     if (U.skipCurrentLoop()) {
56       PA.intersect(std::move(PassPA));
57       break;
58     }
59 
60     // Update the analysis manager as each pass runs and potentially
61     // invalidates analyses.
62     AM.invalidate(L, PassPA);
63 
64     // Finally, we intersect the final preserved analyses to compute the
65     // aggregate preserved set for this pass manager.
66     PA.intersect(std::move(PassPA));
67 
68     // FIXME: Historically, the pass managers all called the LLVM context's
69     // yield function here. We don't have a generic way to acquire the
70     // context and it isn't yet clear what the right pattern is for yielding
71     // in the new pass manager so it is currently omitted.
72     // ...getContext().yield();
73   }
74 
75   // Invalidation for the current loop should be handled above, and other loop
76   // analysis results shouldn't be impacted by runs over this loop. Therefore,
77   // the remaining analysis results in the AnalysisManager are preserved. We
78   // mark this with a set so that we don't need to inspect each one
79   // individually.
80   // FIXME: This isn't correct! This loop and all nested loops' analyses should
81   // be preserved, but unrolling should invalidate the parent loop's analyses.
82   PA.preserveSet<AllAnalysesOn<Loop>>();
83 
84   if (DebugLogging)
85     dbgs() << "Finished Loop pass manager run.\n";
86 
87   return PA;
88 }
89 }
90 
91 PreservedAnalyses FunctionToLoopPassAdaptor::run(Function &F,
92                                                  FunctionAnalysisManager &AM) {
93   // Before we even compute any loop analyses, first run a miniature function
94   // pass pipeline to put loops into their canonical form. Note that we can
95   // directly build up function analyses after this as the function pass
96   // manager handles all the invalidation at that layer.
97   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
98 
99   PreservedAnalyses PA = PreservedAnalyses::all();
100   // Check the PassInstrumentation's BeforePass callbacks before running the
101   // canonicalization pipeline.
102   if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
103     PA = LoopCanonicalizationFPM.run(F, AM);
104     PI.runAfterPass<Function>(LoopCanonicalizationFPM, F, PA);
105   }
106 
107   // Get the loop structure for this function
108   LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
109 
110   // If there are no loops, there is nothing to do here.
111   if (LI.empty())
112     return PA;
113 
114   // Get the analysis results needed by loop passes.
115   MemorySSA *MSSA =
116       UseMemorySSA ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA()) : nullptr;
117   BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
118                                 ? (&AM.getResult<BlockFrequencyAnalysis>(F))
119                                 : nullptr;
120   LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
121                                      AM.getResult<AssumptionAnalysis>(F),
122                                      AM.getResult<DominatorTreeAnalysis>(F),
123                                      AM.getResult<LoopAnalysis>(F),
124                                      AM.getResult<ScalarEvolutionAnalysis>(F),
125                                      AM.getResult<TargetLibraryAnalysis>(F),
126                                      AM.getResult<TargetIRAnalysis>(F),
127                                      BFI,
128                                      MSSA};
129 
130   // Setup the loop analysis manager from its proxy. It is important that
131   // this is only done when there are loops to process and we have built the
132   // LoopStandardAnalysisResults object. The loop analyses cached in this
133   // manager have access to those analysis results and so it must invalidate
134   // itself when they go away.
135   auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
136   if (UseMemorySSA)
137     LAMFP.markMSSAUsed();
138   LoopAnalysisManager &LAM = LAMFP.getManager();
139 
140   // A postorder worklist of loops to process.
141   SmallPriorityWorklist<Loop *, 4> Worklist;
142 
143   // Register the worklist and loop analysis manager so that loop passes can
144   // update them when they mutate the loop nest structure.
145   LPMUpdater Updater(Worklist, LAM);
146 
147   // Add the loop nests in the reverse order of LoopInfo. See method
148   // declaration.
149   appendLoopsToWorklist(LI, Worklist);
150 
151 #ifndef NDEBUG
152   PI.pushBeforeNonSkippedPassCallback([&LAR, &LI](StringRef PassID, Any IR) {
153     if (isSpecialPass(PassID, {"PassManager"}))
154       return;
155     assert(any_isa<const Loop *>(IR));
156     const Loop *L = any_cast<const Loop *>(IR);
157     assert(L && "Loop should be valid for printing");
158 
159     // Verify the loop structure and LCSSA form before visiting the loop.
160     L->verifyLoop();
161     assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
162            "Loops must remain in LCSSA form!");
163   });
164 #endif
165 
166   do {
167     Loop *L = Worklist.pop_back_val();
168 
169     // Reset the update structure for this loop.
170     Updater.CurrentL = L;
171     Updater.SkipCurrentLoop = false;
172 
173 #ifndef NDEBUG
174     // Save a parent loop pointer for asserts.
175     Updater.ParentL = L->getParentLoop();
176 #endif
177     // Check the PassInstrumentation's BeforePass callbacks before running the
178     // pass, skip its execution completely if asked to (callback returns
179     // false).
180     if (!PI.runBeforePass<Loop>(*Pass, *L))
181       continue;
182 
183     PreservedAnalyses PassPA;
184     {
185       TimeTraceScope TimeScope(Pass->name());
186       PassPA = Pass->run(*L, LAM, LAR, Updater);
187     }
188 
189     // Do not pass deleted Loop into the instrumentation.
190     if (Updater.skipCurrentLoop())
191       PI.runAfterPassInvalidated<Loop>(*Pass, PassPA);
192     else
193       PI.runAfterPass<Loop>(*Pass, *L, PassPA);
194 
195     // FIXME: We should verify the set of analyses relevant to Loop passes
196     // are preserved.
197 
198     // If the loop hasn't been deleted, we need to handle invalidation here.
199     if (!Updater.skipCurrentLoop())
200       // We know that the loop pass couldn't have invalidated any other
201       // loop's analyses (that's the contract of a loop pass), so directly
202       // handle the loop analysis manager's invalidation here.
203       LAM.invalidate(*L, PassPA);
204 
205     // Then intersect the preserved set so that invalidation of module
206     // analyses will eventually occur when the module pass completes.
207     PA.intersect(std::move(PassPA));
208   } while (!Worklist.empty());
209 
210 #ifndef NDEBUG
211   PI.popBeforeNonSkippedPassCallback();
212 #endif
213 
214   // By definition we preserve the proxy. We also preserve all analyses on
215   // Loops. This precludes *any* invalidation of loop analyses by the proxy,
216   // but that's OK because we've taken care to invalidate analyses in the
217   // loop analysis manager incrementally above.
218   PA.preserveSet<AllAnalysesOn<Loop>>();
219   PA.preserve<LoopAnalysisManagerFunctionProxy>();
220   // We also preserve the set of standard analyses.
221   PA.preserve<DominatorTreeAnalysis>();
222   PA.preserve<LoopAnalysis>();
223   PA.preserve<ScalarEvolutionAnalysis>();
224   if (UseBlockFrequencyInfo && F.hasProfileData())
225     PA.preserve<BlockFrequencyAnalysis>();
226   if (UseMemorySSA)
227     PA.preserve<MemorySSAAnalysis>();
228   // FIXME: What we really want to do here is preserve an AA category, but
229   // that concept doesn't exist yet.
230   PA.preserve<AAManager>();
231   PA.preserve<BasicAA>();
232   PA.preserve<GlobalsAA>();
233   PA.preserve<SCEVAA>();
234   return PA;
235 }
236 
237 PrintLoopPass::PrintLoopPass() : OS(dbgs()) {}
238 PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
239     : OS(OS), Banner(Banner) {}
240 
241 PreservedAnalyses PrintLoopPass::run(Loop &L, LoopAnalysisManager &,
242                                      LoopStandardAnalysisResults &,
243                                      LPMUpdater &) {
244   printLoop(L, OS, Banner);
245   return PreservedAnalyses::all();
246 }
247