33using namespace PatternMatch;
35#define DEBUG_TYPE "instcombine"
44 const APInt &In2,
bool IsSigned =
false) {
47 Result = In1.
sadd_ov(In2, Overflow);
49 Result = In1.
uadd_ov(In2, Overflow);
57 const APInt &In2,
bool IsSigned =
false) {
60 Result = In1.
ssub_ov(In2, Overflow);
62 Result = In1.
usub_ov(In2, Overflow);
70 for (
auto *U :
I.users())
71 if (isa<BranchInst>(U))
81 if (!ICmpInst::isSigned(Pred))
88 if (Pred == ICmpInst::ICMP_SLT) {
89 Pred = ICmpInst::ICMP_SLE;
92 }
else if (
C.isAllOnes()) {
93 if (Pred == ICmpInst::ICMP_SGT) {
94 Pred = ICmpInst::ICMP_SGE;
113 if (
LI->isVolatile() ||
LI->getType() !=
GEP->getResultElementType() ||
119 if (!isa<ConstantArray>(
Init) && !isa<ConstantDataArray>(
Init))
122 uint64_t ArrayElementCount =
Init->getType()->getArrayNumElements();
131 if (
GEP->getNumOperands() < 3 || !isa<ConstantInt>(
GEP->getOperand(1)) ||
132 !cast<ConstantInt>(
GEP->getOperand(1))->isZero() ||
133 isa<Constant>(
GEP->getOperand(2)))
141 Type *EltTy =
Init->getType()->getArrayElementType();
142 for (
unsigned i = 3, e =
GEP->getNumOperands(); i != e; ++i) {
148 if ((
unsigned)IdxVal != IdxVal)
151 if (
StructType *STy = dyn_cast<StructType>(EltTy))
152 EltTy = STy->getElementType(IdxVal);
153 else if (
ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
154 if (IdxVal >= ATy->getNumElements())
156 EltTy = ATy->getElementType();
164 enum { Overdefined = -3, Undefined = -2 };
173 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
177 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
185 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
194 for (
unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
200 if (!LaterIndices.
empty()) {
215 CompareRHS,
DL, &
TLI);
217 if (isa<UndefValue>(
C)) {
220 if (TrueRangeEnd == (
int)i - 1)
222 if (FalseRangeEnd == (
int)i - 1)
229 if (!isa<ConstantInt>(
C))
234 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
239 if (FirstTrueElement == Undefined)
240 FirstTrueElement = TrueRangeEnd = i;
243 if (SecondTrueElement == Undefined)
244 SecondTrueElement = i;
246 SecondTrueElement = Overdefined;
249 if (TrueRangeEnd == (
int)i - 1)
252 TrueRangeEnd = Overdefined;
256 if (FirstFalseElement == Undefined)
257 FirstFalseElement = FalseRangeEnd = i;
260 if (SecondFalseElement == Undefined)
261 SecondFalseElement = i;
263 SecondFalseElement = Overdefined;
266 if (FalseRangeEnd == (
int)i - 1)
269 FalseRangeEnd = Overdefined;
274 if (i < 64 && IsTrueForElt)
275 MagicBitvector |= 1ULL << i;
280 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
281 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
282 FalseRangeEnd == Overdefined)
293 if (!
GEP->isInBounds()) {
296 if (
Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
307 unsigned ElementSize =
311 Value *Mask = ConstantInt::get(
Idx->getType(), -1);
320 if (SecondTrueElement != Overdefined) {
323 if (FirstTrueElement == Undefined)
326 Value *FirstTrueIdx = ConstantInt::get(
Idx->getType(), FirstTrueElement);
329 if (SecondTrueElement == Undefined)
334 Value *SecondTrueIdx = ConstantInt::get(
Idx->getType(), SecondTrueElement);
336 return BinaryOperator::CreateOr(C1, C2);
341 if (SecondFalseElement != Overdefined) {
344 if (FirstFalseElement == Undefined)
347 Value *FirstFalseIdx = ConstantInt::get(
Idx->getType(), FirstFalseElement);
350 if (SecondFalseElement == Undefined)
355 Value *SecondFalseIdx =
356 ConstantInt::get(
Idx->getType(), SecondFalseElement);
358 return BinaryOperator::CreateAnd(C1, C2);
363 if (TrueRangeEnd != Overdefined) {
364 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
368 if (FirstTrueElement) {
369 Value *Offs = ConstantInt::get(
Idx->getType(), -FirstTrueElement);
374 ConstantInt::get(
Idx->getType(), TrueRangeEnd - FirstTrueElement + 1);
379 if (FalseRangeEnd != Overdefined) {
380 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
383 if (FirstFalseElement) {
384 Value *Offs = ConstantInt::get(
Idx->getType(), -FirstFalseElement);
389 ConstantInt::get(
Idx->getType(), FalseRangeEnd - FirstFalseElement);
402 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
436 while (!WorkList.
empty()) {
439 while (!WorkList.
empty()) {
440 if (Explored.
size() >= 100)
450 if (!isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
455 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
457 auto IsNonConst = [](
Value *V) {
return !isa<ConstantInt>(V); };
458 if (!
GEP->isInBounds() ||
count_if(
GEP->indices(), IsNonConst) > 1)
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())
511 if (
auto *
PHI = dyn_cast<PHINode>(V)) {
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();
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))
561 PHI->getName() +
".idx",
PHI->getIterator());
566 for (
Value *Val : Explored) {
570 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
574 if (isa<ConstantInt>(
Op) && cast<ConstantInt>(
Op)->
isZero())
575 NewInsts[
GEP] = OffsetV;
578 Op, OffsetV,
GEP->getOperand(0)->getName() +
".add");
581 if (isa<PHINode>(Val))
588 for (
Value *Val : Explored) {
593 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
595 for (
unsigned I = 0,
E =
PHI->getNumIncomingValues();
I <
E; ++
I) {
596 Value *NewIncoming =
PHI->getIncomingValue(
I);
599 NewIncoming = NewInsts[NewIncoming];
606 for (
Value *Val : Explored) {
613 Builder.
getInt8Ty(),
Base, NewInsts[Val], Val->getName() +
".ptr");
620 return NewInsts[Start];
683 if (!isa<GetElementPtrInst>(
RHS))
695 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
717 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
722 cast<Constant>(
RHS),
Base->getType()));
726 if (PtrBase != GEPRHS->getOperand(0)) {
727 bool IndicesTheSame =
730 GEPRHS->getPointerOperand()->getType() &&
734 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
735 IndicesTheSame =
false;
748 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
750 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
754 Value *LOffset = EmitGEPOffset(GEPLHS);
755 Value *ROffset = EmitGEPOffset(GEPRHS);
762 if (LHSIndexTy != RHSIndexTy) {
781 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
785 unsigned NumDifferences = 0;
786 unsigned DiffOperand = 0;
787 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
788 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
790 Type *RHSType = GEPRHS->getOperand(i)->getType();
801 if (NumDifferences++)
break;
805 if (NumDifferences == 0)
809 else if (NumDifferences == 1 && GEPsInBounds) {
811 Value *RHSV = GEPRHS->getOperand(DiffOperand);
820 auto *Inst = dyn_cast<Instruction>(
GEP);
827 if (Inst && !
GEP->hasOneUse() && !
GEP->hasAllConstantIndices() &&
828 !
GEP->getSourceElementType()->isIntegerTy(8)) {
831 GEP->getPointerOperand(),
832 Offset,
"", GEPsInBounds));
839 Value *L = EmitGEPOffsetAndRewrite(GEPLHS);
840 Value *R = EmitGEPOffsetAndRewrite(GEPRHS);
867 bool Captured =
false;
872 CmpCaptureTracker(
AllocaInst *Alloca) : Alloca(Alloca) {}
874 void tooManyUses()
override { Captured =
true; }
876 bool captured(
const Use *U)
override {
877 auto *ICmp = dyn_cast<ICmpInst>(U->getUser());
885 auto Res = ICmps.
insert({ICmp, 0});
886 Res.first->second |= 1u << U->getOperandNo();
895 CmpCaptureTracker Tracker(Alloca);
897 if (Tracker.Captured)
900 bool Changed =
false;
901 for (
auto [ICmp,
Operands] : Tracker.ICmps) {
907 auto *Res = ConstantInt::get(
933 assert(!!
C &&
"C should not be zero!");
939 Constant *R = ConstantInt::get(
X->getType(),
949 ConstantInt::get(
X->getType(), -
C));
961 ConstantInt::get(
X->getType(),
SMax -
C));
972 ConstantInt::get(
X->getType(),
SMax - (
C - 1)));
981 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
984 if (
I.getPredicate() ==
I.ICMP_NE)
993 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1005 return getICmp(
I.ICMP_UGT,
A,
1006 ConstantInt::get(
A->getType(), AP2.
logBase2()));
1018 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1022 return getICmp(
I.ICMP_UGE,
A, ConstantInt::get(
A->getType(), Shift));
1023 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1024 }
else if (AP1 == AP2.
lshr(Shift)) {
1025 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1031 auto *TorF = ConstantInt::get(
I.getType(),
I.getPredicate() ==
I.ICMP_NE);
1040 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1043 if (
I.getPredicate() ==
I.ICMP_NE)
1054 if (!AP1 && AP2TrailingZeros != 0)
1057 ConstantInt::get(
A->getType(), AP2.
getBitWidth() - AP2TrailingZeros));
1065 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1066 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1070 auto *TorF = ConstantInt::get(
I.getType(),
I.getPredicate() ==
I.ICMP_NE);
1091 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1099 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1123 if (U == AddWithCst)
1141 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1170 if (!
I.isEquality())
1201 APInt(XBitWidth, XBitWidth - 1))))
1203 }
else if (isa<BinaryOperator>(Val) &&
1228 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1230 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1247 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1259 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1265 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1267 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1268 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1276 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1281 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1313 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1326 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1327 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1329 for (
Value *V : Phi->incoming_values()) {
1338 for (
auto [V, Pred] :
zip(Ops, Phi->blocks()))
1353 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1386 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1391 if (Cmp.hasOneUse() &&
1405 if (!
match(BI->getCondition(),
1411 if (
auto *V = handleDomCond(DomPred, DomC))
1431 if (
C.isOne() &&
C.getBitWidth() > 1) {
1436 ConstantInt::get(V->getType(), 1));
1439 Type *SrcTy =
X->getType();
1450 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1451 return new ICmpInst(NewPred,
Y, ConstantInt::get(SrcTy, DstBits));
1456 return new ICmpInst(Pred,
Y, ConstantInt::get(SrcTy,
C.logBase2()));
1459 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1462 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1466 Constant *WideC = ConstantInt::get(SrcTy,
C.zext(SrcBits));
1475 if ((Known.
Zero | Known.
One).countl_one() >= SrcBits - DstBits) {
1477 APInt NewRHS =
C.zext(SrcBits);
1479 return new ICmpInst(Pred,
X, ConstantInt::get(SrcTy, NewRHS));
1487 const APInt *ShAmtC;
1511 bool YIsZext =
false;
1514 if (
X->getType() !=
Y->getType() &&
1515 (!Cmp.getOperand(0)->hasOneUse() || !Cmp.getOperand(1)->hasOneUse()))
1517 if (!isDesirableIntType(
X->getType()->getScalarSizeInBits()) &&
1518 isDesirableIntType(
Y->getType()->getScalarSizeInBits())) {
1520 Pred = Cmp.getSwappedPredicate(Pred);
1531 Type *TruncTy = Cmp.getOperand(0)->getType();
1536 if (isDesirableIntType(TruncBits) &&
1537 !isDesirableIntType(
X->getType()->getScalarSizeInBits()))
1572 bool TrueIfSigned =
false;
1589 if (
Xor->hasOneUse()) {
1591 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1592 Pred = Cmp.getFlippedSignednessPredicate();
1593 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(),
C ^ *XorC));
1598 Pred = Cmp.getFlippedSignednessPredicate();
1599 Pred = Cmp.getSwappedPredicate(Pred);
1600 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(),
C ^ *XorC));
1607 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1610 if (*XorC ==
C && (
C + 1).isPowerOf2())
1615 if (*XorC == -
C &&
C.isPowerOf2())
1617 ConstantInt::get(
X->getType(), ~
C));
1619 if (*XorC ==
C && (-
C).isPowerOf2())
1621 ConstantInt::get(
X->getType(), ~
C));
1643 const APInt *ShiftC;
1648 Type *XType =
X->getType();
1654 return new ICmpInst(Pred,
Add, ConstantInt::get(XType, Bound));
1663 if (!Shift || !Shift->
isShift())
1671 unsigned ShiftOpcode = Shift->
getOpcode();
1672 bool IsShl = ShiftOpcode == Instruction::Shl;
1675 APInt NewAndCst, NewCmpCst;
1676 bool AnyCmpCstBitsShiftedOut;
1677 if (ShiftOpcode == Instruction::Shl) {
1685 NewCmpCst = C1.
lshr(*C3);
1686 NewAndCst = C2.
lshr(*C3);
1687 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1688 }
else if (ShiftOpcode == Instruction::LShr) {
1693 NewCmpCst = C1.
shl(*C3);
1694 NewAndCst = C2.
shl(*C3);
1695 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1701 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1702 NewCmpCst = C1.
shl(*C3);
1703 NewAndCst = C2.
shl(*C3);
1704 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1705 if (NewAndCst.
ashr(*C3) != C2)
1709 if (AnyCmpCstBitsShiftedOut) {
1719 Shift->
getOperand(0), ConstantInt::get(
And->getType(), NewAndCst));
1720 return new ICmpInst(Cmp.getPredicate(),
1721 NewAnd, ConstantInt::get(
And->getType(), NewCmpCst));
1752 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1754 return new TruncInst(
And->getOperand(0), Cmp.getType());
1762 if (!
And->hasOneUse())
1765 if (Cmp.isEquality() && C1.
isZero()) {
1783 Constant *NegBOC = ConstantInt::get(
And->getType(), -NewC2);
1785 return new ICmpInst(NewPred,
X, NegBOC);
1803 if (!Cmp.getType()->isVectorTy()) {
1804 Type *WideType = W->getType();
1806 Constant *ZextC1 = ConstantInt::get(WideType, C1.
zext(WideScalarBits));
1807 Constant *ZextC2 = ConstantInt::get(WideType, C2->
zext(WideScalarBits));
1809 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1820 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1822 Constant *One = cast<Constant>(
And->getOperand(1));
1827 unsigned UsesRemoved = 0;
1828 if (
And->hasOneUse())
1830 if (
Or->hasOneUse())
1837 if (UsesRemoved >= RequireUsesRemoved) {
1841 One,
Or->getName());
1853 if (!Cmp.getParent()->getParent()->hasFnAttribute(
1854 Attribute::NoImplicitFloat) &&
1857 Type *FPType = V->getType()->getScalarType();
1859 APInt ExponentMask =
1861 if (C1 == ExponentMask) {
1894 Constant *MinSignedC = ConstantInt::get(
1898 return new ICmpInst(NewPred,
X, MinSignedC);
1907 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1908 if (
auto *
LI = dyn_cast<LoadInst>(
X))
1909 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
LI->getOperand(0)))
1910 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1915 if (!Cmp.isEquality())
1921 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1924 return new ICmpInst(NewPred,
X,
SubOne(cast<Constant>(Cmp.getOperand(1))));
1937 assert(Cmp.isEquality() &&
"Not expecting non-equality predicates");
1939 const APInt *TC, *FC;
1956 X->getType()->isIntOrIntVectorTy(1) && (
C.isZero() ||
C.isOne())) {
1962 return BinaryOperator::CreateAnd(TruncY,
X);
1994 while (!WorkList.
empty()) {
1995 auto MatchOrOperatorArgument = [&](
Value *OrOperatorArgument) {
1998 if (
match(OrOperatorArgument,
2004 if (
match(OrOperatorArgument,
2014 Value *OrOperatorLhs, *OrOperatorRhs;
2016 if (!
match(CurrentValue,
2021 MatchOrOperatorArgument(OrOperatorRhs);
2022 MatchOrOperatorArgument(OrOperatorLhs);
2028 CmpValues.
rbegin()->second);
2030 for (
auto It = CmpValues.
rbegin() + 1; It != CmpValues.
rend(); ++It) {
2032 LhsCmp = Builder.
CreateBinOp(BOpc, LhsCmp, RhsCmp);
2048 ConstantInt::get(V->getType(), 1));
2051 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
2053 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
2054 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
2059 return new ICmpInst(Pred, OrOp0, OrOp1);
2066 if (
Or->hasOneUse()) {
2068 Constant *NewC = ConstantInt::get(
Or->getType(),
C ^ (*MaskC));
2080 Constant *NewC = ConstantInt::get(
X->getType(), TrueIfSigned ? 1 : 0);
2108 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
2140 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
2141 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2163 if (Cmp.isEquality()) {
2165 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2166 Constant *NewC = ConstantInt::get(MulTy,
C.sdiv(*MulC));
2174 if (
C.urem(*MulC).isZero()) {
2177 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2178 Constant *NewC = ConstantInt::get(MulTy,
C.udiv(*MulC));
2191 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2197 NewC = ConstantInt::get(
2201 "Unexpected predicate");
2202 NewC = ConstantInt::get(
2207 NewC = ConstantInt::get(
2211 "Unexpected predicate");
2212 NewC = ConstantInt::get(
2217 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2228 unsigned TypeBits =
C.getBitWidth();
2229 bool CIsPowerOf2 =
C.isPowerOf2();
2231 if (Cmp.isUnsigned()) {
2244 unsigned CLog2 =
C.logBase2();
2245 return new ICmpInst(Pred,
Y, ConstantInt::get(ShiftType, CLog2));
2246 }
else if (Cmp.isSigned()) {
2247 Constant *BitWidthMinusOne = ConstantInt::get(ShiftType, TypeBits - 1);
2268 const APInt *ShiftVal;
2298 const APInt *ShiftAmt;
2304 unsigned TypeBits =
C.getBitWidth();
2305 if (ShiftAmt->
uge(TypeBits))
2317 APInt ShiftedC =
C.ashr(*ShiftAmt);
2318 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2321 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2322 APInt ShiftedC =
C.ashr(*ShiftAmt);
2323 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2330 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2331 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2332 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2342 APInt ShiftedC =
C.lshr(*ShiftAmt);
2343 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2346 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2347 APInt ShiftedC =
C.lshr(*ShiftAmt);
2348 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2355 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2356 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2357 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2361 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2367 Constant *LShrC = ConstantInt::get(ShType,
C.lshr(*ShiftAmt));
2372 bool TrueIfSigned =
false;
2384 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2386 if ((
C + 1).isPowerOf2() &&
2394 if (
C.isPowerOf2() &&
2411 if (Shl->
hasOneUse() && Amt != 0 &&
C.countr_zero() >= Amt &&
2414 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2417 ConstantInt::get(TruncTy,
C.ashr(*ShiftAmt).trunc(TypeBits - Amt));
2432 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2433 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2435 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2436 const APInt *ShiftValC;
2438 if (Cmp.isEquality())
2456 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2457 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2459 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2467 const APInt *ShiftAmtC;
2473 unsigned TypeBits =
C.getBitWidth();
2475 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2478 bool IsExact = Shr->
isExact();
2489 APInt ShiftedC =
C.shl(ShAmtVal);
2490 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2491 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2495 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2496 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2497 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2498 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2504 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2505 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2506 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2507 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2514 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2524 }
else if (!IsAShr) {
2528 APInt ShiftedC =
C.shl(ShAmtVal);
2529 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2530 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2534 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2535 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2536 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2540 if (!Cmp.isEquality())
2548 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2549 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2550 "Expected icmp+shr simplify did not occur.");
2555 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy,
C << ShAmtVal));
2561 ConstantInt::get(ShrTy, (
C + 1).shl(ShAmtVal)));
2564 ConstantInt::get(ShrTy, (
C + 1).shl(ShAmtVal) - 1));
2571 Constant *Mask = ConstantInt::get(ShrTy, Val);
2573 return new ICmpInst(Pred,
And, ConstantInt::get(ShrTy,
C << ShAmtVal));
2596 const APInt *DivisorC;
2605 !
C.isStrictlyPositive()))
2611 Constant *MaskC = ConstantInt::get(Ty, SignMask | (*DivisorC - 1));
2615 return new ICmpInst(Pred,
And, ConstantInt::get(Ty,
C));
2642 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2647 "icmp ugt X, UINT_MAX should have been simplified already.");
2649 ConstantInt::get(Ty, C2->
udiv(
C + 1)));
2654 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2656 ConstantInt::get(Ty, C2->
udiv(
C)));
2670 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2680 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2681 (!DivIsSigned ||
C.isMinSignedValue())) {
2706 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2725 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2738 int LoOverflow = 0, HiOverflow = 0;
2739 APInt LoBound, HiBound;
2744 HiOverflow = LoOverflow = ProdOV;
2753 LoBound = -(RangeSize - 1);
2754 HiBound = RangeSize;
2755 }
else if (
C.isStrictlyPositive()) {
2757 HiOverflow = LoOverflow = ProdOV;
2763 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2765 APInt DivNeg = -RangeSize;
2766 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2774 LoBound = RangeSize + 1;
2775 HiBound = -RangeSize;
2776 if (HiBound == *C2) {
2780 }
else if (
C.isStrictlyPositive()) {
2783 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2789 LoOverflow = HiOverflow = ProdOV;
2802 if (LoOverflow && HiOverflow)
2806 X, ConstantInt::get(Ty, LoBound));
2809 X, ConstantInt::get(Ty, HiBound));
2813 if (LoOverflow && HiOverflow)
2817 X, ConstantInt::get(Ty, LoBound));
2820 X, ConstantInt::get(Ty, HiBound));
2825 if (LoOverflow == +1)
2827 if (LoOverflow == -1)
2829 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, LoBound));
2832 if (HiOverflow == +1)
2834 if (HiOverflow == -1)
2867 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2869 return new ICmpInst(SwappedPred,
Y, ConstantInt::get(Ty, SubResult));
2877 if (Cmp.isEquality() &&
C.isZero() &&
2913 (*C2 & (
C - 1)) == (
C - 1))
2926 return new ICmpInst(SwappedPred,
Add, ConstantInt::get(Ty, ~
C));
2932 auto FoldConstant = [&](
bool Val) {
2936 cast<VectorType>(Op0->
getType())->getElementCount(), Res);
2940 switch (Table.to_ulong()) {
2942 return FoldConstant(
false);
2972 return FoldConstant(
true);
2995 unsigned BW =
C.getBitWidth();
2996 std::bitset<4> Table;
2997 auto ComputeTable = [&](
bool Op0Val,
bool Op1Val) {
3000 Res += isa<ZExtInst>(Ext0) ? 1 : -1;
3002 Res += isa<ZExtInst>(Ext1) ? 1 : -1;
3006 Table[0] = ComputeTable(
false,
false);
3007 Table[1] = ComputeTable(
false,
true);
3008 Table[2] = ComputeTable(
true,
false);
3009 Table[3] = ComputeTable(
true,
true);
3024 if ((
Add->hasNoSignedWrap() &&
3026 (
Add->hasNoUnsignedWrap() &&
3030 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
3036 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, NewC));
3042 if (Cmp.isSigned()) {
3043 if (
Lower.isSignMask())
3045 if (
Upper.isSignMask())
3048 if (
Lower.isMinValue())
3050 if (
Upper.isMinValue())
3083 if (!
Add->hasOneUse())
3106 ConstantInt::get(Ty, ~
C));
3126 Value *EqualVal = SI->getTrueValue();
3127 Value *UnequalVal = SI->getFalseValue();
3150 auto FlippedStrictness =
3152 PredB, cast<Constant>(RHS2));
3153 if (!FlippedStrictness)
3156 "basic correctness failure");
3157 RHS2 = FlippedStrictness->second;
3169 assert(
C &&
"Cmp RHS should be a constant int!");
3175 Value *OrigLHS, *OrigRHS;
3176 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
3177 if (Cmp.hasOneUse() &&
3180 assert(C1LessThan && C2Equal && C3GreaterThan);
3182 bool TrueWhenLessThan =
3185 bool TrueWhenEqual =
3188 bool TrueWhenGreaterThan =
3201 if (TrueWhenLessThan)
3207 if (TrueWhenGreaterThan)
3217 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3222 Value *Op1 = Cmp.getOperand(1);
3223 Value *BCSrcOp = Bitcast->getOperand(0);
3224 Type *SrcType = Bitcast->getSrcTy();
3225 Type *DstType = Bitcast->getType();
3245 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(), 1));
3272 Type *XType =
X->getType();
3277 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3291 if (!Cmp.getParent()->getParent()->hasFnAttribute(
3292 Attribute::NoImplicitFloat) &&
3317 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse()) {
3318 if (
Value *NotBCSrcOp =
3329 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3331 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3350 auto *VecTy = cast<VectorType>(SrcType);
3351 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3352 if (
C->isSplat(EltTy->getBitWidth())) {
3360 Value *NewC = ConstantInt::get(EltTy,
C->trunc(EltTy->getBitWidth()));
3361 return new ICmpInst(Pred, Extract, NewC);
3374 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3378 if (
auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3382 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3386 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3390 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3397 Value *Cmp0 = Cmp.getOperand(0);
3399 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3401 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3404 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3406 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3421 if (!Cmp.isEquality())
3426 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3430 case Instruction::SRem:
3441 case Instruction::Add: {
3445 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3448 }
else if (
C.isZero()) {
3451 if (
Value *NegVal = dyn_castNegVal(BOp1))
3452 return new ICmpInst(Pred, BOp0, NegVal);
3453 if (
Value *NegVal = dyn_castNegVal(BOp0))
3454 return new ICmpInst(Pred, NegVal, BOp1);
3458 return new ICmpInst(Pred, BOp0, Neg);
3463 case Instruction::Xor:
3465 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3469 }
else if (
C.isZero()) {
3471 return new ICmpInst(Pred, BOp0, BOp1);
3475 case Instruction::Or: {
3487 case Instruction::UDiv:
3488 case Instruction::SDiv:
3498 return new ICmpInst(Pred, BOp0, BOp1);
3501 Instruction::Mul, BO->
getOpcode() == Instruction::SDiv, BOp1,
3502 Cmp.getOperand(1), BO);
3506 return new ICmpInst(Pred, YC, BOp0);
3510 if (BO->
getOpcode() == Instruction::UDiv &&
C.isZero()) {
3513 return new ICmpInst(NewPred, BOp1, BOp0);
3527 "Non-ctpop intrin in ctpop fold");
3568 case Intrinsic::abs:
3571 if (
C.isZero() ||
C.isMinSignedValue())
3575 case Intrinsic::bswap:
3578 ConstantInt::get(Ty,
C.byteSwap()));
3580 case Intrinsic::bitreverse:
3583 ConstantInt::get(Ty,
C.reverseBits()));
3585 case Intrinsic::ctlz:
3586 case Intrinsic::cttz: {
3595 unsigned Num =
C.getLimitedValue(
BitWidth);
3600 APInt Mask2 = IsTrailing
3604 ConstantInt::get(Ty, Mask2));
3609 case Intrinsic::ctpop: {
3612 bool IsZero =
C.isZero();
3621 case Intrinsic::fshl:
3622 case Intrinsic::fshr:
3624 const APInt *RotAmtC;
3630 ? ConstantInt::get(Ty,
C.rotr(*RotAmtC))
3631 : ConstantInt::get(Ty,
C.rotl(*RotAmtC)));
3635 case Intrinsic::umax:
3636 case Intrinsic::uadd_sat: {
3646 case Intrinsic::ssub_sat:
3651 case Intrinsic::usub_sat: {
3671 assert(Cmp.isEquality());
3674 Value *Op0 = Cmp.getOperand(0);
3675 Value *Op1 = Cmp.getOperand(1);
3676 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3677 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3678 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3681 switch (IIOp0->getIntrinsicID()) {
3682 case Intrinsic::bswap:
3683 case Intrinsic::bitreverse:
3686 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3687 case Intrinsic::fshl:
3688 case Intrinsic::fshr: {
3691 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3693 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3695 if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
3696 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3702 unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
3707 Builder.
CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
3709 Op0->
getType(), IIOp0->getIntrinsicID(),
3710 {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
3711 return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
3728 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3729 switch (II->getIntrinsicID()) {
3732 case Intrinsic::fshl:
3733 case Intrinsic::fshr:
3734 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3736 if (
C.isZero() ||
C.isAllOnes())
3737 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3751 case Instruction::Xor:
3755 case Instruction::And:
3759 case Instruction::Or:
3763 case Instruction::Mul:
3767 case Instruction::Shl:
3771 case Instruction::LShr:
3772 case Instruction::AShr:
3776 case Instruction::SRem:
3780 case Instruction::UDiv:
3784 case Instruction::SDiv:
3788 case Instruction::Sub:
3792 case Instruction::Add:
3839 "This function only works with usub_sat and uadd_sat for now!");
3840 case Intrinsic::uadd_sat:
3843 case Intrinsic::usub_sat:
3866 SatValCheck ? Instruction::BinaryOps::Or : Instruction::BinaryOps::And;
3868 std::optional<ConstantRange> Combination;
3869 if (CombiningOp == Instruction::BinaryOps::Or)
3881 Combination->getEquivalentICmp(EquivPred, EquivInt, EquivOffset);
3886 ConstantInt::get(Op1->
getType(), EquivInt));
3899 case Intrinsic::uadd_sat:
3900 case Intrinsic::usub_sat:
3902 Pred, cast<SaturatingInst>(II),
C,
Builder))
3905 case Intrinsic::ctpop: {
3912 if (Cmp.isEquality())
3918 case Intrinsic::ctpop: {
3930 case Intrinsic::ctlz: {
3933 unsigned Num =
C.getLimitedValue();
3941 unsigned Num =
C.getLimitedValue();
3948 case Intrinsic::cttz: {
3970 case Intrinsic::ssub_sat:
3994 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
3995 Constant *RHSC = dyn_cast<Constant>(Op1);
4001 case Instruction::PHI:
4005 case Instruction::IntToPtr:
4014 case Instruction::Load:
4017 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
4033 auto SimplifyOp = [&](
Value *
Op,
bool SelectCondIsTrue) ->
Value * {
4037 SI->getCondition(), Pred,
Op,
RHS,
DL, SelectCondIsTrue))
4038 return ConstantInt::get(
I.getType(), *Impl);
4043 Value *Op1 = SimplifyOp(SI->getOperand(1),
true);
4045 CI = dyn_cast<ConstantInt>(Op1);
4047 Value *Op2 = SimplifyOp(SI->getOperand(2),
false);
4049 CI = dyn_cast<ConstantInt>(Op2);
4058 bool Transform =
false;
4061 else if (Op1 || Op2) {
4063 if (SI->hasOneUse())
4066 else if (CI && !CI->
isZero())
4085 unsigned Depth = 0) {
4088 if (V->getType()->getScalarSizeInBits() == 1)
4096 switch (
I->getOpcode()) {
4097 case Instruction::ZExt:
4100 case Instruction::SExt:
4104 case Instruction::And:
4105 case Instruction::Or:
4112 case Instruction::Xor:
4122 case Instruction::Select:
4126 case Instruction::Shl:
4129 case Instruction::LShr:
4132 case Instruction::AShr:
4136 case Instruction::Add:
4142 case Instruction::Sub:
4148 case Instruction::Call: {
4149 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
4150 switch (II->getIntrinsicID()) {
4153 case Intrinsic::umax:
4154 case Intrinsic::smax:
4155 case Intrinsic::umin:
4156 case Intrinsic::smin:
4161 case Intrinsic::bitreverse:
4193 bool NeedsNot =
false;
4195 auto CheckMask = [&](
Value *V,
bool Not) {
4202 CheckMask(M,
false)) {
4210 !CheckMask(M,
true))
4268 Type *OpTy = M->getType();
4269 auto *VecC = dyn_cast<Constant>(M);
4270 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
4271 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
4272 Constant *SafeReplacementConstant =
nullptr;
4273 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
4274 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
4279 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
4301 const APInt *C0, *C1;
4318 const APInt &MaskedBits = *C0;
4319 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
4340 auto *XType =
X->getType();
4341 const unsigned XBitWidth = XType->getScalarSizeInBits();
4343 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
4374 !
I.getOperand(0)->hasOneUse())
4399 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
4400 "We did not look past any shifts while matching XShift though.");
4401 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
4408 auto XShiftOpcode = XShift->
getOpcode();
4409 if (XShiftOpcode == YShift->
getOpcode())
4412 Value *
X, *XShAmt, *
Y, *YShAmt;
4419 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
4421 if (!
match(
I.getOperand(0),
4447 unsigned MaximalPossibleTotalShiftAmount =
4450 APInt MaximalRepresentableShiftAmount =
4452 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
4456 auto *NewShAmt = dyn_cast_or_null<Constant>(
4461 if (NewShAmt->getType() != WidestTy) {
4471 if (!
match(NewShAmt,
4473 APInt(WidestBitWidth, WidestBitWidth))))
4478 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
4484 ? NewShAmt->getSplatValue()
4487 if (NewShAmtSplat &&
4493 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
4497 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4498 if (MaxActiveBits <= 1)
4504 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
4508 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4509 if (MaxActiveBits <= 1)
4512 if (NewShAmtSplat) {
4515 if (AdjNewShAmt.
ule(MinLeadZero))
4529 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
4551 if (!
I.isEquality() &&
4561 NeedNegation =
false;
4564 NeedNegation =
true;
4570 if (
I.isEquality() &&
4586 bool MulHadOtherUses =
Mul && !
Mul->hasOneUse();
4587 if (MulHadOtherUses)
4592 ? Intrinsic::umul_with_overflow
4593 : Intrinsic::smul_with_overflow,
4600 if (MulHadOtherUses)
4609 if (MulHadOtherUses)
4635 Type *Ty =
X->getType();
4649 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4673 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4708 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4723 if (PredOut != Pred &&
4725 return new ICmpInst(PredOut, Op0, Op1);
4737 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4793 return new ICmpInst(NewPred, Op1, Zero);
4802 return new ICmpInst(NewPred, Op0, Zero);
4806 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
4807 bool Op0HasNUW =
false, Op1HasNUW =
false;
4808 bool Op0HasNSW =
false, Op1HasNSW =
false;
4812 bool &HasNSW,
bool &HasNUW) ->
bool {
4813 if (isa<OverflowingBinaryOperator>(BO)) {
4819 }
else if (BO.
getOpcode() == Instruction::Or) {
4827 Value *
A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr;
4831 NoOp0WrapProblem = hasNoWrapProblem(*BO0, Pred, Op0HasNSW, Op0HasNUW);
4835 NoOp1WrapProblem = hasNoWrapProblem(*BO1, Pred, Op1HasNSW, Op1HasNUW);
4840 if ((
A == Op1 ||
B == Op1) && NoOp0WrapProblem)
4846 if ((
C == Op0 ||
D == Op0) && NoOp1WrapProblem)
4851 if (
A &&
C && (
A ==
C ||
A ==
D ||
B ==
C ||
B ==
D) && NoOp0WrapProblem &&
4859 }
else if (
A ==
D) {
4863 }
else if (
B ==
C) {
4944 if (
A &&
C && NoOp0WrapProblem && NoOp1WrapProblem &&
4946 const APInt *AP1, *AP2;
4953 if (AP1Abs.
uge(AP2Abs)) {
4954 APInt Diff = *AP1 - *AP2;
4957 A, C3,
"", Op0HasNUW && Diff.
ule(*AP1), Op0HasNSW);
4960 APInt Diff = *AP2 - *AP1;
4963 C, C3,
"", Op1HasNUW && Diff.
ule(*AP2), Op1HasNSW);
4982 if (BO0 && BO0->
getOpcode() == Instruction::Sub) {
4986 if (BO1 && BO1->
getOpcode() == Instruction::Sub) {
4992 if (
A == Op1 && NoOp0WrapProblem)
4995 if (
C == Op0 && NoOp1WrapProblem)
5015 if (
B &&
D &&
B ==
D && NoOp0WrapProblem && NoOp1WrapProblem)
5019 if (
A &&
C &&
A ==
C && NoOp0WrapProblem && NoOp1WrapProblem)
5026 if (
Constant *RHSC = dyn_cast<Constant>(Op1))
5027 if (RHSC->isNotMinSignedValue())
5028 return new ICmpInst(
I.getSwappedPredicate(),
X,
5057 if (NonZero && BO0 && BO1 && Op0HasNSW && Op1HasNSW)
5064 if (NonZero && BO0 && BO1 && Op0HasNUW && Op1HasNUW)
5074 else if (BO1 && BO1->
getOpcode() == Instruction::SRem &&
5104 case Instruction::Add:
5105 case Instruction::Sub:
5106 case Instruction::Xor: {
5113 if (
C->isSignMask()) {
5119 if (BO0->
getOpcode() == Instruction::Xor &&
C->isMaxSignedValue()) {
5121 NewPred =
I.getSwappedPredicate(NewPred);
5127 case Instruction::Mul: {
5128 if (!
I.isEquality())
5136 if (
unsigned TZs =
C->countr_zero()) {
5142 return new ICmpInst(Pred, And1, And2);
5147 case Instruction::UDiv:
5148 case Instruction::LShr:
5153 case Instruction::SDiv:
5159 case Instruction::AShr:
5164 case Instruction::Shl: {
5165 bool NUW = Op0HasNUW && Op1HasNUW;
5166 bool NSW = Op0HasNSW && Op1HasNSW;
5169 if (!NSW &&
I.isSigned())
5234 auto IsCondKnownTrue = [](
Value *Val) -> std::optional<bool> {
5236 return std::nullopt;
5241 return std::nullopt;
5245 if (!CmpXZ.has_value() && !CmpYZ.has_value())
5247 if (!CmpXZ.has_value()) {
5253 if (CmpYZ.has_value())
5277 if (!MinMaxCmpXZ.has_value()) {
5285 if (!MinMaxCmpXZ.has_value())
5301 return FoldIntoCmpYZ();
5328 return FoldIntoCmpYZ();
5337 return FoldIntoCmpYZ();
5359 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
5363 if (
I.isEquality()) {
5398 Type *Ty =
A->getType();
5401 ConstantInt::get(Ty, 2))
5403 ConstantInt::get(Ty, 1));
5410 if (!
I.isEquality())
5413 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
5417 if (
A == Op1 ||
B == Op1) {
5418 Value *OtherVal =
A == Op1 ?
B :
A;
5461 Value *OtherVal =
A == Op0 ?
B :
A;
5468 Value *
X =
nullptr, *
Y =
nullptr, *Z =
nullptr;
5474 }
else if (
A ==
D) {
5478 }
else if (
B ==
C) {
5482 }
else if (
B ==
D) {
5509 (Op0->
hasOneUse() || Op1->hasOneUse())) {
5514 MaskC->
countr_one() ==
A->getType()->getScalarSizeInBits())
5520 const APInt *AP1, *AP2;
5529 if (ShAmt < TypeBits && ShAmt != 0) {
5534 return new ICmpInst(NewPred,
Xor, ConstantInt::get(
A->getType(), CmpVal));
5544 if (ShAmt < TypeBits && ShAmt != 0) {
5548 I.getName() +
".mask");
5562 unsigned ASize = cast<IntegerType>(
A->getType())->getPrimitiveSizeInBits();
5564 if (ShAmt < ASize) {
5587 A->getType()->getScalarSizeInBits() ==
BitWidth * 2 &&
5588 (
I.getOperand(0)->hasOneUse() ||
I.getOperand(1)->hasOneUse())) {
5593 Add, ConstantInt::get(
A->getType(),
C.shl(1)));
5617 m_OneUse(m_Intrinsic<Intrinsic::fshr>(
5637 std::optional<bool> IsZero = std::nullopt;
5681 unsigned SrcBits =
X->getType()->getScalarSizeInBits();
5685 Constant *MaskC = ConstantInt::get(
X->getType(),
C->zext(SrcBits));
5693 Constant *MaskC = ConstantInt::get(
X->getType(), (*
C + 1).zext(SrcBits));
5698 if (
auto *II = dyn_cast<IntrinsicInst>(
X)) {
5699 if (II->getIntrinsicID() == Intrinsic::cttz ||
5700 II->getIntrinsicID() == Intrinsic::ctlz) {
5701 unsigned MaxRet = SrcBits;
5721 assert(isa<CastInst>(ICmp.
getOperand(0)) &&
"Expected cast for operand 0");
5722 auto *CastOp0 = cast<CastInst>(ICmp.
getOperand(0));
5727 bool IsSignedExt = CastOp0->getOpcode() == Instruction::SExt;
5728 bool IsSignedCmp = ICmp.
isSigned();
5733 bool IsZext0 = isa<ZExtInst>(ICmp.
getOperand(0));
5734 bool IsZext1 = isa<ZExtInst>(ICmp.
getOperand(1));
5736 if (IsZext0 != IsZext1) {
5741 if (ICmp.
isEquality() &&
X->getType()->isIntOrIntVectorTy(1) &&
5742 Y->getType()->isIntOrIntVectorTy(1))
5749 auto *NonNegInst0 = dyn_cast<PossiblyNonNegInst>(ICmp.
getOperand(0));
5750 auto *NonNegInst1 = dyn_cast<PossiblyNonNegInst>(ICmp.
getOperand(1));
5752 bool IsNonNeg0 = NonNegInst0 && NonNegInst0->hasNonNeg();
5753 bool IsNonNeg1 = NonNegInst1 && NonNegInst1->hasNonNeg();
5755 if ((IsZext0 && IsNonNeg0) || (IsZext1 && IsNonNeg1))
5762 Type *XTy =
X->getType(), *YTy =
Y->getType();
5769 IsSignedExt ? Instruction::SExt : Instruction::ZExt;
5785 if (IsSignedCmp && IsSignedExt)
5798 Type *SrcTy = CastOp0->getSrcTy();
5806 if (IsSignedExt && IsSignedCmp)
5818 if (IsSignedCmp || !IsSignedExt || !isa<ConstantInt>(
C))
5837 Value *SimplifiedOp0 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(0));
5838 Value *SimplifiedOp1 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(1));
5839 if (SimplifiedOp0 || SimplifiedOp1)
5841 SimplifiedOp0 ? SimplifiedOp0 : ICmp.
getOperand(0),
5842 SimplifiedOp1 ? SimplifiedOp1 : ICmp.
getOperand(1));
5844 auto *CastOp0 = dyn_cast<CastInst>(ICmp.
getOperand(0));
5850 Value *Op0Src = CastOp0->getOperand(0);
5851 Type *SrcTy = CastOp0->getSrcTy();
5852 Type *DestTy = CastOp0->getDestTy();
5856 auto CompatibleSizes = [&](
Type *SrcTy,
Type *DestTy) {
5857 if (isa<VectorType>(SrcTy)) {
5858 SrcTy = cast<VectorType>(SrcTy)->getElementType();
5859 DestTy = cast<VectorType>(DestTy)->getElementType();
5863 if (CastOp0->getOpcode() == Instruction::PtrToInt &&
5864 CompatibleSizes(SrcTy, DestTy)) {
5865 Value *NewOp1 =
nullptr;
5866 if (
auto *PtrToIntOp1 = dyn_cast<PtrToIntOperator>(ICmp.
getOperand(1))) {
5867 Value *PtrSrc = PtrToIntOp1->getOperand(0);
5869 NewOp1 = PtrToIntOp1->getOperand(0);
5870 }
else if (
auto *RHSC = dyn_cast<Constant>(ICmp.
getOperand(1))) {
5888 case Instruction::Add:
5889 case Instruction::Sub:
5891 case Instruction::Mul:
5904 case Instruction::Add:
5909 case Instruction::Sub:
5914 case Instruction::Mul:
5923 bool IsSigned,
Value *LHS,
5927 if (OrigI.
isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS))
5937 if (
auto *LHSTy = dyn_cast<VectorType>(
LHS->
getType()))
5952 Result->takeName(&OrigI);
5957 Result->takeName(&OrigI);
5959 if (
auto *Inst = dyn_cast<Instruction>(Result)) {
5961 Inst->setHasNoSignedWrap();
5963 Inst->setHasNoUnsignedWrap();
5986 const APInt *OtherVal,
5990 if (!isa<IntegerType>(MulVal->
getType()))
5993 auto *MulInstr = dyn_cast<Instruction>(MulVal);
5996 assert(MulInstr->getOpcode() == Instruction::Mul);
5998 auto *
LHS = cast<ZExtInst>(MulInstr->getOperand(0)),
5999 *
RHS = cast<ZExtInst>(MulInstr->getOperand(1));
6000 assert(
LHS->getOpcode() == Instruction::ZExt);
6001 assert(
RHS->getOpcode() == Instruction::ZExt);
6005 Type *TyA =
A->getType(), *TyB =
B->getType();
6007 WidthB = TyB->getPrimitiveSizeInBits();
6010 if (WidthB > WidthA) {
6025 if (
TruncInst *TI = dyn_cast<TruncInst>(U)) {
6028 if (TruncWidth > MulWidth)
6032 if (BO->getOpcode() != Instruction::And)
6034 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
6035 const APInt &CVal = CI->getValue();
6051 switch (
I.getPredicate()) {
6058 if (MaxVal.
eq(*OtherVal))
6068 if (MaxVal.
eq(*OtherVal))
6082 if (WidthA < MulWidth)
6084 if (WidthB < MulWidth)
6087 I.getModule(), Intrinsic::umul_with_overflow, MulType);
6099 if (
TruncInst *TI = dyn_cast<TruncInst>(U)) {
6100 if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
6105 assert(BO->getOpcode() == Instruction::And);
6107 ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
6143 switch (
I.getPredicate()) {
6174 assert(DI && UI &&
"Instruction not defined\n");
6185 auto *Usr = cast<Instruction>(U);
6186 if (Usr != UI && !
DT.
dominates(DB, Usr->getParent()))
6197 auto *BI = dyn_cast_or_null<BranchInst>(BB->
getTerminator());
6198 if (!BI || BI->getNumSuccessors() != 2)
6200 auto *IC = dyn_cast<ICmpInst>(BI->getCondition());
6201 if (!IC || (IC->getOperand(0) != SI && IC->getOperand(1) != SI))
6248 const unsigned SIOpd) {
6249 assert((SIOpd == 1 || SIOpd == 2) &&
"Invalid select operand!");
6251 BasicBlock *Succ = SI->getParent()->getTerminator()->getSuccessor(1);
6265 SI->replaceUsesOutsideBlock(SI->getOperand(SIOpd), SI->getParent());
6275 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6324 if (!isa<Constant>(Op0) && Op0Min == Op0Max)
6326 if (!isa<Constant>(Op1) && Op1Min == Op1Max)
6334 if (!Cmp.hasOneUse())
6343 if (!isMinMaxCmp(
I)) {
6348 if (Op1Min == Op0Max)
6353 if (*CmpC == Op0Min + 1)
6355 ConstantInt::get(Op1->getType(), *CmpC - 1));
6365 if (Op1Max == Op0Min)
6370 if (*CmpC == Op0Max - 1)
6372 ConstantInt::get(Op1->getType(), *CmpC + 1));
6382 if (Op1Min == Op0Max)
6386 if (*CmpC == Op0Min + 1)
6388 ConstantInt::get(Op1->getType(), *CmpC - 1));
6393 if (Op1Max == Op0Min)
6397 if (*CmpC == Op0Max - 1)
6399 ConstantInt::get(Op1->getType(), *CmpC + 1));
6413 if (Op0Max.
ult(Op1Min) || Op0Min.ugt(Op1Max))
6420 APInt Op0KnownZeroInverted = ~Op0Known.Zero;
6426 *LHSC != Op0KnownZeroInverted)
6432 Type *XTy =
X->getType();
6434 APInt C2 = Op0KnownZeroInverted;
6435 APInt C2Pow2 = (C2 & ~(*C1 - 1)) + *C1;
6441 auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
6451 (Op0Known & Op1Known) == Op0Known)
6457 if (Op0Max.
ult(Op1Min))
6459 if (Op0Min.uge(Op1Max))
6464 if (Op0Min.ugt(Op1Max))
6466 if (Op0Max.
ule(Op1Min))
6471 if (Op0Max.
slt(Op1Min))
6473 if (Op0Min.sge(Op1Max))
6478 if (Op0Min.sgt(Op1Max))
6480 if (Op0Max.
sle(Op1Min))
6485 assert(!isa<ConstantInt>(Op1) &&
"ICMP_SGE with ConstantInt not folded!");
6486 if (Op0Min.sge(Op1Max))
6488 if (Op0Max.
slt(Op1Min))
6490 if (Op1Min == Op0Max)
6494 assert(!isa<ConstantInt>(Op1) &&
"ICMP_SLE with ConstantInt not folded!");
6495 if (Op0Max.
sle(Op1Min))
6497 if (Op0Min.sgt(Op1Max))
6499 if (Op1Max == Op0Min)
6503 assert(!isa<ConstantInt>(Op1) &&
"ICMP_UGE with ConstantInt not folded!");
6504 if (Op0Min.uge(Op1Max))
6506 if (Op0Max.
ult(Op1Min))
6508 if (Op1Min == Op0Max)
6512 assert(!isa<ConstantInt>(Op1) &&
"ICMP_ULE with ConstantInt not folded!");
6513 if (Op0Max.
ule(Op1Min))
6515 if (Op0Min.ugt(Op1Max))
6517 if (Op1Max == Op0Min)
6527 return new ICmpInst(
I.getUnsignedPredicate(), Op0, Op1);
6559 bool IsSExt = ExtI->
getOpcode() == Instruction::SExt;
6561 auto CreateRangeCheck = [&] {
6576 }
else if (!IsSExt || HasOneUse) {
6581 return CreateRangeCheck();
6583 }
else if (IsSExt ?
C->isAllOnes() :
C->isOne()) {
6591 }
else if (!IsSExt || HasOneUse) {
6596 return CreateRangeCheck();
6610 Instruction::ICmp, Pred1,
X,
6620std::optional<std::pair<CmpInst::Predicate, Constant *>>
6624 "Only for relational integer predicates.");
6630 bool WillIncrement =
6635 auto ConstantIsOk = [WillIncrement, IsSigned](
ConstantInt *
C) {
6636 return WillIncrement ? !
C->isMaxValue(IsSigned) : !
C->isMinValue(IsSigned);
6639 Constant *SafeReplacementConstant =
nullptr;
6640 if (
auto *CI = dyn_cast<ConstantInt>(
C)) {
6642 if (!ConstantIsOk(CI))
6643 return std::nullopt;
6644 }
else if (
auto *FVTy = dyn_cast<FixedVectorType>(
Type)) {
6645 unsigned NumElts = FVTy->getNumElements();
6646 for (
unsigned i = 0; i != NumElts; ++i) {
6647 Constant *Elt =
C->getAggregateElement(i);
6649 return std::nullopt;
6651 if (isa<UndefValue>(Elt))
6656 auto *CI = dyn_cast<ConstantInt>(Elt);
6657 if (!CI || !ConstantIsOk(CI))
6658 return std::nullopt;
6660 if (!SafeReplacementConstant)
6661 SafeReplacementConstant = CI;
6663 }
else if (isa<VectorType>(
C->getType())) {
6665 Value *SplatC =
C->getSplatValue();
6666 auto *CI = dyn_cast_or_null<ConstantInt>(SplatC);
6668 if (!CI || !ConstantIsOk(CI))
6669 return std::nullopt;
6672 return std::nullopt;
6679 if (
C->containsUndefOrPoisonElement()) {
6680 assert(SafeReplacementConstant &&
"Replacement constant not set");
6687 Constant *OneOrNegOne = ConstantInt::get(
Type, WillIncrement ? 1 : -1,
true);
6690 return std::make_pair(NewPred, NewC);
6702 Value *Op0 =
I.getOperand(0);
6703 Value *Op1 =
I.getOperand(1);
6704 auto *Op1C = dyn_cast<Constant>(Op1);
6708 auto FlippedStrictness =
6710 if (!FlippedStrictness)
6713 return new ICmpInst(FlippedStrictness->first, Op0, FlippedStrictness->second);
6731 I.setName(
I.getName() +
".not");
6742 Value *
A =
I.getOperand(0), *
B =
I.getOperand(1);
6743 assert(
A->getType()->isIntOrIntVectorTy(1) &&
"Bools only");
6749 switch (
I.getPredicate()) {
6758 switch (
I.getPredicate()) {
6768 switch (
I.getPredicate()) {
6777 return BinaryOperator::CreateXor(
A,
B);
6785 return BinaryOperator::CreateAnd(Builder.
CreateNot(
A),
B);
6793 return BinaryOperator::CreateAnd(Builder.
CreateNot(
B),
A);
6801 return BinaryOperator::CreateOr(Builder.
CreateNot(
A),
B);
6809 return BinaryOperator::CreateOr(Builder.
CreateNot(
B),
A);
6865 Value *
LHS = Cmp.getOperand(0), *
RHS = Cmp.getOperand(1);
6870 if (
auto *
I = dyn_cast<Instruction>(V))
6871 I->copyIRFlags(&Cmp);
6872 Module *M = Cmp.getModule();
6874 M, Intrinsic::experimental_vector_reverse, V->getType());
6882 return createCmpReverse(Pred, V1, V2);
6886 return createCmpReverse(Pred, V1,
RHS);
6890 return createCmpReverse(Pred,
LHS, V2);
6915 Constant *ScalarC =
C->getSplatValue(
true);
6934 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6938 auto UAddOvResultPat = m_ExtractValue<0>(
6940 if (
match(Op0, UAddOvResultPat) &&
6949 UAddOv = cast<ExtractValueInst>(Op0)->getAggregateOperand();
6950 else if (
match(Op1, UAddOvResultPat) &&
6953 UAddOv = cast<ExtractValueInst>(Op1)->getAggregateOperand();
6961 if (!
I.getOperand(0)->getType()->isPointerTy() ||
6963 I.getParent()->getParent(),
6964 I.getOperand(0)->getType()->getPointerAddressSpace())) {
6970 Op->isLaunderOrStripInvariantGroup()) {
6972 Op->getOperand(0),
I.getOperand(1));
6984 if (
I.getType()->isVectorTy())
7006 auto *LHSTy = dyn_cast<FixedVectorType>(
LHS->
getType());
7007 if (!LHSTy || !LHSTy->getElementType()->isIntegerTy())
7010 LHSTy->getNumElements() * LHSTy->getElementType()->getIntegerBitWidth();
7012 if (!
DL.isLegalInteger(NumBits))
7016 auto *ScalarTy = Builder.
getIntNTy(NumBits);
7031 if (
auto *
GEP = dyn_cast<GEPOperator>(Op0))
7035 if (
auto *SI = dyn_cast<SelectInst>(Op0))
7039 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Op0))
7070 bool IsIntMinPosion =
C->isAllOnesValue();
7082 CxtI, IsIntMinPosion
7085 X, ConstantInt::get(
X->getType(),
SMin + 1)));
7091 CxtI, IsIntMinPosion
7094 X, ConstantInt::get(
X->getType(),
SMin)));
7110 bool Changed =
false;
7112 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7119 if (Op0Cplxity < Op1Cplxity) {
7134 if (
Value *V = dyn_castNegVal(SelectTrue)) {
7135 if (V == SelectFalse)
7138 else if (
Value *V = dyn_castNegVal(SelectFalse)) {
7139 if (V == SelectTrue)
7180 if (
SelectInst *SI = dyn_cast<SelectInst>(
I.user_back())) {
7238 if (
I.isCommutative()) {
7239 if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
7263 (Op0->
hasOneUse() || Op1->hasOneUse())) {
7279 assert(Op1->getType()->isPointerTy() &&
"Comparing pointer with non-pointer?");
7308 bool ConsumesOp0, ConsumesOp1;
7311 (ConsumesOp0 || ConsumesOp1)) {
7314 assert(InvOp0 && InvOp1 &&
7315 "Mismatch between isFreeToInvert and getFreelyInverted");
7316 return new ICmpInst(
I.getSwappedPredicate(), InvOp0, InvOp1);
7323 isa<IntegerType>(
X->getType())) {
7328 if (AddI->
getOpcode() == Instruction::Add &&
7329 OptimizeOverflowCheck(Instruction::Add,
false,
X,
Y, *AddI,
7330 Result, Overflow)) {
7348 if ((
I.isUnsigned() ||
I.isEquality()) &&
7351 Y->getType()->getScalarSizeInBits() == 1 &&
7352 (Op0->
hasOneUse() || Op1->hasOneUse())) {
7359 unsigned ShiftOpc = ShiftI->
getOpcode();
7360 if ((ExtOpc == Instruction::ZExt && ShiftOpc == Instruction::LShr) ||
7361 (ExtOpc == Instruction::SExt && ShiftOpc == Instruction::AShr)) {
7390 if (
auto *EVI = dyn_cast<ExtractValueInst>(Op0))
7391 if (
auto *ACXI = dyn_cast<AtomicCmpXchgInst>(EVI->getAggregateOperand()))
7392 if (EVI->getIndices()[0] == 0 && ACXI->getCompareOperand() == Op1 &&
7399 if (
I.getType()->isVectorTy())
7409 return Changed ? &
I :
nullptr;
7423 if (MantissaWidth == -1)
return nullptr;
7427 bool LHSUnsigned = isa<UIToFPInst>(LHSI);
7429 if (
I.isEquality()) {
7431 bool IsExact =
false;
7432 APSInt RHSCvt(IntWidth, LHSUnsigned);
7441 if (*
RHS != RHSRoundInt) {
7461 if ((
int)IntWidth > MantissaWidth) {
7463 int Exp = ilogb(*
RHS);
7466 if (MaxExponent < (
int)IntWidth - !LHSUnsigned)
7472 if (MantissaWidth <= Exp && Exp <= (
int)IntWidth - !LHSUnsigned)
7481 assert(!
RHS->isNaN() &&
"NaN comparison not already folded!");
7484 switch (
I.getPredicate()) {
7574 APSInt RHSInt(IntWidth, LHSUnsigned);
7577 if (!
RHS->isZero()) {
7591 if (
RHS->isNegative())
7597 if (
RHS->isNegative())
7603 if (
RHS->isNegative())
7610 if (!
RHS->isNegative())
7616 if (
RHS->isNegative())
7622 if (
RHS->isNegative())
7628 if (
RHS->isNegative())
7635 if (!
RHS->isNegative())
7689 if (
C->isNegative())
7690 Pred =
I.getSwappedPredicate();
7705 if (!
C->isPosZero()) {
7706 if (!
C->isSmallestNormalized())
7719 switch (
I.getPredicate()) {
7745 switch (
I.getPredicate()) {
7770 assert(!
I.hasNoNaNs() &&
"fcmp should have simplified");
7775 assert(!
I.hasNoNaNs() &&
"fcmp should have simplified");
7789 return replacePredAndOp0(&
I,
I.getPredicate(),
X);
7798 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7803 Pred =
I.getSwappedPredicate();
7812 return new FCmpInst(Pred, Op0, Zero,
"", &
I);
7816 bool Changed =
false;
7827 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7834 assert(OpType == Op1->getType() &&
"fcmp with different-typed operands?");
7858 if (
I.isCommutative()) {
7859 if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
7881 return new FCmpInst(
I.getSwappedPredicate(),
X,
Y,
"", &
I);
7894 if (
SelectInst *SI = dyn_cast<SelectInst>(
I.user_back())) {
7963 Type *IntTy =
X->getType();
7975 case Instruction::PHI:
7979 case Instruction::SIToFP:
7980 case Instruction::UIToFP:
7984 case Instruction::FDiv:
7988 case Instruction::Load:
7989 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
7990 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
7992 cast<LoadInst>(LHSI),
GEP, GV,
I))
8006 return new FCmpInst(
I.getSwappedPredicate(),
X, NegC,
"", &
I);
8017 X->getType()->getScalarType()->getFltSemantics();
8053 Constant *NewC = ConstantFP::get(
X->getType(), TruncC);
8067 if (
auto *VecTy = dyn_cast<VectorType>(OpType))
8079 Value *CanonLHS =
nullptr, *CanonRHS =
nullptr;
8080 match(Op0, m_Intrinsic<Intrinsic::canonicalize>(
m_Value(CanonLHS)));
8081 match(Op1, m_Intrinsic<Intrinsic::canonicalize>(
m_Value(CanonRHS)));
8084 if (CanonLHS == Op1)
8085 return new FCmpInst(Pred, Op1, Op1,
"", &
I);
8088 if (CanonRHS == Op0)
8089 return new FCmpInst(Pred, Op0, Op0,
"", &
I);
8092 if (CanonLHS && CanonRHS)
8093 return new FCmpInst(Pred, CanonLHS, CanonRHS,
"", &
I);
8096 if (
I.getType()->isVectorTy())
8100 return Changed ? &
I :
nullptr;
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements the APSInt class, which is a simple class that represents an arbitrary sized int...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static Instruction * foldFCmpReciprocalAndZero(FCmpInst &I, Instruction *LHSI, Constant *RHSC)
Fold (C / X) < 0.0 --> X < 0.0 if possible. Swap predicate if necessary.
static Instruction * foldFabsWithFcmpZero(FCmpInst &I, InstCombinerImpl &IC)
Optimize fabs(X) compared with zero.
static Instruction * foldICmpUSubSatOrUAddSatWithConstant(ICmpInst::Predicate Pred, SaturatingInst *II, const APInt &C, InstCombiner::BuilderTy &Builder)
static bool addWithOverflow(APInt &Result, const APInt &In1, const APInt &In2, bool IsSigned=false)
Compute Result = In1+In2, returning true if the result overflowed for this type.
static Value * foldICmpWithLowBitMaskedVal(ICmpInst::Predicate Pred, Value *Op0, Value *Op1, const SimplifyQuery &Q, InstCombiner &IC)
Some comparisons can be simplified.
static Instruction * foldICmpAndXX(ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
static Instruction * foldVectorCmp(CmpInst &Cmp, InstCombiner::BuilderTy &Builder)
static bool isMaskOrZero(const Value *V, bool Not, const SimplifyQuery &Q, unsigned Depth=0)
static Value * createLogicFromTable(const std::bitset< 4 > &Table, Value *Op0, Value *Op1, IRBuilderBase &Builder, bool HasOneUse)
static Instruction * foldICmpOfUAddOv(ICmpInst &I)
static Instruction * foldICmpShlOne(ICmpInst &Cmp, Instruction *Shl, const APInt &C)
Fold icmp (shl 1, Y), C.
static bool isChainSelectCmpBranch(const SelectInst *SI)
Return true when the instruction sequence within a block is select-cmp-br.
static Instruction * foldICmpInvariantGroup(ICmpInst &I)
static Instruction * foldReductionIdiom(ICmpInst &I, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
This function folds patterns produced by lowering of reduce idioms, such as llvm.vector....
static Instruction * canonicalizeICmpBool(ICmpInst &I, InstCombiner::BuilderTy &Builder)
Integer compare with boolean values can always be turned into bitwise ops.
static Value * foldICmpOrXorSubChain(ICmpInst &Cmp, BinaryOperator *Or, InstCombiner::BuilderTy &Builder)
Fold icmp eq/ne (or (xor/sub (X1, X2), xor/sub (X3, X4))), 0.
static bool hasBranchUse(ICmpInst &I)
Given an icmp instruction, return true if any use of this comparison is a branch on sign bit comparis...
static APInt getDemandedBitsLHSMask(ICmpInst &I, unsigned BitWidth)
When performing a comparison against a constant, it is possible that not all the bits in the LHS are ...
static Instruction * foldICmpXorXX(ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
static Instruction * processUMulZExtIdiom(ICmpInst &I, Value *MulVal, const APInt *OtherVal, InstCombinerImpl &IC)
Recognize and process idiom involving test for multiplication overflow.
static Instruction * transformToIndexedCompare(GEPOperator *GEPLHS, Value *RHS, ICmpInst::Predicate Cond, const DataLayout &DL, InstCombiner &IC)
Converts (CMP GEPLHS, RHS) if this change would make RHS a constant.
static Instruction * foldFCmpFNegCommonOp(FCmpInst &I)
static bool canRewriteGEPAsOffset(Value *Start, Value *Base, const DataLayout &DL, SetVector< Value * > &Explored)
Returns true if we can rewrite Start as a GEP with pointer Base and some integer offset.
static Instruction * foldICmpWithHighBitMask(ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
static ICmpInst * canonicalizeCmpWithConstant(ICmpInst &I)
If we have an icmp le or icmp ge instruction with a constant operand, turn it into the appropriate ic...
static Instruction * foldICmpIntrinsicWithIntrinsic(ICmpInst &Cmp, InstCombiner::BuilderTy &Builder)
Fold an icmp with LLVM intrinsics.
static Instruction * foldICmpPow2Test(ICmpInst &I, InstCombiner::BuilderTy &Builder)
static bool subWithOverflow(APInt &Result, const APInt &In1, const APInt &In2, bool IsSigned=false)
Compute Result = In1-In2, returning true if the result overflowed for this type.
static Instruction * foldICmpXNegX(ICmpInst &I, InstCombiner::BuilderTy &Builder)
static Instruction * processUGT_ADDCST_ADD(ICmpInst &I, Value *A, Value *B, ConstantInt *CI2, ConstantInt *CI1, InstCombinerImpl &IC)
The caller has matched a pattern of the form: I = icmp ugt (add (add A, B), CI2), CI1 If this is of t...
static Value * foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ, InstCombiner::BuilderTy &Builder)
static bool isSignTest(ICmpInst::Predicate &Pred, const APInt &C)
Returns true if the exploded icmp can be expressed as a signed comparison to zero and updates the pre...
static Instruction * foldCtpopPow2Test(ICmpInst &I, IntrinsicInst *CtpopLhs, const APInt &CRhs, InstCombiner::BuilderTy &Builder, const SimplifyQuery &Q)
static void setInsertionPoint(IRBuilder<> &Builder, Value *V, bool Before=true)
static bool isNeutralValue(Instruction::BinaryOps BinaryOp, Value *RHS, bool IsSigned)
static Value * foldICmpWithTruncSignExtendedVal(ICmpInst &I, InstCombiner::BuilderTy &Builder)
Some comparisons can be simplified.
static Value * rewriteGEPAsOffset(Value *Start, Value *Base, const DataLayout &DL, SetVector< Value * > &Explored, InstCombiner &IC)
Returns a re-written value of Start as an indexed GEP using Base as a pointer.
static Instruction * foldICmpOrXX(ICmpInst &I, const SimplifyQuery &Q, InstCombinerImpl &IC)
This file provides internal interfaces used to implement the InstCombine.
This file provides the interface for the instcombine pass implementation.
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
mir Rename Register Operands
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
const SmallVectorImpl< MachineOperand > & Cond
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
This file implements a set that has insertion order iteration characteristics.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
opStatus convert(const fltSemantics &ToSemantics, roundingMode RM, bool *losesInfo)
static APFloat getSmallestNormalized(const fltSemantics &Sem, bool Negative=false)
Returns the smallest (by magnitude) normalized finite number in the given semantics.
APInt bitcastToAPInt() const
static APFloat getLargest(const fltSemantics &Sem, bool Negative=false)
Returns the largest finite number in the given semantics.
static APFloat getInf(const fltSemantics &Sem, bool Negative=false)
Factory for Positive and Negative Infinity.
FPClassTest classify() const
Return the FPClassTest which will return true for the value.
opStatus roundToIntegral(roundingMode RM)
Class for arbitrary precision integers.
APInt udiv(const APInt &RHS) const
Unsigned division operation.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
bool isNegatedPowerOf2() const
Check if this APInt's negated value is a power of two greater than zero.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
unsigned ceilLogBase2() const
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
APInt usub_ov(const APInt &RHS, bool &Overflow) const
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignMask() const
Check if the APInt's value is returned by getSignMask.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
bool eq(const APInt &RHS) const
Equality comparison.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
void negate()
Negate this APInt in place.
unsigned countr_zero() const
Count the number of trailing zero bits.
unsigned countl_zero() const
The APInt version of std::countl_zero.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned countl_one() const
Count the number of leading one bits.
unsigned logBase2() const
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
bool isMaxSignedValue() const
Determine if this is the largest signed value.
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
APInt shl(unsigned shiftAmt) const
Left-shift function.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
bool isOne() const
Determine if this is a value of 1.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
unsigned countr_one() const
Count the number of trailing one bits.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
An arbitrary precision integer that knows its signedness.
an instruction to allocate memory on the stack
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Class to represent array types.
LLVM Basic Block Representation.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
unsigned getNoWrapKind() const
Returns one of OBO::NoSignedWrap or OBO::NoUnsignedWrap.
Instruction::BinaryOps getBinaryOp() const
Returns the binary operation underlying the intrinsic.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
static BinaryOperator * CreateNot(Value *Op, const Twine &Name, BasicBlock::iterator InsertBefore)
Conditional or Unconditional Branch instruction.
Value * getArgOperand(unsigned i) const
This class represents a function call, abstracting a target machine's calling convention.
static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr, BasicBlock::iterator InsertBefore)
This class is the base class for the comparison instructions.
static Type * makeCmpResultType(Type *opnd_type)
Create a result type for fcmp/icmp.
Predicate getStrictPredicate() const
For example, SGE -> SGT, SLE -> SLT, ULE -> ULT, UGE -> UGT.
bool isEquality() const
Determine if this is an equals/not equals predicate.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ FCMP_OEQ
0 0 0 1 True if ordered and equal
@ FCMP_TRUE
1 1 1 1 Always true (always folded)
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ FCMP_OLT
0 1 0 0 True if ordered and less than
@ FCMP_ULE
1 1 0 1 True if unordered, less than, or equal
@ FCMP_OGT
0 0 1 0 True if ordered and greater than
@ FCMP_OGE
0 0 1 1 True if ordered and greater than or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ FCMP_ULT
1 1 0 0 True if unordered or less than
@ FCMP_ONE
0 1 1 0 True if ordered and operands are unequal
@ FCMP_UEQ
1 0 0 1 True if unordered or equal
@ ICMP_ULT
unsigned less than
@ FCMP_UGT
1 0 1 0 True if unordered or greater than
@ FCMP_OLE
0 1 0 1 True if ordered and less than or equal
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
@ ICMP_SGE
signed greater or equal
@ FCMP_UNE
1 1 1 0 True if unordered or not equal
@ ICMP_ULE
unsigned less or equal
@ FCMP_UGE
1 0 1 1 True if unordered, greater than, or equal
@ FCMP_FALSE
0 0 0 0 Always false (always folded)
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a compare instruction, given the opcode, the predicate and the two operands.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
Predicate getPredicate() const
Return the predicate for this instruction.
Predicate getFlippedStrictnessPredicate() const
For predicate of kind "is X or equal to 0" returns the predicate "is X".
Predicate getFlippedSignednessPredicate()
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->Failed assert.
bool isIntPredicate() const
static Constant * getIntToPtr(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getPointerBitCastOrAddrSpaceCast(Constant *C, Type *Ty)
Create a BitCast or AddrSpaceCast for a pointer type depending on the address space.
static Constant * getSub(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getNot(Constant *C)
static Constant * getXor(Constant *C1, Constant *C2)
static Constant * getAdd(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
static Constant * getNeg(Constant *C, bool HasNUW=false, bool HasNSW=false)
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
static Constant * getZero(Type *Ty, bool Negative=false)
This is the shared class of boolean and integer constants.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
static ConstantInt * getFalse(LLVMContext &Context)
unsigned getBitWidth() const
getBitWidth - Return the scalar bitwidth of this constant.
const APInt & getValue() const
Return the constant as an APInt value reference.
static ConstantInt * getBool(LLVMContext &Context, bool V)
This class represents a range of values.
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
std::optional< ConstantRange > exactUnionWith(const ConstantRange &CR) const
Union the two ranges and return the result if it can be represented exactly, otherwise return std::nu...
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
bool isEmptySet() const
Return true if this set contains no members.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
static Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
This is an important base class in LLVM.
static Constant * getIntegerValue(Type *Ty, const APInt &V)
Return the value for an integer or pointer constant, or a vector thereof, with the given scalar value...
static Constant * replaceUndefsWith(Constant *C, Constant *Replacement)
Try to replace undefined constant C or undefined elements in C with Replacement.
static Constant * getAllOnesValue(Type *Ty)
bool isAllOnesValue() const
Return true if this is the value that would be returned by getAllOnesValue.
const APInt & getUniqueInteger() const
If C is a constant integer then return its value, otherwise C must be a vector of constant integers,...
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
bool isLegalInteger(uint64_t Width) const
Returns true if the specified type is known to be a native integer type supported by the CPU.
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
unsigned getPointerTypeSizeInBits(Type *) const
Layout pointer size, in bits, based on the type.
IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
TypeSize getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Type * getSmallestLegalIntType(LLVMContext &C, unsigned Width=0) const
Returns the smallest integer type with size at least as big as Width bits.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
ArrayRef< BranchInst * > conditionsFor(const Value *V) const
Access the list of branches which affect this value.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Type * getSourceElementType() const
Value * getPointerOperand()
bool hasAllConstantIndices() const
Return true if all of the indices of this GEP are constant integers.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Type * getValueType() const
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
bool hasDefinitiveInitializer() const
hasDefinitiveInitializer - Whether the global variable has an initializer, and any other instances of...
This instruction compares its operands according to the predicate given to the constructor.
static bool compare(const APInt &LHS, const APInt &RHS, ICmpInst::Predicate Pred)
Return result of LHS Pred RHS comparison.
Predicate getSignedPredicate() const
For example, EQ->EQ, SLE->SLE, UGT->SGT, etc.
bool isEquality() const
Return true if this predicate is either EQ or NE.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
Predicate getUnsignedPredicate() const
For example, EQ->EQ, SLE->ULE, UGT->UGT, etc.
Common base class shared among various IRBuilders.
CallInst * CreateUnaryIntrinsic(Intrinsic::ID ID, Value *V, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with 1 operand which is mangled on its type.
Value * CreateICmpULT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateNeg(Value *V, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateExtractElement(Value *Vec, Value *Idx, const Twine &Name="")
IntegerType * getIntNTy(unsigned N)
Fetch the type representing an N-bit integer.
Value * CreateICmpSGT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateZExtOrTrunc(Value *V, Type *DestTy, const Twine &Name="")
Create a ZExt or Trunc from the integer value V to DestTy.
Value * CreateVectorSplat(unsigned NumElts, Value *V, const Twine &Name="")
Return a vector value that contains.
Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")
ConstantInt * getTrue()
Get the constant value for i1 true.
CallInst * CreateIntrinsic(Intrinsic::ID ID, ArrayRef< Type * > Types, ArrayRef< Value * > Args, Instruction *FMFSource=nullptr, const Twine &Name="")
Create a call to intrinsic ID with Args, mangled using Types.
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Value * CreateNSWAdd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateInBoundsGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="")
Value * CreateICmpNE(Value *LHS, Value *RHS, const Twine &Name="")
Value * createIsFPClass(Value *FPNum, unsigned Test)
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateNot(Value *V, const Twine &Name="")
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateSub(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Value * CreateICmpUGT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateShl(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
Value * CreateZExt(Value *V, Type *DestTy, const Twine &Name="", bool IsNonNeg=false)
Value * CreateAnd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateAdd(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
ConstantInt * getFalse()
Get the constant value for i1 false.
Value * CreateOr(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBinOp(Instruction::BinaryOps Opc, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateICmpSLT(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateCast(Instruction::CastOps Op, Value *V, Type *DestTy, const Twine &Name="")
Value * CreateIntCast(Value *V, Type *DestTy, bool isSigned, const Twine &Name="")
Value * CreateIsNull(Value *Arg, const Twine &Name="")
Return a boolean value testing if Arg == 0.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args=std::nullopt, const Twine &Name="", MDNode *FPMathTag=nullptr)
Value * CreateXor(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
IntegerType * getInt8Ty()
Fetch the type representing an 8-bit integer.
ConstantInt * getInt(const APInt &AI)
Get a constant integer value.
Value * CreateURem(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateMul(Value *LHS, Value *RHS, const Twine &Name="", bool HasNUW=false, bool HasNSW=false)
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Instruction * foldICmpShrConstant(ICmpInst &Cmp, BinaryOperator *Shr, const APInt &C)
Fold icmp ({al}shr X, Y), C.
Instruction * foldICmpWithZextOrSext(ICmpInst &ICmp)
Instruction * foldICmpSelectConstant(ICmpInst &Cmp, SelectInst *Select, ConstantInt *C)
Instruction * foldICmpSRemConstant(ICmpInst &Cmp, BinaryOperator *UDiv, const APInt &C)
Instruction * foldICmpBinOpWithConstant(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C)
Fold an icmp with BinaryOp and constant operand: icmp Pred BO, C.
Instruction * foldICmpOrConstant(ICmpInst &Cmp, BinaryOperator *Or, const APInt &C)
Fold icmp (or X, Y), C.
Instruction * foldICmpTruncWithTruncOrExt(ICmpInst &Cmp, const SimplifyQuery &Q)
Fold icmp (trunc X), (trunc Y).
Instruction * foldSignBitTest(ICmpInst &I)
Fold equality-comparison between zero and any (maybe truncated) right-shift by one-less-than-bitwidth...
bool SimplifyDemandedBits(Instruction *I, unsigned Op, const APInt &DemandedMask, KnownBits &Known, unsigned Depth=0) override
This form of SimplifyDemandedBits simplifies the specified instruction operand if possible,...
Instruction * foldOpIntoPhi(Instruction &I, PHINode *PN)
Given a binary operator, cast instruction, or select which has a PHI node as operand #0,...
Value * insertRangeTest(Value *V, const APInt &Lo, const APInt &Hi, bool isSigned, bool Inside)
Emit a computation of: (V >= Lo && V < Hi) if Inside is true, otherwise (V < Lo || V >= Hi).
Instruction * foldICmpBinOp(ICmpInst &Cmp, const SimplifyQuery &SQ)
Try to fold icmp (binop), X or icmp X, (binop).
Instruction * foldICmpSubConstant(ICmpInst &Cmp, BinaryOperator *Sub, const APInt &C)
Fold icmp (sub X, Y), C.
Instruction * foldICmpInstWithConstantNotInt(ICmpInst &Cmp)
Handle icmp with constant (but not simple integer constant) RHS.
Instruction * foldICmpWithMinMax(Instruction &I, MinMaxIntrinsic *MinMax, Value *Z, ICmpInst::Predicate Pred)
Fold icmp Pred min|max(X, Y), Z.
Instruction * foldGEPICmp(GEPOperator *GEPLHS, Value *RHS, ICmpInst::Predicate Cond, Instruction &I)
Fold comparisons between a GEP instruction and something else.
Instruction * foldICmpShlConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, const APInt &C2)
Handle "(icmp eq/ne (shl AP2, A), AP1)" -> (icmp eq/ne A, TrailingZeros(AP1) - TrailingZeros(AP2)).
Value * reassociateShiftAmtsOfTwoSameDirectionShifts(BinaryOperator *Sh0, const SimplifyQuery &SQ, bool AnalyzeForSignBitExtraction=false)
Instruction * foldICmpEqIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, const APInt &C)
Fold an equality icmp with LLVM intrinsic and constant operand.
Value * foldMultiplicationOverflowCheck(ICmpInst &Cmp)
Fold (-1 u/ x) u< y ((x * y) ?/ x) != y to @llvm.
Instruction * foldICmpInstWithConstantAllowUndef(ICmpInst &Cmp, const APInt &C)
Try to fold integer comparisons with a constant operand: icmp Pred X, C where X is some kind of instr...
Instruction * foldICmpWithConstant(ICmpInst &Cmp)
Fold icmp Pred X, C.
CmpInst * canonicalizeICmpPredicate(CmpInst &I)
If we have a comparison with a non-canonical predicate, if we can update all the users,...
Instruction * eraseInstFromFunction(Instruction &I) override
Combiner aware instruction erasure.
Instruction * foldICmpWithZero(ICmpInst &Cmp)
Instruction * foldICmpBinOpEqualityWithConstant(ICmpInst &Cmp, BinaryOperator *BO, const APInt &C)
Fold an icmp equality instruction with binary operator LHS and constant RHS: icmp eq/ne BO,...
Instruction * foldICmpUsingBoolRange(ICmpInst &I)
If one operand of an icmp is effectively a bool (value range of {0,1}), then try to reduce patterns b...
Instruction * foldICmpWithTrunc(ICmpInst &Cmp)
Instruction * foldICmpIntrinsicWithConstant(ICmpInst &ICI, IntrinsicInst *II, const APInt &C)
Fold an icmp with LLVM intrinsic and constant operand: icmp Pred II, C.
bool matchThreeWayIntCompare(SelectInst *SI, Value *&LHS, Value *&RHS, ConstantInt *&Less, ConstantInt *&Equal, ConstantInt *&Greater)
Match a select chain which produces one of three values based on whether the LHS is less than,...
Instruction * foldCmpLoadFromIndexedGlobal(LoadInst *LI, GetElementPtrInst *GEP, GlobalVariable *GV, CmpInst &ICI, ConstantInt *AndCst=nullptr)
This is called when we see this pattern: cmp pred (load (gep GV, ...)), cmpcst where GV is a global v...
Instruction * visitFCmpInst(FCmpInst &I)
Instruction * foldICmpUsingKnownBits(ICmpInst &Cmp)
Try to fold the comparison based on range information we can get by checking whether bits are known t...
Instruction * foldICmpDivConstant(ICmpInst &Cmp, BinaryOperator *Div, const APInt &C)
Fold icmp ({su}div X, Y), C.
Instruction * foldIRemByPowerOfTwoToBitTest(ICmpInst &I)
If we have: icmp eq/ne (urem/srem x, y), 0 iff y is a power-of-two, we can replace this with a bit te...
Instruction * foldFCmpIntToFPConst(FCmpInst &I, Instruction *LHSI, Constant *RHSC)
Fold fcmp ([us]itofp x, cst) if possible.
Instruction * foldICmpUDivConstant(ICmpInst &Cmp, BinaryOperator *UDiv, const APInt &C)
Fold icmp (udiv X, Y), C.
Constant * getLosslessTrunc(Constant *C, Type *TruncTy, unsigned ExtOp)
Instruction * foldICmpWithCastOp(ICmpInst &ICmp)
Handle icmp (cast x), (cast or constant).
Instruction * foldICmpTruncConstant(ICmpInst &Cmp, TruncInst *Trunc, const APInt &C)
Fold icmp (trunc X), C.
Instruction * foldICmpAddConstant(ICmpInst &Cmp, BinaryOperator *Add, const APInt &C)
Fold icmp (add X, Y), C.
Instruction * foldICmpMulConstant(ICmpInst &Cmp, BinaryOperator *Mul, const APInt &C)
Fold icmp (mul X, Y), C.
Instruction * tryFoldInstWithCtpopWithNot(Instruction *I)
Instruction * foldICmpXorConstant(ICmpInst &Cmp, BinaryOperator *Xor, const APInt &C)
Fold icmp (xor X, Y), C.
Instruction * foldICmpAddOpConst(Value *X, const APInt &C, ICmpInst::Predicate Pred)
Fold "icmp pred (X+C), X".
Instruction * foldICmpAndShift(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1, const APInt &C2)
Fold icmp (and (sh X, Y), C2), C1.
Instruction * foldICmpInstWithConstant(ICmpInst &Cmp)
Try to fold integer comparisons with a constant operand: icmp Pred X, C where X is some kind of instr...
Instruction * foldICmpXorShiftConst(ICmpInst &Cmp, BinaryOperator *Xor, const APInt &C)
For power-of-2 C: ((X s>> ShiftC) ^ X) u< C --> (X + C) u< (C << 1) ((X s>> ShiftC) ^ X) u> (C - 1) -...
Instruction * foldICmpShlConstant(ICmpInst &Cmp, BinaryOperator *Shl, const APInt &C)
Fold icmp (shl X, Y), C.
Instruction * foldICmpAndConstant(ICmpInst &Cmp, BinaryOperator *And, const APInt &C)
Fold icmp (and X, Y), C.
Instruction * foldICmpEquality(ICmpInst &Cmp)
bool dominatesAllUses(const Instruction *DI, const Instruction *UI, const BasicBlock *DB) const
True when DB dominates all uses of DI except UI.
bool foldAllocaCmp(AllocaInst *Alloca)
Instruction * foldICmpCommutative(ICmpInst::Predicate Pred, Value *Op0, Value *Op1, ICmpInst &CxtI)
Instruction * visitICmpInst(ICmpInst &I)
Instruction * foldSelectICmp(ICmpInst::Predicate Pred, SelectInst *SI, Value *RHS, const ICmpInst &I)
OverflowResult computeOverflow(Instruction::BinaryOps BinaryOp, bool IsSigned, Value *LHS, Value *RHS, Instruction *CxtI) const
Instruction * foldICmpWithDominatingICmp(ICmpInst &Cmp)
Canonicalize icmp instructions based on dominating conditions.
bool replacedSelectWithOperand(SelectInst *SI, const ICmpInst *Icmp, const unsigned SIOpd)
Try to replace select with select operand SIOpd in SI-ICmp sequence.
Instruction * foldICmpShrConstConst(ICmpInst &I, Value *ShAmt, const APInt &C1, const APInt &C2)
Handle "(icmp eq/ne (ashr/lshr AP2, A), AP1)" -> (icmp eq/ne A, Log2(AP2/AP1)) -> (icmp eq/ne A,...
void freelyInvertAllUsersOf(Value *V, Value *IgnoredUser=nullptr)
Freely adapt every user of V as-if V was changed to !V.
Instruction * foldICmpAndConstConst(ICmpInst &Cmp, BinaryOperator *And, const APInt &C1)
Fold icmp (and X, C2), C1.
Instruction * foldICmpBitCast(ICmpInst &Cmp)
The core instruction combiner logic.
OverflowResult computeOverflowForSignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
static bool isCanonicalPredicate(CmpInst::Predicate Pred)
Predicate canonicalization reduces the number of patterns that need to be matched by other transforms...
bool isFreeToInvert(Value *V, bool WillInvertAllUses, bool &DoesConsume)
Return true if the specified value is free to invert (apply ~ to).
static unsigned getComplexity(Value *V)
Assign a complexity or rank value to LLVM Values.
bool isKnownToBeAPowerOfTwo(const Value *V, bool OrZero=false, unsigned Depth=0, const Instruction *CxtI=nullptr)
OverflowResult computeOverflowForUnsignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
uint64_t MaxArraySizeForCombine
Maximum size of array considered when transforming.
OverflowResult computeOverflowForSignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const
static Constant * SubOne(Constant *C)
Subtract one from a Constant.
static std::optional< std::pair< CmpInst::Predicate, Constant * > > getFlippedStrictnessPredicateAndConstant(CmpInst::Predicate Pred, Constant *C)
OverflowResult computeOverflowForUnsignedSub(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
bool canFreelyInvertAllUsersOf(Instruction *V, Value *IgnoredUser)
Given i1 V, can every user of V be freely adapted if V is changed to !V ? InstCombine's freelyInvertA...
void addToWorklist(Instruction *I)
Instruction * replaceOperand(Instruction &I, unsigned OpNum, Value *V)
Replace operand of instruction and add old operand to the worklist.
OverflowResult computeOverflowForSignedMul(const Value *LHS, const Value *RHS, const Instruction *CxtI) const
void computeKnownBits(const Value *V, KnownBits &Known, unsigned Depth, const Instruction *CxtI) const
OverflowResult computeOverflowForUnsignedAdd(const WithCache< const Value * > &LHS, const WithCache< const Value * > &RHS, const Instruction *CxtI) const
Value * getFreelyInverted(Value *V, bool WillInvertAllUses, BuilderTy *Builder, bool &DoesConsume)
const SimplifyQuery & getSimplifyQuery() const
unsigned ComputeMaxSignificantBits(const Value *Op, unsigned Depth=0, const Instruction *CxtI=nullptr) const
bool hasNoUnsignedWrap() const LLVM_READONLY
Determine whether the no unsigned wrap flag is set.
bool hasNoInfs() const LLVM_READONLY
Determine whether the no-infs flag is set.
bool isArithmeticShift() const
Return true if this is an arithmetic shift right.
bool hasNoSignedWrap() const LLVM_READONLY
Determine whether the no signed wrap flag is set.
bool isCommutative() const LLVM_READONLY
Return true if the instruction is commutative:
const BasicBlock * getParent() const
bool isExact() const LLVM_READONLY
Determine whether the exact flag is set.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
An instruction for reading from memory.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
This class represents min/max intrinsics.
A Module instance is used to store all the information related to an LLVM module.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Represents a saturating add/sub intrinsic.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr, BasicBlock::iterator InsertBefore, Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
This instruction constructs a fixed permutation of two input vectors.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
reverse_iterator rbegin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
const fltSemantics & getFltSemantics() const
bool isVectorTy() const
True if this is an instance of VectorType.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
bool isPointerTy() const
True if this is an instance of PointerType.
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
bool isPPC_FP128Ty() const
Return true if this is powerpc long double.
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
int getFPMantissaWidth() const
Return the width of the mantissa of this type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
bool isIEEELikeFPTy() const
Return true if this is a well-behaved IEEE-like type, which has a IEEE compatible layout as defined b...
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
A Use represents the edge between a Value definition and its users.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
bool hasOneUse() const
Return true if there is exactly one use of this value.
iterator_range< user_iterator > users()
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
constexpr ScalarTy getFixedValue() const
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
@ C
The default llvm calling convention, compatible with C.
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
cst_pred_ty< is_lowbit_mask > m_LowBitMask()
Match an integer or vector with only the low bit(s) set.
BinaryOp_match< LHS, RHS, Instruction::And > m_And(const LHS &L, const RHS &R)
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
apint_match m_APIntAllowUndef(const APInt *&Res)
Match APInt while allowing undefs in splat vector constants.
cst_pred_ty< is_power2 > m_Power2()
Match an integer or vector power-of-2.
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
BinaryOp_match< LHS, RHS, Instruction::And, true > m_c_And(const LHS &L, const RHS &R)
Matches an And with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, OpTy > m_ZExtOrSelf(const OpTy &Op)
bool match(Val *V, const Pattern &P)
BinOpPred_match< LHS, RHS, is_idiv_op > m_IDiv(const LHS &L, const RHS &R)
Matches integer division operations.
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
cstfp_pred_ty< is_any_zero_fp > m_AnyZeroFP()
Match a floating-point negative zero or positive zero.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
OverflowingBinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub, OverflowingBinaryOperator::NoSignedWrap > m_NSWNeg(const ValTy &V)
Matches a 'Neg' as 'sub nsw 0, V'.
cst_pred_ty< is_nonnegative > m_NonNegative()
Match an integer or vector of non-negative values.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
BinOpPred_match< LHS, RHS, is_logical_shift_op > m_LogicalShift(const LHS &L, const RHS &R)
Matches logical shift operations.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > m_SMin(const LHS &L, const RHS &R)
CastOperator_match< OpTy, Instruction::Trunc > m_Trunc(const OpTy &Op)
Matches Trunc.
BinaryOp_match< LHS, RHS, Instruction::Xor, true > m_c_Xor(const LHS &L, const RHS &R)
Matches an Xor with LHS and RHS in either order.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
deferredval_ty< Value > m_Deferred(Value *const &V)
Like m_Specific(), but works if the specific value to match is determined as part of the same match()...
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
BinaryOp_match< cst_pred_ty< is_zero_int >, ValTy, Instruction::Sub > m_Neg(const ValTy &V)
Matches a 'Neg' as 'sub 0, V'.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
CastInst_match< OpTy, FPExtInst > m_FPExt(const OpTy &Op)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Mul, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWMul(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::UDiv > m_UDiv(const LHS &L, const RHS &R)
cst_pred_ty< is_negated_power2_or_zero > m_NegatedPower2OrZero()
Match a integer or vector negated power-of-2.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
cst_pred_ty< is_lowbit_mask_or_zero > m_LowBitMaskOrZero()
Match an integer or vector with only the low bit(s) set.
BinaryOp_match< LHS, RHS, Instruction::Add, true > m_c_Add(const LHS &L, const RHS &R)
Matches a Add with LHS and RHS in either order.
match_combine_or< BinaryOp_match< LHS, RHS, Instruction::Add >, DisjointOr_match< LHS, RHS > > m_AddLike(const LHS &L, const RHS &R)
Match either "add" or "or disjoint".
CastInst_match< OpTy, UIToFPInst > m_UIToFP(const OpTy &Op)
CastOperator_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
match_combine_or< CastOperator_match< OpTy, Instruction::Trunc >, OpTy > m_TruncOrSelf(const OpTy &Op)
specific_intval< true > m_SpecificIntAllowUndef(APInt V)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Signum_match< Val_t > m_Signum(const Val_t &V)
Matches a signum pattern.
CastInst_match< OpTy, SIToFPInst > m_SIToFP(const OpTy &Op)
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
match_combine_or< CastInst_match< OpTy, ZExtInst >, CastInst_match< OpTy, SExtInst > > m_ZExtOrSExt(const OpTy &Op)
FNeg_match< OpTy > m_FNeg(const OpTy &X)
Match 'fneg X' as 'fsub -0.0, X'.
cstfp_pred_ty< is_pos_zero_fp > m_PosZeroFP()
Match a floating-point positive zero.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
m_Intrinsic_Ty< Opnd0 >::Ty m_VecReverse(const Opnd0 &Op0)
BinOpPred_match< LHS, RHS, is_irem_op > m_IRem(const LHS &L, const RHS &R)
Matches integer remainder operations.
apfloat_match m_APFloat(const APFloat *&Res)
Match a ConstantFP or splatted ConstantVector, binding the specified pointer to the contained APFloat...
match_combine_or< match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, smax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, smin_pred_ty > >, match_combine_or< MaxMin_match< ICmpInst, LHS, RHS, umax_pred_ty >, MaxMin_match< ICmpInst, LHS, RHS, umin_pred_ty > > > m_MaxOrMin(const LHS &L, const RHS &R)
CastInst_match< OpTy, FPTruncInst > m_FPTrunc(const OpTy &Op)
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< cst_pred_ty< is_all_ones >, ValTy, Instruction::Xor, true > m_Not(const ValTy &V)
Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
BinaryOp_match< LHS, RHS, Instruction::Or > m_Or(const LHS &L, const RHS &R)
CastInst_match< OpTy, SExtInst > m_SExt(const OpTy &Op)
Matches SExt.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ElementWiseBitCast_match< OpTy > m_ElementWiseBitCast(const OpTy &Op)
m_Intrinsic_Ty< Opnd0 >::Ty m_FAbs(const Opnd0 &Op0)
BinaryOp_match< LHS, RHS, Instruction::Mul, true > m_c_Mul(const LHS &L, const RHS &R)
Matches a Mul with LHS and RHS in either order.
CastOperator_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_unless< Ty > m_Unless(const Ty &M)
Match if the inner matcher does NOT match.
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
cst_pred_ty< icmp_pred_with_threshold > m_SpecificInt_ICMP(ICmpInst::Predicate Predicate, const APInt &Threshold)
Match an integer or vector with every element comparing 'pred' (eg/ne/...) to Threshold.
This is an optimization pass for GlobalISel generic memory operations.
detail::zippy< detail::zip_shortest, T, U, Args... > zip(T &&t, U &&u, Args &&...args)
zip iterator for two or more iteratable types.
@ NeverOverflows
Never overflows.
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
@ MayOverflow
May or may not overflow.
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
bool isSignBitCheck(ICmpInst::Predicate Pred, const APInt &RHS, bool &TrueIfSigned)
Given an exploded icmp instruction, return true if the comparison only checks the sign bit.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
bool isKnownToBeAPowerOfTwo(const Value *V, const DataLayout &DL, bool OrZero=false, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to have exactly one bit set when defined.
Constant * ConstantFoldExtractValueInstruction(Constant *Agg, ArrayRef< unsigned > Idxs)
Attempt to constant fold an extractvalue instruction with the specified operands and indices.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Value * emitGEPOffset(IRBuilderBase *Builder, const DataLayout &DL, User *GEP, bool NoAssumptions=false)
Given a getelementptr instruction/constantexpr, emit the code necessary to compute the offset from th...
constexpr unsigned MaxAnalysisRecursionDepth
Constant * ConstantFoldUnaryOpOperand(unsigned Opcode, Constant *Op, const DataLayout &DL)
Attempt to constant fold a unary operation with the specified operand.
SelectPatternFlavor
Specific patterns of select instructions we can match.
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
SelectPatternResult matchSelectPattern(Value *V, Value *&LHS, Value *&RHS, Instruction::CastOps *CastOp=nullptr, unsigned Depth=0)
Pattern match integer [SU]MIN, [SU]MAX and ABS idioms, returning the kind and providing the out param...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Constant * ConstantFoldCastOperand(unsigned Opcode, Constant *C, Type *DestTy, const DataLayout &DL)
Attempt to constant fold a cast with the specified operand.
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
Value * simplifyICmpInst(unsigned Predicate, Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for an ICmpInst, fold the result or return null.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ Or
Bitwise or logical OR of integers.
@ Mul
Product of integers.
@ Xor
Bitwise or logical XOR of integers.
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ And
Bitwise or logical AND of integers.
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
DWARFExpression::Operation Op
constexpr unsigned BitWidth
auto count_if(R &&Range, UnaryPredicate P)
Wrapper function around std::count_if to count the number of times an element satisfying a given pred...
bool decomposeBitTestICmp(Value *LHS, Value *RHS, CmpInst::Predicate &Pred, Value *&X, APInt &Mask, bool LookThroughTrunc=true)
Decompose an icmp into the form ((X & Mask) pred 0) if possible.
bool all_equal(std::initializer_list< T > Values)
Returns true if all Values in the initializer lists are equal or the list.
bool isKnownNeverNaN(const Value *V, unsigned Depth, const SimplifyQuery &SQ)
Return true if the floating-point scalar value is not a NaN or if the floating-point vector value has...
bool isKnownPositive(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the given value is known be positive (i.e.
Value * simplifyFCmpInst(unsigned Predicate, Value *LHS, Value *RHS, FastMathFlags FMF, const SimplifyQuery &Q)
Given operands for an FCmpInst, fold the result or return null.
bool isKnownNonNegative(const Value *V, const SimplifyQuery &SQ, unsigned Depth=0)
Returns true if the give value is known to be non-negative.
std::optional< bool > isImpliedCondition(const Value *LHS, const Value *RHS, const DataLayout &DL, bool LHSIsTrue=true, unsigned Depth=0)
Return true if RHS is known to be implied true by LHS.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static constexpr roundingMode rmNearestTiesToEven
static constexpr roundingMode rmTowardZero
This callback is used in conjunction with PointerMayBeCaptured.
Represent subnormal handling kind for floating point instruction inputs and outputs.
@ PreserveSign
The sign of a flushed-to-zero number is preserved in the sign of 0.
@ PositiveZero
Denormals are flushed to positive zero.
bool isZero() const
Returns true if value is all zero.
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
APInt getSignedMaxValue() const
Return the maximal signed value possible given these KnownBits.
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
unsigned getBitWidth() const
Get the bit width of this value.
bool isConstant() const
Returns true if we know the value of all bits.
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
unsigned countMinPopulation() const
Returns the number of bits known to be one.
APInt getSignedMinValue() const
Return the minimal signed value possible given these KnownBits.
const APInt & getConstant() const
Returns the value when all bits have a known value.
SelectPatternFlavor Flavor
static bool isMinOrMax(SelectPatternFlavor SPF)
When implementing this min/max pattern as fcmp; select, does the fcmp have to be ordered?
SimplifyQuery getWithInstruction(const Instruction *I) const
const DomConditionCache * DC
A MapVector that performs no allocations if smaller than a certain size.