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() > PtrSize)
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!");
546 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
552 for (
Value *Val : Explored) {
557 if (
auto *
PHI = dyn_cast<PHINode>(Val))
559 PHI->getName() +
".idx",
PHI);
564 for (
Value *Val : Explored) {
569 if (
auto *CI = dyn_cast<CastInst>(Val)) {
572 Value *V = NewInsts[CI->getOperand(0)];
576 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
578 :
GEP->getOperand(1);
582 if (
Index->getType()->getScalarSizeInBits() !=
583 NewInsts[
GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
585 Index, NewInsts[
GEP->getOperand(0)]->getType(),
586 GEP->getOperand(0)->getName() +
".sext");
589 auto *Op = NewInsts[
GEP->getOperand(0)];
590 if (isa<ConstantInt>(Op) && cast<ConstantInt>(Op)->
isZero())
594 Op,
Index,
GEP->getOperand(0)->getName() +
".add");
597 if (isa<PHINode>(Val))
604 for (
Value *Val : Explored) {
609 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
611 for (
unsigned I = 0,
E =
PHI->getNumIncomingValues();
I <
E; ++
I) {
612 Value *NewIncoming =
PHI->getIncomingValue(
I);
615 NewIncoming = NewInsts[NewIncoming];
623 ElemTy->
getPointerTo(Start->getType()->getPointerAddressSpace());
624 for (
Value *Val : Explored) {
634 Base, PtrTy, Start->getName() +
"to.ptr");
635 NewVal =
Builder.CreateInBoundsGEP(ElemTy, NewVal,
ArrayRef(NewInsts[Val]),
636 Val->getName() +
".ptr");
637 NewVal =
Builder.CreateBitOrPointerCast(
638 NewVal, Val->
getType(), Val->getName() +
".conv");
639 Val->replaceAllUsesWith(NewVal);
642 return NewInsts[Start];
648static std::pair<Value *, Value *>
651 DL.getIndexTypeSizeInBits(V->getType()));
658 if (!
GEP->isInBounds())
660 if (
GEP->hasAllConstantIndices() &&
GEP->getNumIndices() == 1 &&
661 GEP->getSourceElementType() == ElemTy) {
662 V =
GEP->getOperand(0);
670 if (
auto *CI = dyn_cast<IntToPtrInst>(V)) {
671 if (!CI->isNoopCast(
DL))
673 V = CI->getOperand(0);
676 if (
auto *CI = dyn_cast<PtrToIntInst>(V)) {
677 if (!CI->isNoopCast(
DL))
679 V = CI->getOperand(0);
740 if (!isa<GetElementPtrInst>(
RHS))
752 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
774 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
779 cast<Constant>(
RHS),
Base->getType()));
783 if (PtrBase != GEPRHS->getOperand(0)) {
784 bool IndicesTheSame =
787 GEPRHS->getPointerOperand()->getType() &&
791 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
792 IndicesTheSame =
false;
805 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
807 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
811 Value *LOffset = EmitGEPOffset(GEPLHS);
812 Value *ROffset = EmitGEPOffset(GEPRHS);
819 if (LHSIndexTy != RHSIndexTy) {
846 if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
849 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
853 unsigned NumDifferences = 0;
854 unsigned DiffOperand = 0;
855 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
856 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
858 Type *RHSType = GEPRHS->getOperand(i)->getType();
869 if (NumDifferences++)
break;
873 if (NumDifferences == 0)
877 else if (NumDifferences == 1 && GEPsInBounds) {
879 Value *RHSV = GEPRHS->getOperand(DiffOperand);
888 (isa<ConstantExpr>(GEPLHS) || GEPLHS->
hasOneUse()) &&
889 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
891 Value *L = EmitGEPOffset(GEPLHS);
892 Value *R = EmitGEPOffset(GEPRHS);
921 bool Captured =
false;
922 unsigned NumCmps = 0;
924 void tooManyUses()
override { Captured =
true; }
926 bool captured(
const Use *U)
override {
927 if (isa<ICmpInst>(U->getUser()) && ++NumCmps == 1) {
937 CmpCaptureTracker Tracker;
939 if (Tracker.Captured)
953 assert(!!
C &&
"C should not be zero!");
1001 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1004 if (
I.getPredicate() ==
I.ICMP_NE)
1013 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1025 return getICmp(
I.ICMP_UGT,
A,
1038 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1044 }
else if (AP1 == AP2.
lshr(Shift)) {
1060 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1063 if (
I.getPredicate() ==
I.ICMP_NE)
1074 if (!AP1 && AP2TrailingZeros != 0)
1085 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1111 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1119 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1143 if (U == AddWithCst)
1161 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1167 Builder.SetInsertPoint(OrigAdd);
1169 Value *TruncA =
Builder.CreateTrunc(
A, NewType,
A->getName() +
".trunc");
1170 Value *TruncB =
Builder.CreateTrunc(
B, NewType,
B->getName() +
".trunc");
1190 if (!
I.isEquality())
1221 APInt(XBitWidth, XBitWidth - 1))))
1223 }
else if (isa<BinaryOperator>(Val) &&
1248 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1250 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1267 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1279 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1285 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1287 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1288 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1296 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1301 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1333 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1346 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1347 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1348 Type *Ty = Cmp.getType();
1354 cast<Constant>(Phi->getIncomingValueForBlock(Predecessor));
1379 assert((TrueBB == CmpBB || FalseBB == CmpBB) &&
1380 "Predecessor block does not point to successor?");
1383 if (TrueBB == FalseBB)
1390 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1421 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1426 if (Cmp.hasOneUse() &&
1445 if (
C.isOne() &&
C.getBitWidth() > 1) {
1453 Type *SrcTy =
X->getType();
1464 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1473 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1476 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1489 if ((Known.
Zero | Known.
One).countl_one() >= SrcBits - DstBits) {
1491 APInt NewRHS =
C.zext(SrcBits);
1501 const APInt *ShAmtC;
1531 bool TrueIfSigned =
false;
1548 if (
Xor->hasOneUse()) {
1550 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1551 Pred = Cmp.getFlippedSignednessPredicate();
1557 Pred = Cmp.getFlippedSignednessPredicate();
1558 Pred = Cmp.getSwappedPredicate(Pred);
1566 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1569 if (*XorC ==
C && (
C + 1).isPowerOf2())
1574 if (*XorC == -
C &&
C.isPowerOf2())
1578 if (*XorC ==
C && (-
C).isPowerOf2())
1602 const APInt *ShiftC;
1607 Type *XType =
X->getType();
1622 if (!Shift || !Shift->
isShift())
1630 unsigned ShiftOpcode = Shift->
getOpcode();
1631 bool IsShl = ShiftOpcode == Instruction::Shl;
1634 APInt NewAndCst, NewCmpCst;
1635 bool AnyCmpCstBitsShiftedOut;
1636 if (ShiftOpcode == Instruction::Shl) {
1644 NewCmpCst = C1.
lshr(*C3);
1645 NewAndCst = C2.
lshr(*C3);
1646 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1647 }
else if (ShiftOpcode == Instruction::LShr) {
1652 NewCmpCst = C1.
shl(*C3);
1653 NewAndCst = C2.
shl(*C3);
1654 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1660 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1661 NewCmpCst = C1.
shl(*C3);
1662 NewAndCst = C2.
shl(*C3);
1663 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1664 if (NewAndCst.
ashr(*C3) != C2)
1668 if (AnyCmpCstBitsShiftedOut) {
1679 return new ICmpInst(Cmp.getPredicate(),
1711 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1713 return new TruncInst(
And->getOperand(0), Cmp.getType());
1721 if (!
And->hasOneUse())
1724 if (Cmp.isEquality() && C1.
isZero()) {
1744 return new ICmpInst(NewPred,
X, NegBOC);
1762 if (!Cmp.getType()->isVectorTy()) {
1763 Type *WideType = W->getType();
1768 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1779 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1781 Constant *One = cast<Constant>(
And->getOperand(1));
1786 unsigned UsesRemoved = 0;
1787 if (
And->hasOneUse())
1789 if (
Or->hasOneUse())
1795 Value *NewOr =
nullptr;
1796 if (
auto *
C = dyn_cast<Constant>(
B)) {
1797 if (UsesRemoved >= 1)
1800 if (UsesRemoved >= 3)
1803 One,
Or->getName());
1840 return new ICmpInst(NewPred,
X, MinSignedC);
1849 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1850 if (
auto *
LI = dyn_cast<LoadInst>(
X))
1851 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
LI->getOperand(0)))
1852 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1857 if (!Cmp.isEquality())
1863 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1866 return new ICmpInst(NewPred,
X,
SubOne(cast<Constant>(Cmp.getOperand(1))));
1879 assert(Cmp.isEquality() &&
"Not expecting non-equality predicates");
1881 const APInt *TC, *FC;
1898 X->getType()->isIntOrIntVectorTy(1) && (
C.isZero() ||
C.isOne())) {
1904 return BinaryOperator::CreateAnd(TruncY,
X);
1923 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
1925 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
1926 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
1931 return new ICmpInst(Pred, OrOp0, OrOp1);
1938 if (
Or->hasOneUse()) {
1956 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
1973 Value *X1, *X2, *X3, *X4;
1998 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
1999 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2021 if (Cmp.isEquality()) {
2023 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2032 if (
C.urem(*MulC).isZero()) {
2035 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2049 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2059 "Unexpected predicate");
2069 "Unexpected predicate");
2075 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2086 unsigned TypeBits =
C.getBitWidth();
2087 bool CIsPowerOf2 =
C.isPowerOf2();
2089 if (Cmp.isUnsigned()) {
2102 unsigned CLog2 =
C.logBase2();
2104 }
else if (Cmp.isSigned()) {
2126 const APInt *ShiftVal;
2130 const APInt *ShiftAmt;
2136 unsigned TypeBits =
C.getBitWidth();
2137 if (ShiftAmt->
uge(TypeBits))
2150 APInt ShiftedC =
C.ashr(*ShiftAmt);
2154 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2155 APInt ShiftedC =
C.ashr(*ShiftAmt);
2163 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2164 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2180 APInt ShiftedC =
C.lshr(*ShiftAmt);
2184 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2185 APInt ShiftedC =
C.lshr(*ShiftAmt);
2193 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2194 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2199 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2210 bool TrueIfSigned =
false;
2222 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2224 if ((
C + 1).isPowerOf2() &&
2232 if (
C.isPowerOf2() &&
2249 if (Shl->
hasOneUse() && Amt != 0 &&
C.countr_zero() >= Amt &&
2252 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2270 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2271 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2273 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2274 const APInt *ShiftValC;
2276 if (Cmp.isEquality())
2294 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2295 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2297 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2305 const APInt *ShiftAmtC;
2311 unsigned TypeBits =
C.getBitWidth();
2313 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2316 bool IsExact = Shr->
isExact();
2327 APInt ShiftedC =
C.shl(ShAmtVal);
2328 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2333 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2334 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2335 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2342 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2343 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2344 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2352 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2366 APInt ShiftedC =
C.shl(ShAmtVal);
2367 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2372 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2373 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2378 if (!Cmp.isEquality())
2386 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2387 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2388 "Expected icmp+shr simplify did not occur.");
2434 const APInt *DivisorC;
2443 !
C.isStrictlyPositive()))
2480 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2485 "icmp ugt X, UINT_MAX should have been simplified already.");
2492 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2508 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2518 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2519 (!DivIsSigned ||
C.isMinSignedValue())) {
2544 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2563 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2576 int LoOverflow = 0, HiOverflow = 0;
2577 APInt LoBound, HiBound;
2582 HiOverflow = LoOverflow = ProdOV;
2591 LoBound = -(RangeSize - 1);
2592 HiBound = RangeSize;
2593 }
else if (
C.isStrictlyPositive()) {
2595 HiOverflow = LoOverflow = ProdOV;
2601 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2603 APInt DivNeg = -RangeSize;
2604 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2612 LoBound = RangeSize + 1;
2613 HiBound = -RangeSize;
2614 if (HiBound == *C2) {
2618 }
else if (
C.isStrictlyPositive()) {
2621 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2627 LoOverflow = HiOverflow = ProdOV;
2640 if (LoOverflow && HiOverflow)
2651 if (LoOverflow && HiOverflow)
2663 if (LoOverflow == +1)
2665 if (LoOverflow == -1)
2670 if (HiOverflow == +1)
2672 if (HiOverflow == -1)
2705 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2715 if (Cmp.isEquality() &&
C.isZero() &&
2751 (*C2 & (
C - 1)) == (
C - 1))
2784 if ((
Add->hasNoSignedWrap() &&
2786 (
Add->hasNoUnsignedWrap() &&
2790 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
2802 if (Cmp.isSigned()) {
2803 if (
Lower.isSignMask())
2805 if (
Upper.isSignMask())
2808 if (
Lower.isMinValue())
2810 if (
Upper.isMinValue())
2843 if (!
Add->hasOneUse())
2886 Value *EqualVal =
SI->getTrueValue();
2887 Value *UnequalVal =
SI->getFalseValue();
2910 auto FlippedStrictness =
2912 PredB, cast<Constant>(RHS2));
2913 if (!FlippedStrictness)
2916 "basic correctness failure");
2917 RHS2 = FlippedStrictness->second;
2929 assert(
C &&
"Cmp RHS should be a constant int!");
2935 Value *OrigLHS, *OrigRHS;
2936 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
2937 if (Cmp.hasOneUse() &&
2940 assert(C1LessThan && C2Equal && C3GreaterThan);
2942 bool TrueWhenLessThan =
2945 bool TrueWhenEqual =
2948 bool TrueWhenGreaterThan =
2961 if (TrueWhenLessThan)
2967 if (TrueWhenGreaterThan)
2977 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
2982 Value *Op1 = Cmp.getOperand(1);
2983 Value *BCSrcOp = Bitcast->getOperand(0);
2984 Type *SrcType = Bitcast->getSrcTy();
2985 Type *DstType = Bitcast->getType();
3032 Type *XType =
X->getType();
3037 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3053 if (DstType->
isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
3056 if (
auto *BC2 = dyn_cast<BitCastInst>(Op1))
3057 Op1 = BC2->getOperand(0);
3060 return new ICmpInst(Pred, BCSrcOp, Op1);
3075 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse() &&
3085 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3087 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3106 auto *VecTy = cast<VectorType>(SrcType);
3107 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3108 if (
C->isSplat(EltTy->getBitWidth())) {
3117 return new ICmpInst(Pred, Extract, NewC);
3130 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3134 if (
auto *
SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3138 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3142 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3146 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3153 Value *Cmp0 = Cmp.getOperand(0);
3155 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3157 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3160 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3162 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3177 if (!Cmp.isEquality())
3182 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3186 case Instruction::SRem:
3197 case Instruction::Add: {
3201 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3204 }
else if (
C.isZero()) {
3207 if (
Value *NegVal = dyn_castNegVal(BOp1))
3208 return new ICmpInst(Pred, BOp0, NegVal);
3209 if (
Value *NegVal = dyn_castNegVal(BOp0))
3210 return new ICmpInst(Pred, NegVal, BOp1);
3214 return new ICmpInst(Pred, BOp0, Neg);
3219 case Instruction::Xor:
3221 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3225 }
else if (
C.isZero()) {
3227 return new ICmpInst(Pred, BOp0, BOp1);
3231 case Instruction::Or: {
3243 case Instruction::UDiv:
3247 return new ICmpInst(NewPred, BOp1, BOp0);
3264 case Intrinsic::abs:
3267 if (
C.isZero() ||
C.isMinSignedValue())
3271 case Intrinsic::bswap:
3276 case Intrinsic::bitreverse:
3281 case Intrinsic::ctlz:
3282 case Intrinsic::cttz: {
3291 unsigned Num =
C.getLimitedValue(
BitWidth);
3296 APInt Mask2 = IsTrailing
3305 case Intrinsic::ctpop: {
3308 bool IsZero =
C.isZero();
3317 case Intrinsic::fshl:
3318 case Intrinsic::fshr:
3320 const APInt *RotAmtC;
3331 case Intrinsic::uadd_sat: {
3340 case Intrinsic::usub_sat: {
3358 assert(Cmp.isEquality());
3361 Value *Op0 = Cmp.getOperand(0);
3362 Value *Op1 = Cmp.getOperand(1);
3363 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3364 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3365 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3368 switch (IIOp0->getIntrinsicID()) {
3369 case Intrinsic::bswap:
3370 case Intrinsic::bitreverse:
3373 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3374 case Intrinsic::fshl:
3375 case Intrinsic::fshr:
3378 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3380 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3382 if (IIOp0->getOperand(2) != IIOp1->getOperand(2))
3384 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3399 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3400 switch (II->getIntrinsicID()) {
3403 case Intrinsic::fshl:
3404 case Intrinsic::fshr:
3405 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3407 if (
C.isZero() ||
C.isAllOnes())
3408 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3422 case Instruction::Xor:
3426 case Instruction::And:
3430 case Instruction::Or:
3434 case Instruction::Mul:
3438 case Instruction::Shl:
3442 case Instruction::LShr:
3443 case Instruction::AShr:
3447 case Instruction::SRem:
3451 case Instruction::UDiv:
3455 case Instruction::SDiv:
3459 case Instruction::Sub:
3463 case Instruction::Add:
3479 if (Cmp.isEquality())
3486 case Intrinsic::ctpop: {
3498 case Intrinsic::ctlz: {
3501 unsigned Num =
C.getLimitedValue();
3509 unsigned Num =
C.getLimitedValue();
3516 case Intrinsic::cttz: {
3547 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3548 Constant *RHSC = dyn_cast<Constant>(Op1);
3554 case Instruction::GetElementPtr:
3557 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
3562 case Instruction::PHI:
3570 case Instruction::IntToPtr:
3579 case Instruction::Load:
3582 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
3598 auto SimplifyOp = [&](
Value *Op,
bool SelectCondIsTrue) ->
Value * {
3602 SI->getCondition(), Pred, Op,
RHS,
DL, SelectCondIsTrue))
3608 Value *Op1 = SimplifyOp(
SI->getOperand(1),
true);
3610 CI = dyn_cast<ConstantInt>(Op1);
3612 Value *Op2 = SimplifyOp(
SI->getOperand(2),
false);
3614 CI = dyn_cast<ConstantInt>(Op2);
3623 bool Transform =
false;
3626 else if (Op1 || Op2) {
3628 if (
SI->hasOneUse())
3631 else if (CI && !CI->
isZero())
3728 Type *OpTy = M->getType();
3729 auto *VecC = dyn_cast<Constant>(M);
3730 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
3731 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
3732 Constant *SafeReplacementConstant =
nullptr;
3733 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
3734 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
3739 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
3743 return Builder.CreateICmp(DstPred,
X, M);
3759 const APInt *C0, *C1;
3776 const APInt &MaskedBits = *C0;
3777 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
3798 auto *XType =
X->getType();
3799 const unsigned XBitWidth = XType->getScalarSizeInBits();
3801 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
3832 !
I.getOperand(0)->hasOneUse())
3857 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
3858 "We did not look past any shifts while matching XShift though.");
3859 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
3866 auto XShiftOpcode = XShift->
getOpcode();
3867 if (XShiftOpcode == YShift->
getOpcode())
3870 Value *
X, *XShAmt, *
Y, *YShAmt;
3877 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
3879 if (!
match(
I.getOperand(0),
3905 unsigned MaximalPossibleTotalShiftAmount =
3908 APInt MaximalRepresentableShiftAmount =
3910 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
3914 auto *NewShAmt = dyn_cast_or_null<Constant>(
3924 if (!
match(NewShAmt,
3926 APInt(WidestBitWidth, WidestBitWidth))))
3931 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
3937 ? NewShAmt->getSplatValue()
3940 if (NewShAmtSplat &&
3946 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
3950 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3951 if (MaxActiveBits <= 1)
3957 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
3961 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3962 if (MaxActiveBits <= 1)
3965 if (NewShAmtSplat) {
3968 if (AdjNewShAmt.
ule(MinLeadZero))
3982 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
3986 return Builder.CreateICmp(
I.getPredicate(),
T1,
4004 if (!
I.isEquality() &&
4014 NeedNegation =
false;
4017 NeedNegation =
true;
4023 if (
I.isEquality() &&
4039 bool MulHadOtherUses =
Mul && !
Mul->hasOneUse();
4040 if (MulHadOtherUses)
4045 ? Intrinsic::umul_with_overflow
4046 : Intrinsic::smul_with_overflow,
4053 if (MulHadOtherUses)
4062 if (MulHadOtherUses)
4088 Type *Ty =
X->getType();
4107 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4163 return new ICmpInst(NewPred, Op1, Zero);
4172 return new ICmpInst(NewPred, Op0, Zero);
4176 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
4177 if (BO0 && isa<OverflowingBinaryOperator>(BO0))
4182 if (BO1 && isa<OverflowingBinaryOperator>(BO1))