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(
76 if (
LHS.isNonNegative() &&
RHS.isNonNegative())
80 else if (
LHS.isNegative() &&
RHS.isNegative())
91 "Illegal sext-in-register");
96 unsigned ExtBits =
BitWidth - SrcBitWidth;
98 Result.One =
One << ExtBits;
99 Result.Zero =
Zero << ExtBits;
100 Result.One.ashrInPlace(ExtBits);
101 Result.Zero.ashrInPlace(ExtBits);
112 APInt MaskedVal(Val);
122 if (
LHS.getMinValue().uge(
RHS.getMaxValue()))
124 if (
RHS.getMinValue().uge(
LHS.getMaxValue()))
148 One.
setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
161 One.
setBitVal(SignBitPosition, Val.One[SignBitPosition]);
173 unsigned Shift =
RHS.getConstant().getZExtValue();
175 Known.
Zero <<= Shift;
183 unsigned MinTrailingZeros =
LHS.countMinTrailingZeros();
186 APInt MinShiftAmount =
RHS.getMinValue();
189 MinTrailingZeros = std::min(MinTrailingZeros,
BitWidth);
194 APInt MaxShiftAmount =
RHS.getMaxValue();
196 uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
198 assert(MinShiftAmount.
ult(MaxShiftAmount) &&
"Illegal shift range");
203 ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
205 if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
206 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
209 SpecificShift.
Zero =
LHS.Zero << ShiftAmt;
210 SpecificShift.
One =
LHS.One << ShiftAmt;
226 unsigned Shift =
RHS.getConstant().getZExtValue();
236 unsigned MinLeadingZeros =
LHS.countMinLeadingZeros();
239 APInt MinShiftAmount =
RHS.getMinValue();
242 MinLeadingZeros = std::min(MinLeadingZeros,
BitWidth);
247 APInt MaxShiftAmount =
RHS.getMaxValue();
249 uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
251 assert(MinShiftAmount.
ult(MaxShiftAmount) &&
"Illegal shift range");
256 ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
258 if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
259 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
279 unsigned Shift =
RHS.getConstant().getZExtValue();
287 unsigned MinLeadingZeros =
LHS.countMinLeadingZeros();
288 unsigned MinLeadingOnes =
LHS.countMinLeadingOnes();
291 APInt MinShiftAmount =
RHS.getMinValue();
293 if (MinLeadingZeros) {
295 MinLeadingZeros = std::min(MinLeadingZeros,
BitWidth);
297 if (MinLeadingOnes) {
299 MinLeadingOnes = std::min(MinLeadingOnes,
BitWidth);
305 APInt MaxShiftAmount =
RHS.getMaxValue();
307 uint64_t ShiftAmtZeroMask = (~RHS.Zero).getZExtValue();
309 assert(MinShiftAmount.
ult(MaxShiftAmount) &&
"Illegal shift range");
314 ShiftAmt <= MaxShiftAmt; ++ShiftAmt) {
316 if ((ShiftAmtZeroMask & ShiftAmt) != ShiftAmt ||
317 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
334 if (
LHS.isConstant() &&
RHS.isConstant())
335 return std::optional<bool>(
LHS.getConstant() ==
RHS.getConstant());
336 if (
LHS.One.intersects(
RHS.Zero) ||
RHS.One.intersects(
LHS.Zero))
337 return std::optional<bool>(
false);
342 if (std::optional<bool> KnownEQ =
eq(
LHS,
RHS))
343 return std::optional<bool>(!*KnownEQ);
349 if (
LHS.getMaxValue().ule(
RHS.getMinValue()))
350 return std::optional<bool>(
false);
352 if (
LHS.getMinValue().ugt(
RHS.getMaxValue()))
353 return std::optional<bool>(
true);
358 if (std::optional<bool> IsUGT =
ugt(
RHS,
LHS))
359 return std::optional<bool>(!*IsUGT);
373 if (
LHS.getSignedMaxValue().sle(
RHS.getSignedMinValue()))
374 return std::optional<bool>(
false);
376 if (
LHS.getSignedMinValue().sgt(
RHS.getSignedMaxValue()))
377 return std::optional<bool>(
true);
382 if (std::optional<bool> KnownSGT =
sgt(
RHS,
LHS))
383 return std::optional<bool>(!*KnownSGT);
416 bool NoUndefSelfMultiply) {
419 !
RHS.hasConflict() &&
"Operand mismatch");
421 "Self multiplication knownbits mismatch");
434 APInt UMaxResult = UMaxLHS.
umul_ov(UMaxRHS, HasOverflow);
435 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.
countl_zero();
486 unsigned TrailZero0 =
LHS.countMinTrailingZeros();
487 unsigned TrailZero1 =
RHS.countMinTrailingZeros();
488 unsigned TrailZ = TrailZero0 + TrailZero1;
491 unsigned SmallestOperand =
492 std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);
493 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ,
BitWidth);
500 Res.
Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
504 if (NoUndefSelfMultiply &&
BitWidth > 1) {
506 "Self-multiplication failed Quadratic Reciprocity!");
516 !
RHS.hasConflict() &&
"Operand mismatch");
525 !
RHS.hasConflict() &&
"Operand mismatch");
539 unsigned LeadZ =
LHS.countMinLeadingZeros();
540 unsigned RHSMaxLeadingZeros =
RHS.countMaxLeadingZeros();
554 if (
RHS.isConstant() &&
RHS.getConstant().isPowerOf2()) {
556 APInt LowBits =
RHS.getConstant() - 1;
557 Known.
Zero =
LHS.Zero | ~LowBits;
558 Known.
One =
LHS.One & LowBits;
565 std::max(
LHS.countMinLeadingZeros(),
RHS.countMinLeadingZeros());
575 if (
RHS.isConstant() &&
RHS.getConstant().isPowerOf2()) {
577 APInt LowBits =
RHS.getConstant() - 1;
578 Known.
Zero =
LHS.Zero & LowBits;
579 Known.
One =
LHS.One & LowBits;
584 Known.
Zero |= ~LowBits;
589 Known.
One |= ~LowBits;
648 OS <<
"{Zero=" <<
Zero <<
", One=" <<
One <<
"}";
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
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.
uint64_t getZExtValue() const
Get zero extended value.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
void setSignBit()
Set the sign bit to 1.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
unsigned countl_zero() const
The APInt version of std::countl_zero.
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
void setAllBits()
Set every bit to 1.
bool getBoolValue() const
Convert APInt to a boolean value.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
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.
This class implements an extremely fast bulk output stream that can only output to a stream.
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.
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.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
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 commonBits(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits common to LHS and RHS.
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
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 KnownBits shl(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for shl(LHS, RHS).
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.
static std::optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGE result.
KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for lshr(LHS, 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).
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for ashr(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
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 std::optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLT result.
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 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 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.
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 udiv(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for udiv(LHS, RHS).
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).