72#define DEBUG_TYPE "loop-unroll"
76 cl::desc(
"Forget everything in SCEV when doing LoopUnroll, instead of just"
77 " the current top-most loop. This is sometimes preferred to reduce"
82 cl::desc(
"The cost threshold for loop unrolling"));
87 cl::desc(
"The cost threshold for loop unrolling when optimizing for "
92 cl::desc(
"The cost threshold for partial loop unrolling"));
96 cl::desc(
"The maximum 'boost' (represented as a percentage >= 100) applied "
97 "to the threshold when aggressively unrolling a loop due to the "
98 "dynamic cost savings. If completely unrolling a loop will reduce "
99 "the total runtime from X to Y, we boost the loop unroll "
100 "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, "
101 "X/Y). This limit avoids excessive code bloat."));
105 cl::desc(
"Don't allow loop unrolling to simulate more than this number of"
106 "iterations when checking full unroll profitability"));
110 cl::desc(
"Use this unroll count for all loops including those with "
111 "unroll_count pragma values, for testing purposes"));
115 cl::desc(
"Set the max unroll count for partial and runtime unrolling, for"
116 "testing purposes"));
121 "Set the max unroll count for full unrolling, for testing purposes"));
125 cl::desc(
"Allows loops to be partially unrolled until "
126 "-unroll-threshold loop size is reached."));
130 cl::desc(
"Allow generation of a loop remainder (extra iterations) "
131 "when unrolling a loop."));
135 cl::desc(
"Unroll loops with run-time trip counts"));
140 "The max of trip count upper bound that is considered in unrolling"));
144 cl::desc(
"Unrolled size limit for loops with an unroll(full) or "
145 "unroll_count pragma."));
149 cl::desc(
"If the runtime tripcount for the loop is lower than the "
150 "threshold, the loop is considered as flat and will be less "
151 "aggressively unrolled."));
155 cl::desc(
"Allow the loop remainder to be unrolled."));
162 cl::desc(
"Enqueue and re-visit child loops in the loop PM after unrolling. "
163 "This shouldn't typically be needed as child loops (or their "
164 "clones) were already visited."));
168 cl::desc(
"Threshold (max size of unrolled loop) to use in aggressive (O3) "
173 cl::desc(
"Default threshold (max size of unrolled "
174 "loop), used in all but O3 optimizations"));
178 cl::desc(
"Maximum allowed iterations to unroll under pragma unroll full."));
183static const unsigned NoThreshold = std::numeric_limits<unsigned>::max();
191 std::optional<unsigned> UserThreshold, std::optional<unsigned> UserCount,
192 std::optional<bool> UserAllowPartial, std::optional<bool> UserRuntime,
193 std::optional<bool> UserUpperBound,
194 std::optional<unsigned> UserFullUnrollMaxCount) {
206 UP.
MaxCount = std::numeric_limits<unsigned>::max();
225 bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
229 PGSOQueryType::IRPass));
268 UP.
Count = *UserCount;
269 if (UserAllowPartial)
270 UP.
Partial = *UserAllowPartial;
275 if (UserFullUnrollMaxCount)
289struct UnrolledInstState {
293 unsigned IsCounted : 1;
297struct UnrolledInstStateKeyInfo {
301 static inline UnrolledInstState getEmptyKey() {
302 return {PtrInfo::getEmptyKey(), 0, 0, 0};
305 static inline UnrolledInstState getTombstoneKey() {
306 return {PtrInfo::getTombstoneKey(), 0, 0, 0};
309 static inline unsigned getHashValue(
const UnrolledInstState &S) {
310 return PairInfo::getHashValue({S.I, S.Iteration});
313 static inline bool isEqual(
const UnrolledInstState &LHS,
314 const UnrolledInstState &RHS) {
315 return PairInfo::isEqual({
LHS.I,
LHS.Iteration}, {
RHS.I,
RHS.Iteration});
319struct EstimatedUnrollCost {
321 unsigned UnrolledCost;
325 unsigned RolledDynamicCost;
329 PragmaInfo(
bool UUC,
bool PFU,
unsigned PC,
bool PEU)
330 : UserUnrollCount(UUC), PragmaFullUnroll(PFU), PragmaCount(PC),
331 PragmaEnableUnroll(PEU) {}
332 const bool UserUnrollCount;
333 const bool PragmaFullUnroll;
334 const unsigned PragmaCount;
335 const bool PragmaEnableUnroll;
357 unsigned MaxIterationsCountToAnalyze) {
361 assert(MaxIterationsCountToAnalyze <
362 (
unsigned)(std::numeric_limits<int>::max() / 2) &&
363 "The unroll iterations max is too large!");
367 if (!L->isInnermost())
371 if (!TripCount || TripCount > MaxIterationsCountToAnalyze)
404 auto AddCostRecursively = [&](
Instruction &RootI,
int Iteration) {
405 assert(Iteration >= 0 &&
"Cannot have a negative iteration!");
406 assert(CostWorklist.
empty() &&
"Must start with an empty cost list");
407 assert(PHIUsedList.
empty() &&
"Must start with an empty phi used list");
413 for (;; --Iteration) {
419 auto CostIter = InstCostMap.
find({
I, Iteration, 0, 0});
420 if (CostIter == InstCostMap.
end())
425 auto &
Cost = *CostIter;
431 Cost.IsCounted =
true;
434 if (
auto *PhiI = dyn_cast<PHINode>(
I))
435 if (PhiI->getParent() == L->getHeader()) {
436 assert(
Cost.IsFree &&
"Loop PHIs shouldn't be evaluated as they "
437 "inherently simplify during unrolling.");
444 if (
auto *OpI = dyn_cast<Instruction>(
445 PhiI->getIncomingValueForBlock(L->getLoopLatch())))
446 if (L->contains(OpI))
457 if (auto Res = SimplifiedValues.lookup(Op))
463 << Iteration <<
"): ");
473 auto *OpI = dyn_cast<Instruction>(
Op);
474 if (!OpI || !L->contains(OpI))
480 }
while (!CostWorklist.
empty());
482 if (PHIUsedList.
empty())
487 "Cannot track PHI-used values past the first iteration!");
495 assert(L->isLoopSimplifyForm() &&
"Must put loop into normal form first.");
496 assert(L->isLCSSAForm(DT) &&
497 "Must have loops in LCSSA form to track live-out values.");
499 LLVM_DEBUG(
dbgs() <<
"Starting LoopUnroll profitability analysis...\n");
502 L->getHeader()->getParent()->hasMinSize() ?
508 for (
unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
509 LLVM_DEBUG(
dbgs() <<
" Analyzing iteration " << Iteration <<
"\n");
514 auto *
PHI = dyn_cast<PHINode>(&
I);
521 PHI->getNumIncomingValues() == 2 &&
522 "Must have an incoming value only for the preheader and the latch.");
524 Value *V =
PHI->getIncomingValueForBlock(
525 Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
526 if (Iteration != 0 && SimplifiedValues.
count(V))
527 V = SimplifiedValues.
lookup(V);
532 SimplifiedValues.
clear();
533 while (!SimplifiedInputValues.
empty())
539 BBWorklist.
insert(L->getHeader());
550 if (isa<DbgInfoIntrinsic>(
I) || EphValues.
count(&
I))
560 bool IsFree = Analyzer.visit(
I);
561 bool Inserted = InstCostMap.
insert({&
I, (int)Iteration,
565 assert(Inserted &&
"Cannot have a state for an unvisited instruction!");
572 if (
auto *CI = dyn_cast<CallInst>(&
I)) {
573 const Function *Callee = CI->getCalledFunction();
582 if (
I.mayHaveSideEffects())
583 AddCostRecursively(
I, Iteration);
586 if (UnrolledCost > MaxUnrolledLoopSize) {
588 <<
" UnrolledCost: " << UnrolledCost
589 <<
", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize
598 if (SimplifiedValues.
count(V))
599 V = SimplifiedValues.
lookup(V);
600 return dyn_cast<Constant>(V);
606 if (
BranchInst *BI = dyn_cast<BranchInst>(TI)) {
607 if (BI->isConditional()) {
608 if (
auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
610 if (isa<UndefValue>(SimpleCond))
611 KnownSucc = BI->getSuccessor(0);
613 dyn_cast<ConstantInt>(SimpleCond))
614 KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
617 }
else if (
SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
618 if (
auto *SimpleCond = getSimplifiedConstant(SI->getCondition())) {
620 if (isa<UndefValue>(SimpleCond))
621 KnownSucc = SI->getSuccessor(0);
623 dyn_cast<ConstantInt>(SimpleCond))
624 KnownSucc = SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
628 if (L->contains(KnownSucc))
629 BBWorklist.
insert(KnownSucc);
631 ExitWorklist.
insert({BB, KnownSucc});
637 if (L->contains(Succ))
640 ExitWorklist.
insert({BB, Succ});
641 AddCostRecursively(*TI, Iteration);
646 if (UnrolledCost == RolledDynamicCost) {
648 <<
" UnrolledCost: " << UnrolledCost <<
"\n");
653 while (!ExitWorklist.
empty()) {
655 std::tie(ExitingBB, ExitBB) = ExitWorklist.
pop_back_val();
658 auto *PN = dyn_cast<PHINode>(&
I);
662 Value *
Op = PN->getIncomingValueForBlock(ExitingBB);
663 if (
auto *OpI = dyn_cast<Instruction>(
Op))
664 if (L->contains(OpI))
665 AddCostRecursively(*OpI, TripCount - 1);
670 "All instructions must have a valid cost, whether the "
671 "loop is rolled or unrolled.");
674 <<
"UnrolledCost: " << UnrolledCost <<
", "
675 <<
"RolledDynamicCost: " << RolledDynamicCost <<
"\n");
685 Metrics.analyzeBasicBlock(BB,
TTI, EphValues);
687 NotDuplicatable =
Metrics.notDuplicatable;
697 if (LoopSize.
isValid() && LoopSize < BEInsns + 1)
699 LoopSize = BEInsns + 1;
704 unsigned CountOverwrite)
const {
706 assert(LS >= UP.
BEInsns &&
"LoopSize should not be less than BEInsns!");
717 if (
MDNode *LoopID = L->getLoopID())
744 "Unroll count hint metadata should have two operands.");
746 mdconst::extract<ConstantInt>(MD->
getOperand(1))->getZExtValue();
747 assert(Count >= 1 &&
"Unroll count must be positive.");
759 unsigned MaxPercentThresholdBoost) {
760 if (
Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
762 else if (
Cost.UnrolledCost != 0)
764 return std::min(100 *
Cost.RolledDynamicCost /
Cost.UnrolledCost,
765 MaxPercentThresholdBoost);
767 return MaxPercentThresholdBoost;
770static std::optional<unsigned>
772 const unsigned TripMultiple,
const unsigned TripCount,
779 if (PInfo.UserUnrollCount) {
786 if (PInfo.PragmaCount > 0) {
787 if ((UP.
AllowRemainder || (TripMultiple % PInfo.PragmaCount == 0)))
788 return PInfo.PragmaCount;
791 if (PInfo.PragmaFullUnroll && TripCount != 0) {
803 if (PInfo.PragmaEnableUnroll && !TripCount && MaxTripCount &&
816 assert(FullUnrollTripCount &&
"should be non-zero!");
824 return FullUnrollTripCount;
830 L, FullUnrollTripCount, DT, SE, EphValues,
TTI,
836 return FullUnrollTripCount;
841static std::optional<unsigned>
851 <<
"-unroll-allow-partial not given\n");
908 const bool UserUnrollCount =
UnrollCount.getNumOccurrences() > 0;
913 const bool ExplicitUnroll = PragmaCount > 0 || PragmaFullUnroll ||
914 PragmaEnableUnroll || UserUnrollCount;
916 PragmaInfo PInfo(UserUnrollCount, PragmaFullUnroll, PragmaCount,
923 "explicit unroll count",
false);
933 MaxTripCount, UCE, UP)) {
934 UP.
Count = *UnrollFactor;
936 if (UserUnrollCount || (PragmaCount > 0)) {
940 UP.
Runtime |= (PragmaCount > 0);
941 return ExplicitUnroll;
943 if (ExplicitUnroll && TripCount != 0) {
957 UP.
Count = TripCount;
959 TripCount, UCE, UP)) {
960 UP.
Count = *UnrollFactor;
961 UseUpperBound =
false;
962 return ExplicitUnroll;
978 if (!TripCount && MaxTripCount && (UP.
UpperBound || MaxOrZero) &&
980 UP.
Count = MaxTripCount;
982 MaxTripCount, UCE, UP)) {
983 UP.
Count = *UnrollFactor;
984 UseUpperBound =
true;
985 return ExplicitUnroll;
994 return ExplicitUnroll;
1005 UP.
Count = *UnrollFactor;
1007 if ((PragmaFullUnroll || PragmaEnableUnroll) && TripCount &&
1008 UP.
Count != TripCount)
1011 "FullUnrollAsDirectedTooLarge",
1012 L->getStartLoc(), L->getHeader())
1013 <<
"Unable to fully unroll loop as directed by unroll pragma "
1015 "unrolled size is too large.";
1019 if (UP.
Count == 0) {
1020 if (PragmaEnableUnroll)
1023 "UnrollAsDirectedTooLarge",
1024 L->getStartLoc(), L->getHeader())
1025 <<
"Unable to unroll loop as directed by unroll(enable) "
1027 "because unrolled size is too large.";
1031 return ExplicitUnroll;
1034 "All cases when TripCount is constant should be covered here.");
1035 if (PragmaFullUnroll)
1038 DEBUG_TYPE,
"CantFullUnrollAsDirectedRuntimeTripCount",
1039 L->getStartLoc(), L->getHeader())
1040 <<
"Unable to fully unroll loop as directed by unroll(full) "
1042 "because loop has a runtime trip count.";
1059 if (L->getHeader()->getParent()->hasProfileData()) {
1067 UP.
Runtime |= PragmaEnableUnroll || PragmaCount > 0 || UserUnrollCount;
1070 dbgs() <<
" will not try to unroll loop with runtime trip count "
1071 <<
"-unroll-runtime not given\n");
1080 while (UP.
Count != 0 &&
1085 unsigned OrigCount = UP.
Count;
1089 while (UP.
Count != 0 && TripMultiple % UP.
Count != 0)
1092 dbgs() <<
"Remainder loop is restricted (that could architecture "
1093 "specific or because the loop contains a convergent "
1094 "instruction), so unroll count must divide the trip "
1096 << TripMultiple <<
". Reducing unroll count from " << OrigCount
1097 <<
" to " << UP.
Count <<
".\n");
1099 using namespace ore;
1104 "DifferentUnrollCountFromDirected",
1105 L->getStartLoc(), L->getHeader())
1106 <<
"Unable to unroll loop the number of times directed by "
1107 "unroll_count pragma because remainder loop is restricted "
1108 "(that could architecture specific or because the loop "
1109 "contains a convergent instruction) and so must have an "
1111 "count that divides the loop trip multiple of "
1112 << NV(
"TripMultiple", TripMultiple) <<
". Unrolling instead "
1113 << NV(
"UnrollCount", UP.
Count) <<
" time(s).";
1120 if (MaxTripCount && UP.
Count > MaxTripCount)
1121 UP.
Count = MaxTripCount;
1127 return ExplicitUnroll;
1135 bool OnlyFullUnroll,
bool OnlyWhenForced,
bool ForgetAllSCEV,
1136 std::optional<unsigned> ProvidedCount,
1137 std::optional<unsigned> ProvidedThreshold,
1138 std::optional<bool> ProvidedAllowPartial,
1139 std::optional<bool> ProvidedRuntime,
1140 std::optional<bool> ProvidedUpperBound,
1141 std::optional<bool> ProvidedAllowPeeling,
1142 std::optional<bool> ProvidedAllowProfileBasedPeeling,
1143 std::optional<unsigned> ProvidedFullUnrollMaxCount) {
1146 << L->getHeader()->getParent()->getName() <<
"] Loop %"
1147 << L->getHeader()->getName() <<
"\n");
1156 Loop *ParentL = L->getParentLoop();
1157 if (ParentL !=
nullptr &&
1161 <<
" llvm.loop.unroll_and_jam.\n");
1172 <<
" Not unrolling loop since it has llvm.loop.unroll_and_jam.\n");
1176 if (!L->isLoopSimplifyForm()) {
1178 dbgs() <<
" Not unrolling loop which is not in loop-simplify form.\n");
1187 bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1189 L, SE,
TTI, BFI, PSI, ORE, OptLevel, ProvidedThreshold, ProvidedCount,
1190 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1191 ProvidedFullUnrollMaxCount);
1193 L, SE,
TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling,
true);
1206 LLVM_DEBUG(
dbgs() <<
" Not unrolling loop which contains instructions"
1207 <<
" which cannot be duplicated or have invalid cost.\n");
1220 LLVM_DEBUG(
dbgs() <<
" Not unrolling loop with inlinable calls.\n");
1229 unsigned TripCount = 0;
1230 unsigned TripMultiple = 1;
1232 L->getExitingBlocks(ExitingBlocks);
1233 for (
BasicBlock *ExitingBlock : ExitingBlocks)
1235 if (!TripCount || TC < TripCount)
1236 TripCount = TripMultiple = TC;
1242 BasicBlock *ExitingBlock = L->getLoopLatch();
1243 if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
1244 ExitingBlock = L->getExitingBlock();
1266 unsigned MaxTripCount = 0;
1267 bool MaxOrZero =
false;
1275 bool UseUpperBound =
false;
1277 L,
TTI, DT, LI, &AC, SE, EphValues, &ORE, TripCount, MaxTripCount,
1278 MaxOrZero, TripMultiple, UCE, UP, PP, UseUpperBound);
1283 assert(UP.
Count == 1 &&
"Cannot perform peel and unroll in the same step");
1284 LLVM_DEBUG(
dbgs() <<
"PEELING loop %" << L->getHeader()->getName()
1285 <<
" with iteration count " << PP.
PeelCount <<
"!\n");
1299 L->setLoopAlreadyUnrolled();
1306 if (OnlyFullUnroll && (UP.
Count < TripCount || UP.
Count < MaxTripCount)) {
1308 dbgs() <<
"Not attempting partial/runtime unroll in FullLoopUnroll.\n");
1317 UP.
Runtime &= TripCount == 0 && TripMultiple % UP.
Count != 0;
1320 MDNode *OrigLoopID = L->getLoopID();
1323 Loop *RemainderLoop =
nullptr;
1328 LI, &SE, &DT, &AC, &
TTI, &ORE, PreserveLCSSA, &RemainderLoop);
1332 if (RemainderLoop) {
1333 std::optional<MDNode *> RemainderLoopID =
1336 if (RemainderLoopID)
1337 RemainderLoop->
setLoopID(*RemainderLoopID);
1341 std::optional<MDNode *> NewLoopID =
1345 L->setLoopID(*NewLoopID);
1349 return UnrollResult;
1356 L->setLoopAlreadyUnrolled();
1358 return UnrollResult;
1363class LoopUnroll :
public LoopPass {
1372 bool OnlyWhenForced;
1379 std::optional<unsigned> ProvidedCount;
1380 std::optional<unsigned> ProvidedThreshold;
1381 std::optional<bool> ProvidedAllowPartial;
1382 std::optional<bool> ProvidedRuntime;
1383 std::optional<bool> ProvidedUpperBound;
1384 std::optional<bool> ProvidedAllowPeeling;
1385 std::optional<bool> ProvidedAllowProfileBasedPeeling;
1386 std::optional<unsigned> ProvidedFullUnrollMaxCount;
1388 LoopUnroll(
int OptLevel = 2,
bool OnlyWhenForced =
false,
1389 bool ForgetAllSCEV =
false,
1390 std::optional<unsigned> Threshold = std::nullopt,
1391 std::optional<unsigned> Count = std::nullopt,
1392 std::optional<bool> AllowPartial = std::nullopt,
1393 std::optional<bool>
Runtime = std::nullopt,
1394 std::optional<bool> UpperBound = std::nullopt,
1395 std::optional<bool> AllowPeeling = std::nullopt,
1396 std::optional<bool> AllowProfileBasedPeeling = std::nullopt,
1397 std::optional<unsigned> ProvidedFullUnrollMaxCount = std::nullopt)
1398 :
LoopPass(
ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1399 ForgetAllSCEV(ForgetAllSCEV), ProvidedCount(
std::
move(Count)),
1400 ProvidedThreshold(Threshold), ProvidedAllowPartial(AllowPartial),
1401 ProvidedRuntime(
Runtime), ProvidedUpperBound(UpperBound),
1402 ProvidedAllowPeeling(AllowPeeling),
1403 ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1404 ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1414 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1415 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1416 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1418 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1419 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1424 bool PreserveLCSSA = mustPreserveAnalysisID(
LCSSAID);
1427 L, DT, LI, SE,
TTI, AC, ORE,
nullptr,
nullptr, PreserveLCSSA, OptLevel,
1428 false, OnlyWhenForced, ForgetAllSCEV, ProvidedCount,
1429 ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime,
1430 ProvidedUpperBound, ProvidedAllowPeeling,
1431 ProvidedAllowProfileBasedPeeling, ProvidedFullUnrollMaxCount);
1433 if (Result == LoopUnrollResult::FullyUnrolled)
1436 return Result != LoopUnrollResult::Unmodified;
1452char LoopUnroll::ID = 0;
1461 bool ForgetAllSCEV,
int Threshold,
int Count,
1462 int AllowPartial,
int Runtime,
int UpperBound,
1467 return new LoopUnroll(
1468 OptLevel, OnlyWhenForced, ForgetAllSCEV,
1469 Threshold == -1 ? std::nullopt : std::optional<unsigned>(Threshold),
1470 Count == -1 ? std::nullopt : std::optional<unsigned>(Count),
1471 AllowPartial == -1 ? std::nullopt : std::optional<bool>(AllowPartial),
1473 UpperBound == -1 ? std::nullopt : std::optional<bool>(UpperBound),
1474 AllowPeeling == -1 ? std::nullopt : std::optional<bool>(AllowPeeling));
1487 Loop *ParentL = L.getParentLoop();
1494 std::string LoopName = std::string(L.getName());
1499 true, OptLevel,
true,
1500 OnlyWhenForced, ForgetSCEV, std::nullopt,
1501 std::nullopt,
false,
1532 bool IsCurrentLoopValid =
false;
1539 if (SibLoop == &L) {
1540 IsCurrentLoopValid =
true;
1549 if (!IsCurrentLoopValid) {
1578 LAM = &LAMProxy->getManager();
1583 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1586 bool Changed =
false;
1593 for (
const auto &L : LI) {
1604 while (!Worklist.
empty()) {
1611 Loop *ParentL = L.getParentLoop();
1617 std::optional<bool> LocalAllowPeeling = UnrollOpts.
AllowPeeling;
1618 if (PSI && PSI->hasHugeWorkingSetSize())
1619 LocalAllowPeeling =
false;
1620 std::string LoopName = std::string(L.getName());
1624 &L, DT, &LI, SE,
TTI, AC, ORE, BFI, PSI,
1653 OS, MapClassName2PassName);
1665 <<
"profile-peeling;";
static bool isEqual(const Function &Caller, const Function &Callee)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
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
This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header provides classes for managing per-loop analyses.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
static MDNode * getUnrollMetadataForLoop(const Loop *L, StringRef Name)
static cl::opt< unsigned > UnrollMaxCount("unroll-max-count", cl::Hidden, cl::desc("Set the max unroll count for partial and runtime unrolling, for" "testing purposes"))
static cl::opt< unsigned > UnrollCount("unroll-count", cl::Hidden, cl::desc("Use this unroll count for all loops including those with " "unroll_count pragma values, for testing purposes"))
static cl::opt< unsigned > UnrollThresholdDefault("unroll-threshold-default", cl::init(150), cl::Hidden, cl::desc("Default threshold (max size of unrolled " "loop), used in all but O3 optimizations"))
static cl::opt< unsigned > FlatLoopTripCountThreshold("flat-loop-tripcount-threshold", cl::init(5), cl::Hidden, cl::desc("If the runtime tripcount for the loop is lower than the " "threshold, the loop is considered as flat and will be less " "aggressively unrolled."))
static cl::opt< unsigned > UnrollMaxIterationsCountToAnalyze("unroll-max-iteration-count-to-analyze", cl::init(10), cl::Hidden, cl::desc("Don't allow loop unrolling to simulate more than this number of" "iterations when checking full unroll profitability"))
static LoopUnrollResult tryToUnrollLoop(Loop *L, DominatorTree &DT, LoopInfo *LI, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache &AC, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, bool PreserveLCSSA, int OptLevel, bool OnlyFullUnroll, bool OnlyWhenForced, bool ForgetAllSCEV, std::optional< unsigned > ProvidedCount, std::optional< unsigned > ProvidedThreshold, std::optional< bool > ProvidedAllowPartial, std::optional< bool > ProvidedRuntime, std::optional< bool > ProvidedUpperBound, std::optional< bool > ProvidedAllowPeeling, std::optional< bool > ProvidedAllowProfileBasedPeeling, std::optional< unsigned > ProvidedFullUnrollMaxCount)
static cl::opt< unsigned > UnrollOptSizeThreshold("unroll-optsize-threshold", cl::init(0), cl::Hidden, cl::desc("The cost threshold for loop unrolling when optimizing for " "size"))
static bool hasUnrollFullPragma(const Loop *L)
static cl::opt< bool > UnrollUnrollRemainder("unroll-remainder", cl::Hidden, cl::desc("Allow the loop remainder to be unrolled."))
static unsigned unrollCountPragmaValue(const Loop *L)
static bool hasUnrollEnablePragma(const Loop *L)
static cl::opt< unsigned > UnrollFullMaxCount("unroll-full-max-count", cl::Hidden, cl::desc("Set the max unroll count for full unrolling, for testing purposes"))
static cl::opt< unsigned > UnrollMaxUpperBound("unroll-max-upperbound", cl::init(8), cl::Hidden, cl::desc("The max of trip count upper bound that is considered in unrolling"))
static std::optional< unsigned > shouldFullUnroll(Loop *L, const TargetTransformInfo &TTI, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const unsigned FullUnrollTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static std::optional< EstimatedUnrollCost > analyzeLoopUnrollCost(const Loop *L, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const SmallPtrSetImpl< const Value * > &EphValues, const TargetTransformInfo &TTI, unsigned MaxUnrolledLoopSize, unsigned MaxIterationsCountToAnalyze)
Figure out if the loop is worth full unrolling.
static cl::opt< unsigned > UnrollPartialThreshold("unroll-partial-threshold", cl::Hidden, cl::desc("The cost threshold for partial loop unrolling"))
static cl::opt< bool > UnrollAllowRemainder("unroll-allow-remainder", cl::Hidden, cl::desc("Allow generation of a loop remainder (extra iterations) " "when unrolling a loop."))
static std::optional< unsigned > shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static cl::opt< unsigned > PragmaUnrollFullMaxIterations("pragma-unroll-full-max-iterations", cl::init(1 '000 '000), cl::Hidden, cl::desc("Maximum allowed iterations to unroll under pragma unroll full."))
static const unsigned NoThreshold
A magic value for use with the Threshold parameter to indicate that the loop unroll should be perform...
static std::optional< unsigned > shouldPragmaUnroll(Loop *L, const PragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static cl::opt< bool > UnrollRevisitChildLoops("unroll-revisit-child-loops", cl::Hidden, cl::desc("Enqueue and re-visit child loops in the loop PM after unrolling. " "This shouldn't typically be needed as child loops (or their " "clones) were already visited."))
static cl::opt< unsigned > UnrollThreshold("unroll-threshold", cl::Hidden, cl::desc("The cost threshold for loop unrolling"))
static cl::opt< bool > UnrollRuntime("unroll-runtime", cl::Hidden, cl::desc("Unroll loops with run-time trip counts"))
static bool hasRuntimeUnrollDisablePragma(const Loop *L)
static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
static cl::opt< unsigned > UnrollThresholdAggressive("unroll-threshold-aggressive", cl::init(300), cl::Hidden, cl::desc("Threshold (max size of unrolled loop) to use in aggressive (O3) " "optimizations"))
static cl::opt< unsigned > UnrollMaxPercentThresholdBoost("unroll-max-percent-threshold-boost", cl::init(400), cl::Hidden, cl::desc("The maximum 'boost' (represented as a percentage >= 100) applied " "to the threshold when aggressively unrolling a loop due to the " "dynamic cost savings. If completely unrolling a loop will reduce " "the total runtime from X to Y, we boost the loop unroll " "threshold to DefaultThreshold*std::min(MaxPercentThresholdBoost, " "X/Y). This limit avoids excessive code bloat."))
static cl::opt< unsigned > PragmaUnrollThreshold("pragma-unroll-threshold", cl::init(16 *1024), cl::Hidden, cl::desc("Unrolled size limit for loops with an unroll(full) or " "unroll_count pragma."))
static cl::opt< bool > UnrollAllowPartial("unroll-allow-partial", cl::Hidden, cl::desc("Allows loops to be partially unrolled until " "-unroll-threshold loop size is reached."))
mir Rename Register Operands
const char LLVMTargetMachineRef TM
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
A container for analyses that lazily runs them and caches their results.
void clear(IRUnitT &IR, llvm::StringRef Name)
Clear any cached analysis results for a single unit of IR.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
This is the shared class of boolean and integer constants.
This is an important base class in LLVM.
This class represents an Operation in the Expression.
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Implements a dense probed hash-table based set.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool hasMinSize() const
Optimize this function for minimum size (-Oz).
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
const Function * getFunction() const
Return the function this instruction belongs to.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
void addChildLoops(ArrayRef< Loop * > NewChildLoops)
Loop passes should use this method to indicate they have added new child loops of the current loop.
void markLoopAsDeleted(Loop &L, llvm::StringRef Name)
Loop passes should use this method to indicate they have deleted a loop from the nest.
void addSiblingLoops(ArrayRef< Loop * > NewSibLoops)
Loop passes should use this method to indicate they have added new sibling loops to the current loop.
void markLoopAsDeleted(Loop &L)
Analysis pass that exposes the LoopInfo for a function.
void verifyLoop() const
Verify loop structure.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Represents a single loop in the control flow graph.
void setLoopID(MDNode *LoopID) const
Set the llvm.loop loop id metadata for this loop.
const MDOperand & getOperand(unsigned I) const
unsigned getNumOperands() const
Return number of MDNode operands.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
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.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
unsigned getSmallConstantMaxTripCount(const Loop *L)
Returns the upper bound of the loop trip count as a normal unsigned value.
bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
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.
size_type size() const
Determine the number of elements in the SetVector.
void clear()
Completely clear the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
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...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
Produce an estimate of the unrolled cost of the specified loop.
uint64_t getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, unsigned CountOverwrite=0) const
Returns loop size estimation for unrolled loop, given the unrolling configuration specified by UP.
unsigned NumInlineCandidates
UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns)
bool canUnroll() const
Whether it is legal to unroll this loop.
uint64_t getRolledLoopSize() const
LLVM Value Representation.
std::pair< iterator, bool > insert(const ValueT &V)
iterator find(const_arg_type_t< ValueT > V)
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
initializer< Ty > init(const Ty &Val)
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Returns a loop's estimated trip count based on branch weight metadata.
void initializeLoopUnrollPass(PassRegistry &)
void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
auto successors(const MachineBasicBlock *BB)
@ Runtime
Detect stack use after return if not disabled runtime with (ASAN_OPTIONS=detect_stack_use_after_retur...
bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
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.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Pass * createLoopUnrollPass(int OptLevel=2, bool OnlyWhenForced=false, bool ForgetAllSCEV=false, int Threshold=-1, int Count=-1, int AllowPartial=-1, int Runtime=-1, int UpperBound=-1, int AllowPeeling=-1)
OutputIt transform(R &&Range, OutputIt d_first, UnaryFunction F)
Wrapper function around std::transform to apply a function to a range and store the result elsewhere.
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)
cl::opt< bool > ForgetSCEVInLoopUnroll
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
TransformationMode hasUnrollTransformation(const Loop *L)
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.
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)
void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
const char *const LLVMLoopUnrollFollowupAll
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.
@ TM_Enable
The transformation should be applied without considering a cost model.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
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...
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
const char *const LLVMLoopUnrollFollowupRemainder
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
const char *const LLVMLoopUnrollFollowupUnrolled
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
LoopUnrollResult UnrollLoop(Loop *L, UnrollLoopOptions ULO, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const llvm::TargetTransformInfo *TTI, OptimizationRemarkEmitter *ORE, bool PreserveLCSSA, Loop **RemainderLoop=nullptr)
Unroll the given loop by Count.
void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI)
Perform some cleanup and simplifications on loops after unrolling.
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...
bool peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI, ScalarEvolution *SE, DominatorTree &DT, AssumptionCache *AC, bool PreserveLCSSA, ValueToValueMapTy &VMap)
VMap is the value-map that maps instructions from the original loop to instructions in the last peele...
Implement std::hash so that hash_code can be used in STL containers.
Utility to calculate the size and a few similar metrics for a set of basic blocks.
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).
An information struct used to provide DenseMap with the various necessary components for a given valu...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
bool OnlyWhenForced
If false, use a cost model to determine whether unrolling of a loop is profitable.
const bool ForgetSCEV
If true, forget all loops when unrolling.
std::optional< unsigned > FullUnrollMaxCount
std::optional< bool > AllowPartial
std::optional< bool > AllowRuntime
std::optional< bool > AllowProfileBasedPeeling
std::optional< bool > AllowPeeling
std::optional< bool > AllowUpperBound
A CRTP mix-in to automatically provide informational APIs needed for passes.