34#define DEBUG_TYPE "indvars"
36STATISTIC(NumElimIdentity,
"Number of IV identities eliminated");
37STATISTIC(NumElimOperand,
"Number of IV operands folded into a use");
38STATISTIC(NumFoldedUser,
"Number of IV users folded into a constant");
39STATISTIC(NumElimRem ,
"Number of IV remainder operations eliminated");
42 "Number of IV signed division operations converted to unsigned division");
45 "Number of IV signed remainder operations converted to unsigned remainder");
46STATISTIC(NumElimCmp ,
"Number of IV comparisons eliminated");
53 class SimplifyIndvar {
63 bool RunUnswitching =
false;
72 assert(LI &&
"IV simplification requires LoopInfo");
75 bool hasChanged()
const {
return Changed; }
76 bool runUnswitching()
const {
return RunUnswitching; }
91 bool replaceIVUserWithLoopInvariant(
Instruction *UseInst);
92 bool replaceFloatIVWithIntegerIV(
Instruction *UseInst);
119 for (
auto *
Insn : Instructions)
122 assert(CommonDom &&
"Common dominator not found?");
135 Value *IVSrc =
nullptr;
136 const unsigned OperIdx = 0;
137 const SCEV *FoldedExpr =
nullptr;
138 bool MustDropExactFlag =
false;
142 case Instruction::UDiv:
143 case Instruction::LShr:
146 if (IVOperand != UseInst->
getOperand(OperIdx) ||
152 if (!isa<BinaryOperator>(IVOperand)
153 || !isa<ConstantInt>(IVOperand->
getOperand(1)))
158 assert(SE->isSCEVable(IVSrc->
getType()) &&
"Expect SCEVable IV operand");
161 if (UseInst->
getOpcode() == Instruction::LShr) {
170 const auto *
LHS = SE->getSCEV(IVSrc);
171 const auto *
RHS = SE->getSCEV(
D);
172 FoldedExpr = SE->getUDivExpr(LHS, RHS);
175 if (UseInst->
isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
176 MustDropExactFlag =
true;
179 if (!SE->isSCEVable(UseInst->
getType()))
183 if (SE->getSCEV(UseInst) != FoldedExpr)
186 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated IV operand: " << *IVOperand
187 <<
" -> " << *UseInst <<
'\n');
190 assert(SE->getSCEV(UseInst) == FoldedExpr &&
"bad SCEV with folded oper");
192 if (MustDropExactFlag)
198 DeadInsts.emplace_back(IVOperand);
202bool SimplifyIndvar::makeIVComparisonInvariant(
ICmpInst *ICmp,
204 auto *Preheader =
L->getLoopPreheader();
207 unsigned IVOperIdx = 0;
213 Pred = ICmpInst::getSwappedPredicate(Pred);
219 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
220 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
221 auto LIP = SE->getLoopInvariantPredicate(Pred, S,
X, L, ICmp);
225 const SCEV *InvariantLHS = LIP->LHS;
226 const SCEV *InvariantRHS = LIP->RHS;
229 auto *PHTerm = Preheader->getTerminator();
230 if (
Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,
232 !
Rewriter.isSafeToExpandAt(InvariantLHS, PHTerm) ||
233 !
Rewriter.isSafeToExpandAt(InvariantRHS, PHTerm))
239 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
243 RunUnswitching =
true;
249void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
251 unsigned IVOperIdx = 0;
258 Pred = ICmpInst::getSwappedPredicate(Pred);
264 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
265 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
270 for (
auto *U : ICmp->
users())
271 Users.push_back(cast<Instruction>(U));
273 if (
auto Ev = SE->evaluatePredicateAt(Pred, S,
X, CtxI)) {
274 SE->forgetValue(ICmp);
276 DeadInsts.emplace_back(ICmp);
277 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
278 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
280 }
else if (ICmpInst::isSigned(OriginalPred) &&
281 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(
X)) {
288 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
305 N = SE->getSCEVAtScope(
N, L);
306 D = SE->getSCEVAtScope(
D, L);
309 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
313 UDiv->setIsExact(SDiv->
isExact());
315 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
318 DeadInsts.push_back(SDiv);
331 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
334 DeadInsts.emplace_back(Rem);
338void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
340 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
343 DeadInsts.emplace_back(Rem);
347void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
354 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
357 DeadInsts.emplace_back(Rem);
370 bool UsedAsNumerator = IVOperand == NValue;
371 if (!UsedAsNumerator && !IsSigned)
374 const SCEV *
N = SE->getSCEV(NValue);
378 N = SE->getSCEVAtScope(
N, ICmpLoop);
380 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
383 if (!IsNumeratorNonNegative)
386 const SCEV *
D = SE->getSCEV(DValue);
387 D = SE->getSCEVAtScope(
D, ICmpLoop);
389 if (UsedAsNumerator) {
390 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
391 if (SE->isKnownPredicate(LT,
N,
D)) {
392 replaceRemWithNumerator(Rem);
397 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
398 if (SE->isKnownPredicate(LT, NLessOne,
D)) {
399 replaceRemWithNumeratorOrZero(Rem);
406 if (!IsSigned || !SE->isKnownNonNegative(
D))
409 replaceSRemWithURem(Rem);
431 for (
auto *U : WO->
users()) {
432 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
433 if (EVI->getIndices()[0] == 1)
436 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
437 EVI->replaceAllUsesWith(NewResult);
443 for (
auto *EVI : ToDelete)
444 EVI->eraseFromParent();
453bool SimplifyIndvar::eliminateSaturatingIntrinsic(
SaturatingInst *SI) {
454 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
455 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
456 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(), LHS, RHS))
460 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(),
SI->getIterator());
466 SI->replaceAllUsesWith(BO);
467 DeadInsts.emplace_back(SI);
472bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
490 Type *IVTy =
IV->getType();
491 const SCEV *IVSCEV = SE->getSCEV(
IV);
492 const SCEV *TISCEV = SE->getSCEV(TI);
496 bool DoesSExtCollapse =
false;
497 bool DoesZExtCollapse =
false;
498 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
499 DoesSExtCollapse =
true;
500 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
501 DoesZExtCollapse =
true;
505 if (!DoesSExtCollapse && !DoesZExtCollapse)
511 for (
auto *U : TI->
users()) {
513 if (isa<Instruction>(U) &&
514 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
516 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
517 if (!ICI)
return false;
523 if (ICI->
isSigned() && !DoesSExtCollapse)
531 auto CanUseZExt = [&](
ICmpInst *ICI) {
536 if (!DoesZExtCollapse)
547 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
550 for (
auto *ICI : ICmpUsers) {
551 bool IsSwapped =
L->isLoopInvariant(ICI->
getOperand(0));
562 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
563 if (CanUseZExt(ICI)) {
564 assert(DoesZExtCollapse &&
"Unprofitable zext?");
565 Ext = Builder.CreateZExt(Op1, IVTy,
"zext");
568 assert(DoesSExtCollapse &&
"Unprofitable sext?");
569 Ext = Builder.CreateSExt(Op1, IVTy,
"sext");
573 L->makeLoopInvariant(Ext, Changed);
575 auto *NewCmp = Builder.CreateICmp(Pred,
IV, Ext);
577 DeadInsts.emplace_back(ICI);
582 DeadInsts.emplace_back(TI);
589bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
591 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
592 eliminateIVComparison(ICmp, IVOperand);
596 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
597 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
598 simplifyIVRemainder(
Bin, IVOperand, IsSRem);
602 if (
Bin->getOpcode() == Instruction::SDiv)
603 return eliminateSDiv(
Bin);
606 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
607 if (eliminateOverflowIntrinsic(WO))
610 if (
auto *SI = dyn_cast<SaturatingInst>(UseInst))
611 if (eliminateSaturatingIntrinsic(SI))
614 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
615 if (eliminateTrunc(TI))
618 if (eliminateIdentitySCEV(UseInst, IVOperand))
625 if (
auto *BB = L->getLoopPreheader())
626 return BB->getTerminator();
632bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
633 if (!SE->isSCEVable(
I->getType()))
637 const SCEV *S = SE->getSCEV(
I);
639 if (!SE->isLoopInvariant(S, L))
648 if (!
Rewriter.isSafeToExpandAt(S, IP)) {
650 <<
" with non-speculable loop invariant: " << *S <<
'\n');
654 auto *Invariant =
Rewriter.expandCodeFor(S,
I->getType(), IP);
655 bool NeedToEmitLCSSAPhis =
false;
656 if (!LI->replacementPreservesLCSSAForm(
I, Invariant))
657 NeedToEmitLCSSAPhis =
true;
659 I->replaceAllUsesWith(Invariant);
661 <<
" with loop invariant: " << *S <<
'\n');
663 if (NeedToEmitLCSSAPhis) {
665 NeedsLCSSAPhis.
push_back(cast<Instruction>(Invariant));
668 <<
" inserting LCSSA Phis" <<
'\n');
672 DeadInsts.emplace_back(
I);
677bool SimplifyIndvar::replaceFloatIVWithIntegerIV(
Instruction *UseInst) {
678 if (UseInst->
getOpcode() != CastInst::SIToFP &&
679 UseInst->
getOpcode() != CastInst::UIToFP)
684 const SCEV *
IV = SE->getSCEV(IVOperand);
686 if (UseInst->
getOpcode() == CastInst::SIToFP)
687 MaskBits = (int)SE->getSignedRange(
IV).getMinSignedBits();
689 MaskBits = (int)SE->getUnsignedRange(
IV).getActiveBits();
691 if (MaskBits <= DestNumSigBits) {
694 auto *CI = dyn_cast<CastInst>(U);
699 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
702 Value *Conv =
nullptr;
703 if (IVOperand->
getType() != CI->getType()) {
708 if (SE->getTypeSizeInBits(IVOperand->
getType()) >
709 SE->getTypeSizeInBits(CI->getType())) {
710 Conv = Builder.CreateTrunc(IVOperand, CI->getType(),
Name +
".trunc");
711 }
else if (Opcode == CastInst::FPToUI ||
712 UseInst->
getOpcode() == CastInst::UIToFP) {
713 Conv = Builder.CreateZExt(IVOperand, CI->getType(),
Name +
".zext");
715 Conv = Builder.CreateSExt(IVOperand, CI->getType(),
Name +
".sext");
721 DeadInsts.push_back(CI);
723 <<
" with: " << *Conv <<
'\n');
734bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
736 if (!SE->isSCEVable(UseInst->
getType()) ||
740 const SCEV *UseSCEV = SE->getSCEV(UseInst);
741 if (UseSCEV != SE->getSCEV(IVOperand))
760 if (isa<PHINode>(UseInst))
763 if (!DT || !DT->dominates(IVOperand, UseInst))
766 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
772 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))
776 I->dropPoisonGeneratingAnnotations();
779 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
781 SE->forgetValue(UseInst);
785 DeadInsts.emplace_back(UseInst);
791 return (isa<OverflowingBinaryOperator>(BO) &&
792 strengthenOverflowingOperation(BO, IVOperand)) ||
793 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
798bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
800 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
801 cast<OverflowingBinaryOperator>(BO));
824 if (BO->
getOpcode() == Instruction::Shl) {
825 bool Changed =
false;
826 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
827 for (
auto *U : BO->
users()) {
847void SimplifyIndvar::pushIVUsers(
849 SmallVectorImpl<std::pair<Instruction *, Instruction *>> &SimpleIVUsers) {
862 if (!
L->contains(UI))
869 SimpleIVUsers.push_back(std::make_pair(UI, Def));
907 if (!SE->isSCEVable(CurrIV->
getType()))
919 pushIVUsers(CurrIV, Simplified, SimpleIVUsers);
921 while (!SimpleIVUsers.
empty()) {
922 std::pair<Instruction*, Instruction*> UseOper =
931 DeadInsts.emplace_back(UseInst);
936 if (UseInst == CurrIV)
continue;
940 if (replaceIVUserWithLoopInvariant(UseInst))
945 if ((isa<PtrToIntInst>(UseInst)) || (isa<TruncInst>(UseInst)))
946 for (
Use &U : UseInst->
uses()) {
948 if (replaceIVUserWithLoopInvariant(
User))
953 for (
unsigned N = 0; IVOperand; ++
N) {
957 Value *NewOper = foldIVUser(UseInst, IVOperand);
960 IVOperand = dyn_cast<Instruction>(NewOper);
965 if (eliminateIVUser(UseInst, IVOperand)) {
966 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
971 if (strengthenBinaryOp(BO, IVOperand)) {
974 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
979 if (replaceFloatIVWithIntegerIV(UseInst)) {
981 pushIVUsers(IVOperand, Simplified, SimpleIVUsers);
985 CastInst *Cast = dyn_cast<CastInst>(UseInst);
991 pushIVUsers(UseInst, Simplified, SimpleIVUsers);
1012 SIV.simplifyUsers(CurrIV, V);
1013 return {SIV.hasChanged(), SIV.runUnswitching()};
1025 bool Changed =
false;
1027 const auto &[
C,
_] =
1057 bool UsePostIncrementRanges;
1060 unsigned NumElimExt = 0;
1061 unsigned NumWidened = 0;
1066 const SCEV *WideIncExpr =
nullptr;
1087 std::optional<ConstantRange> getPostIncRangeInfo(
Value *Def,
1089 DefUserPair
Key(Def, UseI);
1090 auto It = PostIncRangeInfos.
find(Key);
1091 return It == PostIncRangeInfos.
end()
1092 ? std::optional<ConstantRange>(std::nullopt)
1096 void calculatePostIncRanges(
PHINode *OrigPhi);
1100 DefUserPair
Key(Def, UseI);
1101 auto It = PostIncRangeInfos.
find(Key);
1102 if (It == PostIncRangeInfos.
end())
1105 It->second =
R.intersectWith(It->second);
1112 struct NarrowIVDefUse {
1120 bool NeverNegative =
false;
1124 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1125 NeverNegative(NeverNegative) {}
1130 bool HasGuards,
bool UsePostIncrementRanges =
true);
1134 unsigned getNumElimExt() {
return NumElimExt; };
1135 unsigned getNumWidened() {
return NumWidened; };
1138 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1142 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1144 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1148 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1150 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1152 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1154 const SCEV *getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1155 unsigned OpCode)
const;
1159 void truncateIVUse(NarrowIVDefUse DU);
1161 bool widenLoopCompare(NarrowIVDefUse DU);
1162 bool widenWithVariantUse(NarrowIVDefUse DU);
1184 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i != e; ++i) {
1185 if (
PHI->getIncomingValue(i) != Def)
1206 auto *DefI = dyn_cast<Instruction>(Def);
1210 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1215 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1217 return DTN->getBlock()->getTerminator();
1225 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1226 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1229 assert(L->getHeader() == OrigPhi->
getParent() &&
"Phi must be an IV");
1230 ExtendKindMap[OrigPhi] = WI.
IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1233Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1239 L &&
L->getLoopPreheader() &&
L->isLoopInvariant(NarrowOper);
1240 L =
L->getParentLoop())
1241 Builder.SetInsertPoint(
L->getLoopPreheader()->getTerminator());
1243 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1244 Builder.CreateZExt(NarrowOper, WideType);
1250Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1252 unsigned Opcode = DU.NarrowUse->
getOpcode();
1256 case Instruction::Add:
1257 case Instruction::Mul:
1258 case Instruction::UDiv:
1259 case Instruction::Sub:
1260 return cloneArithmeticIVUser(DU, WideAR);
1262 case Instruction::And:
1263 case Instruction::Or:
1264 case Instruction::Xor:
1265 case Instruction::Shl:
1266 case Instruction::LShr:
1267 case Instruction::AShr:
1268 return cloneBitwiseIVUser(DU);
1272Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1277 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1283 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1286 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1287 IsSigned, NarrowUse);
1290 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1291 IsSigned, NarrowUse);
1293 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1295 NarrowBO->getName());
1297 Builder.Insert(WideBO);
1298 WideBO->copyIRFlags(NarrowBO);
1302Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1308 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1310 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1321 auto GuessNonIVOperand = [&](
bool SignExt) {
1322 const SCEV *WideLHS;
1323 const SCEV *WideRHS;
1325 auto GetExtend = [
this, SignExt](
const SCEV *S,
Type *Ty) {
1332 WideLHS = SE->
getSCEV(WideDef);
1334 WideRHS = GetExtend(NarrowRHS, WideType);
1337 WideLHS = GetExtend(NarrowLHS, WideType);
1338 WideRHS = SE->
getSCEV(WideDef);
1342 const SCEV *WideUse =
1343 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1345 return WideUse == WideAR;
1348 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1349 if (!GuessNonIVOperand(SignExtend)) {
1350 SignExtend = !SignExtend;
1351 if (!GuessNonIVOperand(SignExtend))
1357 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1358 SignExtend, NarrowUse);
1361 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1362 SignExtend, NarrowUse);
1364 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1366 NarrowBO->getName());
1369 Builder.Insert(WideBO);
1370 WideBO->copyIRFlags(NarrowBO);
1374WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1375 auto It = ExtendKindMap.
find(
I);
1376 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1380const SCEV *WidenIV::getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1381 unsigned OpCode)
const {
1383 case Instruction::Add:
1385 case Instruction::Sub:
1387 case Instruction::Mul:
1389 case Instruction::UDiv:
1410 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
1411 IsNSW = OBO->hasNoSignedWrap();
1412 IsNUW = OBO->hasNoUnsignedWrap();
1417 bool IsNSW =
false,
bool IsNUW =
false)
1418 : Opcode(Opcode),
Operands({
LHS,
RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}
1424 switch (
Op->getOpcode()) {
1425 case Instruction::Add:
1426 case Instruction::Sub:
1427 case Instruction::Mul:
1428 return BinaryOp(
Op);
1429 case Instruction::Or: {
1431 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
1432 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
1436 case Instruction::Shl: {
1437 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
1438 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
1444 if (SA->getValue().ult(
BitWidth)) {
1449 bool IsNUW =
Op->hasNoUnsignedWrap();
1450 bool IsNSW =
Op->hasNoSignedWrap() &&
1451 (IsNUW || SA->getValue().ult(
BitWidth - 1));
1454 ConstantInt::get(
Op->getContext(),
1456 return BinaryOp(Instruction::Mul,
Op->getOperand(0),
X, IsNSW, IsNUW);
1464 return std::nullopt;
1472WidenIV::WidenedRecTy
1473WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1476 return {
nullptr, ExtendKind::Unknown};
1478 assert((
Op->Opcode == Instruction::Add ||
Op->Opcode == Instruction::Sub ||
1479 Op->Opcode == Instruction::Mul) &&
1480 "Unexpected opcode");
1484 const unsigned ExtendOperIdx =
Op->Operands[0] == DU.NarrowDef ? 1 : 0;
1485 assert(
Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef &&
"bad DU");
1487 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1488 if (!(ExtKind == ExtendKind::Sign &&
Op->IsNSW) &&
1489 !(ExtKind == ExtendKind::Zero &&
Op->IsNUW)) {
1490 ExtKind = ExtendKind::Unknown;
1496 if (DU.NeverNegative) {
1498 ExtKind = ExtendKind::Sign;
1499 }
else if (
Op->IsNUW) {
1500 ExtKind = ExtendKind::Zero;
1505 const SCEV *ExtendOperExpr = SE->
getSCEV(
Op->Operands[ExtendOperIdx]);
1506 if (ExtKind == ExtendKind::Sign)
1508 else if (ExtKind == ExtendKind::Zero)
1511 return {
nullptr, ExtendKind::Unknown};
1519 const SCEV *rhs = ExtendOperExpr;
1523 if (ExtendOperIdx == 0)
1526 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs,
Op->Opcode));
1528 if (!AddRec || AddRec->
getLoop() != L)
1529 return {
nullptr, ExtendKind::Unknown};
1531 return {AddRec, ExtKind};
1539WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1540 if (!DU.NarrowUse->getType()->isIntegerTy())
1541 return {
nullptr, ExtendKind::Unknown};
1543 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1548 return {
nullptr, ExtendKind::Unknown};
1551 const SCEV *WideExpr;
1553 if (DU.NeverNegative) {
1555 if (isa<SCEVAddRecExpr>(WideExpr))
1556 ExtKind = ExtendKind::Sign;
1559 ExtKind = ExtendKind::Zero;
1561 }
else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1563 ExtKind = ExtendKind::Sign;
1566 ExtKind = ExtendKind::Zero;
1568 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1569 if (!AddRec || AddRec->
getLoop() != L)
1570 return {
nullptr, ExtendKind::Unknown};
1571 return {AddRec, ExtKind};
1576void WidenIV::truncateIVUse(NarrowIVDefUse DU) {
1580 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1581 << *DU.NarrowUse <<
"\n");
1582 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1585 Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType(),
"",
1586 DU.NeverNegative || ExtKind == ExtendKind::Zero,
1587 DU.NeverNegative || ExtKind == ExtendKind::Sign);
1588 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1594bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1613 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1614 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1617 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1620 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1623 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1626 if (CastWidth < IVWidth) {
1627 Value *ExtOp = createExtendInst(
Op, WideType,
Cmp->isSigned(), Cmp);
1628 DU.NarrowUse->replaceUsesOfWith(
Op, ExtOp);
1653bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1659 const unsigned OpCode = NarrowUse->
getOpcode();
1661 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1662 OpCode != Instruction::Mul)
1672 cast<OverflowingBinaryOperator>(NarrowUse);
1673 ExtendKind ExtKind = getExtendKind(NarrowDef);
1674 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->
hasNoSignedWrap();
1676 auto AnotherOpExtKind = ExtKind;
1686 for (
Use &U : NarrowUse->
uses()) {
1688 if (
User == NarrowDef)
1690 if (!
L->contains(
User)) {
1691 auto *LCSSAPhi = cast<PHINode>(
User);
1694 if (LCSSAPhi->getNumOperands() != 1)
1699 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1705 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1707 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1712 if (ExtKind == ExtendKind::Sign)
1720 if (ExtUsers.
empty()) {
1730 if (!CanSignExtend && !CanZeroExtend) {
1733 if (OpCode != Instruction::Add)
1735 if (ExtKind != ExtendKind::Zero)
1750 AnotherOpExtKind = ExtendKind::Sign;
1756 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1759 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1765 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1766 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1770 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1771 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1773 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1775 NarrowBO->getName());
1777 Builder.Insert(WideBO);
1778 WideBO->copyIRFlags(NarrowBO);
1779 ExtendKindMap[NarrowUse] = ExtKind;
1784 << *WideBO <<
"\n");
1792 Builder.SetInsertPoint(
User);
1794 Builder.CreatePHI(WideBO->getType(), 1,
User->
getName() +
".wide");
1795 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1796 assert(LoopExitingBlock &&
L->contains(LoopExitingBlock) &&
1797 "Not a LCSSA Phi?");
1798 WidePN->addIncoming(WideBO, LoopExitingBlock);
1799 Builder.SetInsertPoint(
User->getParent(),
1800 User->getParent()->getFirstInsertionPt());
1801 auto *TruncPN = Builder.CreateTrunc(WidePN,
User->
getType());
1807 Builder.SetInsertPoint(
User);
1811 if (ExtKind == ExtendKind::Zero)
1812 return Builder.CreateZExt(V, WideBO->getType());
1814 return Builder.CreateSExt(V, WideBO->getType());
1816 auto Pred =
User->getPredicate();
1820 Builder.CreateICmp(Pred, LHS, RHS,
User->
getName() +
".wide");
1830Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,
1834 "Should already know the kind of extension used to widen NarrowDef");
1838 bool CanWidenBySExt =
1839 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1840 bool CanWidenByZExt =
1841 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1844 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1845 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1849 if (UsePhi->getNumOperands() != 1)
1855 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1859 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1860 UsePhi->getIterator());
1861 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1864 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType(),
"",
1865 CanWidenByZExt, CanWidenBySExt);
1868 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1869 << *WidePhi <<
"\n");
1877 (isa<ZExtInst>(DU.NarrowUse) && CanWidenByZExt)) {
1878 Value *NewDef = DU.WideDef;
1879 if (DU.NarrowUse->getType() != WideType) {
1882 if (CastWidth < IVWidth) {
1885 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType(),
"",
1886 CanWidenByZExt, CanWidenBySExt);
1893 <<
" not wide enough to subsume " << *DU.NarrowUse
1895 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1896 NewDef = DU.NarrowUse;
1899 if (NewDef != DU.NarrowUse) {
1901 <<
" replaced by " << *DU.WideDef <<
"\n");
1903 DU.NarrowUse->replaceAllUsesWith(NewDef);
1918 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1919 if (!WideAddRec.first)
1920 WideAddRec = getWideRecurrence(DU);
1921 assert((WideAddRec.first ==
nullptr) ==
1922 (WideAddRec.second == ExtendKind::Unknown));
1923 if (!WideAddRec.first)
1930 bool NeedToRecomputeFlags =
1932 DU.NarrowUse, WideInc) ||
1936 if (WideAddRec.first == WideIncExpr &&
1937 Rewriter.hoistIVInc(WideInc, DU.NarrowUse, NeedToRecomputeFlags))
1940 WideUse = cloneIVUser(DU, WideAddRec.first);
1949 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1950 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1951 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1961 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1966 if (
auto *
I = tryAddRecExpansion())
1971 if (widenLoopCompare(DU))
1979 if (widenWithVariantUse(DU))
1992 bool NonNegativeDef =
1999 if (!Widened.
insert(NarrowUser).second)
2002 bool NonNegativeUse =
false;
2003 if (!NonNegativeDef) {
2005 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
2006 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
2009 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
2010 NonNegativeDef || NonNegativeUse);
2029 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
2034 "Expect the new IV expression to preserve its type");
2037 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
2038 if (!AddRec || AddRec->
getLoop() != L)
2047 "Loop header phi recurrence inputs do not dominate the loop");
2060 calculatePostIncRanges(OrigPhi);
2066 Instruction *InsertPt = &*
L->getHeader()->getFirstInsertionPt();
2067 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
2070 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
2075 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
2088 WideIncExpr = SE->
getSCEV(WideInc);
2105 OrigInc, WideInc) &&
2106 isa<OverflowingBinaryOperator>(OrigInc) &&
2107 isa<OverflowingBinaryOperator>(WideInc)) {
2109 OrigInc->hasNoUnsignedWrap());
2111 OrigInc->hasNoSignedWrap());
2120 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
2123 pushNarrowIVUsers(OrigPhi, WidePhi);
2125 while (!NarrowIVUsers.empty()) {
2126 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
2130 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);
2134 pushNarrowIVUsers(DU.NarrowUse, WideUse);
2137 if (DU.NarrowDef->use_empty())
2149void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
2151 Value *NarrowDefLHS;
2152 const APInt *NarrowDefRHS;
2158 auto UpdateRangeFromCondition = [&] (
Value *Condition,
2170 auto CmpConstrainedLHSRange =
2172 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2175 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2178 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
2183 Ctx->getParent()->rend())) {
2185 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
2186 UpdateRangeFromCondition(
C,
true);
2190 UpdateRangeFromGuards(NarrowUser);
2198 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2199 L->contains(DTB->getBlock());
2200 DTB = DTB->getIDom()) {
2201 auto *BB = DTB->getBlock();
2202 auto *TI = BB->getTerminator();
2203 UpdateRangeFromGuards(TI);
2205 auto *BI = dyn_cast<BranchInst>(TI);
2206 if (!BI || !BI->isConditional())
2209 auto *TrueSuccessor = BI->getSuccessor(0);
2210 auto *FalseSuccessor = BI->getSuccessor(1);
2212 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2213 return BBE.isSingleEdge() &&
2218 UpdateRangeFromCondition(BI->getCondition(),
true);
2221 UpdateRangeFromCondition(BI->getCondition(),
false);
2226void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2232 while (!Worklist.
empty()) {
2235 for (
Use &U : NarrowDef->
uses()) {
2236 auto *NarrowUser = cast<Instruction>(
U.getUser());
2239 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2240 if (!NarrowUserLoop || !
L->contains(NarrowUserLoop))
2243 if (!Visited.
insert(NarrowUser).second)
2248 calculatePostIncRange(NarrowDef, NarrowUser);
2256 unsigned &NumElimExt,
unsigned &NumWidened,
2260 NumElimExt = Widener.getNumElimExt();
2261 NumWidened = Widener.getNumWidened();
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
static const Function * getParent(const Value *V)
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
iv Induction Variable Users
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 cl::opt< bool > WidenIV("loop-flatten-widen-iv", cl::Hidden, cl::init(true), cl::desc("Widen the loop induction variables, if possible, so " "overflow checks won't reject flattening"))
mir Rename Register Operands
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static Instruction * GetLoopInvariantInsertPosition(Loop *L, Instruction *Hint)
static bool isSimpleIVUser(Instruction *I, const Loop *L, ScalarEvolution *SE)
Return true if this instruction generates a simple SCEV expression in terms of that IV.
static Instruction * findCommonDominator(ArrayRef< Instruction * > Instructions, DominatorTree &DT)
Find a point in code which dominates all given instructions.
static Instruction * getInsertPointForUses(Instruction *User, Value *Def, DominatorTree *DT, LoopInfo *LI)
Determine the insertion point for this user.
static std::optional< BinaryOp > matchBinaryOp(Instruction *Op)
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)
static std::optional< unsigned > getOpcode(ArrayRef< VPValue * > Values)
Returns the opcode of Values or ~0 if they do not all agree.
Virtual Register Rewriter
static const uint32_t IV[8]
Class for arbitrary precision integers.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Value handle that asserts if the Value is deleted.
LLVM Basic Block Representation.
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...
bool isSigned() const
Whether the intrinsic is signed or unsigned.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This is the base class for all instructions that perform data casts.
void setPredicate(Predicate P)
Set the predicate for this instruction to the specified value.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
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.
This is the shared class of boolean and integer constants.
static ConstantInt * getFalse(LLVMContext &Context)
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
This class represents an Operation in the Expression.
iterator find(const_arg_type_t< KeyT > Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
Instruction * findNearestCommonDominator(Instruction *I1, Instruction *I2) const
Find the nearest instruction I that dominates both I1 and I2, in the sense that a result produced bef...
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
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.
void setHasNoUnsignedWrap(bool b=true)
Set or clear the nuw flag on this instruction, which must be an operator which supports this flag.
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void setIsExact(bool b=true)
Set or clear the exact flag on this instruction, which must be an operator which supports this flag.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
bool hasNoSignedWrap() const
Test whether this operation is known to never undergo signed overflow, aka the nsw property.
bool hasNoUnsignedWrap() const
Test whether this operation is known to never undergo unsigned overflow, aka the nuw property.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Value * getIncomingValueForBlock(const BasicBlock *BB) const
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
This node represents a polynomial recurrence on the trip count of the specified loop.
const SCEV * getStart() const
const SCEV * getStepRecurrence(ScalarEvolution &SE) const
Constructs and returns the recurrence indicating how much this expression steps by.
const Loop * getLoop() const
This class uses information about analyze scalars to rewrite expressions in canonical form.
static bool canReuseFlagsFromOriginalIVInc(PHINode *OrigPhi, PHINode *WidePhi, Instruction *OrigInc, Instruction *WideInc)
Return true if both increments directly increment the corresponding IV PHI nodes and have the same op...
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
Represents a saturating add/sub intrinsic.
The main scalar evolution driver.
const DataLayout & getDataLayout() const
Return the DataLayout associated with the module this SCEV instance is operating on.
const SCEV * getNegativeSCEV(const SCEV *V, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap)
Return the SCEV object corresponding to -V.
bool isKnownNegative(const SCEV *S)
Test if the given expression is known to be negative.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
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.
ConstantRange getSignedRange(const SCEV *S)
Determine the signed range for a particular SCEV.
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 isKnownPredicate(ICmpInst::Predicate Pred, const SCEV *LHS, const SCEV *RHS)
Test if the given expression is known to satisfy the condition described by Pred, LHS,...
const SCEV * getUDivExpr(const SCEV *LHS, const SCEV *RHS)
Get a canonical unsigned division expression, or something simpler if possible.
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...
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
const SCEV * getSignExtendExpr(const SCEV *Op, Type *Ty, unsigned Depth=0)
const SCEV * getMulExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical multiply expression, or something simpler if possible.
static SCEV::NoWrapFlags maskFlags(SCEV::NoWrapFlags Flags, int Mask)
Convenient NoWrapFlags manipulation that hides enum casts and is visible in the ScalarEvolution name ...
bool properlyDominates(const SCEV *S, const BasicBlock *BB)
Return true if elements that makes up the given SCEV properly dominate the specified basic block.
const SCEV * getAddExpr(SmallVectorImpl< const SCEV * > &Ops, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)
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.
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.
StringRef - Represent a constant reference to a string, i.e.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
int getFPMantissaWidth() const
Return the width of the mantissa of this type.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
bool hasNUses(unsigned N) const
Return true if this Value has exactly N uses.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
Represents an op.with.overflow intrinsic.
const ParentTy * getParent() const
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, SExtInst >, NNegZExt_match< OpTy > > m_SExtLike(const OpTy &Op)
Match either "sext" or "zext nneg".
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
NodeAddr< DefNode * > Def
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool impliesPoison(const Value *ValAssumedPoison, const Value *V)
Return true if V is poison given that ValAssumedPoison is already poison.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< unsigned > SCEVCheapExpansionBudget
bool simplifyLoopIVs(Loop *L, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead)
SimplifyLoopIVs - Simplify users of induction variables within this loop.
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
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...
constexpr unsigned BitWidth
bool formLCSSAForInstructions(SmallVectorImpl< Instruction * > &Worklist, const DominatorTree &DT, const LoopInfo &LI, ScalarEvolution *SE, SmallVectorImpl< PHINode * > *PHIsToRemove=nullptr, SmallVectorImpl< PHINode * > *InsertedPHIs=nullptr)
Ensures LCSSA form for every instruction from the Worklist in the scope of innermost containing loop.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Collect information about induction variables that are used by sign/zero extend operations.