LLVM  10.0.0svn
LoopPassManager.h
Go to the documentation of this file.
1 //===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//
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 /// \file
9 ///
10 /// This header provides classes for managing a pipeline of passes over loops
11 /// in LLVM IR.
12 ///
13 /// The primary loop pass pipeline is managed in a very particular way to
14 /// provide a set of core guarantees:
15 /// 1) Loops are, where possible, in simplified form.
16 /// 2) Loops are *always* in LCSSA form.
17 /// 3) A collection of Loop-specific analysis results are available:
18 /// - LoopInfo
19 /// - DominatorTree
20 /// - ScalarEvolution
21 /// - AAManager
22 /// 4) All loop passes preserve #1 (where possible), #2, and #3.
23 /// 5) Loop passes run over each loop in the loop nest from the innermost to
24 /// the outermost. Specifically, all inner loops are processed before
25 /// passes run over outer loops. When running the pipeline across an inner
26 /// loop creates new inner loops, those are added and processed in this
27 /// order as well.
28 ///
29 /// This process is designed to facilitate transformations which simplify,
30 /// reduce, and remove loops. For passes which are more oriented towards
31 /// optimizing loops, especially optimizing loop *nests* instead of single
32 /// loops in isolation, this framework is less interesting.
33 ///
34 //===----------------------------------------------------------------------===//
35 
36 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
37 #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
38 
41 #include "llvm/ADT/STLExtras.h"
46 #include "llvm/Analysis/LoopInfo.h"
51 #include "llvm/IR/Dominators.h"
52 #include "llvm/IR/PassManager.h"
55 
56 namespace llvm {
57 
58 // Forward declarations of an update tracking API used in the pass manager.
59 class LPMUpdater;
60 
61 // Explicit specialization and instantiation declarations for the pass manager.
62 // See the comments on the definition of the specialization for details on how
63 // it differs from the primary template.
64 template <>
65 PreservedAnalyses
66 PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
67  LPMUpdater &>::run(Loop &InitialL, LoopAnalysisManager &AM,
68  LoopStandardAnalysisResults &AnalysisResults,
69  LPMUpdater &U);
70 extern template class PassManager<Loop, LoopAnalysisManager,
71  LoopStandardAnalysisResults &, LPMUpdater &>;
72 
73 /// The Loop pass manager.
74 ///
75 /// See the documentation for the PassManager template for details. It runs
76 /// a sequence of Loop passes over each Loop that the manager is run over. This
77 /// typedef serves as a convenient way to refer to this construct.
78 typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,
79  LPMUpdater &>
81 
82 /// A partial specialization of the require analysis template pass to forward
83 /// the extra parameters from a transformation's run method to the
84 /// AnalysisManager's getResult.
85 template <typename AnalysisT>
86 struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
87  LoopStandardAnalysisResults &, LPMUpdater &>
88  : PassInfoMixin<
90  LoopStandardAnalysisResults &, LPMUpdater &>> {
91  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
92  LoopStandardAnalysisResults &AR, LPMUpdater &) {
93  (void)AM.template getResult<AnalysisT>(L, AR);
94  return PreservedAnalyses::all();
95  }
96 };
97 
98 /// An alias template to easily name a require analysis loop pass.
99 template <typename AnalysisT>
101  RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
102  LoopStandardAnalysisResults &, LPMUpdater &>;
103 
104 namespace internal {
105 /// Helper to implement appending of loops onto a worklist.
106 ///
107 /// We want to process loops in postorder, but the worklist is a LIFO data
108 /// structure, so we append to it in *reverse* postorder.
109 ///
110 /// For trees, a preorder traversal is a viable reverse postorder, so we
111 /// actually append using a preorder walk algorithm.
112 template <typename RangeT>
113 inline void appendLoopsToWorklist(RangeT &&Loops,
115  // We use an internal worklist to build up the preorder traversal without
116  // recursion.
117  SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
118 
119  // We walk the initial sequence of loops in reverse because we generally want
120  // to visit defs before uses and the worklist is LIFO.
121  for (Loop *RootL : reverse(Loops)) {
122  assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
123  assert(PreOrderWorklist.empty() &&
124  "Must start with an empty preorder walk worklist.");
125  PreOrderWorklist.push_back(RootL);
126  do {
127  Loop *L = PreOrderWorklist.pop_back_val();
128  PreOrderWorklist.append(L->begin(), L->end());
129  PreOrderLoops.push_back(L);
130  } while (!PreOrderWorklist.empty());
131 
132  Worklist.insert(std::move(PreOrderLoops));
133  PreOrderLoops.clear();
134  }
135 }
136 }
137 
138 template <typename LoopPassT> class FunctionToLoopPassAdaptor;
139 
140 /// This class provides an interface for updating the loop pass manager based
141 /// on mutations to the loop nest.
142 ///
143 /// A reference to an instance of this class is passed as an argument to each
144 /// Loop pass, and Loop passes should use it to update LPM infrastructure if
145 /// they modify the loop nest structure.
146 class LPMUpdater {
147 public:
148  /// This can be queried by loop passes which run other loop passes (like pass
149  /// managers) to know whether the loop needs to be skipped due to updates to
150  /// the loop nest.
151  ///
152  /// If this returns true, the loop object may have been deleted, so passes
153  /// should take care not to touch the object.
154  bool skipCurrentLoop() const { return SkipCurrentLoop; }
155 
156  /// Loop passes should use this method to indicate they have deleted a loop
157  /// from the nest.
158  ///
159  /// Note that this loop must either be the current loop or a subloop of the
160  /// current loop. This routine must be called prior to removing the loop from
161  /// the loop nest.
162  ///
163  /// If this is called for the current loop, in addition to clearing any
164  /// state, this routine will mark that the current loop should be skipped by
165  /// the rest of the pass management infrastructure.
167  LAM.clear(L, Name);
168  assert((&L == CurrentL || CurrentL->contains(&L)) &&
169  "Cannot delete a loop outside of the "
170  "subloop tree currently being processed.");
171  if (&L == CurrentL)
172  SkipCurrentLoop = true;
173  }
174 
175  /// Loop passes should use this method to indicate they have added new child
176  /// loops of the current loop.
177  ///
178  /// \p NewChildLoops must contain only the immediate children. Any nested
179  /// loops within them will be visited in postorder as usual for the loop pass
180  /// manager.
181  void addChildLoops(ArrayRef<Loop *> NewChildLoops) {
182  // Insert ourselves back into the worklist first, as this loop should be
183  // revisited after all the children have been processed.
184  Worklist.insert(CurrentL);
185 
186 #ifndef NDEBUG
187  for (Loop *NewL : NewChildLoops)
188  assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "
189  "be immediate children of "
190  "the current loop!");
191 #endif
192 
193  internal::appendLoopsToWorklist(NewChildLoops, Worklist);
194 
195  // Also skip further processing of the current loop--it will be revisited
196  // after all of its newly added children are accounted for.
197  SkipCurrentLoop = true;
198  }
199 
200  /// Loop passes should use this method to indicate they have added new
201  /// sibling loops to the current loop.
202  ///
203  /// \p NewSibLoops must only contain the immediate sibling loops. Any nested
204  /// loops within them will be visited in postorder as usual for the loop pass
205  /// manager.
206  void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
207 #ifndef NDEBUG
208  for (Loop *NewL : NewSibLoops)
209  assert(NewL->getParentLoop() == ParentL &&
210  "All of the new loops must be siblings of the current loop!");
211 #endif
212 
213  internal::appendLoopsToWorklist(NewSibLoops, Worklist);
214 
215  // No need to skip the current loop or revisit it, as sibling loops
216  // shouldn't impact anything.
217  }
218 
219  /// Restart the current loop.
220  ///
221  /// Loop passes should call this method to indicate the current loop has been
222  /// sufficiently changed that it should be re-visited from the begining of
223  /// the loop pass pipeline rather than continuing.
225  // Tell the currently in-flight pipeline to stop running.
226  SkipCurrentLoop = true;
227 
228  // And insert ourselves back into the worklist.
229  Worklist.insert(CurrentL);
230  }
231 
232 private:
233  template <typename LoopPassT> friend class llvm::FunctionToLoopPassAdaptor;
234 
235  /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.
237 
238  /// The analysis manager for use in the current loop nest.
239  LoopAnalysisManager &LAM;
240 
241  Loop *CurrentL;
242  bool SkipCurrentLoop;
243 
244 #ifndef NDEBUG
245  // In debug builds we also track the parent loop to implement asserts even in
246  // the face of loop deletion.
247  Loop *ParentL;
248 #endif
249 
250  LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
251  LoopAnalysisManager &LAM)
252  : Worklist(Worklist), LAM(LAM) {}
253 };
254 
255 /// Adaptor that maps from a function to its loops.
256 ///
257 /// Designed to allow composition of a LoopPass(Manager) and a
258 /// FunctionPassManager. Note that if this pass is constructed with a \c
259 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
260 /// analysis prior to running the loop passes over the function to enable a \c
261 /// LoopAnalysisManager to be used within this run safely.
262 template <typename LoopPassT>
264  : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
265 public:
266  explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
267  bool DebugLogging = false)
268  : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
269  UseMemorySSA(UseMemorySSA) {
270  LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
271  LoopCanonicalizationFPM.addPass(LCSSAPass());
272  }
273 
274  /// Runs the loop passes across every loop in the function.
276  // Before we even compute any loop analyses, first run a miniature function
277  // pass pipeline to put loops into their canonical form. Note that we can
278  // directly build up function analyses after this as the function pass
279  // manager handles all the invalidation at that layer.
281 
283  // Check the PassInstrumentation's BeforePass callbacks before running the
284  // canonicalization pipeline.
285  if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
286  PA = LoopCanonicalizationFPM.run(F, AM);
287  PI.runAfterPass<Function>(LoopCanonicalizationFPM, F);
288  }
289 
290  // Get the loop structure for this function
291  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
292 
293  // If there are no loops, there is nothing to do here.
294  if (LI.empty())
295  return PA;
296 
297  // Get the analysis results needed by loop passes.
298  MemorySSA *MSSA = UseMemorySSA
299  ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
300  : nullptr;
301  LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
304  AM.getResult<LoopAnalysis>(F),
308  MSSA};
309 
310  // Setup the loop analysis manager from its proxy. It is important that
311  // this is only done when there are loops to process and we have built the
312  // LoopStandardAnalysisResults object. The loop analyses cached in this
313  // manager have access to those analysis results and so it must invalidate
314  // itself when they go away.
315  auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
316  if (UseMemorySSA)
317  LAMFP.markMSSAUsed();
318  LoopAnalysisManager &LAM = LAMFP.getManager();
319 
320  // A postorder worklist of loops to process.
322 
323  // Register the worklist and loop analysis manager so that loop passes can
324  // update them when they mutate the loop nest structure.
325  LPMUpdater Updater(Worklist, LAM);
326 
327  // Add the loop nests in the reverse order of LoopInfo. For some reason,
328  // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
329  // the purpose of unrolling, loop deletion, and LICM, we largely want to
330  // work forward across the CFG so that we visit defs before uses and can
331  // propagate simplifications from one loop nest into the next.
332  // FIXME: Consider changing the order in LoopInfo.
334 
335  do {
336  Loop *L = Worklist.pop_back_val();
337 
338  // Reset the update structure for this loop.
339  Updater.CurrentL = L;
340  Updater.SkipCurrentLoop = false;
341 
342 #ifndef NDEBUG
343  // Save a parent loop pointer for asserts.
344  Updater.ParentL = L->getParentLoop();
345 
346  // Verify the loop structure and LCSSA form before visiting the loop.
347  L->verifyLoop();
348  assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
349  "Loops must remain in LCSSA form!");
350 #endif
351  // Check the PassInstrumentation's BeforePass callbacks before running the
352  // pass, skip its execution completely if asked to (callback returns
353  // false).
354  if (!PI.runBeforePass<Loop>(Pass, *L))
355  continue;
356  PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
357 
358  // Do not pass deleted Loop into the instrumentation.
359  if (Updater.skipCurrentLoop())
360  PI.runAfterPassInvalidated<Loop>(Pass);
361  else
362  PI.runAfterPass<Loop>(Pass, *L);
363 
364  // FIXME: We should verify the set of analyses relevant to Loop passes
365  // are preserved.
366 
367  // If the loop hasn't been deleted, we need to handle invalidation here.
368  if (!Updater.skipCurrentLoop())
369  // We know that the loop pass couldn't have invalidated any other
370  // loop's analyses (that's the contract of a loop pass), so directly
371  // handle the loop analysis manager's invalidation here.
372  LAM.invalidate(*L, PassPA);
373 
374  // Then intersect the preserved set so that invalidation of module
375  // analyses will eventually occur when the module pass completes.
376  PA.intersect(std::move(PassPA));
377  } while (!Worklist.empty());
378 
379  // By definition we preserve the proxy. We also preserve all analyses on
380  // Loops. This precludes *any* invalidation of loop analyses by the proxy,
381  // but that's OK because we've taken care to invalidate analyses in the
382  // loop analysis manager incrementally above.
383  PA.preserveSet<AllAnalysesOn<Loop>>();
384  PA.preserve<LoopAnalysisManagerFunctionProxy>();
385  // We also preserve the set of standard analyses.
386  PA.preserve<DominatorTreeAnalysis>();
387  PA.preserve<LoopAnalysis>();
388  PA.preserve<ScalarEvolutionAnalysis>();
389  if (UseMemorySSA)
390  PA.preserve<MemorySSAAnalysis>();
391  // FIXME: What we really want to do here is preserve an AA category, but
392  // that concept doesn't exist yet.
393  PA.preserve<AAManager>();
394  PA.preserve<BasicAA>();
395  PA.preserve<GlobalsAA>();
396  PA.preserve<SCEVAA>();
397  return PA;
398  }
399 
400 private:
401  LoopPassT Pass;
402 
403  FunctionPassManager LoopCanonicalizationFPM;
404 
405  bool UseMemorySSA = false;
406 };
407 
408 /// A function to deduce a loop pass type and wrap it in the templated
409 /// adaptor.
410 template <typename LoopPassT>
412 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
413  bool DebugLogging = false) {
414  return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), UseMemorySSA,
415  DebugLogging);
416 }
417 
418 /// Pass for printing a loop's contents as textual IR.
419 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
420  raw_ostream &OS;
421  std::string Banner;
422 
423 public:
424  PrintLoopPass();
425  PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
426 
427  PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
428  LoopStandardAnalysisResults &, LPMUpdater &);
429 };
430 }
431 
432 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
This file provides a priority worklist.
Converts loops into loop-closed SSA form.
Definition: LCSSA.h:37
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This is the interface for a simple mod/ref and alias analysis over globals.
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:451
This pass is responsible for loop canonicalization.
Definition: LoopSimplify.h:51
Analysis pass providing the TargetTransformInfo.
bool empty() const
Determine if the PriorityWorklist is empty or not.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:230
F(f)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &)
A utility pass template to force an analysis result to be available.
Definition: PassManager.h:1355
void addChildLoops(ArrayRef< Loop *> NewChildLoops)
Loop passes should use this method to indicate they have added new child loops of the current loop...
Hexagon Hardware Loops
Definition: BitVector.h:937
This is the interface for a SCEV-based alias analysis.
bool skipCurrentLoop() const
This can be queried by loop passes which run other loop passes (like pass managers) to know whether t...
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1183
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:261
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
Adaptor that maps from a function to its loops.
void revisitCurrentLoop()
Restart the current loop.
This header provides classes for managing per-loop analyses.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
A manager for alias analyses.
Analysis pass providing a never-invalidated alias analysis result.
Analysis pass providing a never-invalidated alias analysis result.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
void addSiblingLoops(ArrayRef< Loop *> NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:581
A function analysis which provides an AssumptionCache.
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
print lazy value Lazy Value Info Printer Pass
void runAfterPass(const PassT &Pass, const IRUnitT &IR) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
void runAfterPassInvalidated(const PassT &Pass) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed...
iterator begin() const
Definition: LoopInfo.h:147
Pass for printing a loop&#39;s contents as textual IR.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:926
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
void invalidate(IRUnitT &IR)
Invalidate a specific analysis pass for an IR module.
Definition: PassManager.h:848
FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA=false, bool DebugLogging=false)
FunctionToLoopPassAdaptor< LoopPassT > createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA=false, bool DebugLogging=false)
A function to deduce a loop pass type and wrap it in the templated adaptor.
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:387
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Runs the loop passes across every loop in the function.
Analysis pass that exposes the ScalarEvolution for a function.
LoopT * getParentLoop() const
Definition: LoopInfo.h:106
Analysis pass providing a never-invalidated alias analysis result.
PassManager< Loop, LoopAnalysisManager, LoopStandardAnalysisResults &, LPMUpdater & > LoopPassManager
The Loop pass manager.
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
void appendLoopsToWorklist(RangeT &&Loops, SmallPriorityWorklist< Loop *, 4 > &Worklist)
Helper to implement appending of loops onto a worklist.
iterator end() const
Definition: LoopInfo.h:148
Analysis pass providing the TargetLibraryInfo.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:281
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
This is the interface for LLVM&#39;s primary stateless and local alias analysis.
A container for analyses that lazily runs them and caches their results.
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
This pass exposes codegen information to IR-level passes.
This header defines various interfaces for pass management in LLVM.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044