126 if (LI->
isVolatile() || !GV || !GV->isConstant() ||
127 !GV->hasDefinitiveInitializer())
131 TypeSize EltSize =
DL.getTypeStoreSize(EltTy);
147 if (!ConstOffset.
ult(Stride))
155 uint64_t ArrayElementCount =
161 enum { Overdefined = -3, Undefined = -2 };
170 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
174 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
182 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
187 uint64_t MagicBitvector = 0;
192 for (
unsigned i = 0, e = ArrayElementCount; i != e; ++i,
Offset += Stride) {
206 CompareRHS,
DL, &
TLI);
214 if (TrueRangeEnd == (
int)i - 1)
216 if (FalseRangeEnd == (
int)i - 1)
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)
290 auto MaskIdx = [&](
Value *Idx) {
294 Idx =
Builder.CreateAnd(Idx, Mask);
301 if (SecondTrueElement != Overdefined) {
304 if (FirstTrueElement == Undefined)
307 Value *FirstTrueIdx = ConstantInt::get(Idx->
getType(), FirstTrueElement);
310 if (SecondTrueElement == Undefined)
315 Value *SecondTrueIdx = ConstantInt::get(Idx->
getType(), SecondTrueElement);
317 return BinaryOperator::CreateOr(C1, C2);
322 if (SecondFalseElement != Overdefined) {
325 if (FirstFalseElement == Undefined)
328 Value *FirstFalseIdx = ConstantInt::get(Idx->
getType(), FirstFalseElement);
331 if (SecondFalseElement == Undefined)
336 Value *SecondFalseIdx =
337 ConstantInt::get(Idx->
getType(), SecondFalseElement);
339 return BinaryOperator::CreateAnd(C1, C2);
344 if (TrueRangeEnd != Overdefined) {
345 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
349 if (FirstTrueElement) {
351 Idx =
Builder.CreateAdd(Idx, Offs);
355 ConstantInt::get(Idx->
getType(), TrueRangeEnd - FirstTrueElement + 1);
360 if (FalseRangeEnd != Overdefined) {
361 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
364 if (FirstFalseElement) {
366 Idx =
Builder.CreateAdd(Idx, Offs);
370 ConstantInt::get(Idx->
getType(), FalseRangeEnd - FirstFalseElement);
383 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
386 Ty =
DL.getSmallestLegalIntType(
Init->getContext(), ArrayElementCount);
391 V =
Builder.CreateLShr(ConstantInt::get(Ty, MagicBitvector), V);
392 V =
Builder.CreateAnd(ConstantInt::get(Ty, 1), V);
691 if (
Base.Ptr == RHS && CanFold(
Base.LHSNW) && !
Base.isExpensive()) {
695 EmitGEPOffsets(
Base.LHSGEPs,
Base.LHSNW, IdxTy,
true);
703 RHS->getType()->getPointerAddressSpace())) {
734 if (GEPLHS->
getOperand(0) != GEPRHS->getOperand(0)) {
735 bool IndicesTheSame =
738 GEPRHS->getPointerOperand()->getType() &&
742 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
743 IndicesTheSame =
false;
749 if (IndicesTheSame &&
757 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
759 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
763 Value *LOffset = EmitGEPOffset(GEPLHS);
764 Value *ROffset = EmitGEPOffset(GEPRHS);
771 if (LHSIndexTy != RHSIndexTy) {
774 ROffset =
Builder.CreateTrunc(ROffset, LHSIndexTy);
776 LOffset =
Builder.CreateTrunc(LOffset, RHSIndexTy);
785 if (GEPLHS->
getOperand(0) == GEPRHS->getOperand(0) &&
789 unsigned NumDifferences = 0;
790 unsigned DiffOperand = 0;
791 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
792 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
794 Type *RHSType = GEPRHS->getOperand(i)->getType();
805 if (NumDifferences++)
810 if (NumDifferences == 0)
818 Value *RHSV = GEPRHS->getOperand(DiffOperand);
819 return NewICmp(NW, LHSV, RHSV);
823 if (
Base.Ptr && !
Base.isExpensive()) {
825 bool DoFold = CanFold(
Base.LHSNW &
Base.RHSNW);
827 if (!DoFold &&
Base.Ptr->getType()->isPointerTy()) {
831 unsigned BW =
DL.getIndexTypeSizeInBits(GEPLHS->
getType());
836 DL, LOff,
true) ==
Base.Ptr &&
837 RHS->stripAndAccumulateConstantOffsets(
838 DL, ROff,
true) ==
Base.Ptr)
850 return NewICmp(
Base.LHSNW &
Base.RHSNW, L, R);
1478 Type *SrcTy =
X->getType();
1480 SrcBits = SrcTy->getScalarSizeInBits();
1484 if (shouldChangeType(Trunc->
getType(), SrcTy)) {
1486 return new ICmpInst(Pred,
X, ConstantInt::get(SrcTy,
C.sext(SrcBits)));
1488 return new ICmpInst(Pred,
X, ConstantInt::get(SrcTy,
C.zext(SrcBits)));
1491 if (
C.isOne() &&
C.getBitWidth() > 1) {
1496 ConstantInt::get(V->getType(), 1));
1508 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1510 ConstantInt::get(SrcTy, DstBits - Pow2->
logBase2()));
1516 Pred,
Y, ConstantInt::get(SrcTy,
C.logBase2() - Pow2->
logBase2()));
1522 if (!SrcTy->isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1526 Constant *WideC = ConstantInt::get(SrcTy,
C.zext(SrcBits));
1535 if ((
Known.Zero |
Known.One).countl_one() >= SrcBits - DstBits) {
1537 APInt NewRHS =
C.zext(SrcBits);
1539 return new ICmpInst(Pred,
X, ConstantInt::get(SrcTy, NewRHS));
1551 DstBits == SrcBits - ShAmt) {
1729 if (!Shift || !Shift->
isShift())
1737 unsigned ShiftOpcode = Shift->
getOpcode();
1738 bool IsShl = ShiftOpcode == Instruction::Shl;
1741 APInt NewAndCst, NewCmpCst;
1742 bool AnyCmpCstBitsShiftedOut;
1743 if (ShiftOpcode == Instruction::Shl) {
1751 NewCmpCst = C1.
lshr(*C3);
1752 NewAndCst = C2.
lshr(*C3);
1753 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1754 }
else if (ShiftOpcode == Instruction::LShr) {
1759 NewCmpCst = C1.
shl(*C3);
1760 NewAndCst = C2.
shl(*C3);
1761 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1767 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1768 NewCmpCst = C1.
shl(*C3);
1769 NewAndCst = C2.
shl(*C3);
1770 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1771 if (NewAndCst.
ashr(*C3) != C2)
1775 if (AnyCmpCstBitsShiftedOut) {
1785 Shift->
getOperand(0), ConstantInt::get(
And->getType(), NewAndCst));
1786 return new ICmpInst(Cmp.getPredicate(), NewAnd,
1787 ConstantInt::get(
And->getType(), NewCmpCst));
1804 return new ICmpInst(Cmp.getPredicate(), NewAnd, Cmp.getOperand(1));
1818 return new TruncInst(
And->getOperand(0), Cmp.getType());
1829 ConstantInt::get(
X->getType(), ~*C2));
1834 ConstantInt::get(
X->getType(), -*C2));
1837 if (!
And->hasOneUse())
1840 if (Cmp.isEquality() && C1.
isZero()) {
1858 Constant *NegBOC = ConstantInt::get(
And->getType(), -NewC2);
1860 return new ICmpInst(NewPred,
X, NegBOC);
1878 if (!Cmp.getType()->isVectorTy()) {
1879 Type *WideType = W->getType();
1881 Constant *ZextC1 = ConstantInt::get(WideType, C1.
zext(WideScalarBits));
1882 Constant *ZextC2 = ConstantInt::get(WideType, C2->
zext(WideScalarBits));
1884 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1895 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1902 unsigned UsesRemoved = 0;
1903 if (
And->hasOneUse())
1905 if (
Or->hasOneUse())
1912 if (UsesRemoved >= RequireUsesRemoved) {
1916 One,
Or->getName());
1918 return new ICmpInst(Cmp.getPredicate(), NewAnd, Cmp.getOperand(1));
1932 if (!Cmp.getParent()->getParent()->hasFnAttribute(
1933 Attribute::NoImplicitFloat) &&
1936 Type *FPType = V->getType()->getScalarType();
1937 if (FPType->isIEEELikeFPTy() && (C1.
isZero() || C1 == *C2)) {
1938 APInt ExponentMask =
1940 if (*C2 == ExponentMask) {
1941 unsigned Mask = C1.
isZero()
2089 while (!WorkList.
empty()) {
2090 auto MatchOrOperatorArgument = [&](
Value *OrOperatorArgument) {
2093 if (
match(OrOperatorArgument,
2099 if (
match(OrOperatorArgument,
2109 Value *OrOperatorLhs, *OrOperatorRhs;
2111 if (!
match(CurrentValue,
2116 MatchOrOperatorArgument(OrOperatorRhs);
2117 MatchOrOperatorArgument(OrOperatorLhs);
2122 Value *LhsCmp = Builder.CreateICmp(Pred, CmpValues.
rbegin()->first,
2123 CmpValues.
rbegin()->second);
2125 for (
auto It = CmpValues.
rbegin() + 1; It != CmpValues.
rend(); ++It) {
2126 Value *RhsCmp = Builder.CreateICmp(Pred, It->first, It->second);
2127 LhsCmp = Builder.CreateBinOp(BOpc, LhsCmp, RhsCmp);
2244 if (
X ==
Mul->getOperand(1) && !Cmp.isSigned()) {
2246 bool IsSqr =
C == R * R;
2249 if (Cmp.isEquality() &&
2250 (
Mul->hasNoUnsignedWrap() || (
Mul->hasNoSignedWrap() &&
C.isZero()))) {
2258 return new ICmpInst(Pred,
X, ConstantInt::get(MulTy, R));
2263 if (
Mul->hasNoUnsignedWrap()) {
2266 return new ICmpInst(Pred,
X, ConstantInt::get(MulTy, R));
2280 return new ICmpInst(Cmp.getStrictPredicate(),
X,
2281 ConstantInt::get(MulTy, R));
2304 if (Cmp.isEquality()) {
2306 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2307 Constant *NewC = ConstantInt::get(MulTy,
C.sdiv(*MulC));
2315 if (
C.urem(*MulC).isZero()) {
2318 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2319 Constant *NewC = ConstantInt::get(MulTy,
C.udiv(*MulC));
2332 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2338 NewC = ConstantInt::get(
2342 "Unexpected predicate");
2343 NewC = ConstantInt::get(
2348 NewC = ConstantInt::get(
2352 "Unexpected predicate");
2353 NewC = ConstantInt::get(
2358 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2415 const APInt *ShiftVal;
2445 const APInt *ShiftAmt;
2451 unsigned TypeBits =
C.getBitWidth();
2452 if (ShiftAmt->
uge(TypeBits))
2464 APInt ShiftedC =
C.ashr(*ShiftAmt);
2465 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2468 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2469 APInt ShiftedC =
C.ashr(*ShiftAmt);
2470 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2477 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2478 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2479 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2489 APInt ShiftedC =
C.lshr(*ShiftAmt);
2490 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2493 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2494 APInt ShiftedC =
C.lshr(*ShiftAmt);
2495 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2502 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2503 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2504 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2508 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2514 Constant *LShrC = ConstantInt::get(ShType,
C.lshr(*ShiftAmt));
2519 bool TrueIfSigned =
false;
2531 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2533 if ((
C + 1).isPowerOf2() &&
2541 if (
C.isPowerOf2() &&
2571 Pred, ConstantInt::get(ShType->
getContext(),
C))) {
2572 CmpPred = FlippedStrictness->first;
2580 ConstantInt::get(TruncTy, RHSC.
ashr(*ShiftAmt).
trunc(TypeBits - Amt));
2582 Builder.CreateTrunc(
X, TruncTy,
"",
false,
2599 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2600 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2602 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2603 const APInt *ShiftValC;
2605 if (Cmp.isEquality())
2623 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2624 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2626 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2634 const APInt *ShiftAmtC;
2640 unsigned TypeBits =
C.getBitWidth();
2642 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2645 bool IsExact = Shr->
isExact();
2653 (
C - 1).isPowerOf2() &&
C.countLeadingZeros() > ShAmtVal) {
2659 APInt ShiftedC = (
C - 1).shl(ShAmtVal) + 1;
2660 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2666 APInt ShiftedC =
C.shl(ShAmtVal);
2667 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2668 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2672 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2673 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2674 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2675 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2681 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2682 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2683 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2684 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2691 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2701 }
else if (!IsAShr) {
2705 APInt ShiftedC =
C.shl(ShAmtVal);
2706 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2707 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2711 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2712 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2713 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2717 if (!Cmp.isEquality())
2725 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2726 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2727 "Expected icmp+shr simplify did not occur.");
2732 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy,
C << ShAmtVal));
2738 Constant *Mask = ConstantInt::get(ShrTy, Val);
2740 return new ICmpInst(Pred,
And, ConstantInt::get(ShrTy,
C << ShAmtVal));
2868 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2878 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2879 (!DivIsSigned ||
C.isMinSignedValue())) {
2880 Value *XBig =
Builder.CreateICmp(Pred,
X, ConstantInt::get(Ty,
C));
2881 Value *YOne =
Builder.CreateICmp(Pred,
Y, ConstantInt::get(Ty, 1));
2907 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned()) {
2911 DivIsSigned =
false;
2930 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2943 int LoOverflow = 0, HiOverflow = 0;
2944 APInt LoBound, HiBound;
2949 HiOverflow = LoOverflow = ProdOV;
2958 LoBound = -(RangeSize - 1);
2959 HiBound = RangeSize;
2960 }
else if (
C.isStrictlyPositive()) {
2962 HiOverflow = LoOverflow = ProdOV;
2968 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2970 APInt DivNeg = -RangeSize;
2971 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2979 LoBound = RangeSize + 1;
2980 HiBound = -RangeSize;
2981 if (HiBound == *C2) {
2985 }
else if (
C.isStrictlyPositive()) {
2988 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2994 LoOverflow = HiOverflow = ProdOV;
3007 if (LoOverflow && HiOverflow)
3011 X, ConstantInt::get(Ty, LoBound));
3014 X, ConstantInt::get(Ty, HiBound));
3018 if (LoOverflow && HiOverflow)
3022 X, ConstantInt::get(Ty, LoBound));
3025 X, ConstantInt::get(Ty, HiBound));
3030 if (LoOverflow == +1)
3032 if (LoOverflow == -1)
3034 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, LoBound));
3037 if (HiOverflow == +1)
3039 if (HiOverflow == -1)
3149 auto FoldConstant = [&](
bool Val) {
3150 Constant *Res = Val ? Builder.getTrue() : Builder.getFalse();
3157 switch (
Table.to_ulong()) {
3159 return FoldConstant(
false);
3161 return HasOneUse ? Builder.CreateNot(Builder.CreateOr(Op0, Op1)) :
nullptr;
3163 return HasOneUse ? Builder.CreateAnd(Builder.CreateNot(Op0), Op1) :
nullptr;
3165 return Builder.CreateNot(Op0);
3167 return HasOneUse ? Builder.CreateAnd(Op0, Builder.CreateNot(Op1)) :
nullptr;
3169 return Builder.CreateNot(Op1);
3171 return Builder.CreateXor(Op0, Op1);
3173 return HasOneUse ? Builder.CreateNot(Builder.CreateAnd(Op0, Op1)) :
nullptr;
3175 return Builder.CreateAnd(Op0, Op1);
3177 return HasOneUse ? Builder.CreateNot(Builder.CreateXor(Op0, Op1)) :
nullptr;
3181 return HasOneUse ? Builder.CreateOr(Builder.CreateNot(Op0), Op1) :
nullptr;
3185 return HasOneUse ? Builder.CreateOr(Op0, Builder.CreateNot(Op1)) :
nullptr;
3187 return Builder.CreateOr(Op0, Op1);
3189 return FoldConstant(
true);
3244 const APInt *ShAmtC;
3252 return new ICmpInst(Pred,
A, ConstantInt::get(
A->getType(),
C));
3264 if (
Add->hasNoUnsignedWrap() &&
3267 APInt NewC =
C.usub_ov(*C2, Overflow);
3271 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, NewC));
3276 if (
Add->hasNoSignedWrap() &&
3279 APInt NewC =
C.ssub_ov(*C2, Overflow);
3283 return new ICmpInst(ChosenPred,
X, ConstantInt::get(Ty, NewC));
3287 C.isNonNegative() && (
C - *C2).isNonNegative() &&
3290 .isAllNonNegative())
3292 ConstantInt::get(Ty,
C - *C2));
3297 if (Cmp.isSigned()) {
3298 if (
Lower.isSignMask())
3300 if (
Upper.isSignMask())
3303 if (
Lower.isMinValue())
3305 if (
Upper.isMinValue())
3338 if (!
Add->hasOneUse())
3353 ConstantInt::get(Ty,
C * 2));
3367 Builder.CreateAdd(
X, ConstantInt::get(Ty, *C2 -
C - 1)),
3368 ConstantInt::get(Ty, ~
C));
3373 Type *NewCmpTy = V->getType();
3375 if (shouldChangeType(Ty, NewCmpTy)) {
3386 :
Builder.CreateAdd(V, ConstantInt::get(NewCmpTy, EquivOffset)),
3387 ConstantInt::get(NewCmpTy, EquivInt));
3501 Value *Op1 = Cmp.getOperand(1);
3502 Value *BCSrcOp = Bitcast->getOperand(0);
3503 Type *SrcType = Bitcast->getSrcTy();
3504 Type *DstType = Bitcast->getType();
3508 if (SrcType->isVectorTy() == DstType->isVectorTy() &&
3509 SrcType->getScalarSizeInBits() == DstType->getScalarSizeInBits()) {
3524 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(), 1));
3551 Type *XType =
X->getType();
3554 if (!(XType->
isPPC_FP128Ty() || SrcType->isPPC_FP128Ty())) {
3569 Type *FPType = SrcType->getScalarType();
3570 if (!Cmp.getParent()->getParent()->hasFnAttribute(
3571 Attribute::NoImplicitFloat) &&
3572 Cmp.isEquality() && FPType->isIEEELikeFPTy()) {
3578 Builder.createIsFPClass(BCSrcOp, Mask));
3585 if (!
match(Cmp.getOperand(1),
m_APInt(
C)) || !DstType->isIntegerTy() ||
3586 !SrcType->isIntOrIntVectorTy())
3596 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse()) {
3597 if (
Value *NotBCSrcOp =
3599 Value *Cast =
Builder.CreateBitCast(NotBCSrcOp, DstType);
3608 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3611 Type *NewType =
Builder.getIntNTy(VecTy->getPrimitiveSizeInBits());
3631 if (
C->isSplat(EltTy->getBitWidth())) {
3637 Value *Extract =
Builder.CreateExtractElement(Vec, Mask[0]);
3638 Value *NewC = ConstantInt::get(EltTy,
C->trunc(EltTy->getBitWidth()));
3639 return new ICmpInst(Pred, Extract, NewC);
3744 if (!Cmp.isEquality())
3753 case Instruction::SRem:
3764 case Instruction::Add: {
3771 }
else if (
C.isZero()) {
3774 if (
Value *NegVal = dyn_castNegVal(BOp1))
3775 return new ICmpInst(Pred, BOp0, NegVal);
3776 if (
Value *NegVal = dyn_castNegVal(BOp0))
3777 return new ICmpInst(Pred, NegVal, BOp1);
3786 return new ICmpInst(Pred, BOp0, Neg);
3791 case Instruction::Xor:
3796 }
else if (
C.isZero()) {
3798 return new ICmpInst(Pred, BOp0, BOp1);
3801 case Instruction::Or: {
3822 Cond->getType() == Cmp.getType()) {
3860 case Instruction::UDiv:
3861 case Instruction::SDiv:
3871 return new ICmpInst(Pred, BOp0, BOp1);
3874 Instruction::Mul, BO->
getOpcode() == Instruction::SDiv, BOp1,
3875 Cmp.getOperand(1), BO);
3879 return new ICmpInst(Pred, YC, BOp0);
3883 if (BO->
getOpcode() == Instruction::UDiv &&
C.isZero()) {
3886 return new ICmpInst(NewPred, BOp1, BOp0);
4046 assert(Cmp.isEquality());
4049 Value *Op0 = Cmp.getOperand(0);
4050 Value *Op1 = Cmp.getOperand(1);
4053 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
4056 switch (IIOp0->getIntrinsicID()) {
4057 case Intrinsic::bswap:
4058 case Intrinsic::bitreverse:
4061 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
4062 case Intrinsic::fshl:
4063 case Intrinsic::fshr: {
4066 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
4068 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
4070 if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
4071 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
4077 unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
4082 Builder.CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
4083 Value *CombinedRotate = Builder.CreateIntrinsic(
4084 Op0->
getType(), IIOp0->getIntrinsicID(),
4085 {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
4086 return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
4873 !
I.getOperand(0)->hasOneUse())
4898 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
4899 "We did not look past any shifts while matching XShift though.");
4900 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
4907 auto XShiftOpcode = XShift->
getOpcode();
4908 if (XShiftOpcode == YShift->
getOpcode())
4911 Value *
X, *XShAmt, *
Y, *YShAmt;
4920 if (!
match(
I.getOperand(0),
4946 unsigned MaximalPossibleTotalShiftAmount =
4949 APInt MaximalRepresentableShiftAmount =
4951 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
4960 if (NewShAmt->getType() != WidestTy) {
4970 if (!
match(NewShAmt,
4972 APInt(WidestBitWidth, WidestBitWidth))))
4977 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
4983 ? NewShAmt->getSplatValue()
4986 if (NewShAmtSplat &&
4994 unsigned MinLeadZero =
Known.countMinLeadingZeros();
4996 unsigned MaxActiveBits =
Known.getBitWidth() - MinLeadZero;
4997 if (MaxActiveBits <= 1)
5005 unsigned MinLeadZero =
Known.countMinLeadingZeros();
5007 unsigned MaxActiveBits =
Known.getBitWidth() - MinLeadZero;
5008 if (MaxActiveBits <= 1)
5011 if (NewShAmtSplat) {
5014 if (AdjNewShAmt.
ule(MinLeadZero))
5025 X = Builder.CreateZExt(
X, WidestTy);
5026 Y = Builder.CreateZExt(
Y, WidestTy);
5028 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
5029 ? Builder.CreateLShr(
X, NewShAmt)
5030 : Builder.CreateShl(
X, NewShAmt);
5031 Value *
T1 = Builder.CreateAnd(T0,
Y);
5032 return Builder.CreateICmp(
I.getPredicate(),
T1,
5303 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
5371 return new ICmpInst(NewPred, Op1, Zero);
5380 return new ICmpInst(NewPred, Op0, Zero);
5384 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
5385 bool Op0HasNUW =
false, Op1HasNUW =
false;
5386 bool Op0HasNSW =
false, Op1HasNSW =
false;
5390 bool &HasNSW,
bool &HasNUW) ->
bool {
5397 }
else if (BO.
getOpcode() == Instruction::Or) {
5405 Value *
A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr;
5409 NoOp0WrapProblem = hasNoWrapProblem(*BO0, Pred, Op0HasNSW, Op0HasNUW);
5413 NoOp1WrapProblem = hasNoWrapProblem(*BO1, Pred, Op1HasNSW, Op1HasNUW);
5418 if ((
A == Op1 ||
B == Op1) && NoOp0WrapProblem)
5424 if ((
C == Op0 ||
D == Op0) && NoOp1WrapProblem)
5429 if (
A &&
C && (
A ==
C ||
A ==
D ||
B ==
C ||
B ==
D) && NoOp0WrapProblem &&
5437 }
else if (
A ==
D) {
5441 }
else if (
B ==
C) {
5458 bool IsNegative) ->
bool {
5459 const APInt *OffsetC;
5471 if (!
C.isStrictlyPositive())
5492 if (
A && NoOp0WrapProblem &&
5493 ShareCommonDivisor(
A, Op1,
B,
5504 if (
C && NoOp1WrapProblem &&
5505 ShareCommonDivisor(Op0,
C,
D,
5518 if (
A &&
C && NoOp0WrapProblem && NoOp1WrapProblem &&
5520 const APInt *AP1, *AP2;
5528 if (AP1Abs.
uge(AP2Abs)) {
5529 APInt Diff = *AP1 - *AP2;
5532 A, C3,
"", Op0HasNUW && Diff.
ule(*AP1), Op0HasNSW);
5535 APInt Diff = *AP2 - *AP1;
5538 C, C3,
"", Op1HasNUW && Diff.
ule(*AP2), Op1HasNSW);
5557 if (BO0 && BO0->
getOpcode() == Instruction::Sub) {
5561 if (BO1 && BO1->
getOpcode() == Instruction::Sub) {
5567 if (
A == Op1 && NoOp0WrapProblem)
5570 if (
C == Op0 && NoOp1WrapProblem)
5590 if (
B &&
D &&
B ==
D && NoOp0WrapProblem && NoOp1WrapProblem)
5594 if (
A &&
C &&
A ==
C && NoOp0WrapProblem && NoOp1WrapProblem)
5602 if (RHSC->isNotMinSignedValue())
5603 return new ICmpInst(
I.getSwappedPredicate(),
X,
5621 if (Op0HasNSW && Op1HasNSW) {
5628 SQ.getWithInstruction(&
I));
5633 SQ.getWithInstruction(&
I));
5634 if (GreaterThan &&
match(GreaterThan,
m_One()))
5641 if (((Op0HasNSW && Op1HasNSW) || (Op0HasNUW && Op1HasNUW)) &&
5653 if (NonZero && BO0 && BO1 && Op0HasNSW && Op1HasNSW)
5660 if (NonZero && BO0 && BO1 && Op0HasNUW && Op1HasNUW)
5671 else if (BO1 && BO1->
getOpcode() == Instruction::SRem &&
5701 case Instruction::Add:
5702 case Instruction::Sub:
5703 case Instruction::Xor: {
5710 if (
C->isSignMask()) {
5716 if (BO0->
getOpcode() == Instruction::Xor &&
C->isMaxSignedValue()) {
5718 NewPred =
I.getSwappedPredicate(NewPred);
5724 case Instruction::Mul: {
5725 if (!
I.isEquality())
5733 if (
unsigned TZs =
C->countr_zero()) {
5739 return new ICmpInst(Pred, And1, And2);
5744 case Instruction::UDiv:
5745 case Instruction::LShr:
5750 case Instruction::SDiv:
5756 case Instruction::AShr:
5761 case Instruction::Shl: {
5762 bool NUW = Op0HasNUW && Op1HasNUW;
5763 bool NSW = Op0HasNSW && Op1HasNSW;
5766 if (!NSW &&
I.isSigned())
6052 bool AllowRecursion) {
6058 case Instruction::Add:
6059 Offsets.emplace_back(Instruction::Sub, Inst->
getOperand(1));
6060 Offsets.emplace_back(Instruction::Sub, Inst->
getOperand(0));
6062 case Instruction::Sub:
6063 Offsets.emplace_back(Instruction::Add, Inst->
getOperand(1));
6065 case Instruction::Xor:
6066 Offsets.emplace_back(Instruction::Xor, Inst->
getOperand(1));
6067 Offsets.emplace_back(Instruction::Xor, Inst->
getOperand(0));
6069 case Instruction::Shl:
6071 Offsets.emplace_back(Instruction::AShr, Inst->
getOperand(1));
6073 Offsets.emplace_back(Instruction::LShr, Inst->
getOperand(1));
6075 case Instruction::Select:
6076 if (AllowRecursion) {
6124 assert(
I.isEquality() &&
"Expected an equality icmp");
6125 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6136 case Instruction::AShr: {
6137 const APInt *CV, *CRHS;
6139 CV->
ashr(*CRHS).
shl(*CRHS) == *CV) &&
6145 case Instruction::LShr: {
6146 const APInt *CV, *CRHS;
6148 CV->
lshr(*CRHS).
shl(*CRHS) == *CV) &&
6167 auto ApplyOffset = [&](
Value *V,
unsigned BinOpc,
6170 if (!Sel->hasOneUse())
6172 Value *TrueVal = ApplyOffsetImpl(Sel->getTrueValue(), BinOpc,
RHS);
6175 Value *FalseVal = ApplyOffsetImpl(Sel->getFalseValue(), BinOpc,
RHS);
6180 if (
Value *Simplified = ApplyOffsetImpl(V, BinOpc,
RHS))
6185 for (
auto [BinOp,
RHS] : OffsetOps) {
6186 auto BinOpc =
static_cast<unsigned>(BinOp);
6188 auto Op0Result = ApplyOffset(Op0, BinOpc,
RHS);
6189 if (!Op0Result.isValid())
6191 auto Op1Result = ApplyOffset(Op1, BinOpc,
RHS);
6192 if (!Op1Result.isValid())
6195 Value *NewLHS = Op0Result.materialize(Builder);
6196 Value *NewRHS = Op1Result.materialize(Builder);
6197 return new ICmpInst(
I.getPredicate(), NewLHS, NewRHS);
6204 if (!
I.isEquality())
6207 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6211 if (
A == Op1 ||
B == Op1) {
6212 Value *OtherVal =
A == Op1 ?
B :
A;
6240 Value *OtherVal =
A == Op0 ?
B :
A;
6247 Value *
X =
nullptr, *
Y =
nullptr, *Z =
nullptr;
6253 }
else if (
A ==
D) {
6257 }
else if (
B ==
C) {
6261 }
else if (
B ==
D) {
6271 const APInt *C0, *C1;
6273 (*C0 ^ *C1).isNegatedPowerOf2();
6279 int(Op0->
hasOneUse()) + int(Op1->hasOneUse()) +
6281 if (XorIsNegP2 || UseCnt >= 2) {
6284 Op1 =
Builder.CreateAnd(Op1, Z);
6304 (Op0->
hasOneUse() || Op1->hasOneUse())) {
6309 MaskC->
countr_one() ==
A->getType()->getScalarSizeInBits())
6315 const APInt *AP1, *AP2;
6324 if (ShAmt < TypeBits && ShAmt != 0) {
6329 return new ICmpInst(NewPred,
Xor, ConstantInt::get(
A->getType(), CmpVal));
6339 if (ShAmt < TypeBits && ShAmt != 0) {
6359 if (ShAmt < ASize) {
6382 A->getType()->getScalarSizeInBits() ==
BitWidth * 2 &&
6383 (
I.getOperand(0)->hasOneUse() ||
I.getOperand(1)->hasOneUse())) {
6388 Add, ConstantInt::get(
A->getType(),
C.shl(1)));
6415 Builder.CreateIntrinsic(Op0->
getType(), Intrinsic::fshl, {A, A, B}));
6430 std::optional<bool> IsZero = std::nullopt;
6506 bool IsSignedExt = CastOp0->getOpcode() == Instruction::SExt;
6507 bool IsSignedCmp = ICmp.
isSigned();
6515 if (IsZext0 != IsZext1) {
6520 if (ICmp.
isEquality() &&
X->getType()->isIntOrIntVectorTy(1) &&
6521 Y->getType()->isIntOrIntVectorTy(1))
6531 bool IsNonNeg0 = NonNegInst0 && NonNegInst0->hasNonNeg();
6532 bool IsNonNeg1 = NonNegInst1 && NonNegInst1->hasNonNeg();
6534 if ((IsZext0 && IsNonNeg0) || (IsZext1 && IsNonNeg1))
6541 Type *XTy =
X->getType(), *YTy =
Y->getType();
6548 IsSignedExt ? Instruction::SExt : Instruction::ZExt;
6550 X =
Builder.CreateCast(CastOpcode,
X, YTy);
6552 Y =
Builder.CreateCast(CastOpcode,
Y, XTy);
6564 if (IsSignedCmp && IsSignedExt)
6577 Type *SrcTy = CastOp0->getSrcTy();
6585 if (IsSignedExt && IsSignedCmp)
6616 Value *SimplifiedOp0 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(0));
6617 Value *SimplifiedOp1 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(1));
6618 if (SimplifiedOp0 || SimplifiedOp1)
6620 SimplifiedOp0 ? SimplifiedOp0 : ICmp.
getOperand(0),
6621 SimplifiedOp1 ? SimplifiedOp1 : ICmp.
getOperand(1));
6630 Value *Op0Src = CastOp0->getOperand(0);
6631 Type *SrcTy = CastOp0->getSrcTy();
6632 Type *DestTy = CastOp0->getDestTy();
6636 auto CompatibleSizes = [&](
Type *PtrTy,
Type *IntTy) {
6637 unsigned IntWidth = IntTy->getScalarType()->getIntegerBitWidth();
6638 unsigned IndexWidth =
DL.getAddressSizeInBits(PtrTy);
6639 unsigned PtrWidth =
DL.getPointerTypeSizeInBits(PtrTy);
6642 return IntWidth == IndexWidth && IndexWidth == PtrWidth;
6646 Value *NewOp1 =
nullptr;
6648 NewOp1 = PtrToIntOp1->getOperand(0);
6651 NewOp1 = PtrToAddrOp1->getOperand(0);
6658 if ((!HasPtrToInt || CompatibleSizes(SrcTy, DestTy)) &&
6664 if (CastOp0->getOpcode() == Instruction::IntToPtr &&
6665 CompatibleSizes(DestTy, SrcTy)) {
6666 Value *NewOp1 =
nullptr;
6668 Value *IntSrc = IntToPtrOp1->getOperand(0);
6670 NewOp1 = IntToPtrOp1->getOperand(0);
6788 const APInt *OtherVal,
6798 assert(MulInstr->getOpcode() == Instruction::Mul);
6802 assert(
LHS->getOpcode() == Instruction::ZExt);
6803 assert(
RHS->getOpcode() == Instruction::ZExt);
6807 Type *TyA =
A->getType(), *TyB =
B->getType();
6809 WidthB = TyB->getPrimitiveSizeInBits();
6812 if (WidthB > WidthA) {
6829 unsigned TruncWidth = TI->getType()->getPrimitiveSizeInBits();
6830 if (TruncWidth > MulWidth)
6834 if (BO->getOpcode() != Instruction::And)
6837 const APInt &CVal = CI->getValue();
6853 switch (
I.getPredicate()) {
6860 if (MaxVal.
eq(*OtherVal))
6870 if (MaxVal.
eq(*OtherVal))
6884 if (WidthA < MulWidth)
6885 MulA = Builder.CreateZExt(
A, MulType);
6886 if (WidthB < MulWidth)
6887 MulB = Builder.CreateZExt(
B, MulType);
6889 Builder.CreateIntrinsic(Intrinsic::umul_with_overflow, MulType,
6890 {MulA, MulB},
nullptr,
"umul");
6897 Value *
Mul = Builder.CreateExtractValue(
Call, 0,
"umul.value");
6902 if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
6907 assert(BO->getOpcode() == Instruction::And);
6911 Value *ShortAnd = Builder.CreateAnd(
Mul, ShortMask);
6912 Value *Zext = Builder.CreateZExt(ShortAnd, BO->
getType());
6924 Value *Res = Builder.CreateExtractValue(
Call, 1);
7077 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7082 unsigned BitWidth = Ty->isIntOrIntVectorTy()
7083 ? Ty->getScalarSizeInBits()
7084 :
DL.getPointerTypeSizeInBits(Ty->getScalarType());
7108 if (
I.hasSameSign() &&
I.isUnsigned()) {
7110 if (To.isNegative() || To.isNonNegative())
7115 To.makeNonNegative();
7117 PropagateSignBit(Op0Known, Op1Known);
7118 PropagateSignBit(Op1Known, Op0Known);
7153 if (!Cmp.hasOneUse())
7162 if (!isMinMaxCmp(
I)) {
7167 if (Op1Min == Op0Max)
7172 if (*CmpC == Op0Min + 1)
7174 ConstantInt::get(Op1->getType(), *CmpC - 1));
7184 if (Op1Max == Op0Min)
7189 if (*CmpC == Op0Max - 1)
7191 ConstantInt::get(Op1->getType(), *CmpC + 1));
7201 if (Op1Min == Op0Max)
7205 if (*CmpC == Op0Min + 1)
7207 ConstantInt::get(Op1->getType(), *CmpC - 1));
7212 if (Op1Max == Op0Min)
7216 if (*CmpC == Op0Max - 1)
7218 ConstantInt::get(Op1->getType(), *CmpC + 1));
7235 APInt Op0KnownZeroInverted = ~Op0Known.Zero;
7238 Value *LHS =
nullptr;
7241 *LHSC != Op0KnownZeroInverted)
7247 Type *XTy =
X->getType();
7249 APInt C2 = Op0KnownZeroInverted;
7250 APInt C2Pow2 = (C2 & ~(*C1 - 1)) + *C1;
7256 auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
7266 (Op0Known & Op1Known) == Op0Known)
7272 if (Op1Min == Op0Max)
7276 if (Op1Max == Op0Min)
7280 if (Op1Min == Op0Max)
7284 if (Op1Max == Op0Min)
7292 if ((
I.isSigned() || (
I.isUnsigned() && !
I.hasSameSign())) &&
7295 I.setPredicate(
I.getUnsignedPredicate());
7914 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7921 if (Op0Cplxity < Op1Cplxity) {
7936 if (
Value *V = dyn_castNegVal(SelectTrue)) {
7937 if (V == SelectFalse)
7939 }
else if (
Value *V = dyn_castNegVal(SelectFalse)) {
7940 if (V == SelectTrue)
8000 if (
C->isNonNegative())
8004 ConstantInt::get(
X->getType(), ~*
C));
8010 if (
C->isNonNegative())
8014 ConstantInt::get(
X->getType(), ~*
C));
8070 if (
I.isCommutative()) {
8071 if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
8100 (Op0->
hasOneUse() || Op1->hasOneUse())) {
8105 Cond, Res, NewICMP,
"",
nullptr,
8112 Cond, NewICMP, Res,
"",
nullptr,
8128 bool I0NUW = I0->hasNoUnsignedWrap();
8129 bool I1NUW = I1->hasNoUnsignedWrap();
8130 bool I0NSW = I0->hasNoSignedWrap();
8131 bool I1NSW = I1->hasNoSignedWrap();
8135 ((I0NUW || I0NSW) && (I1NUW || I1NSW)))) {
8137 ConstantInt::get(Op0->
getType(), 0));
8144 assert(Op1->getType()->isPointerTy() &&
8145 "Comparing pointer with non-pointer?");
8174 bool ConsumesOp0, ConsumesOp1;
8177 (ConsumesOp0 || ConsumesOp1)) {
8180 assert(InvOp0 && InvOp1 &&
8181 "Mismatch between isFreeToInvert and getFreelyInverted");
8182 return new ICmpInst(
I.getSwappedPredicate(), InvOp0, InvOp1);
8194 if (AddI->
getOpcode() == Instruction::Add &&
8195 OptimizeOverflowCheck(Instruction::Add,
false,
X,
Y, *AddI,
8196 Result, Overflow)) {
8214 if ((
I.isUnsigned() ||
I.isEquality()) &&
8217 Y->getType()->getScalarSizeInBits() == 1 &&
8218 (Op0->
hasOneUse() || Op1->hasOneUse())) {
8225 unsigned ShiftOpc = ShiftI->
getOpcode();
8226 if ((ExtOpc == Instruction::ZExt && ShiftOpc == Instruction::LShr) ||
8227 (ExtOpc == Instruction::SExt && ShiftOpc == Instruction::AShr)) {
8261 if (EVI->getIndices()[0] == 0 && ACXI->getCompareOperand() == Op1 &&
8268 if (
I.getType()->isVectorTy())
8280 const APInt *C1, *C2;
8287 Type *InputTy =
A->getType();
8294 TruncC1.
setBit(InputBitWidth - 1);
8298 ConstantInt::get(InputTy, C2->
trunc(InputBitWidth)));