75#define DEBUG_TYPE "loop-unroll"
79 return LibraryOptions.
get<ScalarOptions>().forget_scev_loop_unroll;
85static const unsigned NoThreshold = std::numeric_limits<unsigned>::max();
93 std::optional<unsigned> UserThreshold, std::optional<bool> UserAllowPartial,
94 std::optional<bool> UserRuntime, std::optional<bool> UserUpperBound,
95 std::optional<unsigned> UserFullUnrollMaxCount) {
101 UP.
Threshold = OptLevel > 2 ? Opts.unroll_threshold_aggressive
102 : Opts.unroll_threshold_default;
108 TTI.getUnrollingPreferences(L, SE, UP, &ORE);
111 bool OptForSize = L->getHeader()->getParent()->hasOptSize() ||
123 if (Opts.unroll_threshold)
125 if (Opts.unroll_partial_threshold)
127 if (Opts.unroll_max_percent_threshold_boost)
129 if (Opts.unroll_max_count)
130 UP.
MaxCount = *Opts.unroll_max_count;
131 if (Opts.unroll_max_upperbound)
133 if (Opts.unroll_full_max_count)
138 if (Opts.unroll_max_upperbound == 0)
141 if (Opts.unroll_max_iteration_count_to_analyze)
143 *Opts.unroll_max_iteration_count_to_analyze;
150 if (UserAllowPartial)
151 UP.
Partial = *UserAllowPartial;
156 if (UserFullUnrollMaxCount)
170struct UnrolledInstState {
174 unsigned IsCounted : 1;
178struct UnrolledInstStateKeyInfo {
179 using PairInfo = DenseMapInfo<std::pair<Instruction *, int>>;
181 static inline unsigned getHashValue(
const UnrolledInstState &S) {
182 return PairInfo::getHashValue({S.I, S.Iteration});
185 static inline bool isEqual(
const UnrolledInstState &
LHS,
186 const UnrolledInstState &
RHS) {
187 return PairInfo::isEqual({
LHS.I,
LHS.Iteration}, {
RHS.I,
RHS.Iteration});
191struct EstimatedUnrollCost {
193 unsigned UnrolledCost;
197 unsigned RolledDynamicCost;
219 unsigned MaxIterationsCountToAnalyze) {
223 assert(MaxIterationsCountToAnalyze <
224 (
unsigned)(std::numeric_limits<int>::max() / 2) &&
225 "The unroll iterations max is too large!");
229 if (!L->isInnermost()) {
231 <<
"Not analyzing loop cost: not an innermost loop.\n");
236 if (!TripCount || TripCount > MaxIterationsCountToAnalyze) {
238 <<
"Not analyzing loop cost: trip count "
239 << (TripCount ?
"too large" :
"unknown") <<
".\n");
273 auto AddCostRecursively = [&](
Instruction &RootI,
int Iteration) {
274 assert(Iteration >= 0 &&
"Cannot have a negative iteration!");
275 assert(CostWorklist.
empty() &&
"Must start with an empty cost list");
276 assert(PHIUsedList.
empty() &&
"Must start with an empty phi used list");
282 for (;; --Iteration) {
288 auto CostIter = InstCostMap.
find({
I, Iteration, 0, 0});
289 if (CostIter == InstCostMap.
end())
294 auto &Cost = *CostIter;
300 Cost.IsCounted =
true;
304 if (PhiI->getParent() == L->getHeader()) {
305 assert(Cost.IsFree &&
"Loop PHIs shouldn't be evaluated as they "
306 "inherently simplify during unrolling.");
314 PhiI->getIncomingValueForBlock(L->getLoopLatch())))
315 if (L->contains(OpI))
326 if (auto Res = SimplifiedValues.lookup(Op))
330 UnrolledCost +=
TTI.getInstructionCost(
I,
Operands, CostKind);
332 <<
"Adding cost of instruction (iteration " << Iteration
344 if (!OpI || !L->contains(OpI))
350 }
while (!CostWorklist.
empty());
352 if (PHIUsedList.
empty())
357 "Cannot track PHI-used values past the first iteration!");
365 assert(L->isLoopSimplifyForm() &&
"Must put loop into normal form first.");
366 assert(L->isLCSSAForm(DT) &&
367 "Must have loops in LCSSA form to track live-out values.");
370 <<
"Starting LoopUnroll profitability analysis...\n");
373 L->getHeader()->getParent()->hasMinSize() ?
379 for (
unsigned Iteration = 0; Iteration < TripCount; ++Iteration) {
392 PHI->getNumIncomingValues() == 2 &&
393 "Must have an incoming value only for the preheader and the latch.");
395 Value *
V =
PHI->getIncomingValueForBlock(
396 Iteration == 0 ? L->getLoopPreheader() : L->getLoopLatch());
397 if (Iteration != 0 && SimplifiedValues.
contains(
V))
403 SimplifiedValues.
clear();
404 while (!SimplifiedInputValues.
empty())
410 BBWorklist.
insert(L->getHeader());
412 for (
unsigned Idx = 0; Idx != BBWorklist.
size(); ++Idx) {
426 RolledDynamicCost +=
TTI.getInstructionCost(&
I, CostKind);
431 bool IsFree = Analyzer.
visit(
I);
432 bool Inserted = InstCostMap.
insert({&
I, (int)Iteration,
436 assert(Inserted &&
"Cannot have a state for an unvisited instruction!");
444 const Function *Callee = CI->getCalledFunction();
445 if (!Callee ||
TTI.isLoweredToCall(Callee)) {
447 <<
"Can't analyze cost of loop with call\n");
454 if (
I.mayHaveSideEffects())
455 AddCostRecursively(
I, Iteration);
458 if (UnrolledCost > MaxUnrolledLoopSize) {
460 dbgs().
indent(3) <<
"Exceeded threshold.. exiting.\n";
462 <<
"UnrolledCost: " << UnrolledCost
463 <<
", MaxUnrolledLoopSize: " << MaxUnrolledLoopSize <<
"\n";
481 if (
auto *SimpleCond = getSimplifiedConstant(BI->getCondition())) {
484 KnownSucc = BI->getSuccessor(0);
487 KnownSucc = BI->getSuccessor(SimpleCondVal->isZero() ? 1 : 0);
490 if (
auto *SimpleCond = getSimplifiedConstant(
SI->getCondition())) {
493 KnownSucc =
SI->getSuccessor(0);
496 KnownSucc =
SI->findCaseValue(SimpleCondVal)->getCaseSuccessor();
500 if (L->contains(KnownSucc))
501 BBWorklist.
insert(KnownSucc);
503 ExitWorklist.
insert({BB, KnownSucc});
509 if (L->contains(Succ))
512 ExitWorklist.
insert({BB, Succ});
513 AddCostRecursively(*TI, Iteration);
518 if (UnrolledCost == RolledDynamicCost) {
520 dbgs().
indent(3) <<
"No opportunities found.. exiting.\n";
521 dbgs().
indent(3) <<
"UnrolledCost: " << UnrolledCost <<
"\n";
527 while (!ExitWorklist.
empty()) {
529 std::tie(ExitingBB, ExitBB) = ExitWorklist.
pop_back_val();
536 Value *
Op = PN->getIncomingValueForBlock(ExitingBB);
538 if (L->contains(OpI))
539 AddCostRecursively(*OpI, TripCount - 1);
544 "All instructions must have a valid cost, whether the "
545 "loop is rolled or unrolled.");
549 dbgs().
indent(3) <<
"UnrolledCost: " << UnrolledCost
550 <<
", RolledDynamicCost: " << RolledDynamicCost <<
"\n";
559 bool PrepareForLTO,
bool TripCountIsUniform) {
562 Metrics.analyzeBasicBlock(BB,
TTI, EphValues, PrepareForLTO, L);
564 NotDuplicatable =
Metrics.notDuplicatable;
581 if (LoopSize.isValid() && LoopSize < BEInsns + 1)
583 LoopSize = BEInsns + 1;
587 const Loop *L)
const {
588 auto ReportCannotUnroll = [&](
StringRef Reason) {
593 L->getStartLoc(), L->getHeader())
594 <<
"unable to unroll loop: " << Reason;
599 ReportCannotUnroll(
"contains convergent operations");
602 if (!LoopSize.isValid()) {
603 ReportCannotUnroll(
"loop size could not be computed");
606 if (NotDuplicatable) {
607 ReportCannotUnroll(
"contains non-duplicatable instructions");
615 unsigned LS = LoopSize.getValue();
616 assert(LS >= UP.
BEInsns &&
"LoopSize should not be less than BEInsns!");
659 "Unroll count hint metadata should have two operands.");
662 assert(
Count >= 1 &&
"Unroll count must be positive.");
683 unsigned MaxPercentThresholdBoost) {
684 if (Cost.RolledDynamicCost >= std::numeric_limits<unsigned>::max() / 100)
686 else if (Cost.UnrolledCost != 0)
688 return std::min(100 * Cost.RolledDynamicCost / Cost.UnrolledCost,
689 MaxPercentThresholdBoost);
691 return MaxPercentThresholdBoost;
694static std::optional<unsigned>
697 const unsigned TripCount,
unsigned MaxTripCount,
709 << *Opts.unroll_count <<
".\n");
710 return *Opts.unroll_count;
713 <<
"Not unrolling with user count " << *Opts.unroll_count <<
": "
715 :
"remainder not allowed")
727 <<
"Not unrolling with pragma count " << PInfo.
PragmaCount
728 <<
": remainder not allowed, count does not divide trip "
729 <<
"multiple " << TripMultiple <<
".\n");
732 L->getStartLoc(), L->getHeader())
733 <<
"may be unable to unroll loop with count "
735 <<
": remainder loop is not allowed and count does not divide "
737 <<
ore::NV(
"TripMultiple", TripMultiple);
742 if (TripCount != 0) {
746 if (TripCount > Opts.pragma_unroll_full_max_iterations) {
748 <<
"Won't unroll; trip count is too large.\n");
751 "PragmaFullUnrollTripCountTooLarge",
752 L->getStartLoc(), L->getHeader())
753 <<
"may be unable to fully unroll loop: trip count "
754 <<
ore::NV(
"TripCount", TripCount) <<
" exceeds limit "
755 <<
ore::NV(
"Limit", Opts.pragma_unroll_full_max_iterations);
761 <<
"Fully unrolling with trip count: " << TripCount <<
".\n");
765 <<
"Not fully unrolling: unknown trip count.\n");
768 "PragmaFullUnrollUnknownTripCount",
769 L->getStartLoc(), L->getHeader())
770 <<
"may be unable to fully unroll loop: trip count is unknown";
777 <<
"Unrolling with max trip count: " << MaxTripCount <<
".\n");
789 assert(FullUnrollTripCount &&
"should be non-zero!");
793 <<
"Not unrolling: trip count " << FullUnrollTripCount
803 <<
" < threshold " << UP.
Threshold <<
".\n");
804 return FullUnrollTripCount;
808 <<
"Unrolled size " << UnrolledSize <<
" exceeds threshold "
809 << UP.
Threshold <<
"; checking for cost benefit.\n");
815 L, FullUnrollTripCount, DT, SE, EphValues,
TTI,
820 unsigned BoostedThreshold = UP.
Threshold * Boost / 100;
821 if (Cost->UnrolledCost < BoostedThreshold) {
823 return FullUnrollTripCount;
826 <<
"Not unrolling: cost " << Cost->UnrolledCost
827 <<
" >= boosted threshold " << BoostedThreshold <<
".\n");
833static std::optional<unsigned>
843 <<
"-unroll-allow-partial not given\n");
846 unsigned Count = TripCount;
854 <<
"Unrolled size exceeds threshold; reducing count "
855 <<
"from " <<
Count <<
" to " << NewCount <<
".\n");
876 <<
"Will not partially unroll: no profitable count.\n");
886 <<
"Partially unrolling with count: " <<
Count <<
"\n");
899 <<
"Not runtime unrolling: disabled by pragma.\n");
906 << MaxTripCount <<
" is small (<= "
912 if (L->getHeader()->getParent()->hasProfileData()) {
914 if (*ProfileTripCount < Opts.flat_loop_tripcount_threshold)
922 <<
"Will not try to unroll loop with runtime trip count "
923 <<
"because -unroll-runtime not given\n");
935 unsigned OrigCount =
Count;
939 while (
Count != 0 && TripMultiple %
Count != 0)
942 <<
"Remainder loop is restricted (that could be architecture "
943 "specific or because the loop contains a convergent "
944 "instruction), so unroll count must divide the trip "
946 << TripMultiple <<
". Reducing unroll count from " << OrigCount
947 <<
" to " <<
Count <<
".\n");
953 if (MaxTripCount &&
Count > MaxTripCount)
954 Count = MaxTripCount;
960 <<
"Runtime unrolling with count: " <<
Count <<
"\n");
975 const unsigned MaxTripCount,
const bool MaxOrZero,
984 << TripCount <<
", MaxTripCount=" << MaxTripCount
985 << (MaxOrZero ?
" (MaxOrZero)" :
"")
986 <<
", TripMultiple=" << TripMultiple <<
"\n");
991 dbgs().
indent(1) <<
"Explicit unroll requested:";
993 dbgs() <<
" user-count";
995 dbgs() <<
" pragma-full";
999 dbgs() <<
" pragma-enable";
1007 if (Opts.unroll_count) {
1009 "explicit unroll count");
1012 <<
"Using explicit peel count: " << PP.
PeelCount <<
".\n");
1028 if (
auto UnrollFactor =
1030 MaxTripCount, UCE, UP, ORE)) {
1035 return *UnrollFactor;
1051 if (
auto UnrollFactor =
1053 return *UnrollFactor;
1069 if (!TripCount && MaxTripCount && (UP.
UpperBound || MaxOrZero) &&
1071 if (
auto UnrollFactor =
1073 return *UnrollFactor;
1081 <<
"Peeling with count: " << PP.
PeelCount <<
".\n");
1095 return *UnrollFactor;
1097 "All cases when TripCount is constant should be covered here.");
1110 bool OnlyFullUnroll,
bool OnlyWhenForced,
bool ForgetAllSCEV,
1111 bool PrepareForLTO, std::optional<unsigned> ProvidedThreshold,
1112 std::optional<bool> ProvidedAllowPartial,
1113 std::optional<bool> ProvidedRuntime,
1114 std::optional<bool> ProvidedUpperBound,
1115 std::optional<bool> ProvidedAllowPeeling,
1116 std::optional<bool> ProvidedAllowProfileBasedPeeling,
1117 std::optional<unsigned> ProvidedFullUnrollMaxCount,
1121 << L->getHeader()->getParent()->getName() <<
"] Loop %"
1122 << L->getHeader()->getName()
1123 <<
" (depth=" << L->getLoopDepth() <<
")\n");
1135 Loop *ParentL = L->getParentLoop();
1136 if (ParentL !=
nullptr &&
1140 <<
" llvm.loop.unroll_and_jam.\n");
1151 <<
"Not unrolling loop since it has llvm.loop.unroll_and_jam.\n");
1155 if (!L->isLoopSimplifyForm()) {
1157 <<
"Not unrolling loop which is not in loop-simplify form.\n");
1161 L->getStartLoc(), L->getHeader())
1162 <<
"unable to unroll loop: not in loop-simplify form";
1170 if (OnlyWhenForced && !(TM &
TM_Enable)) {
1172 <<
"disabled and loop not explicitly "
1177 bool OptForSize = L->getHeader()->getParent()->hasOptSize();
1179 L, SE,
TTI, BFI, PSI, ORE, OptLevel, ProvidedThreshold,
1180 ProvidedAllowPartial, ProvidedRuntime, ProvidedUpperBound,
1181 ProvidedFullUnrollMaxCount);
1183 L, SE,
TTI, ProvidedAllowPeeling, ProvidedAllowProfileBasedPeeling,
true);
1193 L->getStartLoc(), L->getHeader())
1194 <<
"unable to unroll loop: unroll threshold is zero";
1209 TripCountIsUniform);
1223 <<
"Not unrolling loop with inlinable calls.\n");
1227 "InlineCandidatesPreventUnroll",
1228 L->getStartLoc(), L->getHeader())
1229 <<
"unable to unroll loop: contains inlinable calls";
1240 unsigned TripCount = 0;
1241 unsigned TripMultiple = 1;
1243 L->getExitingBlocks(ExitingBlocks);
1244 for (
BasicBlock *ExitingBlock : ExitingBlocks)
1246 if (!TripCount || TC < TripCount)
1247 TripCount = TripMultiple = TC;
1253 BasicBlock *ExitingBlock = L->getLoopLatch();
1254 if (!ExitingBlock || !L->isLoopExiting(ExitingBlock))
1255 ExitingBlock = L->getExitingBlock();
1268 unsigned MaxTripCount = 0;
1269 bool MaxOrZero =
false;
1279 MaxTripCount, MaxOrZero, TripMultiple, UCE, UP, PP);
1282 <<
"Not unrolling: no viable strategy found.\n");
1286 L->getStartLoc(), L->getHeader())
1287 <<
"unable to unroll loop: no viable unroll count found";
1296 assert(
Count == 1 &&
"Cannot perform peel and unroll in the same step");
1297 LLVM_DEBUG(
dbgs() <<
"PEELING loop %" << L->getHeader()->getName()
1298 <<
" with iteration count " << PP.
PeelCount <<
"!\n");
1314 L->setLoopAlreadyUnrolled();
1319 if (OnlyFullUnroll && ((!TripCount && !MaxTripCount) ||
Count < TripCount ||
1320 Count < MaxTripCount)) {
1322 <<
"Not attempting partial/runtime unroll in FullLoopUnroll.\n");
1331 UP.
Runtime &= TripCount == 0 && TripMultiple %
Count != 0;
1334 MDNode *OrigLoopID = L->getLoopID();
1336 DebugLoc LoopStartLoc = L->getStartLoc();
1340 Loop *RemainderLoop =
nullptr;
1353 L, ULO, LI, &SE, &DT, &AC, &
TTI, &ORE, PreserveLCSSA, &RemainderLoop,
AA);
1357 <<
"Failed to unroll loop as explicitly requested.\n");
1360 LoopStartLoc, LoopHeader)
1361 <<
"failed to unroll loop as explicitly requested";
1370 LoopStartLoc, LoopHeader)
1371 <<
"unable to fully unroll loop as directed; "
1372 <<
"unrolled by factor " <<
ore::NV(
"UnrollCount", ULO.
Count);
1378 LoopStartLoc, LoopHeader)
1379 <<
"unable to unroll loop with requested count "
1381 <<
"; unrolled by factor " <<
ore::NV(
"UnrollCount", ULO.
Count);
1385 if (RemainderLoop) {
1386 std::optional<MDNode *> RemainderLoopID =
1389 if (RemainderLoopID)
1390 RemainderLoop->
setLoopID(*RemainderLoopID);
1394 std::optional<MDNode *> NewLoopID =
1398 L->setLoopID(*NewLoopID);
1402 return UnrollResult;
1409 L->setLoopAlreadyUnrolled();
1411 return UnrollResult;
1416class LoopUnroll :
public LoopPass {
1425 bool OnlyWhenForced;
1432 std::optional<unsigned> ProvidedThreshold;
1433 std::optional<bool> ProvidedAllowPartial;
1434 std::optional<bool> ProvidedRuntime;
1435 std::optional<bool> ProvidedUpperBound;
1436 std::optional<bool> ProvidedAllowPeeling;
1437 std::optional<bool> ProvidedAllowProfileBasedPeeling;
1438 std::optional<unsigned> ProvidedFullUnrollMaxCount;
1440 LoopUnroll(
int OptLevel = 2,
bool OnlyWhenForced =
false,
1441 bool ForgetAllSCEV =
false,
1442 std::optional<unsigned> Threshold = std::nullopt,
1443 std::optional<bool> AllowPartial = std::nullopt,
1444 std::optional<bool>
Runtime = std::nullopt,
1445 std::optional<bool> UpperBound = std::nullopt,
1446 std::optional<bool> AllowPeeling = std::nullopt,
1447 std::optional<bool> AllowProfileBasedPeeling = std::nullopt,
1448 std::optional<unsigned> ProvidedFullUnrollMaxCount = std::nullopt)
1449 : LoopPass(
ID), OptLevel(OptLevel), OnlyWhenForced(OnlyWhenForced),
1450 ForgetAllSCEV(ForgetAllSCEV), ProvidedThreshold(Threshold),
1451 ProvidedAllowPartial(AllowPartial), ProvidedRuntime(
Runtime),
1452 ProvidedUpperBound(UpperBound), ProvidedAllowPeeling(AllowPeeling),
1453 ProvidedAllowProfileBasedPeeling(AllowProfileBasedPeeling),
1454 ProvidedFullUnrollMaxCount(ProvidedFullUnrollMaxCount) {
1458 bool runOnLoop(
Loop *L, LPPassManager &LPM)
override {
1464 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1465 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1466 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1467 const TargetTransformInfo &
TTI =
1468 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1469 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
1472 ? &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo()
1477 OptimizationRemarkEmitter ORE(&
F);
1478 bool PreserveLCSSA = mustPreserveAnalysisID(
LCSSAID);
1481 L, DT, LI, SE,
TTI, AC, ORE,
nullptr,
nullptr, PreserveLCSSA, OptLevel,
1482 false, OnlyWhenForced, ForgetAllSCEV,
1483 false, ProvidedThreshold, ProvidedAllowPartial,
1484 ProvidedRuntime, ProvidedUpperBound, ProvidedAllowPeeling,
1485 ProvidedAllowProfileBasedPeeling, ProvidedFullUnrollMaxCount, UI);
1487 if (Result == LoopUnrollResult::FullyUnrolled)
1490 return Result != LoopUnrollResult::Unmodified;
1495 void getAnalysisUsage(AnalysisUsage &AU)
const override {
1507char LoopUnroll::ID = 0;
1517 bool ForgetAllSCEV,
int Threshold,
1518 int AllowPartial,
int Runtime,
int UpperBound,
1523 return new LoopUnroll(
1524 OptLevel, OnlyWhenForced, ForgetAllSCEV,
1525 Threshold == -1 ? std::nullopt : std::optional<unsigned>(Threshold),
1526 AllowPartial == -1 ? std::nullopt : std::optional<bool>(AllowPartial),
1528 UpperBound == -1 ? std::nullopt : std::optional<bool>(UpperBound),
1529 AllowPeeling == -1 ? std::nullopt : std::optional<bool>(AllowPeeling));
1543 Loop *ParentL = L.getParentLoop();
1550 std::string LoopName = std::string(L.getName());
1555 true, OptLevel,
true,
1556 OnlyWhenForced, ForgetSCEV, PrepareForLTO,
1557 std::nullopt,
false,
1588 bool IsCurrentLoopValid =
false;
1595 if (SibLoop == &L) {
1596 IsCurrentLoopValid =
true;
1605 if (!IsCurrentLoopValid) {
1609 if (Opts.unroll_revisit_child_loops) {
1638 if (
auto *LAMProxy = AM.
getCachedResult<LoopAnalysisManagerFunctionProxy>(
F))
1639 LAM = &LAMProxy->getManager();
1644 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
1654 for (
const auto &L : LI) {
1670 for (
const Loop *TopL : LI)
1671 TopLevelNestSize[TopL] = TopL->getLoopsInPreorder().
size();
1673 while (!Worklist.
empty()) {
1680 Loop *ParentL = L.getParentLoop();
1686 std::optional<bool> LocalAllowPeeling = UnrollOpts.AllowPeeling;
1687 if (PSI && PSI->hasHugeWorkingSetSize())
1688 LocalAllowPeeling =
false;
1695 std::optional<bool> LocalAllowRuntime = UnrollOpts.AllowRuntime;
1696 std::optional<bool> LocalAllowPartial = UnrollOpts.AllowPartial;
1698 unsigned NestSize = TopLevelNestSize.
lookup(L.getOutermostLoop());
1699 if (NestSize > MaxNestLoops) {
1700 LocalAllowRuntime =
false;
1701 LocalAllowPartial =
false;
1702 LocalAllowPeeling =
false;
1704 <<
"Disabling runtime/partial unroll and peeling: "
1705 "outermost nest has "
1706 << NestSize <<
" loops (> " << MaxNestLoops <<
").\n");
1710 std::string LoopName = std::string(L.getName());
1715 true, UnrollOpts.OptLevel,
1716 false, UnrollOpts.OnlyWhenForced,
1717 UnrollOpts.ForgetSCEV, UnrollOpts.PrepareForLTO,
1718 std::nullopt, LocalAllowPartial,
1719 LocalAllowRuntime, UnrollOpts.AllowUpperBound,
1720 LocalAllowPeeling, UnrollOpts.AllowProfileBasedPeeling,
1721 UnrollOpts.FullUnrollMaxCount, UI, &
AA);
1732 LAM->clear(L, LoopName);
1743 static_cast<PassInfoMixin<LoopUnrollPass> *
>(
this)->
printPipeline(
1744 OS, MapClassName2PassName);
1746 if (UnrollOpts.AllowPartial != std::nullopt)
1747 OS << (*UnrollOpts.AllowPartial ?
"" :
"no-") <<
"partial;";
1748 if (UnrollOpts.AllowPeeling != std::nullopt)
1749 OS << (*UnrollOpts.AllowPeeling ?
"" :
"no-") <<
"peeling;";
1750 if (UnrollOpts.AllowRuntime != std::nullopt)
1751 OS << (*UnrollOpts.AllowRuntime ?
"" :
"no-") <<
"runtime;";
1752 if (UnrollOpts.AllowUpperBound != std::nullopt)
1753 OS << (*UnrollOpts.AllowUpperBound ?
"" :
"no-") <<
"upperbound;";
1754 if (UnrollOpts.AllowProfileBasedPeeling != std::nullopt)
1755 OS << (*UnrollOpts.AllowProfileBasedPeeling ?
"" :
"no-")
1756 <<
"profile-peeling;";
1757 if (UnrollOpts.FullUnrollMaxCount != std::nullopt)
1758 OS <<
"full-unroll-max=" << UnrollOpts.FullUnrollMaxCount <<
';';
1759 if (UnrollOpts.PrepareForLTO)
1760 OS <<
"prepare-for-lto;";
1761 OS <<
'O' << UnrollOpts.OptLevel;
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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 defines various interfaces for pass management in LLVM.
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 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, bool PrepareForLTO, 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, UniformityInfo *UI=nullptr, AAResults *AA=nullptr)
static bool hasUnrollFullPragma(const Loop *L)
static bool isSCEVUniform(const SCEV *S, UniformityInfo &UI)
Returns true if the SCEV expression is uniform, i.e., all threads in a convergent execution agree on ...
static unsigned unrollCountPragmaValue(const Loop *L)
static bool hasUnrollEnablePragma(const Loop *L)
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 std::optional< unsigned > shouldPragmaUnroll(const ScalarOptions &Opts, Loop *L, const UnrollPragmaInfo &PInfo, const unsigned TripMultiple, const unsigned TripCount, unsigned MaxTripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP, OptimizationRemarkEmitter *ORE)
static std::optional< unsigned > shouldPartialUnroll(const unsigned LoopSize, const unsigned TripCount, const UnrollCostEstimator UCE, const TargetTransformInfo::UnrollingPreferences &UP)
static const unsigned NoThreshold
A magic value for use with the Threshold parameter to indicate that the loop unroll should be perform...
static unsigned shouldRuntimeUnroll(Loop *L, unsigned MaxTripCount, unsigned TripMultiple, const UnrollCostEstimator &UCE, const UnrollPragmaInfo &PInfo, const ScalarOptions &Opts, TargetTransformInfo::UnrollingPreferences &UP)
static bool hasRuntimeUnrollDisablePragma(const Loop *L)
static unsigned getFullUnrollBoostingFactor(const EstimatedUnrollCost &Cost, unsigned MaxPercentThresholdBoost)
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
A manager for alias analyses.
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.
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; assumes that the block is well-formed.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional Branch instruction.
This is the shared class of boolean and integer constants.
This is an important base class in LLVM.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
ValueT lookup(const_arg_type_t< KeyT > Val) const
Return the entry for the specified key, or a default constructed value if no such entry exists.
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).
CostType getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
LLVM_ABI 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.
LLVM_ABI PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Represents a single loop in the control flow graph.
LLVM_ABI 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.
static LLVM_ABI 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.
This class represents an analyzed expression in the program.
LLVM_ABI ArrayRef< SCEVUse > operands() const
Return operands of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getBackedgeTakenCount(const Loop *L, ExitCountKind Kind=Exact)
If the specified loop has a predictable backedge-taken count, return it, otherwise return a SCEVCould...
LLVM_ABI unsigned getSmallConstantTripMultiple(const Loop *L, const SCEV *ExitCount)
Returns the largest constant divisor of the trip count as a normal unsigned value,...
LLVM_ABI unsigned getSmallConstantMaxTripCount(const Loop *L, SmallVectorImpl< const SCEVPredicate * > *Predicates=nullptr)
Returns the upper bound of the loop trip count as a normal unsigned value.
LLVM_ABI bool isBackedgeTakenCountMaxOrZero(const Loop *L)
Return true if the backedge taken count is either the value returned by getConstantMaxBackedgeTakenCo...
LLVM_ABI 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...
void insert_range(Range &&R)
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)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
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.
ConvergenceKind Convergence
bool ConvergenceAllowsRuntime
LLVM_ABI bool canUnroll(OptimizationRemarkEmitter *ORE=nullptr, const Loop *L=nullptr) const
Whether it is legal to unroll this loop.
LLVM_ABI uint64_t getUnrolledLoopSize(const TargetTransformInfo::UnrollingPreferences &UP, unsigned Count) const
Returns loop size estimation for an unrolled loop with the given unroll count and the unrolling confi...
unsigned NumInlineCandidates
LLVM_ABI UnrollCostEstimator(const Loop *L, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, unsigned BEInsns, bool PrepareForLTO=false, bool TripCountIsUniform=false)
uint64_t getRolledLoopSize() const
void visit(Iterator Start, Iterator End)
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.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Abstract Attribute helper functions.
std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)
Extract a Value from Metadata.
DiagnosticInfoOptimizationBase::Argument NV
This is an optimization pass for GlobalISel generic memory operations.
GenericUniformityInfo< SSAContext > UniformityInfo
LLVM_ABI Pass * createLoopUnrollPass(int OptLevel=2, bool OnlyWhenForced=false, bool ForgetAllSCEV=false, int Threshold=-1, int AllowPartial=-1, int Runtime=-1, int UpperBound=-1, int AllowPeeling=-1)
LLVM_ABI std::optional< unsigned > getLoopEstimatedTripCount(Loop *L, unsigned *EstimatedLoopInvocationWeight=nullptr)
Return either:
LLVM_ABI unsigned 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 isEqual(const GCNRPTracker::LiveRegSet &S1, const GCNRPTracker::LiveRegSet &S2)
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
@ Runtime
Detect stack use after return if not disabled runtime with (ASAN_OPTIONS=detect_stack_use_after_retur...
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI, ScalarEvolution *SE)
Put a loop nest into LCSSA form.
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI 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< 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...
LLVM_ABI void simplifyLoopAfterUnroll(Loop *L, bool SimplifyIVs, LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT, AssumptionCache *AC, const TargetTransformInfo *TTI, ArrayRef< BasicBlock * > Blocks, AAResults *AA=nullptr)
Perform some cleanup and simplifications on loops after unrolling.
const ScalarOptions & getScalarOptions(const LLVMContext &C)
AnalysisManager< Loop, LoopStandardAnalysisResults & > LoopAnalysisManager
The loop analysis manager.
LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA, const TargetTransformInfo *TTI=nullptr)
Simplify each loop in a loop nest recursively.
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.
LLVM_ABI void initializeLoopUnrollPass(PassRegistry &)
LLVM_ABI TargetTransformInfo::PeelingPreferences gatherPeelingPreferences(Loop *L, ScalarEvolution &SE, const TargetTransformInfo &TTI, std::optional< bool > UserAllowPeeling, std::optional< bool > UserAllowProfileBasedPeeling, bool UnrollingSpecficValues=false)
LLVM_ABI CallBase * getLoopConvergenceHeart(const Loop *TheLoop)
Find the convergence heart of the loop.
LLVM_ABI bool getForgetSCEVInLoopUnroll(const cl::LibraryOptionsContext &LibraryOptions)
Return -forget-scev-loop-unroll.
LLVM_ABI TransformationMode hasUnrollAndJamTransformation(const Loop *L)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI void computePeelCount(Loop *L, unsigned LoopSize, TargetTransformInfo::PeelingPreferences &PP, unsigned TripCount, DominatorTree &DT, ScalarEvolution &SE, const TargetTransformInfo &TTI, AssumptionCache *AC=nullptr, unsigned Threshold=UINT_MAX)
LLVM_TEMPLATE_ABI void appendLoopsToWorklist(RangeT &&, SmallPriorityWorklist< Loop *, 4 > &)
Utility that implements appending of loops onto a worklist given a range.
LLVM_ABI cl::opt< unsigned > SCEVCheapExpansionBudget
LLVM_ABI 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 isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI void getLoopAnalysisUsage(AnalysisUsage &AU)
Helper to consistently add the set of standard passes to a loop pass's AnalysisUsage.
LLVM_ABI void peelLoop(Loop *L, unsigned PeelCount, bool PeelLast, 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...
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
LLVM_ABI MDNode * getUnrollMetadataForLoop(const Loop *L, StringRef Name)
DWARFExpression::Operation Op
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
const char *const LLVMLoopUnrollFollowupRemainder
LLVM_ABI 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...
constexpr bool valueOr(BoolOrDefault X, bool Default)
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI 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, AAResults *AA=nullptr)
Unroll the given loop by Count.
LLVM_ABI void reportFatalUsageError(Error Err)
Report a fatal error that does not indicate a bug in LLVM.
Utility to calculate the size and a few similar metrics for a set of basic blocks.
static LLVM_ABI 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
const Instruction * Heart
bool RuntimeUnrollMultiExit
bool AllowExpensiveTripCount
bool AddAdditionalAccumulators
unsigned SCEVExpansionBudget
const bool PragmaFullUnroll
LLVM_ABI UnrollPragmaInfo(const Loop *L)
const unsigned PragmaCount
const bool ExplicitUnroll
const bool PragmaRuntimeUnrollDisable
const bool UserUnrollCount
const bool PragmaEnableUnroll