58#define DEBUG_TYPE "loop-unroll-and-jam"
63 "llvm.loop.unroll_and_jam.followup_all";
65 "llvm.loop.unroll_and_jam.followup_inner";
67 "llvm.loop.unroll_and_jam.followup_outer";
69 "llvm.loop.unroll_and_jam.followup_remainder_inner";
71 "llvm.loop.unroll_and_jam.followup_remainder_outer";
76 cl::desc(
"Allows loops to be unroll-and-jammed."));
80 cl::desc(
"Use this unroll count for all loops including those with "
81 "unroll_and_jam_count pragma values, for testing purposes"));
85 cl::desc(
"Threshold to use for inner loop when doing unroll and jam."));
89 cl::desc(
"Unrolled size limit for loops with an unroll_and_jam(full) or "
90 "unroll_count pragma."));
96 if (
MDNode *LoopID = L->getLoopID())
104 if (
MDNode *LoopID = L->getLoopID()) {
106 assert(LoopID->getNumOperands() > 0 &&
"requires at least one operand");
107 assert(LoopID->getOperand(0) == LoopID &&
"invalid loop id");
109 for (
unsigned I = 1,
E = LoopID->getNumOperands();
I <
E; ++
I) {
110 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(
I));
136 "Unroll count hint metadata should have two operands.");
138 mdconst::extract<ConstantInt>(MD->
getOperand(1))->getZExtValue();
139 assert(Count >= 1 &&
"Unroll count must be positive.");
149 assert(LoopSize >= UP.
BEInsns &&
"LoopSize should not be less than BEInsns!");
160 unsigned OuterTripMultiple,
unsigned OuterLoopSize,
unsigned InnerTripCount,
168 unsigned MaxTripCount = 0;
169 bool UseUpperBound =
false;
171 L,
TTI, DT, LI, AC, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
172 false, OuterTripMultiple, OuterLoopSize, UP, PP,
174 if (ExplicitUnroll || UseUpperBound) {
177 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; explicit count set by "
178 "computeUnrollCount\n");
185 if (UserUnrollCount) {
197 if (PragmaCount > 0) {
198 UP.
Count = PragmaCount;
201 if ((UP.
AllowRemainder || (OuterTripMultiple % PragmaCount == 0)) &&
209 bool ExplicitUnrollAndJamCount = PragmaCount > 0 || UserUnrollCount;
210 bool ExplicitUnrollAndJam = PragmaEnableUnroll || ExplicitUnrollAndJamCount;
214 if (ExplicitUnrollAndJam)
219 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; can't create remainder and "
220 "inner loop too large\n");
236 if (ExplicitUnrollAndJam)
241 if (InnerTripCount && InnerLoopSize * InnerTripCount < UP.
Threshold) {
242 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; small inner loop count is "
243 "being left for the unroller\n");
252 dbgs() <<
"Won't unroll-and-jam; More than one inner loop block\n");
260 unsigned NumInvariant = 0;
263 if (
auto *Ld = dyn_cast<LoadInst>(&
I)) {
264 Value *V = Ld->getPointerOperand();
271 if (NumInvariant == 0) {
272 LLVM_DEBUG(
dbgs() <<
"Won't unroll-and-jam; No loop invariant loads\n");
286 L, SE,
TTI,
nullptr,
nullptr, ORE, OptLevel, std::nullopt, std::nullopt,
287 std::nullopt, std::nullopt, std::nullopt, std::nullopt);
306 << L->getHeader()->getParent()->getName() <<
"] Loop %"
307 << L->getHeader()->getName() <<
"\n");
325 unsigned NumInlineCandidates;
326 bool NotDuplicatable;
330 Loop *SubLoop = L->getSubLoops()[0];
337 LLVM_DEBUG(
dbgs() <<
" Outer Loop Size: " << OuterLoopSizeIC <<
"\n");
338 LLVM_DEBUG(
dbgs() <<
" Inner Loop Size: " << InnerLoopSizeIC <<
"\n");
341 LLVM_DEBUG(
dbgs() <<
" Not unrolling loop which contains instructions"
342 <<
" with invalid cost.\n");
345 unsigned InnerLoopSize = *InnerLoopSizeIC.
getValue();
346 unsigned OuterLoopSize = *OuterLoopSizeIC.
getValue();
348 if (NotDuplicatable) {
349 LLVM_DEBUG(
dbgs() <<
" Not unrolling loop which contains non-duplicatable "
353 if (NumInlineCandidates != 0) {
354 LLVM_DEBUG(
dbgs() <<
" Not unrolling loop with inlinable calls.\n");
359 dbgs() <<
" Not unrolling loop with convergent instructions.\n");
364 MDNode *OrigOuterLoopID = L->getLoopID();
373 if (NewInnerEpilogueLoopID)
374 SubLoop->
setLoopID(*NewInnerEpilogueLoopID);
385 L, SubLoop,
TTI, DT, LI, &AC, SE, EphValues, &ORE, OuterTripCount,
386 OuterTripMultiple, OuterLoopSize, InnerTripCount, InnerLoopSize, UP, PP);
390 if (OuterTripCount && UP.
Count > OuterTripCount)
391 UP.
Count = OuterTripCount;
393 Loop *EpilogueOuterLoop =
nullptr;
396 &SE, &DT, &AC, &
TTI, &ORE, &EpilogueOuterLoop);
399 if (EpilogueOuterLoop) {
403 if (NewOuterEpilogueLoopID)
404 EpilogueOuterLoop->
setLoopID(*NewOuterEpilogueLoopID);
407 std::optional<MDNode *> NewInnerLoopID =
419 if (NewOuterLoopID) {
420 L->setLoopID(*NewOuterLoopID);
430 L->setLoopAlreadyUnrolled();
441 bool DidSomething =
false;
449 while (!Worklist.
empty()) {
451 std::string LoopName = std::string(L->getName());
457 U.markLoopAsDeleted(*L, LoopName);
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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 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 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, unsigned OuterLoopSize, unsigned InnerTripCount, unsigned InnerLoopSize, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP)
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
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.
A container for analyses that lazily runs them and caches their results.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
DependenceInfo - This class is the main dependence-analysis driver.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
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.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
MDNode * getLoopID() const
Return the llvm.loop loop id metadata node for this loop if it is present.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
StringRef getString() const
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
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...
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
StringRef - Represent a constant reference to a string, i.e.
bool startswith(StringRef Prefix) const
LLVM Value Representation.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
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.
TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
TransformationMode hasUnrollAndJamTransformation(const Loop *L)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LoopUnrollResult
Represents the result of a UnrollLoop invocation.
@ 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.
TransformationMode
The mode sets how eager a transformation should be applied.
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
@ TM_Disable
The transformation should not be applied.
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, unsigned LoopSize, TargetTransformInfo::UnrollingPreferences &UP, TargetTransformInfo::PeelingPreferences &PP, bool &UseUpperBound)
void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
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.
InstructionCost ApproximateLoopSize(const Loop *L, unsigned &NumCalls, bool &NotDuplicatable, bool &Convergent, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns)
ApproximateLoopSize - Approximate the size of the loop.
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...
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).
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI