LLVM 17.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"
36#include "llvm/Pass.h"
37#include "llvm/PassRegistry.h"
41#include "llvm/Support/Debug.h"
48#include <cassert>
49#include <cstdint>
50
51namespace llvm {
52class Instruction;
53class Value;
54} // namespace llvm
55
56using namespace llvm;
57
58#define DEBUG_TYPE "loop-unroll-and-jam"
59
60/// @{
61/// Metadata attribute names
62static const char *const LLVMLoopUnrollAndJamFollowupAll =
63 "llvm.loop.unroll_and_jam.followup_all";
64static const char *const LLVMLoopUnrollAndJamFollowupInner =
65 "llvm.loop.unroll_and_jam.followup_inner";
66static const char *const LLVMLoopUnrollAndJamFollowupOuter =
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";
72/// @}
73
74static cl::opt<bool>
75 AllowUnrollAndJam("allow-unroll-and-jam", cl::Hidden,
76 cl::desc("Allows loops to be unroll-and-jammed."));
77
79 "unroll-and-jam-count", cl::Hidden,
80 cl::desc("Use this unroll count for all loops including those with "
81 "unroll_and_jam_count pragma values, for testing purposes"));
82
84 "unroll-and-jam-threshold", cl::init(60), cl::Hidden,
85 cl::desc("Threshold to use for inner loop when doing unroll and jam."));
86
88 "pragma-unroll-and-jam-threshold", cl::init(1024), cl::Hidden,
89 cl::desc("Unrolled size limit for loops with an unroll_and_jam(full) or "
90 "unroll_count pragma."));
91
92// Returns the loop hint metadata node with the given name (for example,
93// "llvm.loop.unroll.count"). If no such metadata node exists, then nullptr is
94// returned.
96 if (MDNode *LoopID = L->getLoopID())
97 return GetUnrollMetadata(LoopID, Name);
98 return nullptr;
99}
100
101// Returns true if the loop has any metadata starting with Prefix. For example a
102// Prefix of "llvm.loop.unroll." returns true if we have any unroll metadata.
103static bool hasAnyUnrollPragma(const Loop *L, StringRef Prefix) {
104 if (MDNode *LoopID = L->getLoopID()) {
105 // First operand should refer to the loop id itself.
106 assert(LoopID->getNumOperands() > 0 && "requires at least one operand");
107 assert(LoopID->getOperand(0) == LoopID && "invalid loop id");
108
109 for (unsigned I = 1, E = LoopID->getNumOperands(); I < E; ++I) {
110 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(I));
111 if (!MD)
112 continue;
113
114 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
115 if (!S)
116 continue;
117
118 if (S->getString().startswith(Prefix))
119 return true;
120 }
121 }
122 return false;
123}
124
125// Returns true if the loop has an unroll_and_jam(enable) pragma.
126static bool hasUnrollAndJamEnablePragma(const Loop *L) {
127 return getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.enable");
128}
129
130// If loop has an unroll_and_jam_count pragma return the (necessarily
131// positive) value from the pragma. Otherwise return 0.
132static unsigned unrollAndJamCountPragmaValue(const Loop *L) {
133 MDNode *MD = getUnrollMetadataForLoop(L, "llvm.loop.unroll_and_jam.count");
134 if (MD) {
135 assert(MD->getNumOperands() == 2 &&
136 "Unroll count hint metadata should have two operands.");
137 unsigned Count =
138 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
139 assert(Count >= 1 && "Unroll count must be positive.");
140 return Count;
141 }
142 return 0;
143}
144
145// Returns loop size estimation for unrolled loop.
146static uint64_t
149 assert(LoopSize >= UP.BEInsns && "LoopSize should not be less than BEInsns!");
150 return static_cast<uint64_t>(LoopSize - UP.BEInsns) * UP.Count + UP.BEInsns;
151}
152
153// Calculates unroll and jam count and writes it to UP.Count. Returns true if
154// unroll count was set explicitly.
156 Loop *L, Loop *SubLoop, const TargetTransformInfo &TTI, DominatorTree &DT,
158 const SmallPtrSetImpl<const Value *> &EphValues,
159 OptimizationRemarkEmitter *ORE, unsigned OuterTripCount,
160 unsigned OuterTripMultiple, unsigned OuterLoopSize, unsigned InnerTripCount,
161 unsigned InnerLoopSize, TargetTransformInfo::UnrollingPreferences &UP,
163 // First up use computeUnrollCount from the loop unroller to get a count
164 // for unrolling the outer loop, plus any loops requiring explicit
165 // unrolling we leave to the unroller. This uses UP.Threshold /
166 // UP.PartialThreshold / UP.MaxCount to come up with sensible loop values.
167 // We have already checked that the loop has no unroll.* pragmas.
168 unsigned MaxTripCount = 0;
169 bool UseUpperBound = false;
170 bool ExplicitUnroll = computeUnrollCount(
171 L, TTI, DT, LI, AC, SE, EphValues, ORE, OuterTripCount, MaxTripCount,
172 /*MaxOrZero*/ false, OuterTripMultiple, OuterLoopSize, UP, PP,
173 UseUpperBound);
174 if (ExplicitUnroll || UseUpperBound) {
175 // If the user explicitly set the loop as unrolled, dont UnJ it. Leave it
176 // for the unroller instead.
177 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; explicit count set by "
178 "computeUnrollCount\n");
179 UP.Count = 0;
180 return false;
181 }
182
183 // Override with any explicit Count from the "unroll-and-jam-count" option.
184 bool UserUnrollCount = UnrollAndJamCount.getNumOccurrences() > 0;
185 if (UserUnrollCount) {
187 UP.Force = true;
188 if (UP.AllowRemainder &&
189 getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
190 getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
192 return true;
193 }
194
195 // Check for unroll_and_jam pragmas
196 unsigned PragmaCount = unrollAndJamCountPragmaValue(L);
197 if (PragmaCount > 0) {
198 UP.Count = PragmaCount;
199 UP.Runtime = true;
200 UP.Force = true;
201 if ((UP.AllowRemainder || (OuterTripMultiple % PragmaCount == 0)) &&
202 getUnrollAndJammedLoopSize(OuterLoopSize, UP) < UP.Threshold &&
203 getUnrollAndJammedLoopSize(InnerLoopSize, UP) <
205 return true;
206 }
207
208 bool PragmaEnableUnroll = hasUnrollAndJamEnablePragma(L);
209 bool ExplicitUnrollAndJamCount = PragmaCount > 0 || UserUnrollCount;
210 bool ExplicitUnrollAndJam = PragmaEnableUnroll || ExplicitUnrollAndJamCount;
211
212 // If the loop has an unrolling pragma, we want to be more aggressive with
213 // unrolling limits.
214 if (ExplicitUnrollAndJam)
216
217 if (!UP.AllowRemainder && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
219 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't create remainder and "
220 "inner loop too large\n");
221 UP.Count = 0;
222 return false;
223 }
224
225 // We have a sensible limit for the outer loop, now adjust it for the inner
226 // loop and UP.UnrollAndJamInnerLoopThreshold. If the outer limit was set
227 // explicitly, we want to stick to it.
228 if (!ExplicitUnrollAndJamCount && UP.AllowRemainder) {
229 while (UP.Count != 0 && getUnrollAndJammedLoopSize(InnerLoopSize, UP) >=
231 UP.Count--;
232 }
233
234 // If we are explicitly unroll and jamming, we are done. Otherwise there are a
235 // number of extra performance heuristics to check.
236 if (ExplicitUnrollAndJam)
237 return true;
238
239 // If the inner loop count is known and small, leave the entire loop nest to
240 // be the unroller
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");
244 UP.Count = 0;
245 return false;
246 }
247
248 // Check for situations where UnJ is likely to be unprofitable. Including
249 // subloops with more than 1 block.
250 if (SubLoop->getBlocks().size() != 1) {
252 dbgs() << "Won't unroll-and-jam; More than one inner loop block\n");
253 UP.Count = 0;
254 return false;
255 }
256
257 // Limit to loops where there is something to gain from unrolling and
258 // jamming the loop. In this case, look for loads that are invariant in the
259 // outer loop and can become shared.
260 unsigned NumInvariant = 0;
261 for (BasicBlock *BB : SubLoop->getBlocks()) {
262 for (Instruction &I : *BB) {
263 if (auto *Ld = dyn_cast<LoadInst>(&I)) {
264 Value *V = Ld->getPointerOperand();
265 const SCEV *LSCEV = SE.getSCEVAtScope(V, L);
266 if (SE.isLoopInvariant(LSCEV, L))
267 NumInvariant++;
268 }
269 }
270 }
271 if (NumInvariant == 0) {
272 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; No loop invariant loads\n");
273 UP.Count = 0;
274 return false;
275 }
276
277 return false;
278}
279
280static LoopUnrollResult
284 OptimizationRemarkEmitter &ORE, int OptLevel) {
286 L, SE, TTI, nullptr, nullptr, ORE, OptLevel, std::nullopt, std::nullopt,
287 std::nullopt, std::nullopt, std::nullopt, std::nullopt);
289 gatherPeelingPreferences(L, SE, TTI, std::nullopt, std::nullopt);
290
292 if (EnableMode & TM_Disable)
294 if (EnableMode & TM_ForcedByUser)
295 UP.UnrollAndJam = true;
296
297 if (AllowUnrollAndJam.getNumOccurrences() > 0)
299 if (UnrollAndJamThreshold.getNumOccurrences() > 0)
301 // Exit early if unrolling is disabled.
304
305 LLVM_DEBUG(dbgs() << "Loop Unroll and Jam: F["
306 << L->getHeader()->getParent()->getName() << "] Loop %"
307 << L->getHeader()->getName() << "\n");
308
309 // A loop with any unroll pragma (enabling/disabling/count/etc) is left for
310 // the unroller, so long as it does not explicitly have unroll_and_jam
311 // metadata. This means #pragma nounroll will disable unroll and jam as well
312 // as unrolling
313 if (hasAnyUnrollPragma(L, "llvm.loop.unroll.") &&
314 !hasAnyUnrollPragma(L, "llvm.loop.unroll_and_jam.")) {
315 LLVM_DEBUG(dbgs() << " Disabled due to pragma.\n");
317 }
318
319 if (!isSafeToUnrollAndJam(L, SE, DT, DI, *LI)) {
320 LLVM_DEBUG(dbgs() << " Disabled due to not being safe.\n");
322 }
323
324 // Approximate the loop size and collect useful info
325 unsigned NumInlineCandidates;
326 bool NotDuplicatable;
327 bool Convergent;
329 CodeMetrics::collectEphemeralValues(L, &AC, EphValues);
330 Loop *SubLoop = L->getSubLoops()[0];
331 InstructionCost InnerLoopSizeIC =
332 ApproximateLoopSize(SubLoop, NumInlineCandidates, NotDuplicatable,
333 Convergent, TTI, EphValues, UP.BEInsns);
334 InstructionCost OuterLoopSizeIC =
335 ApproximateLoopSize(L, NumInlineCandidates, NotDuplicatable, Convergent,
336 TTI, EphValues, UP.BEInsns);
337 LLVM_DEBUG(dbgs() << " Outer Loop Size: " << OuterLoopSizeIC << "\n");
338 LLVM_DEBUG(dbgs() << " Inner Loop Size: " << InnerLoopSizeIC << "\n");
339
340 if (!InnerLoopSizeIC.isValid() || !OuterLoopSizeIC.isValid()) {
341 LLVM_DEBUG(dbgs() << " Not unrolling loop which contains instructions"
342 << " with invalid cost.\n");
344 }
345 unsigned InnerLoopSize = *InnerLoopSizeIC.getValue();
346 unsigned OuterLoopSize = *OuterLoopSizeIC.getValue();
347
348 if (NotDuplicatable) {
349 LLVM_DEBUG(dbgs() << " Not unrolling loop which contains non-duplicatable "
350 "instructions.\n");
352 }
353 if (NumInlineCandidates != 0) {
354 LLVM_DEBUG(dbgs() << " Not unrolling loop with inlinable calls.\n");
356 }
357 if (Convergent) {
359 dbgs() << " Not unrolling loop with convergent instructions.\n");
361 }
362
363 // Save original loop IDs for after the transformation.
364 MDNode *OrigOuterLoopID = L->getLoopID();
365 MDNode *OrigSubLoopID = SubLoop->getLoopID();
366
367 // To assign the loop id of the epilogue, assign it before unrolling it so it
368 // is applied to every inner loop of the epilogue. We later apply the loop ID
369 // for the jammed inner loop.
370 std::optional<MDNode *> NewInnerEpilogueLoopID = makeFollowupLoopID(
371 OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
373 if (NewInnerEpilogueLoopID)
374 SubLoop->setLoopID(*NewInnerEpilogueLoopID);
375
376 // Find trip count and trip multiple
377 BasicBlock *Latch = L->getLoopLatch();
378 BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
379 unsigned OuterTripCount = SE.getSmallConstantTripCount(L, Latch);
380 unsigned OuterTripMultiple = SE.getSmallConstantTripMultiple(L, Latch);
381 unsigned InnerTripCount = SE.getSmallConstantTripCount(SubLoop, SubLoopLatch);
382
383 // Decide if, and by how much, to unroll
384 bool IsCountSetExplicitly = computeUnrollAndJamCount(
385 L, SubLoop, TTI, DT, LI, &AC, SE, EphValues, &ORE, OuterTripCount,
386 OuterTripMultiple, OuterLoopSize, InnerTripCount, InnerLoopSize, UP, PP);
387 if (UP.Count <= 1)
389 // Unroll factor (Count) must be less or equal to TripCount.
390 if (OuterTripCount && UP.Count > OuterTripCount)
391 UP.Count = OuterTripCount;
392
393 Loop *EpilogueOuterLoop = nullptr;
394 LoopUnrollResult UnrollResult = UnrollAndJamLoop(
395 L, UP.Count, OuterTripCount, OuterTripMultiple, UP.UnrollRemainder, LI,
396 &SE, &DT, &AC, &TTI, &ORE, &EpilogueOuterLoop);
397
398 // Assign new loop attributes.
399 if (EpilogueOuterLoop) {
400 std::optional<MDNode *> NewOuterEpilogueLoopID = makeFollowupLoopID(
401 OrigOuterLoopID, {LLVMLoopUnrollAndJamFollowupAll,
403 if (NewOuterEpilogueLoopID)
404 EpilogueOuterLoop->setLoopID(*NewOuterEpilogueLoopID);
405 }
406
407 std::optional<MDNode *> NewInnerLoopID =
410 if (NewInnerLoopID)
411 SubLoop->setLoopID(*NewInnerLoopID);
412 else
413 SubLoop->setLoopID(OrigSubLoopID);
414
415 if (UnrollResult == LoopUnrollResult::PartiallyUnrolled) {
416 std::optional<MDNode *> NewOuterLoopID = makeFollowupLoopID(
417 OrigOuterLoopID,
419 if (NewOuterLoopID) {
420 L->setLoopID(*NewOuterLoopID);
421
422 // Do not setLoopAlreadyUnrolled if a followup was given.
423 return UnrollResult;
424 }
425 }
426
427 // If loop has an unroll count pragma or unrolled by explicitly set count
428 // mark loop as unrolled to prevent unrolling beyond that requested.
429 if (UnrollResult != LoopUnrollResult::FullyUnrolled && IsCountSetExplicitly)
430 L->setLoopAlreadyUnrolled();
431
432 return UnrollResult;
433}
434
436 ScalarEvolution &SE,
439 OptimizationRemarkEmitter &ORE, int OptLevel,
440 LPMUpdater &U) {
441 bool DidSomething = false;
443 Loop *OutmostLoop = &LN.getOutermostLoop();
444
445 // Add the loop nests in the reverse order of LN. See method
446 // declaration.
448 appendLoopsToWorklist(Loops, Worklist);
449 while (!Worklist.empty()) {
450 Loop *L = Worklist.pop_back_val();
451 std::string LoopName = std::string(L->getName());
452 LoopUnrollResult Result =
453 tryToUnrollAndJamLoop(L, DT, &LI, SE, TTI, AC, DI, ORE, OptLevel);
454 if (Result != LoopUnrollResult::Unmodified)
455 DidSomething = true;
456 if (L == OutmostLoop && Result == LoopUnrollResult::FullyUnrolled)
457 U.markLoopAsDeleted(*L, LoopName);
458 }
459
460 return DidSomething;
461}
462
466 LPMUpdater &U) {
467 Function &F = *LN.getParent();
468
469 DependenceInfo DI(&F, &AR.AA, &AR.SE, &AR.LI);
471
472 if (!tryToUnrollAndJamLoop(LN, AR.DT, AR.LI, AR.SE, AR.TTI, AR.AC, DI, ORE,
473 OptLevel, U))
474 return PreservedAnalyses::all();
475
477 PA.preserve<LoopNestAnalysis>();
478 return PA;
479}
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 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
#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:620
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:56
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:166
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.
Definition: LoopInfoImpl.h:232
ArrayRef< BlockT * > getBlocks() const
Get a list of the basic blocks which make up this loop.
Definition: LoopInfo.h:188
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:547
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:943
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1291
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1297
A single uniqued string.
Definition: Metadata.h:611
StringRef getString() const
Definition: Metadata.cpp:507
The optimization diagnostic interface.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
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:344
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool startswith(StringRef Prefix) const
Definition: StringRef.h:261
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
LLVM Value Representation.
Definition: Value.h:74
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
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:811
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.
TransformationMode
The mode sets how eager a transformation should be applied.
Definition: LoopUtils.h:271
@ TM_ForcedByUser
The transformation was directed by the user, e.g.
Definition: LoopUtils.h:288
@ TM_Disable
The transformation should not be applied.
Definition: LoopUtils.h:280
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.
Definition: LoopUtils.cpp:1537
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...
Definition: LoopUnroll.cpp:901
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 ...