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 {
71 assert(LI &&
"IV simplification requires LoopInfo");
74 bool hasChanged()
const {
return Changed; }
84 bool replaceIVUserWithLoopInvariant(
Instruction *UseInst);
85 bool replaceFloatIVWithIntegerIV(
Instruction *UseInst);
112 for (
auto *
Insn : Instructions)
115 assert(CommonDom &&
"Common dominator not found?");
128 Value *IVSrc =
nullptr;
129 const unsigned OperIdx = 0;
130 const SCEV *FoldedExpr =
nullptr;
131 bool MustDropExactFlag =
false;
135 case Instruction::UDiv:
136 case Instruction::LShr:
139 if (IVOperand != UseInst->
getOperand(OperIdx) ||
145 if (!isa<BinaryOperator>(IVOperand)
146 || !isa<ConstantInt>(IVOperand->
getOperand(1)))
151 assert(SE->isSCEVable(IVSrc->
getType()) &&
"Expect SCEVable IV operand");
154 if (UseInst->
getOpcode() == Instruction::LShr) {
163 const auto *
LHS = SE->getSCEV(IVSrc);
164 const auto *
RHS = SE->getSCEV(
D);
165 FoldedExpr = SE->getUDivExpr(LHS, RHS);
168 if (UseInst->
isExact() && LHS != SE->getMulExpr(FoldedExpr, RHS))
169 MustDropExactFlag =
true;
172 if (!SE->isSCEVable(UseInst->
getType()))
176 if (SE->getSCEV(UseInst) != FoldedExpr)
179 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated IV operand: " << *IVOperand
180 <<
" -> " << *UseInst <<
'\n');
183 assert(SE->getSCEV(UseInst) == FoldedExpr &&
"bad SCEV with folded oper");
185 if (MustDropExactFlag)
191 DeadInsts.emplace_back(IVOperand);
195bool SimplifyIndvar::makeIVComparisonInvariant(
ICmpInst *ICmp,
197 auto *Preheader =
L->getLoopPreheader();
200 unsigned IVOperIdx = 0;
206 Pred = ICmpInst::getSwappedPredicate(Pred);
212 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
213 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
214 auto LIP = SE->getLoopInvariantPredicate(Pred, S,
X, L, ICmp);
218 const SCEV *InvariantLHS = LIP->LHS;
219 const SCEV *InvariantRHS = LIP->RHS;
222 auto *PHTerm = Preheader->getTerminator();
223 if (
Rewriter.isHighCostExpansion({InvariantLHS, InvariantRHS}, L,
225 !
Rewriter.isSafeToExpandAt(InvariantLHS, PHTerm) ||
226 !
Rewriter.isSafeToExpandAt(InvariantRHS, PHTerm))
232 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
241void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
243 unsigned IVOperIdx = 0;
250 Pred = ICmpInst::getSwappedPredicate(Pred);
256 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
257 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
262 for (
auto *U : ICmp->
users())
263 Users.push_back(cast<Instruction>(U));
265 if (
auto Ev = SE->evaluatePredicateAt(Pred, S,
X, CtxI)) {
266 SE->forgetValue(ICmp);
268 DeadInsts.emplace_back(ICmp);
269 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
270 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
272 }
else if (ICmpInst::isSigned(OriginalPred) &&
273 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(
X)) {
280 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
297 N = SE->getSCEVAtScope(
N, L);
298 D = SE->getSCEVAtScope(
D, L);
301 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
305 UDiv->setIsExact(SDiv->
isExact());
307 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
310 DeadInsts.push_back(SDiv);
323 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
326 DeadInsts.emplace_back(Rem);
330void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
332 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
335 DeadInsts.emplace_back(Rem);
339void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
346 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
349 DeadInsts.emplace_back(Rem);
362 bool UsedAsNumerator = IVOperand == NValue;
363 if (!UsedAsNumerator && !IsSigned)
366 const SCEV *
N = SE->getSCEV(NValue);
370 N = SE->getSCEVAtScope(
N, ICmpLoop);
372 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
375 if (!IsNumeratorNonNegative)
378 const SCEV *
D = SE->getSCEV(DValue);
379 D = SE->getSCEVAtScope(
D, ICmpLoop);
381 if (UsedAsNumerator) {
382 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
383 if (SE->isKnownPredicate(LT,
N,
D)) {
384 replaceRemWithNumerator(Rem);
389 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
390 if (SE->isKnownPredicate(LT, NLessOne,
D)) {
391 replaceRemWithNumeratorOrZero(Rem);
398 if (!IsSigned || !SE->isKnownNonNegative(
D))
401 replaceSRemWithURem(Rem);
423 for (
auto *U : WO->
users()) {
424 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
425 if (EVI->getIndices()[0] == 1)
428 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
429 EVI->replaceAllUsesWith(NewResult);
435 for (
auto *EVI : ToDelete)
436 EVI->eraseFromParent();
445bool SimplifyIndvar::eliminateSaturatingIntrinsic(
SaturatingInst *SI) {
446 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
447 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
448 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(), LHS, RHS))
452 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(),
SI->getIterator());
458 SI->replaceAllUsesWith(BO);
459 DeadInsts.emplace_back(SI);
464bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
482 Type *IVTy =
IV->getType();
483 const SCEV *IVSCEV = SE->getSCEV(
IV);
484 const SCEV *TISCEV = SE->getSCEV(TI);
488 bool DoesSExtCollapse =
false;
489 bool DoesZExtCollapse =
false;
490 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
491 DoesSExtCollapse =
true;
492 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
493 DoesZExtCollapse =
true;
497 if (!DoesSExtCollapse && !DoesZExtCollapse)
503 for (
auto *U : TI->
users()) {
505 if (isa<Instruction>(U) &&
506 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
508 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
509 if (!ICI)
return false;
515 if (ICI->
isSigned() && !DoesSExtCollapse)
523 auto CanUseZExt = [&](
ICmpInst *ICI) {
528 if (!DoesZExtCollapse)
539 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
542 for (
auto *ICI : ICmpUsers) {
543 bool IsSwapped =
L->isLoopInvariant(ICI->
getOperand(0));
554 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
555 if (CanUseZExt(ICI)) {
556 assert(DoesZExtCollapse &&
"Unprofitable zext?");
557 Ext = Builder.CreateZExt(Op1, IVTy,
"zext");
560 assert(DoesSExtCollapse &&
"Unprofitable sext?");
561 Ext = Builder.CreateSExt(Op1, IVTy,
"sext");
565 L->makeLoopInvariant(Ext, Changed);
567 auto *NewCmp = Builder.CreateICmp(Pred,
IV, Ext);
569 DeadInsts.emplace_back(ICI);
574 DeadInsts.emplace_back(TI);
581bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
583 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
584 eliminateIVComparison(ICmp, IVOperand);
588 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
589 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
590 simplifyIVRemainder(
Bin, IVOperand, IsSRem);
594 if (
Bin->getOpcode() == Instruction::SDiv)
595 return eliminateSDiv(
Bin);
598 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
599 if (eliminateOverflowIntrinsic(WO))
602 if (
auto *SI = dyn_cast<SaturatingInst>(UseInst))
603 if (eliminateSaturatingIntrinsic(SI))
606 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
607 if (eliminateTrunc(TI))
610 if (eliminateIdentitySCEV(UseInst, IVOperand))
617 if (
auto *BB = L->getLoopPreheader())
618 return BB->getTerminator();
624bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
625 if (!SE->isSCEVable(
I->getType()))
629 const SCEV *S = SE->getSCEV(
I);
631 if (!SE->isLoopInvariant(S, L))
640 if (!
Rewriter.isSafeToExpandAt(S, IP)) {
642 <<
" with non-speculable loop invariant: " << *S <<
'\n');
646 auto *Invariant =
Rewriter.expandCodeFor(S,
I->getType(), IP);
647 bool NeedToEmitLCSSAPhis =
false;
648 if (!LI->replacementPreservesLCSSAForm(
I, Invariant))
649 NeedToEmitLCSSAPhis =
true;
651 I->replaceAllUsesWith(Invariant);
653 <<
" with loop invariant: " << *S <<
'\n');
655 if (NeedToEmitLCSSAPhis) {
657 NeedsLCSSAPhis.
push_back(cast<Instruction>(Invariant));
660 <<
" inserting LCSSA Phis" <<
'\n');
664 DeadInsts.emplace_back(
I);
669bool SimplifyIndvar::replaceFloatIVWithIntegerIV(
Instruction *UseInst) {
670 if (UseInst->
getOpcode() != CastInst::SIToFP &&
671 UseInst->
getOpcode() != CastInst::UIToFP)
676 const SCEV *
IV = SE->getSCEV(IVOperand);
678 if (UseInst->
getOpcode() == CastInst::SIToFP)
679 MaskBits = (int)SE->getSignedRange(
IV).getMinSignedBits();
681 MaskBits = (int)SE->getUnsignedRange(
IV).getActiveBits();
683 if (MaskBits <= DestNumSigBits) {
686 auto *CI = dyn_cast<CastInst>(U);
691 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
694 Value *Conv =
nullptr;
695 if (IVOperand->
getType() != CI->getType()) {
700 if (SE->getTypeSizeInBits(IVOperand->
getType()) >
701 SE->getTypeSizeInBits(CI->getType())) {
702 Conv = Builder.CreateTrunc(IVOperand, CI->getType(),
Name +
".trunc");
703 }
else if (Opcode == CastInst::FPToUI ||
704 UseInst->
getOpcode() == CastInst::UIToFP) {
705 Conv = Builder.CreateZExt(IVOperand, CI->getType(),
Name +
".zext");
707 Conv = Builder.CreateSExt(IVOperand, CI->getType(),
Name +
".sext");
713 DeadInsts.push_back(CI);
715 <<
" with: " << *Conv <<
'\n');
726bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
728 if (!SE->isSCEVable(UseInst->
getType()) ||
732 const SCEV *UseSCEV = SE->getSCEV(UseInst);
733 if (UseSCEV != SE->getSCEV(IVOperand))
752 if (isa<PHINode>(UseInst))
755 if (!DT || !DT->dominates(IVOperand, UseInst))
758 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
764 if (!SE->canReuseInstruction(UseSCEV, IVOperand, DropPoisonGeneratingInsts))
768 I->dropPoisonGeneratingFlagsAndMetadata();
771 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
773 SE->forgetValue(UseInst);
777 DeadInsts.emplace_back(UseInst);
783 return (isa<OverflowingBinaryOperator>(BO) &&
784 strengthenOverflowingOperation(BO, IVOperand)) ||
785 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
790bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
792 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
793 cast<OverflowingBinaryOperator>(BO));
816 if (BO->
getOpcode() == Instruction::Shl) {
817 bool Changed =
false;
818 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
819 for (
auto *U : BO->
users()) {
842 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
844 for (
User *U : Def->users()) {
856 if (!L->contains(UI))
860 if (!Simplified.insert(UI).second)
863 SimpleIVUsers.push_back(std::make_pair(UI, Def));
901 if (!SE->isSCEVable(CurrIV->
getType()))
915 while (!SimpleIVUsers.
empty()) {
916 std::pair<Instruction*, Instruction*> UseOper =
925 DeadInsts.emplace_back(UseInst);
930 if (UseInst == CurrIV)
continue;
934 if (replaceIVUserWithLoopInvariant(UseInst))
939 if ((isa<PtrToIntInst>(UseInst)) || (isa<TruncInst>(UseInst)))
940 for (
Use &U : UseInst->
uses()) {
942 if (replaceIVUserWithLoopInvariant(
User))
947 for (
unsigned N = 0; IVOperand; ++
N) {
951 Value *NewOper = foldIVUser(UseInst, IVOperand);
954 IVOperand = dyn_cast<Instruction>(NewOper);
959 if (eliminateIVUser(UseInst, IVOperand)) {
960 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
965 if (strengthenBinaryOp(BO, IVOperand)) {
968 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
973 if (replaceFloatIVWithIntegerIV(UseInst)) {
975 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
979 CastInst *Cast = dyn_cast<CastInst>(UseInst);
985 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
1002 SIV.simplifyUsers(CurrIV, V);
1003 return SIV.hasChanged();
1015 bool Changed =
false;
1046 bool UsePostIncrementRanges;
1049 unsigned NumElimExt = 0;
1050 unsigned NumWidened = 0;
1055 const SCEV *WideIncExpr =
nullptr;
1076 std::optional<ConstantRange> getPostIncRangeInfo(
Value *Def,
1078 DefUserPair
Key(Def, UseI);
1079 auto It = PostIncRangeInfos.
find(Key);
1080 return It == PostIncRangeInfos.
end()
1081 ? std::optional<ConstantRange>(std::nullopt)
1085 void calculatePostIncRanges(
PHINode *OrigPhi);
1089 DefUserPair
Key(Def, UseI);
1090 auto It = PostIncRangeInfos.
find(Key);
1091 if (It == PostIncRangeInfos.
end())
1094 It->second =
R.intersectWith(It->second);
1101 struct NarrowIVDefUse {
1109 bool NeverNegative =
false;
1113 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1114 NeverNegative(NeverNegative) {}
1119 bool HasGuards,
bool UsePostIncrementRanges =
true);
1123 unsigned getNumElimExt() {
return NumElimExt; };
1124 unsigned getNumWidened() {
return NumWidened; };
1127 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1131 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1133 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1137 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1139 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1141 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1143 const SCEV *getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1144 unsigned OpCode)
const;
1149 bool widenLoopCompare(NarrowIVDefUse DU);
1150 bool widenWithVariantUse(NarrowIVDefUse DU);
1172 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i != e; ++i) {
1173 if (
PHI->getIncomingValue(i) != Def)
1194 auto *DefI = dyn_cast<Instruction>(Def);
1198 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1203 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1205 return DTN->getBlock()->getTerminator();
1213 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1214 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1217 assert(L->getHeader() == OrigPhi->
getParent() &&
"Phi must be an IV");
1218 ExtendKindMap[OrigPhi] = WI.
IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1221Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1227 L &&
L->getLoopPreheader() &&
L->isLoopInvariant(NarrowOper);
1228 L =
L->getParentLoop())
1229 Builder.SetInsertPoint(
L->getLoopPreheader()->getTerminator());
1231 return IsSigned ? Builder.CreateSExt(NarrowOper, WideType) :
1232 Builder.CreateZExt(NarrowOper, WideType);
1238Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1240 unsigned Opcode = DU.NarrowUse->
getOpcode();
1244 case Instruction::Add:
1245 case Instruction::Mul:
1246 case Instruction::UDiv:
1247 case Instruction::Sub:
1248 return cloneArithmeticIVUser(DU, WideAR);
1250 case Instruction::And:
1251 case Instruction::Or:
1252 case Instruction::Xor:
1253 case Instruction::Shl:
1254 case Instruction::LShr:
1255 case Instruction::AShr:
1256 return cloneBitwiseIVUser(DU);
1260Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1265 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1271 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1274 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1275 IsSigned, NarrowUse);
1278 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1279 IsSigned, NarrowUse);
1281 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1283 NarrowBO->getName());
1285 Builder.Insert(WideBO);
1286 WideBO->copyIRFlags(NarrowBO);
1290Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1296 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1298 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1309 auto GuessNonIVOperand = [&](
bool SignExt) {
1310 const SCEV *WideLHS;
1311 const SCEV *WideRHS;
1313 auto GetExtend = [
this, SignExt](
const SCEV *S,
Type *Ty) {
1320 WideLHS = SE->
getSCEV(WideDef);
1322 WideRHS = GetExtend(NarrowRHS, WideType);
1325 WideLHS = GetExtend(NarrowLHS, WideType);
1326 WideRHS = SE->
getSCEV(WideDef);
1330 const SCEV *WideUse =
1331 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1333 return WideUse == WideAR;
1336 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1337 if (!GuessNonIVOperand(SignExtend)) {
1338 SignExtend = !SignExtend;
1339 if (!GuessNonIVOperand(SignExtend))
1345 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1346 SignExtend, NarrowUse);
1349 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1350 SignExtend, NarrowUse);
1352 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1354 NarrowBO->getName());
1357 Builder.Insert(WideBO);
1358 WideBO->copyIRFlags(NarrowBO);
1362WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1363 auto It = ExtendKindMap.
find(
I);
1364 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1368const SCEV *WidenIV::getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1369 unsigned OpCode)
const {
1371 case Instruction::Add:
1373 case Instruction::Sub:
1375 case Instruction::Mul:
1377 case Instruction::UDiv:
1398 if (
auto *OBO = dyn_cast<OverflowingBinaryOperator>(
Op)) {
1399 IsNSW = OBO->hasNoSignedWrap();
1400 IsNUW = OBO->hasNoUnsignedWrap();
1405 bool IsNSW =
false,
bool IsNUW =
false)
1406 : Opcode(Opcode),
Operands({
LHS,
RHS}), IsNSW(IsNSW), IsNUW(IsNUW) {}
1412 switch (
Op->getOpcode()) {
1413 case Instruction::Add:
1414 case Instruction::Sub:
1415 case Instruction::Mul:
1416 return BinaryOp(
Op);
1417 case Instruction::Or: {
1419 if (cast<PossiblyDisjointInst>(
Op)->isDisjoint())
1420 return BinaryOp(Instruction::Add,
Op->getOperand(0),
Op->getOperand(1),
1424 case Instruction::Shl: {
1425 if (
ConstantInt *SA = dyn_cast<ConstantInt>(
Op->getOperand(1))) {
1426 unsigned BitWidth = cast<IntegerType>(SA->getType())->getBitWidth();
1432 if (SA->getValue().ult(
BitWidth)) {
1437 bool IsNUW =
Op->hasNoUnsignedWrap();
1438 bool IsNSW =
Op->hasNoSignedWrap() &&
1439 (IsNUW || SA->getValue().ult(
BitWidth - 1));
1442 ConstantInt::get(
Op->getContext(),
1444 return BinaryOp(Instruction::Mul,
Op->getOperand(0),
X, IsNSW, IsNUW);
1452 return std::nullopt;
1460WidenIV::WidenedRecTy
1461WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1464 return {
nullptr, ExtendKind::Unknown};
1466 assert((
Op->Opcode == Instruction::Add ||
Op->Opcode == Instruction::Sub ||
1467 Op->Opcode == Instruction::Mul) &&
1468 "Unexpected opcode");
1472 const unsigned ExtendOperIdx =
Op->Operands[0] == DU.NarrowDef ? 1 : 0;
1473 assert(
Op->Operands[1 - ExtendOperIdx] == DU.NarrowDef &&
"bad DU");
1475 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1476 if (!(ExtKind == ExtendKind::Sign &&
Op->IsNSW) &&
1477 !(ExtKind == ExtendKind::Zero &&
Op->IsNUW)) {
1478 ExtKind = ExtendKind::Unknown;
1484 if (DU.NeverNegative) {
1486 ExtKind = ExtendKind::Sign;
1487 }
else if (
Op->IsNUW) {
1488 ExtKind = ExtendKind::Zero;
1493 const SCEV *ExtendOperExpr = SE->
getSCEV(
Op->Operands[ExtendOperIdx]);
1494 if (ExtKind == ExtendKind::Sign)
1496 else if (ExtKind == ExtendKind::Zero)
1499 return {
nullptr, ExtendKind::Unknown};
1507 const SCEV *rhs = ExtendOperExpr;
1511 if (ExtendOperIdx == 0)
1514 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs,
Op->Opcode));
1516 if (!AddRec || AddRec->
getLoop() != L)
1517 return {
nullptr, ExtendKind::Unknown};
1519 return {AddRec, ExtKind};
1527WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1528 if (!DU.NarrowUse->getType()->isIntegerTy())
1529 return {
nullptr, ExtendKind::Unknown};
1531 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1536 return {
nullptr, ExtendKind::Unknown};
1539 const SCEV *WideExpr;
1541 if (DU.NeverNegative) {
1543 if (isa<SCEVAddRecExpr>(WideExpr))
1544 ExtKind = ExtendKind::Sign;
1547 ExtKind = ExtendKind::Zero;
1549 }
else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1551 ExtKind = ExtendKind::Sign;
1554 ExtKind = ExtendKind::Zero;
1556 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1557 if (!AddRec || AddRec->
getLoop() != L)
1558 return {
nullptr, ExtendKind::Unknown};
1559 return {AddRec, ExtKind};
1569 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1570 << *DU.NarrowUse <<
"\n");
1573 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1579bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1598 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1599 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1602 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1605 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1608 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1611 if (CastWidth < IVWidth) {
1612 Value *ExtOp = createExtendInst(
Op, WideType,
Cmp->isSigned(), Cmp);
1613 DU.NarrowUse->replaceUsesOfWith(
Op, ExtOp);
1638bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1644 const unsigned OpCode = NarrowUse->
getOpcode();
1646 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1647 OpCode != Instruction::Mul)
1657 cast<OverflowingBinaryOperator>(NarrowUse);
1658 ExtendKind ExtKind = getExtendKind(NarrowDef);
1659 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->
hasNoSignedWrap();
1661 auto AnotherOpExtKind = ExtKind;
1671 for (
Use &U : NarrowUse->
uses()) {
1673 if (
User == NarrowDef)
1675 if (!
L->contains(
User)) {
1676 auto *LCSSAPhi = cast<PHINode>(
User);
1679 if (LCSSAPhi->getNumOperands() != 1)
1684 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1690 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1692 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1697 if (ExtKind == ExtendKind::Sign)
1705 if (ExtUsers.
empty()) {
1715 if (!CanSignExtend && !CanZeroExtend) {
1718 if (OpCode != Instruction::Add)
1720 if (ExtKind != ExtendKind::Zero)
1735 AnotherOpExtKind = ExtendKind::Sign;
1741 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1744 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1750 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1751 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1755 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1756 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1758 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1760 NarrowBO->getName());
1762 Builder.Insert(WideBO);
1763 WideBO->copyIRFlags(NarrowBO);
1764 ExtendKindMap[NarrowUse] = ExtKind;
1769 << *WideBO <<
"\n");
1777 Builder.SetInsertPoint(
User);
1779 Builder.CreatePHI(WideBO->getType(), 1,
User->
getName() +
".wide");
1780 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1781 assert(LoopExitingBlock &&
L->contains(LoopExitingBlock) &&
1782 "Not a LCSSA Phi?");
1783 WidePN->addIncoming(WideBO, LoopExitingBlock);
1784 Builder.SetInsertPoint(
User->getParent(),
1785 User->getParent()->getFirstInsertionPt());
1786 auto *TruncPN = Builder.CreateTrunc(WidePN,
User->
getType());
1792 Builder.SetInsertPoint(
User);
1796 if (ExtKind == ExtendKind::Zero)
1797 return Builder.CreateZExt(V, WideBO->getType());
1799 return Builder.CreateSExt(V, WideBO->getType());
1801 auto Pred =
User->getPredicate();
1805 Builder.CreateICmp(Pred, LHS, RHS,
User->
getName() +
".wide");
1815Instruction *WidenIV::widenIVUse(WidenIV::NarrowIVDefUse DU,
1819 "Should already know the kind of extension used to widen NarrowDef");
1822 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1823 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1827 if (UsePhi->getNumOperands() != 1)
1833 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1837 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1838 UsePhi->getIterator());
1839 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1842 Value *Trunc = Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1845 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1846 << *WidePhi <<
"\n");
1854 auto canWidenBySExt = [&]() {
1855 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1857 auto canWidenByZExt = [&]() {
1858 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1863 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1864 Value *NewDef = DU.WideDef;
1865 if (DU.NarrowUse->getType() != WideType) {
1868 if (CastWidth < IVWidth) {
1871 NewDef = Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1878 <<
" not wide enough to subsume " << *DU.NarrowUse
1880 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1881 NewDef = DU.NarrowUse;
1884 if (NewDef != DU.NarrowUse) {
1886 <<
" replaced by " << *DU.WideDef <<
"\n");
1888 DU.NarrowUse->replaceAllUsesWith(NewDef);
1903 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1904 if (!WideAddRec.first)
1905 WideAddRec = getWideRecurrence(DU);
1906 assert((WideAddRec.first ==
nullptr) ==
1907 (WideAddRec.second == ExtendKind::Unknown));
1908 if (!WideAddRec.first)
1915 bool NeedToRecomputeFlags =
1917 DU.NarrowUse, WideInc) ||
1921 if (WideAddRec.first == WideIncExpr &&
1922 Rewriter.hoistIVInc(WideInc, DU.NarrowUse, NeedToRecomputeFlags))
1925 WideUse = cloneIVUser(DU, WideAddRec.first);
1934 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1935 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1936 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1946 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1951 if (
auto *
I = tryAddRecExpansion())
1956 if (widenLoopCompare(DU))
1964 if (widenWithVariantUse(DU))
1977 bool NonNegativeDef =
1984 if (!Widened.
insert(NarrowUser).second)
1987 bool NonNegativeUse =
false;
1988 if (!NonNegativeDef) {
1990 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1991 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1994 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1995 NonNegativeDef || NonNegativeUse);
2014 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
2019 "Expect the new IV expression to preserve its type");
2022 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
2023 if (!AddRec || AddRec->
getLoop() != L)
2032 "Loop header phi recurrence inputs do not dominate the loop");
2045 calculatePostIncRanges(OrigPhi);
2051 Instruction *InsertPt = &*
L->getHeader()->getFirstInsertionPt();
2052 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
2055 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
2060 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
2073 WideIncExpr = SE->
getSCEV(WideInc);
2090 OrigInc, WideInc) &&
2091 isa<OverflowingBinaryOperator>(OrigInc) &&
2092 isa<OverflowingBinaryOperator>(WideInc)) {
2094 OrigInc->hasNoUnsignedWrap());
2096 OrigInc->hasNoSignedWrap());
2105 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
2108 pushNarrowIVUsers(OrigPhi, WidePhi);
2110 while (!NarrowIVUsers.empty()) {
2111 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
2115 Instruction *WideUse = widenIVUse(DU, Rewriter, OrigPhi, WidePhi);
2119 pushNarrowIVUsers(DU.NarrowUse, WideUse);
2122 if (DU.NarrowDef->use_empty())
2134void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
2136 Value *NarrowDefLHS;
2137 const APInt *NarrowDefRHS;
2143 auto UpdateRangeFromCondition = [&] (
Value *Condition,
2155 auto CmpConstrainedLHSRange =
2157 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2160 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2163 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
2168 Ctx->getParent()->rend())) {
2170 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
2171 UpdateRangeFromCondition(
C,
true);
2175 UpdateRangeFromGuards(NarrowUser);
2183 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2184 L->contains(DTB->getBlock());
2185 DTB = DTB->getIDom()) {
2186 auto *BB = DTB->getBlock();
2187 auto *TI = BB->getTerminator();
2188 UpdateRangeFromGuards(TI);
2190 auto *BI = dyn_cast<BranchInst>(TI);
2191 if (!BI || !BI->isConditional())
2194 auto *TrueSuccessor = BI->getSuccessor(0);
2195 auto *FalseSuccessor = BI->getSuccessor(1);
2197 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2198 return BBE.isSingleEdge() &&
2203 UpdateRangeFromCondition(BI->getCondition(),
true);
2206 UpdateRangeFromCondition(BI->getCondition(),
false);
2211void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2217 while (!Worklist.
empty()) {
2220 for (
Use &U : NarrowDef->
uses()) {
2221 auto *NarrowUser = cast<Instruction>(
U.getUser());
2224 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2225 if (!NarrowUserLoop || !
L->contains(NarrowUserLoop))
2228 if (!Visited.
insert(NarrowUser).second)
2233 calculatePostIncRange(NarrowDef, NarrowUser);
2241 unsigned &NumElimExt,
unsigned &NumWidened,
2245 NumElimExt = Widener.getNumElimExt();
2246 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 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.
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.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Interface for visiting interesting IV users that are recognized but not simplified by this utility.
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 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
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.