84using namespace PatternMatch;
86#define DEBUG_TYPE "indvars"
89STATISTIC(NumReplaced ,
"Number of exit values replaced");
90STATISTIC(NumLFTR ,
"Number of loop exit tests replaced");
91STATISTIC(NumElimExt ,
"Number of IV sign/zero extends eliminated");
92STATISTIC(NumElimIV ,
"Number of congruent IVs eliminated");
96 cl::desc(
"Choose the strategy to replace exit value in IndVarSimplify"),
100 "only replace exit value when the cost is cheap"),
103 "only replace exit value when it is an unused "
104 "induction variable in the loop and has cheap replacement cost"),
106 "only replace exit values when loop def likely dead"),
108 "always replace exit value whenever possible")));
112 cl::desc(
"Use post increment control-dependent ranges in IndVarSimplify"),
117 cl::desc(
"Disable Linear Function Test Replace optimization"));
121 cl::desc(
"Predicate conditions in read only loops"));
125 cl::desc(
"Allow widening of indvars to eliminate s/zext"));
129class IndVarSimplify {
136 std::unique_ptr<MemorySSAUpdater> MSSAU;
141 bool RunUnswitching =
false;
144 bool rewriteNonIntegerIVs(
Loop *L);
150 bool canonicalizeExitCondition(
Loop *L);
157 bool rewriteFirstIterationLoopExitValues(
Loop *L);
160 const SCEV *ExitCount,
163 bool sinkUnusedInvariants(
Loop *L);
169 : LI(LI), SE(SE), DT(DT),
DL(
DL), TLI(TLI),
TTI(
TTI),
170 WidenIndVars(WidenIndVars) {
172 MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
177 bool runUnswitching()
const {
return RunUnswitching; }
188 bool isExact =
false;
192 APFloat::rmTowardZero, &isExact) != APFloat::opOK ||
207bool IndVarSimplify::handleFloatingPointIV(
Loop *L,
PHINode *PN) {
209 unsigned BackEdge = IncomingEdge^1;
212 auto *InitValueVal = dyn_cast<ConstantFP>(PN->
getIncomingValue(IncomingEdge));
215 if (!InitValueVal || !
ConvertToSInt(InitValueVal->getValueAPF(), InitValue))
221 if (Incr ==
nullptr || Incr->getOpcode() != Instruction::FAdd)
return false;
225 ConstantFP *IncValueVal = dyn_cast<ConstantFP>(Incr->getOperand(1));
227 if (IncValueVal ==
nullptr || Incr->getOperand(0) != PN ||
235 if (IncrUse == Incr->user_end())
return false;
237 if (IncrUse != Incr->user_end())
return false;
243 Compare = dyn_cast<FCmpInst>(U2);
244 if (!Compare || !
Compare->hasOneUse() ||
245 !isa<BranchInst>(
Compare->user_back()))
264 if (ExitValueVal ==
nullptr ||
270 switch (
Compare->getPredicate()) {
271 default:
return false;
293 if (!isInt<32>(InitValue) || !isInt<32>(IncValue) || !isInt<32>(ExitValue))
304 if (InitValue >= ExitValue)
311 if (++Range == 0)
return false;
325 if (Leftover != 0 && int32_t(ExitValue+IncValue) < ExitValue)
330 if (InitValue <= ExitValue)
337 if (++Range == 0)
return false;
351 if (Leftover != 0 && int32_t(ExitValue+IncValue) > ExitValue)
364 BinaryOperator::CreateAdd(NewPHI, ConstantInt::get(
Int32Ty, IncValue),
365 Incr->getName() +
".int", Incr->getIterator());
379 Compare->replaceAllUsesWith(NewCompare);
402bool IndVarSimplify::rewriteNonIntegerIVs(
Loop *L) {
409 for (
PHINode &PN : Header->phis())
412 bool Changed =
false;
414 if (
PHINode *PN = dyn_cast_or_null<PHINode>(&*
PHI))
415 Changed |= handleFloatingPointIV(L, PN);
434bool IndVarSimplify::rewriteFirstIterationLoopExitValues(
Loop *L) {
439 L->getUniqueExitBlocks(ExitBlocks);
441 bool MadeAnyChanges =
false;
442 for (
auto *ExitBB : ExitBlocks) {
445 for (
PHINode &PN : ExitBB->phis()) {
447 IncomingValIdx != E; ++IncomingValIdx) {
455 if (!
L->getLoopLatch() ||
456 !DT->dominates(IncomingBB,
L->getLoopLatch()))
463 if (
auto *BI = dyn_cast<BranchInst>(TermInst)) {
466 Cond = BI->getCondition();
467 }
else if (
auto *SI = dyn_cast<SwitchInst>(TermInst))
468 Cond =
SI->getCondition();
472 if (!
L->isLoopInvariant(
Cond))
478 if (!ExitVal || ExitVal->getParent() !=
L->getHeader())
484 auto *LoopPreheader =
L->getLoopPreheader();
485 assert(LoopPreheader &&
"Invalid loop");
486 int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
487 if (PreheaderIdx != -1) {
488 assert(ExitVal->getParent() ==
L->getHeader() &&
489 "ExitVal must be in loop header");
490 MadeAnyChanges =
true;
492 ExitVal->getIncomingValue(PreheaderIdx));
493 SE->forgetValue(&PN);
498 return MadeAnyChanges;
511 bool IsSigned = Cast->
getOpcode() == Instruction::SExt;
512 if (!IsSigned && Cast->
getOpcode() != Instruction::ZExt)
525 if (NarrowIVWidth >= Width)
565class IndVarSimplifyVisitor :
public IVVisitor {
592bool IndVarSimplify::simplifyAndExtend(
Loop *L,
597 auto *GuardDecl =
L->getBlocks()[0]->getModule()->getFunction(
599 bool HasGuards = GuardDecl && !GuardDecl->use_empty();
602 for (
PHINode &PN :
L->getHeader()->phis())
609 bool Changed =
false;
610 while (!LoopPhis.
empty()) {
621 IndVarSimplifyVisitor Visitor(CurrIV, SE,
TTI, DT);
628 if (Visitor.WI.WidestNativeType) {
631 }
while(!LoopPhis.
empty());
641 DT, DeadInsts, ElimExt, Widened,
643 NumElimExt += ElimExt;
644 NumWidened += Widened;
666 case Instruction::Add:
667 case Instruction::Sub:
669 case Instruction::GetElementPtr:
679 if (Phi && Phi->getParent() == L->getHeader()) {
684 if (IncI->
getOpcode() == Instruction::GetElementPtr)
689 if (Phi && Phi->getParent() == L->getHeader()) {
712 assert(L->getLoopLatch() &&
"Must be in simplified form");
729 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
735 if (!L->isLoopInvariant(
RHS)) {
736 if (!L->isLoopInvariant(
LHS))
749 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
754 Value *IncV = Phi->getIncomingValue(
Idx);
763 if (isa<Constant>(V))
764 return !isa<UndefValue>(V);
776 if(
I->mayReadFromMemory() || isa<CallInst>(
I) || isa<InvokeInst>(
I))
805 assert(Phi->getParent() == L->getHeader());
806 assert(L->getLoopLatch());
816 if (!Step || !Step->
isOne())
819 int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());
820 Value *IncV = Phi->getIncomingValue(LatchIdx);
822 isa<SCEVAddRecExpr>(SE->
getSCEV(IncV)));
841 const SCEV *BestInit =
nullptr;
843 assert(LatchBlock &&
"Must be in simplified form");
844 const DataLayout &
DL = L->getHeader()->getModule()->getDataLayout();
851 const auto *AR = cast<SCEVAddRecExpr>(SE->
getSCEV(Phi));
857 if (PhiWidth < BCWidth || !
DL.isLegalInteger(PhiWidth))
866 Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);
880 if (!Phi->getType()->isIntegerTy() &&
900 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->
getType()))
913 const SCEV *ExitCount,
bool UsePostInc,
Loop *L,
929 if (!isa<SCEVConstant>(IVInit) || !isa<SCEVConstant>(ExitCount))
936 "Computed iteration count is not loop invariant!");
948 const SCEV *ExitCount,
950 assert(
L->getLoopLatch() &&
"Loop no longer in simplified form?");
956 Value *CmpIndVar = IndVar;
957 bool UsePostInc =
false;
962 if (ExitingBB ==
L->getLoopLatch()) {
989 if (
auto *BO = dyn_cast<BinaryOperator>(IncVar)) {
990 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));
991 if (BO->hasNoUnsignedWrap())
993 if (BO->hasNoSignedWrap())
998 IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);
1001 "genLoopLimit missed a cast");
1007 P = ICmpInst::ICMP_NE;
1009 P = ICmpInst::ICMP_EQ;
1016 Builder.SetCurrentDebugLocation(
Cond->getDebugLoc());
1023 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->
getType());
1024 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->
getType());
1025 if (CmpIndVarSize > ExitCntSize) {
1035 const SCEV *
IV = SE->getSCEV(CmpIndVar);
1036 const SCEV *TruncatedIV = SE->getTruncateExpr(
IV, ExitCnt->
getType());
1037 const SCEV *ZExtTrunc =
1038 SE->getZeroExtendExpr(TruncatedIV, CmpIndVar->
getType());
1040 if (ZExtTrunc ==
IV) {
1042 ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->
getType(),
1045 const SCEV *SExtTrunc =
1046 SE->getSignExtendExpr(TruncatedIV, CmpIndVar->
getType());
1047 if (SExtTrunc ==
IV) {
1049 ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->
getType(),
1056 L->makeLoopInvariant(ExitCnt, Discard);
1058 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->
getType(),
1061 LLVM_DEBUG(
dbgs() <<
"INDVARS: Rewriting loop exit condition to:\n"
1062 <<
" LHS:" << *CmpIndVar <<
'\n'
1063 <<
" op:\t" << (
P == ICmpInst::ICMP_NE ?
"!=" :
"==")
1065 <<
" RHS:\t" << *ExitCnt <<
"\n"
1066 <<
"ExitCount:\t" << *ExitCount <<
"\n"
1069 Value *
Cond = Builder.CreateICmp(
P, CmpIndVar, ExitCnt,
"exitcond");
1077 DeadInsts.emplace_back(OrigCond);
1090bool IndVarSimplify::sinkUnusedInvariants(
Loop *L) {
1092 if (!ExitBlock)
return false;
1095 if (!Preheader)
return false;
1097 bool MadeAnyChanges =
false;
1100 while (
I != Preheader->
begin()) {
1103 if (isa<PHINode>(
I))
1112 if (
I->mayHaveSideEffects() ||
I->mayReadFromMemory())
1116 if (isa<DbgInfoIntrinsic>(
I))
1127 if (isa<AllocaInst>(
I))
1132 bool UsedInLoop =
false;
1133 for (
Use &U :
I->uses()) {
1139 UseBB =
P->getIncomingBlock(i);
1141 if (UseBB == Preheader ||
L->contains(UseBB)) {
1155 if (
I != Preheader->
begin()) {
1159 }
while (
I->isDebugOrPseudoInst() &&
I != Preheader->
begin());
1161 if (
I->isDebugOrPseudoInst() &&
I == Preheader->
begin())
1167 MadeAnyChanges =
true;
1169 SE->forgetValue(ToMove);
1174 return MadeAnyChanges;
1180 LLVM_DEBUG(
dbgs() <<
"Replacing condition of loop-exiting branch " << *BI
1181 <<
" with " << *NewCond <<
"\n");
1183 if (OldCond->use_empty())
1190 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1192 return ConstantInt::get(OldCond->getType(),
1193 IsTaken ? ExitIfTrue : !ExitIfTrue);
1206 assert(L->isLoopSimplifyForm() &&
"Should only do it in simplify form!");
1207 auto *LoopPreheader = L->getLoopPreheader();
1208 auto *LoopHeader = L->getHeader();
1210 for (
auto &PN : LoopHeader->phis()) {
1213 Worklist.
push_back(cast<Instruction>(U));
1222 while (!Worklist.
empty()) {
1224 if (!Visited.
insert(
I).second)
1228 if (!L->contains(
I))
1233 for (
User *U :
I->users())
1234 Worklist.
push_back(cast<Instruction>(U));
1235 I->replaceAllUsesWith(Res);
1246 BasicBlock *Preheader = L->getLoopPreheader();
1247 assert(Preheader &&
"Preheader doesn't exist");
1251 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1253 InvariantPred = ICmpInst::getInversePredicate(InvariantPred);
1256 return Builder.
CreateICmp(InvariantPred, LHSV, RHSV,
1260static std::optional<Value *>
1262 const SCEV *MaxIter,
bool Inverted,
bool SkipLastIter,
1280 auto *MaxIterTy = MaxIter->
getType();
1297 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter)) {
1298 for (
auto *
Op :
UMin->operands())
1309 return std::nullopt;
1324 "Not a loop exit!");
1337 auto GoThrough = [&](
Value *V) {
1358 if (!GoThrough(Curr))
1359 if (
auto *ICmp = dyn_cast<ICmpInst>(Curr))
1361 }
while (!Worklist.
empty());
1368 if (!SkipLastIter && LeafConditions.
size() > 1 &&
1370 ScalarEvolution::ExitCountKind::SymbolicMaximum) ==
1372 for (
auto *ICmp : LeafConditions) {
1376 if (isa<SCEVCouldNotCompute>(ExitMax))
1384 if (WideExitMax == WideMaxIter)
1385 ICmpsFailingOnLastIter.
insert(ICmp);
1388 bool Changed =
false;
1389 for (
auto *OldCond : LeafConditions) {
1394 bool OptimisticSkipLastIter = SkipLastIter;
1395 if (!OptimisticSkipLastIter) {
1396 if (ICmpsFailingOnLastIter.
size() > 1)
1397 OptimisticSkipLastIter =
true;
1398 else if (ICmpsFailingOnLastIter.
size() == 1)
1399 OptimisticSkipLastIter = !ICmpsFailingOnLastIter.
count(OldCond);
1403 OptimisticSkipLastIter, SE,
Rewriter)) {
1405 auto *NewCond = *Replaced;
1406 if (
auto *NCI = dyn_cast<Instruction>(NewCond)) {
1407 NCI->setName(OldCond->
getName() +
".first_iter");
1409 LLVM_DEBUG(
dbgs() <<
"Unknown exit count: Replacing " << *OldCond
1410 <<
" with " << *NewCond <<
"\n");
1416 ICmpsFailingOnLastIter.
erase(OldCond);
1422bool IndVarSimplify::canonicalizeExitCondition(
Loop *L) {
1433 L->getExitingBlocks(ExitingBlocks);
1434 bool Changed =
false;
1435 for (
auto *ExitingBB : ExitingBlocks) {
1436 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1442 if (!ICmp || !ICmp->hasOneUse())
1445 auto *
LHS = ICmp->getOperand(0);
1446 auto *
RHS = ICmp->getOperand(1);
1450 if (!
L->isLoopInvariant(RHS)) {
1451 if (!
L->isLoopInvariant(LHS))
1458 Value *LHSOp =
nullptr;
1463 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1464 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1465 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1466 FullCR = FullCR.zeroExtend(OuterBitWidth);
1467 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1468 if (FullCR.contains(RHSCR)) {
1471 ICmp->setPredicate(ICmp->getUnsignedPredicate());
1481 for (
auto *ExitingBB : ExitingBlocks) {
1482 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1488 if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned())
1491 bool Swapped =
false;
1492 auto *
LHS = ICmp->getOperand(0);
1493 auto *
RHS = ICmp->getOperand(1);
1494 if (
L->isLoopInvariant(LHS) ==
L->isLoopInvariant(RHS))
1497 if (
L->isLoopInvariant(LHS)) {
1503 assert(!
L->isLoopInvariant(LHS) &&
L->isLoopInvariant(RHS));
1508 Value *LHSOp =
nullptr;
1518 if (!
LHS->
hasOneUse() && !isa<SCEVAddRecExpr>(SE->getSCEV(LHSOp)))
1525 auto doRotateTransform = [&]() {
1526 assert(ICmp->isUnsigned() &&
"must have proven unsigned already");
1528 Instruction::Trunc, RHS, LHSOp->
getType(),
"",
1529 L->getLoopPreheader()->getTerminator()->getIterator());
1530 ICmp->setOperand(Swapped ? 1 : 0, LHSOp);
1531 ICmp->setOperand(Swapped ? 0 : 1, NewRHS);
1533 DeadInsts.push_back(LHS);
1538 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1539 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1540 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1541 FullCR = FullCR.zeroExtend(OuterBitWidth);
1542 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1543 if (FullCR.contains(RHSCR)) {
1544 doRotateTransform();
1558 L->getExitingBlocks(ExitingBlocks);
1575 if (!DT->dominates(ExitingBB,
L->getLoopLatch()))
1582 if (!L->contains(BI->getSuccessor(CI->isNullValue())))
1583 replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, *SE);
1590 if (ExitingBlocks.
empty())
1594 const SCEV *MaxBECount = SE->getSymbolicMaxBackedgeTakenCount(L);
1595 if (isa<SCEVCouldNotCompute>(MaxBECount))
1604 if (
A ==
B)
return false;
1605 if (DT->properlyDominates(
A,
B))
1608 assert(DT->properlyDominates(B, A) &&
1609 "expected total dominance order!");
1614 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++) {
1615 assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]));
1619 bool Changed =
false;
1620 bool SkipLastIter =
false;
1621 const SCEV *CurrMaxExit = SE->getCouldNotCompute();
1622 auto UpdateSkipLastIter = [&](
const SCEV *MaxExitCount) {
1623 if (SkipLastIter || isa<SCEVCouldNotCompute>(MaxExitCount))
1625 if (isa<SCEVCouldNotCompute>(CurrMaxExit))
1626 CurrMaxExit = MaxExitCount;
1628 CurrMaxExit = SE->getUMinFromMismatchedTypes(CurrMaxExit, MaxExitCount);
1631 if (CurrMaxExit == MaxBECount)
1632 SkipLastIter =
true;
1635 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1636 const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBB);
1637 const SCEV *MaxExitCount = SE->getExitCount(
1638 L, ExitingBB, ScalarEvolution::ExitCountKind::SymbolicMaximum);
1639 if (isa<SCEVCouldNotCompute>(ExactExitCount)) {
1643 auto OptimizeCond = [&](
bool SkipLastIter) {
1645 MaxBECount, SkipLastIter,
1646 SE, Rewriter, DeadInsts);
1665 if (OptimizeCond(
false))
1667 else if (SkipLastIter && OptimizeCond(
true))
1669 UpdateSkipLastIter(MaxExitCount);
1673 UpdateSkipLastIter(ExactExitCount);
1680 if (ExactExitCount->
isZero()) {
1681 foldExit(L, ExitingBB,
true, DeadInsts);
1689 "Exit counts must be integers");
1692 SE->getWiderType(MaxBECount->
getType(), ExactExitCount->
getType());
1693 ExactExitCount = SE->getNoopOrZeroExtend(ExactExitCount, WiderType);
1694 MaxBECount = SE->getNoopOrZeroExtend(MaxBECount, WiderType);
1701 foldExit(L, ExitingBB,
false, DeadInsts);
1710 if (!DominatingExactExitCounts.
insert(ExactExitCount).second) {
1711 foldExit(L, ExitingBB,
false, DeadInsts);
1728 L->getExitingBlocks(ExitingBlocks);
1745 const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
1746 if (isa<SCEVCouldNotCompute>(ExactBTC) || !
Rewriter.isSafeToExpand(ExactBTC))
1749 assert(SE->isLoopInvariant(ExactBTC, L) &&
"BTC must be loop invariant");
1773 if (!ExitBlock->
phis().empty())
1776 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1777 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1778 !
Rewriter.isSafeToExpand(ExitCount))
1781 assert(SE->isLoopInvariant(ExitCount, L) &&
1782 "Exit count must be loop invariant");
1799 if (DT->properlyDominates(
A,
B))
return true;
1800 if (DT->properlyDominates(
B,
A))
return false;
1801 return A->getName() <
B->getName();
1806 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++)
1807 if (!DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]))
1812 for (
unsigned i = 0, e = ExitingBlocks.
size(); i < e; i++)
1813 if (BadExit(ExitingBlocks[i])) {
1818 if (ExitingBlocks.
empty())
1826 return DT->dominates(ExitingBB,
L->getLoopLatch());
1840 if (
I.mayHaveSideEffects())
1843 bool Changed =
false;
1854 Rewriter.setInsertPoint(
L->getLoopPreheader()->getTerminator());
1856 Value *ExactBTCV =
nullptr;
1857 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1858 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1862 if (ExitCount == ExactBTC) {
1864 B.getFalse() :
B.getTrue();
1868 ExactBTCV =
Rewriter.expandCodeFor(ExactBTC);
1872 ECV =
B.CreateZExt(ECV, WiderTy);
1873 RHS =
B.CreateZExt(RHS, WiderTy);
1876 ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
1877 NewCond =
B.CreateICmp(Pred, ECV, RHS);
1882 DeadInsts.emplace_back(OldCond);
1884 RunUnswitching =
true;
1894bool IndVarSimplify::run(
Loop *L) {
1896 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
1897 "LCSSA required to run indvars!");
1908 if (!
L->isLoopSimplifyForm())
1911 bool Changed =
false;
1914 Changed |= rewriteNonIntegerIVs(L);
1929 Changed |= simplifyAndExtend(L, Rewriter, LI);
1938 NumReplaced += Rewrites;
1944 NumElimIV +=
Rewriter.replaceCongruentIVs(L, DT, DeadInsts,
TTI);
1948 Changed |= canonicalizeExitCondition(L);
1951 if (optimizeLoopExits(L, Rewriter)) {
1956 SE->forgetTopmostLoop(L);
1961 if (predicateLoopExits(L, Rewriter)) {
1973 L->getExitingBlocks(ExitingBlocks);
1974 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1988 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1989 if (isa<SCEVCouldNotCompute>(ExitCount))
2009 if (!
Rewriter.isSafeToExpand(ExitCount))
2012 Changed |= linearFunctionTestReplace(L, ExitingBB,
2024 while (!DeadInsts.empty()) {
2025 Value *
V = DeadInsts.pop_back_val();
2027 if (
PHINode *
PHI = dyn_cast_or_null<PHINode>(V))
2029 else if (
Instruction *Inst = dyn_cast_or_null<Instruction>(V))
2038 Changed |= sinkUnusedInvariants(L);
2043 Changed |= rewriteFirstIterationLoopExitValues(L);
2049 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
2050 "Indvars did not preserve LCSSA!");
2052 MSSAU->getMemorySSA()->verifyMemorySSA();
2060 Function *
F = L.getHeader()->getParent();
2070 if (IVS.runUnswitching()) {
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")
#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.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
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.
@ C
The default llvm calling convention, compatible with C.
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.
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
std::pair< bool, 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...
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
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.