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()) {
206 CompareRHS,
DL, &
TLI);
208 if (isa<UndefValue>(
C)) {
211 if (TrueRangeEnd == (
int)i-1)
213 if (FalseRangeEnd == (
int)i-1)
220 if (!isa<ConstantInt>(
C))
return nullptr;
224 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
229 if (FirstTrueElement == Undefined)
230 FirstTrueElement = TrueRangeEnd = i;
233 if (SecondTrueElement == Undefined)
234 SecondTrueElement = i;
236 SecondTrueElement = Overdefined;
239 if (TrueRangeEnd == (
int)i-1)
242 TrueRangeEnd = Overdefined;
246 if (FirstFalseElement == Undefined)
247 FirstFalseElement = FalseRangeEnd = i;
250 if (SecondFalseElement == Undefined)
251 SecondFalseElement = i;
253 SecondFalseElement = Overdefined;
256 if (FalseRangeEnd == (
int)i-1)
259 FalseRangeEnd = Overdefined;
264 if (i < 64 && IsTrueForElt)
265 MagicBitvector |= 1ULL << i;
270 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
271 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
272 FalseRangeEnd == Overdefined)
283 if (!
GEP->isInBounds()) {
286 if (
Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
297 unsigned ElementSize =
310 if (SecondTrueElement != Overdefined) {
313 if (FirstTrueElement == Undefined)
319 if (SecondTrueElement == Undefined)
326 return BinaryOperator::CreateOr(C1, C2);
331 if (SecondFalseElement != Overdefined) {
334 if (FirstFalseElement == Undefined)
340 if (SecondFalseElement == Undefined)
347 return BinaryOperator::CreateAnd(C1, C2);
352 if (TrueRangeEnd != Overdefined) {
353 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
357 if (FirstTrueElement) {
363 TrueRangeEnd-FirstTrueElement+1);
368 if (FalseRangeEnd != Overdefined) {
369 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
372 if (FirstFalseElement) {
378 FalseRangeEnd-FirstFalseElement);
391 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
425 while (!WorkList.
empty()) {
428 while (!WorkList.
empty()) {
429 if (Explored.
size() >= 100)
439 if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
440 !isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
445 if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
446 auto *CI = cast<CastInst>(V);
447 if (!CI->isNoopCast(
DL))
450 if (!Explored.
contains(CI->getOperand(0)))
454 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
458 if (
GEP->getNumIndices() != 1 || !
GEP->isInBounds() ||
459 GEP->getSourceElementType() != ElemTy)
466 if (WorkList.
back() == V) {
472 if (
auto *PN = dyn_cast<PHINode>(V)) {
474 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
482 for (
auto *PN : PHIs)
483 for (
Value *Op : PN->incoming_values())
491 for (
Value *Val : Explored) {
494 auto *
PHI = dyn_cast<PHINode>(
Use);
495 auto *Inst = dyn_cast<Instruction>(Val);
497 if (Inst ==
Base || Inst ==
PHI || !Inst || !
PHI ||
501 if (
PHI->getParent() == Inst->getParent())
511 bool Before =
true) {
512 if (
auto *
PHI = dyn_cast<PHINode>(V)) {
513 Builder.SetInsertPoint(&*
PHI->getParent()->getFirstInsertionPt());
516 if (
auto *
I = dyn_cast<Instruction>(V)) {
518 I = &*std::next(
I->getIterator());
522 if (
auto *
A = dyn_cast<Argument>(V)) {
524 BasicBlock &Entry =
A->getParent()->getEntryBlock();
525 Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
530 assert(isa<Constant>(V) &&
"Setting insertion point for unknown value!");
547 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
553 for (
Value *Val : Explored) {
558 if (
auto *
PHI = dyn_cast<PHINode>(Val))
560 PHI->getName() +
".idx",
PHI);
565 for (
Value *Val : Explored) {
570 if (
auto *CI = dyn_cast<CastInst>(Val)) {
573 Value *V = NewInsts[CI->getOperand(0)];
577 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
579 :
GEP->getOperand(1);
583 if (
Index->getType()->getScalarSizeInBits() !=
584 NewInsts[
GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
586 Index, NewInsts[
GEP->getOperand(0)]->getType(),
587 GEP->getOperand(0)->getName() +
".sext");
590 auto *Op = NewInsts[
GEP->getOperand(0)];
591 if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->
isZero())
595 Op,
Index,
GEP->getOperand(0)->getName() +
".add");
598 if (isa<PHINode>(Val))
605 for (
Value *Val : Explored) {
610 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
612 for (
unsigned I = 0,
E =
PHI->getNumIncomingValues();
I <
E; ++
I) {
613 Value *NewIncoming =
PHI->getIncomingValue(
I);
616 NewIncoming = NewInsts[NewIncoming];
624 ElemTy->
getPointerTo(Start->getType()->getPointerAddressSpace());
625 for (
Value *Val : Explored) {
635 Base, PtrTy, Start->getName() +
"to.ptr");
636 NewVal =
Builder.CreateInBoundsGEP(ElemTy, NewVal,
ArrayRef(NewInsts[Val]),
637 Val->getName() +
".ptr");
638 NewVal =
Builder.CreateBitOrPointerCast(
639 NewVal, Val->
getType(), Val->getName() +
".conv");
646 return NewInsts[Start];
652static std::pair<Value *, Value *>
655 DL.getIndexTypeSizeInBits(V->getType()));
662 if (!
GEP->isInBounds())
664 if (
GEP->hasAllConstantIndices() &&
GEP->getNumIndices() == 1 &&
665 GEP->getSourceElementType() == ElemTy) {
666 V =
GEP->getOperand(0);
674 if (
auto *CI = dyn_cast<IntToPtrInst>(V)) {
675 if (!CI->isNoopCast(
DL))
677 V = CI->getOperand(0);
680 if (
auto *CI = dyn_cast<PtrToIntInst>(V)) {
681 if (!CI->isNoopCast(
DL))
683 V = CI->getOperand(0);
745 if (!isa<GetElementPtrInst>(
RHS))
757 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
779 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
784 cast<Constant>(
RHS),
Base->getType()));
788 if (PtrBase != GEPRHS->getOperand(0)) {
789 bool IndicesTheSame =
792 GEPRHS->getPointerOperand()->getType() &&
796 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
797 IndicesTheSame =
false;
810 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
812 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
816 Value *LOffset = EmitGEPOffset(GEPLHS);
817 Value *ROffset = EmitGEPOffset(GEPRHS);
824 if (LHSIndexTy != RHSIndexTy) {
851 if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
854 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
858 unsigned NumDifferences = 0;
859 unsigned DiffOperand = 0;
860 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
861 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
863 Type *RHSType = GEPRHS->getOperand(i)->getType();
874 if (NumDifferences++)
break;
878 if (NumDifferences == 0)
882 else if (NumDifferences == 1 && GEPsInBounds) {
884 Value *RHSV = GEPRHS->getOperand(DiffOperand);
893 (isa<ConstantExpr>(GEPLHS) || GEPLHS->
hasOneUse()) &&
894 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
896 Value *L = EmitGEPOffset(GEPLHS);
897 Value *R = EmitGEPOffset(GEPRHS);
924 bool Captured =
false;
929 CmpCaptureTracker(
AllocaInst *Alloca) : Alloca(Alloca) {}
931 void tooManyUses()
override { Captured =
true; }
933 bool captured(
const Use *U)
override {
934 auto *ICmp = dyn_cast<ICmpInst>(U->getUser());
942 auto Res = ICmps.
insert({ICmp, 0});
943 Res.first->second |= 1u << U->getOperandNo();
952 CmpCaptureTracker Tracker(Alloca);
954 if (Tracker.Captured)
957 bool Changed =
false;
958 for (
auto [ICmp,
Operands] : Tracker.ICmps) {
990 assert(!!
C &&
"C should not be zero!");
1038 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1041 if (
I.getPredicate() ==
I.ICMP_NE)
1050 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1062 return getICmp(
I.ICMP_UGT,
A,
1075 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1081 }
else if (AP1 == AP2.
lshr(Shift)) {
1097 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1100 if (
I.getPredicate() ==
I.ICMP_NE)
1111 if (!AP1 && AP2TrailingZeros != 0)
1122 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1148 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1156 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1180 if (U == AddWithCst)
1198 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1204 Builder.SetInsertPoint(OrigAdd);
1206 Value *TruncA =
Builder.CreateTrunc(
A, NewType,
A->getName() +
".trunc");
1207 Value *TruncB =
Builder.CreateTrunc(
B, NewType,
B->getName() +
".trunc");
1227 if (!
I.isEquality())
1258 APInt(XBitWidth, XBitWidth - 1))))
1260 }
else if (isa<BinaryOperator>(Val) &&
1285 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1287 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1304 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1316 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1322 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1324 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1325 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1333 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1338 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1370 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1383 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1384 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1386 for (
Value *V : Phi->incoming_values()) {
1395 for (
auto [V, Pred] :
zip(Ops, Phi->blocks()))
1417 assert((TrueBB == CmpBB || FalseBB == CmpBB) &&
1418 "Predecessor block does not point to successor?");
1421 if (TrueBB == FalseBB)
1428 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1459 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1464 if (Cmp.hasOneUse() &&
1483 if (
C.isOne() &&
C.getBitWidth() > 1) {
1491 Type *SrcTy =
X->getType();
1502 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1511 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1514 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1527 if ((Known.
Zero | Known.
One).countl_one() >= SrcBits - DstBits) {
1529 APInt NewRHS =
C.zext(SrcBits);
1539 const APInt *ShAmtC;
1569 bool TrueIfSigned =
false;
1586 if (
Xor->hasOneUse()) {
1588 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1589 Pred = Cmp.getFlippedSignednessPredicate();
1595 Pred = Cmp.getFlippedSignednessPredicate();
1596 Pred = Cmp.getSwappedPredicate(Pred);
1604 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1607 if (*XorC ==
C && (
C + 1).isPowerOf2())
1612 if (*XorC == -
C &&
C.isPowerOf2())
1616 if (*XorC ==
C && (-
C).isPowerOf2())
1640 const APInt *ShiftC;
1645 Type *XType =
X->getType();
1660 if (!Shift || !Shift->
isShift())
1668 unsigned ShiftOpcode = Shift->
getOpcode();
1669 bool IsShl = ShiftOpcode == Instruction::Shl;
1672 APInt NewAndCst, NewCmpCst;
1673 bool AnyCmpCstBitsShiftedOut;
1674 if (ShiftOpcode == Instruction::Shl) {
1682 NewCmpCst = C1.
lshr(*C3);
1683 NewAndCst = C2.
lshr(*C3);
1684 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1685 }
else if (ShiftOpcode == Instruction::LShr) {
1690 NewCmpCst = C1.
shl(*C3);
1691 NewAndCst = C2.
shl(*C3);
1692 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1698 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1699 NewCmpCst = C1.
shl(*C3);
1700 NewAndCst = C2.
shl(*C3);
1701 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1702 if (NewAndCst.
ashr(*C3) != C2)
1706 if (AnyCmpCstBitsShiftedOut) {
1717 return new ICmpInst(Cmp.getPredicate(),
1749 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1751 return new TruncInst(
And->getOperand(0), Cmp.getType());
1759 if (!
And->hasOneUse())
1762 if (Cmp.isEquality() && C1.
isZero()) {
1782 return new ICmpInst(NewPred,
X, NegBOC);
1800 if (!Cmp.getType()->isVectorTy()) {
1801 Type *WideType = W->getType();
1806 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1817 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1819 Constant *One = cast<Constant>(
And->getOperand(1));
1824 unsigned UsesRemoved = 0;
1825 if (
And->hasOneUse())
1827 if (
Or->hasOneUse())
1833 Value *NewOr =
nullptr;
1834 if (
auto *
C = dyn_cast<Constant>(
B)) {
1835 if (UsesRemoved >= 1)
1838 if (UsesRemoved >= 3)
1841 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);
1961 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
1963 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
1964 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
1969 return new ICmpInst(Pred, OrOp0, OrOp1);
1976 if (
Or->hasOneUse()) {
2018 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
2035 Value *X1, *X2, *X3, *X4;
2060 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
2061 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2083 if (Cmp.isEquality()) {
2085 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2094 if (
C.urem(*MulC).isZero()) {
2097 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2111 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2121 "Unexpected predicate");
2131 "Unexpected predicate");
2137 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2148 unsigned TypeBits =
C.getBitWidth();
2149 bool CIsPowerOf2 =
C.isPowerOf2();
2151 if (Cmp.isUnsigned()) {
2164 unsigned CLog2 =
C.logBase2();
2166 }
else if (Cmp.isSigned()) {
2188 const APInt *ShiftVal;
2192 const APInt *ShiftAmt;
2198 unsigned TypeBits =
C.getBitWidth();
2199 if (ShiftAmt->
uge(TypeBits))
2212 APInt ShiftedC =
C.ashr(*ShiftAmt);
2216 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2217 APInt ShiftedC =
C.ashr(*ShiftAmt);
2225 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2226 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2242 APInt ShiftedC =
C.lshr(*ShiftAmt);
2246 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2247 APInt ShiftedC =
C.lshr(*ShiftAmt);
2255 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2256 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2261 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2272 bool TrueIfSigned =
false;
2284 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2286 if ((
C + 1).isPowerOf2() &&
2294 if (
C.isPowerOf2() &&
2311 if (Shl->
hasOneUse() && Amt != 0 &&
C.countr_zero() >= Amt &&
2314 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2332 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2333 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2335 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2336 const APInt *ShiftValC;
2338 if (Cmp.isEquality())
2356 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2357 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2359 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2367 const APInt *ShiftAmtC;
2373 unsigned TypeBits =
C.getBitWidth();
2375 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2378 bool IsExact = Shr->
isExact();
2389 APInt ShiftedC =
C.shl(ShAmtVal);
2390 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2395 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2396 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2397 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2404 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2405 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2406 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2414 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2428 APInt ShiftedC =
C.shl(ShAmtVal);
2429 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2434 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2435 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2440 if (!Cmp.isEquality())
2448 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2449 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2450 "Expected icmp+shr simplify did not occur.");
2496 const APInt *DivisorC;
2505 !
C.isStrictlyPositive()))
2542 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2547 "icmp ugt X, UINT_MAX should have been simplified already.");
2554 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2570 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2580 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2581 (!DivIsSigned ||
C.isMinSignedValue())) {
2606 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2625 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2638 int LoOverflow = 0, HiOverflow = 0;
2639 APInt LoBound, HiBound;
2644 HiOverflow = LoOverflow = ProdOV;
2653 LoBound = -(RangeSize - 1);
2654 HiBound = RangeSize;
2655 }
else if (
C.isStrictlyPositive()) {
2657 HiOverflow = LoOverflow = ProdOV;
2663 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2665 APInt DivNeg = -RangeSize;
2666 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2674 LoBound = RangeSize + 1;
2675 HiBound = -RangeSize;
2676 if (HiBound == *C2) {
2680 }
else if (
C.isStrictlyPositive()) {
2683 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2689 LoOverflow = HiOverflow = ProdOV;
2702 if (LoOverflow && HiOverflow)
2713 if (LoOverflow && HiOverflow)
2725 if (LoOverflow == +1)
2727 if (LoOverflow == -1)
2732 if (HiOverflow == +1)
2734 if (HiOverflow == -1)
2767 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2777 if (Cmp.isEquality() &&
C.isZero() &&
2813 (*C2 & (
C - 1)) == (
C - 1))
2846 if ((
Add->hasNoSignedWrap() &&
2848 (
Add->hasNoUnsignedWrap() &&
2852 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
2864 if (Cmp.isSigned()) {
2865 if (
Lower.isSignMask())
2867 if (
Upper.isSignMask())
2870 if (
Lower.isMinValue())
2872 if (
Upper.isMinValue())
2905 if (!
Add->hasOneUse())
2948 Value *EqualVal =
SI->getTrueValue();
2949 Value *UnequalVal =
SI->getFalseValue();
2972 auto FlippedStrictness =
2974 PredB, cast<Constant>(RHS2));
2975 if (!FlippedStrictness)
2978 "basic correctness failure");
2979 RHS2 = FlippedStrictness->second;
2991 assert(
C &&
"Cmp RHS should be a constant int!");
2997 Value *OrigLHS, *OrigRHS;
2998 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
2999 if (Cmp.hasOneUse() &&
3002 assert(C1LessThan && C2Equal && C3GreaterThan);
3004 bool TrueWhenLessThan =
3007 bool TrueWhenEqual =
3010 bool TrueWhenGreaterThan =
3023 if (TrueWhenLessThan)
3029 if (TrueWhenGreaterThan)
3039 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3044 Value *Op1 = Cmp.getOperand(1);
3045 Value *BCSrcOp = Bitcast->getOperand(0);
3046 Type *SrcType = Bitcast->getSrcTy();
3047 Type *DstType = Bitcast->getType();
3094 Type *XType =
X->getType();
3099 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3115 if (DstType->
isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
3118 if (
auto *BC2 = dyn_cast<BitCastInst>(Op1))
3119 Op1 = BC2->getOperand(0);
3122 return new ICmpInst(Pred, BCSrcOp, Op1);
3137 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse() &&
3147 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3149 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3168 auto *VecTy = cast<VectorType>(SrcType);
3169 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3170 if (
C->isSplat(EltTy->getBitWidth())) {
3179 return new ICmpInst(Pred, Extract, NewC);
3192 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3196 if (
auto *
SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3200 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3204 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3208 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3215 Value *Cmp0 = Cmp.getOperand(0);
3217 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3219 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3222 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3224 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3239 if (!Cmp.isEquality())
3244 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3248 case Instruction::SRem:
3259 case Instruction::Add: {
3263 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3266 }
else if (
C.isZero()) {
3269 if (
Value *NegVal = dyn_castNegVal(BOp1))
3270 return new ICmpInst(Pred, BOp0, NegVal);
3271 if (
Value *NegVal = dyn_castNegVal(BOp0))
3272 return new ICmpInst(Pred, NegVal, BOp1);
3276 return new ICmpInst(Pred, BOp0, Neg);
3281 case Instruction::Xor:
3283 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3287 }
else if (
C.isZero()) {
3289 return new ICmpInst(Pred, BOp0, BOp1);
3293 case Instruction::Or: {
3305 case Instruction::UDiv:
3309 return new ICmpInst(NewPred, BOp1, BOp0);
3326 case Intrinsic::abs:
3329 if (
C.isZero() ||
C.isMinSignedValue())
3333 case Intrinsic::bswap:
3338 case Intrinsic::bitreverse:
3343 case Intrinsic::ctlz:
3344 case Intrinsic::cttz: {
3353 unsigned Num =
C.getLimitedValue(
BitWidth);
3358 APInt Mask2 = IsTrailing
3367 case Intrinsic::ctpop: {
3370 bool IsZero =
C.isZero();
3379 case Intrinsic::fshl:
3380 case Intrinsic::fshr:
3382 const APInt *RotAmtC;
3393 case Intrinsic::umax:
3394 case Intrinsic::uadd_sat: {
3404 case Intrinsic::ssub_sat:
3409 case Intrinsic::usub_sat: {
3427 assert(Cmp.isEquality());
3430 Value *Op0 = Cmp.getOperand(0);
3431 Value *Op1 = Cmp.getOperand(1);
3432 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3433 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3434 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3437 switch (IIOp0->getIntrinsicID()) {
3438 case Intrinsic::bswap:
3439 case Intrinsic::bitreverse:
3442 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3443 case Intrinsic::fshl:
3444 case Intrinsic::fshr:
3447 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3449 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3451 if (IIOp0->getOperand(2) != IIOp1->getOperand(2))
3453 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3468 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3469 switch (II->getIntrinsicID()) {
3472 case Intrinsic::fshl:
3473 case Intrinsic::fshr:
3474 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3476 if (
C.isZero() ||
C.isAllOnes())
3477 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3491 case Instruction::Xor:
3495 case Instruction::And:
3499 case Instruction::Or:
3503 case Instruction::Mul:
3507 case Instruction::Shl:
3511 case Instruction::LShr:
3512 case Instruction::AShr:
3516 case Instruction::SRem:
3520 case Instruction::UDiv:
3524 case Instruction::SDiv:
3528 case Instruction::Sub:
3532 case Instruction::Add:
3548 if (Cmp.isEquality())
3555 case Intrinsic::ctpop: {
3567 case Intrinsic::ctlz: {
3570 unsigned Num =
C.getLimitedValue();
3578 unsigned Num =
C.getLimitedValue();
3585 case Intrinsic::cttz: {
3607 case Intrinsic::ssub_sat:
3631 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3632 Constant *RHSC = dyn_cast<Constant>(Op1);
3638 case Instruction::GetElementPtr:
3641 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
3646 case Instruction::PHI:
3654 case Instruction::IntToPtr:
3663 case Instruction::Load:
3666 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
3682 auto SimplifyOp = [&](
Value *Op,
bool SelectCondIsTrue) ->
Value * {
3686 SI->getCondition(), Pred, Op,
RHS,
DL, SelectCondIsTrue))
3692 Value *Op1 = SimplifyOp(
SI->getOperand(1),
true);
3694 CI = dyn_cast<ConstantInt>(Op1);
3696 Value *Op2 = SimplifyOp(
SI->getOperand(2),
false);
3698 CI = dyn_cast<ConstantInt>(Op2);
3707 bool Transform =
false;
3710 else if (Op1 || Op2) {
3712 if (
SI->hasOneUse())
3715 else if (CI && !CI->
isZero())
3812 Type *OpTy = M->getType();
3813 auto *VecC = dyn_cast<Constant>(M);
3814 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
3815 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
3816 Constant *SafeReplacementConstant =
nullptr;
3817 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
3818 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
3823 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
3827 return Builder.CreateICmp(DstPred,
X, M);
3843 const APInt *C0, *C1;
3860 const APInt &MaskedBits = *C0;
3861 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
3882 auto *XType =
X->getType();
3883 const unsigned XBitWidth = XType->getScalarSizeInBits();
3885 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
3916 !
I.getOperand(0)->hasOneUse())
3941 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
3942 "We did not look past any shifts while matching XShift though.");
3943 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
3950 auto XShiftOpcode = XShift->
getOpcode();
3951 if (XShiftOpcode == YShift->
getOpcode())
3954 Value *
X, *XShAmt, *
Y, *YShAmt;
3961 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
3963 if (!
match(
I.getOperand(0),
3989 unsigned MaximalPossibleTotalShiftAmount =
3992 APInt MaximalRepresentableShiftAmount =
3994 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
3998 auto *NewShAmt = dyn_cast_or_null<Constant>(
4008 if (!
match(NewShAmt,
4010 APInt(WidestBitWidth, WidestBitWidth))))
4015 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
4021 ? NewShAmt->getSplatValue()
4024 if (NewShAmtSplat &&
4030 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
4034 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4035 if (MaxActiveBits <= 1)
4041 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
4045 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4046 if (MaxActiveBits <= 1)
4049 if (NewShAmtSplat) {
4052 if (AdjNewShAmt.
ule(MinLeadZero))
4066 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
4070 return Builder.CreateICmp(
I.getPredicate(),
T1,
4088 if (!
I.isEquality() &&
4098 NeedNegation =
false;
4101 NeedNegation =
true;
4107 if (
I.isEquality() &&
4123 bool MulHadOtherUses =
Mul && !
Mul->hasOneUse();
4124 if (MulHadOtherUses)
4129 ? Intrinsic::umul_with_overflow
4130 : Intrinsic::smul_with_overflow,
4137 if (MulHadOtherUses)
4146 if (MulHadOtherUses)
4172 Type *Ty =
X->getType();
4186 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4201 if (PredOut != Pred &&
4203 return new ICmpInst(PredOut, Op0, Op1);