83using namespace PatternMatch;
85#define DEBUG_TYPE "indvars"
88STATISTIC(NumReplaced ,
"Number of exit values replaced");
89STATISTIC(NumLFTR ,
"Number of loop exit tests replaced");
90STATISTIC(NumElimExt ,
"Number of IV sign/zero extends eliminated");
91STATISTIC(NumElimIV ,
"Number of congruent IVs eliminated");
95 cl::desc(
"Choose the strategy to replace exit value in IndVarSimplify"),
99 "only replace exit value when the cost is cheap"),
102 "only replace exit value when it is an unused "
103 "induction variable in the loop and has cheap replacement cost"),
105 "only replace exit values when loop def likely dead"),
107 "always replace exit value whenever possible")));
111 cl::desc(
"Use post increment control-dependent ranges in IndVarSimplify"),
116 cl::desc(
"Disable Linear Function Test Replace optimization"));
120 cl::desc(
"Predicate conditions in read only loops"));
124 cl::desc(
"Allow widening of indvars to eliminate s/zext"));
128class IndVarSimplify {
135 std::unique_ptr<MemorySSAUpdater> MSSAU;
141 bool rewriteNonIntegerIVs(
Loop *L);
147 bool canonicalizeExitCondition(
Loop *L);
154 bool rewriteFirstIterationLoopExitValues(
Loop *L);
157 const SCEV *ExitCount,
160 bool sinkUnusedInvariants(
Loop *L);
166 : LI(LI), SE(SE), DT(DT),
DL(
DL), TLI(TLI),
TTI(
TTI),
167 WidenIndVars(WidenIndVars) {
169 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
183 bool isExact =
false;
187 APFloat::rmTowardZero, &isExact) != APFloat::opOK ||
202bool IndVarSimplify::handleFloatingPointIV(
Loop *L,
PHINode *PN) {
204 unsigned BackEdge = IncomingEdge^1;
207 auto *InitValueVal = dyn_cast<ConstantFP>(PN->
getIncomingValue(IncomingEdge));
210 if (!InitValueVal || !
ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
216 if (Incr ==
nullptr || Incr->getOpcode() != Instruction::FAdd)
return false;
220 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
222 if (IncValueVal ==
nullptr || Incr->getOperand(0) != PN ||
230 if (IncrUse == Incr->user_end())
return false;
232 if (IncrUse != Incr->user_end())
return false;
238 Compare = dyn_cast<FCmpInst>(U2);
239 if (!Compare || !
Compare->hasOneUse() ||
240 !isa<BranchInst>(
Compare->user_back()))
259 if (ExitValueVal ==
nullptr ||
265 switch (
Compare->getPredicate()) {
266 default:
return false;
288 if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
299 if (InitValue >= ExitValue)
306 if (++Range == 0)
return false;
320 if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
325 if (InitValue <= ExitValue)
332 if (++Range == 0)
return false;
346 if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
359 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(
Int32Ty, IncValue),
360 Incr->getName() +
".int", Incr->getIterator());
374 Compare->replaceAllUsesWith(NewCompare);
397bool IndVarSimplify::rewriteNonIntegerIVs(
Loop *L) {
404 for (
PHINode &PN : Header->phis())
407 bool Changed =
false;
409 if (
PHINode *PN = dyn_cast_or_null<PHINode>(&*
PHI))
410 Changed |= handleFloatingPointIV(L, PN);
429bool IndVarSimplify::rewriteFirstIterationLoopExitValues(
Loop *L) {
434 L->getUniqueExitBlocks(ExitBlocks);
436 bool MadeAnyChanges =
false;
437 for (
auto *ExitBB : ExitBlocks) {
440 for (
PHINode &PN : ExitBB->phis()) {
442 IncomingValIdx !=
E; ++IncomingValIdx) {
450 if (!
L->getLoopLatch() ||
451 !DT->dominates(IncomingBB,
L->getLoopLatch()))
458 if (
auto *BI = dyn_cast<BranchInst>(TermInst)) {
461 Cond = BI->getCondition();
462 }
else if (
auto *SI = dyn_cast<SwitchInst>(TermInst))
463 Cond =
SI->getCondition();
467 if (!
L->isLoopInvariant(
Cond))
473 if (!ExitVal || ExitVal->getParent() !=
L->getHeader())
479 auto *LoopPreheader =
L->getLoopPreheader();
480 assert(LoopPreheader &&
"Invalid loop");
481 int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
482 if (PreheaderIdx != -1) {
483 assert(ExitVal->getParent() ==
L->getHeader() &&
484 "ExitVal must be in loop header");
485 MadeAnyChanges =
true;
487 ExitVal->getIncomingValue(PreheaderIdx));
488 SE->forgetValue(&PN);
493 return MadeAnyChanges;
506 bool IsSigned = Cast->
getOpcode() == Instruction::SExt;
507 if (!IsSigned && Cast->
getOpcode() != Instruction::ZExt)
520 if (NarrowIVWidth >= Width)
560class IndVarSimplifyVisitor :
public IVVisitor {
587bool IndVarSimplify::simplifyAndExtend(
Loop *L,
592 auto *GuardDecl =
L->getBlocks()[0]->getModule()->getFunction(
594 bool HasGuards = GuardDecl && !GuardDecl->use_empty();
597 for (
PHINode &PN :
L->getHeader()->phis())
604 bool Changed =
false;
605 while (!LoopPhis.
empty()) {
616 IndVarSimplifyVisitor Visitor(CurrIV, SE,
TTI, DT);
621 if (Visitor.WI.WidestNativeType) {
624 }
while(!LoopPhis.
empty());
634 DT, DeadInsts, ElimExt, Widened,
636 NumElimExt += ElimExt;
637 NumWidened += Widened;
659 case Instruction::Add:
660 case Instruction::Sub:
662 case Instruction::GetElementPtr:
672 if (Phi && Phi->getParent() == L->getHeader()) {
677 if (IncI->
getOpcode() == Instruction::GetElementPtr)
682 if (Phi && Phi->getParent() == L->getHeader()) {
705 assert(L->getLoopLatch() &&
"Must be in simplified form");
722 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
728 if (!L->isLoopInvariant(
RHS)) {
729 if (!L->isLoopInvariant(
LHS))
742 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
747 Value *IncV = Phi->getIncomingValue(
Idx);
756 if (isa<Constant>(V))
757 return !isa<UndefValue>(V);
769 if(
I->mayReadFromMemory() || isa<CallInst>(
I) || isa<InvokeInst>(
I))
798 assert(Phi->getParent() == L->getHeader());
799 assert(L->getLoopLatch());
809 if (!Step || !Step->
isOne())
812 int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());
813 Value *IncV = Phi->getIncomingValue(LatchIdx);
815 isa<SCEVAddRecExpr>(SE->
getSCEV(IncV)));
834 const SCEV *BestInit =
nullptr;
836 assert(LatchBlock &&
"Must be in simplified form");
837 const DataLayout &
DL = L->getHeader()->getModule()->getDataLayout();
844 const auto *AR = cast<SCEVAddRecExpr>(SE->
getSCEV(Phi));
850 if (PhiWidth < BCWidth || !
DL.isLegalInteger(PhiWidth))
859 Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);
873 if (!Phi->getType()->isIntegerTy() &&
893 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->
getType()))
906 const SCEV *ExitCount,
bool UsePostInc,
Loop *L,
922 if (!isa<SCEVConstant>(IVInit) || !isa<SCEVConstant>(ExitCount))
929 "Computed iteration count is not loop invariant!");
941 const SCEV *ExitCount,
943 assert(
L->getLoopLatch() &&
"Loop no longer in simplified form?");
949 Value *CmpIndVar = IndVar;
950 bool UsePostInc =
false;
955 if (ExitingBB ==
L->getLoopLatch()) {
982 if (
auto *BO = dyn_cast<BinaryOperator>(IncVar)) {
983 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));
984 if (BO->hasNoUnsignedWrap())
986 if (BO->hasNoSignedWrap())
991 IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);
994 "genLoopLimit missed a cast");
1000 P = ICmpInst::ICMP_NE;
1002 P = ICmpInst::ICMP_EQ;
1009 Builder.SetCurrentDebugLocation(
Cond->getDebugLoc());
1016 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->
getType());
1017 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->
getType());
1018 if (CmpIndVarSize > ExitCntSize) {
1028 const SCEV *
IV = SE->getSCEV(CmpIndVar);
1029 const SCEV *TruncatedIV = SE->getTruncateExpr(
IV, ExitCnt->
getType());
1030 const SCEV *ZExtTrunc =
1031 SE->getZeroExtendExpr(TruncatedIV, CmpIndVar->
getType());
1033 if (ZExtTrunc ==
IV) {
1035 ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->
getType(),
1038 const SCEV *SExtTrunc =
1039 SE->getSignExtendExpr(TruncatedIV, CmpIndVar->
getType());
1040 if (SExtTrunc ==
IV) {
1042 ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->
getType(),
1049 L->makeLoopInvariant(ExitCnt, Discard);
1051 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->
getType(),
1054 LLVM_DEBUG(
dbgs() <<
"INDVARS: Rewriting loop exit condition to:\n"
1055 <<
" LHS:" << *CmpIndVar <<
'\n'
1056 <<
" op:\t" << (
P == ICmpInst::ICMP_NE ?
"!=" :
"==")
1058 <<
" RHS:\t" << *ExitCnt <<
"\n"
1059 <<
"ExitCount:\t" << *ExitCount <<
"\n"
1062 Value *
Cond = Builder.CreateICmp(
P, CmpIndVar, ExitCnt,
"exitcond");
1070 DeadInsts.emplace_back(OrigCond);
1083bool IndVarSimplify::sinkUnusedInvariants(
Loop *L) {
1085 if (!ExitBlock)
return false;
1088 if (!Preheader)
return false;
1090 bool MadeAnyChanges =
false;
1093 while (
I != Preheader->
begin()) {
1096 if (isa<PHINode>(
I))
1105 if (
I->mayHaveSideEffects() ||
I->mayReadFromMemory())
1109 if (isa<DbgInfoIntrinsic>(
I))
1120 if (isa<AllocaInst>(
I))
1125 bool UsedInLoop =
false;
1126 for (
Use &U :
I->uses()) {
1132 UseBB =
P->getIncomingBlock(i);
1134 if (UseBB == Preheader ||
L->contains(UseBB)) {
1148 if (
I != Preheader->
begin()) {
1152 }
while (
I->isDebugOrPseudoInst() &&
I != Preheader->
begin());
1154 if (
I->isDebugOrPseudoInst() &&
I == Preheader->
begin())
1160 MadeAnyChanges =
true;
1162 SE->forgetValue(ToMove);
1167 return MadeAnyChanges;
1173 LLVM_DEBUG(
dbgs() <<
"Replacing condition of loop-exiting branch " << *BI
1174 <<
" with " << *NewCond <<
"\n");
1176 if (OldCond->use_empty())
1183 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1185 return ConstantInt::get(OldCond->getType(),
1186 IsTaken ? ExitIfTrue : !ExitIfTrue);
1199 assert(L->isLoopSimplifyForm() &&
"Should only do it in simplify form!");
1200 auto *LoopPreheader = L->getLoopPreheader();
1201 auto *LoopHeader = L->getHeader();
1203 for (
auto &PN : LoopHeader->phis()) {
1206 Worklist.
push_back(cast<Instruction>(U));
1215 while (!Worklist.
empty()) {
1217 if (!Visited.
insert(
I).second)
1221 if (!L->contains(
I))
1226 for (
User *U :
I->users())
1227 Worklist.
push_back(cast<Instruction>(U));
1228 I->replaceAllUsesWith(Res);
1239 BasicBlock *Preheader = L->getLoopPreheader();
1240 assert(Preheader &&
"Preheader doesn't exist");
1244 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1246 InvariantPred = ICmpInst::getInversePredicate(InvariantPred);
1249 return Builder.
CreateICmp(InvariantPred, LHSV, RHSV,
1253static std::optional<Value *>
1255 const SCEV *MaxIter,
bool Inverted,
bool SkipLastIter,
1273 auto *MaxIterTy = MaxIter->
getType();
1290 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter)) {
1291 for (
auto *
Op :
UMin->operands())
1302 return std::nullopt;
1317 "Not a loop exit!");
1330 auto GoThrough = [&](
Value *V) {
1351 if (!GoThrough(Curr))
1352 if (
auto *ICmp = dyn_cast<ICmpInst>(Curr))
1354 }
while (!Worklist.
empty());
1361 if (!SkipLastIter && LeafConditions.
size() > 1 &&
1363 ScalarEvolution::ExitCountKind::SymbolicMaximum) ==
1365 for (
auto *ICmp : LeafConditions) {
1369 if (isa<SCEVCouldNotCompute>(ExitMax))
1377 if (WideExitMax == WideMaxIter)
1378 ICmpsFailingOnLastIter.
insert(ICmp);
1381 bool Changed =
false;
1382 for (
auto *OldCond : LeafConditions) {
1387 bool OptimisticSkipLastIter = SkipLastIter;
1388 if (!OptimisticSkipLastIter) {
1389 if (ICmpsFailingOnLastIter.
size() > 1)
1390 OptimisticSkipLastIter =
true;
1391 else if (ICmpsFailingOnLastIter.
size() == 1)
1392 OptimisticSkipLastIter = !ICmpsFailingOnLastIter.
count(OldCond);
1396 OptimisticSkipLastIter, SE,
Rewriter)) {
1398 auto *NewCond = *Replaced;
1399 if (
auto *NCI = dyn_cast<Instruction>(NewCond)) {
1400 NCI->setName(OldCond->
getName() +
".first_iter");
1402 LLVM_DEBUG(
dbgs() <<
"Unknown exit count: Replacing " << *OldCond
1403 <<
" with " << *NewCond <<
"\n");
1409 ICmpsFailingOnLastIter.
erase(OldCond);
1415bool IndVarSimplify::canonicalizeExitCondition(
Loop *L) {
1426 L->getExitingBlocks(ExitingBlocks);
1427 bool Changed =
false;
1428 for (
auto *ExitingBB : ExitingBlocks) {
1429 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1435 if (!ICmp || !ICmp->hasOneUse())
1438 auto *
LHS = ICmp->getOperand(0);
1439 auto *
RHS = ICmp->getOperand(1);
1443 if (!
L->isLoopInvariant(RHS)) {
1444 if (!
L->isLoopInvariant(LHS))
1451 Value *LHSOp =
nullptr;
1456 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1457 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1458 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1459 FullCR = FullCR.zeroExtend(OuterBitWidth);
1460 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1461 if (FullCR.contains(RHSCR)) {
1464 ICmp->setPredicate(ICmp->getUnsignedPredicate());
1474 for (
auto *ExitingBB : ExitingBlocks) {
1475 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1481 if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned())
1484 bool Swapped =
false;
1485 auto *
LHS = ICmp->getOperand(0);
1486 auto *
RHS = ICmp->getOperand(1);
1487 if (
L->isLoopInvariant(LHS) ==
L->isLoopInvariant(RHS))
1490 if (
L->isLoopInvariant(LHS)) {
1496 assert(!
L->isLoopInvariant(LHS) &&
L->isLoopInvariant(RHS));
1501 Value *LHSOp =
nullptr;
1511 if (!
LHS->
hasOneUse() && !isa<SCEVAddRecExpr>(SE->getSCEV(LHSOp)))
1518 auto doRotateTransform = [&]() {
1519 assert(ICmp->isUnsigned() &&
"must have proven unsigned already");
1521 Instruction::Trunc, RHS, LHSOp->
getType(),
"",
1522 L->getLoopPreheader()->getTerminator()->getIterator());
1523 ICmp->setOperand(Swapped ? 1 : 0, LHSOp);
1524 ICmp->setOperand(Swapped ? 0 : 1, NewRHS);
1526 DeadInsts.push_back(LHS);
1531 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1532 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1533 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1534 FullCR = FullCR.zeroExtend(OuterBitWidth);
1535 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1536 if (FullCR.contains(RHSCR)) {
1537 doRotateTransform();
1551 L->getExitingBlocks(ExitingBlocks);
1568 if (!DT->dominates(ExitingBB,
L->getLoopLatch()))
1575 if (!L->contains(BI->getSuccessor(CI->isNullValue())))
1576 replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, *SE);
1583 if (ExitingBlocks.
empty())
1587 const SCEV *MaxBECount = SE->getSymbolicMaxBackedgeTakenCount(L);
1588 if (isa<SCEVCouldNotCompute>(MaxBECount))
1597 if (
A ==
B)
return false;
1598 if (DT->properlyDominates(
A,
B))
1601 assert(DT->properlyDominates(B, A) &&
1602 "expected total dominance order!");
1607 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++) {
1608 assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]));
1612 bool Changed =
false;
1613 bool SkipLastIter =
false;
1614 const SCEV *CurrMaxExit = SE->getCouldNotCompute();
1615 auto UpdateSkipLastIter = [&](
const SCEV *MaxExitCount) {
1616 if (SkipLastIter || isa<SCEVCouldNotCompute>(MaxExitCount))
1618 if (isa<SCEVCouldNotCompute>(CurrMaxExit))
1619 CurrMaxExit = MaxExitCount;
1621 CurrMaxExit = SE->getUMinFromMismatchedTypes(CurrMaxExit, MaxExitCount);
1624 if (CurrMaxExit == MaxBECount)
1625 SkipLastIter =
true;
1628 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1629 const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBB);
1630 const SCEV *MaxExitCount = SE->getExitCount(
1631 L, ExitingBB, ScalarEvolution::ExitCountKind::SymbolicMaximum);
1632 if (isa<SCEVCouldNotCompute>(ExactExitCount)) {
1636 auto OptimizeCond = [&](
bool SkipLastIter) {
1638 MaxBECount, SkipLastIter,
1639 SE, Rewriter, DeadInsts);
1658 if (OptimizeCond(
false))
1660 else if (SkipLastIter && OptimizeCond(
true))
1662 UpdateSkipLastIter(MaxExitCount);
1666 UpdateSkipLastIter(ExactExitCount);
1673 if (ExactExitCount->
isZero()) {
1674 foldExit(L, ExitingBB,
true, DeadInsts);
1682 "Exit counts must be integers");
1685 SE->getWiderType(MaxBECount->
getType(), ExactExitCount->
getType());
1686 ExactExitCount = SE->getNoopOrZeroExtend(ExactExitCount, WiderType);
1687 MaxBECount = SE->getNoopOrZeroExtend(MaxBECount, WiderType);
1694 foldExit(L, ExitingBB,
false, DeadInsts);
1703 if (!DominatingExactExitCounts.
insert(ExactExitCount).second) {
1704 foldExit(L, ExitingBB,
false, DeadInsts);
1721 L->getExitingBlocks(ExitingBlocks);
1738 const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
1739 if (isa<SCEVCouldNotCompute>(ExactBTC) || !
Rewriter.isSafeToExpand(ExactBTC))
1742 assert(SE->isLoopInvariant(ExactBTC, L) &&
"BTC must be loop invariant");
1766 if (!ExitBlock->
phis().empty())
1769 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1770 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1771 !
Rewriter.isSafeToExpand(ExitCount))
1774 assert(SE->isLoopInvariant(ExitCount, L) &&
1775 "Exit count must be loop invariant");
1792 if (DT->properlyDominates(
A,
B))
return true;
1793 if (DT->properlyDominates(
B,
A))
return false;
1794 return A->getName() <
B->getName();
1799 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++)
1800 if (!DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]))
1805 for (
unsigned i = 0, e = ExitingBlocks.
size(); i < e; i++)
1806 if (BadExit(ExitingBlocks[i])) {
1811 if (ExitingBlocks.
empty())
1819 return DT->dominates(ExitingBB,
L->getLoopLatch());
1833 if (
I.mayHaveSideEffects())
1836 bool Changed =
false;
1847 Rewriter.setInsertPoint(
L->getLoopPreheader()->getTerminator());
1849 Value *ExactBTCV =
nullptr;
1850 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1851 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1855 if (ExitCount == ExactBTC) {
1857 B.getFalse() :
B.getTrue();
1861 ExactBTCV =
Rewriter.expandCodeFor(ExactBTC);
1865 ECV =
B.CreateZExt(ECV, WiderTy);
1866 RHS =
B.CreateZExt(RHS, WiderTy);
1869 ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
1870 NewCond =
B.CreateICmp(Pred, ECV, RHS);
1875 DeadInsts.emplace_back(OldCond);
1886bool IndVarSimplify::run(
Loop *L) {
1888 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
1889 "LCSSA required to run indvars!");
1900 if (!
L->isLoopSimplifyForm())
1903 bool Changed =
false;
1906 Changed |= rewriteNonIntegerIVs(L);
1921 Changed |= simplifyAndExtend(L, Rewriter, LI);
1930 NumReplaced += Rewrites;
1936 NumElimIV +=
Rewriter.replaceCongruentIVs(L, DT, DeadInsts,
TTI);
1940 Changed |= canonicalizeExitCondition(L);
1943 if (optimizeLoopExits(L, Rewriter)) {
1948 SE->forgetTopmostLoop(L);
1953 if (predicateLoopExits(L, Rewriter)) {
1965 L->getExitingBlocks(ExitingBlocks);
1966 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1980 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1981 if (isa<SCEVCouldNotCompute>(ExitCount))
2001 if (!
Rewriter.isSafeToExpand(ExitCount))
2004 Changed |= linearFunctionTestReplace(L, ExitingBB,
2016 while (!DeadInsts.empty()) {
2017 Value *
V = DeadInsts.pop_back_val();
2019 if (
PHINode *
PHI = dyn_cast_or_null<PHINode>(V))
2021 else if (
Instruction *Inst = dyn_cast_or_null<Instruction>(V))
2030 Changed |= sinkUnusedInvariants(L);
2035 Changed |= rewriteFirstIterationLoopExitValues(L);
2041 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
2042 "Indvars did not preserve LCSSA!");
2044 MSSAU->getMemorySSA()->verifyMemorySSA();
2052 Function *
F = L.getHeader()->getParent();
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file declares a class to represent arbitrary precision floating point values and provide a varie...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define clEnumValN(ENUMVAL, FLAGNAME, DESC)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
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
static Value * genLoopLimit(PHINode *IndVar, BasicBlock *ExitingBB, const SCEV *ExitCount, bool UsePostInc, Loop *L, SCEVExpander &Rewriter, ScalarEvolution *SE)
Insert an IR expression which computes the value held by the IV IndVar (which must be an loop counter...
static void replaceExitCond(BranchInst *BI, Value *NewCond, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
static cl::opt< bool > DisableLFTR("disable-lftr", cl::Hidden, cl::init(false), cl::desc("Disable Linear Function Test Replace optimization"))
static bool isLoopExitTestBasedOn(Value *V, BasicBlock *ExitingBB)
Whether the current loop exit test is based on this value.
static cl::opt< ReplaceExitVal > ReplaceExitValue("replexitval", cl::Hidden, cl::init(OnlyCheapRepl), cl::desc("Choose the strategy to replace exit value in IndVarSimplify"), cl::values(clEnumValN(NeverRepl, "never", "never replace exit value"), clEnumValN(OnlyCheapRepl, "cheap", "only replace exit value when the cost is cheap"), clEnumValN(UnusedIndVarInLoop, "unusedindvarinloop", "only replace exit value when it is an unused " "induction variable in the loop and has cheap replacement cost"), clEnumValN(NoHardUse, "noharduse", "only replace exit values when loop def likely dead"), clEnumValN(AlwaysRepl, "always", "always replace exit value whenever possible")))
static void visitIVCast(CastInst *Cast, WideIVInfo &WI, ScalarEvolution *SE, const TargetTransformInfo *TTI)
Update information about the induction variable that is extended by this sign or zero extend operatio...
static void replaceLoopPHINodesWithPreheaderValues(LoopInfo *LI, Loop *L, SmallVectorImpl< WeakTrackingVH > &DeadInsts, ScalarEvolution &SE)
static bool needsLFTR(Loop *L, BasicBlock *ExitingBB)
linearFunctionTestReplace policy.
static bool optimizeLoopExitWithUnknownExitCount(const Loop *L, BranchInst *BI, BasicBlock *ExitingBB, const SCEV *MaxIter, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
static Value * createInvariantCond(const Loop *L, BasicBlock *ExitingBB, const ScalarEvolution::LoopInvariantPredicate &LIP, SCEVExpander &Rewriter)
static bool isLoopCounter(PHINode *Phi, Loop *L, ScalarEvolution *SE)
Return true if the given phi is a "counter" in L.
static std::optional< Value * > createReplacement(ICmpInst *ICmp, const Loop *L, BasicBlock *ExitingBB, const SCEV *MaxIter, bool Inverted, bool SkipLastIter, ScalarEvolution *SE, SCEVExpander &Rewriter)
static bool hasConcreteDefImpl(Value *V, SmallPtrSetImpl< Value * > &Visited, unsigned Depth)
Recursive helper for hasConcreteDef().
static bool hasConcreteDef(Value *V)
Return true if the given value is concrete.
static void foldExit(const Loop *L, BasicBlock *ExitingBB, bool IsTaken, SmallVectorImpl< WeakTrackingVH > &DeadInsts)
static PHINode * getLoopPhiForCounter(Value *IncV, Loop *L)
Given an Value which is hoped to be part of an add recurance in the given loop, return the associated...
static Constant * createFoldedExitCond(const Loop *L, BasicBlock *ExitingBB, bool IsTaken)
static cl::opt< bool > UsePostIncrementRanges("indvars-post-increment-ranges", cl::Hidden, cl::desc("Use post increment control-dependent ranges in IndVarSimplify"), cl::init(true))
static PHINode * FindLoopCounter(Loop *L, BasicBlock *ExitingBB, const SCEV *BECount, ScalarEvolution *SE, DominatorTree *DT)
Search the loop header for a loop counter (anadd rec w/step of one) suitable for use by LFTR.
static cl::opt< bool > AllowIVWidening("indvars-widen-indvars", cl::Hidden, cl::init(true), cl::desc("Allow widening of indvars to eliminate s/zext"))
static bool ConvertToSInt(const APFloat &APF, int64_t &IntVal)
Convert APF to an integer, if possible.
static cl::opt< bool > LoopPredication("indvars-predicate-loops", cl::Hidden, cl::init(true), cl::desc("Predicate conditions in read only loops"))
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallPtrSet class.
This file defines the SmallSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This defines the Use class.
Virtual Register Rewriter
static const uint32_t IV[8]
opStatus convertToInteger(MutableArrayRef< integerPart > Input, unsigned int Width, bool IsSigned, roundingMode RM, bool *IsExact) const
A container for analyses that lazily runs them and caches their results.
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
InstListType::iterator iterator
Instruction iterators...
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...
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Conditional or Unconditional Branch instruction.
void setCondition(Value *V)
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Represents analyses that only rely on functions' control flow.
This is the base class for all instructions that perform data casts.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ FCMP_OLT
0 1 0 0 True if ordered and less than
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
@ ICMP_SGT
signed greater than
@ FCMP_ULT
1 1 0 0 True if unordered or less than
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
@ ICMP_ULT
unsigned less than
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
@ ICMP_SGE
signed greater or equal
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
ConstantFP - Floating Point Values [float, double].
const APFloat & getValueAPF() const
This is an important base class in LLVM.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This instruction compares its operands according to the predicate given to the constructor.
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Interface for visiting interesting IV users that are recognized but not simplified by this utility.
virtual void visitCast(CastInst *Cast)=0
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
const BasicBlock * getParent() const
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
Class to represent integer types.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
bool replacementPreservesLCSSAForm(Instruction *From, Value *To)
Returns true if replacing From with To everywhere is guaranteed to preserve LCSSA form.
Represents a single loop in the control flow graph.
An analysis that produces MemorySSA for a function.
Encapsulates MemorySSA, including all data associated with memory accesses.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void setIncomingValue(unsigned i, Value *V)
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
static unsigned getIncomingValueNumForOperand(unsigned i)
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
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.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * evaluateAtIteration(const SCEV *It, ScalarEvolution &SE) const
Return the value of this chain of recurrences at the specified iteration number.
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
bool isAffine() const
Return true if this represents an expression A + B*x where A and B are loop invariant values.
const SCEVAddRecExpr * getPostIncExpr(ScalarEvolution &SE) const
Return an expression representing the value of this expression one iteration of the loop ahead.
const Loop * getLoop() const
This class uses information about analyze scalars to rewrite expressions in canonical form.
bool hasNoUnsignedWrap() const
bool hasNoSignedWrap() const
This class represents an analyzed expression in the program.
bool isOne() const
Return true if the expression is a constant one.
bool isZero() const
Return true if the expression is a constant zero.
Type * getType() const
Return the LLVM type of this SCEV expression.
This class represents a cast from signed integer to floating point.
The main scalar evolution driver.
Type * getWiderType(Type *Ty1, Type *Ty2) const
const SCEV * getSCEVAtScope(const SCEV *S, const Loop *L)
Return a SCEV expression for the specified value at the specified scope in the program.
ExitLimit computeExitLimitFromCond(const Loop *L, Value *ExitCond, bool ExitIfTrue, bool ControlsOnlyExit, bool AllowPredicates=false)
Compute the number of times the backedge of the specified loop will execute if its exit condition wer...
uint64_t getTypeSizeInBits(Type *Ty) const
Return the size in bits of the specified type, for which isSCEVable must return true.
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
bool isKnownPredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
const SCEV * getZeroExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
bool isSCEVable(Type *Ty) const
Test if values of the given type are analyzable within the SCEV framework.
Type * getEffectiveSCEVType(Type *Ty) const
Return a type with the same bitwidth as the given type and which represents how SCEV will treat the g...
std::optional< bool > evaluatePredicateAt(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Instruction *CtxI)
Check whether the condition described by Pred, LHS, and RHS is true or false in the given Context.
void forgetValue(Value *V)
This method should be called by the client when it has changed a value in a way that may effect its v...
const SCEV * getTruncateExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getMinusOne(Type *Ty)
Return a SCEV for the constant -1 of a specific type.
const SCEV * getNoopOrZeroExtend(const SCEV *V, Type *Ty)
Return a SCEV corresponding to a conversion of the input value to the specified type.
const SCEV * getUMinFromMismatchedTypes(const SCEV *LHS, const SCEV *RHS, bool Sequential=false)
Promote the operands to the wider of the types using zero-extension, and then perform a umin operatio...
const SCEV * getExitCount(const Loop *L, const BasicBlock *ExitingBlock, ExitCountKind Kind=Exact)
Return the number of times the backedge executes before the given exit would be taken; if not exactly...
std::optional< LoopInvariantPredicate > getLoopInvariantExitCondDuringFirstIterations(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS, const Loop *L, const Instruction *CtxI, const SCEV *MaxIter)
If the result of the predicate LHS Pred RHS is loop invariant with respect to L at given Context duri...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
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.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
The instances of the Type class are immutable: once they are created, they are never changed.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
LLVMContext & getContext() const
All values hold a context through their type.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
Value handle that is nullable, but tries to track the Value.
self_iterator getIterator()
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
StringRef getName(ID id)
Return the LLVM name for an intrinsic, such as "llvm.ppc.altivec.lvx".
bool match(Val *V, const Pattern &P)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
bool mustExecuteUBIfPoisonOnPathTo(Instruction *Root, Instruction *OnPathTo, DominatorTree *DT)
Return true if undefined behavior would provable be executed on the path to OnPathTo if Root produced...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
PHINode * createWideIV(const WideIVInfo &WI, LoopInfo *LI, ScalarEvolution *SE, SCEVExpander &Rewriter, DominatorTree *DT, SmallVectorImpl< WeakTrackingVH > &DeadInsts, unsigned &NumElimExt, unsigned &NumWidened, bool HasGuards, bool UsePostIncrementRanges)
Widen Induction Variables - Extend the width of an IV to cover its widest uses.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< unsigned > SCEVCheapExpansionBudget
bool simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)
simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...
bool VerifyMemorySSA
Enables verification of MemorySSA.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
PreservedAnalyses getLoopPassPreservedAnalyses()
Returns the minimum set of Analyses that all loop passes must preserve.
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
bool isAlmostDeadIV(PHINode *IV, BasicBlock *LatchBlock, Value *Cond)
Return true if the induction variable IV in a Loop whose latch is LatchBlock would become dead if the...
int rewriteLoopExitValues(Loop *L, LoopInfo *LI, TargetLibraryInfo *TLI, ScalarEvolution *SE, const TargetTransformInfo *TTI, SCEVExpander &Rewriter, DominatorTree *DT, ReplaceExitVal ReplaceExitValue, SmallVector< WeakTrackingVH, 16 > &DeadInsts)
If the final value of any expressions that are recurrent in the loop can be computed,...
bool RecursivelyDeleteDeadPHINode(PHINode *PN, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
If the specified value is an effectively dead PHI node, due to being a def-use chain of single-use no...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
TargetTransformInfo & TTI
const SCEV * SymbolicMaxNotTaken
Collect information about induction variables that are used by sign/zero extend operations.