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,
222 !
Rewriter.isSafeToExpandAt(InvariantLHS, PHTerm) ||
223 !
Rewriter.isSafeToExpandAt(InvariantRHS, PHTerm))
229 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified comparison: " << *ICmp <<
'\n');
238void SimplifyIndvar::eliminateIVComparison(
ICmpInst *ICmp,
240 unsigned IVOperIdx = 0;
247 Pred = ICmpInst::getSwappedPredicate(Pred);
253 const SCEV *S = SE->getSCEVAtScope(ICmp->
getOperand(IVOperIdx), ICmpLoop);
254 const SCEV *
X = SE->getSCEVAtScope(ICmp->
getOperand(1 - IVOperIdx), ICmpLoop);
259 for (
auto *U : ICmp->
users())
260 Users.push_back(cast<Instruction>(U));
262 if (
auto Ev = SE->evaluatePredicateAt(Pred, S,
X, CtxI)) {
263 SE->forgetValue(ICmp);
265 DeadInsts.emplace_back(ICmp);
266 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated comparison: " << *ICmp <<
'\n');
267 }
else if (makeIVComparisonInvariant(ICmp, IVOperand)) {
269 }
else if (ICmpInst::isSigned(OriginalPred) &&
270 SE->isKnownNonNegative(S) && SE->isKnownNonNegative(
X)) {
277 LLVM_DEBUG(
dbgs() <<
"INDVARS: Turn to unsigned comparison: " << *ICmp
294 N = SE->getSCEVAtScope(
N, L);
295 D = SE->getSCEVAtScope(
D, L);
298 if (SE->isKnownNonNegative(
N) && SE->isKnownNonNegative(
D)) {
301 SDiv->
getName() +
".udiv", SDiv);
302 UDiv->setIsExact(SDiv->
isExact());
304 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified sdiv: " << *SDiv <<
'\n');
307 DeadInsts.push_back(SDiv);
318 Rem->
getName() +
".urem", Rem);
320 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified srem: " << *Rem <<
'\n');
323 DeadInsts.emplace_back(Rem);
327void SimplifyIndvar::replaceRemWithNumerator(
BinaryOperator *Rem) {
329 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
332 DeadInsts.emplace_back(Rem);
336void SimplifyIndvar::replaceRemWithNumeratorOrZero(
BinaryOperator *Rem) {
343 LLVM_DEBUG(
dbgs() <<
"INDVARS: Simplified rem: " << *Rem <<
'\n');
346 DeadInsts.emplace_back(Rem);
359 bool UsedAsNumerator = IVOperand == NValue;
360 if (!UsedAsNumerator && !IsSigned)
363 const SCEV *
N = SE->getSCEV(NValue);
367 N = SE->getSCEVAtScope(
N, ICmpLoop);
369 bool IsNumeratorNonNegative = !IsSigned || SE->isKnownNonNegative(
N);
372 if (!IsNumeratorNonNegative)
375 const SCEV *
D = SE->getSCEV(DValue);
376 D = SE->getSCEVAtScope(
D, ICmpLoop);
378 if (UsedAsNumerator) {
379 auto LT = IsSigned ? ICmpInst::ICMP_SLT : ICmpInst::ICMP_ULT;
380 if (SE->isKnownPredicate(LT,
N,
D)) {
381 replaceRemWithNumerator(Rem);
386 const auto *NLessOne = SE->getMinusSCEV(
N, SE->getOne(
T));
387 if (SE->isKnownPredicate(LT, NLessOne,
D)) {
388 replaceRemWithNumeratorOrZero(Rem);
395 if (!IsSigned || !SE->isKnownNonNegative(
D))
398 replaceSRemWithURem(Rem);
420 for (
auto *U : WO->
users()) {
421 if (
auto *EVI = dyn_cast<ExtractValueInst>(U)) {
422 if (EVI->getIndices()[0] == 1)
425 assert(EVI->getIndices()[0] == 0 &&
"Only two possibilities!");
426 EVI->replaceAllUsesWith(NewResult);
432 for (
auto *EVI : ToDelete)
433 EVI->eraseFromParent();
442bool SimplifyIndvar::eliminateSaturatingIntrinsic(
SaturatingInst *SI) {
443 const SCEV *
LHS = SE->getSCEV(
SI->getLHS());
444 const SCEV *
RHS = SE->getSCEV(
SI->getRHS());
445 if (!SE->willNotOverflow(
SI->getBinaryOp(),
SI->isSigned(), LHS, RHS))
449 SI->getBinaryOp(),
SI->getLHS(),
SI->getRHS(),
SI->getName(), SI);
455 SI->replaceAllUsesWith(BO);
456 DeadInsts.emplace_back(SI);
461bool SimplifyIndvar::eliminateTrunc(
TruncInst *TI) {
479 Type *IVTy =
IV->getType();
480 const SCEV *IVSCEV = SE->getSCEV(
IV);
481 const SCEV *TISCEV = SE->getSCEV(TI);
485 bool DoesSExtCollapse =
false;
486 bool DoesZExtCollapse =
false;
487 if (IVSCEV == SE->getSignExtendExpr(TISCEV, IVTy))
488 DoesSExtCollapse =
true;
489 if (IVSCEV == SE->getZeroExtendExpr(TISCEV, IVTy))
490 DoesZExtCollapse =
true;
494 if (!DoesSExtCollapse && !DoesZExtCollapse)
500 for (
auto *U : TI->
users()) {
502 if (isa<Instruction>(U) &&
503 !DT->isReachableFromEntry(cast<Instruction>(U)->getParent()))
505 ICmpInst *ICI = dyn_cast<ICmpInst>(U);
506 if (!ICI)
return false;
512 if (ICI->
isSigned() && !DoesSExtCollapse)
520 auto CanUseZExt = [&](
ICmpInst *ICI) {
525 if (!DoesZExtCollapse)
536 return SE->isKnownNonNegative(SCEVOP1) && SE->isKnownNonNegative(SCEVOP2);
539 for (
auto *ICI : ICmpUsers) {
540 bool IsSwapped =
L->isLoopInvariant(ICI->
getOperand(0));
550 if (IsSwapped) Pred = ICmpInst::getSwappedPredicate(Pred);
551 if (CanUseZExt(ICI)) {
552 assert(DoesZExtCollapse &&
"Unprofitable zext?");
556 assert(DoesSExtCollapse &&
"Unprofitable sext?");
561 L->makeLoopInvariant(Ext, Changed);
565 DeadInsts.emplace_back(ICI);
570 DeadInsts.emplace_back(TI);
577bool SimplifyIndvar::eliminateIVUser(
Instruction *UseInst,
579 if (
ICmpInst *ICmp = dyn_cast<ICmpInst>(UseInst)) {
580 eliminateIVComparison(ICmp, IVOperand);
584 bool IsSRem =
Bin->getOpcode() == Instruction::SRem;
585 if (IsSRem ||
Bin->getOpcode() == Instruction::URem) {
586 simplifyIVRemainder(
Bin, IVOperand, IsSRem);
590 if (
Bin->getOpcode() == Instruction::SDiv)
591 return eliminateSDiv(
Bin);
594 if (
auto *WO = dyn_cast<WithOverflowInst>(UseInst))
595 if (eliminateOverflowIntrinsic(WO))
598 if (
auto *SI = dyn_cast<SaturatingInst>(UseInst))
599 if (eliminateSaturatingIntrinsic(SI))
602 if (
auto *TI = dyn_cast<TruncInst>(UseInst))
603 if (eliminateTrunc(TI))
606 if (eliminateIdentitySCEV(UseInst, IVOperand))
613 if (
auto *BB = L->getLoopPreheader())
614 return BB->getTerminator();
620bool SimplifyIndvar::replaceIVUserWithLoopInvariant(
Instruction *
I) {
621 if (!SE->isSCEVable(
I->getType()))
625 const SCEV *S = SE->getSCEV(
I);
627 if (!SE->isLoopInvariant(S, L))
636 if (!
Rewriter.isSafeToExpandAt(S, IP)) {
638 <<
" with non-speculable loop invariant: " << *S <<
'\n');
642 auto *Invariant =
Rewriter.expandCodeFor(S,
I->getType(), IP);
644 I->replaceAllUsesWith(Invariant);
646 <<
" with loop invariant: " << *S <<
'\n');
649 DeadInsts.emplace_back(
I);
654bool SimplifyIndvar::replaceFloatIVWithIntegerIV(
Instruction *UseInst) {
655 if (UseInst->
getOpcode() != CastInst::SIToFP &&
656 UseInst->
getOpcode() != CastInst::UIToFP)
661 const SCEV *
IV = SE->getSCEV(IVOperand);
663 if (UseInst->
getOpcode() == CastInst::SIToFP)
664 MaskBits = SE->getSignedRange(
IV).getMinSignedBits();
666 MaskBits = SE->getUnsignedRange(
IV).getActiveBits();
668 if (MaskBits <= DestNumSigBits) {
671 auto *CI = dyn_cast<CastInst>(U);
676 if (Opcode != CastInst::FPToSI && Opcode != CastInst::FPToUI)
679 Value *Conv =
nullptr;
680 if (IVOperand->
getType() != CI->getType()) {
685 if (SE->getTypeSizeInBits(IVOperand->
getType()) >
686 SE->getTypeSizeInBits(CI->getType())) {
687 Conv =
Builder.CreateTrunc(IVOperand, CI->getType(),
Name +
".trunc");
688 }
else if (Opcode == CastInst::FPToUI ||
689 UseInst->
getOpcode() == CastInst::UIToFP) {
690 Conv =
Builder.CreateZExt(IVOperand, CI->getType(),
Name +
".zext");
692 Conv =
Builder.CreateSExt(IVOperand, CI->getType(),
Name +
".sext");
698 DeadInsts.push_back(CI);
700 <<
" with: " << *Conv <<
'\n');
711bool SimplifyIndvar::eliminateIdentitySCEV(
Instruction *UseInst,
713 if (!SE->isSCEVable(UseInst->
getType()) ||
715 (SE->getSCEV(UseInst) != SE->getSCEV(IVOperand)))
734 if (isa<PHINode>(UseInst))
737 if (!DT || !DT->dominates(IVOperand, UseInst))
740 if (!LI->replacementPreservesLCSSAForm(UseInst, IVOperand))
743 LLVM_DEBUG(
dbgs() <<
"INDVARS: Eliminated identity: " << *UseInst <<
'\n');
745 SE->forgetValue(UseInst);
749 DeadInsts.emplace_back(UseInst);
755 return (isa<OverflowingBinaryOperator>(BO) &&
756 strengthenOverflowingOperation(BO, IVOperand)) ||
757 (isa<ShlOperator>(BO) && strengthenRightShift(BO, IVOperand));
762bool SimplifyIndvar::strengthenOverflowingOperation(
BinaryOperator *BO,
764 auto Flags = SE->getStrengthenedNoWrapFlagsFromBinOp(
765 cast<OverflowingBinaryOperator>(BO));
790 if (BO->
getOpcode() == Instruction::Shl) {
791 bool Changed =
false;
792 ConstantRange IVRange = SE->getUnsignedRange(SE->getSCEV(IVOperand));
793 for (
auto *U : BO->
users()) {
816 SmallVectorImpl< std::pair<Instruction*,Instruction*> > &SimpleIVUsers) {
818 for (
User *U : Def->users()) {
830 if (!L->contains(UI))
834 if (!Simplified.insert(UI).second)
837 SimpleIVUsers.push_back(std::make_pair(UI, Def));
875 if (!SE->isSCEVable(CurrIV->
getType()))
889 while (!SimpleIVUsers.
empty()) {
890 std::pair<Instruction*, Instruction*> UseOper =
899 DeadInsts.emplace_back(UseInst);
904 if (UseInst == CurrIV)
continue;
908 if (replaceIVUserWithLoopInvariant(UseInst))
912 if (isa<PtrToIntInst>(UseInst))
913 for (
Use &U : UseInst->
uses()) {
915 if (replaceIVUserWithLoopInvariant(
User))
920 for (
unsigned N = 0; IVOperand; ++
N) {
924 Value *NewOper = foldIVUser(UseInst, IVOperand);
927 IVOperand = dyn_cast<Instruction>(NewOper);
932 if (eliminateIVUser(UseInst, IVOperand)) {
933 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
938 if (strengthenBinaryOp(BO, IVOperand)) {
941 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
946 if (replaceFloatIVWithIntegerIV(UseInst)) {
948 pushIVUsers(IVOperand, L, Simplified, SimpleIVUsers);
952 CastInst *Cast = dyn_cast<CastInst>(UseInst);
958 pushIVUsers(UseInst, L, Simplified, SimpleIVUsers);
975 SIV.simplifyUsers(CurrIV, V);
976 return SIV.hasChanged();
988 bool Changed =
false;
1019 bool UsePostIncrementRanges;
1022 unsigned NumElimExt = 0;
1023 unsigned NumWidened = 0;
1028 const SCEV *WideIncExpr =
nullptr;
1049 std::optional<ConstantRange> getPostIncRangeInfo(
Value *Def,
1051 DefUserPair
Key(Def, UseI);
1052 auto It = PostIncRangeInfos.
find(Key);
1053 return It == PostIncRangeInfos.
end()
1054 ? std::optional<ConstantRange>(std::nullopt)
1058 void calculatePostIncRanges(
PHINode *OrigPhi);
1062 DefUserPair
Key(Def, UseI);
1063 auto It = PostIncRangeInfos.
find(Key);
1064 if (It == PostIncRangeInfos.
end())
1067 It->second =
R.intersectWith(It->second);
1074 struct NarrowIVDefUse {
1082 bool NeverNegative =
false;
1086 : NarrowDef(ND), NarrowUse(NU), WideDef(WD),
1087 NeverNegative(NeverNegative) {}
1092 bool HasGuards,
bool UsePostIncrementRanges =
true);
1096 unsigned getNumElimExt() {
return NumElimExt; };
1097 unsigned getNumWidened() {
return NumWidened; };
1100 Value *createExtendInst(
Value *NarrowOper,
Type *WideType,
bool IsSigned,
1104 Instruction *cloneArithmeticIVUser(NarrowIVDefUse DU,
1106 Instruction *cloneBitwiseIVUser(NarrowIVDefUse DU);
1110 using WidenedRecTy = std::pair<const SCEVAddRecExpr *, ExtendKind>;
1112 WidenedRecTy getWideRecurrence(NarrowIVDefUse DU);
1114 WidenedRecTy getExtendedOperandRecurrence(NarrowIVDefUse DU);
1116 const SCEV *getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1117 unsigned OpCode)
const;
1121 bool widenLoopCompare(NarrowIVDefUse DU);
1122 bool widenWithVariantUse(NarrowIVDefUse DU);
1144 for (
unsigned i = 0, e =
PHI->getNumIncomingValues(); i != e; ++i) {
1145 if (
PHI->getIncomingValue(i) != Def)
1166 auto *DefI = dyn_cast<Instruction>(Def);
1170 assert(DT->
dominates(DefI, InsertPt) &&
"def does not dominate all uses");
1175 for (
auto *DTN = (*DT)[InsertPt->
getParent()]; DTN; DTN = DTN->getIDom())
1177 return DTN->getBlock()->getTerminator();
1185 : OrigPhi(WI.NarrowIV), WideType(WI.WidestNativeType), LI(LInfo),
1186 L(LI->getLoopFor(OrigPhi->
getParent())), SE(SEv), DT(DTree),
1189 assert(L->getHeader() == OrigPhi->
getParent() &&
"Phi must be an IV");
1190 ExtendKindMap[OrigPhi] = WI.
IsSigned ? ExtendKind::Sign : ExtendKind::Zero;
1193Value *WidenIV::createExtendInst(
Value *NarrowOper,
Type *WideType,
1199 L &&
L->getLoopPreheader() &&
L->isLoopInvariant(NarrowOper);
1200 L =
L->getParentLoop())
1201 Builder.SetInsertPoint(
L->getLoopPreheader()->getTerminator());
1203 return IsSigned ?
Builder.CreateSExt(NarrowOper, WideType) :
1204 Builder.CreateZExt(NarrowOper, WideType);
1210Instruction *WidenIV::cloneIVUser(WidenIV::NarrowIVDefUse DU,
1212 unsigned Opcode = DU.NarrowUse->
getOpcode();
1216 case Instruction::Add:
1217 case Instruction::Mul:
1218 case Instruction::UDiv:
1219 case Instruction::Sub:
1220 return cloneArithmeticIVUser(DU, WideAR);
1222 case Instruction::And:
1223 case Instruction::Or:
1224 case Instruction::Xor:
1225 case Instruction::Shl:
1226 case Instruction::LShr:
1227 case Instruction::AShr:
1228 return cloneBitwiseIVUser(DU);
1232Instruction *WidenIV::cloneBitwiseIVUser(WidenIV::NarrowIVDefUse DU) {
1237 LLVM_DEBUG(
dbgs() <<
"Cloning bitwise IVUser: " << *NarrowUse <<
"\n");
1243 bool IsSigned = getExtendKind(NarrowDef) == ExtendKind::Sign;
1246 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1247 IsSigned, NarrowUse);
1250 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1251 IsSigned, NarrowUse);
1253 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1255 NarrowBO->getName());
1258 WideBO->copyIRFlags(NarrowBO);
1262Instruction *WidenIV::cloneArithmeticIVUser(WidenIV::NarrowIVDefUse DU,
1268 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1270 unsigned IVOpIdx = (NarrowUse->
getOperand(0) == NarrowDef) ? 0 : 1;
1281 auto GuessNonIVOperand = [&](
bool SignExt) {
1282 const SCEV *WideLHS;
1283 const SCEV *WideRHS;
1285 auto GetExtend = [
this, SignExt](
const SCEV *S,
Type *Ty) {
1292 WideLHS = SE->
getSCEV(WideDef);
1294 WideRHS = GetExtend(NarrowRHS, WideType);
1297 WideLHS = GetExtend(NarrowLHS, WideType);
1298 WideRHS = SE->
getSCEV(WideDef);
1302 const SCEV *WideUse =
1303 getSCEVByOpCode(WideLHS, WideRHS, NarrowUse->
getOpcode());
1305 return WideUse == WideAR;
1308 bool SignExtend = getExtendKind(NarrowDef) == ExtendKind::Sign;
1309 if (!GuessNonIVOperand(SignExtend)) {
1310 SignExtend = !SignExtend;
1311 if (!GuessNonIVOperand(SignExtend))
1317 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1318 SignExtend, NarrowUse);
1321 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1322 SignExtend, NarrowUse);
1324 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1326 NarrowBO->getName());
1330 WideBO->copyIRFlags(NarrowBO);
1334WidenIV::ExtendKind WidenIV::getExtendKind(
Instruction *
I) {
1335 auto It = ExtendKindMap.
find(
I);
1336 assert(It != ExtendKindMap.
end() &&
"Instruction not yet extended!");
1340const SCEV *WidenIV::getSCEVByOpCode(
const SCEV *LHS,
const SCEV *RHS,
1341 unsigned OpCode)
const {
1343 case Instruction::Add:
1345 case Instruction::Sub:
1347 case Instruction::Mul:
1349 case Instruction::UDiv:
1361WidenIV::WidenedRecTy
1362WidenIV::getExtendedOperandRecurrence(WidenIV::NarrowIVDefUse DU) {
1364 const unsigned OpCode = DU.NarrowUse->getOpcode();
1366 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1367 OpCode != Instruction::Mul)
1368 return {
nullptr, ExtendKind::Unknown};
1372 const unsigned ExtendOperIdx =
1373 DU.NarrowUse->getOperand(0) == DU.NarrowDef ? 1 : 0;
1374 assert(DU.NarrowUse->getOperand(1-ExtendOperIdx) == DU.NarrowDef &&
"bad DU");
1376 const SCEV *ExtendOperExpr =
nullptr;
1378 cast<OverflowingBinaryOperator>(DU.NarrowUse);
1379 ExtendKind ExtKind = getExtendKind(DU.NarrowDef);
1382 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1385 SE->
getSCEV(DU.NarrowUse->getOperand(ExtendOperIdx)), WideType);
1387 return {
nullptr, ExtendKind::Unknown};
1395 const SCEV *rhs = ExtendOperExpr;
1399 if (ExtendOperIdx == 0)
1402 dyn_cast<SCEVAddRecExpr>(getSCEVByOpCode(lhs, rhs, OpCode));
1404 if (!AddRec || AddRec->
getLoop() != L)
1405 return {
nullptr, ExtendKind::Unknown};
1407 return {AddRec, ExtKind};
1415WidenIV::WidenedRecTy WidenIV::getWideRecurrence(WidenIV::NarrowIVDefUse DU) {
1416 if (!DU.NarrowUse->getType()->isIntegerTy())
1417 return {
nullptr, ExtendKind::Unknown};
1419 const SCEV *NarrowExpr = SE->
getSCEV(DU.NarrowUse);
1424 return {
nullptr, ExtendKind::Unknown};
1427 const SCEV *WideExpr;
1429 if (DU.NeverNegative) {
1431 if (isa<SCEVAddRecExpr>(WideExpr))
1432 ExtKind = ExtendKind::Sign;
1435 ExtKind = ExtendKind::Zero;
1437 }
else if (getExtendKind(DU.NarrowDef) == ExtendKind::Sign) {
1439 ExtKind = ExtendKind::Sign;
1442 ExtKind = ExtendKind::Zero;
1444 const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(WideExpr);
1445 if (!AddRec || AddRec->
getLoop() != L)
1446 return {
nullptr, ExtendKind::Unknown};
1447 return {AddRec, ExtKind};
1457 LLVM_DEBUG(
dbgs() <<
"INDVARS: Truncate IV " << *DU.WideDef <<
" for user "
1458 << *DU.NarrowUse <<
"\n");
1460 Value *Trunc =
Builder.CreateTrunc(DU.WideDef, DU.NarrowDef->getType());
1461 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, Trunc);
1467bool WidenIV::widenLoopCompare(WidenIV::NarrowIVDefUse DU) {
1486 bool IsSigned = getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1487 if (!(DU.NeverNegative || IsSigned ==
Cmp->isSigned()))
1490 Value *
Op =
Cmp->getOperand(
Cmp->getOperand(0) == DU.NarrowDef ? 1 : 0);
1493 assert(CastWidth <= IVWidth &&
"Unexpected width while widening compare.");
1500 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1503 if (CastWidth < IVWidth) {
1504 Value *ExtOp = createExtendInst(
Op, WideType,
Cmp->isSigned(), Cmp);
1505 DU.NarrowUse->replaceUsesOfWith(
Op, ExtOp);
1530bool WidenIV::widenWithVariantUse(WidenIV::NarrowIVDefUse DU) {
1536 const unsigned OpCode = NarrowUse->
getOpcode();
1538 if (OpCode != Instruction::Add && OpCode != Instruction::Sub &&
1539 OpCode != Instruction::Mul)
1549 cast<OverflowingBinaryOperator>(NarrowUse);
1550 ExtendKind ExtKind = getExtendKind(NarrowDef);
1551 bool CanSignExtend = ExtKind == ExtendKind::Sign && OBO->
hasNoSignedWrap();
1553 auto AnotherOpExtKind = ExtKind;
1563 for (
Use &U : NarrowUse->
uses()) {
1565 if (
User == NarrowDef)
1567 if (!
L->contains(
User)) {
1568 auto *LCSSAPhi = cast<PHINode>(
User);
1571 if (LCSSAPhi->getNumOperands() != 1)
1576 if (
auto *ICmp = dyn_cast<ICmpInst>(
User)) {
1582 if (ExtKind == ExtendKind::Zero && ICmpInst::isSigned(Pred))
1584 if (ExtKind == ExtendKind::Sign && ICmpInst::isUnsigned(Pred))
1589 if (ExtKind == ExtendKind::Sign)
1597 if (ExtUsers.
empty()) {
1607 if (!CanSignExtend && !CanZeroExtend) {
1610 if (OpCode != Instruction::Add)
1612 if (ExtKind != ExtendKind::Zero)
1627 AnotherOpExtKind = ExtendKind::Sign;
1633 if (!AddRecOp1 || AddRecOp1->
getLoop() != L)
1636 LLVM_DEBUG(
dbgs() <<
"Cloning arithmetic IVUser: " << *NarrowUse <<
"\n");
1642 : createExtendInst(NarrowUse->
getOperand(0), WideType,
1643 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1647 : createExtendInst(NarrowUse->
getOperand(1), WideType,
1648 AnotherOpExtKind == ExtendKind::Sign, NarrowUse);
1650 auto *NarrowBO = cast<BinaryOperator>(NarrowUse);
1652 NarrowBO->getName());
1655 WideBO->copyIRFlags(NarrowBO);
1656 ExtendKindMap[NarrowUse] = ExtKind;
1661 << *WideBO <<
"\n");
1672 BasicBlock *LoopExitingBlock =
User->getParent()->getSinglePredecessor();
1673 assert(LoopExitingBlock &&
L->contains(LoopExitingBlock) &&
1674 "Not a LCSSA Phi?");
1675 WidePN->addIncoming(WideBO, LoopExitingBlock);
1677 User->getParent()->getFirstInsertionPt());
1688 if (ExtKind == ExtendKind::Zero)
1689 return Builder.CreateZExt(V, WideBO->getType());
1691 return Builder.CreateSExt(V, WideBO->getType());
1693 auto Pred =
User->getPredicate();
1709 "Should already know the kind of extension used to widen NarrowDef");
1712 if (
PHINode *UsePhi = dyn_cast<PHINode>(DU.NarrowUse)) {
1713 if (LI->
getLoopFor(UsePhi->getParent()) != L) {
1717 if (UsePhi->getNumOperands() != 1)
1723 if (isa<CatchSwitchInst>(UsePhi->getParent()->getTerminator()))
1727 PHINode::Create(DU.WideDef->getType(), 1, UsePhi->getName() +
".wide",
1729 WidePhi->
addIncoming(DU.WideDef, UsePhi->getIncomingBlock(0));
1732 Value *Trunc =
Builder.CreateTrunc(WidePhi, DU.NarrowDef->getType());
1733 UsePhi->replaceAllUsesWith(Trunc);
1735 LLVM_DEBUG(
dbgs() <<
"INDVARS: Widen lcssa phi " << *UsePhi <<
" to "
1736 << *WidePhi <<
"\n");
1744 auto canWidenBySExt = [&]() {
1745 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Sign;
1747 auto canWidenByZExt = [&]() {
1748 return DU.NeverNegative || getExtendKind(DU.NarrowDef) == ExtendKind::Zero;
1752 if ((isa<SExtInst>(DU.NarrowUse) && canWidenBySExt()) ||
1753 (isa<ZExtInst>(DU.NarrowUse) && canWidenByZExt())) {
1754 Value *NewDef = DU.WideDef;
1755 if (DU.NarrowUse->getType() != WideType) {
1758 if (CastWidth < IVWidth) {
1761 NewDef =
Builder.CreateTrunc(DU.WideDef, DU.NarrowUse->getType());
1768 <<
" not wide enough to subsume " << *DU.NarrowUse
1770 DU.NarrowUse->replaceUsesOfWith(DU.NarrowDef, DU.WideDef);
1771 NewDef = DU.NarrowUse;
1774 if (NewDef != DU.NarrowUse) {
1776 <<
" replaced by " << *DU.WideDef <<
"\n");
1778 DU.NarrowUse->replaceAllUsesWith(NewDef);
1792 WidenedRecTy WideAddRec = getExtendedOperandRecurrence(DU);
1793 if (!WideAddRec.first)
1794 WideAddRec = getWideRecurrence(DU);
1796 assert((WideAddRec.first ==
nullptr) ==
1797 (WideAddRec.second == ExtendKind::Unknown));
1798 if (!WideAddRec.first) {
1801 if (widenLoopCompare(DU))
1809 if (widenWithVariantUse(DU))
1822 if (WideAddRec.first == WideIncExpr &&
1823 Rewriter.hoistIVInc(WideInc, DU.NarrowUse))
1826 WideUse = cloneIVUser(DU, WideAddRec.first);
1835 if (WideAddRec.first != SE->
getSCEV(WideUse)) {
1836 LLVM_DEBUG(
dbgs() <<
"Wide use expression mismatch: " << *WideUse <<
": "
1837 << *SE->
getSCEV(WideUse) <<
" != " << *WideAddRec.first
1847 ExtendKindMap[DU.NarrowUse] = WideAddRec.second;
1855 bool NonNegativeDef =
1862 if (!Widened.
insert(NarrowUser).second)
1865 bool NonNegativeUse =
false;
1866 if (!NonNegativeDef) {
1868 if (
auto RangeInfo = getPostIncRangeInfo(NarrowDef, NarrowUser))
1869 NonNegativeUse = RangeInfo->getSignedMin().isNonNegative();
1872 NarrowIVUsers.emplace_back(NarrowDef, NarrowUser, WideDef,
1873 NonNegativeDef || NonNegativeUse);
1892 const SCEV *WideIVExpr = getExtendKind(OrigPhi) == ExtendKind::Sign
1897 "Expect the new IV expression to preserve its type");
1900 AddRec = dyn_cast<SCEVAddRecExpr>(WideIVExpr);
1901 if (!AddRec || AddRec->
getLoop() != L)
1910 "Loop header phi recurrence inputs do not dominate the loop");
1923 calculatePostIncRanges(OrigPhi);
1929 Instruction *InsertPt = &*
L->getHeader()->getFirstInsertionPt();
1930 Value *ExpandInst =
Rewriter.expandCodeFor(AddRec, WideType, InsertPt);
1933 if (!(WidePhi = dyn_cast<PHINode>(ExpandInst))) {
1938 Rewriter.isInsertedInstruction(cast<Instruction>(ExpandInst)))
1951 WideIncExpr = SE->
getSCEV(WideInc);
1964 assert(Widened.
empty() && NarrowIVUsers.empty() &&
"expect initial state" );
1967 pushNarrowIVUsers(OrigPhi, WidePhi);
1969 while (!NarrowIVUsers.empty()) {
1970 WidenIV::NarrowIVDefUse DU = NarrowIVUsers.pop_back_val();
1978 pushNarrowIVUsers(DU.NarrowUse, WideUse);
1981 if (DU.NarrowDef->use_empty())
1993void WidenIV::calculatePostIncRange(
Instruction *NarrowDef,
1997 Value *NarrowDefLHS;
1998 const APInt *NarrowDefRHS;
2004 auto UpdateRangeFromCondition = [&] (
Value *Condition,
2016 auto CmpConstrainedLHSRange =
2018 auto NarrowDefRange = CmpConstrainedLHSRange.addWithNoWrap(
2021 updatePostIncRangeInfo(NarrowDef, NarrowUser, NarrowDefRange);
2024 auto UpdateRangeFromGuards = [&](
Instruction *Ctx) {
2029 Ctx->getParent()->rend())) {
2031 if (
match(&
I, m_Intrinsic<Intrinsic::experimental_guard>(
m_Value(
C))))
2032 UpdateRangeFromCondition(
C,
true);
2036 UpdateRangeFromGuards(NarrowUser);
2044 for (
auto *DTB = (*DT)[NarrowUserBB]->getIDom();
2045 L->contains(DTB->getBlock());
2046 DTB = DTB->getIDom()) {
2047 auto *BB = DTB->getBlock();
2048 auto *TI = BB->getTerminator();
2049 UpdateRangeFromGuards(TI);
2051 auto *BI = dyn_cast<BranchInst>(TI);
2052 if (!BI || !BI->isConditional())
2055 auto *TrueSuccessor = BI->getSuccessor(0);
2056 auto *FalseSuccessor = BI->getSuccessor(1);
2058 auto DominatesNarrowUser = [
this, NarrowUser] (
BasicBlockEdge BBE) {
2059 return BBE.isSingleEdge() &&
2064 UpdateRangeFromCondition(BI->getCondition(),
true);
2067 UpdateRangeFromCondition(BI->getCondition(),
false);
2072void WidenIV::calculatePostIncRanges(
PHINode *OrigPhi) {
2078 while (!Worklist.
empty()) {
2081 for (
Use &U : NarrowDef->
uses()) {
2082 auto *NarrowUser = cast<Instruction>(
U.getUser());
2085 auto *NarrowUserLoop = (*LI)[NarrowUser->
getParent()];
2086 if (!NarrowUserLoop || !
L->contains(NarrowUserLoop))
2089 if (!Visited.
insert(NarrowUser).second)
2094 calculatePostIncRange(NarrowDef, NarrowUser);
2102 unsigned &NumElimExt,
unsigned &NumWidened,
2106 NumElimExt = Widener.getNumElimExt();
2107 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...
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.
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
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.