34using namespace PatternMatch;
36#define DEBUG_TYPE "instcombine"
45 const APInt &In2,
bool IsSigned =
false) {
48 Result = In1.
sadd_ov(In2, Overflow);
50 Result = In1.
uadd_ov(In2, Overflow);
58 const APInt &In2,
bool IsSigned =
false) {
61 Result = In1.
ssub_ov(In2, Overflow);
63 Result = In1.
usub_ov(In2, Overflow);
71 for (
auto *U :
I.users())
72 if (isa<BranchInst>(U))
82 if (!ICmpInst::isSigned(Pred))
89 if (Pred == ICmpInst::ICMP_SLT) {
90 Pred = ICmpInst::ICMP_SLE;
93 }
else if (
C.isAllOnes()) {
94 if (Pred == ICmpInst::ICMP_SGT) {
95 Pred = ICmpInst::ICMP_SGE;
114 if (
LI->isVolatile() ||
LI->getType() !=
GEP->getResultElementType() ||
120 if (!isa<ConstantArray>(
Init) && !isa<ConstantDataArray>(
Init))
123 uint64_t ArrayElementCount =
Init->getType()->getArrayNumElements();
132 if (
GEP->getNumOperands() < 3 || !isa<ConstantInt>(
GEP->getOperand(1)) ||
133 !cast<ConstantInt>(
GEP->getOperand(1))->isZero() ||
134 isa<Constant>(
GEP->getOperand(2)))
142 Type *EltTy =
Init->getType()->getArrayElementType();
143 for (
unsigned i = 3, e =
GEP->getNumOperands(); i != e; ++i) {
149 if ((
unsigned)IdxVal != IdxVal)
152 if (
StructType *STy = dyn_cast<StructType>(EltTy))
153 EltTy = STy->getElementType(IdxVal);
154 else if (
ArrayType *ATy = dyn_cast<ArrayType>(EltTy)) {
155 if (IdxVal >= ATy->getNumElements())
157 EltTy = ATy->getElementType();
165 enum { Overdefined = -3, Undefined = -2 };
174 int FirstTrueElement = Undefined, SecondTrueElement = Undefined;
178 int FirstFalseElement = Undefined, SecondFalseElement = Undefined;
186 int TrueRangeEnd = Undefined, FalseRangeEnd = Undefined;
195 for (
unsigned i = 0, e = ArrayElementCount; i != e; ++i) {
201 if (!LaterIndices.
empty()) {
216 CompareRHS,
DL, &
TLI);
218 if (isa<UndefValue>(
C)) {
221 if (TrueRangeEnd == (
int)i - 1)
223 if (FalseRangeEnd == (
int)i - 1)
230 if (!isa<ConstantInt>(
C))
235 bool IsTrueForElt = !cast<ConstantInt>(
C)->isZero();
240 if (FirstTrueElement == Undefined)
241 FirstTrueElement = TrueRangeEnd = i;
244 if (SecondTrueElement == Undefined)
245 SecondTrueElement = i;
247 SecondTrueElement = Overdefined;
250 if (TrueRangeEnd == (
int)i - 1)
253 TrueRangeEnd = Overdefined;
257 if (FirstFalseElement == Undefined)
258 FirstFalseElement = FalseRangeEnd = i;
261 if (SecondFalseElement == Undefined)
262 SecondFalseElement = i;
264 SecondFalseElement = Overdefined;
267 if (FalseRangeEnd == (
int)i - 1)
270 FalseRangeEnd = Overdefined;
275 if (i < 64 && IsTrueForElt)
276 MagicBitvector |= 1ULL << i;
281 if ((i & 8) == 0 && i >= 64 && SecondTrueElement == Overdefined &&
282 SecondFalseElement == Overdefined && TrueRangeEnd == Overdefined &&
283 FalseRangeEnd == Overdefined)
294 if (!
GEP->isInBounds()) {
297 if (
Idx->getType()->getPrimitiveSizeInBits().getFixedValue() > OffsetSize)
308 unsigned ElementSize =
312 Value *Mask = ConstantInt::get(
Idx->getType(), -1);
321 if (SecondTrueElement != Overdefined) {
324 if (FirstTrueElement == Undefined)
327 Value *FirstTrueIdx = ConstantInt::get(
Idx->getType(), FirstTrueElement);
330 if (SecondTrueElement == Undefined)
335 Value *SecondTrueIdx = ConstantInt::get(
Idx->getType(), SecondTrueElement);
337 return BinaryOperator::CreateOr(C1, C2);
342 if (SecondFalseElement != Overdefined) {
345 if (FirstFalseElement == Undefined)
348 Value *FirstFalseIdx = ConstantInt::get(
Idx->getType(), FirstFalseElement);
351 if (SecondFalseElement == Undefined)
356 Value *SecondFalseIdx =
357 ConstantInt::get(
Idx->getType(), SecondFalseElement);
359 return BinaryOperator::CreateAnd(C1, C2);
364 if (TrueRangeEnd != Overdefined) {
365 assert(TrueRangeEnd != FirstTrueElement &&
"Should emit single compare");
369 if (FirstTrueElement) {
370 Value *Offs = ConstantInt::get(
Idx->getType(), -FirstTrueElement);
375 ConstantInt::get(
Idx->getType(), TrueRangeEnd - FirstTrueElement + 1);
380 if (FalseRangeEnd != Overdefined) {
381 assert(FalseRangeEnd != FirstFalseElement &&
"Should emit single compare");
384 if (FirstFalseElement) {
385 Value *Offs = ConstantInt::get(
Idx->getType(), -FirstFalseElement);
390 ConstantInt::get(
Idx->getType(), FalseRangeEnd - FirstFalseElement);
403 if (ArrayElementCount <= Idx->
getType()->getIntegerBitWidth())
437 while (!WorkList.
empty()) {
440 while (!WorkList.
empty()) {
441 if (Explored.
size() >= 100)
451 if (!isa<GetElementPtrInst>(V) && !isa<PHINode>(V))
456 if (
auto *
GEP = dyn_cast<GEPOperator>(V)) {
458 auto IsNonConst = [](
Value *V) {
return !isa<ConstantInt>(V); };
459 if (!
GEP->isInBounds() ||
count_if(
GEP->indices(), IsNonConst) > 1)
466 if (WorkList.
back() == V) {
472 if (
auto *PN = dyn_cast<PHINode>(V)) {
474 if (isa<CatchSwitchInst>(PN->getParent()->getTerminator()))
482 for (
auto *PN : PHIs)
483 for (
Value *
Op : PN->incoming_values())
491 for (
Value *Val : Explored) {
494 auto *
PHI = dyn_cast<PHINode>(
Use);
495 auto *Inst = dyn_cast<Instruction>(Val);
497 if (Inst ==
Base || Inst ==
PHI || !Inst || !
PHI ||
501 if (
PHI->getParent() == Inst->getParent())
512 if (
auto *
PHI = dyn_cast<PHINode>(V)) {
517 if (
auto *
I = dyn_cast<Instruction>(V)) {
519 I = &*std::next(
I->getIterator());
523 if (
auto *
A = dyn_cast<Argument>(V)) {
525 BasicBlock &Entry =
A->getParent()->getEntryBlock();
531 assert(isa<Constant>(V) &&
"Setting insertion point for unknown value!");
548 Base->getContext(),
DL.getIndexTypeSizeInBits(Start->getType()));
554 for (
Value *Val : Explored) {
559 if (
auto *
PHI = dyn_cast<PHINode>(Val))
562 PHI->getName() +
".idx",
PHI->getIterator());
567 for (
Value *Val : Explored) {
571 if (
auto *
GEP = dyn_cast<GEPOperator>(Val)) {
575 if (isa<ConstantInt>(
Op) && cast<ConstantInt>(
Op)->
isZero())
576 NewInsts[
GEP] = OffsetV;
579 Op, OffsetV,
GEP->getOperand(0)->getName() +
".add");
582 if (isa<PHINode>(Val))
589 for (
Value *Val : Explored) {
594 if (
auto *
PHI = dyn_cast<PHINode>(Val)) {
596 for (
unsigned I = 0, E =
PHI->getNumIncomingValues();
I < E; ++
I) {
597 Value *NewIncoming =
PHI->getIncomingValue(
I);
600 NewIncoming = NewInsts[NewIncoming];
607 for (
Value *Val : Explored) {
614 Builder.
getInt8Ty(),
Base, NewInsts[Val], Val->getName() +
".ptr");
621 return NewInsts[Start];
684 if (!isa<GetElementPtrInst>(
RHS))
696 isa<Constant>(
RHS) && cast<Constant>(
RHS)->isNullValue() &&
718 auto EC = cast<VectorType>(GEPLHS->
getType())->getElementCount();
723 cast<Constant>(
RHS),
Base->getType()));
727 if (PtrBase != GEPRHS->getOperand(0)) {
728 bool IndicesTheSame =
731 GEPRHS->getPointerOperand()->getType() &&
735 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
736 IndicesTheSame =
false;
749 if (GEPLHS->
isInBounds() && GEPRHS->isInBounds() &&
751 (GEPRHS->hasAllConstantIndices() || GEPRHS->hasOneUse()) &&
755 Value *LOffset = EmitGEPOffset(GEPLHS);
756 Value *ROffset = EmitGEPOffset(GEPRHS);
763 if (LHSIndexTy != RHSIndexTy) {
782 bool GEPsInBounds = GEPLHS->
isInBounds() && GEPRHS->isInBounds();
786 unsigned NumDifferences = 0;
787 unsigned DiffOperand = 0;
788 for (
unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
789 if (GEPLHS->
getOperand(i) != GEPRHS->getOperand(i)) {
791 Type *RHSType = GEPRHS->getOperand(i)->getType();
802 if (NumDifferences++)
break;
806 if (NumDifferences == 0)
810 else if (NumDifferences == 1 && GEPsInBounds) {
812 Value *RHSV = GEPRHS->getOperand(DiffOperand);
821 auto *Inst = dyn_cast<Instruction>(
GEP);
828 if (Inst && !
GEP->hasOneUse() && !
GEP->hasAllConstantIndices() &&
829 !
GEP->getSourceElementType()->isIntegerTy(8)) {
832 GEP->getPointerOperand(),
833 Offset,
"", GEPsInBounds));
840 Value *L = EmitGEPOffsetAndRewrite(GEPLHS);
841 Value *R = EmitGEPOffsetAndRewrite(GEPRHS);
868 bool Captured =
false;
873 CmpCaptureTracker(
AllocaInst *Alloca) : Alloca(Alloca) {}
875 void tooManyUses()
override { Captured =
true; }
877 bool captured(
const Use *U)
override {
878 auto *ICmp = dyn_cast<ICmpInst>(U->getUser());
886 auto Res = ICmps.
insert({ICmp, 0});
887 Res.first->second |= 1u << U->getOperandNo();
896 CmpCaptureTracker Tracker(Alloca);
898 if (Tracker.Captured)
901 bool Changed =
false;
902 for (
auto [ICmp,
Operands] : Tracker.ICmps) {
908 auto *Res = ConstantInt::get(
934 assert(!!
C &&
"C should not be zero!");
940 Constant *R = ConstantInt::get(
X->getType(),
950 ConstantInt::get(
X->getType(), -
C));
962 ConstantInt::get(
X->getType(),
SMax -
C));
973 ConstantInt::get(
X->getType(),
SMax - (
C - 1)));
982 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
985 if (
I.getPredicate() ==
I.ICMP_NE)
994 bool IsAShr = isa<AShrOperator>(
I.getOperand(0));
1006 return getICmp(
I.ICMP_UGT,
A,
1007 ConstantInt::get(
A->getType(), AP2.
logBase2()));
1019 if (IsAShr && AP1 == AP2.
ashr(Shift)) {
1023 return getICmp(
I.ICMP_UGE,
A, ConstantInt::get(
A->getType(), Shift));
1024 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1025 }
else if (AP1 == AP2.
lshr(Shift)) {
1026 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1032 auto *TorF = ConstantInt::get(
I.getType(),
I.getPredicate() ==
I.ICMP_NE);
1041 assert(
I.isEquality() &&
"Cannot fold icmp gt/lt");
1044 if (
I.getPredicate() ==
I.ICMP_NE)
1055 if (!AP1 && AP2TrailingZeros != 0)
1058 ConstantInt::get(
A->getType(), AP2.
getBitWidth() - AP2TrailingZeros));
1066 if (Shift > 0 && AP2.
shl(Shift) == AP1)
1067 return getICmp(
I.ICMP_EQ,
A, ConstantInt::get(
A->getType(), Shift));
1071 auto *TorF = ConstantInt::get(
I.getType(),
I.getPredicate() ==
I.ICMP_NE);
1092 Instruction *AddWithCst = cast<Instruction>(
I.getOperand(0));
1100 if (NewWidth != 7 && NewWidth != 15 && NewWidth != 31)
1124 if (U == AddWithCst)
1142 I.getModule(), Intrinsic::sadd_with_overflow, NewType);
1171 if (!
I.isEquality())
1202 APInt(XBitWidth, XBitWidth - 1))))
1204 }
else if (isa<BinaryOperator>(Val) &&
1229 return new ICmpInst(Pred,
B, Cmp.getOperand(1));
1231 return new ICmpInst(Pred,
A, Cmp.getOperand(1));
1248 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1260 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1266 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1268 auto *BO0 = cast<OverflowingBinaryOperator>(Cmp.getOperand(0));
1269 if (BO0->hasNoUnsignedWrap() || BO0->hasNoSignedWrap()) {
1277 return new ICmpInst(Pred,
Y, Cmp.getOperand(1));
1282 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
1314 Value *Op0 = Cmp.getOperand(0), *Op1 = Cmp.getOperand(1);
1327 if (
auto *Phi = dyn_cast<PHINode>(Op0))
1328 if (
all_of(Phi->operands(), [](
Value *V) { return isa<Constant>(V); })) {
1330 for (
Value *V : Phi->incoming_values()) {
1339 for (
auto [V, Pred] :
zip(Ops, Phi->blocks()))
1354 Value *
X = Cmp.getOperand(0), *
Y = Cmp.getOperand(1);
1387 if (Cmp.isEquality() || (IsSignBit &&
hasBranchUse(Cmp)))
1392 if (Cmp.hasOneUse() &&
1406 if (!
match(BI->getCondition(),
1412 if (
auto *V = handleDomCond(DomPred, DomC))
1432 if (
C.isOne() &&
C.getBitWidth() > 1) {
1437 ConstantInt::get(V->getType(), 1));
1440 Type *SrcTy =
X->getType();
1451 auto NewPred = (Pred == Cmp.ICMP_EQ) ? Cmp.ICMP_UGE : Cmp.ICMP_ULT;
1452 return new ICmpInst(NewPred,
Y, ConstantInt::get(SrcTy, DstBits));
1457 return new ICmpInst(Pred,
Y, ConstantInt::get(SrcTy,
C.logBase2()));
1460 if (Cmp.isEquality() && Trunc->
hasOneUse()) {
1463 if (!SrcTy->
isVectorTy() && shouldChangeType(DstBits, SrcBits)) {
1467 Constant *WideC = ConstantInt::get(SrcTy,
C.zext(SrcBits));
1476 if ((Known.
Zero | Known.
One).countl_one() >= SrcBits - DstBits) {
1478 APInt NewRHS =
C.zext(SrcBits);
1480 return new ICmpInst(Pred,
X, ConstantInt::get(SrcTy, NewRHS));
1488 const APInt *ShAmtC;
1512 bool YIsZext =
false;
1515 if (
X->getType() !=
Y->getType() &&
1516 (!Cmp.getOperand(0)->hasOneUse() || !Cmp.getOperand(1)->hasOneUse()))
1518 if (!isDesirableIntType(
X->getType()->getScalarSizeInBits()) &&
1519 isDesirableIntType(
Y->getType()->getScalarSizeInBits())) {
1521 Pred = Cmp.getSwappedPredicate(Pred);
1532 Type *TruncTy = Cmp.getOperand(0)->getType();
1537 if (isDesirableIntType(TruncBits) &&
1538 !isDesirableIntType(
X->getType()->getScalarSizeInBits()))
1573 bool TrueIfSigned =
false;
1590 if (
Xor->hasOneUse()) {
1592 if (!Cmp.isEquality() && XorC->
isSignMask()) {
1593 Pred = Cmp.getFlippedSignednessPredicate();
1594 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(),
C ^ *XorC));
1599 Pred = Cmp.getFlippedSignednessPredicate();
1600 Pred = Cmp.getSwappedPredicate(Pred);
1601 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(),
C ^ *XorC));
1608 if (*XorC == ~
C && (
C + 1).isPowerOf2())
1611 if (*XorC ==
C && (
C + 1).isPowerOf2())
1616 if (*XorC == -
C &&
C.isPowerOf2())
1618 ConstantInt::get(
X->getType(), ~
C));
1620 if (*XorC ==
C && (-
C).isPowerOf2())
1622 ConstantInt::get(
X->getType(), ~
C));
1644 const APInt *ShiftC;
1649 Type *XType =
X->getType();
1655 return new ICmpInst(Pred,
Add, ConstantInt::get(XType, Bound));
1664 if (!Shift || !Shift->
isShift())
1672 unsigned ShiftOpcode = Shift->
getOpcode();
1673 bool IsShl = ShiftOpcode == Instruction::Shl;
1676 APInt NewAndCst, NewCmpCst;
1677 bool AnyCmpCstBitsShiftedOut;
1678 if (ShiftOpcode == Instruction::Shl) {
1686 NewCmpCst = C1.
lshr(*C3);
1687 NewAndCst = C2.
lshr(*C3);
1688 AnyCmpCstBitsShiftedOut = NewCmpCst.
shl(*C3) != C1;
1689 }
else if (ShiftOpcode == Instruction::LShr) {
1694 NewCmpCst = C1.
shl(*C3);
1695 NewAndCst = C2.
shl(*C3);
1696 AnyCmpCstBitsShiftedOut = NewCmpCst.
lshr(*C3) != C1;
1702 assert(ShiftOpcode == Instruction::AShr &&
"Unknown shift opcode");
1703 NewCmpCst = C1.
shl(*C3);
1704 NewAndCst = C2.
shl(*C3);
1705 AnyCmpCstBitsShiftedOut = NewCmpCst.
ashr(*C3) != C1;
1706 if (NewAndCst.
ashr(*C3) != C2)
1710 if (AnyCmpCstBitsShiftedOut) {
1720 Shift->
getOperand(0), ConstantInt::get(
And->getType(), NewAndCst));
1721 return new ICmpInst(Cmp.getPredicate(),
1722 NewAnd, ConstantInt::get(
And->getType(), NewCmpCst));
1753 if (isICMP_NE && Cmp.getType()->isVectorTy() && C1.
isZero() &&
1755 return new TruncInst(
And->getOperand(0), Cmp.getType());
1763 if (!
And->hasOneUse())
1766 if (Cmp.isEquality() && C1.
isZero()) {
1784 Constant *NegBOC = ConstantInt::get(
And->getType(), -NewC2);
1786 return new ICmpInst(NewPred,
X, NegBOC);
1804 if (!Cmp.getType()->isVectorTy()) {
1805 Type *WideType = W->getType();
1807 Constant *ZextC1 = ConstantInt::get(WideType, C1.
zext(WideScalarBits));
1808 Constant *ZextC2 = ConstantInt::get(WideType, C2->
zext(WideScalarBits));
1810 return new ICmpInst(Cmp.getPredicate(), NewAnd, ZextC1);
1821 if (!Cmp.isSigned() && C1.
isZero() &&
And->getOperand(0)->hasOneUse() &&
1823 Constant *One = cast<Constant>(
And->getOperand(1));
1828 unsigned UsesRemoved = 0;
1829 if (
And->hasOneUse())
1831 if (
Or->hasOneUse())
1838 if (UsesRemoved >= RequireUsesRemoved) {
1842 One,
Or->getName());
1854 if (!Cmp.getParent()->getParent()->hasFnAttribute(
1855 Attribute::NoImplicitFloat) &&
1858 Type *FPType = V->getType()->getScalarType();
1860 APInt ExponentMask =
1862 if (C1 == ExponentMask) {
1895 Constant *MinSignedC = ConstantInt::get(
1899 return new ICmpInst(NewPred,
X, MinSignedC);
1908 if (
auto *C2 = dyn_cast<ConstantInt>(
Y))
1909 if (
auto *
LI = dyn_cast<LoadInst>(
X))
1910 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(
LI->getOperand(0)))
1911 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
1916 if (!Cmp.isEquality())
1922 if (Cmp.getOperand(1) ==
Y &&
C.isNegatedPowerOf2()) {
1925 return new ICmpInst(NewPred,
X,
SubOne(cast<Constant>(Cmp.getOperand(1))));
1938 assert(Cmp.isEquality() &&
"Not expecting non-equality predicates");
1940 const APInt *TC, *FC;
1957 X->getType()->isIntOrIntVectorTy(1) && (
C.isZero() ||
C.isOne())) {
1963 return BinaryOperator::CreateAnd(TruncY,
X);
1995 while (!WorkList.
empty()) {
1996 auto MatchOrOperatorArgument = [&](
Value *OrOperatorArgument) {
1999 if (
match(OrOperatorArgument,
2005 if (
match(OrOperatorArgument,
2015 Value *OrOperatorLhs, *OrOperatorRhs;
2017 if (!
match(CurrentValue,
2022 MatchOrOperatorArgument(OrOperatorRhs);
2023 MatchOrOperatorArgument(OrOperatorLhs);
2029 CmpValues.
rbegin()->second);
2031 for (
auto It = CmpValues.
rbegin() + 1; It != CmpValues.
rend(); ++It) {
2033 LhsCmp = Builder.
CreateBinOp(BOpc, LhsCmp, RhsCmp);
2049 ConstantInt::get(V->getType(), 1));
2052 Value *OrOp0 =
Or->getOperand(0), *OrOp1 =
Or->getOperand(1);
2057 cast<PossiblyDisjointInst>(
Or)->isDisjoint()) {
2060 return new ICmpInst(Pred, OrOp0, NewC);
2064 if (
match(OrOp1,
m_APInt(MaskC)) && Cmp.isEquality()) {
2065 if (*MaskC ==
C && (
C + 1).isPowerOf2()) {
2070 return new ICmpInst(Pred, OrOp0, OrOp1);
2077 if (
Or->hasOneUse()) {
2079 Constant *NewC = ConstantInt::get(
Or->getType(),
C ^ (*MaskC));
2091 Constant *NewC = ConstantInt::get(
X->getType(), TrueIfSigned ? 1 : 0);
2119 if (!Cmp.isEquality() || !
C.isZero() || !
Or->hasOneUse())
2151 if (Cmp.isEquality() &&
C.isZero() &&
X ==
Mul->getOperand(1) &&
2152 (
Mul->hasNoUnsignedWrap() ||
Mul->hasNoSignedWrap()))
2174 if (Cmp.isEquality()) {
2176 if (
Mul->hasNoSignedWrap() &&
C.srem(*MulC).isZero()) {
2177 Constant *NewC = ConstantInt::get(MulTy,
C.sdiv(*MulC));
2185 if (
C.urem(*MulC).isZero()) {
2188 if ((*MulC & 1).isOne() ||
Mul->hasNoUnsignedWrap()) {
2189 Constant *NewC = ConstantInt::get(MulTy,
C.udiv(*MulC));
2202 if (
C.isMinSignedValue() && MulC->
isAllOnes())
2208 NewC = ConstantInt::get(
2212 "Unexpected predicate");
2213 NewC = ConstantInt::get(
2218 NewC = ConstantInt::get(
2222 "Unexpected predicate");
2223 NewC = ConstantInt::get(
2228 return NewC ?
new ICmpInst(Pred,
X, NewC) :
nullptr;
2239 unsigned TypeBits =
C.getBitWidth();
2240 bool CIsPowerOf2 =
C.isPowerOf2();
2242 if (Cmp.isUnsigned()) {
2255 unsigned CLog2 =
C.logBase2();
2256 return new ICmpInst(Pred,
Y, ConstantInt::get(ShiftType, CLog2));
2257 }
else if (Cmp.isSigned()) {
2258 Constant *BitWidthMinusOne = ConstantInt::get(ShiftType, TypeBits - 1);
2279 const APInt *ShiftVal;
2309 const APInt *ShiftAmt;
2315 unsigned TypeBits =
C.getBitWidth();
2316 if (ShiftAmt->
uge(TypeBits))
2328 APInt ShiftedC =
C.ashr(*ShiftAmt);
2329 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2332 C.ashr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2333 APInt ShiftedC =
C.ashr(*ShiftAmt);
2334 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2341 assert(!
C.isMinSignedValue() &&
"Unexpected icmp slt");
2342 APInt ShiftedC = (
C - 1).ashr(*ShiftAmt) + 1;
2343 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2353 APInt ShiftedC =
C.lshr(*ShiftAmt);
2354 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2357 C.lshr(*ShiftAmt).shl(*ShiftAmt) ==
C) {
2358 APInt ShiftedC =
C.lshr(*ShiftAmt);
2359 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2366 assert(
C.ugt(0) &&
"ult 0 should have been eliminated");
2367 APInt ShiftedC = (
C - 1).lshr(*ShiftAmt) + 1;
2368 return new ICmpInst(Pred,
X, ConstantInt::get(ShType, ShiftedC));
2372 if (Cmp.isEquality() && Shl->
hasOneUse()) {
2378 Constant *LShrC = ConstantInt::get(ShType,
C.lshr(*ShiftAmt));
2383 bool TrueIfSigned =
false;
2395 if (Cmp.isUnsigned() && Shl->
hasOneUse()) {
2397 if ((
C + 1).isPowerOf2() &&
2405 if (
C.isPowerOf2() &&
2422 if (Shl->
hasOneUse() && Amt != 0 &&
C.countr_zero() >= Amt &&
2425 if (
auto *ShVTy = dyn_cast<VectorType>(ShType))
2428 ConstantInt::get(TruncTy,
C.ashr(*ShiftAmt).trunc(TypeBits - Amt));
2443 if (Cmp.isEquality() && Shr->
isExact() &&
C.isZero())
2444 return new ICmpInst(Pred,
X, Cmp.getOperand(1));
2446 bool IsAShr = Shr->
getOpcode() == Instruction::AShr;
2447 const APInt *ShiftValC;
2449 if (Cmp.isEquality())
2467 assert(ShiftValC->
uge(
C) &&
"Expected simplify of compare");
2468 assert((IsUGT || !
C.isZero()) &&
"Expected X u< 0 to simplify");
2470 unsigned CmpLZ = IsUGT ?
C.countl_zero() : (
C - 1).
countl_zero();
2478 const APInt *ShiftAmtC;
2484 unsigned TypeBits =
C.getBitWidth();
2486 if (ShAmtVal >= TypeBits || ShAmtVal == 0)
2489 bool IsExact = Shr->
isExact();
2500 APInt ShiftedC =
C.shl(ShAmtVal);
2501 if (ShiftedC.
ashr(ShAmtVal) ==
C)
2502 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2506 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2507 if (!
C.isMaxSignedValue() && !(
C + 1).shl(ShAmtVal).isMinSignedValue() &&
2508 (ShiftedC + 1).ashr(ShAmtVal) == (
C + 1))
2509 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2515 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2516 if ((ShiftedC + 1).ashr(ShAmtVal) == (
C + 1) ||
2517 (
C + 1).shl(ShAmtVal).isMinSignedValue())
2518 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2525 if (
C.getBitWidth() > 2 &&
C.getNumSignBits() <= ShAmtVal) {
2535 }
else if (!IsAShr) {
2539 APInt ShiftedC =
C.shl(ShAmtVal);
2540 if (ShiftedC.
lshr(ShAmtVal) ==
C)
2541 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2545 APInt ShiftedC = (
C + 1).shl(ShAmtVal) - 1;
2546 if ((ShiftedC + 1).lshr(ShAmtVal) == (
C + 1))
2547 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy, ShiftedC));
2551 if (!Cmp.isEquality())
2559 assert(((IsAShr &&
C.shl(ShAmtVal).ashr(ShAmtVal) ==
C) ||
2560 (!IsAShr &&
C.shl(ShAmtVal).lshr(ShAmtVal) ==
C)) &&
2561 "Expected icmp+shr simplify did not occur.");
2566 return new ICmpInst(Pred,
X, ConstantInt::get(ShrTy,
C << ShAmtVal));
2572 ConstantInt::get(ShrTy, (
C + 1).shl(ShAmtVal)));
2575 ConstantInt::get(ShrTy, (
C + 1).shl(ShAmtVal) - 1));
2582 Constant *Mask = ConstantInt::get(ShrTy, Val);
2584 return new ICmpInst(Pred,
And, ConstantInt::get(ShrTy,
C << ShAmtVal));
2607 const APInt *DivisorC;
2616 !
C.isStrictlyPositive()))
2622 Constant *MaskC = ConstantInt::get(Ty, SignMask | (*DivisorC - 1));
2626 return new ICmpInst(Pred,
And, ConstantInt::get(Ty,
C));
2653 assert(*C2 != 0 &&
"udiv 0, X should have been simplified already.");
2658 "icmp ugt X, UINT_MAX should have been simplified already.");
2660 ConstantInt::get(Ty, C2->
udiv(
C + 1)));
2665 assert(
C != 0 &&
"icmp ult X, 0 should have been simplified already.");
2667 ConstantInt::get(Ty, C2->
udiv(
C)));
2681 bool DivIsSigned = Div->
getOpcode() == Instruction::SDiv;
2691 if (Cmp.isEquality() && Div->
hasOneUse() &&
C.isSignBitSet() &&
2692 (!DivIsSigned ||
C.isMinSignedValue())) {
2717 if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
2736 bool ProdOV = (DivIsSigned ? Prod.
sdiv(*C2) : Prod.
udiv(*C2)) !=
C;
2749 int LoOverflow = 0, HiOverflow = 0;
2750 APInt LoBound, HiBound;
2755 HiOverflow = LoOverflow = ProdOV;
2764 LoBound = -(RangeSize - 1);
2765 HiBound = RangeSize;
2766 }
else if (
C.isStrictlyPositive()) {
2768 HiOverflow = LoOverflow = ProdOV;
2774 LoOverflow = HiOverflow = ProdOV ? -1 : 0;
2776 APInt DivNeg = -RangeSize;
2777 LoOverflow =
addWithOverflow(LoBound, HiBound, DivNeg,
true) ? -1 : 0;
2785 LoBound = RangeSize + 1;
2786 HiBound = -RangeSize;
2787 if (HiBound == *C2) {
2791 }
else if (
C.isStrictlyPositive()) {
2794 HiOverflow = LoOverflow = ProdOV ? -1 : 0;
2800 LoOverflow = HiOverflow = ProdOV;
2813 if (LoOverflow && HiOverflow)
2817 X, ConstantInt::get(Ty, LoBound));
2820 X, ConstantInt::get(Ty, HiBound));
2824 if (LoOverflow && HiOverflow)
2828 X, ConstantInt::get(Ty, LoBound));
2831 X, ConstantInt::get(Ty, HiBound));
2836 if (LoOverflow == +1)
2838 if (LoOverflow == -1)
2840 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, LoBound));
2843 if (HiOverflow == +1)
2845 if (HiOverflow == -1)
2878 ((Cmp.isUnsigned() && HasNUW) || (Cmp.isSigned() && HasNSW)) &&
2880 return new ICmpInst(SwappedPred,
Y, ConstantInt::get(Ty, SubResult));
2888 if (Cmp.isEquality() &&
C.isZero() &&
2924 (*C2 & (
C - 1)) == (
C - 1))
2937 return new ICmpInst(SwappedPred,
Add, ConstantInt::get(Ty, ~
C));
2943 auto FoldConstant = [&](
bool Val) {
2947 cast<VectorType>(Op0->
getType())->getElementCount(), Res);
2951 switch (Table.to_ulong()) {
2953 return FoldConstant(
false);
2983 return FoldConstant(
true);
3006 unsigned BW =
C.getBitWidth();
3007 std::bitset<4> Table;
3008 auto ComputeTable = [&](
bool Op0Val,
bool Op1Val) {
3011 Res += isa<ZExtInst>(Ext0) ? 1 : -1;
3013 Res += isa<ZExtInst>(Ext1) ? 1 : -1;
3017 Table[0] = ComputeTable(
false,
false);
3018 Table[1] = ComputeTable(
false,
true);
3019 Table[2] = ComputeTable(
true,
false);
3020 Table[3] = ComputeTable(
true,
true);
3035 if ((
Add->hasNoSignedWrap() &&
3037 (
Add->hasNoUnsignedWrap() &&
3041 Cmp.isSigned() ?
C.ssub_ov(*C2, Overflow) :
C.usub_ov(*C2, Overflow);
3047 return new ICmpInst(Pred,
X, ConstantInt::get(Ty, NewC));
3053 if (Cmp.isSigned()) {
3054 if (
Lower.isSignMask())
3056 if (
Upper.isSignMask())
3059 if (
Lower.isMinValue())
3061 if (
Upper.isMinValue())
3094 if (!
Add->hasOneUse())
3117 ConstantInt::get(Ty, ~
C));
3137 Value *EqualVal = SI->getTrueValue();
3138 Value *UnequalVal = SI->getFalseValue();
3161 auto FlippedStrictness =
3163 PredB, cast<Constant>(RHS2));
3164 if (!FlippedStrictness)
3167 "basic correctness failure");
3168 RHS2 = FlippedStrictness->second;
3180 assert(
C &&
"Cmp RHS should be a constant int!");
3186 Value *OrigLHS, *OrigRHS;
3187 ConstantInt *C1LessThan, *C2Equal, *C3GreaterThan;
3188 if (Cmp.hasOneUse() &&
3191 assert(C1LessThan && C2Equal && C3GreaterThan);
3193 bool TrueWhenLessThan =
3196 bool TrueWhenEqual =
3199 bool TrueWhenGreaterThan =
3212 if (TrueWhenLessThan)
3218 if (TrueWhenGreaterThan)
3228 auto *Bitcast = dyn_cast<BitCastInst>(Cmp.getOperand(0));
3233 Value *Op1 = Cmp.getOperand(1);
3234 Value *BCSrcOp = Bitcast->getOperand(0);
3235 Type *SrcType = Bitcast->getSrcTy();
3236 Type *DstType = Bitcast->getType();
3256 return new ICmpInst(Pred,
X, ConstantInt::get(
X->getType(), 1));
3283 Type *XType =
X->getType();
3288 if (
auto *XVTy = dyn_cast<VectorType>(XType))
3302 if (!Cmp.getParent()->getParent()->hasFnAttribute(
3303 Attribute::NoImplicitFloat) &&
3328 if (Cmp.isEquality() &&
C->isAllOnes() && Bitcast->hasOneUse()) {
3329 if (
Value *NotBCSrcOp =
3340 if (Cmp.isEquality() &&
C->isZero() && Bitcast->hasOneUse() &&
3342 if (
auto *VecTy = dyn_cast<FixedVectorType>(
X->getType())) {
3361 auto *VecTy = cast<VectorType>(SrcType);
3362 auto *EltTy = cast<IntegerType>(VecTy->getElementType());
3363 if (
C->isSplat(EltTy->getBitWidth())) {
3371 Value *NewC = ConstantInt::get(EltTy,
C->trunc(EltTy->getBitWidth()));
3372 return new ICmpInst(Pred, Extract, NewC);
3385 if (
auto *BO = dyn_cast<BinaryOperator>(Cmp.getOperand(0)))
3389 if (
auto *SI = dyn_cast<SelectInst>(Cmp.getOperand(0)))
3393 if (
auto *ConstRHS = dyn_cast<ConstantInt>(Cmp.getOperand(1)))
3397 if (
auto *TI = dyn_cast<TruncInst>(Cmp.getOperand(0)))
3401 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0)))
3408 Value *Cmp0 = Cmp.getOperand(0);
3410 if (
C->isZero() && Cmp.isEquality() && Cmp0->
hasOneUse() &&
3412 m_ExtractValue<0>(m_Intrinsic<Intrinsic::ssub_with_overflow>(
3415 m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
3417 return new ICmpInst(Cmp.getPredicate(),
X,
Y);
3432 if (!Cmp.isEquality())
3437 Constant *
RHS = cast<Constant>(Cmp.getOperand(1));
3441 case Instruction::SRem:
3452 case Instruction::Add: {
3456 if (
Constant *C2 = dyn_cast<Constant>(BOp1)) {
3459 }
else if (
C.isZero()) {
3462 if (
Value *NegVal = dyn_castNegVal(BOp1))
3463 return new ICmpInst(Pred, BOp0, NegVal);
3464 if (
Value *NegVal = dyn_castNegVal(BOp0))
3465 return new ICmpInst(Pred, NegVal, BOp1);
3474 return new ICmpInst(Pred, BOp0, Neg);
3479 case Instruction::Xor:
3481 if (
Constant *BOC = dyn_cast<Constant>(BOp1)) {
3485 }
else if (
C.isZero()) {
3487 return new ICmpInst(Pred, BOp0, BOp1);
3491 case Instruction::Or: {
3503 case Instruction::UDiv:
3504 case Instruction::SDiv:
3514 return new ICmpInst(Pred, BOp0, BOp1);
3517 Instruction::Mul, BO->
getOpcode() == Instruction::SDiv, BOp1,
3518 Cmp.getOperand(1), BO);
3522 return new ICmpInst(Pred, YC, BOp0);
3526 if (BO->
getOpcode() == Instruction::UDiv &&
C.isZero()) {
3529 return new ICmpInst(NewPred, BOp1, BOp0);
3543 "Non-ctpop intrin in ctpop fold");
3584 case Intrinsic::abs:
3587 if (
C.isZero() ||
C.isMinSignedValue())
3591 case Intrinsic::bswap:
3594 ConstantInt::get(Ty,
C.byteSwap()));
3596 case Intrinsic::bitreverse:
3599 ConstantInt::get(Ty,
C.reverseBits()));
3601 case Intrinsic::ctlz:
3602 case Intrinsic::cttz: {
3611 unsigned Num =
C.getLimitedValue(
BitWidth);
3616 APInt Mask2 = IsTrailing
3620 ConstantInt::get(Ty, Mask2));
3625 case Intrinsic::ctpop: {
3628 bool IsZero =
C.isZero();
3637 case Intrinsic::fshl:
3638 case Intrinsic::fshr:
3640 const APInt *RotAmtC;
3646 ? ConstantInt::get(Ty,
C.rotr(*RotAmtC))
3647 : ConstantInt::get(Ty,
C.rotl(*RotAmtC)));
3651 case Intrinsic::umax:
3652 case Intrinsic::uadd_sat: {
3662 case Intrinsic::ssub_sat:
3667 case Intrinsic::usub_sat: {
3687 assert(Cmp.isEquality());
3690 Value *Op0 = Cmp.getOperand(0);
3691 Value *Op1 = Cmp.getOperand(1);
3692 const auto *IIOp0 = dyn_cast<IntrinsicInst>(Op0);
3693 const auto *IIOp1 = dyn_cast<IntrinsicInst>(Op1);
3694 if (!IIOp0 || !IIOp1 || IIOp0->getIntrinsicID() != IIOp1->getIntrinsicID())
3697 switch (IIOp0->getIntrinsicID()) {
3698 case Intrinsic::bswap:
3699 case Intrinsic::bitreverse:
3702 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3703 case Intrinsic::fshl:
3704 case Intrinsic::fshr: {
3707 if (IIOp0->getOperand(0) != IIOp0->getOperand(1))
3709 if (IIOp1->getOperand(0) != IIOp1->getOperand(1))
3711 if (IIOp0->getOperand(2) == IIOp1->getOperand(2))
3712 return new ICmpInst(Pred, IIOp0->getOperand(0), IIOp1->getOperand(0));
3718 unsigned OneUses = IIOp0->hasOneUse() + IIOp1->hasOneUse();
3723 Builder.
CreateSub(IIOp0->getOperand(2), IIOp1->getOperand(2));
3725 Op0->
getType(), IIOp0->getIntrinsicID(),
3726 {IIOp0->getOperand(0), IIOp0->getOperand(0), SubAmt});
3727 return new ICmpInst(Pred, IIOp1->getOperand(0), CombinedRotate);
3744 if (
auto *II = dyn_cast<IntrinsicInst>(Cmp.getOperand(0))) {
3745 switch (II->getIntrinsicID()) {
3748 case Intrinsic::fshl:
3749 case Intrinsic::fshr:
3750 if (Cmp.isEquality() && II->getArgOperand(0) == II->getArgOperand(1)) {
3752 if (
C.isZero() ||
C.isAllOnes())
3753 return new ICmpInst(Pred, II->getArgOperand(0), Cmp.getOperand(1));
3767 case Instruction::Xor:
3771 case Instruction::And:
3775 case Instruction::Or:
3779 case Instruction::Mul:
3783 case Instruction::Shl:
3787 case Instruction::LShr:
3788 case Instruction::AShr:
3792 case Instruction::SRem:
3796 case Instruction::UDiv:
3800 case Instruction::SDiv:
3804 case Instruction::Sub:
3808 case Instruction::Add:
3855 "This function only works with usub_sat and uadd_sat for now!");
3856 case Intrinsic::uadd_sat:
3859 case Intrinsic::usub_sat:
3882 SatValCheck ? Instruction::BinaryOps::Or : Instruction::BinaryOps::And;
3884 std::optional<ConstantRange> Combination;
3885 if (CombiningOp == Instruction::BinaryOps::Or)
3897 Combination->getEquivalentICmp(EquivPred, EquivInt, EquivOffset);
3902 ConstantInt::get(Op1->
getType(), EquivInt));
3915 case Intrinsic::uadd_sat:
3916 case Intrinsic::usub_sat:
3918 Pred, cast<SaturatingInst>(II),
C,
Builder))
3921 case Intrinsic::ctpop: {
3928 if (Cmp.isEquality())
3934 case Intrinsic::ctpop: {
3946 case Intrinsic::ctlz: {
3949 unsigned Num =
C.getLimitedValue();
3957 unsigned Num =
C.getLimitedValue();
3964 case Intrinsic::cttz: {
3986 case Intrinsic::ssub_sat:
4010 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4011 Constant *RHSC = dyn_cast<Constant>(Op1);
4017 case Instruction::PHI:
4021 case Instruction::IntToPtr:
4030 case Instruction::Load:
4033 dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
4049 auto SimplifyOp = [&](
Value *
Op,
bool SelectCondIsTrue) ->
Value * {
4053 SI->getCondition(), Pred,
Op,
RHS,
DL, SelectCondIsTrue))
4054 return ConstantInt::get(
I.getType(), *Impl);
4059 Value *Op1 = SimplifyOp(SI->getOperand(1),
true);
4061 CI = dyn_cast<ConstantInt>(Op1);
4063 Value *Op2 = SimplifyOp(SI->getOperand(2),
false);
4065 CI = dyn_cast<ConstantInt>(Op2);
4074 bool Transform =
false;
4077 else if (Op1 || Op2) {
4079 if (SI->hasOneUse())
4082 else if (CI && !CI->
isZero())
4101 unsigned Depth = 0) {
4104 if (V->getType()->getScalarSizeInBits() == 1)
4112 switch (
I->getOpcode()) {
4113 case Instruction::ZExt:
4116 case Instruction::SExt:
4120 case Instruction::And:
4121 case Instruction::Or:
4128 case Instruction::Xor:
4138 case Instruction::Select:
4142 case Instruction::Shl:
4145 case Instruction::LShr:
4148 case Instruction::AShr:
4152 case Instruction::Add:
4158 case Instruction::Sub:
4164 case Instruction::Call: {
4165 if (
auto *II = dyn_cast<IntrinsicInst>(
I)) {
4166 switch (II->getIntrinsicID()) {
4169 case Intrinsic::umax:
4170 case Intrinsic::smax:
4171 case Intrinsic::umin:
4172 case Intrinsic::smin:
4177 case Intrinsic::bitreverse:
4267 auto IsLowBitMask = [&]() {
4285 auto Check = [&]() {
4303 auto Check = [&]() {
4322 if (!IsLowBitMask())
4329 Type *OpTy = M->getType();
4330 auto *VecC = dyn_cast<Constant>(M);
4331 auto *OpVTy = dyn_cast<FixedVectorType>(OpTy);
4332 if (OpVTy && VecC && VecC->containsUndefOrPoisonElement()) {
4333 Constant *SafeReplacementConstant =
nullptr;
4334 for (
unsigned i = 0, e = OpVTy->getNumElements(); i != e; ++i) {
4335 if (!isa<UndefValue>(VecC->getAggregateElement(i))) {
4340 assert(SafeReplacementConstant &&
"Failed to find undef replacement");
4360 const APInt *C0, *C1;
4377 const APInt &MaskedBits = *C0;
4378 assert(MaskedBits != 0 &&
"shift by zero should be folded away already.");
4399 auto *XType =
X->getType();
4400 const unsigned XBitWidth = XType->getScalarSizeInBits();
4402 assert(
BitWidth.ugt(MaskedBits) &&
"shifts should leave some bits untouched");
4433 !
I.getOperand(0)->hasOneUse())
4458 assert(NarrowestTy ==
I.getOperand(0)->getType() &&
4459 "We did not look past any shifts while matching XShift though.");
4460 bool HadTrunc = WidestTy !=
I.getOperand(0)->getType();
4467 auto XShiftOpcode = XShift->
getOpcode();
4468 if (XShiftOpcode == YShift->
getOpcode())
4471 Value *
X, *XShAmt, *
Y, *YShAmt;
4478 if (!isa<Constant>(
X) && !isa<Constant>(
Y)) {
4480 if (!
match(
I.getOperand(0),
4506 unsigned MaximalPossibleTotalShiftAmount =
4509 APInt MaximalRepresentableShiftAmount =
4511 if (MaximalRepresentableShiftAmount.
ult(MaximalPossibleTotalShiftAmount))
4515 auto *NewShAmt = dyn_cast_or_null<Constant>(
4520 if (NewShAmt->getType() != WidestTy) {
4530 if (!
match(NewShAmt,
4532 APInt(WidestBitWidth, WidestBitWidth))))
4537 auto CanFold = [NewShAmt, WidestBitWidth, NarrowestShift, SQ,
4543 ? NewShAmt->getSplatValue()
4546 if (NewShAmtSplat &&
4552 if (
auto *
C = dyn_cast<Constant>(NarrowestShift->getOperand(0))) {
4556 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4557 if (MaxActiveBits <= 1)
4563 if (
auto *
C = dyn_cast<Constant>(WidestShift->
getOperand(0))) {
4567 unsigned MaxActiveBits = Known.
getBitWidth() - MinLeadZero;
4568 if (MaxActiveBits <= 1)
4571 if (NewShAmtSplat) {
4574 if (AdjNewShAmt.
ule(MinLeadZero))
4588 Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
4610 if (!
I.isEquality() &&
4620 NeedNegation =
false;
4623 NeedNegation =
true;
4629 if (
I.isEquality() &&
4645 bool MulHadOtherUses =
Mul && !
Mul->hasOneUse();
4646 if (MulHadOtherUses)
4651 ? Intrinsic::umul_with_overflow
4652 : Intrinsic::smul_with_overflow,
4659 if (MulHadOtherUses)
4668 if (MulHadOtherUses)
4694 Type *Ty =
X->getType();
4708 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4732 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4767 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1), *
A;
4783 return new ICmpInst(PredOut, Op0, Op1);
4795 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
4851 return new ICmpInst(NewPred, Op1, Zero);
4860 return new ICmpInst(NewPred, Op0, Zero);
4864 bool NoOp0WrapProblem =
false, NoOp1WrapProblem =
false;
4865 bool Op0HasNUW =
false, Op1HasNUW =
false;
4866 bool Op0HasNSW =
false, Op1HasNSW =
false;
4870 bool &HasNSW,
bool &HasNUW) ->
bool {
4871 if (isa<OverflowingBinaryOperator>(BO)) {
4877 }
else if (BO.
getOpcode() == Instruction::Or) {
4885 Value *
A =
nullptr, *
B =
nullptr, *
C =
nullptr, *
D =
nullptr;
4889 NoOp0WrapProblem = hasNoWrapProblem(*BO0, Pred, Op0HasNSW, Op0HasNUW);
4893 NoOp1WrapProblem = hasNoWrapProblem(*BO1, Pred, Op1HasNSW, Op1HasNUW);
4898 if ((
A == Op1 ||
B == Op1) && NoOp0WrapProblem)
4904 if ((
C == Op0 ||
D == Op0) && NoOp1WrapProblem)
4909 if (
A &&
C && (
A ==
C ||
A ==
D ||
B ==
C ||
B ==
D) && NoOp0WrapProblem &&
4917 }
else if (
A ==
D) {
4921 }
else if (
B ==
C) {
5002 if (
A &&
C && NoOp0WrapProblem && NoOp1WrapProblem &&
5004 const APInt *AP1, *AP2;
5012 if (AP1Abs.
uge(AP2Abs)) {
5013 APInt Diff = *AP1 - *AP2;
5016 A, C3,
"", Op0HasNUW && Diff.
ule(*AP1), Op0HasNSW);
5019 APInt Diff = *AP2 - *AP1;
5022 C, C3,
"", Op1HasNUW && Diff.
ule(*AP2), Op1HasNSW);
5041 if (BO0 && BO0->
getOpcode() == Instruction::Sub) {
5045 if (BO1 && BO1->
getOpcode() == Instruction::Sub) {
5051 if (
A == Op1 && NoOp0WrapProblem)
5054 if (
C == Op0 && NoOp1WrapProblem)
5074 if (
B &&
D &&
B ==
D && NoOp0WrapProblem && NoOp1WrapProblem)
5078 if (
A &&
C &&
A ==
C && NoOp0WrapProblem && NoOp1WrapProblem)
5085 if (
Constant *RHSC = dyn_cast<Constant>(Op1))
5086 if (RHSC->isNotMinSignedValue())
5087 return new ICmpInst(
I.getSwappedPredicate(),
X,
5115 if (NonZero && BO0 && BO1 && Op0HasNSW && Op1HasNSW)
5122 if (NonZero && BO0 && BO1 && Op0HasNUW && Op1HasNUW)
5132 else if (BO1 && BO1->
getOpcode() == Instruction::SRem &&
5162 case Instruction::Add:
5163 case Instruction::Sub:
5164 case Instruction::Xor: {
5171 if (
C->isSignMask()) {
5177 if (BO0->
getOpcode() == Instruction::Xor &&
C->isMaxSignedValue()) {
5179 NewPred =
I.getSwappedPredicate(NewPred);
5185 case Instruction::Mul: {
5186 if (!
I.isEquality())
5194 if (
unsigned TZs =
C->countr_zero()) {
5200 return new ICmpInst(Pred, And1, And2);
5205 case Instruction::UDiv:
5206 case Instruction::LShr:
5211 case Instruction::SDiv:
5217 case Instruction::AShr:
5222 case Instruction::Shl: {
5223 bool NUW = Op0HasNUW && Op1HasNUW;
5224 bool NSW = Op0HasNSW && Op1HasNSW;
5227 if (!NSW &&
I.isSigned())
5292 auto IsCondKnownTrue = [](
Value *Val) -> std::optional<bool> {
5294 return std::nullopt;
5299 return std::nullopt;
5303 if (!CmpXZ.has_value() && !CmpYZ.has_value())
5305 if (!CmpXZ.has_value()) {
5311 if (CmpYZ.has_value())
5335 if (!MinMaxCmpXZ.has_value()) {
5343 if (!MinMaxCmpXZ.has_value())
5359 return FoldIntoCmpYZ();
5386 return FoldIntoCmpYZ();
5395 return FoldIntoCmpYZ();
5417 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
5421 if (
I.isEquality()) {
5456 Type *Ty =
A->getType();
5459 ConstantInt::get(Ty, 2))
5461 ConstantInt::get(Ty, 1));
5468 if (!
I.isEquality())
5471 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
5475 if (
A == Op1 ||
B == Op1) {
5476 Value *OtherVal =
A == Op1 ?
B :
A;
5519 Value *OtherVal =
A == Op0 ?
B :
A;
5526 Value *
X =
nullptr, *
Y =
nullptr, *Z =
nullptr;
5532 }
else if (
A ==
D) {
5536 }
else if (
B ==
C) {
5540 }
else if (
B ==
D) {
5567 (Op0->
hasOneUse() || Op1->hasOneUse())) {
5572 MaskC->
countr_one() ==
A->getType()->getScalarSizeInBits())
5578 const APInt *AP1, *AP2;
5587 if (ShAmt < TypeBits && ShAmt != 0) {
5592 return new ICmpInst(NewPred,
Xor, ConstantInt::get(
A->getType(), CmpVal));
5602 if (ShAmt < TypeBits && ShAmt != 0) {
5606 I.getName() +
".mask");
5620 unsigned ASize = cast<IntegerType>(
A->getType())->getPrimitiveSizeInBits();
5622 if (ShAmt < ASize) {
5645 A->getType()->getScalarSizeInBits() ==
BitWidth * 2 &&
5646 (
I.getOperand(0)->hasOneUse() ||
I.getOperand(1)->hasOneUse())) {
5651 Add, ConstantInt::get(
A->getType(),
C.shl(1)));
5675 m_OneUse(m_Intrinsic<Intrinsic::fshr>(
5695 std::optional<bool> IsZero = std::nullopt;
5739 unsigned SrcBits =
X->getType()->getScalarSizeInBits();
5743 Constant *MaskC = ConstantInt::get(
X->getType(),
C->zext(SrcBits));
5751 Constant *MaskC = ConstantInt::get(
X->getType(), (*
C + 1).zext(SrcBits));
5756 if (
auto *II = dyn_cast<IntrinsicInst>(
X)) {
5757 if (II->getIntrinsicID() == Intrinsic::cttz ||
5758 II->getIntrinsicID() == Intrinsic::ctlz) {
5759 unsigned MaxRet = SrcBits;
5779 assert(isa<CastInst>(ICmp.
getOperand(0)) &&
"Expected cast for operand 0");
5780 auto *CastOp0 = cast<CastInst>(ICmp.
getOperand(0));
5785 bool IsSignedExt = CastOp0->getOpcode() == Instruction::SExt;
5786 bool IsSignedCmp = ICmp.
isSigned();
5791 bool IsZext0 = isa<ZExtInst>(ICmp.
getOperand(0));
5792 bool IsZext1 = isa<ZExtInst>(ICmp.
getOperand(1));
5794 if (IsZext0 != IsZext1) {
5799 if (ICmp.
isEquality() &&
X->getType()->isIntOrIntVectorTy(1) &&
5800 Y->getType()->isIntOrIntVectorTy(1))
5807 auto *NonNegInst0 = dyn_cast<PossiblyNonNegInst>(ICmp.
getOperand(0));
5808 auto *NonNegInst1 = dyn_cast<PossiblyNonNegInst>(ICmp.
getOperand(1));
5810 bool IsNonNeg0 = NonNegInst0 && NonNegInst0->hasNonNeg();
5811 bool IsNonNeg1 = NonNegInst1 && NonNegInst1->hasNonNeg();
5813 if ((IsZext0 && IsNonNeg0) || (IsZext1 && IsNonNeg1))
5820 Type *XTy =
X->getType(), *YTy =
Y->getType();
5827 IsSignedExt ? Instruction::SExt : Instruction::ZExt;
5843 if (IsSignedCmp && IsSignedExt)
5856 Type *SrcTy = CastOp0->getSrcTy();
5864 if (IsSignedExt && IsSignedCmp)
5876 if (IsSignedCmp || !IsSignedExt || !isa<ConstantInt>(
C))
5895 Value *SimplifiedOp0 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(0));
5896 Value *SimplifiedOp1 = simplifyIntToPtrRoundTripCast(ICmp.
getOperand(1));
5897 if (SimplifiedOp0 || SimplifiedOp1)
5899 SimplifiedOp0 ? SimplifiedOp0 : ICmp.
getOperand(0),
5900 SimplifiedOp1 ? SimplifiedOp1 : ICmp.
getOperand(1));
5902 auto *CastOp0 = dyn_cast<CastInst>(ICmp.
getOperand(0));
5908 Value *Op0Src = CastOp0->getOperand(0);
5909 Type *SrcTy = CastOp0->getSrcTy();
5910 Type *DestTy = CastOp0->getDestTy();
5914 auto CompatibleSizes = [&](
Type *SrcTy,
Type *DestTy) {
5915 if (isa<VectorType>(SrcTy)) {
5916 SrcTy = cast<VectorType>(SrcTy)->getElementType();
5917 DestTy = cast<VectorType>(DestTy)->getElementType();
5921 if (CastOp0->getOpcode() == Instruction::PtrToInt &&
5922 CompatibleSizes(SrcTy, DestTy)) {
5923 Value *NewOp1 =
nullptr;
5924 if (
auto *PtrToIntOp1 = dyn_cast<PtrToIntOperator>(ICmp.
getOperand(1))) {
5925 Value *PtrSrc = PtrToIntOp1->getOperand(0);
5927 NewOp1 = PtrToIntOp1->getOperand(0);
5928 }
else if (
auto *RHSC = dyn_cast<Constant>(ICmp.
getOperand(1))) {
5946 case Instruction::Add:
5947 case Instruction::Sub:
5949 case Instruction::Mul:
5962 case Instruction::Add:
5967 case Instruction::Sub:
5972 case Instruction::Mul:
5981 bool IsSigned,
Value *LHS,
5985 if (OrigI.
isCommutative() && isa<Constant>(LHS) && !isa<Constant>(RHS))
5995 if (
auto *LHSTy = dyn_cast<VectorType>(
LHS->
getType()))
6010 Result->takeName(&OrigI);
6015 Result->takeName(&OrigI);
6017 if (
auto *Inst = dyn_cast<Instruction>(Result)) {
6019 Inst->setHasNoSignedWrap();
6021 Inst->setHasNoUnsignedWrap();
6044 const APInt *OtherVal,
6048 if (!isa<IntegerType>(MulVal->
getType()))
6051 auto *MulInstr = dyn_cast<Instruction>(MulVal);
6054 assert(MulInstr->getOpcode() == Instruction::Mul);
6056 auto *
LHS = cast<ZExtInst>(MulInstr->getOperand(0)),
6057 *
RHS = cast<ZExtInst>(MulInstr->getOperand(1));
6058 assert(
LHS->getOpcode() == Instruction::ZExt);
6059 assert(
RHS->getOpcode() == Instruction::ZExt);
6063 Type *TyA =
A->getType(), *TyB =
B->getType();
6065 WidthB = TyB->getPrimitiveSizeInBits();
6068 if (WidthB > WidthA) {
6083 if (
TruncInst *TI = dyn_cast<TruncInst>(U)) {
6086 if (TruncWidth > MulWidth)
6090 if (BO->getOpcode() != Instruction::And)
6092 if (
ConstantInt *CI = dyn_cast<ConstantInt>(BO->getOperand(1))) {
6093 const APInt &CVal = CI->getValue();
6109 switch (
I.getPredicate()) {
6116 if (MaxVal.
eq(*OtherVal))
6126 if (MaxVal.
eq(*OtherVal))
6140 if (WidthA < MulWidth)
6142 if (WidthB < MulWidth)
6145 I.getModule(), Intrinsic::umul_with_overflow, MulType);
6157 if (
TruncInst *TI = dyn_cast<TruncInst>(U)) {
6158 if (TI->getType()->getPrimitiveSizeInBits() == MulWidth)
6163 assert(BO->getOpcode() == Instruction::And);
6165 ConstantInt *CI = cast<ConstantInt>(BO->getOperand(1));
6201 switch (
I.getPredicate()) {
6232 assert(DI && UI &&
"Instruction not defined\n");
6243 auto *Usr = cast<Instruction>(U);
6244 if (Usr != UI && !
DT.
dominates(DB, Usr->getParent()))
6255 auto *BI = dyn_cast_or_null<BranchInst>(BB->
getTerminator());
6256 if (!BI || BI->getNumSuccessors() != 2)
6258 auto *IC = dyn_cast<ICmpInst>(BI->getCondition());
6259 if (!IC || (IC->getOperand(0) != SI && IC->getOperand(1) != SI))
6306 const unsigned SIOpd) {
6307 assert((SIOpd == 1 || SIOpd == 2) &&
"Invalid select operand!");
6309 BasicBlock *Succ = SI->getParent()->getTerminator()->getSuccessor(1);
6323 SI->replaceUsesOutsideBlock(SI->getOperand(SIOpd), SI->getParent());
6333 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6382 if (!isa<Constant>(Op0) && Op0Min == Op0Max)
6384 if (!isa<Constant>(Op1) && Op1Min == Op1Max)
6392 if (!Cmp.hasOneUse())
6401 if (!isMinMaxCmp(
I)) {
6406 if (Op1Min == Op0Max)
6411 if (*CmpC == Op0Min + 1)
6413 ConstantInt::get(Op1->getType(), *CmpC - 1));
6423 if (Op1Max == Op0Min)
6428 if (*CmpC == Op0Max - 1)
6430 ConstantInt::get(Op1->getType(), *CmpC + 1));
6440 if (Op1Min == Op0Max)
6444 if (*CmpC == Op0Min + 1)
6446 ConstantInt::get(Op1->getType(), *CmpC - 1));
6451 if (Op1Max == Op0Min)
6455 if (*CmpC == Op0Max - 1)
6457 ConstantInt::get(Op1->getType(), *CmpC + 1));
6471 if (Op0Max.
ult(Op1Min) || Op0Min.ugt(Op1Max))
6478 APInt Op0KnownZeroInverted = ~Op0Known.Zero;
6484 *LHSC != Op0KnownZeroInverted)
6490 Type *XTy =
X->getType();
6492 APInt C2 = Op0KnownZeroInverted;
6493 APInt C2Pow2 = (C2 & ~(*C1 - 1)) + *C1;
6499 auto *CmpC = ConstantInt::get(XTy, Log2C2 - Log2C1);
6509 (Op0Known & Op1Known) == Op0Known)
6515 if (Op0Max.
ult(Op1Min))
6517 if (Op0Min.uge(Op1Max))
6522 if (Op0Min.ugt(Op1Max))
6524 if (Op0Max.
ule(Op1Min))
6529 if (Op0Max.
slt(Op1Min))
6531 if (Op0Min.sge(Op1Max))
6536 if (Op0Min.sgt(Op1Max))
6538 if (Op0Max.
sle(Op1Min))
6543 assert(!isa<ConstantInt>(Op1) &&
"ICMP_SGE with ConstantInt not folded!");
6544 if (Op0Min.sge(Op1Max))
6546 if (Op0Max.
slt(Op1Min))
6548 if (Op1Min == Op0Max)
6552 assert(!isa<ConstantInt>(Op1) &&
"ICMP_SLE with ConstantInt not folded!");
6553 if (Op0Max.
sle(Op1Min))
6555 if (Op0Min.sgt(Op1Max))
6557 if (Op1Max == Op0Min)
6561 assert(!isa<ConstantInt>(Op1) &&
"ICMP_UGE with ConstantInt not folded!");
6562 if (Op0Min.uge(Op1Max))
6564 if (Op0Max.
ult(Op1Min))
6566 if (Op1Min == Op0Max)
6570 assert(!isa<ConstantInt>(Op1) &&
"ICMP_ULE with ConstantInt not folded!");
6571 if (Op0Max.
ule(Op1Min))
6573 if (Op0Min.ugt(Op1Max))
6575 if (Op1Max == Op0Min)
6585 return new ICmpInst(
I.getUnsignedPredicate(), Op0, Op1);
6617 bool IsSExt = ExtI->
getOpcode() == Instruction::SExt;
6619 auto CreateRangeCheck = [&] {
6634 }
else if (!IsSExt || HasOneUse) {
6639 return CreateRangeCheck();
6641 }
else if (IsSExt ?
C->isAllOnes() :
C->isOne()) {
6649 }
else if (!IsSExt || HasOneUse) {
6654 return CreateRangeCheck();
6668 Instruction::ICmp, Pred1,
X,
6678std::optional<std::pair<CmpInst::Predicate, Constant *>>
6682 "Only for relational integer predicates.");
6688 bool WillIncrement =
6693 auto ConstantIsOk = [WillIncrement, IsSigned](
ConstantInt *
C) {
6694 return WillIncrement ? !
C->isMaxValue(IsSigned) : !
C->isMinValue(IsSigned);
6697 Constant *SafeReplacementConstant =
nullptr;
6698 if (
auto *CI = dyn_cast<ConstantInt>(
C)) {
6700 if (!ConstantIsOk(CI))
6701 return std::nullopt;
6702 }
else if (
auto *FVTy = dyn_cast<FixedVectorType>(
Type)) {
6703 unsigned NumElts = FVTy->getNumElements();
6704 for (
unsigned i = 0; i != NumElts; ++i) {
6705 Constant *Elt =
C->getAggregateElement(i);
6707 return std::nullopt;
6709 if (isa<UndefValue>(Elt))
6714 auto *CI = dyn_cast<ConstantInt>(Elt);
6715 if (!CI || !ConstantIsOk(CI))
6716 return std::nullopt;
6718 if (!SafeReplacementConstant)
6719 SafeReplacementConstant = CI;
6721 }
else if (isa<VectorType>(
C->getType())) {
6723 Value *SplatC =
C->getSplatValue();
6724 auto *CI = dyn_cast_or_null<ConstantInt>(SplatC);
6726 if (!CI || !ConstantIsOk(CI))
6727 return std::nullopt;
6730 return std::nullopt;
6737 if (
C->containsUndefOrPoisonElement()) {
6738 assert(SafeReplacementConstant &&
"Replacement constant not set");
6745 Constant *OneOrNegOne = ConstantInt::get(
Type, WillIncrement ? 1 : -1,
true);
6748 return std::make_pair(NewPred, NewC);
6760 Value *Op0 =
I.getOperand(0);
6761 Value *Op1 =
I.getOperand(1);
6762 auto *Op1C = dyn_cast<Constant>(Op1);
6766 auto FlippedStrictness =
6768 if (!FlippedStrictness)
6771 return new ICmpInst(FlippedStrictness->first, Op0, FlippedStrictness->second);
6789 I.setName(
I.getName() +
".not");
6800 Value *
A =
I.getOperand(0), *
B =
I.getOperand(1);
6801 assert(
A->getType()->isIntOrIntVectorTy(1) &&
"Bools only");
6807 switch (
I.getPredicate()) {
6816 switch (
I.getPredicate()) {
6826 switch (
I.getPredicate()) {
6835 return BinaryOperator::CreateXor(
A,
B);
6843 return BinaryOperator::CreateAnd(Builder.
CreateNot(
A),
B);
6851 return BinaryOperator::CreateAnd(Builder.
CreateNot(
B),
A);
6859 return BinaryOperator::CreateOr(Builder.
CreateNot(
A),
B);
6867 return BinaryOperator::CreateOr(Builder.
CreateNot(
B),
A);
6923 Value *
LHS = Cmp.getOperand(0), *
RHS = Cmp.getOperand(1);
6928 if (
auto *
I = dyn_cast<Instruction>(V))
6929 I->copyIRFlags(&Cmp);
6930 Module *M = Cmp.getModule();
6932 M, Intrinsic::experimental_vector_reverse, V->getType());
6940 return createCmpReverse(Pred, V1, V2);
6944 return createCmpReverse(Pred, V1,
RHS);
6948 return createCmpReverse(Pred,
LHS, V2);
6973 Constant *ScalarC =
C->getSplatValue(
true);
6992 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
6996 auto UAddOvResultPat = m_ExtractValue<0>(
6998 if (
match(Op0, UAddOvResultPat) &&
7007 UAddOv = cast<ExtractValueInst>(Op0)->getAggregateOperand();
7008 else if (
match(Op1, UAddOvResultPat) &&
7011 UAddOv = cast<ExtractValueInst>(Op1)->getAggregateOperand();
7019 if (!
I.getOperand(0)->getType()->isPointerTy() ||
7021 I.getParent()->getParent(),
7022 I.getOperand(0)->getType()->getPointerAddressSpace())) {
7028 Op->isLaunderOrStripInvariantGroup()) {
7030 Op->getOperand(0),
I.getOperand(1));
7042 if (
I.getType()->isVectorTy())
7064 auto *LHSTy = dyn_cast<FixedVectorType>(
LHS->
getType());
7065 if (!LHSTy || !LHSTy->getElementType()->isIntegerTy())
7068 LHSTy->getNumElements() * LHSTy->getElementType()->getIntegerBitWidth();
7070 if (!
DL.isLegalInteger(NumBits))
7074 auto *ScalarTy = Builder.
getIntNTy(NumBits);
7089 if (
auto *
GEP = dyn_cast<GEPOperator>(Op0))
7093 if (
auto *SI = dyn_cast<SelectInst>(Op0))
7097 if (
auto *
MinMax = dyn_cast<MinMaxIntrinsic>(Op0))
7128 bool IsIntMinPosion =
C->isAllOnesValue();
7140 CxtI, IsIntMinPosion
7143 X, ConstantInt::get(
X->getType(),
SMin + 1)));
7149 CxtI, IsIntMinPosion
7152 X, ConstantInt::get(
X->getType(),
SMin)));
7166 const APInt *Divisor;
7202 bool Changed =
false;
7204 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7211 if (Op0Cplxity < Op1Cplxity) {
7226 if (
Value *V = dyn_castNegVal(SelectTrue)) {
7227 if (V == SelectFalse)
7230 else if (
Value *V = dyn_castNegVal(SelectFalse)) {
7231 if (V == SelectTrue)
7272 if (
SelectInst *SI = dyn_cast<SelectInst>(
I.user_back())) {
7330 if (
I.isCommutative()) {
7331 if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
7355 (Op0->
hasOneUse() || Op1->hasOneUse())) {
7371 assert(Op1->getType()->isPointerTy() &&
"Comparing pointer with non-pointer?");
7400 bool ConsumesOp0, ConsumesOp1;
7403 (ConsumesOp0 || ConsumesOp1)) {
7406 assert(InvOp0 && InvOp1 &&
7407 "Mismatch between isFreeToInvert and getFreelyInverted");
7408 return new ICmpInst(
I.getSwappedPredicate(), InvOp0, InvOp1);
7415 isa<IntegerType>(
X->getType())) {
7420 if (AddI->
getOpcode() == Instruction::Add &&
7421 OptimizeOverflowCheck(Instruction::Add,
false,
X,
Y, *AddI,
7422 Result, Overflow)) {
7440 if ((
I.isUnsigned() ||
I.isEquality()) &&
7443 Y->getType()->getScalarSizeInBits() == 1 &&
7444 (Op0->
hasOneUse() || Op1->hasOneUse())) {
7451 unsigned ShiftOpc = ShiftI->
getOpcode();
7452 if ((ExtOpc == Instruction::ZExt && ShiftOpc == Instruction::LShr) ||
7453 (ExtOpc == Instruction::SExt && ShiftOpc == Instruction::AShr)) {
7482 if (
auto *EVI = dyn_cast<ExtractValueInst>(Op0))
7483 if (
auto *ACXI = dyn_cast<AtomicCmpXchgInst>(EVI->getAggregateOperand()))
7484 if (EVI->getIndices()[0] == 0 && ACXI->getCompareOperand() == Op1 &&
7491 if (
I.getType()->isVectorTy())
7501 return Changed ? &
I :
nullptr;
7515 if (MantissaWidth == -1)
return nullptr;
7519 bool LHSUnsigned = isa<UIToFPInst>(LHSI);
7521 if (
I.isEquality()) {
7523 bool IsExact =
false;
7524 APSInt RHSCvt(IntWidth, LHSUnsigned);
7533 if (*
RHS != RHSRoundInt) {
7553 if ((
int)IntWidth > MantissaWidth) {
7555 int Exp = ilogb(*
RHS);
7558 if (MaxExponent < (
int)IntWidth - !LHSUnsigned)
7564 if (MantissaWidth <= Exp && Exp <= (
int)IntWidth - !LHSUnsigned)
7573 assert(!
RHS->isNaN() &&
"NaN comparison not already folded!");
7576 switch (
I.getPredicate()) {
7666 APSInt RHSInt(IntWidth, LHSUnsigned);
7669 if (!
RHS->isZero()) {
7683 if (
RHS->isNegative())
7689 if (
RHS->isNegative())
7695 if (
RHS->isNegative())
7702 if (!
RHS->isNegative())
7708 if (
RHS->isNegative())
7714 if (
RHS->isNegative())
7720 if (
RHS->isNegative())
7727 if (!
RHS->isNegative())
7781 if (
C->isNegative())
7782 Pred =
I.getSwappedPredicate();
7797 if (!
C->isPosZero()) {
7798 if (!
C->isSmallestNormalized())
7811 switch (
I.getPredicate()) {
7837 switch (
I.getPredicate()) {
7862 assert(!
I.hasNoNaNs() &&
"fcmp should have simplified");
7867 assert(!
I.hasNoNaNs() &&
"fcmp should have simplified");
7881 return replacePredAndOp0(&
I,
I.getPredicate(),
X);
7890 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7895 Pred =
I.getSwappedPredicate();
7904 return new FCmpInst(Pred, Op0, Zero,
"", &
I);
7908 bool Changed =
false;
7919 Value *Op0 =
I.getOperand(0), *Op1 =
I.getOperand(1);
7926 assert(OpType == Op1->getType() &&
"fcmp with different-typed operands?");
7950 if (
I.isCommutative()) {
7951 if (
auto Pair = matchSymmetricPair(
I.getOperand(0),
I.getOperand(1))) {
7973 return new FCmpInst(
I.getSwappedPredicate(),
X,
Y,
"", &
I);
7986 if (
SelectInst *SI = dyn_cast<SelectInst>(
I.user_back())) {
8055 Type *IntTy =
X->getType();
8067 case Instruction::PHI:
8071 case Instruction::SIToFP:
8072 case Instruction::UIToFP:
8076 case Instruction::FDiv:
8080 case Instruction::Load:
8081 if (
auto *
GEP = dyn_cast<GetElementPtrInst>(LHSI->
getOperand(0)))
8082 if (
auto *GV = dyn_cast<GlobalVariable>(
GEP->getOperand(0)))
8084 cast<LoadInst>(LHSI),
GEP, GV,
I))
8098 return new FCmpInst(
I.getSwappedPredicate(),
X, NegC,
"", &
I);
8117 X->getType()->getScalarType()->getFltSemantics();
8153 Constant *NewC = ConstantFP::get(
X->getType(), TruncC);
8167 if (
auto *VecTy = dyn_cast<VectorType>(OpType))
8179 Value *CanonLHS =
nullptr, *CanonRHS =
nullptr;
8180 match(Op0, m_Intrinsic<Intrinsic::canonicalize>(
m_Value(CanonLHS)));
8181 match(Op1, m_Intrinsic<Intrinsic::canonicalize>(
m_Value(CanonRHS)));
8184 if (CanonLHS == Op1)
8185 return new FCmpInst(Pred, Op1, Op1,
"", &
I);
8188 if (CanonRHS == Op0)
8189 return new FCmpInst(Pred, Op0, Op0,
"", &
I);
8192 if (CanonLHS && CanonRHS)
8193 return new FCmpInst(Pred, CanonLHS, CanonRHS,
"", &
I);
8196 if (
I.getType()->isVectorTy())
8200 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")
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.
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getNonStrictPredicate() const
For example, SGT -> SGE, SLT -> SLE, ULT -> ULE, UGT -> UGE.
static CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a compare instruction, given the opcode, the predicate and the two operands.
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 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 * 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 * CreateNeg(Value *V, const Twine &Name="", bool HasNSW=false)
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 * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="", bool IsNUW=false, bool IsNSW=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 * 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 * foldICmpInstWithConstantAllowPoison(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 * 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)
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.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
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)
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
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.
specific_intval< true > m_SpecificIntAllowPoison(const APInt &V)
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::FAdd > m_FAdd(const LHS &L, const RHS &R)
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.
apint_match m_APIntAllowPoison(const APInt *&Res)
Match APInt while allowing poison in splat vector constants.
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)
BinaryOp_match< LHS, RHS, Instruction::SDiv > m_SDiv(const LHS &L, const RHS &R)
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 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.
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ 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.