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; }
86 bool replaceIVUserWithLoopInvariant(
Instruction *UseInst);
87 bool replaceFloatIVWithIntegerIV(
Instruction *UseInst);
114 for (
auto *
Insn : Instructions)
117 assert(CommonDom &&
"Common dominator not found?");
130 Value *IVSrc =
nullptr;
131 const unsigned OperIdx = 0;
132 const SCEV *FoldedExpr =
nullptr;
133 bool MustDropExactFlag =
false;
137 case Instruction::UDiv:
138 case Instruction::LShr:
141 if (IVOperand != UseInst->
getOperand(OperIdx) ||
147 if (!isa<BinaryOperator>(IVOperand)
148 || !isa<ConstantInt>(IVOperand->
getOperand(1)))
153 assert(SE->isSCEVable(IVSrc->
getType()) &&
"Expect SCEVable IV operand");
156 if (UseInst->
getOpcode() == Instruction::LShr) {
165 const auto *
LHS = SE->getSCEV(IVSrc);
166 const auto *
RHS = SE->getSCEV(
D);
167 FoldedExpr = SE->getUDivExpr(LHS, RHS);
170 if (UseInst->
isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
171 MustDropExactFlag =
true;
174 if (!SE->isSCEVable(UseInst->
getType()))
178 if (SE->getSCEV(UseInst) != FoldedExpr)
181 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated IV operand: " << *IVOperand
182 <<
" -> " << *UseInst <<
'\n');
185 assert(SE->getSCEV(UseInst) == FoldedExpr &&
"bad SCEV with folded oper");
187 if (MustDropExactFlag)
193 DeadInsts.emplace_back(IVOperand);
197bool SimplifyIndvar::makeIVComparisonInvariant(
ICmpInst *ICmp,
199 auto *Preheader =
L->getLoopPreheader();
202 unsigned IVOperIdx = 0;
208 Pred = ICmpInst::getSwappedPredicate(Pred);
214 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
215 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
216 auto LIP = SE->getLoopInvariantPredicate(Pred, S,
X, L, ICmp);
220 const SCEV *InvariantLHS = LIP->LHS;
221 const SCEV *InvariantRHS = LIP->RHS;
224 auto *PHTerm = Preheader->getTerminator();
225 if (
Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,
227 !
Rewriter.isSafeToExpandAt(InvariantLHS, PHTerm) ||
228 !
Rewriter.isSafeToExpandAt(InvariantRHS, PHTerm))
234 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
238 RunUnswitching =
true;
244void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
246 unsigned IVOperIdx = 0;
253 Pred = ICmpInst::getSwappedPredicate(Pred);
259 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
260 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
265 for (
auto *U : ICmp->
users())
266 Users.push_back(cast<Instruction>(U));
268 if (
auto Ev = SE->evaluatePredicateAt(Pred, S,
X, CtxI)) {
269 SE->forgetValue(ICmp);
271 DeadInsts.emplace_back(ICmp);
272 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
273 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
275 }
else if (ICmpInst::isSigned(OriginalPred) &&
276 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(
X)) {
283 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
300 N = SE->getSCEVAtScope(
N, L);
301 D = SE->getSCEVAtScope(
D, L);
304 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
308 UDiv->setIsExact(SDiv->
isExact());
310 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
313 DeadInsts.push_back(SDiv);
326 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
329 DeadInsts.emplace_back(Rem);
333void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
335 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
338 DeadInsts.emplace_back(Rem);
342void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
349 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
352 DeadInsts.emplace_back(Rem);
365 bool UsedAsNumerator = IVOperand == NValue;
366 if (!UsedAsNumerator && !IsSigned)
369 const SCEV *
N = SE->getSCEV(NValue);
373 N = SE->getSCEVAtScope(
N, ICmpLoop);
375 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
378 if (!IsNumeratorNonNegative)
381 const SCEV *
D = SE->getSCEV(DValue);
382 D = SE->getSCEVAtScope(
D, ICmpLoop);
384 if (UsedAsNumerator) {
385 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
386 if (SE->isKnownPredicate(LT,
N,
D)) {
387 replaceRemWithNumerator(Rem);
392 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
393 if (SE->isKnownPredicate(LT, NLessOne,
D)) {
394 replaceRemWithNumeratorOrZero(Rem);
401 if (!IsSigned || !SE->isKnownNonNegative(
D))
404 replaceSRemWithURem(Rem);
426 for (
auto *U : WO->
users()) {
427 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
428 if (EVI->getIndices()[0] == 1)
431 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
432 EVI->replaceAllUsesWith(NewResult);
438 for (
auto *EVI : ToDelete)
439 EVI->eraseFromParent();
448bool SimplifyIndvar::eliminateSaturatingIntrinsic(
SaturatingInst *SI) {
449 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
450 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
451 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(), LHS, RHS))
455 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(),
SI->getIterator());
461 SI->replaceAllUsesWith(BO);
462 DeadInsts.emplace_back(SI);
467bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
485 Type *IVTy =
IV->getType();
486 const SCEV *IVSCEV = SE->getSCEV(
IV);
487 const SCEV *TISCEV = SE->getSCEV(TI);
491 bool DoesSExtCollapse =
false;
492 bool DoesZExtCollapse =
false;
493 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
494 DoesSExtCollapse =
true;
495 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
496 DoesZExtCollapse =
true;
500 if (!DoesSExtCollapse && !DoesZExtCollapse)
506 for (
auto *U : TI->
users()) {
508 if (isa<Instruction>(U) &&
509 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
511 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
512 if (!ICI)
return false;
518 if (ICI->
isSigned() && !DoesSExtCollapse)
526 auto CanUseZExt = [&](
ICmpInst *ICI) {
531 if (!DoesZExtCollapse)
542 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
545 for (
auto *ICI : ICmpUsers) {
546 bool IsSwapped =
L->isLoopInvariant(ICI->
getOperand(0));
557 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
558 if (CanUseZExt(ICI)) {
559 assert(DoesZExtCollapse &&
"Unprofitable zext?");
560 Ext = Builder.CreateZExt(Op1, IVTy,
"zext");
563 assert(DoesSExtCollapse &&
"Unprofitable sext?");
564 Ext = Builder.CreateSExt(Op1, IVTy,
"sext");
568 L->makeLoopInvariant(Ext, Changed);
570 auto *NewCmp = Builder.CreateICmp(Pred,
IV, Ext);
572 DeadInsts.emplace_back(ICI);
577 DeadInsts.emplace_back(TI);
584bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
586 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
587 eliminateIVComparison(ICmp, IVOperand);
591 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
592 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
593 simplifyIVRemainder(
Bin, IVOperand, IsSRem);
597 if (
Bin->getOpcode() == Instruction::SDiv)
598 return eliminateSDiv(
Bin);
601 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
602 if (eliminateOverflowIntrinsic(WO))
605 if (
auto *SI = dyn_cast<SaturatingInst>(UseInst))
606 if (eliminateSaturatingIntrinsic(SI))
609 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
610 if (eliminateTrunc(TI))
613 if (eliminateIdentitySCEV(UseInst, IVOperand))
620 if (
auto *BB = L->getLoopPreheader())
621 return BB->getTerminator();
627bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
628 if (!SE->isSCEVable(
I->getType()))
632 const SCEV *S = SE->getSCEV(
I);
634 if (!SE->isLoopInvariant(S, L))
643 if (!
Rewriter.isSafeToExpandAt(S, IP)) {
645 <<
" with non-speculable loop invariant: " << *S <<
'\n');
649 auto *Invariant =
Rewriter.expandCodeFor(S,
I->getType(), IP);
650 bool NeedToEmitLCSSAPhis =
false;
651 if (!LI->replacementPreservesLCSSAForm(
I, Invariant))
652 NeedToEmitLCSSAPhis =
true;
654 I->replaceAllUsesWith(Invariant);
656 <<
" with loop invariant: " << *S <<
'\n');
658 if (NeedToEmitLCSSAPhis) {
660 NeedsLCSSAPhis.
push_back(cast<Instruction>(Invariant));
663 <<
" inserting LCSSA Phis" <<
'\n');
667 DeadInsts.emplace_back(
I);
672bool SimplifyIndvar::replaceFloatIVWithIntegerIV(
Instruction *UseInst) {
673 if (UseInst->
getOpcode() != CastInst::SIToFP &&
674 UseInst->
getOpcode() != CastInst::UIToFP)
679 const SCEV *
IV = SE->getSCEV(IVOperand);
681 if (UseInst->
getOpcode() == CastInst::SIToFP)
682 MaskBits = (int)SE->getSignedRange(
IV).getMinSignedBits();
684 MaskBits = (int)SE->getUnsignedRange(
IV).getActiveBits();
686 if (MaskBits <= DestNumSigBits) {
689 auto *CI = dyn_cast<CastInst>(U);
694 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
697 Value *Conv =
nullptr;
698 if (IVOperand->
getType() != CI->getType()) {
703 if (SE->getTypeSizeInBits(IVOperand->
getType()) >
704 SE->getTypeSizeInBits(CI->getType())) {
705 Conv = Builder.CreateTrunc(IVOperand, CI->getType(),
Name +
".trunc");
706 }
else if (Opcode == CastInst::FPToUI ||
707 UseInst->
getOpcode() == CastInst::UIToFP) {
708 Conv = Builder.CreateZExt(IVOperand, CI->getType(),
Name +
".zext");
710 Conv = Builder.CreateSExt(IVOperand, CI->getType(),
Name +
".sext");
716 DeadInsts.push_back(CI);
718 <<
" with: " << *Conv <<
'\n');
729bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
731 if (!SE->isSCEVable(UseInst->
getType()) ||
735 const SCEV *UseSCEV = SE->getSCEV(UseInst);
736 if (UseSCEV != SE->getSCEV(IVOperand))
755 if (isa<PHINode>(UseInst))
758 if (!DT || !DT->dominates(IVOperand, UseInst))
761 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
767 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))
771 I->dropPoisonGeneratingAnnotations();
774 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
776 SE->forgetValue(UseInst);
780 DeadInsts.emplace_back(UseInst);
786 return (isa<OverflowingBinaryOperator>(BO) &&
787 strengthenOverflowingOperation(BO, IVOperand)) ||
788 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
793bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
795 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
796 cast<OverflowingBinaryOperator>(BO));
819 if (BO->
getOpcode() == Instruction::Shl) {
820 bool Changed =
false;
821 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
822 for (
auto *U : BO->
users()) {
845 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
847 for (
User *U : Def->users()) {
859 if (!L->contains(UI))
863 if (!Simplified.insert(UI).second)
866 SimpleIVUsers.push_back(std::make_pair(UI, Def));
904 if (!SE->isSCEVable(CurrIV->
getType()))
918 while (!SimpleIVUsers.
empty()) {
919 std::pair<Instruction*, Instruction*> UseOper =
928 DeadInsts.emplace_back(UseInst);
933 if (UseInst == CurrIV)
continue;
937 if (replaceIVUserWithLoopInvariant(UseInst))
942 if ((isa<PtrToIntInst>(UseInst)) || (isa<TruncInst>(UseInst)))
943 for (
Use &U : UseInst->
uses()) {
945 if (replaceIVUserWithLoopInvariant(
User))
950 for (
unsigned N = 0; IVOperand; ++
N) {
954 Value *NewOper = foldIVUser(UseInst, IVOperand);
957 IVOperand = dyn_cast<Instruction>(NewOper);
962 if (eliminateIVUser(UseInst, IVOperand)) {
963 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
968 if (strengthenBinaryOp(BO, IVOperand)) {
971 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
976 if (replaceFloatIVWithIntegerIV(UseInst)) {
978 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
982 CastInst *Cast = dyn_cast<CastInst>(UseInst);
988 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
1009 SIV.simplifyUsers(CurrIV, V);
1010 return {SIV.hasChanged(), SIV.runUnswitching()};
1022 bool Changed =
false;
1024 const auto &[
C,
_] =
1054 bool UsePostIncrementRanges;
1057 unsigned NumElimExt = 0;
1058 unsigned NumWidened = 0;
1063 const SCEV *WideIncExpr =
nullptr;
1084 std::optional<ConstantRange> getPostIncRangeInfo(
Value *Def,
1086 DefUserPair
Key(Def, UseI);
1087 auto It = PostIncRangeInfos.
find(Key);
1088 return It == PostIncRangeInfos.
end()
1089 ? std::optional<ConstantRange>(std::nullopt)
1093 void calculatePostIncRanges(
PHINode *OrigPhi);
1097 DefUserPair
Key(Def, UseI);
1098 auto It = PostIncRangeInfos.
find(Key);
1099 if (It == PostIncRangeInfos.
end())
1102 It->second =
R.intersectWith(It->second);
1109 struct NarrowIVDefUse {
1117 bool NeverNegative =
false;
1121 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1122 NeverNegative(NeverNegative) {}
1127 bool HasGuards,
bool UsePostIncrementRanges =
true);
1131 unsigned getNumElimExt() {
return NumElimExt; };
1132 unsigned getNumWidened() {
return NumWidened; };
1135 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1139 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1141 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1145 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1147 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1149 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1151 const SCEV *getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1152 unsigned OpCode)
const;
1156 void truncateIVUse(NarrowIVDefUse DU);
1158 bool widenLoopCompare(NarrowIVDefUse DU);
1159 bool widenWithVariantUse(NarrowIVDefUse DU);
1181 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i != e; ++i) {
1182 if (
PHI->getIncomingValue(i) != Def)
1203 auto *DefI = dyn_cast<Instruction>(Def);
1207 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1212 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1214 return DTN->getBlock()->getTerminator();
1222 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1223 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1226 assert(L->getHeader() == OrigPhi->
getParent() &&
"Phi must be an IV");
1227 ExtendKindMap[OrigPhi] = WI.
IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1230Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1236 L &&
L->getLoopPreheader() &&
L->isLoopInvariant(NarrowOper);
1237 L =
L->getParentLoop())
1238 Builder.SetInsertPoint(
L->getLoopPreheader()->getTerminator());
1240 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1241 Builder.CreateZExt(NarrowOper, WideType);
1247Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1249 unsigned Opcode = DU.NarrowUse->
getOpcode();
1253 case Instruction::Add:
1254 case Instruction::Mul:
1255 case Instruction::UDiv:
1256 case Instruction::Sub:
1257 return cloneArithmeticIVUser(DU, WideAR);
1259 case Instruction::And:
1260 case Instruction::Or:
1261 case Instruction::Xor:
1262 case Instruction::Shl:
1263 case Instruction::LShr:
1264 case Instruction::AShr:
1265 return cloneBitwiseIVUser(DU);
1269Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1274 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1280 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1283 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1284 IsSigned, NarrowUse);
1287 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1288 IsSigned, NarrowUse);
1290 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1292 NarrowBO->getName());
1294 Builder.Insert(WideBO);
1295 WideBO->copyIRFlags(NarrowBO);
1299Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1305 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1307 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1318 auto GuessNonIVOperand = [&](
bool SignExt) {
1319 const SCEV *WideLHS;
1320 const SCEV *WideRHS;
1322 auto GetExtend = [
this, SignExt](
const SCEV *S,
Type *Ty) {
1329 WideLHS = SE->
getSCEV(WideDef);
1331 WideRHS = GetExtend(NarrowRHS, WideType);
1334 WideLHS = GetExtend(NarrowLHS, WideType);
1335 WideRHS = SE->
getSCEV(WideDef);
1339 const SCEV *WideUse =
1340 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1342 return WideUse == WideAR;
1345 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1346 if (!GuessNonIVOperand(SignExtend)) {
1347 SignExtend = !SignExtend;
1348 if (!GuessNonIVOperand(SignExtend))
1354 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1355 SignExtend, NarrowUse);
1358 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1359 SignExtend, NarrowUse);
1361 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1363 NarrowBO->getName());
1366 Builder.Insert(WideBO);
1367 WideBO->copyIRFlags(NarrowBO);
1371WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1372 auto It = ExtendKindMap.
find(
I);
1373 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1377const SCEV *WidenIV::getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1378 unsigned OpCode)
const {
1380 case Instruction::Add:
1382 case Instruction::Sub:
1384 case Instruction::Mul:
1386 case Instruction::UDiv:
1407 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
1408 IsNSW = OBO->hasNoSignedWrap();
1409 IsNUW = OBO->hasNoUnsignedWrap();
1414 bool IsNSW =
false,
bool IsNUW =
false)
1415 : Opcode(Opcode),
Operands({
LHS,
RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}
1421 switch (
Op->getOpcode()) {
1422 case Instruction::Add:
1423 case Instruction::Sub:
1424 case Instruction::Mul:
1425 return BinaryOp(
Op);
1426 case Instruction::Or: {
1428 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
1429 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
1433 case Instruction::Shl: {
1434 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
1435 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
1441 if (SA->getValue().ult(
BitWidth)) {
1446 bool IsNUW =
Op->hasNoUnsignedWrap();
1447 bool IsNSW =
Op->hasNoSignedWrap() &&
1448 (IsNUW || SA->getValue().ult(
BitWidth - 1));
1451 ConstantInt::get(
Op->getContext(),
1453 return BinaryOp(Instruction::Mul,
Op->getOperand(0),
X, IsNSW, IsNUW);
1461 return std::nullopt;
1469WidenIV::WidenedRecTy
1470WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1473 return {
nullptr, ExtendKind::Unknown};
1475 assert((
Op->Opcode == Instruction::Add ||
Op->Opcode == Instruction::Sub ||
1476 Op->Opcode == Instruction::Mul) &&
1477 "Unexpected opcode");
1481 const unsigned ExtendOperIdx =
Op->Operands[0] == DU.NarrowDef ? 1 : 0;
1482 assert(
Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef &&
"bad DU");
1484 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1485 if (!(ExtKind == ExtendKind::Sign &&
Op->IsNSW) &&
1486 !(ExtKind == ExtendKind::Zero &&
Op->IsNUW)) {
1487 ExtKind = ExtendKind::Unknown;
1493 if (DU.NeverNegative) {
1495 ExtKind = ExtendKind::Sign;
1496 }
else if (
Op->IsNUW) {
1497 ExtKind = ExtendKind::Zero;
1502 const SCEV *ExtendOperExpr = SE->
getSCEV(
Op->Operands[ExtendOperIdx]);
1503 if (ExtKind == ExtendKind::Sign)
1505 else if (ExtKind == ExtendKind::Zero)
1508 return {
nullptr, ExtendKind::Unknown};
1516 const SCEV *rhs = ExtendOperExpr;
1520 if (ExtendOperIdx == 0)
1523 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs,
Op->Opcode));
1525 if (!AddRec || AddRec->
getLoop() != L)
1526 return {
nullptr, ExtendKind::Unknown};
1528 return {AddRec, ExtKind};
1536WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1537 if (!DU.NarrowUse->getType()->isIntegerTy())
1538 return {
nullptr, ExtendKind::Unknown};
1540 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1545 return {
nullptr, ExtendKind::Unknown};
1548 const SCEV *WideExpr;
1550 if (DU.NeverNegative) {
1552 if (isa<SCEVAddRecExpr>(WideExpr))
1553 ExtKind = ExtendKind::Sign;
1556 ExtKind = ExtendKind::Zero;
1558 }
else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1560 ExtKind = ExtendKind::Sign;
1563 ExtKind = ExtendKind::Zero;
1565 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1566 if (!AddRec || AddRec->
getLoop() != L)
1567 return {
nullptr, ExtendKind::Unknown};
1568 return {AddRec, ExtKind};
1573void WidenIV::truncateIVUse(NarrowIVDefUse DU) {
1577 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1578 << *DU.NarrowUse <<
"\n");
1579 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1582 Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType(),
"",
1583 DU.NeverNegative || ExtKind == ExtendKind::Zero,
1584 DU.NeverNegative || ExtKind == ExtendKind::Sign);
1585 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1591bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1610 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1611 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1614 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1617 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1620 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1623 if (CastWidth < IVWidth) {
1624 Value *ExtOp = createExtendInst(
Op, WideType,
Cmp->isSigned(), Cmp);
1625 DU.NarrowUse->replaceUsesOfWith(
Op, ExtOp);
1650bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1656 const unsigned OpCode = NarrowUse->
getOpcode();
1658 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1659 OpCode != Instruction::Mul)
1669 cast<OverflowingBinaryOperator>(NarrowUse);
1670 ExtendKind ExtKind = getExtendKind(NarrowDef);
1671 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->
hasNoSignedWrap();
1673 auto AnotherOpExtKind = ExtKind;
1683 for (
Use &U : NarrowUse->
uses()) {
1685 if (
User == NarrowDef)
1687 if (!
L->contains(
User)) {
1688 auto *LCSSAPhi = cast<PHINode>(
User);
1691 if (LCSSAPhi->getNumOperands() != 1)
1696 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1702 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1704 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1709 if (ExtKind == ExtendKind::Sign)
1717 if (ExtUsers.
empty()) {
1727 if (!CanSignExtend && !CanZeroExtend) {
1730 if (OpCode != Instruction::Add)
1732 if (ExtKind != ExtendKind::Zero)
1747 AnotherOpExtKind = ExtendKind::Sign;
1753 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1756 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1762 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1763 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1767 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1768 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1770 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1772 NarrowBO->getName());
1774 Builder.Insert(WideBO);
1775 WideBO->copyIRFlags(NarrowBO);
1776 ExtendKindMap[NarrowUse] = ExtKind;
1781 << *WideBO <<
"\n");
1789 Builder.SetInsertPoint(
User);
1791 Builder.CreatePHI(WideBO->getType(), 1,
User->
getName() +
".wide");
1792 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1793 assert(LoopExitingBlock &&
L->contains(LoopExitingBlock) &&
1794 "Not a LCSSA Phi?");
1795 WidePN->addIncoming(WideBO, LoopExitingBlock);
1796 Builder.SetInsertPoint(
User->getParent(),
1797 User->getParent()->getFirstInsertionPt());
1798 auto *TruncPN = Builder.CreateTrunc(WidePN,
User->
getType());
1804 Builder.SetInsertPoint(
User);
1808 if (ExtKind == ExtendKind::Zero)
1809 return Builder.CreateZExt(V, WideBO->getType());
1811 return Builder.CreateSExt(V, WideBO->getType());
1813 auto Pred =
User->getPredicate();
1817 Builder.CreateICmp(Pred, LHS, RHS,
User->
getName() +
".wide");
1827Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,
1831 "Should already know the kind of extension used to widen NarrowDef");
1835 bool CanWidenBySExt =
1836 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1837 bool CanWidenByZExt =
1838 DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1841 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1842 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1846 if (UsePhi->getNumOperands() != 1)
1852 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1856 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1857 UsePhi->getIterator());
1858 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1861 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType(),
"",
1862 CanWidenByZExt, CanWidenBySExt);
1865 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1866 << *WidePhi <<
"\n");
1874 (isa<ZExtInst>(DU.NarrowUse) && CanWidenByZExt)) {
1875 Value *NewDef = DU.WideDef;
1876 if (DU.NarrowUse->getType() != WideType) {
1879 if (CastWidth < IVWidth) {
1882 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType(),
"",
1883 CanWidenByZExt, CanWidenBySExt);
1890 <<
" not wide enough to subsume " << *DU.NarrowUse
1892 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1893 NewDef = DU.NarrowUse;
1896 if (NewDef != DU.NarrowUse) {
1898 <<
" replaced by " << *DU.WideDef <<
"\n");
1900 DU.NarrowUse->replaceAllUsesWith(NewDef);
1915 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1916 if (!WideAddRec.first)
1917 WideAddRec = getWideRecurrence(DU);
1918 assert((WideAddRec.first ==
nullptr) ==
1919 (WideAddRec.second == ExtendKind::Unknown));
1920 if (!WideAddRec.first)
1927 bool NeedToRecomputeFlags =
1929 DU.NarrowUse, WideInc) ||
1933 if (WideAddRec.first == WideIncExpr &&
1934 Rewriter.hoistIVInc(WideInc, DU.NarrowUse, NeedToRecomputeFlags))
1937 WideUse = cloneIVUser(DU, WideAddRec.first);
1946 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1947 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1948 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1958 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1963 if (
auto *
I = tryAddRecExpansion())
1968 if (widenLoopCompare(DU))
1976 if (widenWithVariantUse(DU))
1989 bool NonNegativeDef =
1996 if (!Widened.
insert(NarrowUser).second)
1999 bool NonNegativeUse =
false;
2000 if (!NonNegativeDef) {
2002 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
2003 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
2006 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
2007 NonNegativeDef || NonNegativeUse);
2026 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
2031 "Expect the new IV expression to preserve its type");
2034 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
2035 if (!AddRec || AddRec->
getLoop() != L)
2044 "Loop header phi recurrence inputs do not dominate the loop");
2057 calculatePostIncRanges(OrigPhi);
2063 Instruction *InsertPt = &*
L->getHeader()->getFirstInsertionPt();
2064 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
2067 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
2072 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
2085 WideIncExpr = SE->
getSCEV(WideInc);
2102 OrigInc, WideInc) &&
2103 isa<OverflowingBinaryOperator>(OrigInc) &&
2104 isa<OverflowingBinaryOperator>(WideInc)) {
2106 OrigInc->hasNoUnsignedWrap());
2108 OrigInc->hasNoSignedWrap());
2117 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
2120 pushNarrowIVUsers(OrigPhi, WidePhi);
2122 while (!NarrowIVUsers.empty()) {
2123 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
2127 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);
2131 pushNarrowIVUsers(DU.NarrowUse, WideUse);
2134 if (DU.NarrowDef->use_empty())
2146void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
2148 Value *NarrowDefLHS;
2149 const APInt *NarrowDefRHS;
2155 auto UpdateRangeFromCondition = [&] (
Value *Condition,
2167 auto CmpConstrainedLHSRange =
2169 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2172 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2175 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
2180 Ctx->getParent()->rend())) {
2182 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
2183 UpdateRangeFromCondition(
C,
true);
2187 UpdateRangeFromGuards(NarrowUser);
2195 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2196 L->contains(DTB->getBlock());
2197 DTB = DTB->getIDom()) {
2198 auto *BB = DTB->getBlock();
2199 auto *TI = BB->getTerminator();
2200 UpdateRangeFromGuards(TI);
2202 auto *BI = dyn_cast<BranchInst>(TI);
2203 if (!BI || !BI->isConditional())
2206 auto *TrueSuccessor = BI->getSuccessor(0);
2207 auto *FalseSuccessor = BI->getSuccessor(1);
2209 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2210 return BBE.isSingleEdge() &&
2215 UpdateRangeFromCondition(BI->getCondition(),
true);
2218 UpdateRangeFromCondition(BI->getCondition(),
false);
2223void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2229 while (!Worklist.
empty()) {
2232 for (
Use &U : NarrowDef->
uses()) {
2233 auto *NarrowUser = cast<Instruction>(
U.getUser());
2236 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2237 if (!NarrowUserLoop || !
L->contains(NarrowUserLoop))
2240 if (!Visited.
insert(NarrowUser).second)
2245 calculatePostIncRange(NarrowDef, NarrowUser);
2253 unsigned &NumElimExt,
unsigned &NumWidened,
2257 NumElimExt = Widener.getNumElimExt();
2258 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 void pushIVUsers(Instruction *Def, Loop *L, SmallPtrSet< Instruction *, 16 > &Simplified, SmallVectorImpl< std::pair< Instruction *, Instruction * > > &SimpleIVUsers)
Add all uses of Def to the current IV's worklist.
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.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
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.
const BasicBlock * getParent() const
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.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
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, BasicBlock::iterator InsertBefore, 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.
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)
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.