Go to the documentation of this file.
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;
38 APInt Known =
std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
40 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
41 "known bits of sum differ");
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();
183 unsigned MinTrailingZeros =
LHS.countMinTrailingZeros();
186 APInt MinShiftAmount =
RHS.getMinValue();
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();
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) {
297 if (MinLeadingOnes) {
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())
336 if (
LHS.One.intersects(
RHS.Zero) ||
RHS.One.intersects(
LHS.Zero))
349 if (
LHS.getMaxValue().ule(
RHS.getMinValue()))
352 if (
LHS.getMinValue().ugt(
RHS.getMaxValue()))
373 if (
LHS.getSignedMaxValue().sle(
RHS.getSignedMinValue()))
376 if (
LHS.getSignedMinValue().sgt(
RHS.getSignedMaxValue()))
416 bool NoUndefSelfMultiply) {
419 !
RHS.hasConflict() &&
"Operand mismatch");
421 "Self multiplication knownbits mismatch");
434 APInt UMaxResult = UMaxLHS.
umul_ov(UMaxRHS, HasOverflow);
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);
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;
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;
627 OS <<
"{Zero=" <<
Zero <<
", One=" <<
One <<
"}";
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for shl(LHS, RHS).
void setAllBits()
Set every bit to 1.
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for lshr(LHS, RHS).
void print(raw_ostream &OS) const
This is an optimization pass for GlobalISel generic memory operations.
bool isUnknown() const
Returns true if we don't know any bits.
KnownBits makeGE(const APInt &Val) const
Return KnownBits based on this, but updated given that the underlying value is known to be greater th...
static Optional< bool > ult(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULT result.
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
unsigned countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
void makeNegative()
Make this value negative.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from zero-extended multiply-hi.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
KnownBits & operator&=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
KnownBits abs(bool IntMinIsPoison=false) const
Compute known bits for the absolute value.
uint64_t getZExtValue() const
Get zero extended value.
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.
This class implements an extremely fast bulk output stream that can only output to a stream.
bool isNegative() const
Returns true if this value is known to be negative.
void setSignBit()
Set the sign bit to 1.
static Optional< bool > sle(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLE result.
static Optional< bool > eq(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_EQ result.
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
static 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 ORing with RHS.
static Optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLT result.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
unsigned countTrailingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the least significant bit to the first zero bit.
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
static Optional< bool > ule(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULE result.
bool getBoolValue() const
Convert APInt to a boolean value.
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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 KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for ashr(LHS, RHS).
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Class for arbitrary precision integers.
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from sign-extended multiply-hi.
static Optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_NE result.
unsigned countLeadingZeros() const
The APInt version of the countLeadingZeros functions in MathExtras.h.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for udiv(LHS, RHS).
constexpr unsigned BitWidth
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits common to LHS and RHS.
Align max(MaybeAlign Lhs, Align Rhs)
static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
static Optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGE result.
unsigned getBitWidth() const
Get the bit width of this value.
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
static Optional< bool > ugt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGT result.
void makeNonNegative()
Make this value non-negative.
static Optional< bool > sgt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGT result.