23 bool CarryZero,
bool CarryOne) {
24 assert(!(CarryZero && CarryOne) &&
25 "Carry can't be zero and one at the same time");
27 APInt PossibleSumZero =
LHS.getMaxValue() +
RHS.getMaxValue() + !CarryZero;
28 APInt PossibleSumOne =
LHS.getMinValue() +
RHS.getMinValue() + CarryOne;
31 APInt CarryKnownZero = ~(PossibleSumZero ^
LHS.Zero ^
RHS.Zero);
32 APInt CarryKnownOne = PossibleSumOne ^
LHS.One ^
RHS.One;
37 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
38 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
40 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
41 "known bits of sum differ");
46 KnownOut.
One = std::move(PossibleSumOne) & Known;
53 return ::computeForAddCarry(
64 if (
LHS.isUnknown() &&
RHS.isUnknown())
67 if (!
LHS.isUnknown() && !
RHS.isUnknown()) {
85 APInt MinVal =
LHS.getMinValue().uadd_sat(
RHS.getMinValue());
97 APInt MaxVal =
LHS.getMaxValue().usub_sat(
RHS.getMinValue());
115 MinVal =
LHS.getSignedMinValue().sadd_sat(
RHS.getSignedMinValue());
116 MaxVal =
LHS.getSignedMaxValue().sadd_sat(
RHS.getSignedMaxValue());
119 MinVal =
LHS.getSignedMinValue().ssub_sat(
RHS.getSignedMaxValue());
120 MaxVal =
LHS.getSignedMaxValue().ssub_sat(
RHS.getSignedMinValue());
150 return ::computeForAddCarry(
LHS,
RHS,
158 "Illegal sext-in-register");
163 unsigned ExtBits =
BitWidth - SrcBitWidth;
165 Result.One =
One << ExtBits;
166 Result.Zero =
Zero << ExtBits;
167 Result.One.ashrInPlace(ExtBits);
168 Result.Zero.ashrInPlace(ExtBits);
179 APInt MaskedVal(Val);
189 if (
LHS.getMinValue().uge(
RHS.getMaxValue()))
191 if (
RHS.getMinValue().uge(
LHS.getMaxValue()))
199 return L.intersectWith(R);
215 One.
setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
228 One.
setBitVal(SignBitPosition, Val.One[SignBitPosition]);
239 true, UMaxValue, UMinValue);
258 false, SMaxValue, SMinValue);
280 bool NSW,
bool ShAmtNonZero) {
282 auto ShiftByConst = [&](
const KnownBits &
LHS,
unsigned ShiftAmt) {
284 bool ShiftedOutZero, ShiftedOutOne;
285 Known.
Zero =
LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);
287 Known.
One =
LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);
291 if (NUW && ShiftAmt != 0)
293 ShiftedOutZero =
true;
297 else if (ShiftedOutOne)
305 unsigned MinShiftAmount =
RHS.getMinValue().getLimitedValue(
BitWidth);
306 if (MinShiftAmount == 0 && ShAmtNonZero)
308 if (
LHS.isUnknown()) {
310 if (NUW && NSW && MinShiftAmount != 0)
319 MaxShiftAmount = std::min(MaxShiftAmount,
LHS.countMaxLeadingZeros() - 1);
321 MaxShiftAmount = std::min(MaxShiftAmount,
LHS.countMaxLeadingZeros());
323 MaxShiftAmount = std::min(
325 std::max(
LHS.countMaxLeadingZeros(),
LHS.countMaxLeadingOnes()) - 1);
328 if (MinShiftAmount == 0 && MaxShiftAmount ==
BitWidth - 1 &&
334 if (
LHS.isNonNegative())
336 if (
LHS.isNegative())
343 unsigned ShiftAmtZeroMask =
RHS.Zero.zextOrTrunc(32).getZExtValue();
344 unsigned ShiftAmtOneMask =
RHS.One.zextOrTrunc(32).getZExtValue();
347 for (
unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
350 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
351 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
365 bool ShAmtNonZero,
bool Exact) {
367 auto ShiftByConst = [&](
const KnownBits &
LHS,
unsigned ShiftAmt) {
378 unsigned MinShiftAmount =
RHS.getMinValue().getLimitedValue(
BitWidth);
379 if (MinShiftAmount == 0 && ShAmtNonZero)
381 if (
LHS.isUnknown()) {
392 unsigned FirstOne =
LHS.countMaxTrailingZeros();
393 if (FirstOne < MinShiftAmount) {
398 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
401 unsigned ShiftAmtZeroMask =
RHS.Zero.zextOrTrunc(32).getZExtValue();
402 unsigned ShiftAmtOneMask =
RHS.One.zextOrTrunc(32).getZExtValue();
405 for (
unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
408 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
409 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
423 bool ShAmtNonZero,
bool Exact) {
425 auto ShiftByConst = [&](
const KnownBits &
LHS,
unsigned ShiftAmt) {
434 unsigned MinShiftAmount =
RHS.getMinValue().getLimitedValue(
BitWidth);
435 if (MinShiftAmount == 0 && ShAmtNonZero)
437 if (
LHS.isUnknown()) {
452 unsigned FirstOne =
LHS.countMaxTrailingZeros();
453 if (FirstOne < MinShiftAmount) {
458 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
461 unsigned ShiftAmtZeroMask =
RHS.Zero.zextOrTrunc(32).getZExtValue();
462 unsigned ShiftAmtOneMask =
RHS.One.zextOrTrunc(32).getZExtValue();
465 for (
unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
468 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
469 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
483 if (
LHS.isConstant() &&
RHS.isConstant())
484 return std::optional<bool>(
LHS.getConstant() ==
RHS.getConstant());
485 if (
LHS.One.intersects(
RHS.Zero) ||
RHS.One.intersects(
LHS.Zero))
486 return std::optional<bool>(
false);
491 if (std::optional<bool> KnownEQ =
eq(
LHS,
RHS))
492 return std::optional<bool>(!*KnownEQ);
498 if (
LHS.getMaxValue().ule(
RHS.getMinValue()))
499 return std::optional<bool>(
false);
501 if (
LHS.getMinValue().ugt(
RHS.getMaxValue()))
502 return std::optional<bool>(
true);
507 if (std::optional<bool> IsUGT =
ugt(
RHS,
LHS))
508 return std::optional<bool>(!*IsUGT);
522 if (
LHS.getSignedMaxValue().sle(
RHS.getSignedMinValue()))
523 return std::optional<bool>(
false);
525 if (
LHS.getSignedMinValue().sgt(
RHS.getSignedMaxValue()))
526 return std::optional<bool>(
true);
531 if (std::optional<bool> KnownSGT =
sgt(
RHS,
LHS))
532 return std::optional<bool>(!*KnownSGT);
563 false, IntMinIsPoison,
false,
606 assert(!
LHS.hasConflict() && !
RHS.hasConflict() &&
"Bad inputs");
612 auto SignBitKnown = [&](
const KnownBits &K) {
615 std::optional<bool> Overflow;
620 if (SignBitKnown(
LHS) && SignBitKnown(
RHS) && SignBitKnown(Res)) {
623 Overflow = (
LHS.isNonNegative() ==
RHS.isNonNegative() &&
627 Overflow = (
LHS.isNonNegative() !=
RHS.isNonNegative() &&
634 (void)
LHS.getMaxValue().uadd_ov(
RHS.getMaxValue(), Of);
638 (void)
LHS.getMinValue().uadd_ov(
RHS.getMinValue(), Of);
645 (void)
LHS.getMinValue().usub_ov(
RHS.getMaxValue(), Of);
649 (void)
LHS.getMaxValue().usub_ov(
RHS.getMinValue(), Of);
657 if (
LHS.isNonNegative() &&
RHS.isNonNegative()) {
662 if (
LHS.isNegative() &&
RHS.isNegative()) {
668 if (
LHS.isNegative() &&
RHS.isNonNegative()) {
672 }
else if (
LHS.isNonNegative() &&
RHS.isNegative()) {
682 unsigned LeadingKnown;
685 std::max(
LHS.countMinLeadingOnes(),
RHS.countMinLeadingOnes());
688 std::max(
LHS.countMinLeadingZeros(),
RHS.countMinLeadingOnes());
715 "We somehow know overflow without knowing input sign");
766 bool NoUndefSelfMultiply) {
769 !
RHS.hasConflict() &&
"Operand mismatch");
771 "Self multiplication knownbits mismatch");
784 APInt UMaxResult = UMaxLHS.
umul_ov(UMaxRHS, HasOverflow);
785 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.
countl_zero();
836 unsigned TrailZero0 =
LHS.countMinTrailingZeros();
837 unsigned TrailZero1 =
RHS.countMinTrailingZeros();
838 unsigned TrailZ = TrailZero0 + TrailZero1;
841 unsigned SmallestOperand =
842 std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);
843 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ,
BitWidth);
850 Res.
Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
854 if (NoUndefSelfMultiply &&
BitWidth > 1) {
856 "Self-multiplication failed Quadratic Reciprocity!");
866 !
RHS.hasConflict() &&
"Operand mismatch");
875 !
RHS.hasConflict() &&
"Operand mismatch");
894 (int)
LHS.countMinTrailingZeros() - (int)
RHS.countMaxTrailingZeros();
896 (int)
LHS.countMaxTrailingZeros() - (int)
RHS.countMinTrailingZeros();
900 if (MinTZ == MaxTZ) {
904 }
else if (MaxTZ < 0) {
920 if (
LHS.isNonNegative() &&
RHS.isNonNegative())
924 assert(!
LHS.hasConflict() && !
RHS.hasConflict() &&
"Bad inputs");
927 if (
LHS.isZero() ||
RHS.isZero()) {
934 std::optional<APInt> Res;
935 if (
LHS.isNegative() &&
RHS.isNegative()) {
937 APInt Denom =
RHS.getSignedMaxValue();
938 APInt Num =
LHS.getSignedMinValue();
944 }
else if (
LHS.isNegative() &&
RHS.isNonNegative()) {
946 if (Exact || (-
LHS.getSignedMaxValue()).uge(
RHS.getSignedMaxValue())) {
947 APInt Denom =
RHS.getSignedMinValue();
948 APInt Num =
LHS.getSignedMinValue();
951 }
else if (
LHS.isStrictlyPositive() &&
RHS.isNegative()) {
953 if (Exact ||
LHS.getSignedMinValue().uge(-
RHS.getSignedMinValue())) {
954 APInt Denom =
RHS.getSignedMaxValue();
955 APInt Num =
LHS.getSignedMaxValue();
956 Res = Num.
sdiv(Denom);
961 if (Res->isNonNegative()) {
965 unsigned LeadO = Res->countLeadingOnes();
982 if (
LHS.isZero() ||
RHS.isZero()) {
1007 if (!
RHS.isZero() &&
RHS.Zero[0]) {
1009 unsigned RHSZeros =
RHS.countMinTrailingZeros();
1022 if (
RHS.isConstant() &&
RHS.getConstant().isPowerOf2()) {
1024 APInt HighBits = ~(
RHS.getConstant() - 1);
1025 Known.
Zero |= HighBits;
1032 std::max(
LHS.countMinLeadingZeros(),
RHS.countMinLeadingZeros());
1041 if (
RHS.isConstant() &&
RHS.getConstant().isPowerOf2()) {
1043 APInt LowBits =
RHS.getConstant() - 1;
1047 Known.
Zero |= ~LowBits;
1052 Known.
One |= ~LowBits;
1085 Zero = std::move(Z);
static KnownBits computeForSatAddSub(bool Add, bool Signed, const KnownBits &LHS, const KnownBits &RHS)
static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS, const KnownBits &RHS, bool Exact)
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt udiv(const APInt &RHS) const
Unsigned division operation.
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
unsigned popcount() const
Count the number of bits set.
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
void setSignBit()
Set the sign bit to 1.
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.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
void clearAllBits()
Set every bit to 0.
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
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.
unsigned countLeadingZeros() const
unsigned countl_one() const
Count the number of leading one bits.
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
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.
void setAllBits()
Set every bit to 1.
bool getBoolValue() const
Convert APInt to a boolean value.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
void clearSignBit()
Set the sign bit to 0.
This class implements an extremely fast bulk output stream that can only output to a stream.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
int countl_one(T Value)
Count the number of ones from the most significant bit to the first zero bit.
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
static std::optional< bool > eq(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_EQ result.
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from zero-extended multiply-hi.
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
bool isNonNegative() const
Returns true if this value is known to be non-negative.
KnownBits blsi() const
Compute known bits for X & -X, which has only the lowest bit set of X set.
void makeNonNegative()
Make this value non-negative.
static KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.usub.sat(LHS, RHS)
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)
static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
bool isUnknown() const
Returns true if we don't know any bits.
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
static std::optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_NE result.
KnownBits makeGE(const APInt &Val) const
Return KnownBits based on this, but updated given that the underlying value is known to be greater th...
KnownBits blsmsk() const
Compute known bits for X ^ (X - 1), which has all bits up to and including the lowest set bit of X se...
void makeNegative()
Make this value negative.
bool hasConflict() const
Returns true if there is conflicting information.
static std::optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGE result.
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
void setAllZero()
Make all bits known to be zero and discard any previous information.
KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
void print(raw_ostream &OS) const
unsigned getBitWidth() const
Get the bit width of this value.
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
KnownBits unionWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for either this or RHS or both.
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abdu(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
static KnownBits computeForSubBorrow(const KnownBits &LHS, KnownBits RHS, const KnownBits &Borrow)
Compute known bits results from subtracting RHS from LHS with 1-bit Borrow.
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
KnownBits & operator&=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from sign-extended multiply-hi.
static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
static std::optional< bool > ugt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGT result.
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
static std::optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLT result.
static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)
Compute known bits resulting from adding LHS and RHS.
static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for sdiv(LHS, RHS).
static std::optional< bool > ult(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULT result.
static std::optional< bool > ule(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULE result.
bool isNegative() const
Returns true if this value is known to be negative.
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry)
Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
static KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
KnownBits abs(bool IntMinIsPoison=false) const
Compute known bits for the absolute value.
static KnownBits abds(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abds(LHS, RHS).
static std::optional< bool > sle(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLE result.
static std::optional< bool > sgt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGT result.
unsigned countMinPopulation() const
Returns the number of bits known to be one.
static std::optional< bool > uge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGE result.
KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).