Line data Source code
1 : //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : /// \file
10 : ///
11 : /// This header provides classes for managing a pipeline of passes over loops
12 : /// in LLVM IR.
13 : ///
14 : /// The primary loop pass pipeline is managed in a very particular way to
15 : /// provide a set of core guarantees:
16 : /// 1) Loops are, where possible, in simplified form.
17 : /// 2) Loops are *always* in LCSSA form.
18 : /// 3) A collection of Loop-specific analysis results are available:
19 : /// - LoopInfo
20 : /// - DominatorTree
21 : /// - ScalarEvolution
22 : /// - AAManager
23 : /// 4) All loop passes preserve #1 (where possible), #2, and #3.
24 : /// 5) Loop passes run over each loop in the loop nest from the innermost to
25 : /// the outermost. Specifically, all inner loops are processed before
26 : /// passes run over outer loops. When running the pipeline across an inner
27 : /// loop creates new inner loops, those are added and processed in this
28 : /// order as well.
29 : ///
30 : /// This process is designed to facilitate transformations which simplify,
31 : /// reduce, and remove loops. For passes which are more oriented towards
32 : /// optimizing loops, especially optimizing loop *nests* instead of single
33 : /// loops in isolation, this framework is less interesting.
34 : ///
35 : //===----------------------------------------------------------------------===//
36 :
37 : #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
38 : #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
39 :
40 : #include "llvm/ADT/PostOrderIterator.h"
41 : #include "llvm/ADT/PriorityWorklist.h"
42 : #include "llvm/ADT/STLExtras.h"
43 : #include "llvm/Analysis/AliasAnalysis.h"
44 : #include "llvm/Analysis/BasicAliasAnalysis.h"
45 : #include "llvm/Analysis/GlobalsModRef.h"
46 : #include "llvm/Analysis/LoopAnalysisManager.h"
47 : #include "llvm/Analysis/LoopInfo.h"
48 : #include "llvm/Analysis/ScalarEvolution.h"
49 : #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
50 : #include "llvm/Analysis/TargetLibraryInfo.h"
51 : #include "llvm/Analysis/TargetTransformInfo.h"
52 : #include "llvm/IR/Dominators.h"
53 : #include "llvm/IR/PassManager.h"
54 : #include "llvm/Transforms/Utils/LCSSA.h"
55 : #include "llvm/Transforms/Utils/LoopSimplify.h"
56 :
57 : namespace llvm {
58 :
59 : // Forward declarations of an update tracking API used in the pass manager.
60 : class LPMUpdater;
61 :
62 : // Explicit specialization and instantiation declarations for the pass manager.
63 : // See the comments on the definition of the specialization for details on how
64 : // it differs from the primary template.
65 : template <>
66 : PreservedAnalyses
67 : PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
68 : LPMUpdater &>::run(Loop &InitialL, LoopAnalysisManager &AM,
69 : LoopStandardAnalysisResults &AnalysisResults,
70 : LPMUpdater &U);
71 : extern template class PassManager<Loop, LoopAnalysisManager,
72 : LoopStandardAnalysisResults &, LPMUpdater &>;
73 :
74 : /// The Loop pass manager.
75 : ///
76 : /// See the documentation for the PassManager template for details. It runs
77 : /// a sequence of Loop passes over each Loop that the manager is run over. This
78 : /// typedef serves as a convenient way to refer to this construct.
79 : typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
80 : LPMUpdater &>
81 : LoopPassManager;
82 :
83 : /// A partial specialization of the require analysis template pass to forward
84 : /// the extra parameters from a transformation's run method to the
85 : /// AnalysisManager's getResult.
86 : template <typename AnalysisT>
87 : struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
88 : LoopStandardAnalysisResults &, LPMUpdater &>
89 : : PassInfoMixin<
90 : RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
91 : LoopStandardAnalysisResults &, LPMUpdater &>> {
92 0 : PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
93 : LoopStandardAnalysisResults &AR, LPMUpdater &) {
94 : (void)AM.template getResult<AnalysisT>(L, AR);
95 0 : return PreservedAnalyses::all();
96 : }
97 0 : };
98 :
99 : /// An alias template to easily name a require analysis loop pass.
100 0 : template <typename AnalysisT>
101 : using RequireAnalysisLoopPass =
102 0 : RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
103 : LoopStandardAnalysisResults &, LPMUpdater &>;
104 :
105 0 : namespace internal {
106 : /// Helper to implement appending of loops onto a worklist.
107 0 : ///
108 : /// We want to process loops in postorder, but the worklist is a LIFO data
109 : /// structure, so we append to it in *reverse* postorder.
110 0 : ///
111 : /// For trees, a preorder traversal is a viable reverse postorder, so we
112 0 : /// actually append using a preorder walk algorithm.
113 : template <typename RangeT>
114 150 : inline void appendLoopsToWorklist(RangeT &&Loops,
115 0 : SmallPriorityWorklist<Loop *, 4> &Worklist) {
116 : // We use an internal worklist to build up the preorder traversal without
117 : // recursion.
118 : SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
119 :
120 : // We walk the initial sequence of loops in reverse because we generally want
121 : // to visit defs before uses and the worklist is LIFO.
122 305 : for (Loop *RootL : reverse(Loops)) {
123 : assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
124 63 : assert(PreOrderWorklist.empty() &&
125 : "Must start with an empty preorder walk worklist.");
126 155 : PreOrderWorklist.push_back(RootL);
127 : do {
128 167 : Loop *L = PreOrderWorklist.pop_back_val();
129 167 : PreOrderWorklist.append(L->begin(), L->end());
130 167 : PreOrderLoops.push_back(L);
131 167 : } while (!PreOrderWorklist.empty());
132 128 :
133 155 : Worklist.insert(std::move(PreOrderLoops));
134 755 : PreOrderLoops.clear();
135 : }
136 215 : }
137 : }
138 132 :
139 132 : template <typename LoopPassT> class FunctionToLoopPassAdaptor;
140 132 :
141 132 : /// This class provides an interface for updating the loop pass manager based
142 1517 : /// on mutations to the loop nest.
143 65 : ///
144 : /// A reference to an instance of this class is passed as an argument to each
145 : /// Loop pass, and Loop passes should use it to update LPM infrastructure if
146 825 : /// they modify the loop nest structure.
147 57 : class LPMUpdater {
148 897 : public:
149 897 : /// This can be queried by loop passes which run other loop passes (like pass
150 897 : /// managers) to know whether the loop needs to be skipped due to updates to
151 897 : /// the loop nest.
152 : ///
153 762 : /// If this returns true, the loop object may have been deleted, so passes
154 : /// should take care not to touch the object.
155 115 : bool skipCurrentLoop() const { return SkipCurrentLoop; }
156 755 :
157 : /// Loop passes should use this method to indicate they have deleted a loop
158 : /// from the nest.
159 58 : ///
160 : /// Note that this loop must either be the current loop or a subloop of the
161 124 : /// current loop. This routine must be called prior to removing the loop from
162 124 : /// the loop nest.
163 124 : ///
164 124 : /// If this is called for the current loop, in addition to clearing any
165 : /// state, this routine will mark that the current loop should be skipped by
166 58 : /// the rest of the pass management infrastructure.
167 : void markLoopAsDeleted(Loop &L, llvm::StringRef Name) {
168 24 : LAM.clear(L, Name);
169 57 : assert((&L == CurrentL || CurrentL->contains(&L)) &&
170 6 : "Cannot delete a loop outside of the "
171 : "subloop tree currently being processed.");
172 24 : if (&L == CurrentL)
173 24 : SkipCurrentLoop = true;
174 : }
175 0 :
176 : /// Loop passes should use this method to indicate they have added new child
177 : /// loops of the current loop.
178 13 : ///
179 : /// \p NewChildLoops must contain only the immediate children. Any nested
180 : /// loops within them will be visited in postorder as usual for the loop pass
181 : /// manager.
182 8 : void addChildLoops(ArrayRef<Loop *> NewChildLoops) {
183 : // Insert ourselves back into the worklist first, as this loop should be
184 8 : // revisited after all the children have been processed.
185 9 : Worklist.insert(CurrentL);
186 8 :
187 8 : #ifndef NDEBUG
188 : for (Loop *NewL : NewChildLoops)
189 7 : assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "
190 : "be immediate children of "
191 : "the current loop!");
192 6 : #endif
193 :
194 1 : internal::appendLoopsToWorklist(NewChildLoops, Worklist);
195 :
196 : // Also skip further processing of the current loop--it will be revisited
197 : // after all of its newly added children are accounted for.
198 1 : SkipCurrentLoop = true;
199 1 : }
200 :
201 : /// Loop passes should use this method to indicate they have added new
202 : /// sibling loops to the current loop.
203 : ///
204 : /// \p NewSibLoops must only contain the immediate sibling loops. Any nested
205 : /// loops within them will be visited in postorder as usual for the loop pass
206 : /// manager.
207 0 : void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
208 : #ifndef NDEBUG
209 : for (Loop *NewL : NewSibLoops)
210 : assert(NewL->getParentLoop() == ParentL &&
211 0 : "All of the new loops must be siblings of the current loop!");
212 : #endif
213 :
214 106 : internal::appendLoopsToWorklist(NewSibLoops, Worklist);
215 :
216 : // No need to skip the current loop or revisit it, as sibling loops
217 : // shouldn't impact anything.
218 0 : }
219 :
220 : /// Restart the current loop.
221 : ///
222 : /// Loop passes should call this method to indicate the current loop has been
223 : /// sufficiently changed that it should be re-visited from the begining of
224 : /// the loop pass pipeline rather than continuing.
225 : void revisitCurrentLoop() {
226 : // Tell the currently in-flight pipeline to stop running.
227 : SkipCurrentLoop = true;
228 :
229 : // And insert ourselves back into the worklist.
230 : Worklist.insert(CurrentL);
231 : }
232 :
233 : private:
234 : template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
235 :
236 : /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
237 : SmallPriorityWorklist<Loop *, 4> &Worklist;
238 2 :
239 : /// The analysis manager for use in the current loop nest.
240 : LoopAnalysisManager &LAM;
241 2 :
242 : Loop *CurrentL;
243 : bool SkipCurrentLoop;
244 :
245 : #ifndef NDEBUG
246 : // In debug builds we also track the parent loop to implement asserts even in
247 : // the face of loop deletion.
248 : Loop *ParentL;
249 : #endif
250 2 :
251 : LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
252 : LoopAnalysisManager &LAM)
253 : : Worklist(Worklist), LAM(LAM) {}
254 2 : };
255 2 :
256 : /// Adaptor that maps from a function to its loops.
257 : ///
258 : /// Designed to allow composition of a LoopPass(Manager) and a
259 : /// FunctionPassManager. Note that if this pass is constructed with a \c
260 : /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
261 : /// analysis prior to running the loop passes over the function to enable a \c
262 : /// LoopAnalysisManager to be used within this run safely.
263 0 : template <typename LoopPassT>
264 : class FunctionToLoopPassAdaptor
265 : : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
266 : public:
267 : explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false)
268 : : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging) {
269 : LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
270 0 : LoopCanonicalizationFPM.addPass(LCSSAPass());
271 : }
272 :
273 755 : /// Runs the loop passes across every loop in the function.
274 0 : PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
275 : // Before we even compute any loop analyses, first run a miniature function
276 : // pass pipeline to put loops into their canonical form. Note that we can
277 : // directly build up function analyses after this as the function pass
278 : // manager handles all the invalidation at that layer.
279 : PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(F);
280 :
281 : PreservedAnalyses PA = PreservedAnalyses::all();
282 : // Check the PassInstrumentation's BeforePass callbacks before running the
283 : // canonicalization pipeline.
284 499 : if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
285 : PA = LoopCanonicalizationFPM.run(F, AM);
286 : PI.runAfterPass<Function>(LoopCanonicalizationFPM, F);
287 309 : }
288 368 :
289 499 : // Get the loop structure for this function
290 499 : LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
291 309 :
292 : // If there are no loops, there is nothing to do here.
293 : if (LI.empty())
294 1207 : return PA;
295 :
296 : // Get the analysis results needed by loop passes.
297 : MemorySSA *MSSA = EnableMSSALoopDependency
298 : ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
299 1207 : : nullptr;
300 : LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
301 : AM.getResult<AssumptionAnalysis>(F),
302 : AM.getResult<DominatorTreeAnalysis>(F),
303 : AM.getResult<LoopAnalysis>(F),
304 1207 : AM.getResult<ScalarEvolutionAnalysis>(F),
305 1207 : AM.getResult<TargetLibraryAnalysis>(F),
306 1207 : AM.getResult<TargetIRAnalysis>(F),
307 : MSSA};
308 :
309 11 : // Setup the loop analysis manager from its proxy. It is important that
310 : // this is only done when there are loops to process and we have built the
311 : // LoopStandardAnalysisResults object. The loop analyses cached in this
312 : // manager have access to those analysis results and so it must invalidate
313 1207 : // itself when they go away.
314 : LoopAnalysisManager &LAM =
315 : AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
316 :
317 755 : // A postorder worklist of loops to process.
318 : SmallPriorityWorklist<Loop *, 4> Worklist;
319 :
320 794 : // Register the worklist and loop analysis manager so that loop passes can
321 : // update them when they mutate the loop nest structure.
322 : LPMUpdater Updater(Worklist, LAM);
323 8 :
324 8 : // Add the loop nests in the reverse order of LoopInfo. For some reason,
325 31 : // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
326 31 : // the purpose of unrolling, loop deletion, and LICM, we largely want to
327 8 : // work forward across the CFG so that we visit defs before uses and can
328 : // propagate simplifications from one loop nest into the next.
329 : // FIXME: Consider changing the order in LoopInfo.
330 57 : internal::appendLoopsToWorklist(reverse(LI), Worklist);
331 :
332 : do {
333 : Loop *L = Worklist.pop_back_val();
334 :
335 812 : // Reset the update structure for this loop.
336 : Updater.CurrentL = L;
337 : Updater.SkipCurrentLoop = false;
338 :
339 : #ifndef NDEBUG
340 57 : // Save a parent loop pointer for asserts.
341 57 : Updater.ParentL = L->getParentLoop();
342 57 :
343 : // Verify the loop structure and LCSSA form before visiting the loop.
344 : L->verifyLoop();
345 : assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
346 : "Loops must remain in LCSSA form!");
347 : #endif
348 : // Check the PassInstrumentation's BeforePass callbacks before running the
349 57 : // pass, skip its execution completely if asked to (callback returns
350 755 : // false).
351 : if (!PI.runBeforePass<Loop>(Pass, *L))
352 : continue;
353 57 : PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
354 :
355 : PI.runAfterPass<Loop>(Pass, *L);
356 1202 :
357 1145 : // FIXME: We should verify the set of analyses relevant to Loop passes
358 : // are preserved.
359 :
360 : // If the loop hasn't been deleted, we need to handle invalidation here.
361 : if (!Updater.skipCurrentLoop())
362 : // We know that the loop pass couldn't have invalidated any other
363 : // loop's analyses (that's the contract of a loop pass), so directly
364 : // handle the loop analysis manager's invalidation here.
365 : LAM.invalidate(*L, PassPA);
366 :
367 : // Then intersect the preserved set so that invalidation of module
368 : // analyses will eventually occur when the module pass completes.
369 : PA.intersect(std::move(PassPA));
370 : } while (!Worklist.empty());
371 1202 :
372 0 : // By definition we preserve the proxy. We also preserve all analyses on
373 2290 : // Loops. This precludes *any* invalidation of loop analyses by the proxy,
374 : // but that's OK because we've taken care to invalidate analyses in the
375 1145 : // loop analysis manager incrementally above.
376 : PA.preserveSet<AllAnalysesOn<Loop>>();
377 : PA.preserve<LoopAnalysisManagerFunctionProxy>();
378 : // We also preserve the set of standard analyses.
379 : PA.preserve<DominatorTreeAnalysis>();
380 : PA.preserve<LoopAnalysis>();
381 1145 : PA.preserve<ScalarEvolutionAnalysis>();
382 : if (EnableMSSALoopDependency)
383 : PA.preserve<MemorySSAAnalysis>();
384 : // FIXME: What we really want to do here is preserve an AA category, but
385 1029 : // that concept doesn't exist yet.
386 57 : PA.preserve<AAManager>();
387 : PA.preserve<BasicAA>();
388 : PA.preserve<GlobalsAA>();
389 1145 : PA.preserve<SCEVAA>();
390 1145 : return PA;
391 : }
392 42 :
393 42 : private:
394 : LoopPassT Pass;
395 :
396 : FunctionPassManager LoopCanonicalizationFPM;
397 : };
398 :
399 : /// A function to deduce a loop pass type and wrap it in the templated
400 : /// adaptor.
401 : template <typename LoopPassT>
402 755 : FunctionToLoopPassAdaptor<LoopPassT>
403 : createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) {
404 : return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging);
405 : }
406 :
407 134 : /// Pass for printing a loop's contents as textual IR.
408 0 : class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
409 268 : raw_ostream &OS;
410 : std::string Banner;
411 134 :
412 878 : public:
413 : PrintLoopPass();
414 : PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
415 :
416 : PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
417 920 : LoopStandardAnalysisResults &, LPMUpdater &);
418 : };
419 : }
420 :
421 127 : #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
|
