LLVM 19.0.0git
LoopUnrollAndJamPass.cpp
Go to the documentation of this file.
1//===- LoopUnrollAndJam.cpp - Loop unroll and jam pass --------------------===//
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// This pass implements an unroll and jam pass. Most of the work is done by
10// Utils/UnrollLoopAndJam.cpp.
11//===----------------------------------------------------------------------===//
12
14#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/StringRef.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/Function.h"
33#include "llvm/IR/Metadata.h"
34#include "llvm/IR/PassManager.h"
38#include "llvm/Support/Debug.h"
44#include <cassert>
45#include <cstdint>
46
47namespace llvm {
48class Instruction;
49class Value;
50} // namespace llvm
51
52using namespace llvm;
53
54#define DEBUG_TYPE "loop-unroll-and-jam"
55
56/// @{
57/// Metadata attribute names
58static const char *const LLVMLoopUnrollAndJamFollowupAll =
59 "llvm.loop.unroll_and_jam.followup_all";
60static const char *const LLVMLoopUnrollAndJamFollowupInner =
61 "llvm.loop.unroll_and_jam.followup_inner";
62static const char *const LLVMLoopUnrollAndJamFollowupOuter =
63 "llvm.loop.unroll_and_jam.followup_outer";
65 "llvm.loop.unroll_and_jam.followup_remainder_inner";
67 "llvm.loop.unroll_and_jam.followup_remainder_outer";
68/// @}
69
70static cl::opt<bool>
71 AllowUnrollAndJam("allow-unroll-and-jam", cl::Hidden,
72 cl::desc("Allows loops to be unroll-and-jammed."));
73
75 "unroll-and-jam-count", cl::Hidden,
76 cl::desc("Use this unroll count for all loops including those with "
77 "unroll_and_jam_count pragma values, for testing purposes"));
78
80 "unroll-and-jam-threshold", cl::init(60), cl::Hidden,
81 cl::desc("Threshold to use for inner loop when doing unroll and jam."));
82
84 "pragma-unroll-and-jam-threshold", cl::init(1024), cl::Hidden,
85 cl::desc("Unrolled size limit for loops with an unroll_and_jam(full) or "
86 "unroll_count pragma."));
87
88// Returns the loop hint metadata node with the given name (for example,
89// "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
90// returned.
92 if (MDNode *LoopID = L->getLoopID())
93 return GetUnrollMetadata(LoopID, Name);
94 return nullptr;
95}
96
97// Returns true if the loop has any metadata starting with Prefix. For example a
98// Prefix of "llvm.loop.unroll." returns true if we have any unroll metadata.
99static bool hasAnyUnrollPragma(const Loop *L, StringRef Prefix) {
100 if (MDNode *LoopID = L->getLoopID()) {
101 // First operand should refer to the loop id itself.
102 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
103 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
104
105 for (unsigned I = 1, E = LoopID->getNumOperands(); I < E; ++I) {
106 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(I));
107 if (!MD)
108 continue;
109
110 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
111 if (!S)
112 continue;
113
114 if (S->getString().starts_with(Prefix))
115 return true;
116 }
117 }
118 return false;
119}
120
121// Returns true if the loop has an unroll_and_jam(enable) pragma.
122static bool hasUnrollAndJamEnablePragma(const Loop *L) {
123 return getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.enable");
124}
125
126// If loop has an unroll_and_jam_count pragma return the (necessarily
127// positive) value from the pragma. Otherwise return 0.
128static unsigned unrollAndJamCountPragmaValue(const Loop *L) {
129 MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.count");
130 if (MD) {
131 assert(MD->getNumOperands() == 2 &&
132 "Unroll count hint metadata should have two operands.");
133 unsigned Count =
134 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
135 assert(Count >= 1 && "Unroll count must be positive.");
136 return Count;
137 }
138 return 0;
139}
140
141// Returns loop size estimation for unrolled loop.
142static uint64_t
145 assert(LoopSize >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
146 return static_cast<uint64_t>(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
147}
148
149// Calculates unroll and jam count and writes it to UP.Count. Returns true if
150// unroll count was set explicitly.
152 Loop *L, Loop *SubLoop, const TargetTransformInfo &TTI, DominatorTree &DT,
154 const SmallPtrSetImpl<const Value *> &EphValues,
155 OptimizationRemarkEmitter *ORE, unsigned OuterTripCount,
156 unsigned OuterTripMultiple, const UnrollCostEstimator &OuterUCE,
157 unsigned InnerTripCount, unsigned InnerLoopSize,
160 unsigned OuterLoopSize = OuterUCE.getRolledLoopSize();
161 // First up use computeUnrollCount from the loop unroller to get a count
162 // for unrolling the outer loop, plus any loops requiring explicit
163 // unrolling we leave to the unroller. This uses UP.Threshold /
164 // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.
165 // We have already checked that the loop has no unroll.* pragmas.
166 unsigned MaxTripCount = 0;
167 bool UseUpperBound = false;
168 bool ExplicitUnroll = computeUnrollCount(
169 L, TTI, DT, LI, AC, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
170 /*MaxOrZero*/ false, OuterTripMultiple, OuterUCE, UP, PP,
171 UseUpperBound);
172 if (ExplicitUnroll || UseUpperBound) {
173 // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it
174 // for the unroller instead.
175 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; explicit count set by "
176 "computeUnrollCount\n");
177 UP.Count = 0;
178 return false;
179 }
180
181 // Override with any explicit Count from the "unroll-and-jam-count" option.
182 bool UserUnrollCount = UnrollAndJamCount.getNumOccurrences() > 0;
183 if (UserUnrollCount) {
185 UP.Force = true;
186 if (UP.AllowRemainder &&
187 getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
188 getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
190 return true;
191 }
192
193 // Check for unroll_and_jam pragmas
194 unsigned PragmaCount = unrollAndJamCountPragmaValue(L);
195 if (PragmaCount > 0) {
196 UP.Count = PragmaCount;
197 UP.Runtime = true;
198 UP.Force = true;
199 if ((UP.AllowRemainder || (OuterTripMultiple % PragmaCount == 0)) &&
200 getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
201 getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
203 return true;
204 }
205
206 bool PragmaEnableUnroll = hasUnrollAndJamEnablePragma(L);
207 bool ExplicitUnrollAndJamCount = PragmaCount > 0 || UserUnrollCount;
208 bool ExplicitUnrollAndJam = PragmaEnableUnroll || ExplicitUnrollAndJamCount;
209
210 // If the loop has an unrolling pragma, we want to be more aggressive with
211 // unrolling limits.
212 if (ExplicitUnrollAndJam)
214
215 if (!UP.AllowRemainder && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
217 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't create remainder and "
218 "inner loop too large\n");
219 UP.Count = 0;
220 return false;
221 }
222
223 // We have a sensible limit for the outer loop, now adjust it for the inner
224 // loop and UP.UnrollAndJamInnerLoopThreshold. If the outer limit was set
225 // explicitly, we want to stick to it.
226 if (!ExplicitUnrollAndJamCount && UP.AllowRemainder) {
227 while (UP.Count != 0 && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
229 UP.Count--;
230 }
231
232 // If we are explicitly unroll and jamming, we are done. Otherwise there are a
233 // number of extra performance heuristics to check.
234 if (ExplicitUnrollAndJam)
235 return true;
236
237 // If the inner loop count is known and small, leave the entire loop nest to
238 // be the unroller
239 if (InnerTripCount && InnerLoopSize * InnerTripCount < UP.Threshold) {
240 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; small inner loop count is "
241 "being left for the unroller\n");
242 UP.Count = 0;
243 return false;
244 }
245
246 // Check for situations where UnJ is likely to be unprofitable. Including
247 // subloops with more than 1 block.
248 if (SubLoop->getBlocks().size() != 1) {
250 dbgs() << "Won't unroll-and-jam; More than one inner loop block\n");
251 UP.Count = 0;
252 return false;
253 }
254
255 // Limit to loops where there is something to gain from unrolling and
256 // jamming the loop. In this case, look for loads that are invariant in the
257 // outer loop and can become shared.
258 unsigned NumInvariant = 0;
259 for (BasicBlock *BB : SubLoop->getBlocks()) {
260 for (Instruction &I : *BB) {
261 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
262 Value *V = Ld->getPointerOperand();
263 const SCEV *LSCEV = SE.getSCEVAtScope(V, L);
264 if (SE.isLoopInvariant(LSCEV, L))
265 NumInvariant++;
266 }
267 }
268 }
269 if (NumInvariant == 0) {
270 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; No loop invariant loads\n");
271 UP.Count = 0;
272 return false;
273 }
274
275 return false;
276}
277
278static LoopUnrollResult
282 OptimizationRemarkEmitter &ORE, int OptLevel) {
284 L, SE, TTI, nullptr, nullptr, ORE, OptLevel, std::nullopt, std::nullopt,
285 std::nullopt, std::nullopt, std::nullopt, std::nullopt);
287 gatherPeelingPreferences(L, SE, TTI, std::nullopt, std::nullopt);
288
290 if (EnableMode & TM_Disable)
292 if (EnableMode & TM_ForcedByUser)
293 UP.UnrollAndJam = true;
294
295 if (AllowUnrollAndJam.getNumOccurrences() > 0)
297 if (UnrollAndJamThreshold.getNumOccurrences() > 0)
299 // Exit early if unrolling is disabled.
302
303 LLVM_DEBUG(dbgs() << "Loop Unroll and Jam: F["
304 << L->getHeader()->getParent()->getName() << "] Loop %"
305 << L->getHeader()->getName() << "\n");
306
307 // A loop with any unroll pragma (enabling/disabling/count/etc) is left for
308 // the unroller, so long as it does not explicitly have unroll_and_jam
309 // metadata. This means #pragma nounroll will disable unroll and jam as well
310 // as unrolling
311 if (hasAnyUnrollPragma(L, "llvm.loop.unroll.") &&
312 !hasAnyUnrollPragma(L, "llvm.loop.unroll_and_jam.")) {
313 LLVM_DEBUG(dbgs() << " Disabled due to pragma.\n");
315 }
316
317 if (!isSafeToUnrollAndJam(L, SE, DT, DI, *LI)) {
318 LLVM_DEBUG(dbgs() << " Disabled due to not being safe.\n");
320 }
321
322 // Approximate the loop size and collect useful info
324 CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
325 Loop *SubLoop = L->getSubLoops()[0];
326 UnrollCostEstimator InnerUCE(SubLoop, TTI, EphValues, UP.BEInsns);
327 UnrollCostEstimator OuterUCE(L, TTI, EphValues, UP.BEInsns);
328
329 if (!InnerUCE.canUnroll() || !OuterUCE.canUnroll()) {
330 LLVM_DEBUG(dbgs() << " Not unrolling loop which contains instructions"
331 << " which cannot be duplicated or have invalid cost.\n");
333 }
334
335 unsigned InnerLoopSize = InnerUCE.getRolledLoopSize();
336 LLVM_DEBUG(dbgs() << " Outer Loop Size: " << OuterUCE.getRolledLoopSize()
337 << "\n");
338 LLVM_DEBUG(dbgs() << " Inner Loop Size: " << InnerLoopSize << "\n");
339
340 if (InnerUCE.NumInlineCandidates != 0 || OuterUCE.NumInlineCandidates != 0) {
341 LLVM_DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
343 }
344 if (InnerUCE.Convergent || OuterUCE.Convergent) {
346 dbgs() << " Not unrolling loop with convergent instructions.\n");
348 }
349
350 // Save original loop IDs for after the transformation.
351 MDNode *OrigOuterLoopID = L->getLoopID();
352 MDNode *OrigSubLoopID = SubLoop->getLoopID();
353
354 // To assign the loop id of the epilogue, assign it before unrolling it so it
355 // is applied to every inner loop of the epilogue. We later apply the loop ID
356 // for the jammed inner loop.
357 std::optional<MDNode *> NewInnerEpilogueLoopID = makeFollowupLoopID(
358 OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
360 if (NewInnerEpilogueLoopID)
361 SubLoop->setLoopID(*NewInnerEpilogueLoopID);
362
363 // Find trip count and trip multiple
364 BasicBlock *Latch = L->getLoopLatch();
365 BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
366 unsigned OuterTripCount = SE.getSmallConstantTripCount(L, Latch);
367 unsigned OuterTripMultiple = SE.getSmallConstantTripMultiple(L, Latch);
368 unsigned InnerTripCount = SE.getSmallConstantTripCount(SubLoop, SubLoopLatch);
369
370 // Decide if, and by how much, to unroll
371 bool IsCountSetExplicitly = computeUnrollAndJamCount(
372 L, SubLoop, TTI, DT, LI, &AC, SE, EphValues, &ORE, OuterTripCount,
373 OuterTripMultiple, OuterUCE, InnerTripCount, InnerLoopSize, UP, PP);
374 if (UP.Count <= 1)
376 // Unroll factor (Count) must be less or equal to TripCount.
377 if (OuterTripCount && UP.Count > OuterTripCount)
378 UP.Count = OuterTripCount;
379
380 Loop *EpilogueOuterLoop = nullptr;
381 LoopUnrollResult UnrollResult = UnrollAndJamLoop(
382 L, UP.Count, OuterTripCount, OuterTripMultiple, UP.UnrollRemainder, LI,
383 &SE, &DT, &AC, &TTI, &ORE, &EpilogueOuterLoop);
384
385 // Assign new loop attributes.
386 if (EpilogueOuterLoop) {
387 std::optional<MDNode *> NewOuterEpilogueLoopID = makeFollowupLoopID(
388 OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
390 if (NewOuterEpilogueLoopID)
391 EpilogueOuterLoop->setLoopID(*NewOuterEpilogueLoopID);
392 }
393
394 std::optional<MDNode *> NewInnerLoopID =
397 if (NewInnerLoopID)
398 SubLoop->setLoopID(*NewInnerLoopID);
399 else
400 SubLoop->setLoopID(OrigSubLoopID);
401
402 if (UnrollResult == LoopUnrollResult::PartiallyUnrolled) {
403 std::optional<MDNode *> NewOuterLoopID = makeFollowupLoopID(
404 OrigOuterLoopID,
406 if (NewOuterLoopID) {
407 L->setLoopID(*NewOuterLoopID);
408
409 // Do not setLoopAlreadyUnrolled if a followup was given.
410 return UnrollResult;
411 }
412 }
413
414 // If loop has an unroll count pragma or unrolled by explicitly set count
415 // mark loop as unrolled to prevent unrolling beyond that requested.
416 if (UnrollResult != LoopUnrollResult::FullyUnrolled && IsCountSetExplicitly)
417 L->setLoopAlreadyUnrolled();
418
419 return UnrollResult;
420}
421
423 ScalarEvolution &SE,
426 OptimizationRemarkEmitter &ORE, int OptLevel,
427 LPMUpdater &U) {
428 bool DidSomething = false;
430 Loop *OutmostLoop = &LN.getOutermostLoop();
431
432 // Add the loop nests in the reverse order of LN. See method
433 // declaration.
435 appendLoopsToWorklist(Loops, Worklist);
436 while (!Worklist.empty()) {
437 Loop *L = Worklist.pop_back_val();
438 std::string LoopName = std::string(L->getName());
439 LoopUnrollResult Result =
440 tryToUnrollAndJamLoop(L, DT, &LI, SE, TTI, AC, DI, ORE, OptLevel);
441 if (Result != LoopUnrollResult::Unmodified)
442 DidSomething = true;
443 if (L == OutmostLoop && Result == LoopUnrollResult::FullyUnrolled)
444 U.markLoopAsDeleted(*L, LoopName);
445 }
446
447 return DidSomething;
448}
449
453 LPMUpdater &U) {
454 Function &F = *LN.getParent();
455
456 DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
458
459 if (!tryToUnrollAndJamLoop(LN, AR.DT, AR.LI, AR.SE, AR.TTI, AR.AC, DI, ORE,
460 OptLevel, U))
461 return PreservedAnalyses::all();
462
464 PA.preserve<LoopNestAnalysis>();
465 return PA;
466}
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
#define LLVM_DEBUG(X)
Definition: Debug.h:101
std::string Name
Hexagon Hardware Loops
This header provides classes for managing per-loop analyses.
This file defines the interface for the loop nest analysis.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
static const char *const LLVMLoopUnrollAndJamFollowupInner
static const char *const LLVMLoopUnrollAndJamFollowupRemainderInner
static const char *const LLVMLoopUnrollAndJamFollowupRemainderOuter
static MDNode * getUnrollMetadataForLoop(const Loop *L, StringRef Name)
static const char *const LLVMLoopUnrollAndJamFollowupOuter
static bool computeUnrollAndJamCount(Loop *L, Loop *SubLoop, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, OptimizationRemarkEmitter *ORE, unsigned OuterTripCount, unsigned OuterTripMultiple, const UnrollCostEstimator &OuterUCE, unsigned InnerTripCount, unsigned InnerLoopSize, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP)
static cl::opt< bool > AllowUnrollAndJam("allow-unroll-and-jam", cl::Hidden, cl::desc("Allows loops to be unroll-and-jammed."))
static uint64_t getUnrollAndJammedLoopSize(unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP)
static cl::opt< unsigned > UnrollAndJamCount("unroll-and-jam-count", cl::Hidden, cl::desc("Use this unroll count for all loops including those with " "unroll_and_jam_count pragma values, for testing purposes"))
static LoopUnrollResult tryToUnrollAndJamLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache &AC, DependenceInfo &DI, OptimizationRemarkEmitter &ORE, int OptLevel)
static bool hasAnyUnrollPragma(const Loop *L, StringRef Prefix)
static cl::opt< unsigned > PragmaUnrollAndJamThreshold("pragma-unroll-and-jam-threshold", cl::init(1024), cl::Hidden, cl::desc("Unrolled size limit for loops with an unroll_and_jam(full) or " "unroll_count pragma."))
static cl::opt< unsigned > UnrollAndJamThreshold("unroll-and-jam-threshold", cl::init(60), cl::Hidden, cl::desc("Threshold to use for inner loop when doing unroll and jam."))
static unsigned unrollAndJamCountPragmaValue(const Loop *L)
static bool hasUnrollAndJamEnablePragma(const Loop *L)
static const char *const LLVMLoopUnrollAndJamFollowupAll
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This file contains the declarations for metadata subclasses.
This header defines various interfaces for pass management in LLVM.
This file provides a priority worklist.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This pass exposes codegen information to IR-level passes.
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
DependenceInfo - This class is the main dependence-analysis driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
This analysis provides information for a loop nest.
This class represents a loop nest and can be used to query its properties.
ArrayRef< Loop * > getLoops() const
Get the loops in the nest.
Function * getParent() const
Return the function to which the loop-nest belongs.
Loop & getOutermostLoop() const
Return the outermost loop in the loop nest.
PreservedAnalyses run(LoopNest &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
Definition: LoopInfo.cpp:525
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
Definition: LoopInfo.cpp:501
Metadata node.
Definition: Metadata.h:1067
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1428
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1434
A single uniqued string.
Definition: Metadata.h:720
StringRef getString() const
Definition: Metadata.cpp:607
The optimization diagnostic interface.
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
bool empty() const
Determine if the PriorityWorklist is empty or not.
This class represents an analyzed expression in the program.
The main scalar evolution driver.
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
unsigned getSmallConstantTripCount(const Loop *L)
Returns the exact trip count of the loop if we can compute it, and the result is a small constant.
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:257
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Produce an estimate of the unrolled cost of the specified loop.
Definition: UnrollLoop.h:122
bool canUnroll() const
Whether it is legal to unroll this loop.
Definition: UnrollLoop.h:135
uint64_t getRolledLoopSize() const
Definition: UnrollLoop.h:137
LLVM Value Representation.
Definition: Value.h:74
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT, DependenceInfo &DI, LoopInfo &LI)
std::optional< MDNode * > makeFollowupLoopID(MDNode *OrigLoopID, ArrayRef< StringRef > FollowupAttrs, const char *InheritOptionsAttrsPrefix="", bool AlwaysNew=false)
Create a new loop identifier for a loop created from a loop transformation.
Definition: LoopUtils.cpp:263
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
Definition: LoopPeel.cpp:832
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
Definition: LoopUtils.cpp:373
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
Definition: UnrollLoop.h:54
@ PartiallyUnrolled
The loop was partially unrolled – we still have a loop, but with a smaller trip count.
@ Unmodified
The loop was not modified.
@ FullyUnrolled
The loop was fully unrolled into straight-line code.
bool computeUnrollCount(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, LoopInfo *LI, AssumptionCache *AC, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, OptimizationRemarkEmitter *ORE, unsigned TripCount, unsigned MaxTripCount, bool MaxOrZero, unsigned TripMultiple, const UnrollCostEstimator &UCE, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound)
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:275
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:292
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:284
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
Definition: LoopUtils.cpp:1681
TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, llvm::OptimizationRemarkEmitter &ORE, int OptLevel, std::optional< unsigned > UserThreshold, std::optional< unsigned > UserCount, std::optional< bool > UserAllowPartial, std::optional< bool > UserRuntime, std::optional< bool > UserUpperBound, std::optional< unsigned > UserFullUnrollMaxCount)
Gather the various unrolling parameters based on the defaults, compiler flags, TTI overrides and user...
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
LoopUnrollResult UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount, unsigned TripMultiple, bool UnrollRemainder, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop=nullptr)
MDNode * GetUnrollMetadata(MDNode *LoopID, StringRef Name)
Given an llvm.loop loop id metadata node, returns the loop hint metadata node with the given name (fo...
Definition: LoopUnroll.cpp:927
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:70
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Parameters that control the generic loop unrolling transformation.
unsigned Count
A forced unrolling factor (the number of concatenated bodies of the original loop in the unrolled loo...
unsigned Threshold
The cost threshold for the unrolled loop.
bool Force
Apply loop unroll on any kind of loop (mainly to loops that fail runtime unrolling).
unsigned UnrollAndJamInnerLoopThreshold
Threshold for unroll and jam, for inner loop size.
bool AllowRemainder
Allow generation of a loop remainder (extra iterations after unroll).
bool UnrollAndJam
Allow unroll and jam. Used to enable unroll and jam for the target.
bool UnrollRemainder
Allow unrolling of all the iterations of the runtime loop remainder.
bool Runtime
Allow runtime unrolling (unrolling of loops to expand the size of the loop body even when the number ...