30using namespace PatternMatch;
32#define DEBUG_TYPE "instcombine"
41 const APInt &In2,
bool IsSigned =
false) {
44 Result = In1.
sadd_ov(In2, Overflow);
46 Result = In1.
uadd_ov(In2, Overflow);
54 const APInt &In2,
bool IsSigned =
false) {
57 Result = In1.
ssub_ov(In2, Overflow);
59 Result = In1.
usub_ov(In2, Overflow);
67 for (
auto *U :
I.users())
68 if (isa<BranchInst>(U))
78 if (!ICmpInst::isSigned(Pred))
85 if (Pred == ICmpInst::ICMP_SLT) {
86 Pred = ICmpInst::ICMP_SLE;
89 }
else if (
C.isAllOnes()) {
90 if (Pred == ICmpInst::ICMP_SGT) {
91 Pred = ICmpInst::ICMP_SGE;
110 if (
LI->isVolatile() ||
LI->getType() !=
GEP->getResultElementType() ||
116 if (!isa<ConstantArray>(
Init) && !isa<ConstantDataArray>(
Init))
119 uint64_t ArrayElementCount =
Init->getType()->getArrayNumElements();
128 if (
GEP->getNumOperands() < 3 ||
129 !isa<ConstantInt>(
GEP->getOperand(1)) ||
130 !cast<ConstantInt>(
GEP->getOperand(1))->isZero() ||
131 isa<Constant>(
GEP->getOperand(2)))
139 Type *EltTy =
Init->getType()->getArrayElementType();
140 for (
unsigned i = 3, e =
GEP->getNumOperands(); i != e; ++i) {
142 if (!
Idx)
return nullptr;
145 if ((
unsigned)IdxVal != IdxVal)
return nullptr;
147 if (
StructType *STy = dyn_cast<StructType>(EltTy))
148 EltTy = STy->getElementType(IdxVal);
149 else if (
ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
150 if (IdxVal >= ATy->getNumElements())
return nullptr;
151 EltTy = ATy->getElementType();
159 enum { Overdefined = -3, Undefined = -2 };
168 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
172 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
180 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
189 for (
unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
191 if (!Elt)
return nullptr;
194 if (!LaterIndices.
empty()) {
205 CompareRHS,
DL, &
TLI);
207 if (isa<UndefValue>(
C)) {
210 if (TrueRangeEnd == (
int)i-1)
212 if (FalseRangeEnd == (
int)i-1)
219 if (!isa<ConstantInt>(
C))
return nullptr;
223 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
228 if (FirstTrueElement == Undefined)
229 FirstTrueElement = TrueRangeEnd = i;
232 if (SecondTrueElement == Undefined)
233 SecondTrueElement = i;
235 SecondTrueElement = Overdefined;
238 if (TrueRangeEnd == (
int)i-1)
241 TrueRangeEnd = Overdefined;
245 if (FirstFalseElement == Undefined)
246 FirstFalseElement = FalseRangeEnd = i;
249 if (SecondFalseElement == Undefined)
250 SecondFalseElement = i;
252 SecondFalseElement = Overdefined;
255 if (FalseRangeEnd == (
int)i-1)
258 FalseRangeEnd = Overdefined;
263 if (i < 64 && IsTrueForElt)
264 MagicBitvector |= 1ULL << i;
269 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
270 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
271 FalseRangeEnd == Overdefined)
282 if (!
GEP->isInBounds()) {
285 if (
Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > PtrSize)
296 unsigned ElementSize =
309 if (SecondTrueElement != Overdefined) {
312 if (FirstTrueElement == Undefined)
318 if (SecondTrueElement == Undefined)
325 return BinaryOperator::CreateOr(C1, C2);
330 if (SecondFalseElement != Overdefined) {
333 if (FirstFalseElement == Undefined)
339 if (SecondFalseElement == Undefined)
346 return BinaryOperator::CreateAnd(C1, C2);
351 if (TrueRangeEnd != Overdefined) {
352 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
356 if (FirstTrueElement) {
362 TrueRangeEnd-FirstTrueElement+1);
367 if (FalseRangeEnd != Overdefined) {
368 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
371 if (FirstFalseElement) {
377 FalseRangeEnd-FirstFalseElement);
390 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
424 while (!WorkList.
empty()) {
427 while (!WorkList.
empty()) {
428 if (Explored.
size() >= 100)
438 if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
439 !isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
444 if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
445 auto *CI = cast<CastInst>(V);
446 if (!CI->isNoopCast(
DL))
449 if (!Explored.
contains(CI->getOperand(0)))
453 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
457 if (
GEP->getNumIndices() != 1 || !
GEP->isInBounds() ||
458 GEP->getSourceElementType() != ElemTy)
465 if (WorkList.
back() == V) {
471 if (
auto *PN = dyn_cast<PHINode>(V)) {
473 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
481 for (
auto *PN : PHIs)
482 for (
Value *Op : PN->incoming_values())
490 for (
Value *Val : Explored) {
493 auto *
PHI = dyn_cast<PHINode>(
Use);
494 auto *Inst = dyn_cast<Instruction>(Val);
496 if (Inst ==
Base || Inst ==
PHI || !Inst || !
PHI ||
500 if (
PHI->getParent() == Inst->getParent())
510 bool Before =
true) {
511 if (
auto *
PHI = dyn_cast<PHINode>(V)) {
512 Builder.SetInsertPoint(&*
PHI->getParent()->getFirstInsertionPt());
515 if (
auto *
I = dyn_cast<Instruction>(V)) {
517 I = &*std::next(
I->getIterator());
521 if (
auto *
A = dyn_cast<Argument>(V)) {
523 BasicBlock &Entry =
A->getParent()->getEntryBlock();
524 Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
529 assert(isa<Constant>(V) &&
"Setting insertion point for unknown value!");
545 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
551 for (
Value *Val : Explored) {
556 if (
auto *
PHI = dyn_cast<PHINode>(Val))
558 PHI->getName() +
".idx",
PHI);
563 for (
Value *Val : Explored) {
565 if (NewInsts.
find(Val) != NewInsts.
end())
568 if (
auto *CI = dyn_cast<CastInst>(Val)) {
571 Value *V = NewInsts[CI->getOperand(0)];
575 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
577 :
GEP->getOperand(1);
581 if (
Index->getType()->getScalarSizeInBits() !=
582 NewInsts[
GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
584 Index, NewInsts[
GEP->getOperand(0)]->getType(),
585 GEP->getOperand(0)->getName() +
".sext");
588 auto *Op = NewInsts[
GEP->getOperand(0)];
589 if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->
isZero())
593 Op,
Index,
GEP->getOperand(0)->getName() +
".add");
596 if (isa<PHINode>(Val))
603 for (
Value *Val : Explored) {
608 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
610 for (
unsigned I = 0,
E =
PHI->getNumIncomingValues();
I <
E; ++
I) {
611 Value *NewIncoming =
PHI->getIncomingValue(
I);
613 if (NewInsts.
find(NewIncoming) != NewInsts.
end())
614 NewIncoming = NewInsts[NewIncoming];
622 ElemTy->
getPointerTo(Start->getType()->getPointerAddressSpace());
623 for (
Value *Val : Explored) {
633 Base, PtrTy, Start->getName() +
"to.ptr");
634 NewVal =
Builder.CreateInBoundsGEP(ElemTy, NewVal,
ArrayRef(NewInsts[Val]),
635 Val->getName() +
".ptr");
636 NewVal =
Builder.CreateBitOrPointerCast(
637 NewVal, Val->
getType(), Val->getName() +
".conv");
638 Val->replaceAllUsesWith(NewVal);
641 return NewInsts[Start];
647static std::pair<Value *, Value *>
650 DL.getIndexTypeSizeInBits(V->
getType()));
657 if (!
GEP->isInBounds())
659 if (
GEP->hasAllConstantIndices() &&
GEP->getNumIndices() == 1 &&
660 GEP->getSourceElementType() == ElemTy) {
661 V =
GEP->getOperand(0);
669 if (
auto *CI = dyn_cast<IntToPtrInst>(V)) {
670 if (!CI->isNoopCast(
DL))
672 V = CI->getOperand(0);
675 if (
auto *CI = dyn_cast<PtrToIntInst>(V)) {
676 if (!CI->isNoopCast(
DL))
678 V = CI->getOperand(0);
739 if (!isa<GetElementPtrInst>(
RHS))
751 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
773 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
778 cast<Constant>(
RHS),
Base->getType()));
782 if (PtrBase != GEPRHS->getOperand(0)) {
783 bool IndicesTheSame =
786 GEPRHS->getPointerOperand()->getType() &&
790 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
791 IndicesTheSame =
false;
804 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
806 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
810 Value *LOffset = EmitGEPOffset(GEPLHS);
811 Value *ROffset = EmitGEPOffset(GEPRHS);
818 if (LHSIndexTy != RHSIndexTy) {
845 if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
848 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
852 unsigned NumDifferences = 0;
853 unsigned DiffOperand = 0;
854 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
855 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
857 Type *RHSType = GEPRHS->getOperand(i)->getType();
868 if (NumDifferences++)
break;
872 if (NumDifferences == 0)
876 else if (NumDifferences == 1 && GEPsInBounds) {
878 Value *RHSV = GEPRHS->getOperand(DiffOperand);
886 if (GEPsInBounds && (isa<ConstantExpr>(GEPLHS) || GEPLHS->
hasOneUse()) &&
887 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
889 Value *L = EmitGEPOffset(GEPLHS);
890 Value *R = EmitGEPOffset(GEPRHS);
918 unsigned MaxIter = 32;
921 for (
const Use &U : Alloca->
uses()) {
927 unsigned NumCmps = 0;
931 const Value *V = U->getUser();
934 if (isa<BitCastInst>(V) || isa<GetElementPtrInst>(V) || isa<PHINode>(V) ||
935 isa<SelectInst>(V)) {
937 }
else if (isa<LoadInst>(V)) {
940 }
else if (
const auto *
SI = dyn_cast<StoreInst>(V)) {
942 if (
SI->getValueOperand() == U->get())
945 }
else if (isa<ICmpInst>(V)) {
949 }
else if (
const auto *Intrin = dyn_cast<IntrinsicInst>(V)) {
950 switch (Intrin->getIntrinsicID()) {
954 case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
955 case Intrinsic::memcpy:
case Intrinsic::memmove:
case Intrinsic::memset:
963 for (
const Use &U : V->
uses()) {
981 assert(!!
C &&
"C should not be zero!");
1029 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1032 if (
I.getPredicate() ==
I.ICMP_NE)
1041 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1053 return getICmp(
I.ICMP_UGT,
A,
1066 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1072 }
else if (AP1 == AP2.
lshr(Shift)) {
1088 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1091 if (
I.getPredicate() ==
I.ICMP_NE)
1102 if (!AP1 && AP2TrailingZeros != 0)
1113 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1139 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1147 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1171 if (U == AddWithCst)
1189 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1195 Builder.SetInsertPoint(OrigAdd);
1197 Value *TruncA =
Builder.CreateTrunc(
A, NewType,
A->getName() +
".trunc");
1198 Value *TruncB =
Builder.CreateTrunc(
B, NewType,
B->getName() +
".trunc");
1218 if (!
I.isEquality())
1249 APInt(XBitWidth, XBitWidth - 1))))
1251 }
else if (isa<BinaryOperator>(Val) &&
1276 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1278 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1295 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1307 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1313 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1315 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1316 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1324 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1329 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1361 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1374 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1375 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1376 Type *Ty = Cmp.getType();
1382 cast<Constant>(Phi->getIncomingValueForBlock(Predecessor));
1407 assert((TrueBB == CmpBB || FalseBB == CmpBB) &&
1408 "Predecessor block does not point to successor?");
1411 if (TrueBB == FalseBB)
1415 std::optional<bool> Imp =
1421 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1452 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1457 if (Cmp.hasOneUse() &&
1476 if (
C.isOne() &&
C.getBitWidth() > 1) {
1484 Type *SrcTy =
X->getType();
1495 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1504 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1507 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1520 if ((Known.
Zero | Known.
One).countLeadingOnes() >= SrcBits - DstBits) {
1522 APInt NewRHS =
C.zext(SrcBits);
1532 const APInt *ShAmtC;
1562 bool TrueIfSigned =
false;
1579 if (
Xor->hasOneUse()) {
1581 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1582 Pred = Cmp.getFlippedSignednessPredicate();
1588 Pred = Cmp.getFlippedSignednessPredicate();
1589 Pred = Cmp.getSwappedPredicate(Pred);
1597 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1600 if (*XorC ==
C && (
C + 1).isPowerOf2())
1605 if (*XorC == -
C &&
C.isPowerOf2())
1609 if (*XorC ==
C && (-
C).isPowerOf2())
1633 const APInt *ShiftC;
1638 Type *XType =
X->getType();
1653 if (!Shift || !Shift->
isShift())
1661 unsigned ShiftOpcode = Shift->
getOpcode();
1662 bool IsShl = ShiftOpcode == Instruction::Shl;
1665 APInt NewAndCst, NewCmpCst;
1666 bool AnyCmpCstBitsShiftedOut;
1667 if (ShiftOpcode == Instruction::Shl) {
1675 NewCmpCst = C1.
lshr(*C3);
1676 NewAndCst = C2.
lshr(*C3);
1677 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1678 }
else if (ShiftOpcode == Instruction::LShr) {
1683 NewCmpCst = C1.
shl(*C3);
1684 NewAndCst = C2.
shl(*C3);
1685 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1691 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1692 NewCmpCst = C1.
shl(*C3);
1693 NewAndCst = C2.
shl(*C3);
1694 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1695 if (NewAndCst.
ashr(*C3) != C2)
1699 if (AnyCmpCstBitsShiftedOut) {
1710 return new ICmpInst(Cmp.getPredicate(),
1742 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1744 return new TruncInst(
And->getOperand(0), Cmp.getType());
1752 if (!
And->hasOneUse())
1755 if (Cmp.isEquality() && C1.
isZero()) {
1775 return new ICmpInst(NewPred,
X, NegBOC);
1793 if (!Cmp.getType()->isVectorTy()) {
1794 Type *WideType = W->getType();
1799 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1810 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1812 Constant *One = cast<Constant>(
And->getOperand(1));
1817 unsigned UsesRemoved = 0;
1818 if (
And->hasOneUse())
1820 if (
Or->hasOneUse())
1826 Value *NewOr =
nullptr;
1827 if (
auto *
C = dyn_cast<Constant>(
B)) {
1828 if (UsesRemoved >= 1)
1831 if (UsesRemoved >= 3)
1834 One,
Or->getName());
1871 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1872 if (
auto *
LI = dyn_cast<LoadInst>(
X))
1873 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
LI->getOperand(0)))
1874 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1879 if (!Cmp.isEquality())
1885 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1888 return new ICmpInst(NewPred,
X,
SubOne(cast<Constant>(Cmp.getOperand(1))));
1901 assert(Cmp.isEquality() &&
"Not expecting non-equality predicates");
1903 const APInt *TC, *FC;
1920 X->getType()->isIntOrIntVectorTy(1) && (
C.isZero() ||
C.isOne())) {
1926 return BinaryOperator::CreateAnd(TruncY,
X);
1945 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
1947 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
1948 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
1953 return new ICmpInst(Pred, OrOp0, OrOp1);
1960 if (
Or->hasOneUse()) {
1978 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
1995 Value *X1, *X2, *X3, *X4;
2020 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
2021 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2043 if (Cmp.isEquality()) {
2045 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2054 if (
C.urem(*MulC).isZero()) {
2057 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2064 if (!
Mul->hasNoSignedWrap() && !
Mul->hasNoUnsignedWrap())
2072 if (
Mul->hasNoSignedWrap()) {
2074 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2086 assert(
Mul->hasNoUnsignedWrap() &&
"Expected mul nuw");
2095 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2106 unsigned TypeBits =
C.getBitWidth();
2107 bool CIsPowerOf2 =
C.isPowerOf2();
2109 if (Cmp.isUnsigned()) {
2122 unsigned CLog2 =
C.logBase2();
2124 }
else if (Cmp.isSigned()) {
2146 const APInt *ShiftVal;
2150 const APInt *ShiftAmt;
2156 unsigned TypeBits =
C.getBitWidth();
2157 if (ShiftAmt->
uge(TypeBits))
2170 APInt ShiftedC =
C.ashr(*ShiftAmt);
2174 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2175 APInt ShiftedC =
C.ashr(*ShiftAmt);
2183 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2184 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2200 APInt ShiftedC =
C.lshr(*ShiftAmt);
2204 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2205 APInt ShiftedC =
C.lshr(*ShiftAmt);
2213 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2214 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2219 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2230 bool TrueIfSigned =
false;
2242 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2244 if ((
C + 1).isPowerOf2() &&
2252 if (
C.isPowerOf2() &&
2269 if (Shl->
hasOneUse() && Amt != 0 &&
C.countTrailingZeros() >= Amt &&
2272 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2290 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2291 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2293 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2294 const APInt *ShiftValC;
2296 if (Cmp.isEquality())
2314 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2315 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2326 const APInt *ShiftAmtC;
2332 unsigned TypeBits =
C.getBitWidth();
2334 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2337 bool IsExact = Shr->
isExact();
2348 APInt ShiftedC =
C.shl(ShAmtVal);
2349 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2354 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2355 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2356 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2363 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2364 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2365 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2373 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2387 APInt ShiftedC =
C.shl(ShAmtVal);
2388 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2393 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2394 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2399 if (!Cmp.isEquality())
2407 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2408 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2409 "Expected icmp+shr simplify did not occur.");
2455 const APInt *DivisorC;
2464 !
C.isStrictlyPositive()))
2501 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2506 "icmp ugt X, UINT_MAX should have been simplified already.");
2513 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2529 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2539 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2540 (!DivIsSigned ||
C.isMinSignedValue())) {
2565 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2584 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2597 int LoOverflow = 0, HiOverflow = 0;
2598 APInt LoBound, HiBound;
2603 HiOverflow = LoOverflow = ProdOV;
2612 LoBound = -(RangeSize - 1);
2613 HiBound = RangeSize;
2614 }
else if (
C.isStrictlyPositive()) {
2616 HiOverflow = LoOverflow = ProdOV;
2622 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2624 APInt DivNeg = -RangeSize;
2625 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2633 LoBound = RangeSize + 1;
2634 HiBound = -RangeSize;
2635 if (HiBound == *C2) {
2639 }
else if (
C.isStrictlyPositive()) {
2642 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2648 LoOverflow = HiOverflow = ProdOV;
2661 if (LoOverflow && HiOverflow)
2672 if (LoOverflow && HiOverflow)
2684 if (LoOverflow == +1)
2686 if (LoOverflow == -1)
2691 if (HiOverflow == +1)
2693 if (HiOverflow == -1)
2726 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2736 if (Cmp.isEquality() &&
C.isZero() &&
2772 (*C2 & (
C - 1)) == (
C - 1))
2805 if ((
Add->hasNoSignedWrap() &&
2807 (
Add->hasNoUnsignedWrap() &&
2811 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
2823 if (Cmp.isSigned()) {
2824 if (
Lower.isSignMask())
2826 if (
Upper.isSignMask())
2829 if (
Lower.isMinValue())
2831 if (
Upper.isMinValue())
2864 if (!
Add->hasOneUse())
2907 Value *EqualVal =
SI->getTrueValue();
2908 Value *UnequalVal =
SI->getFalseValue();
2931 auto FlippedStrictness =
2933 PredB, cast<Constant>(RHS2));
2934 if (!FlippedStrictness)
2937 "basic correctness failure");
2938 RHS2 = FlippedStrictness->second;
2950 assert(
C &&
"Cmp RHS should be a constant int!");
2956 Value *OrigLHS, *OrigRHS;
2957 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
2958 if (Cmp.hasOneUse() &&
2961 assert(C1LessThan && C2Equal && C3GreaterThan);
2963 bool TrueWhenLessThan =
2966 bool TrueWhenEqual =
2969 bool TrueWhenGreaterThan =
2982 if (TrueWhenLessThan)
2988 if (TrueWhenGreaterThan)
2998 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3003 Value *Op1 = Cmp.getOperand(1);
3004 Value *BCSrcOp = Bitcast->getOperand(0);
3005 Type *SrcType = Bitcast->getSrcTy();
3006 Type *DstType = Bitcast->getType();
3053 Type *XType =
X->getType();
3058 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3074 if (DstType->
isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
3077 if (
auto *BC2 = dyn_cast<BitCastInst>(Op1))
3078 Op1 = BC2->getOperand(0);
3081 return new ICmpInst(Pred, BCSrcOp, Op1);
3096 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse() &&
3106 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3108 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3127 auto *VecTy = cast<VectorType>(SrcType);
3128 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3129 if (
C->isSplat(EltTy->getBitWidth())) {
3138 return new ICmpInst(Pred, Extract, NewC);
3151 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3155 if (
auto *
SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3159 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3163 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3167 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3174 Value *Cmp0 = Cmp.getOperand(0);
3176 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3178 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3181 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3183 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3198 if (!Cmp.isEquality())
3203 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3207 case Instruction::SRem:
3218 case Instruction::Add: {
3222 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3225 }
else if (
C.isZero()) {
3228 if (
Value *NegVal = dyn_castNegVal(BOp1))
3229 return new ICmpInst(Pred, BOp0, NegVal);
3230 if (
Value *NegVal = dyn_castNegVal(BOp0))
3231 return new ICmpInst(Pred, NegVal, BOp1);
3235 return new ICmpInst(Pred, BOp0, Neg);
3240 case Instruction::Xor:
3242 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3246 }
else if (
C.isZero()) {
3248 return new ICmpInst(Pred, BOp0, BOp1);
3252 case Instruction::Or: {
3264 case Instruction::And: {
3268 if (
C == *BOC &&
C.isPowerOf2())
3274 case Instruction::UDiv:
3278 return new ICmpInst(NewPred, BOp1, BOp0);
3295 case Intrinsic::abs:
3298 if (
C.isZero() ||
C.isMinSignedValue())
3302 case Intrinsic::bswap:
3307 case Intrinsic::ctlz:
3308 case Intrinsic::cttz: {
3317 unsigned Num =
C.getLimitedValue(
BitWidth);
3322 APInt Mask2 = IsTrailing
3331 case Intrinsic::ctpop: {
3334 bool IsZero =
C.isZero();
3343 case Intrinsic::fshl:
3344 case Intrinsic::fshr:
3346 const APInt *RotAmtC;
3357 case Intrinsic::uadd_sat: {
3366 case Intrinsic::usub_sat: {
3384 assert(Cmp.isEquality());
3387 Value *Op0 = Cmp.getOperand(0);
3388 Value *Op1 = Cmp.getOperand(1);
3389 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3390 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3391 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3394 switch (IIOp0->getIntrinsicID()) {
3395 case Intrinsic::bswap:
3396 case Intrinsic::bitreverse:
3399 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3400 case Intrinsic::fshl:
3401 case Intrinsic::fshr:
3404 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3406 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3408 if (IIOp0->getOperand(2) != IIOp1->getOperand(2))
3410 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3425 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3426 switch (II->getIntrinsicID()) {
3429 case Intrinsic::fshl:
3430 case Intrinsic::fshr:
3431 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3433 if (
C.isZero() ||
C.isAllOnes())
3434 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3448 case Instruction::Xor:
3452 case Instruction::And:
3456 case Instruction::Or:
3460 case Instruction::Mul:
3464 case Instruction::Shl:
3468 case Instruction::LShr:
3469 case Instruction::AShr:
3473 case Instruction::SRem:
3477 case Instruction::UDiv:
3481 case Instruction::SDiv:
3485 case Instruction::Sub:
3489 case Instruction::Add:
3505 if (Cmp.isEquality())
3512 case Intrinsic::ctpop: {
3524 case Intrinsic::ctlz: {
3527 unsigned Num =
C.getLimitedValue();
3535 unsigned Num =
C.getLimitedValue();
3542 case Intrinsic::cttz: {
3573 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3574 Constant *RHSC = dyn_cast<Constant>(Op1);
3580 case Instruction::GetElementPtr:
3583 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
3588 case Instruction::PHI:
3596 case Instruction::IntToPtr:
3605 case Instruction::Load:
3608 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
3624 auto SimplifyOp = [&](
Value *Op,
bool SelectCondIsTrue) ->
Value * {
3628 SI->getCondition(), Pred, Op,
RHS,
DL, SelectCondIsTrue))
3634 Value *Op1 = SimplifyOp(
SI->getOperand(1),
true);
3636 CI = dyn_cast<ConstantInt>(Op1);
3638 Value *Op2 = SimplifyOp(
SI->getOperand(2),
false);
3640 CI = dyn_cast<ConstantInt>(Op2);
3649 bool Transform =
false;
3652 else if (Op1 || Op2) {
3654 if (
SI->hasOneUse())
3657 else if (CI && !CI->
isZero())
3754 Type *OpTy = M->getType();
3755 auto *VecC = dyn_cast<Constant>(M);
3756 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
3757 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
3758 Constant *SafeReplacementConstant =
nullptr;
3759 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
3760 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
3765 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
3769 return Builder.CreateICmp(DstPred,
X, M);
3785 const APInt *C0, *C1;
3802 const APInt &MaskedBits = *C0;
3803 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
3824 auto *XType =
X->getType();
3825 const unsigned XBitWidth = XType->getScalarSizeInBits();
3827 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
3858 !
I.getOperand(0)->hasOneUse())
3883 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
3884 "We did not look past any shifts while matching XShift though.");
3885 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
3892 auto XShiftOpcode = XShift->
getOpcode();
3893 if (XShiftOpcode == YShift->
getOpcode())
3896 Value *
X, *XShAmt, *
Y, *YShAmt;
3903 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
3905 if (!
match(
I.getOperand(0),
3931 unsigned MaximalPossibleTotalShiftAmount =
3934 APInt MaximalRepresentableShiftAmount =
3936 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
3940 auto *NewShAmt = dyn_cast_or_null<Constant>(
3950 if (!
match(NewShAmt,
3952 APInt(WidestBitWidth, WidestBitWidth))))
3957 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
3963 ? NewShAmt->getSplatValue()
3966 if (NewShAmtSplat &&
3972 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
3976 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3977 if (MaxActiveBits <= 1)
3983 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
3987 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3988 if (MaxActiveBits <= 1)
3991 if (NewShAmtSplat) {
3994 if (AdjNewShAmt.
ule(MinLeadZero))
4008 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
4012 return Builder.CreateICmp(
I.getPredicate(),
T1,
4030 if (!
I.isEquality() &&
4040 NeedNegation =
false;
4043 NeedNegation =
true;
4049 if (
I.isEquality() &&
4065 bool MulHadOtherUses =
Mul && !
Mul->hasOneUse();
4066 if (MulHadOtherUses)
4071 ? Intrinsic::umul_with_overflow
4072 : Intrinsic::smul_with_overflow,
4079 if (MulHadOtherUses)
4088 if (MulHadOtherUses)
4117 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4173 return new ICmpInst(NewPred, Op1, Zero);
4182 return new ICmpInst(NewPred, Op0, Zero);
4186 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
4187 if (BO0 && isa<OverflowingBinaryOperator>(BO0))
4192 if (BO1 && isa<OverflowingBinaryOperator>(BO1))