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)
373 Compare->replaceAllUsesWith(NewCompare);
396bool IndVarSimplify::rewriteNonIntegerIVs(
Loop *L) {
403 for (
PHINode &PN : Header->phis())
406 bool Changed =
false;
408 if (
PHINode *PN = dyn_cast_or_null<PHINode>(&*
PHI))
409 Changed |= handleFloatingPointIV(L, PN);
428bool IndVarSimplify::rewriteFirstIterationLoopExitValues(
Loop *L) {
433 L->getUniqueExitBlocks(ExitBlocks);
435 bool MadeAnyChanges =
false;
436 for (
auto *ExitBB : ExitBlocks) {
439 for (
PHINode &PN : ExitBB->phis()) {
441 IncomingValIdx !=
E; ++IncomingValIdx) {
449 if (!
L->getLoopLatch() ||
450 !DT->dominates(IncomingBB,
L->getLoopLatch()))
457 if (
auto *BI = dyn_cast<BranchInst>(TermInst)) {
460 Cond = BI->getCondition();
461 }
else if (
auto *SI = dyn_cast<SwitchInst>(TermInst))
462 Cond =
SI->getCondition();
466 if (!
L->isLoopInvariant(
Cond))
472 if (!ExitVal || ExitVal->getParent() !=
L->getHeader())
478 auto *LoopPreheader =
L->getLoopPreheader();
479 assert(LoopPreheader &&
"Invalid loop");
480 int PreheaderIdx = ExitVal->getBasicBlockIndex(LoopPreheader);
481 if (PreheaderIdx != -1) {
482 assert(ExitVal->getParent() ==
L->getHeader() &&
483 "ExitVal must be in loop header");
484 MadeAnyChanges =
true;
486 ExitVal->getIncomingValue(PreheaderIdx));
487 SE->forgetValue(&PN);
492 return MadeAnyChanges;
505 bool IsSigned = Cast->
getOpcode() == Instruction::SExt;
506 if (!IsSigned && Cast->
getOpcode() != Instruction::ZExt)
519 if (NarrowIVWidth >= Width)
559class IndVarSimplifyVisitor :
public IVVisitor {
586bool IndVarSimplify::simplifyAndExtend(
Loop *L,
591 auto *GuardDecl =
L->getBlocks()[0]->getModule()->getFunction(
593 bool HasGuards = GuardDecl && !GuardDecl->use_empty();
596 for (
PHINode &PN :
L->getHeader()->phis())
603 bool Changed =
false;
604 while (!LoopPhis.
empty()) {
615 IndVarSimplifyVisitor Visitor(CurrIV, SE,
TTI, DT);
620 if (Visitor.WI.WidestNativeType) {
623 }
while(!LoopPhis.
empty());
633 DT, DeadInsts, ElimExt, Widened,
635 NumElimExt += ElimExt;
636 NumWidened += Widened;
658 case Instruction::Add:
659 case Instruction::Sub:
661 case Instruction::GetElementPtr:
671 if (Phi && Phi->getParent() == L->getHeader()) {
676 if (IncI->
getOpcode() == Instruction::GetElementPtr)
681 if (Phi && Phi->getParent() == L->getHeader()) {
704 assert(L->getLoopLatch() &&
"Must be in simplified form");
721 if (Pred != ICmpInst::ICMP_NE && Pred != ICmpInst::ICMP_EQ)
727 if (!L->isLoopInvariant(
RHS)) {
728 if (!L->isLoopInvariant(
LHS))
741 int Idx = Phi->getBasicBlockIndex(L->getLoopLatch());
746 Value *IncV = Phi->getIncomingValue(
Idx);
755 if (isa<Constant>(V))
756 return !isa<UndefValue>(V);
768 if(
I->mayReadFromMemory() || isa<CallInst>(
I) || isa<InvokeInst>(
I))
797 assert(Phi->getParent() == L->getHeader());
798 assert(L->getLoopLatch());
808 if (!Step || !Step->
isOne())
811 int LatchIdx = Phi->getBasicBlockIndex(L->getLoopLatch());
812 Value *IncV = Phi->getIncomingValue(LatchIdx);
814 isa<SCEVAddRecExpr>(SE->
getSCEV(IncV)));
833 const SCEV *BestInit =
nullptr;
835 assert(LatchBlock &&
"Must be in simplified form");
836 const DataLayout &
DL = L->getHeader()->getModule()->getDataLayout();
843 const auto *AR = cast<SCEVAddRecExpr>(SE->
getSCEV(Phi));
849 if (PhiWidth < BCWidth || !
DL.isLegalInteger(PhiWidth))
858 Value *IncPhi = Phi->getIncomingValueForBlock(LatchBlock);
872 if (!Phi->getType()->isIntegerTy() &&
892 else if (PhiWidth <= SE->getTypeSizeInBits(BestPhi->
getType()))
905 const SCEV *ExitCount,
bool UsePostInc,
Loop *L,
921 if (!isa<SCEVConstant>(IVInit) || !isa<SCEVConstant>(ExitCount))
928 "Computed iteration count is not loop invariant!");
940 const SCEV *ExitCount,
942 assert(
L->getLoopLatch() &&
"Loop no longer in simplified form?");
948 Value *CmpIndVar = IndVar;
949 bool UsePostInc =
false;
954 if (ExitingBB ==
L->getLoopLatch()) {
981 if (
auto *BO = dyn_cast<BinaryOperator>(IncVar)) {
982 const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(SE->getSCEV(IncVar));
983 if (BO->hasNoUnsignedWrap())
985 if (BO->hasNoSignedWrap())
990 IndVar, ExitingBB, ExitCount, UsePostInc, L, Rewriter, SE);
993 "genLoopLimit missed a cast");
999 P = ICmpInst::ICMP_NE;
1001 P = ICmpInst::ICMP_EQ;
1008 Builder.SetCurrentDebugLocation(
Cond->getDebugLoc());
1015 unsigned CmpIndVarSize = SE->getTypeSizeInBits(CmpIndVar->
getType());
1016 unsigned ExitCntSize = SE->getTypeSizeInBits(ExitCnt->
getType());
1017 if (CmpIndVarSize > ExitCntSize) {
1027 const SCEV *
IV = SE->getSCEV(CmpIndVar);
1028 const SCEV *TruncatedIV = SE->getTruncateExpr(
IV, ExitCnt->
getType());
1029 const SCEV *ZExtTrunc =
1030 SE->getZeroExtendExpr(TruncatedIV, CmpIndVar->
getType());
1032 if (ZExtTrunc ==
IV) {
1034 ExitCnt = Builder.CreateZExt(ExitCnt, IndVar->
getType(),
1037 const SCEV *SExtTrunc =
1038 SE->getSignExtendExpr(TruncatedIV, CmpIndVar->
getType());
1039 if (SExtTrunc ==
IV) {
1041 ExitCnt = Builder.CreateSExt(ExitCnt, IndVar->
getType(),
1048 L->makeLoopInvariant(ExitCnt, Discard);
1050 CmpIndVar = Builder.CreateTrunc(CmpIndVar, ExitCnt->
getType(),
1053 LLVM_DEBUG(
dbgs() <<
"INDVARS: Rewriting loop exit condition to:\n"
1054 <<
" LHS:" << *CmpIndVar <<
'\n'
1055 <<
" op:\t" << (
P == ICmpInst::ICMP_NE ?
"!=" :
"==")
1057 <<
" RHS:\t" << *ExitCnt <<
"\n"
1058 <<
"ExitCount:\t" << *ExitCount <<
"\n"
1061 Value *
Cond = Builder.CreateICmp(
P, CmpIndVar, ExitCnt,
"exitcond");
1069 DeadInsts.emplace_back(OrigCond);
1082bool IndVarSimplify::sinkUnusedInvariants(
Loop *L) {
1084 if (!ExitBlock)
return false;
1087 if (!Preheader)
return false;
1089 bool MadeAnyChanges =
false;
1092 while (
I != Preheader->
begin()) {
1095 if (isa<PHINode>(
I))
1104 if (
I->mayHaveSideEffects() ||
I->mayReadFromMemory())
1108 if (isa<DbgInfoIntrinsic>(
I))
1119 if (isa<AllocaInst>(
I))
1124 bool UsedInLoop =
false;
1125 for (
Use &U :
I->uses()) {
1131 UseBB =
P->getIncomingBlock(i);
1133 if (UseBB == Preheader ||
L->contains(UseBB)) {
1147 if (
I != Preheader->
begin()) {
1151 }
while (
I->isDebugOrPseudoInst() &&
I != Preheader->
begin());
1153 if (
I->isDebugOrPseudoInst() &&
I == Preheader->
begin())
1159 MadeAnyChanges =
true;
1161 SE->forgetValue(ToMove);
1166 return MadeAnyChanges;
1172 LLVM_DEBUG(
dbgs() <<
"Replacing condition of loop-exiting branch " << *BI
1173 <<
" with " << *NewCond <<
"\n");
1175 if (OldCond->use_empty())
1182 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1185 IsTaken ? ExitIfTrue : !ExitIfTrue);
1198 assert(L->isLoopSimplifyForm() &&
"Should only do it in simplify form!");
1199 auto *LoopPreheader = L->getLoopPreheader();
1200 auto *LoopHeader = L->getHeader();
1202 for (
auto &PN : LoopHeader->phis()) {
1205 Worklist.
push_back(cast<Instruction>(U));
1214 while (!Worklist.
empty()) {
1216 if (!Visited.
insert(
I).second)
1220 if (!L->contains(
I))
1225 for (
User *U :
I->users())
1226 Worklist.
push_back(cast<Instruction>(U));
1227 I->replaceAllUsesWith(Res);
1238 BasicBlock *Preheader = L->getLoopPreheader();
1239 assert(Preheader &&
"Preheader doesn't exist");
1243 bool ExitIfTrue = !L->contains(*
succ_begin(ExitingBB));
1245 InvariantPred = ICmpInst::getInversePredicate(InvariantPred);
1248 return Builder.
CreateICmp(InvariantPred, LHSV, RHSV,
1252static std::optional<Value *>
1254 const SCEV *MaxIter,
bool Inverted,
bool SkipLastIter,
1272 auto *MaxIterTy = MaxIter->
getType();
1289 if (
auto *
UMin = dyn_cast<SCEVUMinExpr>(MaxIter)) {
1290 for (
auto *
Op :
UMin->operands())
1301 return std::nullopt;
1316 "Not a loop exit!");
1329 auto GoThrough = [&](
Value *V) {
1350 if (!GoThrough(Curr))
1351 if (
auto *ICmp = dyn_cast<ICmpInst>(Curr))
1353 }
while (!Worklist.
empty());
1360 if (!SkipLastIter && LeafConditions.
size() > 1 &&
1362 ScalarEvolution::ExitCountKind::SymbolicMaximum) ==
1364 for (
auto *ICmp : LeafConditions) {
1368 if (isa<SCEVCouldNotCompute>(ExitMax))
1376 if (WideExitMax == WideMaxIter)
1377 ICmpsFailingOnLastIter.
insert(ICmp);
1380 bool Changed =
false;
1381 for (
auto *OldCond : LeafConditions) {
1386 bool OptimisticSkipLastIter = SkipLastIter;
1387 if (!OptimisticSkipLastIter) {
1388 if (ICmpsFailingOnLastIter.
size() > 1)
1389 OptimisticSkipLastIter =
true;
1390 else if (ICmpsFailingOnLastIter.
size() == 1)
1391 OptimisticSkipLastIter = !ICmpsFailingOnLastIter.
count(OldCond);
1395 OptimisticSkipLastIter, SE,
Rewriter)) {
1397 auto *NewCond = *Replaced;
1398 if (
auto *NCI = dyn_cast<Instruction>(NewCond)) {
1399 NCI->setName(OldCond->
getName() +
".first_iter");
1401 LLVM_DEBUG(
dbgs() <<
"Unknown exit count: Replacing " << *OldCond
1402 <<
" with " << *NewCond <<
"\n");
1408 ICmpsFailingOnLastIter.
erase(OldCond);
1414bool IndVarSimplify::canonicalizeExitCondition(
Loop *L) {
1425 L->getExitingBlocks(ExitingBlocks);
1426 bool Changed =
false;
1427 for (
auto *ExitingBB : ExitingBlocks) {
1428 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1434 if (!ICmp || !ICmp->hasOneUse())
1437 auto *
LHS = ICmp->getOperand(0);
1438 auto *
RHS = ICmp->getOperand(1);
1442 if (!
L->isLoopInvariant(RHS)) {
1443 if (!
L->isLoopInvariant(LHS))
1450 Value *LHSOp =
nullptr;
1455 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1456 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1457 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1458 FullCR = FullCR.zeroExtend(OuterBitWidth);
1459 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1460 if (FullCR.contains(RHSCR)) {
1463 ICmp->setPredicate(ICmp->getUnsignedPredicate());
1473 for (
auto *ExitingBB : ExitingBlocks) {
1474 auto *BI = dyn_cast<BranchInst>(ExitingBB->
getTerminator());
1480 if (!ICmp || !ICmp->hasOneUse() || !ICmp->isUnsigned())
1483 bool Swapped =
false;
1484 auto *
LHS = ICmp->getOperand(0);
1485 auto *
RHS = ICmp->getOperand(1);
1486 if (
L->isLoopInvariant(LHS) ==
L->isLoopInvariant(RHS))
1489 if (
L->isLoopInvariant(LHS)) {
1495 assert(!
L->isLoopInvariant(LHS) &&
L->isLoopInvariant(RHS));
1500 Value *LHSOp =
nullptr;
1510 if (!
LHS->
hasOneUse() && !isa<SCEVAddRecExpr>(SE->getSCEV(LHSOp)))
1517 auto doRotateTransform = [&]() {
1518 assert(ICmp->isUnsigned() &&
"must have proven unsigned already");
1521 L->getLoopPreheader()->getTerminator());
1522 ICmp->setOperand(Swapped ? 1 : 0, LHSOp);
1523 ICmp->setOperand(Swapped ? 0 : 1, NewRHS);
1525 DeadInsts.push_back(LHS);
1530 const unsigned InnerBitWidth =
DL.getTypeSizeInBits(LHSOp->
getType());
1531 const unsigned OuterBitWidth =
DL.getTypeSizeInBits(
RHS->
getType());
1532 auto FullCR = ConstantRange::getFull(InnerBitWidth);
1533 FullCR = FullCR.zeroExtend(OuterBitWidth);
1534 auto RHSCR = SE->getUnsignedRange(SE->applyLoopGuards(SE->getSCEV(RHS), L));
1535 if (FullCR.contains(RHSCR)) {
1536 doRotateTransform();
1550 L->getExitingBlocks(ExitingBlocks);
1567 if (!DT->dominates(ExitingBB,
L->getLoopLatch()))
1574 if (!L->contains(BI->getSuccessor(CI->isNullValue())))
1575 replaceLoopPHINodesWithPreheaderValues(LI, L, DeadInsts, *SE);
1582 if (ExitingBlocks.
empty())
1586 const SCEV *MaxBECount = SE->getSymbolicMaxBackedgeTakenCount(L);
1587 if (isa<SCEVCouldNotCompute>(MaxBECount))
1596 if (
A ==
B)
return false;
1597 if (DT->properlyDominates(
A,
B))
1600 assert(DT->properlyDominates(B, A) &&
1601 "expected total dominance order!");
1606 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++) {
1607 assert(DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]));
1611 bool Changed =
false;
1612 bool SkipLastIter =
false;
1613 const SCEV *CurrMaxExit = SE->getCouldNotCompute();
1614 auto UpdateSkipLastIter = [&](
const SCEV *MaxExitCount) {
1615 if (SkipLastIter || isa<SCEVCouldNotCompute>(MaxExitCount))
1617 if (isa<SCEVCouldNotCompute>(CurrMaxExit))
1618 CurrMaxExit = MaxExitCount;
1620 CurrMaxExit = SE->getUMinFromMismatchedTypes(CurrMaxExit, MaxExitCount);
1623 if (CurrMaxExit == MaxBECount)
1624 SkipLastIter =
true;
1627 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1628 const SCEV *ExactExitCount = SE->getExitCount(L, ExitingBB);
1629 const SCEV *MaxExitCount = SE->getExitCount(
1630 L, ExitingBB, ScalarEvolution::ExitCountKind::SymbolicMaximum);
1631 if (isa<SCEVCouldNotCompute>(ExactExitCount)) {
1635 auto OptimizeCond = [&](
bool SkipLastIter) {
1637 MaxBECount, SkipLastIter,
1638 SE, Rewriter, DeadInsts);
1657 if (OptimizeCond(
false))
1659 else if (SkipLastIter && OptimizeCond(
true))
1661 UpdateSkipLastIter(MaxExitCount);
1665 UpdateSkipLastIter(ExactExitCount);
1672 if (ExactExitCount->
isZero()) {
1673 foldExit(L, ExitingBB,
true, DeadInsts);
1681 "Exit counts must be integers");
1684 SE->getWiderType(MaxBECount->
getType(), ExactExitCount->
getType());
1685 ExactExitCount = SE->getNoopOrZeroExtend(ExactExitCount, WiderType);
1686 MaxBECount = SE->getNoopOrZeroExtend(MaxBECount, WiderType);
1693 foldExit(L, ExitingBB,
false, DeadInsts);
1702 if (!DominatingExactExitCounts.
insert(ExactExitCount).second) {
1703 foldExit(L, ExitingBB,
false, DeadInsts);
1720 L->getExitingBlocks(ExitingBlocks);
1737 const SCEV *ExactBTC = SE->getBackedgeTakenCount(L);
1738 if (isa<SCEVCouldNotCompute>(ExactBTC) || !
Rewriter.isSafeToExpand(ExactBTC))
1741 assert(SE->isLoopInvariant(ExactBTC, L) &&
"BTC must be loop invariant");
1765 if (!ExitBlock->
phis().empty())
1768 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1769 if (isa<SCEVCouldNotCompute>(ExitCount) ||
1770 !
Rewriter.isSafeToExpand(ExitCount))
1773 assert(SE->isLoopInvariant(ExitCount, L) &&
1774 "Exit count must be loop invariant");
1791 if (DT->properlyDominates(
A,
B))
return true;
1792 if (DT->properlyDominates(
B,
A))
return false;
1793 return A->getName() <
B->getName();
1798 for (
unsigned i = 1; i < ExitingBlocks.
size(); i++)
1799 if (!DT->dominates(ExitingBlocks[i-1], ExitingBlocks[i]))
1804 for (
unsigned i = 0, e = ExitingBlocks.
size(); i < e; i++)
1805 if (BadExit(ExitingBlocks[i])) {
1810 if (ExitingBlocks.
empty())
1818 return DT->dominates(ExitingBB,
L->getLoopLatch());
1832 if (
I.mayHaveSideEffects())
1835 bool Changed =
false;
1846 Rewriter.setInsertPoint(
L->getLoopPreheader()->getTerminator());
1848 Value *ExactBTCV =
nullptr;
1849 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1850 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1854 if (ExitCount == ExactBTC) {
1856 B.getFalse() :
B.getTrue();
1860 ExactBTCV =
Rewriter.expandCodeFor(ExactBTC);
1864 ECV =
B.CreateZExt(ECV, WiderTy);
1865 RHS =
B.CreateZExt(RHS, WiderTy);
1868 ICmpInst::ICMP_NE : ICmpInst::ICMP_EQ;
1869 NewCond =
B.CreateICmp(Pred, ECV, RHS);
1874 DeadInsts.emplace_back(OldCond);
1885bool IndVarSimplify::run(
Loop *L) {
1887 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
1888 "LCSSA required to run indvars!");
1899 if (!
L->isLoopSimplifyForm())
1902 bool Changed =
false;
1905 Changed |= rewriteNonIntegerIVs(L);
1920 Changed |= simplifyAndExtend(L, Rewriter, LI);
1929 NumReplaced += Rewrites;
1935 NumElimIV +=
Rewriter.replaceCongruentIVs(L, DT, DeadInsts,
TTI);
1939 Changed |= canonicalizeExitCondition(L);
1942 if (optimizeLoopExits(L, Rewriter)) {
1947 SE->forgetTopmostLoop(L);
1952 if (predicateLoopExits(L, Rewriter)) {
1964 L->getExitingBlocks(ExitingBlocks);
1965 for (
BasicBlock *ExitingBB : ExitingBlocks) {
1979 const SCEV *ExitCount = SE->getExitCount(L, ExitingBB);
1980 if (isa<SCEVCouldNotCompute>(ExitCount))
2000 if (!
Rewriter.isSafeToExpand(ExitCount))
2003 Changed |= linearFunctionTestReplace(L, ExitingBB,
2015 while (!DeadInsts.empty()) {
2016 Value *
V = DeadInsts.pop_back_val();
2018 if (
PHINode *
PHI = dyn_cast_or_null<PHINode>(V))
2020 else if (
Instruction *Inst = dyn_cast_or_null<Instruction>(V))
2029 Changed |= sinkUnusedInvariants(L);
2034 Changed |= rewriteFirstIterationLoopExitValues(L);
2040 assert(
L->isRecursivelyLCSSAForm(*DT, *LI) &&
2041 "Indvars did not preserve LCSSA!");
2043 MSSAU->getMemorySSA()->verifyMemorySSA();
2051 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="", Instruction *InsertBefore=nullptr)
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
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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.
void setIncomingValue(unsigned i, Value *V)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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)
CastInst_match< OpTy, Instruction::ZExt > m_ZExt(const OpTy &Op)
Matches ZExt.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
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.