31#define DEBUG_TYPE "indvars"
33STATISTIC(NumElimIdentity,
"Number of IV identities eliminated");
34STATISTIC(NumElimOperand,
"Number of IV operands folded into a use");
35STATISTIC(NumFoldedUser,
"Number of IV users folded into a constant");
36STATISTIC(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");
43STATISTIC(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);
82 bool replaceFloatIVWithIntegerIV(
Instruction *UseInst);
109 for (
auto *
Insn : Instructions)
112 assert(CommonDom &&
"Common dominator not found?");
125 Value *IVSrc =
nullptr;
126 const unsigned OperIdx = 0;
127 const SCEV *FoldedExpr =
nullptr;
128 bool MustDropExactFlag =
false;
132 case Instruction::UDiv:
133 case Instruction::LShr:
136 if (IVOperand != UseInst->
getOperand(OperIdx) ||
142 if (!isa<BinaryOperator>(IVOperand)
143 || !isa<ConstantInt>(IVOperand->
getOperand(1)))
148 assert(SE->isSCEVable(IVSrc->
getType()) &&
"Expect SCEVable IV operand");
151 if (UseInst->
getOpcode() == Instruction::LShr) {
160 const auto *
LHS = SE->getSCEV(IVSrc);
161 const auto *
RHS = SE->getSCEV(
D);
162 FoldedExpr = SE->getUDivExpr(LHS, RHS);
165 if (UseInst->
isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
166 MustDropExactFlag =
true;
169 if (!SE->isSCEVable(UseInst->
getType()))
173 if (SE->getSCEV(UseInst) != FoldedExpr)
176 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated IV operand: " << *IVOperand
177 <<
" -> " << *UseInst <<
'\n');
180 assert(SE->getSCEV(UseInst) == FoldedExpr &&
"bad SCEV with folded oper");
182 if (MustDropExactFlag)
188 DeadInsts.emplace_back(IVOperand);
192bool SimplifyIndvar::makeIVComparisonInvariant(
ICmpInst *ICmp,
194 auto *Preheader =
L->getLoopPreheader();
197 unsigned IVOperIdx = 0;
203 Pred = ICmpInst::getSwappedPredicate(Pred);
209 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
210 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
211 auto LIP = SE->getLoopInvariantPredicate(Pred, S,
X, L, ICmp);
215 const SCEV *InvariantLHS = LIP->LHS;
216 const SCEV *InvariantRHS = LIP->RHS;
219 auto *PHTerm = Preheader->getTerminator();
220 if (
Rewriter.isHighCostExpansion({ InvariantLHS, InvariantRHS }, L,
227 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
236void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
238 unsigned IVOperIdx = 0;
245 Pred = ICmpInst::getSwappedPredicate(Pred);
251 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
252 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
257 for (
auto *U : ICmp->
users())
258 Users.push_back(cast<Instruction>(U));
260 if (
auto Ev = SE->evaluatePredicateAt(Pred, S,
X, CtxI)) {
261 SE->forgetValue(ICmp);
263 DeadInsts.emplace_back(ICmp);
264 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
265 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
267 }
else if (ICmpInst::isSigned(OriginalPred) &&
268 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(
X)) {
275 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
292 N = SE->getSCEVAtScope(
N, L);
293 D = SE->getSCEVAtScope(
D, L);
296 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
299 SDiv->
getName() +
".udiv", SDiv);
300 UDiv->setIsExact(SDiv->
isExact());
302 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
305 DeadInsts.push_back(SDiv);
316 Rem->
getName() +
".urem", Rem);
318 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
321 DeadInsts.emplace_back(Rem);
325void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
327 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
330 DeadInsts.emplace_back(Rem);
334void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
341 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
344 DeadInsts.emplace_back(Rem);
357 bool UsedAsNumerator = IVOperand == NValue;
358 if (!UsedAsNumerator && !IsSigned)
361 const SCEV *
N = SE->getSCEV(NValue);
365 N = SE->getSCEVAtScope(
N, ICmpLoop);
367 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
370 if (!IsNumeratorNonNegative)
373 const SCEV *
D = SE->getSCEV(DValue);
374 D = SE->getSCEVAtScope(
D, ICmpLoop);
376 if (UsedAsNumerator) {
377 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
378 if (SE->isKnownPredicate(LT,
N,
D)) {
379 replaceRemWithNumerator(Rem);
384 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
385 if (SE->isKnownPredicate(LT, NLessOne,
D)) {
386 replaceRemWithNumeratorOrZero(Rem);
393 if (!IsSigned || !SE->isKnownNonNegative(
D))
396 replaceSRemWithURem(Rem);
418 for (
auto *U : WO->
users()) {
419 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
420 if (EVI->getIndices()[0] == 1)
423 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
424 EVI->replaceAllUsesWith(NewResult);
430 for (
auto *EVI : ToDelete)
431 EVI->eraseFromParent();
440bool SimplifyIndvar::eliminateSaturatingIntrinsic(
SaturatingInst *SI) {
441 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
442 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
443 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(), LHS, RHS))
447 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(), SI);
453 SI->replaceAllUsesWith(BO);
454 DeadInsts.emplace_back(SI);
459bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
477 Type *IVTy =
IV->getType();
478 const SCEV *IVSCEV = SE->getSCEV(
IV);
479 const SCEV *TISCEV = SE->getSCEV(TI);
483 bool DoesSExtCollapse =
false;
484 bool DoesZExtCollapse =
false;
485 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
486 DoesSExtCollapse =
true;
487 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
488 DoesZExtCollapse =
true;
492 if (!DoesSExtCollapse && !DoesZExtCollapse)
498 for (
auto *U : TI->
users()) {
500 if (isa<Instruction>(U) &&
501 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
503 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
504 if (!ICI)
return false;
510 if (ICI->
isSigned() && !DoesSExtCollapse)
518 auto CanUseZExt = [&](
ICmpInst *ICI) {
523 if (!DoesZExtCollapse)
534 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
537 for (
auto *ICI : ICmpUsers) {
538 bool IsSwapped =
L->isLoopInvariant(ICI->
getOperand(0));
548 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
549 if (CanUseZExt(ICI)) {
550 assert(DoesZExtCollapse &&
"Unprofitable zext?");
554 assert(DoesSExtCollapse &&
"Unprofitable sext?");
559 L->makeLoopInvariant(Ext, Changed);
563 DeadInsts.emplace_back(ICI);
568 DeadInsts.emplace_back(TI);
575bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
577 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
578 eliminateIVComparison(ICmp, IVOperand);
582 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
583 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
584 simplifyIVRemainder(
Bin, IVOperand, IsSRem);
588 if (
Bin->getOpcode() == Instruction::SDiv)
589 return eliminateSDiv(
Bin);
592 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
593 if (eliminateOverflowIntrinsic(WO))
596 if (
auto *SI = dyn_cast<SaturatingInst>(UseInst))
597 if (eliminateSaturatingIntrinsic(SI))
600 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
601 if (eliminateTrunc(TI))
604 if (eliminateIdentitySCEV(UseInst, IVOperand))
611 if (
auto *BB = L->getLoopPreheader())
612 return BB->getTerminator();
618bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
619 if (!SE->isSCEVable(
I->getType()))
623 const SCEV *S = SE->getSCEV(
I);
625 if (!SE->isLoopInvariant(S, L))
634 if (!
Rewriter.isSafeToExpandAt(S, IP)) {
636 <<
" with non-speculable loop invariant: " << *S <<
'\n');
640 auto *Invariant =
Rewriter.expandCodeFor(S,
I->getType(), IP);
642 I->replaceAllUsesWith(Invariant);
644 <<
" with loop invariant: " << *S <<
'\n');
647 DeadInsts.emplace_back(
I);
652bool SimplifyIndvar::replaceFloatIVWithIntegerIV(
Instruction *UseInst) {
653 if (UseInst->
getOpcode() != CastInst::SIToFP &&
654 UseInst->
getOpcode() != CastInst::UIToFP)
659 const SCEV *
IV = SE->getSCEV(IVOperand);
661 if (UseInst->
getOpcode() == CastInst::SIToFP)
662 MaskBits = SE->getSignedRange(
IV).getMinSignedBits();
664 MaskBits = SE->getUnsignedRange(
IV).getActiveBits();
666 if (MaskBits <= DestNumSigBits) {
669 auto *CI = dyn_cast<CastInst>(U);
674 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
677 Value *Conv =
nullptr;
678 if (IVOperand->
getType() != CI->getType()) {
683 if (SE->getTypeSizeInBits(IVOperand->
getType()) >
684 SE->getTypeSizeInBits(CI->getType())) {
685 Conv =
Builder.CreateTrunc(IVOperand, CI->getType(),
Name +
".trunc");
686 }
else if (Opcode == CastInst::FPToUI ||
687 UseInst->
getOpcode() == CastInst::UIToFP) {
688 Conv =
Builder.CreateZExt(IVOperand, CI->getType(),
Name +
".zext");
690 Conv =
Builder.CreateSExt(IVOperand, CI->getType(),
Name +
".sext");
696 DeadInsts.push_back(CI);
698 <<
" with: " << *Conv <<
'\n');
709bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
711 if (!SE->isSCEVable(UseInst->
getType()) ||
713 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
732 if (isa<PHINode>(UseInst))
735 if (!DT || !DT->dominates(IVOperand, UseInst))
738 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
741 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
743 SE->forgetValue(UseInst);
747 DeadInsts.emplace_back(UseInst);
753 return (isa<OverflowingBinaryOperator>(BO) &&
754 strengthenOverflowingOperation(BO, IVOperand)) ||
755 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
760bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
762 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
763 cast<OverflowingBinaryOperator>(BO));
788 if (BO->
getOpcode() == Instruction::Shl) {
789 bool Changed =
false;
790 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
791 for (
auto *U : BO->
users()) {
814 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
816 for (
User *U : Def->users()) {
828 if (!L->contains(UI))
832 if (!Simplified.insert(UI).second)
835 SimpleIVUsers.push_back(std::make_pair(UI, Def));
873 if (!SE->isSCEVable(CurrIV->
getType()))
887 while (!SimpleIVUsers.
empty()) {
888 std::pair<Instruction*, Instruction*> UseOper =
897 DeadInsts.emplace_back(UseInst);
902 if (UseInst == CurrIV)
continue;
906 if (replaceIVUserWithLoopInvariant(UseInst))
910 for (
unsigned N = 0; IVOperand; ++
N) {
914 Value *NewOper = foldIVUser(UseInst, IVOperand);
917 IVOperand = dyn_cast<Instruction>(NewOper);
922 if (eliminateIVUser(UseInst, IVOperand)) {
923 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
928 if (strengthenBinaryOp(BO, IVOperand)) {
931 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
936 if (replaceFloatIVWithIntegerIV(UseInst)) {
938 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
942 CastInst *Cast = dyn_cast<CastInst>(UseInst);
948 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
965 SIV.simplifyUsers(CurrIV, V);
966 return SIV.hasChanged();
978 bool Changed =
false;
1009 bool UsePostIncrementRanges;
1012 unsigned NumElimExt = 0;
1013 unsigned NumWidened = 0;
1018 const SCEV *WideIncExpr =
nullptr;
1039 std::optional<ConstantRange> getPostIncRangeInfo(
Value *Def,
1041 DefUserPair
Key(Def, UseI);
1042 auto It = PostIncRangeInfos.
find(Key);
1043 return It == PostIncRangeInfos.
end()
1044 ? std::optional<ConstantRange>(std::nullopt)
1048 void calculatePostIncRanges(
PHINode *OrigPhi);
1052 DefUserPair
Key(Def, UseI);
1053 auto It = PostIncRangeInfos.
find(Key);
1054 if (It == PostIncRangeInfos.
end())
1057 It->second =
R.intersectWith(It->second);
1064 struct NarrowIVDefUse {
1072 bool NeverNegative =
false;
1076 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1077 NeverNegative(NeverNegative) {}
1082 bool HasGuards,
bool UsePostIncrementRanges =
true);
1086 unsigned getNumElimExt() {
return NumElimExt; };
1087 unsigned getNumWidened() {
return NumWidened; };
1090 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1094 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1096 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1100 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1102 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1104 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1106 const SCEV *getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1107 unsigned OpCode)
const;
1111 bool widenLoopCompare(NarrowIVDefUse DU);
1112 bool widenWithVariantUse(NarrowIVDefUse DU);
1134 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i != e; ++i) {
1135 if (
PHI->getIncomingValue(i) != Def)
1156 auto *DefI = dyn_cast<Instruction>(Def);
1160 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1165 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1167 return DTN->getBlock()->getTerminator();
1175 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1176 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1179 assert(L->getHeader() == OrigPhi->
getParent() &&
"Phi must be an IV");
1180 ExtendKindMap[OrigPhi] = WI.
IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1183Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1189 L &&
L->getLoopPreheader() &&
L->isLoopInvariant(NarrowOper);
1190 L =
L->getParentLoop())
1191 Builder.SetInsertPoint(
L->getLoopPreheader()->getTerminator());
1193 return IsSigned ?
Builder.CreateSExt(NarrowOper, WideType) :
1194 Builder.CreateZExt(NarrowOper, WideType);
1200Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1202 unsigned Opcode = DU.NarrowUse->
getOpcode();
1206 case Instruction::Add:
1207 case Instruction::Mul:
1208 case Instruction::UDiv:
1209 case Instruction::Sub:
1210 return cloneArithmeticIVUser(DU, WideAR);
1212 case Instruction::And:
1213 case Instruction::Or:
1214 case Instruction::Xor:
1215 case Instruction::Shl:
1216 case Instruction::LShr:
1217 case Instruction::AShr:
1218 return cloneBitwiseIVUser(DU);
1222Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1227 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1233 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1236 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1237 IsSigned, NarrowUse);
1240 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1241 IsSigned, NarrowUse);
1243 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1245 NarrowBO->getName());
1248 WideBO->copyIRFlags(NarrowBO);
1252Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1258 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1260 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1271 auto GuessNonIVOperand = [&](
bool SignExt) {
1272 const SCEV *WideLHS;
1273 const SCEV *WideRHS;
1275 auto GetExtend = [
this, SignExt](
const SCEV *S,
Type *Ty) {
1282 WideLHS = SE->
getSCEV(WideDef);
1284 WideRHS = GetExtend(NarrowRHS, WideType);
1287 WideLHS = GetExtend(NarrowLHS, WideType);
1288 WideRHS = SE->
getSCEV(WideDef);
1292 const SCEV *WideUse =
1293 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1295 return WideUse == WideAR;
1298 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1299 if (!GuessNonIVOperand(SignExtend)) {
1300 SignExtend = !SignExtend;
1301 if (!GuessNonIVOperand(SignExtend))
1307 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1308 SignExtend, NarrowUse);
1311 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1312 SignExtend, NarrowUse);
1314 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1316 NarrowBO->getName());
1320 WideBO->copyIRFlags(NarrowBO);
1324WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1325 auto It = ExtendKindMap.
find(
I);
1326 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1330const SCEV *WidenIV::getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1331 unsigned OpCode)
const {
1333 case Instruction::Add:
1335 case Instruction::Sub:
1337 case Instruction::Mul:
1339 case Instruction::UDiv:
1351WidenIV::WidenedRecTy
1352WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1354 const unsigned OpCode = DU.NarrowUse->getOpcode();
1356 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1357 OpCode != Instruction::Mul)
1358 return {
nullptr, ExtendKind::Unknown};
1362 const unsigned ExtendOperIdx =
1363 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1364 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef &&
"bad DU");
1366 const SCEV *ExtendOperExpr =
nullptr;
1368 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1369 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1372 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1375 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1377 return {
nullptr, ExtendKind::Unknown};
1385 const SCEV *rhs = ExtendOperExpr;
1389 if (ExtendOperIdx == 0)
1392 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1394 if (!AddRec || AddRec->
getLoop() != L)
1395 return {
nullptr, ExtendKind::Unknown};
1397 return {AddRec, ExtKind};
1405WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1406 if (!DU.NarrowUse->getType()->isIntegerTy())
1407 return {
nullptr, ExtendKind::Unknown};
1409 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1414 return {
nullptr, ExtendKind::Unknown};
1417 const SCEV *WideExpr;
1419 if (DU.NeverNegative) {
1421 if (isa<SCEVAddRecExpr>(WideExpr))
1422 ExtKind = ExtendKind::Sign;
1425 ExtKind = ExtendKind::Zero;
1427 }
else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1429 ExtKind = ExtendKind::Sign;
1432 ExtKind = ExtendKind::Zero;
1434 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1435 if (!AddRec || AddRec->
getLoop() != L)
1436 return {
nullptr, ExtendKind::Unknown};
1437 return {AddRec, ExtKind};
1447 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1448 << *DU.NarrowUse <<
"\n");
1450 Value *Trunc =
Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1451 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1457bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1476 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1477 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1480 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1483 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1490 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1493 if (CastWidth < IVWidth) {
1494 Value *ExtOp = createExtendInst(Op, WideType,
Cmp->isSigned(), Cmp);
1495 DU.NarrowUse->replaceUsesOfWith(Op, ExtOp);
1520bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1526 const unsigned OpCode = NarrowUse->
getOpcode();
1528 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1529 OpCode != Instruction::Mul)
1539 cast<OverflowingBinaryOperator>(NarrowUse);
1540 ExtendKind ExtKind = getExtendKind(NarrowDef);
1541 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->
hasNoSignedWrap();
1543 auto AnotherOpExtKind = ExtKind;
1553 for (
Use &U : NarrowUse->
uses()) {
1555 if (
User == NarrowDef)
1557 if (!
L->contains(
User)) {
1558 auto *LCSSAPhi = cast<PHINode>(
User);
1561 if (LCSSAPhi->getNumOperands() != 1)
1566 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1572 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1574 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1579 if (ExtKind == ExtendKind::Sign)
1587 if (ExtUsers.
empty()) {
1597 if (!CanSignExtend && !CanZeroExtend) {
1600 if (OpCode != Instruction::Add)
1602 if (ExtKind != ExtendKind::Zero)
1617 AnotherOpExtKind = ExtendKind::Sign;
1623 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1626 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1632 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1633 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1637 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1638 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1640 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1642 NarrowBO->getName());
1645 WideBO->copyIRFlags(NarrowBO);
1646 ExtendKindMap[NarrowUse] = ExtKind;
1651 << *WideBO <<
"\n");
1662 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1663 assert(LoopExitingBlock &&
L->contains(LoopExitingBlock) &&
1664 "Not a LCSSA Phi?");
1665 WidePN->addIncoming(WideBO, LoopExitingBlock);
1666 Builder.SetInsertPoint(&*
User->getParent()->getFirstInsertionPt());
1677 if (ExtKind == ExtendKind::Zero)
1678 return Builder.CreateZExt(V, WideBO->getType());
1680 return Builder.CreateSExt(V, WideBO->getType());
1682 auto Pred =
User->getPredicate();
1698 "Should already know the kind of extension used to widen NarrowDef");
1701 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1702 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1706 if (UsePhi->getNumOperands() != 1)
1712 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1716 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1718 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1720 Value *Trunc =
Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1721 UsePhi->replaceAllUsesWith(Trunc);
1723 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1724 << *WidePhi <<
"\n");
1732 auto canWidenBySExt = [&]() {
1733 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1735 auto canWidenByZExt = [&]() {
1736 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1740 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1741 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1742 Value *NewDef = DU.WideDef;
1743 if (DU.NarrowUse->getType() != WideType) {
1746 if (CastWidth < IVWidth) {
1749 NewDef =
Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1756 <<
" not wide enough to subsume " << *DU.NarrowUse
1758 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1759 NewDef = DU.NarrowUse;
1762 if (NewDef != DU.NarrowUse) {
1764 <<
" replaced by " << *DU.WideDef <<
"\n");
1766 DU.NarrowUse->replaceAllUsesWith(NewDef);
1780 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1781 if (!WideAddRec.first)
1782 WideAddRec = getWideRecurrence(DU);
1784 assert((WideAddRec.first ==
nullptr) ==
1785 (WideAddRec.second == ExtendKind::Unknown));
1786 if (!WideAddRec.first) {
1789 if (widenLoopCompare(DU))
1797 if (widenWithVariantUse(DU))
1810 if (WideAddRec.first == WideIncExpr &&
1811 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1814 WideUse = cloneIVUser(DU, WideAddRec.first);
1823 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1824 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1825 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1835 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1843 bool NonNegativeDef =
1850 if (!Widened.
insert(NarrowUser).second)
1853 bool NonNegativeUse =
false;
1854 if (!NonNegativeDef) {
1856 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1857 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1860 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1861 NonNegativeDef || NonNegativeUse);
1880 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
1885 "Expect the new IV expression to preserve its type");
1888 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1889 if (!AddRec || AddRec->
getLoop() != L)
1898 "Loop header phi recurrence inputs do not dominate the loop");
1911 calculatePostIncRanges(OrigPhi);
1917 Instruction *InsertPt = &*
L->getHeader()->getFirstInsertionPt();
1918 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1921 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1926 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1938 WideIncExpr = SE->
getSCEV(WideInc);
1950 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
1953 pushNarrowIVUsers(OrigPhi, WidePhi);
1955 while (!NarrowIVUsers.empty()) {
1956 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1964 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1967 if (DU.NarrowDef->use_empty())
1979void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
1983 Value *NarrowDefLHS;
1984 const APInt *NarrowDefRHS;
1990 auto UpdateRangeFromCondition = [&] (
Value *Condition,
2002 auto CmpConstrainedLHSRange =
2004 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2007 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2010 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
2015 Ctx->getParent()->rend())) {
2017 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
2018 UpdateRangeFromCondition(
C,
true);
2022 UpdateRangeFromGuards(NarrowUser);
2030 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2031 L->contains(DTB->getBlock());
2032 DTB = DTB->getIDom()) {
2033 auto *BB = DTB->getBlock();
2034 auto *TI = BB->getTerminator();
2035 UpdateRangeFromGuards(TI);
2037 auto *BI = dyn_cast<BranchInst>(TI);
2038 if (!BI || !BI->isConditional())
2041 auto *TrueSuccessor = BI->getSuccessor(0);
2042 auto *FalseSuccessor = BI->getSuccessor(1);
2044 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2045 return BBE.isSingleEdge() &&
2050 UpdateRangeFromCondition(BI->getCondition(),
true);
2053 UpdateRangeFromCondition(BI->getCondition(),
false);
2058void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2064 while (!Worklist.
empty()) {
2067 for (
Use &U : NarrowDef->
uses()) {
2068 auto *NarrowUser = cast<Instruction>(
U.getUser());
2071 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2072 if (!NarrowUserLoop || !
L->contains(NarrowUserLoop))
2075 if (!Visited.
insert(NarrowUser).second)
2080 calculatePostIncRange(NarrowDef, NarrowUser);
2088 unsigned &NumElimExt,
unsigned &NumWidened,
2092 NumElimExt = Widener.getNumElimExt();
2093 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"))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void truncateIVUse(WidenIV::NarrowIVDefUse DU, DominatorTree *DT, LoopInfo *LI)
This IV user cannot be widened.
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.
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)
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=Twine(), Instruction *InsertBefore=nullptr)
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 Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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...
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.
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
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.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Value * getIncomingValueForBlock(const BasicBlock *BB) const
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.
This class represents an analyzed expression in the program.
Type * getType() const
Return the LLVM type of this SCEV expression.
This class represents a sign extension of integer types.
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="", Instruction *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.
This class represents zero extension of integer types.
#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)
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.
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 simplifyUsersOfIV(PHINode *CurrIV, ScalarEvolution *SE, DominatorTree *DT, LoopInfo *LI, const TargetTransformInfo *TTI, SmallVectorImpl< WeakTrackingVH > &Dead, SCEVExpander &Rewriter, IVVisitor *V=nullptr)
simplifyUsersOfIV - Simplify instructions that use this induction variable by using ScalarEvolution t...
bool replaceAllDbgUsesWith(Instruction &From, Value &To, Instruction &DomPoint, DominatorTree &DT)
Point debug users of From to To or salvage them.
constexpr unsigned BitWidth
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.