31 #define DEBUG_TYPE "indvars"
33 STATISTIC(NumElimIdentity,
"Number of IV identities eliminated");
34 STATISTIC(NumElimOperand,
"Number of IV operands folded into a use");
35 STATISTIC(NumFoldedUser,
"Number of IV users folded into a constant");
36 STATISTIC(NumElimRem ,
"Number of IV remainder operations eliminated");
39 "Number of IV signed division operations converted to unsigned division");
42 "Number of IV signed remainder operations converted to unsigned remainder");
43 STATISTIC(NumElimCmp ,
"Number of IV comparisons eliminated");
50 class SimplifyIndvar {
68 assert(LI &&
"IV simplification requires LoopInfo");
71 bool hasChanged()
const {
return Changed; }
81 bool replaceIVUserWithLoopInvariant(
Instruction *UseInst);
87 bool makeIVComparisonInvariant(
ICmpInst *ICmp,
Value *IVOperand);
114 assert(CommonDom &&
"Common dominator not found?");
127 Value *IVSrc =
nullptr;
128 const unsigned OperIdx = 0;
129 const SCEV *FoldedExpr =
nullptr;
130 bool MustDropExactFlag =
false;
134 case Instruction::UDiv:
135 case Instruction::LShr:
138 if (IVOperand != UseInst->
getOperand(OperIdx) ||
144 if (!isa<BinaryOperator>(IVOperand)
145 || !isa<ConstantInt>(IVOperand->
getOperand(1)))
150 assert(SE->isSCEVable(IVSrc->
getType()) &&
"Expect SCEVable IV operand");
153 if (UseInst->
getOpcode() == Instruction::LShr) {
162 const auto *
LHS = SE->getSCEV(IVSrc);
163 const auto *
RHS = SE->getSCEV(
D);
164 FoldedExpr = SE->getUDivExpr(
LHS,
RHS);
167 if (UseInst->
isExact() &&
LHS != SE->getMulExpr(FoldedExpr,
RHS))
168 MustDropExactFlag =
true;
171 if (!SE->isSCEVable(UseInst->
getType()))
175 if (SE->getSCEV(UseInst) != FoldedExpr)
178 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated IV operand: " << *IVOperand
179 <<
" -> " << *UseInst <<
'\n');
182 assert(SE->getSCEV(UseInst) == FoldedExpr &&
"bad SCEV with folded oper");
184 if (MustDropExactFlag)
190 DeadInsts.emplace_back(IVOperand);
194 bool SimplifyIndvar::makeIVComparisonInvariant(
ICmpInst *ICmp,
196 unsigned IVOperIdx = 0;
208 const SCEV *
S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
209 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
211 auto *PN = dyn_cast<PHINode>(IVOperand);
214 auto LIP = SE->getLoopInvariantPredicate(Pred,
S,
X, L);
218 const SCEV *InvariantLHS = LIP->LHS;
219 const SCEV *InvariantRHS = LIP->RHS;
227 CheapExpansions[
X] = ICmp->
getOperand(1 - IVOperIdx);
231 if (
auto *
BB = L->getLoopPredecessor()) {
232 const int Idx = PN->getBasicBlockIndex(
BB);
234 Value *Incoming = PN->getIncomingValue(Idx);
235 const SCEV *IncomingS = SE->getSCEV(Incoming);
236 CheapExpansions[IncomingS] = Incoming;
239 Value *NewLHS = CheapExpansions[InvariantLHS];
240 Value *NewRHS = CheapExpansions[InvariantRHS];
243 if (
auto *ConstLHS = dyn_cast<SCEVConstant>(InvariantLHS))
244 NewLHS = ConstLHS->getValue();
246 if (
auto *ConstRHS = dyn_cast<SCEVConstant>(InvariantRHS))
247 NewRHS = ConstRHS->getValue();
249 if (!NewLHS || !NewRHS)
255 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
264 void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
Value *IVOperand) {
265 unsigned IVOperIdx = 0;
278 const SCEV *
S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
279 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
284 for (
auto *U : ICmp->
users())
285 Users.push_back(cast<Instruction>(U));
287 if (
auto Ev = SE->evaluatePredicateAt(Pred,
S,
X, CtxI)) {
289 DeadInsts.emplace_back(ICmp);
290 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
291 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
294 SE->isKnownNonNegative(
S) && SE->isKnownNonNegative(
X)) {
301 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
318 N = SE->getSCEVAtScope(
N, L);
319 D = SE->getSCEVAtScope(
D, L);
322 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
325 SDiv->
getName() +
".udiv", SDiv);
326 UDiv->setIsExact(SDiv->
isExact());
328 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
331 DeadInsts.push_back(SDiv);
342 Rem->
getName() +
".urem", Rem);
344 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
347 DeadInsts.emplace_back(Rem);
351 void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
353 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
356 DeadInsts.emplace_back(Rem);
360 void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
367 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
370 DeadInsts.emplace_back(Rem);
382 bool UsedAsNumerator = IVOperand == NValue;
383 if (!UsedAsNumerator && !IsSigned)
386 const SCEV *
N = SE->getSCEV(NValue);
390 N = SE->getSCEVAtScope(
N, ICmpLoop);
392 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
395 if (!IsNumeratorNonNegative)
398 const SCEV *
D = SE->getSCEV(DValue);
399 D = SE->getSCEVAtScope(
D, ICmpLoop);
401 if (UsedAsNumerator) {
403 if (SE->isKnownPredicate(
LT,
N,
D)) {
404 replaceRemWithNumerator(Rem);
409 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
410 if (SE->isKnownPredicate(
LT, NLessOne,
D)) {
411 replaceRemWithNumeratorOrZero(Rem);
418 if (!IsSigned || !SE->isKnownNonNegative(
D))
421 replaceSRemWithURem(Rem);
443 for (
auto *U : WO->
users()) {
444 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
445 if (EVI->getIndices()[0] == 1)
448 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
449 EVI->replaceAllUsesWith(NewResult);
451 ToDelete.push_back(EVI);
455 for (
auto *EVI : ToDelete)
456 EVI->eraseFromParent();
466 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
467 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
468 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(),
LHS,
RHS))
472 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(),
SI);
478 SI->replaceAllUsesWith(BO);
479 DeadInsts.emplace_back(
SI);
484 bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
502 Type *IVTy =
IV->getType();
503 const SCEV *IVSCEV = SE->getSCEV(
IV);
504 const SCEV *TISCEV = SE->getSCEV(TI);
508 bool DoesSExtCollapse =
false;
509 bool DoesZExtCollapse =
false;
510 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
511 DoesSExtCollapse =
true;
512 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
513 DoesZExtCollapse =
true;
517 if (!DoesSExtCollapse && !DoesZExtCollapse)
523 for (
auto *U : TI->
users()) {
525 if (isa<Instruction>(U) &&
526 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
528 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
529 if (!ICI)
return false;
535 if (ICI->
isSigned() && !DoesSExtCollapse)
540 ICmpUsers.push_back(ICI);
543 auto CanUseZExt = [&](
ICmpInst *ICI) {
548 if (!DoesZExtCollapse)
559 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
562 for (
auto *ICI : ICmpUsers) {
574 if (CanUseZExt(ICI)) {
575 assert(DoesZExtCollapse &&
"Unprofitable zext?");
579 assert(DoesSExtCollapse &&
"Unprofitable sext?");
588 DeadInsts.emplace_back(ICI);
593 DeadInsts.emplace_back(TI);
600 bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
602 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
603 eliminateIVComparison(ICmp, IVOperand);
607 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
608 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
609 simplifyIVRemainder(Bin, IVOperand, IsSRem);
613 if (
Bin->getOpcode() == Instruction::SDiv)
614 return eliminateSDiv(Bin);
617 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
618 if (eliminateOverflowIntrinsic(WO))
621 if (
auto *
SI = dyn_cast<SaturatingInst>(UseInst))
622 if (eliminateSaturatingIntrinsic(
SI))
625 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
626 if (eliminateTrunc(TI))
629 if (eliminateIdentitySCEV(UseInst, IVOperand))
637 return BB->getTerminator();
643 bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
644 if (!SE->isSCEVable(
I->getType()))
648 const SCEV *
S = SE->getSCEV(
I);
650 if (!SE->isLoopInvariant(
S, L))
661 <<
" with non-speculable loop invariant: " << *
S <<
'\n');
667 I->replaceAllUsesWith(Invariant);
669 <<
" with loop invariant: " << *
S <<
'\n');
672 DeadInsts.emplace_back(
I);
677 bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
679 if (!SE->isSCEVable(UseInst->
getType()) ||
681 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
700 if (isa<PHINode>(UseInst))
703 if (!DT || !DT->dominates(IVOperand, UseInst))
706 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
709 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
714 DeadInsts.emplace_back(UseInst);
720 bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
724 std::tie(Flags, Deduced) = SE->getStrengthenedNoWrapFlagsFromBinOp(
725 cast<OverflowingBinaryOperator>(BO));
750 if (BO->
getOpcode() == Instruction::Shl) {
751 bool Changed =
false;
752 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
753 for (
auto *U : BO->
users()) {
776 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
797 SimpleIVUsers.push_back(std::make_pair(UI,
Def));
835 if (!SE->isSCEVable(CurrIV->
getType()))
849 while (!SimpleIVUsers.empty()) {
850 std::pair<Instruction*, Instruction*> UseOper =
859 DeadInsts.emplace_back(UseInst);
864 if (UseInst == CurrIV)
continue;
868 if (replaceIVUserWithLoopInvariant(UseInst))
872 for (
unsigned N = 0; IVOperand; ++
N) {
876 Value *NewOper = foldIVUser(UseInst, IVOperand);
879 IVOperand = dyn_cast<Instruction>(NewOper);
884 if (eliminateIVUser(UseInst, IVOperand)) {
890 if ((isa<OverflowingBinaryOperator>(BO) &&
891 strengthenOverflowingOperation(BO, IVOperand)) ||
892 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand))) {
899 CastInst *Cast = dyn_cast<CastInst>(UseInst);
922 SIV.simplifyUsers(CurrIV, V);
923 return SIV.hasChanged();
935 bool Changed =
false;
969 unsigned NumElimExt = 0;
970 unsigned NumWidened = 0;
975 const SCEV *WideIncExpr =
nullptr;
980 enum ExtendKind { ZeroExtended, SignExtended,
Unknown };
998 DefUserPair
Key(
Def, UseI);
999 auto It = PostIncRangeInfos.
find(
Key);
1000 return It == PostIncRangeInfos.
end()
1005 void calculatePostIncRanges(
PHINode *OrigPhi);
1009 DefUserPair
Key(
Def, UseI);
1010 auto It = PostIncRangeInfos.
find(
Key);
1011 if (It == PostIncRangeInfos.
end())
1014 It->second =
R.intersectWith(It->second);
1021 struct NarrowIVDefUse {
1029 bool NeverNegative =
false;
1033 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1034 NeverNegative(NeverNegative) {}
1043 unsigned getNumElimExt() {
return NumElimExt; };
1044 unsigned getNumWidened() {
return NumWidened; };
1047 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1051 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1053 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1057 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1059 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1061 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1068 bool widenLoopCompare(NarrowIVDefUse DU);
1069 bool widenWithVariantUse(NarrowIVDefUse DU);
1113 auto *DefI = dyn_cast<Instruction>(
Def);
1117 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1122 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1124 return DTN->getBlock()->getTerminator();
1132 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1133 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1137 ExtendKindMap[OrigPhi] = WI.
IsSigned ? SignExtended : ZeroExtended;
1140 Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1150 return IsSigned ?
Builder.CreateSExt(NarrowOper, WideType) :
1151 Builder.CreateZExt(NarrowOper, WideType);
1157 Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1159 unsigned Opcode = DU.NarrowUse->
getOpcode();
1165 case Instruction::UDiv:
1166 case Instruction::Sub:
1167 return cloneArithmeticIVUser(DU, WideAR);
1169 case Instruction::And:
1170 case Instruction::Or:
1171 case Instruction::Xor:
1172 case Instruction::Shl:
1173 case Instruction::LShr:
1174 case Instruction::AShr:
1175 return cloneBitwiseIVUser(DU);
1179 Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1184 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1190 bool IsSigned = getExtendKind(NarrowDef) == SignExtended;
1193 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1194 IsSigned, NarrowUse);
1197 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1198 IsSigned, NarrowUse);
1200 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1201 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(),
LHS,
RHS,
1205 WideBO->copyIRFlags(NarrowBO);
1209 Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1215 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1217 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1228 auto GuessNonIVOperand = [&](
bool SignExt) {
1229 const SCEV *WideLHS;
1230 const SCEV *WideRHS;
1232 auto GetExtend = [
this, SignExt](
const SCEV *
S,
Type *Ty) {
1239 WideLHS = SE->
getSCEV(WideDef);
1241 WideRHS = GetExtend(NarrowRHS, WideType);
1244 WideLHS = GetExtend(NarrowLHS, WideType);
1245 WideRHS = SE->
getSCEV(WideDef);
1249 const SCEV *WideUse =
1250 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1252 return WideUse == WideAR;
1255 bool SignExtend = getExtendKind(NarrowDef) == SignExtended;
1256 if (!GuessNonIVOperand(SignExtend)) {
1258 if (!GuessNonIVOperand(SignExtend))
1264 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1268 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1271 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1272 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(),
LHS,
RHS,
1277 WideBO->copyIRFlags(NarrowBO);
1281 WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1282 auto It = ExtendKindMap.
find(
I);
1283 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1292 case Instruction::Sub:
1296 case Instruction::UDiv:
1308 WidenIV::WidenedRecTy
1309 WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1311 const unsigned OpCode = DU.NarrowUse->getOpcode();
1319 const unsigned ExtendOperIdx =
1320 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1321 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef &&
"bad DU");
1323 const SCEV *ExtendOperExpr =
nullptr;
1325 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1326 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1329 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1332 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1342 const SCEV *rhs = ExtendOperExpr;
1346 if (ExtendOperIdx == 0)
1349 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs,
OpCode));
1351 if (!AddRec || AddRec->
getLoop() != L)
1354 return {AddRec, ExtKind};
1362 WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1363 if (!DU.NarrowUse->getType()->isIntegerTy())
1366 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1374 const SCEV *WideExpr;
1376 if (DU.NeverNegative) {
1378 if (isa<SCEVAddRecExpr>(WideExpr))
1379 ExtKind = SignExtended;
1382 ExtKind = ZeroExtended;
1384 }
else if (getExtendKind(DU.NarrowDef) == SignExtended) {
1386 ExtKind = SignExtended;
1389 ExtKind = ZeroExtended;
1391 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1392 if (!AddRec || AddRec->
getLoop() != L)
1394 return {AddRec, ExtKind};
1404 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1405 << *DU.NarrowUse <<
"\n");
1407 Value *Trunc =
Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1408 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1414 bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1433 bool IsSigned = getExtendKind(DU.NarrowDef) == SignExtended;
1434 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1437 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1440 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1447 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1450 if (CastWidth < IVWidth) {
1451 Value *ExtOp = createExtendInst(
Op, WideType,
Cmp->isSigned(), Cmp);
1452 DU.NarrowUse->replaceUsesOfWith(
Op, ExtOp);
1477 bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1496 cast<OverflowingBinaryOperator>(NarrowUse);
1497 ExtendKind ExtKind = getExtendKind(NarrowDef);
1498 bool CanSignExtend = ExtKind == SignExtended && OBO->
hasNoSignedWrap();
1500 auto AnotherOpExtKind = ExtKind;
1510 for (
Use &U : NarrowUse->
uses()) {
1512 if (
User == NarrowDef)
1515 auto *LCSSAPhi = cast<PHINode>(
User);
1518 if (LCSSAPhi->getNumOperands() != 1)
1520 LCSSAPhiUsers.push_back(LCSSAPhi);
1523 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1529 if (ExtKind == ZeroExtended && ICmpInst::isSigned(Pred))
1531 if (ExtKind == SignExtended && ICmpInst::isUnsigned(Pred))
1533 ICmpUsers.push_back(ICmp);
1536 if (ExtKind == SignExtended)
1542 ExtUsers.push_back(
User);
1544 if (ExtUsers.empty()) {
1554 if (!CanSignExtend && !CanZeroExtend) {
1559 if (ExtKind != ZeroExtended)
1574 AnotherOpExtKind = SignExtended;
1580 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1583 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1588 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1589 AnotherOpExtKind, NarrowUse);
1592 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1593 AnotherOpExtKind, NarrowUse);
1595 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1596 auto *WideBO = BinaryOperator::Create(NarrowBO->getOpcode(),
LHS,
RHS,
1600 WideBO->copyIRFlags(NarrowBO);
1601 ExtendKindMap[NarrowUse] = ExtKind;
1606 << *WideBO <<
"\n");
1617 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1619 "Not a LCSSA Phi?");
1620 WidePN->addIncoming(WideBO, LoopExitingBlock);
1621 Builder.SetInsertPoint(&*
User->getParent()->getFirstInsertionPt());
1632 if (ExtKind == ZeroExtended)
1633 return Builder.CreateZExt(V, WideBO->getType());
1635 return Builder.CreateSExt(V, WideBO->getType());
1637 auto Pred =
User->getPredicate();
1653 "Should already know the kind of extension used to widen NarrowDef");
1656 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1657 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1661 if (UsePhi->getNumOperands() != 1)
1667 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1671 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1673 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1675 Value *Trunc =
Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1676 UsePhi->replaceAllUsesWith(Trunc);
1678 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1679 << *WidePhi <<
"\n");
1687 auto canWidenBySExt = [&]() {
1688 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == SignExtended;
1690 auto canWidenByZExt = [&]() {
1691 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ZeroExtended;
1695 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1696 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1697 Value *NewDef = DU.WideDef;
1698 if (DU.NarrowUse->getType() != WideType) {
1701 if (CastWidth < IVWidth) {
1704 NewDef =
Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1711 <<
" not wide enough to subsume " << *DU.NarrowUse
1713 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1714 NewDef = DU.NarrowUse;
1717 if (NewDef != DU.NarrowUse) {
1719 <<
" replaced by " << *DU.WideDef <<
"\n");
1721 DU.NarrowUse->replaceAllUsesWith(NewDef);
1735 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1736 if (!WideAddRec.first)
1737 WideAddRec = getWideRecurrence(DU);
1739 assert((WideAddRec.first ==
nullptr) == (WideAddRec.second ==
Unknown));
1740 if (!WideAddRec.first) {
1743 if (widenLoopCompare(DU))
1751 if (widenWithVariantUse(DU))
1762 assert(DU.NarrowUse != DU.NarrowUse->getParent()->getTerminator() &&
1763 "SCEV is not expected to evaluate a block terminator");
1768 if (WideAddRec.first == WideIncExpr &&
1769 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1772 WideUse = cloneIVUser(DU, WideAddRec.first);
1781 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1782 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1783 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1793 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1801 bool NonNegativeDef =
1808 if (!Widened.
insert(NarrowUser).second)
1811 bool NonNegativeUse =
false;
1812 if (!NonNegativeDef) {
1814 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1815 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1818 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1819 NonNegativeDef || NonNegativeUse);
1838 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == SignExtended
1843 "Expect the new IV expression to preserve its type");
1846 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1847 if (!AddRec || AddRec->
getLoop() != L)
1856 "Loop header phi recurrence inputs do not dominate the loop");
1869 calculatePostIncRanges(OrigPhi);
1876 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1879 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1884 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1896 WideIncExpr = SE->
getSCEV(WideInc);
1908 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
1911 pushNarrowIVUsers(OrigPhi, WidePhi);
1913 while (!NarrowIVUsers.empty()) {
1914 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1922 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1925 if (DU.NarrowDef->use_empty())
1937 void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
1941 Value *NarrowDefLHS;
1942 const APInt *NarrowDefRHS;
1948 auto UpdateRangeFromCondition = [&] (
Value *Condition,
1960 auto CmpConstrainedLHSRange =
1962 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
1965 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
1968 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
1973 Ctx->getParent()->rend())) {
1975 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
1976 UpdateRangeFromCondition(
C,
true);
1980 UpdateRangeFromGuards(NarrowUser);
1988 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
1990 DTB = DTB->getIDom()) {
1991 auto *
BB = DTB->getBlock();
1992 auto *TI =
BB->getTerminator();
1993 UpdateRangeFromGuards(TI);
1995 auto *BI = dyn_cast<BranchInst>(TI);
1996 if (!BI || !BI->isConditional())
1999 auto *TrueSuccessor = BI->getSuccessor(0);
2000 auto *FalseSuccessor = BI->getSuccessor(1);
2002 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2003 return BBE.isSingleEdge() &&
2008 UpdateRangeFromCondition(BI->getCondition(),
true);
2011 UpdateRangeFromCondition(BI->getCondition(),
false);
2016 void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2019 Worklist.push_back(OrigPhi);
2022 while (!Worklist.empty()) {
2025 for (
Use &U : NarrowDef->
uses()) {
2026 auto *NarrowUser = cast<Instruction>(U.getUser());
2029 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2030 if (!NarrowUserLoop || !L->
contains(NarrowUserLoop))
2033 if (!Visited.
insert(NarrowUser).second)
2036 Worklist.push_back(NarrowUser);
2038 calculatePostIncRange(NarrowDef, NarrowUser);
2046 unsigned &NumElimExt,
unsigned &NumWidened,
2050 NumElimExt = Widener.getNumElimExt();
2051 NumWidened = Widener.getNumWidened();