21#include "llvm/Config/llvm-config.h"
31#define DEBUG_TYPE "apint"
37 memset(result, 0, numWords *
sizeof(
uint64_t));
48inline static unsigned getDigit(
char cdigit, uint8_t radix) {
51 if (radix == 16 || radix == 36) {
84void APInt::initSlowCase(
const APInt& that) {
90 assert(bigVal.
data() &&
"Null pointer detected!");
106 initFromArray(bigVal);
111 initFromArray(
ArrayRef(bigVal, numWords));
116 fromString(numbits, Str, radix);
119void APInt::reallocate(
unsigned NewBitWidth) {
122 BitWidth = NewBitWidth;
131 BitWidth = NewBitWidth;
138void APInt::assignSlowCase(
const APInt &RHS) {
144 reallocate(
RHS.getBitWidth());
155 ID.AddInteger(BitWidth);
158 ID.AddInteger(U.VAL);
163 for (
unsigned i = 0; i < NumWords; ++i)
164 ID.AddInteger(U.pVal[i]);
173 return clearUnusedBits();
182 return clearUnusedBits();
189 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
194 return clearUnusedBits();
202 return clearUnusedBits();
209 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
214 return clearUnusedBits();
222 return clearUnusedBits();
226 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
228 return APInt(BitWidth, U.VAL *
RHS.U.VAL);
232 Result.clearUnusedBits();
236void APInt::andAssignSlowCase(
const APInt &RHS) {
242void APInt::orAssignSlowCase(
const APInt &RHS) {
248void APInt::xorAssignSlowCase(
const APInt &RHS) {
266 return clearUnusedBits();
269bool APInt::equalSlowCase(
const APInt &RHS)
const {
273int APInt::compare(
const APInt& RHS)
const {
274 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
276 return U.VAL <
RHS.U.VAL ? -1 : U.VAL >
RHS.U.VAL;
281int APInt::compareSigned(
const APInt& RHS)
const {
282 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
286 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
290 bool rhsNeg =
RHS.isNegative();
293 if (lhsNeg != rhsNeg)
294 return lhsNeg ? -1 : 1;
301void APInt::setBitsSlowCase(
unsigned loBit,
unsigned hiBit) {
302 unsigned loWord = whichWord(loBit);
303 unsigned hiWord = whichWord(hiBit);
309 unsigned hiShiftAmt = whichBit(hiBit);
310 if (hiShiftAmt != 0) {
315 if (hiWord == loWord)
318 U.pVal[hiWord] |= hiMask;
321 U.pVal[loWord] |= loMask;
324 for (
unsigned word = loWord + 1; word < hiWord; ++word)
330 for (
unsigned i = 0; i < parts; i++)
335void APInt::flipAllBitsSlowCase() {
344APInt APInt::concatSlowCase(
const APInt &NewLSB)
const {
355 assert(bitPosition < BitWidth &&
"Out of the bit-width range!");
356 setBitVal(bitPosition, !(*
this)[bitPosition]);
361 assert((subBitWidth + bitPosition) <= BitWidth &&
"Illegal bit insertion");
364 if (subBitWidth == 0)
368 if (subBitWidth == BitWidth) {
376 U.VAL &= ~(mask << bitPosition);
377 U.VAL |= (subBits.U.
VAL << bitPosition);
381 unsigned loBit = whichBit(bitPosition);
382 unsigned loWord = whichWord(bitPosition);
383 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
386 if (loWord == hi1Word) {
388 U.pVal[loWord] &= ~(mask << loBit);
389 U.pVal[loWord] |= (subBits.U.
VAL << loBit);
402 if (remainingBits != 0) {
404 U.pVal[hi1Word] &= ~mask;
405 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
413 for (
unsigned i = 0; i != subBitWidth; ++i)
418 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
421 U.VAL &= ~(maskBits << bitPosition);
422 U.VAL |= subBits << bitPosition;
426 unsigned loBit = whichBit(bitPosition);
427 unsigned loWord = whichWord(bitPosition);
428 unsigned hiWord = whichWord(bitPosition + numBits - 1);
429 if (loWord == hiWord) {
430 U.pVal[loWord] &= ~(maskBits << loBit);
431 U.pVal[loWord] |= subBits << loBit;
435 static_assert(8 *
sizeof(
WordType) <= 64,
"This code assumes only two words affected");
436 unsigned wordBits = 8 *
sizeof(
WordType);
437 U.pVal[loWord] &= ~(maskBits << loBit);
438 U.pVal[loWord] |= subBits << loBit;
440 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
441 U.pVal[hiWord] |= subBits >> (wordBits - loBit);
445 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
446 "Illegal bit extraction");
449 return APInt(numBits, U.VAL >> bitPosition);
451 unsigned loBit = whichBit(bitPosition);
452 unsigned loWord = whichWord(bitPosition);
453 unsigned hiWord = whichWord(bitPosition + numBits - 1);
456 if (loWord == hiWord)
457 return APInt(numBits, U.pVal[loWord] >> loBit);
462 return APInt(numBits,
ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
465 APInt Result(numBits, 0);
467 unsigned NumDstWords = Result.getNumWords();
469 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
470 for (
unsigned word = 0; word < NumDstWords; ++word) {
471 uint64_t w0 = U.pVal[loWord + word];
473 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
477 return Result.clearUnusedBits();
481 unsigned bitPosition)
const {
482 assert(numBits > 0 &&
"Can't extract zero bits");
483 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
484 "Illegal bit extraction");
485 assert(numBits <= 64 &&
"Illegal bit extraction");
487 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
489 return (U.VAL >> bitPosition) & maskBits;
491 unsigned loBit = whichBit(bitPosition);
492 unsigned loWord = whichWord(bitPosition);
493 unsigned hiWord = whichWord(bitPosition + numBits - 1);
494 if (loWord == hiWord)
495 return (U.pVal[loWord] >> loBit) & maskBits;
497 static_assert(8 *
sizeof(
WordType) <= 64,
"This code assumes only two words affected");
498 unsigned wordBits = 8 *
sizeof(
WordType);
499 uint64_t retBits = U.pVal[loWord] >> loBit;
500 retBits |= U.pVal[hiWord] << (wordBits - loBit);
506 assert(!Str.empty() &&
"Invalid string length");
507 size_t StrLen = Str.size();
510 unsigned IsNegative =
false;
511 if (Str[0] ==
'-' || Str[0] ==
'+') {
512 IsNegative = Str[0] ==
'-';
514 assert(StrLen &&
"String is only a sign, needs a value.");
520 return StrLen + IsNegative;
522 return StrLen * 3 + IsNegative;
524 return StrLen * 4 + IsNegative;
531 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;
534 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
544 if (radix == 2 || radix == 8 || radix == 16)
550 size_t slen = str.
size();
555 if (*p ==
'-' || *p ==
'+') {
558 assert(slen &&
"String is only a sign, needs a value.");
569 if (log == (
unsigned)-1) {
579 if (
Arg.isSingleWord())
588 return static_cast<unsigned>(
hash_value(Key));
593 "SplatSizeInBits must divide width!");
596 return *
this ==
rotl(SplatSizeInBits);
601 return this->
lshr(BitWidth - numBits);
613 assert(NewLen >= V.getBitWidth() &&
"Can't splat to smaller bit width!");
615 APInt Val = V.zext(NewLen);
616 for (
unsigned I = V.getBitWidth();
I < NewLen;
I <<= 1)
622unsigned APInt::countLeadingZerosSlowCase()
const {
639unsigned APInt::countLeadingOnesSlowCase()
const {
650 if (Count == highWordBits) {
651 for (i--; i >= 0; --i) {
663unsigned APInt::countTrailingZerosSlowCase()
const {
670 return std::min(Count, BitWidth);
673unsigned APInt::countTrailingOnesSlowCase()
const {
680 assert(Count <= BitWidth);
684unsigned APInt::countPopulationSlowCase()
const {
691bool APInt::intersectsSlowCase(
const APInt &RHS)
const {
693 if ((U.pVal[i] &
RHS.U.pVal[i]) != 0)
699bool APInt::isSubsetOfSlowCase(
const APInt &RHS)
const {
701 if ((U.pVal[i] & ~
RHS.U.pVal[i]) != 0)
708 assert(BitWidth >= 16 && BitWidth % 8 == 0 &&
"Cannot byteswap!");
710 return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));
712 return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));
713 if (BitWidth <= 64) {
714 uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);
715 Tmp1 >>= (64 - BitWidth);
716 return APInt(BitWidth, Tmp1);
721 Result.U.pVal[
I] = llvm::byteswap<uint64_t>(U.pVal[
N -
I - 1]);
722 if (Result.BitWidth != BitWidth) {
723 Result.lshrInPlace(Result.BitWidth - BitWidth);
724 Result.BitWidth = BitWidth;
732 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
734 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
736 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
738 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
746 APInt Reversed(BitWidth, 0);
747 unsigned S = BitWidth;
761 if (
A ==
B)
return A;
770 unsigned Pow2_A =
A.countr_zero();
771 unsigned Pow2_B =
B.countr_zero();
772 if (Pow2_A > Pow2_B) {
773 A.lshrInPlace(Pow2_A - Pow2_B);
775 }
else if (Pow2_B > Pow2_A) {
776 B.lshrInPlace(Pow2_B - Pow2_A);
792 A.lshrInPlace(
A.countr_zero() - Pow2);
795 B.lshrInPlace(
B.countr_zero() - Pow2);
806 bool isNeg =
I >> 63;
809 int64_t exp = ((
I >> 52) & 0x7ff) - 1023;
813 return APInt(width, 0u);
816 uint64_t mantissa = (
I & (~0ULL >> 12)) | 1ULL << 52;
820 return isNeg ? -
APInt(width, mantissa >> (52 - exp)) :
821 APInt(width, mantissa >> (52 - exp));
825 if (width <= exp - 52)
826 return APInt(width, 0);
829 APInt Tmp(width, mantissa);
831 return isNeg ? -Tmp : Tmp;
850 return double(getWord(0));
854 bool isNeg =
isSigned ? (*this)[BitWidth-1] :
false;
857 APInt Tmp(isNeg ? -(*
this) : (*
this));
870 return std::numeric_limits<double>::infinity();
872 return -std::numeric_limits<double>::infinity();
879 unsigned hiWord = whichWord(n-1);
881 mantissa = Tmp.U.
pVal[0];
885 assert(hiWord > 0 &&
"huh?");
888 mantissa = hibits | lobits;
893 uint64_t I = sign | (exp << 52) | mantissa;
894 return bit_cast<double>(
I);
899 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
904 if (width == BitWidth)
912 Result.U.pVal[i] = U.pVal[i];
917 Result.U.pVal[i] = U.pVal[i] <<
bits >>
bits;
924 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
935 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
947 assert(Width >= BitWidth &&
"Invalid APInt SignExtend request");
952 if (Width == BitWidth)
968 Result.clearUnusedBits();
974 assert(width >= BitWidth &&
"Invalid APInt ZeroExtend request");
977 return APInt(width, U.VAL);
979 if (width == BitWidth)
995 if (BitWidth < width)
997 if (BitWidth > width)
1003 if (BitWidth < width)
1005 if (BitWidth > width)
1006 return trunc(width);
1018void APInt::ashrSlowCase(
unsigned ShiftAmt) {
1031 if (WordsToMove != 0) {
1037 if (BitShift == 0) {
1038 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove *
APINT_WORD_SIZE);
1041 for (
unsigned i = 0; i != WordsToMove - 1; ++i)
1042 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
1046 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
1048 U.pVal[WordsToMove - 1] =
1054 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
1067void APInt::lshrSlowCase(
unsigned ShiftAmt) {
1079void APInt::shlSlowCase(
unsigned ShiftAmt) {
1089 APInt rot = rotateAmt;
1106 rotateAmt %= BitWidth;
1109 return shl(rotateAmt) |
lshr(BitWidth - rotateAmt);
1119 rotateAmt %= BitWidth;
1122 return lshr(rotateAmt) |
shl(BitWidth - rotateAmt);
1151 return lg +
unsigned((*
this)[lg - 1]);
1168 if (magnitude <= 5) {
1169 static const uint8_t results[32] = {
1174 4, 4, 4, 4, 4, 4, 4, 4,
1175 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1185 if (magnitude < 52) {
1186 return APInt(BitWidth,
1196 unsigned nbits = BitWidth, i = 4;
1197 APInt testy(BitWidth, 16);
1198 APInt x_old(BitWidth, 1);
1199 APInt x_new(BitWidth, 0);
1200 APInt two(BitWidth, 2);
1203 for (;; i += 2, testy = testy.
shl(2))
1204 if (i >= nbits || this->
ule(testy)) {
1205 x_old = x_old.
shl(i / 2);
1211 x_new = (this->
udiv(x_old) + x_old).
udiv(two);
1212 if (x_old.
ule(x_new))
1223 APInt square(x_old * x_old);
1224 APInt nextSquare((x_old + 1) * (x_old +1));
1225 if (this->
ult(square))
1227 assert(this->
ule(nextSquare) &&
"Error in APInt::sqrt computation");
1228 APInt midpoint((nextSquare - square).
udiv(two));
1229 APInt offset(*
this - square);
1230 if (offset.
ult(midpoint))
1243 assert(
ult(modulo) &&
"This APInt must be smaller than the modulo");
1253 APInt r[2] = { modulo, *
this };
1255 APInt q(BitWidth, 0);
1258 for (i = 0; r[i^1] != 0; i ^= 1) {
1263 udivrem(r[i], r[i^1], q, r[i]);
1272 return APInt(BitWidth, 0);
1281 return std::move(t[i]);
1289 unsigned m,
unsigned n) {
1290 assert(u &&
"Must provide dividend");
1291 assert(v &&
"Must provide divisor");
1292 assert(q &&
"Must provide quotient");
1293 assert(u != v && u != q && v != q &&
"Must use different memory");
1294 assert(n>1 &&
"n must be > 1");
1302#define DEBUG_KNUTH(X) LLVM_DEBUG(X)
1304#define DEBUG_KNUTH(X) do {} while(false)
1325 for (
unsigned i = 0; i < m+n; ++i) {
1326 uint32_t u_tmp = u[i] >> (32 - shift);
1327 u[i] = (u[i] << shift) | u_carry;
1330 for (
unsigned i = 0; i < n; ++i) {
1331 uint32_t v_tmp = v[i] >> (32 - shift);
1332 v[i] = (v[i] << shift) | v_carry;
1360 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1363 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1366 DEBUG_KNUTH(
dbgs() <<
"KnuthDiv: qp == " << qp <<
", rp == " << rp <<
'\n');
1377 for (
unsigned i = 0; i < n; ++i) {
1379 int64_t subres = int64_t(u[j+i]) - borrow -
Lo_32(p);
1380 u[j+i] =
Lo_32(subres);
1383 <<
", borrow = " << borrow <<
'\n');
1385 bool isNeg = u[j+n] < borrow;
1386 u[j+n] -=
Lo_32(borrow);
1404 for (
unsigned i = 0; i < n; i++) {
1405 uint32_t limit = std::min(u[j+i],v[i]);
1406 u[j+i] += v[i] + carry;
1407 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1432 for (
int i = n-1; i >= 0; i--) {
1433 r[i] = (u[i] >> shift) | carry;
1434 carry = u[i] << (32 - shift);
1438 for (
int i = n-1; i >= 0; i--) {
1448void APInt::divide(
const WordType *LHS,
unsigned lhsWords,
const WordType *RHS,
1449 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1450 assert(lhsWords >= rhsWords &&
"Fractional result");
1459 unsigned n = rhsWords * 2;
1460 unsigned m = (lhsWords * 2) - n;
1469 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1472 Q = &SPACE[(m+n+1) + n];
1474 R = &SPACE[(m+n+1) + n + (m+n)];
1484 memset(U, 0, (m+n+1)*
sizeof(
uint32_t));
1485 for (
unsigned i = 0; i < lhsWords; ++i) {
1488 U[i * 2 + 1] =
Hi_32(tmp);
1493 memset(V, 0, (n)*
sizeof(
uint32_t));
1494 for (
unsigned i = 0; i < rhsWords; ++i) {
1497 V[i * 2 + 1] =
Hi_32(tmp);
1501 memset(Q, 0, (m+n) *
sizeof(
uint32_t));
1503 memset(R, 0, n *
sizeof(
uint32_t));
1509 for (
unsigned i = n; i > 0 &&
V[i-1] == 0; i--) {
1513 for (
unsigned i = m+n; i > 0 &&
U[i-1] == 0; i--)
1522 assert(n != 0 &&
"Divide by zero?");
1526 for (
int i = m; i >= 0; i--) {
1528 if (partial_dividend == 0) {
1531 }
else if (partial_dividend < divisor) {
1533 remainder =
Lo_32(partial_dividend);
1534 }
else if (partial_dividend == divisor) {
1538 Q[i] =
Lo_32(partial_dividend / divisor);
1539 remainder =
Lo_32(partial_dividend - (Q[i] * divisor));
1552 for (
unsigned i = 0; i < lhsWords; ++i)
1553 Quotient[i] =
Make_64(Q[i*2+1], Q[i*2]);
1558 for (
unsigned i = 0; i < rhsWords; ++i)
1559 Remainder[i] =
Make_64(R[i*2+1], R[i*2]);
1563 if (U != &SPACE[0]) {
1572 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1576 assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1577 return APInt(BitWidth, U.VAL /
RHS.U.VAL);
1582 unsigned rhsBits =
RHS.getActiveBits();
1584 assert(rhsWords &&
"Divided by zero???");
1589 return APInt(BitWidth, 0);
1593 if (lhsWords < rhsWords || this->
ult(
RHS))
1595 return APInt(BitWidth, 0);
1598 return APInt(BitWidth, 1);
1601 return APInt(BitWidth, this->U.pVal[0] /
RHS.U.pVal[0]);
1604 APInt Quotient(BitWidth, 0);
1605 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
nullptr);
1614 return APInt(BitWidth, U.VAL /
RHS);
1622 return APInt(BitWidth, 0);
1628 return APInt(BitWidth, 0);
1631 return APInt(BitWidth, 1);
1634 return APInt(BitWidth, this->U.pVal[0] /
RHS);
1637 APInt Quotient(BitWidth, 0);
1638 divide(U.pVal, lhsWords, &
RHS, 1, Quotient.U.
pVal,
nullptr);
1644 if (
RHS.isNegative())
1646 return -((-(*this)).
udiv(
RHS));
1648 if (
RHS.isNegative())
1649 return -(this->
udiv(-RHS));
1650 return this->
udiv(RHS);
1657 return -((-(*this)).
udiv(
RHS));
1660 return -(this->
udiv(-RHS));
1661 return this->
udiv(RHS);
1665 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1667 assert(
RHS.U.VAL != 0 &&
"Remainder by zero?");
1668 return APInt(BitWidth, U.VAL %
RHS.U.VAL);
1675 unsigned rhsBits =
RHS.getActiveBits();
1677 assert(rhsWords &&
"Performing remainder operation by zero ???");
1682 return APInt(BitWidth, 0);
1685 return APInt(BitWidth, 0);
1686 if (lhsWords < rhsWords || this->
ult(
RHS))
1691 return APInt(BitWidth, 0);
1694 return APInt(BitWidth, U.pVal[0] %
RHS.U.pVal[0]);
1697 APInt Remainder(BitWidth, 0);
1698 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords,
nullptr, Remainder.U.
pVal);
1703 assert(
RHS != 0 &&
"Remainder by zero?");
1726 return U.pVal[0] %
RHS;
1730 divide(U.pVal, lhsWords, &
RHS, 1,
nullptr, &Remainder);
1736 if (
RHS.isNegative())
1737 return -((-(*this)).
urem(-
RHS));
1738 return -((-(*this)).
urem(
RHS));
1740 if (
RHS.isNegative())
1741 return this->
urem(-RHS);
1742 return this->
urem(RHS);
1748 return -((-(*this)).
urem(-
RHS));
1749 return -((-(*this)).
urem(
RHS));
1752 return this->
urem(-RHS);
1753 return this->
urem(RHS);
1758 assert(
LHS.BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1759 unsigned BitWidth =
LHS.BitWidth;
1762 if (
LHS.isSingleWord()) {
1763 assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1773 unsigned rhsBits =
RHS.getActiveBits();
1775 assert(rhsWords &&
"Performing divrem operation by zero ???");
1778 if (lhsWords == 0) {
1789 if (lhsWords < rhsWords ||
LHS.ult(
RHS)) {
1808 if (lhsWords == 1) {
1812 Quotient = lhsValue / rhsValue;
1813 Remainder = lhsValue % rhsValue;
1818 divide(
LHS.U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
1821 std::memset(Quotient.U.
pVal + lhsWords, 0,
1823 std::memset(Remainder.U.
pVal + rhsWords, 0,
1830 unsigned BitWidth =
LHS.BitWidth;
1833 if (
LHS.isSingleWord()) {
1835 Remainder =
LHS.U.VAL %
RHS;
1844 if (lhsWords == 0) {
1857 Remainder =
LHS.getZExtValue();
1873 if (lhsWords == 1) {
1876 Quotient = lhsValue /
RHS;
1877 Remainder = lhsValue %
RHS;
1882 divide(
LHS.U.pVal, lhsWords, &
RHS, 1, Quotient.U.
pVal, &Remainder);
1884 std::memset(Quotient.U.
pVal + lhsWords, 0,
1890 if (
LHS.isNegative()) {
1891 if (
RHS.isNegative())
1898 }
else if (
RHS.isNegative()) {
1907 APInt &Quotient, int64_t &Remainder) {
1909 if (
LHS.isNegative()) {
1917 }
else if (
RHS < 0) {
1948 Overflow = Res.
ugt(*
this);
1962 Overflow = Res.
sdiv(
RHS) != *
this ||
1989 return APInt(BitWidth, 0);
1996 return *
this << ShAmt;
2002 return APInt(BitWidth, 0);
2006 return *
this << ShAmt;
2044 return APInt(BitWidth, 0);
2088void APInt::fromString(
unsigned numbits,
StringRef str, uint8_t radix) {
2091 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2093 "Radix should be 2, 8, 10, 16, or 36!");
2096 size_t slen = str.
size();
2097 bool isNeg = *p ==
'-';
2098 if (*p ==
'-' || *p ==
'+') {
2101 assert(slen &&
"String is only a sign, needs a value.");
2103 assert((slen <= numbits || radix != 2) &&
"Insufficient bit width");
2104 assert(((slen-1)*3 <= numbits || radix != 8) &&
"Insufficient bit width");
2105 assert(((slen-1)*4 <= numbits || radix != 16) &&
"Insufficient bit width");
2106 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2107 "Insufficient bit width");
2116 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2120 unsigned digit =
getDigit(*p, radix);
2121 assert(digit < radix &&
"Invalid character in digit string");
2140 bool Signed,
bool formatAsCLiteral)
const {
2141 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2143 "Radix should be 2, 8, 10, 16, or 36!");
2145 const char *Prefix =
"";
2146 if (formatAsCLiteral) {
2169 Str.push_back(*Prefix);
2176 static const char Digits[] =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2180 char *BufPtr = std::end(Buffer);
2196 Str.push_back(*Prefix);
2201 *--BufPtr = Digits[
N % Radix];
2204 Str.append(BufPtr, std::end(Buffer));
2219 Str.push_back(*Prefix);
2224 unsigned StartDig = Str.size();
2229 if (Radix == 2 || Radix == 8 || Radix == 16) {
2231 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2232 unsigned MaskAmt = Radix - 1;
2236 Str.push_back(Digits[Digit]);
2242 udivrem(Tmp, Radix, Tmp, Digit);
2243 assert(Digit < Radix &&
"divide failed");
2244 Str.push_back(Digits[Digit]);
2249 std::reverse(Str.begin()+StartDig, Str.end());
2252#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2257 dbgs() <<
"APInt(" << BitWidth <<
"b, "
2258 << U <<
"u " << S <<
"s)\n";
2274 "Part width must be divisible by 2!");
2298 for (
unsigned i = 1; i < parts; i++)
2304 for (
unsigned i = 0; i < parts; i++)
2310 for (
unsigned i = 0; i < parts; i++)
2319 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2324 parts[whichWord(bit)] |= maskBit(bit);
2329 parts[whichWord(bit)] &= ~maskBit(bit);
2335 for (
unsigned i = 0; i < n; i++) {
2336 if (parts[i] != 0) {
2351 if (parts[n] != 0) {
2352 static_assert(
sizeof(parts[n]) <=
sizeof(
uint64_t));
2368 unsigned srcBits,
unsigned srcLSB) {
2370 assert(dstParts <= dstCount);
2373 tcAssign(dst, src + firstSrcPart, dstParts);
2384 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2386 }
else if (n > srcBits) {
2392 while (dstParts < dstCount)
2393 dst[dstParts++] = 0;
2401 for (
unsigned i = 0; i < parts; i++) {
2404 dst[i] += rhs[i] + 1;
2421 for (
unsigned i = 0; i < parts; ++i) {
2436 for (
unsigned i = 0; i < parts; i++) {
2439 dst[i] -= rhs[i] + 1;
2459 for (
unsigned i = 0; i < parts; ++i) {
2487 unsigned srcParts,
unsigned dstParts,
2490 assert(dst <= src || dst >= src + srcParts);
2491 assert(dstParts <= srcParts + 1);
2494 unsigned n = std::min(dstParts, srcParts);
2496 for (
unsigned i = 0; i < n; i++) {
2503 if (multiplier == 0 || srcPart == 0) {
2513 if (low + mid < low)
2520 if (low + mid < low)
2525 if (low + carry < low)
2532 if (low + dst[i] < low)
2541 if (srcParts < dstParts) {
2543 assert(srcParts + 1 == dstParts);
2544 dst[srcParts] = carry;
2556 for (
unsigned i = dstParts; i < srcParts; i++)
2569 const WordType *rhs,
unsigned parts) {
2570 assert(dst != lhs && dst != rhs);
2573 tcSet(dst, 0, parts);
2575 for (
unsigned i = 0; i < parts; i++)
2585 const WordType *rhs,
unsigned lhsParts,
2586 unsigned rhsParts) {
2588 if (lhsParts > rhsParts)
2591 assert(dst != lhs && dst != rhs);
2593 tcSet(dst, 0, rhsParts);
2595 for (
unsigned i = 0; i < lhsParts; i++)
2596 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1,
true);
2611 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2613 unsigned shiftCount =
tcMSB(rhs, parts) + 1;
2614 if (shiftCount == 0)
2624 tcSet(lhs, 0, parts);
2629 int compare =
tcCompare(remainder, srhs, parts);
2635 if (shiftCount == 0)
2639 if ((mask >>= 1) == 0) {
2660 if (BitShift == 0) {
2661 std::memmove(Dst + WordShift, Dst, (Words - WordShift) *
APINT_WORD_SIZE);
2663 while (Words-- > WordShift) {
2664 Dst[Words] = Dst[Words - WordShift] << BitShift;
2665 if (Words > WordShift)
2686 unsigned WordsToMove = Words - WordShift;
2688 if (BitShift == 0) {
2691 for (
unsigned i = 0; i != WordsToMove; ++i) {
2692 Dst[i] = Dst[i + WordShift] >> BitShift;
2693 if (i + 1 != WordsToMove)
2707 if (lhs[parts] != rhs[parts])
2708 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2764 unsigned RangeWidth) {
2765 unsigned CoeffWidth =
A.getBitWidth();
2766 assert(CoeffWidth ==
B.getBitWidth() && CoeffWidth ==
C.getBitWidth());
2767 assert(RangeWidth <= CoeffWidth &&
2768 "Value range width should be less than coefficient width");
2769 assert(RangeWidth > 1 &&
"Value range bit width should be > 1");
2772 <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2775 if (
C.sextOrTrunc(RangeWidth).isZero()) {
2777 return APInt(CoeffWidth, 0);
2795 A =
A.sext(CoeffWidth);
2796 B =
B.sext(CoeffWidth);
2797 C =
C.sext(CoeffWidth);
2801 if (
A.isNegative()) {
2835 assert(
A.isStrictlyPositive());
2839 return V.isNegative() ? V+
T : V+(
A-
T);
2844 if (
B.isNonNegative()) {
2850 if (
C.isStrictlyPositive())
2861 LowkR = RoundUp(LowkR, R);
2871 C -= -RoundUp(-
C, R);
2888 LLVM_DEBUG(
dbgs() << __func__ <<
": updated coefficients " <<
A <<
"x^2 + "
2889 <<
B <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2892 assert(
D.isNonNegative() &&
"Negative discriminant");
2896 bool InexactSQ = Q !=
D;
2919 assert(
X.isNonNegative() &&
"Solution should be non-negative");
2921 if (!InexactSQ && Rem.
isZero()) {
2926 assert((SQ*SQ).sle(
D) &&
"SQ = |_sqrt(D)_|, so SQ*SQ <= D");
2944 return std::nullopt;
2952std::optional<unsigned>
2954 assert(
A.getBitWidth() ==
B.getBitWidth() &&
"Must have the same bitwidth");
2956 return std::nullopt;
2961 bool MatchAllBits) {
2962 unsigned OldBitWidth =
A.getBitWidth();
2963 assert((((OldBitWidth % NewBitWidth) == 0) ||
2964 ((NewBitWidth % OldBitWidth) == 0)) &&
2965 "One size should be a multiple of the other one. "
2966 "Can't do fractional scaling.");
2969 if (OldBitWidth == NewBitWidth)
2978 if (NewBitWidth > OldBitWidth) {
2980 unsigned Scale = NewBitWidth / OldBitWidth;
2981 for (
unsigned i = 0; i != OldBitWidth; ++i)
2983 NewA.
setBits(i * Scale, (i + 1) * Scale);
2985 unsigned Scale = OldBitWidth / NewBitWidth;
2986 for (
unsigned i = 0; i != NewBitWidth; ++i) {
2988 if (
A.extractBits(Scale, i * Scale).isAllOnes())
2991 if (!
A.extractBits(Scale, i * Scale).isZero())
3003 unsigned StoreBytes) {
3004 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes &&
"Integer too small!");
3005 const uint8_t *Src = (
const uint8_t *)IntVal.getRawData();
3010 memcpy(Dst, Src, StoreBytes);
3015 while (StoreBytes >
sizeof(
uint64_t)) {
3018 memcpy(Dst + StoreBytes, Src,
sizeof(
uint64_t));
3022 memcpy(Dst, Src +
sizeof(
uint64_t) - StoreBytes, StoreBytes);
3029 unsigned LoadBytes) {
3030 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes &&
"Integer too small!");
3031 uint8_t *Dst =
reinterpret_cast<uint8_t *
>(
3032 const_cast<uint64_t *
>(IntVal.getRawData()));
3037 memcpy(Dst, Src, LoadBytes);
3043 while (LoadBytes >
sizeof(
uint64_t)) {
3046 memcpy(Dst, Src + LoadBytes,
sizeof(
uint64_t));
3050 memcpy(Dst +
sizeof(
uint64_t) - LoadBytes, Src, LoadBytes);
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
static APInt::WordType lowHalf(APInt::WordType part)
Returns the value of the lower half of PART.
static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt)
static APInt::WordType highHalf(APInt::WordType part)
Returns the value of the upper half of PART.
static void tcComplement(APInt::WordType *dst, unsigned parts)
static unsigned getDigit(char cdigit, uint8_t radix)
A utility function that converts a character to a digit.
static APInt::WordType lowBitMask(unsigned bits)
static uint64_t * getMemory(unsigned numWords)
A utility function for allocating memory and checking for allocation failure.
static void KnuthDiv(uint32_t *u, uint32_t *v, uint32_t *q, uint32_t *r, unsigned m, unsigned n)
Implementation of Knuth's Algorithm D (Division of nonnegative integers) from "Art of Computer Progra...
static uint64_t * getClearedMemory(unsigned numWords)
A utility function for allocating memory, checking for allocation failures, and ensuring the contents...
This file implements a class to represent arbitrary precision integral constant values and operations...
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")
#define LLVM_UNLIKELY(EXPR)
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isSigned(unsigned int Opcode)
This file defines a hash set that can be used to remove duplication of nodes in a graph.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallString class.
This file implements the C++20 <bit> header.
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt usub_sat(const APInt &RHS) const
APInt udiv(const APInt &RHS) const
Unsigned division operation.
static void tcSetBit(WordType *, unsigned bit)
Set the given bit of a bignum. Zero-based.
static void tcSet(WordType *, WordType, unsigned)
Sets the least significant part of a bignum to the input value, and zeroes out higher parts.
unsigned nearestLogBase2() const
static void udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
Dual division/remainder interface.
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
static int tcExtractBit(const WordType *, unsigned bit)
Extract the given bit of a bignum; returns 0 or 1. Zero-based.
void toString(SmallVectorImpl< char > &Str, unsigned Radix, bool Signed, bool formatAsCLiteral=false) const
Converts an APInt to a string and append it to Str.
APInt zext(unsigned width) const
Zero extend to a new width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
uint64_t getZExtValue() const
Get zero extended value.
APInt truncUSat(unsigned width) const
Truncate to new width with unsigned saturation.
uint64_t * pVal
Used to store the >64 bits integer value.
static void sdivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder)
static WordType tcAdd(WordType *, const WordType *, WordType carry, unsigned)
DST += RHS + CARRY where CARRY is zero or one. Returns the carry flag.
static void tcExtract(WordType *, unsigned dstCount, const WordType *, unsigned srcBits, unsigned srcLSB)
Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to DST, of dstCOUNT parts,...
APInt multiplicativeInverse(const APInt &modulo) const
Computes the multiplicative inverse of this APInt for a given modulo.
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
APInt getHiBits(unsigned numBits) const
Compute an APInt containing numBits highbits from this APInt.
APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
static unsigned getSufficientBitsNeeded(StringRef Str, uint8_t Radix)
Get the bits that are sufficient to represent the string 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.
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
void toStringUnsigned(SmallVectorImpl< char > &Str, unsigned Radix=10) const
Considers the APInt to be unsigned and converts it into a string in the radix given.
APInt sshl_ov(const APInt &Amt, bool &Overflow) const
APInt smul_sat(const APInt &RHS) const
APInt sadd_sat(const APInt &RHS) const
bool sgt(const APInt &RHS) const
Signed greater than comparison.
static int tcCompare(const WordType *, const WordType *, unsigned)
Comparison (unsigned) of two bignums.
APInt & operator++()
Prefix increment operator.
APInt usub_ov(const APInt &RHS, bool &Overflow) const
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
void print(raw_ostream &OS, bool isSigned) const
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
static void tcAssign(WordType *, const WordType *, unsigned)
Assign one bignum to another.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static void tcShiftRight(WordType *, unsigned Words, unsigned Count)
Shift a bignum right Count bits.
static void tcFullMultiply(WordType *, const WordType *, const WordType *, unsigned, unsigned)
DST = LHS * RHS, where DST has width the sum of the widths of the operands.
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.
bool isSingleWord() const
Determine if this APInt just has one word to store value.
unsigned getNumWords() const
Get the number of words.
APInt()
Default constructor that creates an APInt with a 1-bit zero value.
bool isNegative() const
Determine sign of this APInt.
APInt sadd_ov(const APInt &RHS, bool &Overflow) const
APInt & operator<<=(unsigned ShiftAmt)
Left-shift assignment function.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
double roundToDouble() const
Converts this unsigned APInt to a double value.
APInt rotr(unsigned rotateAmt) const
Rotate right by rotateAmt.
APInt reverseBits() const
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
APInt uadd_ov(const APInt &RHS, bool &Overflow) const
static void tcClearBit(WordType *, unsigned bit)
Clear the given bit of a bignum. Zero-based.
void negate()
Negate this APInt in place.
static WordType tcDecrement(WordType *dst, unsigned parts)
Decrement a bignum in-place. Return the borrow flag.
bool isSplat(unsigned SplatSizeInBits) const
Check if the APInt consists of a repeated bit pattern.
APInt & operator-=(const APInt &RHS)
Subtraction assignment operator.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
APInt sdiv_ov(const APInt &RHS, bool &Overflow) const
APInt operator*(const APInt &RHS) const
Multiplication operator.
static unsigned tcLSB(const WordType *, unsigned n)
Returns the bit number of the least or most significant set bit of a number.
unsigned countl_zero() const
The APInt version of std::countl_zero.
static void tcShiftLeft(WordType *, unsigned Words, unsigned Count)
Shift a bignum left Count bits.
static APInt getSplat(unsigned NewLen, const APInt &V)
Return a value containing V broadcasted over NewLen bits.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
APInt sshl_sat(const APInt &RHS) const
static constexpr WordType WORDTYPE_MAX
APInt ushl_sat(const APInt &RHS) const
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
static WordType tcSubtractPart(WordType *, WordType, unsigned)
DST -= RHS. Returns the carry flag.
static bool tcIsZero(const WordType *, unsigned)
Returns true if a bignum is zero, false otherwise.
APInt sextOrTrunc(unsigned width) const
Sign extend or truncate to width.
static unsigned tcMSB(const WordType *parts, unsigned n)
Returns the bit number of the most significant set bit of a number.
static int tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder, WordType *scratch, unsigned parts)
If RHS is zero LHS and REMAINDER are left unchanged, return one.
void dump() const
debug method
APInt rotl(unsigned rotateAmt) const
Rotate left by rotateAmt.
unsigned countl_one() const
Count the number of leading one bits.
void insertBits(const APInt &SubBits, unsigned bitPosition)
Insert the bits from a smaller APInt starting at bitPosition.
unsigned logBase2() const
static int tcMultiplyPart(WordType *dst, const WordType *src, WordType multiplier, WordType carry, unsigned srcParts, unsigned dstParts, bool add)
DST += SRC * MULTIPLIER + PART if add is true DST = SRC * MULTIPLIER + PART if add is false.
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.
static int tcMultiply(WordType *, const WordType *, const WordType *, unsigned)
DST = LHS * RHS, where DST has the same width as the operands and is filled with the least significan...
APInt uadd_sat(const APInt &RHS) const
APInt & operator*=(const APInt &RHS)
Multiplication assignment operator.
uint64_t VAL
Used to store the <= 64 bits integer value.
static unsigned getBitsNeeded(StringRef str, uint8_t radix)
Get bits required for string value.
static WordType tcSubtract(WordType *, const WordType *, WordType carry, unsigned)
DST -= RHS + CARRY where CARRY is zero or one. Returns the carry flag.
static void tcNegate(WordType *, unsigned)
Negate a bignum in-place.
bool getBoolValue() const
Convert APInt to a boolean value.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
static WordType tcIncrement(WordType *dst, unsigned parts)
Increment a bignum in-place. Return the carry flag.
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
APInt sext(unsigned width) const
Sign extend to a new width.
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
APInt shl(unsigned shiftAmt) const
Left-shift function.
APInt umul_sat(const APInt &RHS) const
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
APInt & operator+=(const APInt &RHS)
Addition assignment operator.
void flipBit(unsigned bitPosition)
Toggles a given bit to its opposite value.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static WordType tcAddPart(WordType *, WordType, unsigned)
DST += RHS. Returns the carry flag.
const uint64_t * getRawData() const
This function returns a pointer to the internal storage of the APInt.
void Profile(FoldingSetNodeID &id) const
Used to insert APInt objects, or objects that contain APInt objects, into FoldingSets.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
@ APINT_WORD_SIZE
Byte size of a word.
@ APINT_BITS_PER_WORD
Bits in a word.
APInt extractBits(unsigned numBits, unsigned bitPosition) const
Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
bool isIntN(unsigned N) const
Check if this APInt has an N-bits unsigned integer value.
APInt ssub_ov(const APInt &RHS, bool &Overflow) const
APInt & operator--()
Prefix decrement operator.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
int64_t getSExtValue() const
Get sign extended value.
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
APInt sqrt() const
Compute the square root.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
APInt ssub_sat(const APInt &RHS) const
void toStringSigned(SmallVectorImpl< char > &Str, unsigned Radix=10) const
Considers the APInt to be signed and converts it into a string in the radix given.
APInt truncSSat(unsigned width) const
Truncate to new width with signed saturation.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
size_t size() const
size - Get the array size.
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
SmallString - A SmallString is just a SmallVector with methods and accessors that make it work better...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
StringRef - Represent a constant reference to a string, i.e.
constexpr bool empty() const
empty - Check if the string is empty.
constexpr size_t size() const
size - Get the string size.
An opaque object representing a hash code.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
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.
APInt RoundDoubleToAPInt(double Double, unsigned width)
Converts the given double value into a APInt.
APInt ScaleBitMask(const APInt &A, unsigned NewBitWidth, bool MatchAllBits=false)
Splat/Merge neighboring bits to widen/narrow the bitmask represented by.
std::optional< APInt > SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, unsigned RangeWidth)
Let q(n) = An^2 + Bn + C, and BW = bit width of the value range (e.g.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
@ C
The default llvm calling convention, compatible with C.
static const bool IsLittleEndianHost
This is an optimization pass for GlobalISel generic memory operations.
hash_code hash_value(const FixedPointSemantics &Val)
int popcount(T Value) noexcept
Count the number of set bits in a value.
void StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, unsigned StoreBytes)
StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst with the integer held in In...
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
int countr_zero(T Val)
Count number of 0's from the least significant bit to the most stopping at the first 1.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
constexpr uint32_t Hi_32(uint64_t Value)
Return the high 32 bits of a 64 bit value.
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 uint32_t Lo_32(uint64_t Value)
Return the low 32 bits of a 64 bit value.
@ Mod
The access may modify the value stored in memory.
constexpr unsigned BitWidth
constexpr int64_t SignExtend64(uint64_t x)
Sign-extend the number in the bottom B bits of X to a 64-bit integer.
hash_code hash_combine(const Ts &...args)
Combine values into a single hash_code.
constexpr uint64_t Make_64(uint32_t High, uint32_t Low)
Make a 64-bit integer from a high / low pair of 32-bit integers.
void LoadIntFromMemory(APInt &IntVal, const uint8_t *Src, unsigned LoadBytes)
LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting from Src into IntVal,...
hash_code hash_combine_range(InputIteratorT first, InputIteratorT last)
Compute a hash_code for a sequence of values.
An information struct used to provide DenseMap with the various necessary components for a given valu...
static uint64_t round(uint64_t Acc, uint64_t Input)