LLVM  8.0.0svn
LoopPassManager.h
Go to the documentation of this file.
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 
42 #include "llvm/ADT/STLExtras.h"
47 #include "llvm/Analysis/LoopInfo.h"
52 #include "llvm/IR/Dominators.h"
53 #include "llvm/IR/PassManager.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 &>
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<
91  LoopStandardAnalysisResults &, LPMUpdater &>> {
92  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
93  LoopStandardAnalysisResults &AR, LPMUpdater &) {
94  (void)AM.template getResult<AnalysisT>(L, AR);
95  return PreservedAnalyses::all();
96  }
97 };
98 
99 /// An alias template to easily name a require analysis loop pass.
100 template <typename AnalysisT>
102  RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,
103  LoopStandardAnalysisResults &, LPMUpdater &>;
104 
105 namespace internal {
106 /// Helper to implement appending of loops onto a worklist.
107 ///
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 ///
111 /// For trees, a preorder traversal is a viable reverse postorder, so we
112 /// actually append using a preorder walk algorithm.
113 template <typename RangeT>
114 inline void appendLoopsToWorklist(RangeT &&Loops,
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  for (Loop *RootL : reverse(Loops)) {
123  assert(PreOrderLoops.empty() && "Must start with an empty preorder walk.");
124  assert(PreOrderWorklist.empty() &&
125  "Must start with an empty preorder walk worklist.");
126  PreOrderWorklist.push_back(RootL);
127  do {
128  Loop *L = PreOrderWorklist.pop_back_val();
129  PreOrderWorklist.append(L->begin(), L->end());
130  PreOrderLoops.push_back(L);
131  } while (!PreOrderWorklist.empty());
132 
133  Worklist.insert(std::move(PreOrderLoops));
134  PreOrderLoops.clear();
135  }
136 }
137 }
138 
139 template <typename LoopPassT> class FunctionToLoopPassAdaptor;
140 
141 /// This class provides an interface for updating the loop pass manager based
142 /// on mutations to the loop nest.
143 ///
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 /// they modify the loop nest structure.
147 class LPMUpdater {
148 public:
149  /// This can be queried by loop passes which run other loop passes (like pass
150  /// managers) to know whether the loop needs to be skipped due to updates to
151  /// the loop nest.
152  ///
153  /// If this returns true, the loop object may have been deleted, so passes
154  /// should take care not to touch the object.
155  bool skipCurrentLoop() const { return SkipCurrentLoop; }
156 
157  /// Loop passes should use this method to indicate they have deleted a loop
158  /// from the nest.
159  ///
160  /// Note that this loop must either be the current loop or a subloop of the
161  /// current loop. This routine must be called prior to removing the loop from
162  /// the loop nest.
163  ///
164  /// 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  /// the rest of the pass management infrastructure.
168  LAM.clear(L, Name);
169  assert((&L == CurrentL || CurrentL->contains(&L)) &&
170  "Cannot delete a loop outside of the "
171  "subloop tree currently being processed.");
172  if (&L == CurrentL)
173  SkipCurrentLoop = true;
174  }
175 
176  /// Loop passes should use this method to indicate they have added new child
177  /// loops of the current loop.
178  ///
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  void addChildLoops(ArrayRef<Loop *> NewChildLoops) {
183  // Insert ourselves back into the worklist first, as this loop should be
184  // revisited after all the children have been processed.
185  Worklist.insert(CurrentL);
186 
187 #ifndef NDEBUG
188  for (Loop *NewL : NewChildLoops)
189  assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "
190  "be immediate children of "
191  "the current loop!");
192 #endif
193 
194  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  SkipCurrentLoop = true;
199  }
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  void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {
208 #ifndef NDEBUG
209  for (Loop *NewL : NewSibLoops)
210  assert(NewL->getParentLoop() == ParentL &&
211  "All of the new loops must be siblings of the current loop!");
212 #endif
213 
214  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  }
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.
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.
238 
239  /// The analysis manager for use in the current loop nest.
240  LoopAnalysisManager &LAM;
241 
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 
251  LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,
252  LoopAnalysisManager &LAM)
253  : Worklist(Worklist), LAM(LAM) {}
254 };
255 
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 template <typename LoopPassT>
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  LoopCanonicalizationFPM.addPass(LCSSAPass());
271  }
272 
273  /// Runs the loop passes across every loop in the function.
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.
280 
282  // Check the PassInstrumentation's BeforePass callbacks before running the
283  // canonicalization pipeline.
284  if (PI.runBeforePass<Function>(LoopCanonicalizationFPM, F)) {
285  PA = LoopCanonicalizationFPM.run(F, AM);
286  PI.runAfterPass<Function>(LoopCanonicalizationFPM, F);
287  }
288 
289  // Get the loop structure for this function
290  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
291 
292  // If there are no loops, there is nothing to do here.
293  if (LI.empty())
294  return PA;
295 
296  // Get the analysis results needed by loop passes.
298  ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
299  : nullptr;
300  LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
303  AM.getResult<LoopAnalysis>(F),
307  MSSA};
308 
309  // 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  // itself when they go away.
314  LoopAnalysisManager &LAM =
315  AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
316 
317  // A postorder worklist of loops to process.
319 
320  // 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 
324  // Add the loop nests in the reverse order of LoopInfo. For some reason,
325  // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
326  // the purpose of unrolling, loop deletion, and LICM, we largely want to
327  // 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.
331 
332  do {
333  Loop *L = Worklist.pop_back_val();
334 
335  // Reset the update structure for this loop.
336  Updater.CurrentL = L;
337  Updater.SkipCurrentLoop = false;
338 
339 #ifndef NDEBUG
340  // Save a parent loop pointer for asserts.
341  Updater.ParentL = L->getParentLoop();
342 
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  // pass, skip its execution completely if asked to (callback returns
350  // false).
351  if (!PI.runBeforePass<Loop>(Pass, *L))
352  continue;
353  PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
354 
355  PI.runAfterPass<Loop>(Pass, *L);
356 
357  // 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 
372  // By definition we preserve the proxy. We also preserve all analyses on
373  // 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  // 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  PA.preserve<ScalarEvolutionAnalysis>();
383  PA.preserve<MemorySSAAnalysis>();
384  // FIXME: What we really want to do here is preserve an AA category, but
385  // that concept doesn't exist yet.
386  PA.preserve<AAManager>();
387  PA.preserve<BasicAA>();
388  PA.preserve<GlobalsAA>();
389  PA.preserve<SCEVAA>();
390  return PA;
391  }
392 
393 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>
403 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging = false) {
404  return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), DebugLogging);
405 }
406 
407 /// Pass for printing a loop's contents as textual IR.
408 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
409  raw_ostream &OS;
410  std::string Banner;
411 
412 public:
413  PrintLoopPass();
414  PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");
415 
416  PreservedAnalyses run(Loop &L, LoopAnalysisManager &,
417  LoopStandardAnalysisResults &, LPMUpdater &);
418 };
419 }
420 
421 #endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:81
This file provides a priority worklist.
Converts loops into loop-closed SSA form.
Definition: LCSSA.h:38
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:770
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This is the interface for a simple mod/ref and alias analysis over globals.
bool isRecursivelyLCSSAForm(DominatorTree &DT, const LoopInfo &LI) const
Return true if this Loop and all inner subloops are in LCSSA form.
Definition: LoopInfo.cpp:184
This pass is responsible for loop canonicalization.
Definition: LoopSimplify.h:50
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:231
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:1349
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
amdgpu Simplify well known AMD library false Value Value const Twine & Name
Definition: BitVector.h:938
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:700
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:939
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:251
FunctionToLoopPassAdaptor< LoopPassT > createFunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging=false)
A function to deduce a loop pass type and wrap it in the templated adaptor.
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:366
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:33
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:154
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:160
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:575
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:110
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:847
iterator begin() const
Definition: LoopInfo.h:142
Pass for printing a loop&#39;s contents as textual IR.
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:914
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
Definition: SmallVector.h:394
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:101
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:56
void appendLoopsToWorklist(RangeT &&Loops, SmallPriorityWorklist< Loop *, 4 > &Worklist)
Helper to implement appending of loops onto a worklist.
iterator end() const
Definition: LoopInfo.h:143
Analysis pass providing the TargetLibraryInfo.
FunctionToLoopPassAdaptor(LoopPassT Pass, bool DebugLogging=false)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:92
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:46
void verifyLoop() const
Verify loop structure.
Definition: LoopInfoImpl.h:295
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
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:1038
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.