29 using namespace PatternMatch;
31 #define DEBUG_TYPE "instcombine"
34 STATISTIC(NumSel,
"Number of select opts");
40 const APInt &In2,
bool IsSigned =
false) {
43 Result = In1.
sadd_ov(In2, Overflow);
45 Result = In1.
uadd_ov(In2, Overflow);
53 const APInt &In2,
bool IsSigned =
false) {
56 Result = In1.
ssub_ov(In2, Overflow);
58 Result = In1.
usub_ov(In2, Overflow);
66 for (
auto *U :
I.users())
67 if (isa<BranchInst>(U))
88 }
else if (
C.isAllOnes()) {
115 if (!isa<ConstantArray>(
Init) && !isa<ConstantDataArray>(
Init))
118 uint64_t ArrayElementCount =
Init->getType()->getArrayNumElements();
120 if (ArrayElementCount > MaxArraySizeForCombine)
127 if (
GEP->getNumOperands() < 3 ||
128 !isa<ConstantInt>(
GEP->getOperand(1)) ||
129 !cast<ConstantInt>(
GEP->getOperand(1))->isZero() ||
130 isa<Constant>(
GEP->getOperand(2)))
138 Type *EltTy =
Init->getType()->getArrayElementType();
139 for (
unsigned i = 3,
e =
GEP->getNumOperands();
i !=
e; ++
i) {
141 if (!Idx)
return nullptr;
144 if ((
unsigned)IdxVal != IdxVal)
return nullptr;
146 if (
StructType *STy = dyn_cast<StructType>(EltTy))
147 EltTy = STy->getElementType(IdxVal);
148 else if (
ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
149 if (IdxVal >= ATy->getNumElements())
return nullptr;
150 EltTy = ATy->getElementType();
155 LaterIndices.push_back(IdxVal);
158 enum { Overdefined = -3, Undefined = -2 };
167 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
171 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
179 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
188 for (
unsigned i = 0,
e = ArrayElementCount;
i !=
e; ++
i) {
190 if (!Elt)
return nullptr;
193 if (!LaterIndices.empty())
201 CompareRHS,
DL, &TLI);
203 if (isa<UndefValue>(
C)) {
206 if (TrueRangeEnd == (
int)
i-1)
208 if (FalseRangeEnd == (
int)
i-1)
215 if (!isa<ConstantInt>(
C))
return nullptr;
219 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
224 if (FirstTrueElement == Undefined)
225 FirstTrueElement = TrueRangeEnd =
i;
228 if (SecondTrueElement == Undefined)
229 SecondTrueElement =
i;
231 SecondTrueElement = Overdefined;
234 if (TrueRangeEnd == (
int)
i-1)
237 TrueRangeEnd = Overdefined;
241 if (FirstFalseElement == Undefined)
242 FirstFalseElement = FalseRangeEnd =
i;
245 if (SecondFalseElement == Undefined)
246 SecondFalseElement =
i;
248 SecondFalseElement = Overdefined;
251 if (FalseRangeEnd == (
int)
i-1)
254 FalseRangeEnd = Overdefined;
259 if (
i < 64 && IsTrueForElt)
260 MagicBitvector |= 1ULL <<
i;
265 if ((
i & 8) == 0 &&
i >= 64 && SecondTrueElement == Overdefined &&
266 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
267 FalseRangeEnd == Overdefined)
278 if (!
GEP->isInBounds()) {
279 Type *IntPtrTy =
DL.getIntPtrType(
GEP->getType());
282 Idx =
Builder.CreateTrunc(Idx, IntPtrTy);
292 unsigned ElementSize =
293 DL.getTypeAllocSize(
Init->getType()->getArrayElementType());
294 auto MaskIdx = [&](
Value* Idx){
305 if (SecondTrueElement != Overdefined) {
308 if (FirstTrueElement == Undefined)
309 return replaceInstUsesWith(ICI,
Builder.getFalse());
314 if (SecondTrueElement == Undefined)
321 return BinaryOperator::CreateOr(
C1, C2);
326 if (SecondFalseElement != Overdefined) {
329 if (FirstFalseElement == Undefined)
330 return replaceInstUsesWith(ICI,
Builder.getTrue());
335 if (SecondFalseElement == Undefined)
342 return BinaryOperator::CreateAnd(
C1, C2);
347 if (TrueRangeEnd != Overdefined) {
348 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
352 if (FirstTrueElement) {
354 Idx =
Builder.CreateAdd(Idx, Offs);
358 TrueRangeEnd-FirstTrueElement+1);
363 if (FalseRangeEnd != Overdefined) {
364 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
367 if (FirstFalseElement) {
369 Idx =
Builder.CreateAdd(Idx, Offs);
373 FalseRangeEnd-FirstFalseElement);
386 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
389 Ty =
DL.getSmallestLegalIntType(
Init->getContext(), ArrayElementCount);
422 unsigned i,
e =
GEP->getNumOperands();
424 for (
i = 1;
i !=
e; ++
i, ++GTI) {
427 if (CI->isZero())
continue;
431 Offset +=
DL.getStructLayout(STy)->getElementOffset(CI->getZExtValue());
434 Offset += Size*CI->getSExtValue();
444 if (
i ==
e)
return nullptr;
452 for (++
i, ++GTI;
i !=
e; ++
i, ++GTI) {
454 if (!CI)
return nullptr;
457 if (CI->
isZero())
continue;
461 Offset +=
DL.getStructLayout(STy)->getElementOffset(CI->
getZExtValue());
471 Type *IntPtrTy =
DL.getIntPtrType(
GEP->getOperand(0)->getType());
487 VariableScale =
SignExtend64(VariableScale, IntPtrWidth);
493 int64_t NewOffs = Offset / (int64_t)VariableScale;
494 if (Offset != NewOffs*(int64_t)VariableScale)
498 if (VariableIdx->
getType() != IntPtrTy)
522 while (!WorkList.empty()) {
525 while (!WorkList.empty()) {
526 if (Explored.
size() >= 100)
529 Value *V = WorkList.back();
536 if (!isa<IntToPtrInst>(V) && !isa<PtrToIntInst>(V) &&
537 !isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
542 if (isa<IntToPtrInst>(V) || isa<PtrToIntInst>(V)) {
543 auto *CI = cast<CastInst>(V);
544 if (!CI->isNoopCast(
DL))
547 if (!Explored.
contains(CI->getOperand(0)))
548 WorkList.push_back(CI->getOperand(0));
551 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
555 if (
GEP->getNumIndices() != 1 || !
GEP->isInBounds() ||
556 GEP->getSourceElementType() != ElemTy)
560 WorkList.push_back(
GEP->getOperand(0));
563 if (WorkList.back() == V) {
569 if (
auto *PN = dyn_cast<PHINode>(V)) {
571 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
579 for (
auto *PN : PHIs)
580 for (
Value *
Op : PN->incoming_values())
582 WorkList.push_back(
Op);
588 for (
Value *Val : Explored) {
591 auto *PHI = dyn_cast<PHINode>(
Use);
592 auto *Inst = dyn_cast<Instruction>(Val);
594 if (Inst ==
Base || Inst == PHI || !Inst || !PHI ||
595 !Explored.contains(PHI))
598 if (PHI->getParent() == Inst->getParent())
608 bool Before =
true) {
609 if (
auto *PHI = dyn_cast<PHINode>(V)) {
610 Builder.SetInsertPoint(&*PHI->getParent()->getFirstInsertionPt());
613 if (
auto *
I = dyn_cast<Instruction>(V)) {
615 I = &*std::next(
I->getIterator());
619 if (
auto *A = dyn_cast<Argument>(V)) {
621 BasicBlock &Entry = A->getParent()->getEntryBlock();
622 Builder.SetInsertPoint(&*Entry.getFirstInsertionPt());
627 assert(isa<Constant>(V) &&
"Setting insertion point for unknown value!");
643 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
649 for (
Value *Val : Explored) {
654 if (
auto *PHI = dyn_cast<PHINode>(Val))
655 NewInsts[PHI] =
PHINode::Create(IndexType, PHI->getNumIncomingValues(),
656 PHI->getName() +
".idx", PHI);
661 for (
Value *Val : Explored) {
663 if (NewInsts.
find(Val) != NewInsts.
end())
666 if (
auto *CI = dyn_cast<CastInst>(Val)) {
669 Value *V = NewInsts[CI->getOperand(0)];
673 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
675 :
GEP->getOperand(1);
679 if (
Index->getType()->getScalarSizeInBits() !=
680 NewInsts[
GEP->getOperand(0)]->getType()->getScalarSizeInBits()) {
682 Index, NewInsts[
GEP->getOperand(0)]->getType(),
683 GEP->getOperand(0)->getName() +
".sext");
686 auto *
Op = NewInsts[
GEP->getOperand(0)];
687 if (isa<ConstantInt>(
Op) && cast<ConstantInt>(
Op)->
isZero())
691 Op,
Index,
GEP->getOperand(0)->getName() +
".add");
694 if (isa<PHINode>(Val))
701 for (
Value *Val : Explored) {
706 if (
auto *PHI = dyn_cast<PHINode>(Val)) {
708 for (
unsigned I = 0,
E = PHI->getNumIncomingValues();
I <
E; ++
I) {
709 Value *NewIncoming = PHI->getIncomingValue(
I);
711 if (NewInsts.
find(NewIncoming) != NewInsts.
end())
712 NewIncoming = NewInsts[NewIncoming];
714 NewPhi->
addIncoming(NewIncoming, PHI->getIncomingBlock(
I));
720 ElemTy->
getPointerTo(Start->getType()->getPointerAddressSpace());
721 for (
Value *Val : Explored) {
731 Base, PtrTy, Start->getName() +
"to.ptr");
732 NewVal =
Builder.CreateInBoundsGEP(
733 ElemTy, NewVal,
makeArrayRef(NewInsts[Val]), Val->getName() +
".ptr");
734 NewVal =
Builder.CreateBitOrPointerCast(
735 NewVal, Val->
getType(), Val->getName() +
".conv");
736 Val->replaceAllUsesWith(NewVal);
739 return NewInsts[Start];
745 static std::pair<Value *, Value *>
748 DL.getIndexTypeSizeInBits(V->
getType()));
755 if (!
GEP->isInBounds())
757 if (
GEP->hasAllConstantIndices() &&
GEP->getNumIndices() == 1 &&
758 GEP->getSourceElementType() == ElemTy) {
759 V =
GEP->getOperand(0);
767 if (
auto *CI = dyn_cast<IntToPtrInst>(V)) {
768 if (!CI->isNoopCast(
DL))
770 V = CI->getOperand(0);
773 if (
auto *CI = dyn_cast<PtrToIntInst>(V)) {
774 if (!CI->isNoopCast(
DL))
776 V = CI->getOperand(0);
837 if (!isa<GetElementPtrInst>(
RHS))
858 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
880 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
885 cast<Constant>(
RHS),
Base->getType()));
889 if (PtrBase != GEPRHS->getOperand(0)) {
890 bool IndicesTheSame =
893 GEPRHS->getPointerOperand()->getType() &&
898 IndicesTheSame =
false;
911 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
913 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
925 if (LHSIndexTy != RHSIndexTy) {
928 ROffset =
Builder.CreateTrunc(ROffset, LHSIndexTy);
930 LOffset =
Builder.CreateTrunc(LOffset, RHSIndexTy);
935 return replaceInstUsesWith(
I, Cmp);
947 return foldGEPICmp(GEPRHS, GEPLHS->
getOperand(0),
952 if (!GEPRHS->getType()->isVectorTy() && GEPRHS->hasAllZeroIndices())
955 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
959 unsigned NumDifferences = 0;
960 unsigned DiffOperand = 0;
961 for (
unsigned i = 1,
e = GEPRHS->getNumOperands();
i !=
e; ++
i)
964 Type *RHSType = GEPRHS->getOperand(
i)->getType();
975 if (NumDifferences++)
break;
979 if (NumDifferences == 0)
980 return replaceInstUsesWith(
I,
983 else if (NumDifferences == 1 && GEPsInBounds) {
985 Value *RHSV = GEPRHS->getOperand(DiffOperand);
993 if (GEPsInBounds && (isa<ConstantExpr>(GEPLHS) || GEPLHS->
hasOneUse()) &&
994 (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
1025 unsigned MaxIter = 32;
1028 for (
const Use &U : Alloca->
uses()) {
1029 if (Worklist.size() >= MaxIter)
1031 Worklist.push_back(&U);
1034 unsigned NumCmps = 0;
1035 while (!Worklist.empty()) {
1036 assert(Worklist.size() <= MaxIter);
1038 const Value *V = U->getUser();
1041 if (isa<BitCastInst>(V) || isa<GetElementPtrInst>(V) || isa<PHINode>(V) ||
1042 isa<SelectInst>(V)) {
1044 }
else if (isa<LoadInst>(V)) {
1047 }
else if (
const auto *
SI = dyn_cast<StoreInst>(V)) {
1049 if (
SI->getValueOperand() == U->get())
1052 }
else if (isa<ICmpInst>(V)) {
1056 }
else if (
const auto *Intrin = dyn_cast<IntrinsicInst>(V)) {
1057 switch (Intrin->getIntrinsicID()) {
1061 case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
1070 for (
const Use &U : V->
uses()) {
1071 if (Worklist.size() >= MaxIter)
1073 Worklist.push_back(&U);
1079 return replaceInstUsesWith(ICI, Res);
1088 assert(!!
C &&
"C should not be zero!");
1136 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1139 if (
I.getPredicate() ==
I.ICMP_NE)
1148 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1160 return getICmp(
I.ICMP_UGT, A,
1187 return replaceInstUsesWith(
I, TorF);
1195 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1198 if (
I.getPredicate() ==
I.ICMP_NE)
1209 if (!AP1 && AP2TrailingZeros != 0)
1226 return replaceInstUsesWith(
I, TorF);
1246 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1254 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1278 if (U == AddWithCst)
1296 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1302 Builder.SetInsertPoint(OrigAdd);
1304 Value *TruncA =
Builder.CreateTrunc(A, NewType, A->getName() +
".trunc");
1305 Value *TruncB =
Builder.CreateTrunc(
B, NewType,
B->getName() +
".trunc");
1307 Value *Add =
Builder.CreateExtractValue(Call, 0,
"sadd.result");
1325 if (!
I.isEquality())
1356 APInt(XBitWidth, XBitWidth - 1))))
1358 }
else if (isa<BinaryOperator>(Val) &&
1359 (
X = reassociateShiftAmtsOfTwoSameDirectionShifts(
1360 cast<BinaryOperator>(Val), SQ.getWithInstruction(Val),
1383 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1385 return new ICmpInst(Pred, A, Cmp.getOperand(1));
1389 if (
Instruction *New = foldIRemByPowerOfTwoToBitTest(Cmp))
1402 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1426 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1436 if (!
C ||
C->canTrap())
1439 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1440 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1441 Type *Ty = Cmp.getType();
1444 Builder.CreatePHI(Ty, Phi->getNumOperands());
1447 cast<Constant>(Phi->getIncomingValueForBlock(Predecessor));
1452 return replaceInstUsesWith(Cmp, NewPhi);
1472 assert((TrueBB == CmpBB || FalseBB == CmpBB) &&
1473 "Predecessor block does not point to successor?");
1476 if (TrueBB == FalseBB)
1485 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1505 return replaceInstUsesWith(Cmp,
Builder.getFalse());
1507 return replaceInstUsesWith(Cmp,
Builder.getTrue());
1515 bool IsSignBit = isSignBitCheck(Pred, *
C, UnusedBit);
1516 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1521 if (Cmp.hasOneUse() &&
1540 if (
C.isOne() &&
C.getBitWidth() > 1) {
1549 SrcBits =
X->getType()->getScalarSizeInBits();
1550 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1556 if ((Known.
Zero | Known.
One).countLeadingOnes() >= SrcBits - DstBits) {
1568 const APInt *ShAmtC;
1570 if (isSignBitCheck(Pred,
C, TrueIfSigned) &&
1596 bool TrueIfSigned =
false;
1597 if (isSignBitCheck(Cmp.getPredicate(),
C, TrueIfSigned)) {
1602 return replaceOperand(Cmp, 0,
X);
1613 if (
Xor->hasOneUse()) {
1615 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1616 Pred = Cmp.getFlippedSignednessPredicate();
1622 Pred = Cmp.getFlippedSignednessPredicate();
1623 Pred = Cmp.getSwappedPredicate(Pred);
1631 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1634 if (*XorC ==
C && (
C + 1).isPowerOf2())
1643 if (*XorC ==
C && (-
C).isPowerOf2())
1664 unsigned ShiftOpcode =
Shift->getOpcode();
1665 bool IsShl = ShiftOpcode == Instruction::Shl;
1668 APInt NewAndCst, NewCmpCst;
1669 bool AnyCmpCstBitsShiftedOut;
1670 if (ShiftOpcode == Instruction::Shl) {
1675 if (Cmp.isSigned() && (C2.
isNegative() ||
C1.isNegative()))
1678 NewCmpCst =
C1.lshr(*C3);
1679 NewAndCst = C2.
lshr(*C3);
1680 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) !=
C1;
1681 }
else if (ShiftOpcode == Instruction::LShr) {
1686 NewCmpCst =
C1.shl(*C3);
1687 NewAndCst = C2.
shl(*C3);
1688 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) !=
C1;
1694 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1695 NewCmpCst =
C1.shl(*C3);
1696 NewAndCst = C2.
shl(*C3);
1697 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) !=
C1;
1698 if (NewAndCst.
ashr(*C3) != C2)
1702 if (AnyCmpCstBitsShiftedOut) {
1713 return new ICmpInst(Cmp.getPredicate(),
1721 if (
Shift->hasOneUse() &&
C1.isZero() && Cmp.isEquality() &&
1722 !
Shift->isArithmeticShift() && !isa<Constant>(
Shift->getOperand(0))) {
1730 return replaceOperand(Cmp, 0, NewAnd);
1745 if (isICMP_NE && Cmp.getType()->isVectorTy() &&
C1.isZero() &&
1747 return new TruncInst(
And->getOperand(0), Cmp.getType());
1755 if (!
And->hasOneUse())
1758 if (Cmp.isEquality() &&
C1.isZero()) {
1769 if ((~(*C2) + 1).isPowerOf2()) {
1773 return new ICmpInst(NewPred,
X, NegBOC);
1787 (Cmp.isEquality() || (!
C1.isNegative() && !C2->
isNegative()))) {
1791 if (!Cmp.getType()->isVectorTy()) {
1792 Type *WideType =
W->getType();
1797 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1808 if (!Cmp.isSigned() &&
C1.isZero() &&
And->getOperand(0)->hasOneUse() &&
1810 Constant *One = cast<Constant>(
And->getOperand(1));
1815 unsigned UsesRemoved = 0;
1816 if (
And->hasOneUse())
1818 if (
Or->hasOneUse())
1824 Value *NewOr =
nullptr;
1825 if (
auto *
C = dyn_cast<Constant>(
B)) {
1826 if (UsesRemoved >= 1)
1829 if (UsesRemoved >= 3)
1832 One,
Or->getName());
1836 return replaceOperand(Cmp, 0, NewAnd);
1853 if (isSignBitCheck(Pred,
C, TrueIfNeg)) {
1869 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1870 if (
auto *LI = dyn_cast<LoadInst>(
X))
1871 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(LI->getOperand(0)))
1872 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1874 foldCmpLoadFromIndexedGlobal(LI,
GEP, GV, Cmp, C2))
1877 if (!Cmp.isEquality())
1883 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1886 return new ICmpInst(NewPred,
X, SubOne(cast<Constant>(Cmp.getOperand(1))));
1905 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
1907 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
1908 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
1913 return new ICmpInst(Pred, OrOp0, OrOp1);
1920 if (
Or->hasOneUse()) {
1931 if (isSignBitCheck(Pred,
C, TrueIfSigned) &&
1938 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
1955 Value *X1, *X2, *X3, *X4;
1989 if (Cmp.isEquality() && !MulC->
isZero()) {
2013 unsigned TypeBits =
C.getBitWidth();
2014 bool CIsPowerOf2 =
C.isPowerOf2();
2016 if (Cmp.isUnsigned()) {
2031 unsigned CLog2 =
C.logBase2();
2032 if (CLog2 == TypeBits - 1) {
2039 }
else if (Cmp.isSigned()) {
2041 if (
C.isAllOnes()) {
2060 }
else if (Cmp.isEquality() && CIsPowerOf2) {
2071 const APInt *ShiftVal;
2073 return foldICmpShlConstConst(Cmp, Shl->
getOperand(1),
C, *ShiftVal);
2075 const APInt *ShiftAmt;
2081 unsigned TypeBits =
C.getBitWidth();
2082 if (ShiftAmt->
uge(TypeBits))
2099 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2108 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2109 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2129 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2138 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2139 APInt ShiftedC = (
C - 1).
lshr(*ShiftAmt) + 1;
2144 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2155 bool TrueIfSigned =
false;
2156 if (Shl->
hasOneUse() && isSignBitCheck(Pred,
C, TrueIfSigned)) {
2167 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2169 if ((
C + 1).isPowerOf2() &&
2177 if (
C.isPowerOf2() &&
2194 if (Shl->
hasOneUse() && Amt != 0 &&
C.countTrailingZeros() >= Amt &&
2195 DL.isLegalInteger(TypeBits - Amt)) {
2197 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2215 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2216 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2218 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2219 const APInt *ShiftValC;
2221 if (Cmp.isEquality())
2222 return foldICmpShrConstConst(Cmp, Shr->
getOperand(1),
C, *ShiftValC);
2228 assert(ShiftValC->
ugt(
C) &&
"Expected simplify of compare");
2229 unsigned CmpLZ =
C.countLeadingZeros();
2236 const APInt *ShiftAmtC;
2244 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2247 bool IsExact = Shr->
isExact();
2259 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2264 APInt ShiftedC = (
C + 1).
shl(ShAmtVal) - 1;
2265 if (!
C.isMaxSignedValue() && !(
C + 1).
shl(ShAmtVal).isMinSignedValue() &&
2266 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2273 APInt ShiftedC = (
C + 1).
shl(ShAmtVal) - 1;
2274 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2275 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2283 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2298 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2303 APInt ShiftedC = (
C + 1).
shl(ShAmtVal) - 1;
2304 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2309 if (!Cmp.isEquality())
2317 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2318 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2319 "Expected icmp+shr simplify did not occur.");
2365 const APInt *DivisorC;
2374 !
C.isStrictlyPositive()))
2411 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2416 "icmp ugt X, UINT_MAX should have been simplified already.");
2423 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2439 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2449 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2450 (!DivIsSigned ||
C.isMinSignedValue())) {
2475 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2494 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2507 int LoOverflow = 0, HiOverflow = 0;
2508 APInt LoBound, HiBound;
2513 HiOverflow = LoOverflow = ProdOV;
2519 }
else if (C2->isStrictlyPositive()) {
2522 LoBound = -(RangeSize - 1);
2523 HiBound = RangeSize;
2524 }
else if (
C.isStrictlyPositive()) {
2526 HiOverflow = LoOverflow = ProdOV;
2532 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2534 APInt DivNeg = -RangeSize;
2535 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2538 }
else if (C2->isNegative()) {
2543 LoBound = RangeSize + 1;
2544 HiBound = -RangeSize;
2545 if (HiBound == *C2) {
2549 }
else if (
C.isStrictlyPositive()) {
2552 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2558 LoOverflow = HiOverflow = ProdOV;
2571 if (LoOverflow && HiOverflow)
2572 return replaceInstUsesWith(Cmp,
Builder.getFalse());
2579 return replaceInstUsesWith(
2580 Cmp, insertRangeTest(
X, LoBound, HiBound, DivIsSigned,
true));
2582 if (LoOverflow && HiOverflow)
2583 return replaceInstUsesWith(Cmp,
Builder.getTrue());
2590 return replaceInstUsesWith(
2591 Cmp, insertRangeTest(
X, LoBound, HiBound, DivIsSigned,
false));
2594 if (LoOverflow == +1)
2595 return replaceInstUsesWith(Cmp,
Builder.getTrue());
2596 if (LoOverflow == -1)
2597 return replaceInstUsesWith(Cmp,
Builder.getFalse());
2601 if (HiOverflow == +1)
2602 return replaceInstUsesWith(Cmp,
Builder.getFalse());
2603 if (HiOverflow == -1)
2604 return replaceInstUsesWith(Cmp,
Builder.getTrue());
2636 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2646 if (Cmp.isEquality() &&
C.isZero() &&
2682 (*C2 & (
C - 1)) == (
C - 1))
2702 Value *
Y = Add->getOperand(1);
2708 Value *
X = Add->getOperand(0);
2709 Type *Ty = Add->getType();
2715 if ((Add->hasNoSignedWrap() &&
2717 (Add->hasNoUnsignedWrap() &&
2721 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
2732 const APInt &Lower = CR.getLower();
2733 if (Cmp.isSigned()) {
2734 if (Lower.isSignMask())
2736 if (
Upper.isSignMask())
2739 if (Lower.isMinValue())
2741 if (
Upper.isMinValue())
2767 if (!Add->hasOneUse())
2810 Value *EqualVal =
SI->getTrueValue();
2811 Value *UnequalVal =
SI->getFalseValue();
2834 auto FlippedStrictness =
2836 PredB, cast<Constant>(RHS2));
2837 if (!FlippedStrictness)
2840 "basic correctness failure");
2841 RHS2 = FlippedStrictness->second;
2853 assert(
C &&
"Cmp RHS should be a constant int!");
2859 Value *OrigLHS, *OrigRHS;
2860 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
2861 if (Cmp.hasOneUse() &&
2862 matchThreeWayIntCompare(
Select, OrigLHS, OrigRHS, C1LessThan, C2Equal,
2864 assert(C1LessThan && C2Equal && C3GreaterThan);
2866 bool TrueWhenLessThan =
2869 bool TrueWhenEqual =
2872 bool TrueWhenGreaterThan =
2885 if (TrueWhenLessThan)
2891 if (TrueWhenGreaterThan)
2895 return replaceInstUsesWith(Cmp,
Cond);
2901 auto *
Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
2906 Value *Op1 = Cmp.getOperand(1);
2956 Type *XType =
X->getType();
2961 if (
auto *XVTy = dyn_cast<VectorType>(XType))
2977 if (DstType->
isPointerTy() && (isa<Constant>(Op1) || isa<BitCastInst>(Op1))) {
2980 if (
auto *BC2 = dyn_cast<BitCastInst>(Op1))
2981 Op1 = BC2->getOperand(0);
2983 Op1 =
Builder.CreateBitCast(Op1, SrcType);
2984 return new ICmpInst(Pred, BCSrcOp, Op1);
2999 if (Cmp.isEquality() &&
C->isAllOnes() &&
Bitcast->hasOneUse() &&
3000 isFreeToInvert(BCSrcOp, BCSrcOp->
hasOneUse())) {
3009 if (Cmp.isEquality() &&
C->isZero() &&
Bitcast->hasOneUse() &&
3011 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3012 Type *NewType =
Builder.getIntNTy(VecTy->getPrimitiveSizeInBits());
3030 auto *VecTy = cast<VectorType>(SrcType);
3031 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3032 if (
C->isSplat(EltTy->getBitWidth())) {
3039 Value *Extract =
Builder.CreateExtractElement(Vec, Elem);
3041 return new ICmpInst(Pred, Extract, NewC);
3054 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3055 if (
Instruction *
I = foldICmpBinOpWithConstant(Cmp, BO, *
C))
3058 if (
auto *
SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3062 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3066 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3070 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3071 if (
Instruction *
I = foldICmpIntrinsicWithConstant(Cmp, II, *
C))
3076 return foldICmpInstWithConstantAllowUndef(Cmp, *
C);
3087 if (!Cmp.isEquality())
3092 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3096 case Instruction::SRem:
3109 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3112 }
else if (
C.isZero()) {
3115 if (
Value *NegVal = dyn_castNegVal(BOp1))
3116 return new ICmpInst(Pred, BOp0, NegVal);
3117 if (
Value *NegVal = dyn_castNegVal(BOp0))
3118 return new ICmpInst(Pred, NegVal, BOp1);
3122 return new ICmpInst(Pred, BOp0, Neg);
3127 case Instruction::Xor:
3129 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3133 }
else if (
C.isZero()) {
3135 return new ICmpInst(Pred, BOp0, BOp1);
3139 case Instruction::Or: {
3151 case Instruction::And: {
3161 case Instruction::UDiv:
3165 return new ICmpInst(NewPred, BOp1, BOp0);
3185 if (
C.isZero() ||
C.isMinSignedValue())
3189 case Intrinsic::bswap:
3194 case Intrinsic::ctlz:
3195 case Intrinsic::cttz: {
3204 unsigned Num =
C.getLimitedValue(
BitWidth);
3209 APInt Mask2 = IsTrailing
3218 case Intrinsic::ctpop: {
3221 bool IsZero =
C.isZero();
3230 case Intrinsic::fshl:
3231 case Intrinsic::fshr:
3233 const APInt *RotAmtC;
3244 case Intrinsic::uadd_sat: {
3253 case Intrinsic::usub_sat: {
3271 assert(Cmp.isEquality());
3274 Value *Op0 = Cmp.getOperand(0);
3275 Value *Op1 = Cmp.getOperand(1);
3276 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3277 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3278 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3281 switch (IIOp0->getIntrinsicID()) {
3282 case Intrinsic::bswap:
3283 case Intrinsic::bitreverse:
3286 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3287 case Intrinsic::fshl:
3288 case Intrinsic::fshr:
3291 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3293 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3295 if (IIOp0->getOperand(2) != IIOp1->getOperand(2))
3297 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3312 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3313 switch (II->getIntrinsicID()) {
3316 case Intrinsic::fshl:
3317 case Intrinsic::fshr:
3318 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3320 if (
C.isZero() ||
C.isAllOnes())
3321 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3335 case Instruction::Xor:
3339 case Instruction::And:
3343 case Instruction::Or:
3351 case Instruction::Shl:
3355 case Instruction::LShr:
3356 case Instruction::AShr:
3360 case Instruction::SRem:
3364 case Instruction::UDiv:
3368 case Instruction::SDiv:
3372 case Instruction::Sub:
3385 return foldICmpBinOpEqualityWithConstant(Cmp, BO,
C);
3392 if (Cmp.isEquality())
3393 return foldICmpEqIntrinsicWithConstant(Cmp, II,
C);
3399 case Intrinsic::ctpop: {
3411 case Intrinsic::ctlz: {
3414 unsigned Num =
C.getLimitedValue();
3422 unsigned Num =
C.getLimitedValue();
3429 case Intrinsic::cttz: {
3460 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3461 Constant *RHSC = dyn_cast<Constant>(Op1);
3467 case Instruction::GetElementPtr:
3470 cast<GetElementPtrInst>(LHSI)->hasAllZeroIndices())
3475 case Instruction::PHI:
3483 case Instruction::IntToPtr:
3495 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
3498 foldCmpLoadFromIndexedGlobal(cast<LoadInst>(LHSI),
GEP, GV,
I))
3511 auto SimplifyOp = [&](
Value *
Op,
bool SelectCondIsTrue) ->
Value * {
3515 RHS,
DL, SelectCondIsTrue))
3521 Value *Op1 = SimplifyOp(
SI->getOperand(1),
true);
3523 CI = dyn_cast<ConstantInt>(Op1);
3525 Value *Op2 = SimplifyOp(
SI->getOperand(2),
false);
3527 CI = dyn_cast<ConstantInt>(Op2);
3536 bool Transform =
false;
3539 else if (Op1 || Op2) {
3541 if (
SI->hasOneUse())
3544 else if (CI && !CI->
isZero())
3548 Transform = replacedSelectWithOperand(
SI, &
I, Op1 ? 2 : 1);
3552 Op1 =
Builder.CreateICmp(Pred,
SI->getOperand(1),
RHS,
I.getName());
3554 Op2 =
Builder.CreateICmp(Pred,
SI->getOperand(2),
RHS,
I.getName());
3591 case ICmpInst::Predicate::ICMP_EQ:
3593 DstPred = ICmpInst::Predicate::ICMP_ULE;
3595 case ICmpInst::Predicate::ICMP_NE:
3597 DstPred = ICmpInst::Predicate::ICMP_UGT;
3599 case ICmpInst::Predicate::ICMP_ULT:
3602 DstPred = ICmpInst::Predicate::ICMP_UGT;
3604 case ICmpInst::Predicate::ICMP_UGE:
3607 DstPred = ICmpInst::Predicate::ICMP_ULE;
3609 case ICmpInst::Predicate::ICMP_SLT:
3616 DstPred = ICmpInst::Predicate::ICMP_SGT;
3618 case ICmpInst::Predicate::ICMP_SGE:
3625 DstPred = ICmpInst::Predicate::ICMP_SLE;
3627 case ICmpInst::Predicate::ICMP_SGT:
3628 case ICmpInst::Predicate::ICMP_SLE:
3630 case ICmpInst::Predicate::ICMP_UGT:
3631 case ICmpInst::Predicate::ICMP_ULE:
3641 Type *OpTy =
M->getType();
3642 auto *VecC = dyn_cast<Constant>(
M);
3643 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
3644 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
3645 Constant *SafeReplacementConstant =
nullptr;
3646 for (
unsigned i = 0,
e = OpVTy->getNumElements();
i !=
e; ++
i) {
3647 if (!isa<UndefValue>(VecC->getAggregateElement(
i))) {
3652 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
3656 return Builder.CreateICmp(DstPred,
X,
M);
3689 const APInt &MaskedBits = *C0;
3690 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
3694 case ICmpInst::Predicate::ICMP_EQ:
3698 DstPred = ICmpInst::Predicate::ICMP_ULT;
3700 case ICmpInst::Predicate::ICMP_NE:
3704 DstPred = ICmpInst::Predicate::ICMP_UGE;
3711 auto *XType =
X->getType();
3712 const unsigned XBitWidth = XType->getScalarSizeInBits();
3714 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
3745 !
I.getOperand(0)->hasOneUse())
3770 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
3771 "We did not look past any shifts while matching XShift though.");
3772 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
3779 auto XShiftOpcode = XShift->
getOpcode();
3780 if (XShiftOpcode == YShift->
getOpcode())
3783 Value *
X, *XShAmt, *
Y, *YShAmt;
3790 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
3792 if (!
match(
I.getOperand(0),
3818 unsigned MaximalPossibleTotalShiftAmount =
3821 APInt MaximalRepresentableShiftAmount =
3823 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
3827 auto *NewShAmt = dyn_cast_or_null<Constant>(
3837 if (!
match(NewShAmt,
3839 APInt(WidestBitWidth, WidestBitWidth))))
3844 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
3850 ? NewShAmt->getSplatValue()
3853 if (NewShAmtSplat &&
3859 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
3863 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3864 if (MaxActiveBits <= 1)
3870 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
3874 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
3875 if (MaxActiveBits <= 1)
3878 if (NewShAmtSplat) {
3881 if (AdjNewShAmt.
ule(MinLeadZero))
3895 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
3899 return Builder.CreateICmp(
I.getPredicate(),
T1,
3917 if (!
I.isEquality() &&
3926 case ICmpInst::Predicate::ICMP_ULT:
3927 NeedNegation =
false;
3929 case ICmpInst::Predicate::ICMP_UGE:
3930 NeedNegation =
true;
3936 if (
I.isEquality() &&
3945 NeedNegation = Pred == ICmpInst::Predicate::ICMP_EQ;
3953 if (MulHadOtherUses)
3958 ? Intrinsic::umul_with_overflow
3959 : Intrinsic::smul_with_overflow,
3966 if (MulHadOtherUses)
3967 replaceInstUsesWith(*
Mul,
Builder.CreateExtractValue(Call, 0,
"mul.val"));
3969 Value *Res =
Builder.CreateExtractValue(Call, 1,
"mul.ov");
3971 Res =
Builder.CreateNot(Res,
"mul.not.ov");
3975 if (MulHadOtherUses)
3976 eraseInstFromFunction(*
Mul);
4004 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4060 return new ICmpInst(NewPred, Op1, Zero);
4069 return new ICmpInst(NewPred, Op0, Zero);
4073 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
4074 if (BO0 && isa<OverflowingBinaryOperator>(BO0))
4079 if (BO1 && isa<OverflowingBinaryOperator>(BO1))
4087 Value *A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr;
4099 if ((A == Op1 ||
B == Op1) && NoOp0WrapProblem)
4100 return new ICmpInst(Pred, A == Op1 ?
B : A,
4105 if ((
C == Op0 ||
D == Op0) && NoOp1WrapProblem)
4110 if (A &&
C && (A ==
C || A ==
D ||
B ==
C ||
B ==
D) && NoOp0WrapProblem &&
4118 }
else if (A ==
D) {
4122 }
else if (
B ==
C) {
4203 if (A &&
C && NoOp0WrapProblem && NoOp1WrapProblem &&
4205 const APInt *AP1, *AP2;
4212 if (AP1Abs.
uge(AP2Abs)) {
4213 APInt Diff = *AP1 - *AP2;
4217 Value *NewAdd =
Builder.CreateAdd(A, C3,
"", HasNUW, HasNSW);
4220 APInt Diff = *AP2 - *AP1;
4224 Value *NewAdd =
Builder.CreateAdd(
C, C3,
"", HasNUW, HasNSW);
4225 return new ICmpInst(Pred, A, NewAdd);
4233 return new ICmpInst(Pred, A, NewAdd);
4243 if (BO0 && BO0->
getOpcode() == Instruction::Sub) {
4247 if (BO1 && BO1->
getOpcode() == Instruction::Sub) {
4253 if (A == Op1 && NoOp0WrapProblem)
4256 if (
C == Op0 && NoOp1WrapProblem)
4276 if (
B &&
D &&
B ==
D && NoOp0WrapProblem && NoOp1WrapProblem)
4280 if (A &&
C && A ==
C && NoOp0WrapProblem && NoOp1WrapProblem)
4287 if (
Constant *RHSC = dyn_cast<Constant>(Op1))
4288 if (RHSC->isNotMinSignedValue())
4289 return new ICmpInst(
I.getSwappedPredicate(),
X,
4300 if (!
C->countTrailingZeros() ||
4311 else if (BO1 && BO1->
getOpcode() == Instruction::SRem &&
4341 case Instruction::Sub:
4342 case Instruction::Xor: {
4349 if (
C->isSignMask()) {
4355 if (BO0->
getOpcode() == Instruction::Xor &&
C->isMaxSignedValue()) {
4357 NewPred =
I.getSwappedPredicate(NewPred);
4364 if (!
I.isEquality())
4372 if (
unsigned TZs =
C->countTrailingZeros()) {
4378 return new ICmpInst(Pred, And1, And2);
4383 case Instruction::UDiv:
4384 case Instruction::LShr:
4389 case Instruction::SDiv:
4394 case Instruction::AShr:
4399 case Instruction::Shl: {
4404 if (!NSW &&
I.isSigned())
4422 if (
Value *V = foldMultiplicationOverflowCheck(
I))
4423 return replaceInstUsesWith(
I, V);
4426 return replaceInstUsesWith(
I, V);
4429 return replaceInstUsesWith(
I, V);
4432 return replaceInstUsesWith(
I, V);
4440 Value *Op0 = Cmp.getOperand(0);
4441 Value *
X = Cmp.getOperand(1);
4449 Pred = Cmp.getSwappedPredicate();
4525 if (!
I.isEquality())
4528 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4532 if (A == Op1 ||
B == Op1) {
4533 Value *OtherVal = A == Op1 ?
B : A;
4561 Value *OtherVal = A == Op0 ?
B : A;
4568 Value *
X =
nullptr, *
Y =
nullptr, *Z =
nullptr;
4574 }
else if (A ==
D) {