LLVM 19.0.0git
LoopPassManager.cpp
Go to the documentation of this file.
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
18
19using namespace llvm;
20
21namespace llvm {
22
23/// Explicitly specialize the pass manager's run method to handle loop nest
24/// structure updates.
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.
42
43 return PA;
44}
45
47 LPMUpdater &>::printPipeline(raw_ostream &OS,
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.
70 LPMUpdater &U) {
71 assert(L.isOutermost() &&
72 "Loop-nest passes should only run on top-level loops.");
74
75 // Request PassInstrumentation from analysis manager, will use it to run
76 // instrumenting callbacks for the passes later.
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.
153 LPMUpdater &U) {
155
156 // Request PassInstrumentation from analysis manager, will use it to run
157 // instrumenting callbacks for the passes later.
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
193 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
194 OS << (UseMemorySSA ? "loop-mssa(" : "loop(");
195 Pass->printPipeline(OS, MapClassName2PassName);
196 OS << ')';
197}
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.
205
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()
226 : nullptr;
228 UseBranchProbabilityInfo && F.hasProfileData()
230 : nullptr;
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.
248 if (UseMemorySSA)
249 LAMFP.markMSSAUsed();
250 LoopAnalysisManager &LAM = LAMFP.getManager();
251
252 // A postorder worklist of loops to process.
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
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>>();
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
367PrintLoopPass::PrintLoopPass(raw_ostream &OS, const std::string &Banner)
368 : OS(OS), Banner(Banner) {}
369
372 LPMUpdater &) {
373 printLoop(L, OS, Banner);
374 return PreservedAnalyses::all();
375}
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
uint64_t Size
Legalize the Machine IR a function s Machine IR
Definition: Legalizer.cpp:81
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define P(N)
LoopAnalysisManager LAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This pass exposes codegen information to IR-level passes.
A manager for alias analyses.
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:242
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:394
Definition: Any.h:28
A function analysis which provides an AssumptionCache.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Analysis pass which computes BranchProbabilityInfo.
Analysis providing branch probability information.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Runs the loop passes across every loop in the function.
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:552
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
bool skipCurrentLoop() const
This can be queried by loop passes which run other loop passes (like pass managers) to know whether t...
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
LoopT * getParentLoop() const
Return the parent loop if it exists or nullptr for top level loops.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
This analysis provides information for a loop nest.
static std::unique_ptr< LoopNest > getLoopNest(Loop &Root, ScalarEvolution &SE)
Construct a LoopNest object.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:928
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:701
void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
Definition: MemorySSA.cpp:1905
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
void runAfterPassInvalidated(const PassT &Pass, const PreservedAnalyses &PA) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed.
void pushBeforeNonSkippedPassCallback(CallableT C)
void runAfterPass(const PassT &Pass, const IRUnitT &IR, const PreservedAnalyses &PA) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
PreservedAnalyses runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
PreservedAnalyses runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:161
PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs)
Run all of the passes in this manager over the given unit of IR.
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:94
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: Analysis.h:180
void preserveSet()
Mark an analysis set as preserved.
Definition: Analysis.h:144
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
PreservedAnalyses run(Loop &L, LoopAnalysisManager &, LoopStandardAnalysisResults &, LPMUpdater &)
bool empty() const
Determine if the PriorityWorklist is empty or not.
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Analysis pass that exposes the ScalarEvolution for a function.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool VerifySCEV
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:167
bool isSpecialPass(StringRef PassID, const std::vector< StringRef > &Specials)
bool VerifyLoopInfo
Enable verification of loop info.
Definition: LoopInfo.cpp:50
bool VerifyMemorySSA
Enables verification of MemorySSA.
Definition: MemorySSA.cpp:84
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1669
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:40
void printLoop(Loop &L, raw_ostream &OS, const std::string &Banner="")
Function to print a loop's contents as LLVM's text IR assembly.
Definition: LoopInfo.cpp:977
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...