31using namespace PatternMatch;
33#define DEBUG_TYPE "instcombine"
42 const APInt &In2,
bool IsSigned =
false) {
45 Result = In1.
sadd_ov(In2, Overflow);
47 Result = In1.
uadd_ov(In2, Overflow);
55 const APInt &In2,
bool IsSigned =
false) {
58 Result = In1.
ssub_ov(In2, Overflow);
60 Result = In1.
usub_ov(In2, Overflow);
68 for (
auto *U :
I.users())
69 if (isa<BranchInst>(U))
79 if (!ICmpInst::isSigned(Pred))
86 if (Pred == ICmpInst::ICMP_SLT) {
87 Pred = ICmpInst::ICMP_SLE;
90 }
else if (
C.isAllOnes()) {
91 if (Pred == ICmpInst::ICMP_SGT) {
92 Pred = ICmpInst::ICMP_SGE;
111 if (
LI->isVolatile() ||
LI->getType() !=
GEP->getResultElementType() ||
117 if (!isa<ConstantArray>(
Init) && !isa<ConstantDataArray>(
Init))
120 uint64_t ArrayElementCount =
Init->getType()->getArrayNumElements();
129 if (
GEP->getNumOperands() < 3 ||
130 !isa<ConstantInt>(
GEP->getOperand(1)) ||
131 !cast<ConstantInt>(
GEP->getOperand(1))->isZero() ||
132 isa<Constant>(
GEP->getOperand(2)))
140 Type *EltTy =
Init->getType()->getArrayElementType();
141 for (
unsigned i = 3, e =
GEP->getNumOperands(); i != e; ++i) {
143 if (!
Idx)
return nullptr;
146 if ((
unsigned)IdxVal != IdxVal)
return nullptr;
148 if (
StructType *STy = dyn_cast<StructType>(EltTy))
149 EltTy = STy->getElementType(IdxVal);
150 else if (
ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
151 if (IdxVal >= ATy->getNumElements())
return nullptr;
152 EltTy = ATy->getElementType();
160 enum { Overdefined = -3, Undefined = -2 };
169 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
173 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
181 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
190 for (
unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
192 if (!Elt)
return nullptr;
195 if (!LaterIndices.
empty()) {
210 CompareRHS,
DL, &
TLI);
212 if (isa<UndefValue>(
C)) {
215 if (TrueRangeEnd == (
int)i-1)
217 if (FalseRangeEnd == (
int)i-1)
224 if (!isa<ConstantInt>(
C))
return nullptr;
228 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
233 if (FirstTrueElement == Undefined)
234 FirstTrueElement = TrueRangeEnd = i;
237 if (SecondTrueElement == Undefined)
238 SecondTrueElement = i;
240 SecondTrueElement = Overdefined;
243 if (TrueRangeEnd == (
int)i-1)
246 TrueRangeEnd = Overdefined;
250 if (FirstFalseElement == Undefined)
251 FirstFalseElement = FalseRangeEnd = i;
254 if (SecondFalseElement == Undefined)
255 SecondFalseElement = i;
257 SecondFalseElement = Overdefined;
260 if (FalseRangeEnd == (
int)i-1)
263 FalseRangeEnd = Overdefined;
268 if (i < 64 && IsTrueForElt)
269 MagicBitvector |= 1ULL << i;
274 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
275 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
276 FalseRangeEnd == Overdefined)
287 if (!
GEP->isInBounds()) {
290 if (
Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
301 unsigned ElementSize =
314 if (SecondTrueElement != Overdefined) {
317 if (FirstTrueElement == Undefined)
323 if (SecondTrueElement == Undefined)
330 return BinaryOperator::CreateOr(C1, C2);
335 if (SecondFalseElement != Overdefined) {
338 if (FirstFalseElement == Undefined)
344 if (SecondFalseElement == Undefined)
351 return BinaryOperator::CreateAnd(C1, C2);
356 if (TrueRangeEnd != Overdefined) {
357 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
361 if (FirstTrueElement) {
367 TrueRangeEnd-FirstTrueElement+1);
372 if (FalseRangeEnd != Overdefined) {
373 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
376 if (FirstFalseElement) {
382 FalseRangeEnd-FirstFalseElement);
395 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
429 while (!WorkList.
empty()) {
432 while (!WorkList.
empty()) {
433 if (Explored.
size() >= 100)
443 if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
444 !isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
449 if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
450 auto *CI = cast<CastInst>(V);
451 if (!CI->isNoopCast(
DL))
454 if (!Explored.
contains(CI->getOperand(0)))
458 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
462 if (
GEP->getNumIndices() != 1 || !
GEP->isInBounds() ||
463 GEP->getSourceElementType() != ElemTy)
470 if (WorkList.
back() == V) {
476 if (
auto *PN = dyn_cast<PHINode>(V)) {
478 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
486 for (
auto *PN : PHIs)
487 for (
Value *
Op : PN->incoming_values())
495 for (
Value *Val : Explored) {
498 auto *
PHI = dyn_cast<PHINode>(
Use);
499 auto *Inst = dyn_cast<Instruction>(Val);
501 if (Inst ==
Base || Inst ==
PHI || !Inst || !
PHI ||
505 if (
PHI->getParent() == Inst->getParent())
515 bool Before =
true) {
516 if (
auto *
PHI = dyn_cast<PHINode>(V)) {
521 if (
auto *
I = dyn_cast<Instruction>(V)) {
523 I = &*std::next(
I->getIterator());
527 if (
auto *
A = dyn_cast<Argument>(V)) {
529 BasicBlock &Entry =
A->getParent()->getEntryBlock();
530 Builder.SetInsertPoint(&Entry, Entry.getFirstInsertionPt());
535 assert(isa<Constant>(V) &&
"Setting insertion point for unknown value!");
552 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
558 for (
Value *Val : Explored) {
563 if (
auto *
PHI = dyn_cast<PHINode>(Val))
565 PHI->getName() +
".idx",
PHI);
570 for (
Value *Val : Explored) {
575 if (
auto *CI = dyn_cast<CastInst>(Val)) {
578 Value *V = NewInsts[CI->getOperand(0)];
582 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
584 :
GEP->getOperand(1);
588 if (
Index->getType()->getScalarSizeInBits() !=
589 NewInsts[
GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
591 Index, NewInsts[
GEP->getOperand(0)]->getType(),
592 GEP->getOperand(0)->getName() +
".sext");
595 auto *
Op = NewInsts[
GEP->getOperand(0)];
596 if (isa<ConstantInt>(
Op) && cast<ConstantInt>(
Op)->
isZero())
600 Op,
Index,
GEP->getOperand(0)->getName() +
".add");
603 if (isa<PHINode>(Val))
610 for (
Value *Val : Explored) {
615 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
617 for (
unsigned I = 0,
E =
PHI->getNumIncomingValues();
I <
E; ++
I) {
618 Value *NewIncoming =
PHI->getIncomingValue(
I);
621 NewIncoming = NewInsts[NewIncoming];
629 Base->getContext(), Start->getType()->getPointerAddressSpace());
630 for (
Value *Val : Explored) {
640 Base, PtrTy, Start->getName() +
"to.ptr");
641 NewVal =
Builder.CreateInBoundsGEP(ElemTy, NewVal,
ArrayRef(NewInsts[Val]),
642 Val->getName() +
".ptr");
643 NewVal =
Builder.CreateBitOrPointerCast(
644 NewVal, Val->
getType(), Val->getName() +
".conv");
651 return NewInsts[Start];
657static std::pair<Value *, Value *>
660 DL.getIndexTypeSizeInBits(V->getType()));
667 if (!
GEP->isInBounds())
669 if (
GEP->hasAllConstantIndices() &&
GEP->getNumIndices() == 1 &&
670 GEP->getSourceElementType() == ElemTy) {
671 V =
GEP->getOperand(0);
679 if (
auto *CI = dyn_cast<IntToPtrInst>(V)) {
680 if (!CI->isNoopCast(
DL))
682 V = CI->getOperand(0);
685 if (
auto *CI = dyn_cast<PtrToIntInst>(V)) {
686 if (!CI->isNoopCast(
DL))
688 V = CI->getOperand(0);
750 if (!isa<GetElementPtrInst>(
RHS))
762 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
784 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
789 cast<Constant>(
RHS),
Base->getType()));
793 if (PtrBase != GEPRHS->getOperand(0)) {
794 bool IndicesTheSame =
797 GEPRHS->getPointerOperand()->getType() &&
801 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
802 IndicesTheSame =
false;
815 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
817 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
821 Value *LOffset = EmitGEPOffset(GEPLHS);
822 Value *ROffset = EmitGEPOffset(GEPRHS);
829 if (LHSIndexTy != RHSIndexTy) {
856 if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
859 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
863 unsigned NumDifferences = 0;
864 unsigned DiffOperand = 0;
865 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
866 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
868 Type *RHSType = GEPRHS->getOperand(i)->getType();
879 if (NumDifferences++)
break;
883 if (NumDifferences == 0)
887 else if (NumDifferences == 1 && GEPsInBounds) {
889 Value *RHSV = GEPRHS->getOperand(DiffOperand);
898 (isa<ConstantExpr>(GEPLHS) || GEPLHS->
hasOneUse()) &&
899 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
901 Value *L = EmitGEPOffset(GEPLHS);
902 Value *R = EmitGEPOffset(GEPRHS);
929 bool Captured =
false;
934 CmpCaptureTracker(
AllocaInst *Alloca) : Alloca(Alloca) {}
936 void tooManyUses()
override { Captured =
true; }
938 bool captured(
const Use *U)
override {
939 auto *ICmp = dyn_cast<ICmpInst>(U->getUser());
947 auto Res = ICmps.
insert({ICmp, 0});
948 Res.first->second |= 1u << U->getOperandNo();
957 CmpCaptureTracker Tracker(Alloca);
959 if (Tracker.Captured)
962 bool Changed =
false;
963 for (
auto [ICmp,
Operands] : Tracker.ICmps) {
995 assert(!!
C &&
"C should not be zero!");
1043 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1046 if (
I.getPredicate() ==
I.ICMP_NE)
1055 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1067 return getICmp(
I.ICMP_UGT,
A,
1080 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1086 }
else if (AP1 == AP2.
lshr(Shift)) {
1102 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1105 if (
I.getPredicate() ==
I.ICMP_NE)
1116 if (!AP1 && AP2TrailingZeros != 0)
1127 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1153 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1161 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1185 if (U == AddWithCst)
1203 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1209 Builder.SetInsertPoint(OrigAdd);
1211 Value *TruncA =
Builder.CreateTrunc(
A, NewType,
A->getName() +
".trunc");
1212 Value *TruncB =
Builder.CreateTrunc(
B, NewType,
B->getName() +
".trunc");
1232 if (!
I.isEquality())
1263 APInt(XBitWidth, XBitWidth - 1))))
1265 }
else if (isa<BinaryOperator>(Val) &&
1290 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1292 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1309 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1321 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1327 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1329 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1330 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1338 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1343 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1375 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1388 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1389 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1391 for (
Value *V : Phi->incoming_values()) {
1400 for (
auto [V, Pred] :
zip(Ops, Phi->blocks()))
1422 assert((TrueBB == CmpBB || FalseBB == CmpBB) &&
1423 "Predecessor block does not point to successor?");
1426 if (TrueBB == FalseBB)
1433 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1464 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1469 if (Cmp.hasOneUse() &&
1488 if (
C.isOne() &&
C.getBitWidth() > 1) {
1496 Type *SrcTy =
X->getType();
1507 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1516 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1519 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1532 if ((Known.
Zero | Known.
One).countl_one() >= SrcBits - DstBits) {
1534 APInt NewRHS =
C.zext(SrcBits);
1544 const APInt *ShAmtC;
1574 bool TrueIfSigned =
false;
1591 if (
Xor->hasOneUse()) {
1593 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1594 Pred = Cmp.getFlippedSignednessPredicate();
1600 Pred = Cmp.getFlippedSignednessPredicate();
1601 Pred = Cmp.getSwappedPredicate(Pred);
1609 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1612 if (*XorC ==
C && (
C + 1).isPowerOf2())
1617 if (*XorC == -
C &&
C.isPowerOf2())
1621 if (*XorC ==
C && (-
C).isPowerOf2())
1645 const APInt *ShiftC;
1650 Type *XType =
X->getType();
1665 if (!Shift || !Shift->
isShift())
1673 unsigned ShiftOpcode = Shift->
getOpcode();
1674 bool IsShl = ShiftOpcode == Instruction::Shl;
1677 APInt NewAndCst, NewCmpCst;
1678 bool AnyCmpCstBitsShiftedOut;
1679 if (ShiftOpcode == Instruction::Shl) {
1687 NewCmpCst = C1.
lshr(*C3);
1688 NewAndCst = C2.
lshr(*C3);
1689 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1690 }
else if (ShiftOpcode == Instruction::LShr) {
1695 NewCmpCst = C1.
shl(*C3);
1696 NewAndCst = C2.
shl(*C3);
1697 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1703 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1704 NewCmpCst = C1.
shl(*C3);
1705 NewAndCst = C2.
shl(*C3);
1706 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1707 if (NewAndCst.
ashr(*C3) != C2)
1711 if (AnyCmpCstBitsShiftedOut) {
1722 return new ICmpInst(Cmp.getPredicate(),
1754 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1756 return new TruncInst(
And->getOperand(0), Cmp.getType());
1764 if (!
And->hasOneUse())
1767 if (Cmp.isEquality() && C1.
isZero()) {
1787 return new ICmpInst(NewPred,
X, NegBOC);
1805 if (!Cmp.getType()->isVectorTy()) {
1806 Type *WideType = W->getType();
1811 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1822 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1824 Constant *One = cast<Constant>(
And->getOperand(1));
1829 unsigned UsesRemoved = 0;
1830 if (
And->hasOneUse())
1832 if (
Or->hasOneUse())
1839 if (UsesRemoved >= RequireUsesRemoved) {
1843 One,
Or->getName());
1878 return new ICmpInst(NewPred,
X, MinSignedC);
1887 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1888 if (
auto *
LI = dyn_cast<LoadInst>(
X))
1889 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
LI->getOperand(0)))
1890 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1895 if (!Cmp.isEquality())
1901 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1904 return new ICmpInst(NewPred,
X,
SubOne(cast<Constant>(Cmp.getOperand(1))));
1917 assert(Cmp.isEquality() &&
"Not expecting non-equality predicates");
1919 const APInt *TC, *FC;
1936 X->getType()->isIntOrIntVectorTy(1) && (
C.isZero() ||
C.isOne())) {
1942 return BinaryOperator::CreateAnd(TruncY,
X);
1963 while (!WorkList.
empty()) {
1964 auto MatchOrOperatorArgument = [&](
Value *OrOperatorArgument) {
1967 if (
match(OrOperatorArgument,
1973 if (
match(OrOperatorArgument,
1983 Value *OrOperatorLhs, *OrOperatorRhs;
1985 if (!
match(CurrentValue,
1990 MatchOrOperatorArgument(OrOperatorRhs);
1991 MatchOrOperatorArgument(OrOperatorLhs);
1997 CmpValues.
rbegin()->second);
1999 for (
auto It = CmpValues.
rbegin() + 1; It != CmpValues.
rend(); ++It) {
2000 Value *RhsCmp =
Builder.CreateICmp(Pred, It->first, It->second);
2001 LhsCmp =
Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp);
2020 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
2022 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
2023 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
2028 return new ICmpInst(Pred, OrOp0, OrOp1);
2035 if (
Or->hasOneUse()) {
2077 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
2109 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
2110 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2132 if (Cmp.isEquality()) {
2134 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2143 if (
C.urem(*MulC).isZero()) {
2146 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2160 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2170 "Unexpected predicate");
2180 "Unexpected predicate");
2186 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2197 unsigned TypeBits =
C.getBitWidth();
2198 bool CIsPowerOf2 =
C.isPowerOf2();
2200 if (Cmp.isUnsigned()) {
2213 unsigned CLog2 =
C.logBase2();
2215 }
else if (Cmp.isSigned()) {
2237 const APInt *ShiftVal;
2267 const APInt *ShiftAmt;
2273 unsigned TypeBits =
C.getBitWidth();
2274 if (ShiftAmt->
uge(TypeBits))
2286 APInt ShiftedC =
C.ashr(*ShiftAmt);
2290 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2291 APInt ShiftedC =
C.ashr(*ShiftAmt);
2299 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2300 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2311 APInt ShiftedC =
C.lshr(*ShiftAmt);
2315 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2316 APInt ShiftedC =
C.lshr(*ShiftAmt);
2324 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2325 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2330 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2341 bool TrueIfSigned =
false;
2353 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2355 if ((
C + 1).isPowerOf2() &&
2363 if (
C.isPowerOf2() &&
2380 if (Shl->
hasOneUse() && Amt != 0 &&
C.countr_zero() >= Amt &&
2383 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2401 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2402 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2404 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2405 const APInt *ShiftValC;
2407 if (Cmp.isEquality())
2425 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2426 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2428 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2436 const APInt *ShiftAmtC;
2442 unsigned TypeBits =
C.getBitWidth();
2444 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2447 bool IsExact = Shr->
isExact();
2458 APInt ShiftedC =
C.shl(ShAmtVal);
2459 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2464 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2465 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2466 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2473 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2474 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2475 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2483 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2497 APInt ShiftedC =
C.shl(ShAmtVal);
2498 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2503 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2504 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2509 if (!Cmp.isEquality())
2517 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2518 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2519 "Expected icmp+shr simplify did not occur.");
2565 const APInt *DivisorC;
2574 !
C.isStrictlyPositive()))
2611 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2616 "icmp ugt X, UINT_MAX should have been simplified already.");
2623 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2639 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2649 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2650 (!DivIsSigned ||
C.isMinSignedValue())) {
2675 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2694 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2707 int LoOverflow = 0, HiOverflow = 0;
2708 APInt LoBound, HiBound;
2713 HiOverflow = LoOverflow = ProdOV;
2722 LoBound = -(RangeSize - 1);
2723 HiBound = RangeSize;
2724 }
else if (
C.isStrictlyPositive()) {
2726 HiOverflow = LoOverflow = ProdOV;
2732 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2734 APInt DivNeg = -RangeSize;
2735 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2743 LoBound = RangeSize + 1;
2744 HiBound = -RangeSize;
2745 if (HiBound == *C2) {
2749 }
else if (
C.isStrictlyPositive()) {
2752 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2758 LoOverflow = HiOverflow = ProdOV;
2771 if (LoOverflow && HiOverflow)
2782 if (LoOverflow && HiOverflow)
2794 if (LoOverflow == +1)
2796 if (LoOverflow == -1)
2801 if (HiOverflow == +1)
2803 if (HiOverflow == -1)
2836 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2846 if (Cmp.isEquality() &&
C.isZero() &&
2882 (*C2 & (
C - 1)) == (
C - 1))
2915 if ((
Add->hasNoSignedWrap() &&
2917 (
Add->hasNoUnsignedWrap() &&
2921 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
2933 if (Cmp.isSigned()) {
2934 if (
Lower.isSignMask())
2936 if (
Upper.isSignMask())
2939 if (
Lower.isMinValue())
2941 if (
Upper.isMinValue())
2974 if (!
Add->hasOneUse())
3017 Value *EqualVal = SI->getTrueValue();
3018 Value *UnequalVal = SI->getFalseValue();
3041 auto FlippedStrictness =
3043 PredB, cast<Constant>(RHS2));
3044 if (!FlippedStrictness)
3047 "basic correctness failure");
3048 RHS2 = FlippedStrictness->second;
3060 assert(
C &&
"Cmp RHS should be a constant int!");
3066 Value *OrigLHS, *OrigRHS;
3067 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
3068 if (Cmp.hasOneUse() &&
3071 assert(C1LessThan && C2Equal && C3GreaterThan);
3073 bool TrueWhenLessThan =
3076 bool TrueWhenEqual =
3079 bool TrueWhenGreaterThan =
3092 if (TrueWhenLessThan)
3098 if (TrueWhenGreaterThan)
3108 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3113 Value *Op1 = Cmp.getOperand(1);
3114 Value *BCSrcOp = Bitcast->getOperand(0);
3115 Type *SrcType = Bitcast->getSrcTy();
3116 Type *DstType = Bitcast->getType();
3163 Type *XType =
X->getType();
3168 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3184 if (DstType->
isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
3187 if (
auto *BC2 = dyn_cast<BitCastInst>(Op1))
3188 Op1 = BC2->getOperand(0);
3191 return new ICmpInst(Pred, BCSrcOp, Op1);
3206 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse() &&
3216 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3218 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3237 auto *VecTy = cast<VectorType>(SrcType);
3238 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3239 if (
C->isSplat(EltTy->getBitWidth())) {
3248 return new ICmpInst(Pred, Extract, NewC);
3261 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3265 if (
auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3269 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3273 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3277 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3284 Value *Cmp0 = Cmp.getOperand(0);
3286 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3288 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3291 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3293 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3308 if (!Cmp.isEquality())
3313 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3317 case Instruction::SRem:
3328 case Instruction::Add: {
3332 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3335 }
else if (
C.isZero()) {
3338 if (
Value *NegVal = dyn_castNegVal(BOp1))
3339 return new ICmpInst(Pred, BOp0, NegVal);
3340 if (
Value *NegVal = dyn_castNegVal(BOp0))
3341 return new ICmpInst(Pred, NegVal, BOp1);
3345 return new ICmpInst(Pred, BOp0, Neg);
3350 case Instruction::Xor:
3352 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3356 }
else if (
C.isZero()) {
3358 return new ICmpInst(Pred, BOp0, BOp1);
3362 case Instruction::Or: {
3374 case Instruction::UDiv:
3375 case Instruction::SDiv:
3385 return new ICmpInst(Pred, BOp0, BOp1);
3388 Instruction::Mul, BO->
getOpcode() == Instruction::SDiv, BOp1,
3389 Cmp.getOperand(1), BO);
3393 return new ICmpInst(Pred, YC, BOp0);
3397 if (BO->
getOpcode() == Instruction::UDiv &&
C.isZero()) {
3400 return new ICmpInst(NewPred, BOp1, BOp0);
3414 "Non-ctpop intrin in ctpop fold");
3455 case Intrinsic::abs:
3458 if (
C.isZero() ||
C.isMinSignedValue())
3462 case Intrinsic::bswap:
3467 case Intrinsic::bitreverse:
3472 case Intrinsic::ctlz:
3473 case Intrinsic::cttz: {
3482 unsigned Num =
C.getLimitedValue(
BitWidth);
3487 APInt Mask2 = IsTrailing
3496 case Intrinsic::ctpop: {
3499 bool IsZero =
C.isZero();
3508 case Intrinsic::fshl:
3509 case Intrinsic::fshr:
3511 const APInt *RotAmtC;
3522 case Intrinsic::umax:
3523 case Intrinsic::uadd_sat: {
3533 case Intrinsic::ssub_sat:
3538 case Intrinsic::usub_sat: {
3558 assert(Cmp.isEquality());
3561 Value *Op0 = Cmp.getOperand(0);
3562 Value *Op1 = Cmp.getOperand(1);
3563 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3564 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3565 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3568 switch (IIOp0->getIntrinsicID()) {
3569 case Intrinsic::bswap:
3570 case Intrinsic::bitreverse:
3573 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3574 case Intrinsic::fshl:
3575 case Intrinsic::fshr: {
3578 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3580 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3582 if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
3583 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3589 unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
3594 Builder.CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
3596 Op0->
getType(), IIOp0->getIntrinsicID(),
3597 {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
3598 return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
3615 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3616 switch (II->getIntrinsicID()) {
3619 case Intrinsic::fshl:
3620 case Intrinsic::fshr:
3621 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3623 if (
C.isZero() ||
C.isAllOnes())
3624 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3638 case Instruction::Xor:
3642 case Instruction::And:
3646 case Instruction::Or:
3650 case Instruction::Mul:
3654 case Instruction::Shl:
3658 case Instruction::LShr:
3659 case Instruction::AShr:
3663 case Instruction::SRem:
3667 case Instruction::UDiv:
3671 case Instruction::SDiv:
3675 case Instruction::Sub:
3679 case Instruction::Add:
3726 "This function only works with usub_sat and uadd_sat for now!");
3727 case Intrinsic::uadd_sat:
3730 case Intrinsic::usub_sat:
3753 SatValCheck ? Instruction::BinaryOps::Or : Instruction::BinaryOps::And;
3755 std::optional<ConstantRange> Combination;
3756 if (CombiningOp == Instruction::BinaryOps::Or)
3768 Combination->getEquivalentICmp(EquivPred, EquivInt, EquivOffset);
3786 case Intrinsic::uadd_sat:
3787 case Intrinsic::usub_sat:
3789 Pred, cast<SaturatingInst>(II),
C,
Builder))
3792 case Intrinsic::ctpop: {
3799 if (Cmp.isEquality())
3805 case Intrinsic::ctpop: {
3817 case Intrinsic::ctlz: {
3820 unsigned Num =
C.getLimitedValue();
3828 unsigned Num =
C.getLimitedValue();
3835 case Intrinsic::cttz: {
3857 case Intrinsic::ssub_sat:
3881 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3882 Constant *RHSC = dyn_cast<Constant>(Op1);
3888 case Instruction::GetElementPtr:
3891 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
3896 case Instruction::PHI:
3900 case Instruction::IntToPtr:
3909 case Instruction::Load:
3912 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
3928 auto SimplifyOp = [&](
Value *
Op,
bool SelectCondIsTrue) ->
Value * {
3932 SI->getCondition(), Pred,
Op,
RHS,
DL, SelectCondIsTrue))
3938 Value *Op1 = SimplifyOp(SI->getOperand(1),
true);
3940 CI = dyn_cast<ConstantInt>(Op1);
3942 Value *Op2 = SimplifyOp(SI->getOperand(2),
false);
3944 CI = dyn_cast<ConstantInt>(Op2);
3953 bool Transform =
false;
3956 else if (Op1 || Op2) {
3958 if (SI->hasOneUse())
3961 else if (CI && !CI->
isZero())
4058 Type *OpTy = M->getType();
4059 auto *VecC = dyn_cast<Constant>(M);
4060 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
4061 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
4062 Constant *SafeReplacementConstant =
nullptr;
4063 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
4064 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
4069 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
4073 return Builder.CreateICmp(DstPred,
X, M);
4089 const APInt *C0, *C1;
4106 const APInt &MaskedBits = *C0;
4107 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
4128 auto *XType =
X->getType();
4129 const unsigned XBitWidth = XType->getScalarSizeInBits();
4131 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
4162 !
I.getOperand(0)->hasOneUse())
4187 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
4188 "We did not look past any shifts while matching XShift though.");
4189 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
4196 auto XShiftOpcode = XShift->
getOpcode();
4197 if (XShiftOpcode == YShift->
getOpcode())
4200 Value *
X, *XShAmt, *
Y, *YShAmt;
4207 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
4209 if (!
match(
I.getOperand(0),
4235 unsigned MaximalPossibleTotalShiftAmount =
4238 APInt MaximalRepresentableShiftAmount =
4240 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
4244 auto *NewShAmt = dyn_cast_or_null<Constant>(