21#include "llvm/Config/llvm-config.h"
32#define DEBUG_TYPE "apint"
38 memset(result, 0, numWords *
sizeof(
uint64_t));
49inline static unsigned getDigit(
char cdigit, uint8_t radix) {
52 if (radix == 16 || radix == 36) {
85void APInt::initSlowCase(
const APInt& that) {
91 assert(bigVal.
data() &&
"Null pointer detected!");
107 initFromArray(bigVal);
112 initFromArray(
ArrayRef(bigVal, numWords));
117 fromString(numbits, Str, radix);
120void APInt::reallocate(
unsigned NewBitWidth) {
123 BitWidth = NewBitWidth;
132 BitWidth = NewBitWidth;
139void APInt::assignSlowCase(
const APInt &RHS) {
145 reallocate(
RHS.getBitWidth());
156 ID.AddInteger(BitWidth);
159 ID.AddInteger(U.VAL);
164 for (
unsigned i = 0; i < NumWords; ++i)
165 ID.AddInteger(U.pVal[i]);
172 const unsigned MinimumTrailingZeroes =
Log2(
A);
173 return TrailingZeroes >= MinimumTrailingZeroes;
182 return clearUnusedBits();
191 return clearUnusedBits();
198 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
203 return clearUnusedBits();
211 return clearUnusedBits();
218 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
223 return clearUnusedBits();
231 return clearUnusedBits();
235 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
237 return APInt(BitWidth, U.VAL *
RHS.U.VAL);
241 Result.clearUnusedBits();
245void APInt::andAssignSlowCase(
const APInt &RHS) {
251void APInt::orAssignSlowCase(
const APInt &RHS) {
257void APInt::xorAssignSlowCase(
const APInt &RHS) {
275 return clearUnusedBits();
278bool APInt::equalSlowCase(
const APInt &RHS)
const {
282int APInt::compare(
const APInt& RHS)
const {
283 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
285 return U.VAL <
RHS.U.VAL ? -1 : U.VAL >
RHS.U.VAL;
290int APInt::compareSigned(
const APInt& RHS)
const {
291 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
295 return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
299 bool rhsNeg =
RHS.isNegative();
302 if (lhsNeg != rhsNeg)
303 return lhsNeg ? -1 : 1;
310void APInt::setBitsSlowCase(
unsigned loBit,
unsigned hiBit) {
311 unsigned loWord = whichWord(loBit);
312 unsigned hiWord = whichWord(hiBit);
318 unsigned hiShiftAmt = whichBit(hiBit);
319 if (hiShiftAmt != 0) {
324 if (hiWord == loWord)
327 U.pVal[hiWord] |= hiMask;
330 U.pVal[loWord] |= loMask;
333 for (
unsigned word = loWord + 1; word < hiWord; ++word)
339 for (
unsigned i = 0; i < parts; i++)
344void APInt::flipAllBitsSlowCase() {
353APInt APInt::concatSlowCase(
const APInt &NewLSB)
const {
364 assert(bitPosition < BitWidth &&
"Out of the bit-width range!");
365 setBitVal(bitPosition, !(*
this)[bitPosition]);
370 assert((subBitWidth + bitPosition) <= BitWidth &&
"Illegal bit insertion");
373 if (subBitWidth == 0)
377 if (subBitWidth == BitWidth) {
385 U.VAL &= ~(mask << bitPosition);
386 U.VAL |= (subBits.U.
VAL << bitPosition);
390 unsigned loBit = whichBit(bitPosition);
391 unsigned loWord = whichWord(bitPosition);
392 unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
395 if (loWord == hi1Word) {
397 U.pVal[loWord] &= ~(mask << loBit);
398 U.pVal[loWord] |= (subBits.U.
VAL << loBit);
411 if (remainingBits != 0) {
413 U.pVal[hi1Word] &= ~mask;
414 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
422 for (
unsigned i = 0; i != subBitWidth; ++i)
427 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
430 U.VAL &= ~(maskBits << bitPosition);
431 U.VAL |= subBits << bitPosition;
435 unsigned loBit = whichBit(bitPosition);
436 unsigned loWord = whichWord(bitPosition);
437 unsigned hiWord = whichWord(bitPosition + numBits - 1);
438 if (loWord == hiWord) {
439 U.pVal[loWord] &= ~(maskBits << loBit);
440 U.pVal[loWord] |= subBits << loBit;
444 static_assert(8 *
sizeof(
WordType) <= 64,
"This code assumes only two words affected");
445 unsigned wordBits = 8 *
sizeof(
WordType);
446 U.pVal[loWord] &= ~(maskBits << loBit);
447 U.pVal[loWord] |= subBits << loBit;
449 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
450 U.pVal[hiWord] |= subBits >> (wordBits - loBit);
454 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
455 "Illegal bit extraction");
458 return APInt(numBits, U.VAL >> bitPosition);
460 unsigned loBit = whichBit(bitPosition);
461 unsigned loWord = whichWord(bitPosition);
462 unsigned hiWord = whichWord(bitPosition + numBits - 1);
465 if (loWord == hiWord)
466 return APInt(numBits, U.pVal[loWord] >> loBit);
471 return APInt(numBits,
ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
474 APInt Result(numBits, 0);
476 unsigned NumDstWords = Result.getNumWords();
478 uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
479 for (
unsigned word = 0; word < NumDstWords; ++word) {
480 uint64_t w0 = U.pVal[loWord + word];
482 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
486 return Result.clearUnusedBits();
490 unsigned bitPosition)
const {
491 assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
492 "Illegal bit extraction");
493 assert(numBits <= 64 &&
"Illegal bit extraction");
495 uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
497 return (U.VAL >> bitPosition) & maskBits;
499 unsigned loBit = whichBit(bitPosition);
500 unsigned loWord = whichWord(bitPosition);
501 unsigned hiWord = whichWord(bitPosition + numBits - 1);
502 if (loWord == hiWord)
503 return (U.pVal[loWord] >> loBit) & maskBits;
505 static_assert(8 *
sizeof(
WordType) <= 64,
"This code assumes only two words affected");
506 unsigned wordBits = 8 *
sizeof(
WordType);
507 uint64_t retBits = U.pVal[loWord] >> loBit;
508 retBits |= U.pVal[hiWord] << (wordBits - loBit);
514 assert(!Str.empty() &&
"Invalid string length");
515 size_t StrLen = Str.size();
518 unsigned IsNegative =
false;
519 if (Str[0] ==
'-' || Str[0] ==
'+') {
520 IsNegative = Str[0] ==
'-';
522 assert(StrLen &&
"String is only a sign, needs a value.");
528 return StrLen + IsNegative;
530 return StrLen * 3 + IsNegative;
532 return StrLen * 4 + IsNegative;
539 return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;
542 return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
552 if (radix == 2 || radix == 8 || radix == 16)
558 size_t slen = str.
size();
563 if (*p ==
'-' || *p ==
'+') {
566 assert(slen &&
"String is only a sign, needs a value.");
577 if (log == (
unsigned)-1) {
596 return static_cast<unsigned>(
hash_value(Key));
601 "SplatSizeInBits must divide width!");
604 return *
this ==
rotl(SplatSizeInBits);
609 return this->
lshr(BitWidth - numBits);
621 assert(NewLen >= V.getBitWidth() &&
"Can't splat to smaller bit width!");
623 APInt Val = V.zext(NewLen);
624 for (
unsigned I = V.getBitWidth();
I < NewLen;
I <<= 1)
630unsigned APInt::countLeadingZerosSlowCase()
const {
647unsigned APInt::countLeadingOnesSlowCase()
const {
658 if (Count == highWordBits) {
659 for (i--; i >= 0; --i) {
671unsigned APInt::countTrailingZerosSlowCase()
const {
678 return std::min(Count, BitWidth);
681unsigned APInt::countTrailingOnesSlowCase()
const {
688 assert(Count <= BitWidth);
692unsigned APInt::countPopulationSlowCase()
const {
699bool APInt::intersectsSlowCase(
const APInt &RHS)
const {
701 if ((U.pVal[i] &
RHS.U.pVal[i]) != 0)
707bool APInt::isSubsetOfSlowCase(
const APInt &RHS)
const {
709 if ((U.pVal[i] & ~
RHS.U.pVal[i]) != 0)
716 assert(BitWidth >= 16 && BitWidth % 8 == 0 &&
"Cannot byteswap!");
718 return APInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));
720 return APInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));
721 if (BitWidth <= 64) {
722 uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);
723 Tmp1 >>= (64 - BitWidth);
724 return APInt(BitWidth, Tmp1);
729 Result.U.pVal[
I] = llvm::byteswap<uint64_t>(U.pVal[
N -
I - 1]);
730 if (Result.BitWidth != BitWidth) {
731 Result.lshrInPlace(Result.BitWidth - BitWidth);
732 Result.BitWidth = BitWidth;
740 return APInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
742 return APInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
744 return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
746 return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
754 APInt Reversed(BitWidth, 0);
755 unsigned S = BitWidth;
769 if (
A ==
B)
return A;
778 unsigned Pow2_A =
A.countr_zero();
779 unsigned Pow2_B =
B.countr_zero();
780 if (Pow2_A > Pow2_B) {
781 A.lshrInPlace(Pow2_A - Pow2_B);
783 }
else if (Pow2_B > Pow2_A) {
784 B.lshrInPlace(Pow2_B - Pow2_A);
800 A.lshrInPlace(
A.countr_zero() - Pow2);
803 B.lshrInPlace(
B.countr_zero() - Pow2);
817 int64_t exp = ((
I >> 52) & 0x7ff) - 1023;
821 return APInt(width, 0u);
824 uint64_t mantissa = (
I & (~0ULL >> 12)) | 1ULL << 52;
828 return isNeg ? -
APInt(width, mantissa >> (52 - exp)) :
829 APInt(width, mantissa >> (52 - exp));
833 if (width <= exp - 52)
834 return APInt(width, 0);
837 APInt Tmp(width, mantissa);
839 return isNeg ? -Tmp : Tmp;
858 return double(getWord(0));
878 return std::numeric_limits<double>::infinity();
880 return -std::numeric_limits<double>::infinity();
887 unsigned hiWord = whichWord(n-1);
889 mantissa = Tmp.U.
pVal[0];
893 assert(hiWord > 0 &&
"huh?");
896 mantissa = hibits | lobits;
901 uint64_t I = sign | (exp << 52) | mantissa;
902 return bit_cast<double>(
I);
907 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
912 if (width == BitWidth)
920 Result.U.pVal[i] = U.pVal[i];
925 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
932 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
943 assert(width <= BitWidth &&
"Invalid APInt Truncate request");
955 assert(Width >= BitWidth &&
"Invalid APInt SignExtend request");
960 if (Width == BitWidth)
976 Result.clearUnusedBits();
982 assert(width >= BitWidth &&
"Invalid APInt ZeroExtend request");
985 return APInt(width, U.VAL);
987 if (width == BitWidth)
1003 if (BitWidth < width)
1005 if (BitWidth > width)
1006 return trunc(width);
1011 if (BitWidth < width)
1013 if (BitWidth > width)
1014 return trunc(width);
1026void APInt::ashrSlowCase(
unsigned ShiftAmt) {
1039 if (WordsToMove != 0) {
1045 if (BitShift == 0) {
1046 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove *
APINT_WORD_SIZE);
1049 for (
unsigned i = 0; i != WordsToMove - 1; ++i)
1050 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
1054 U.pVal[WordsToMove - 1] = U.pVal[WordShift + WordsToMove - 1] >> BitShift;
1056 U.pVal[WordsToMove - 1] =
1062 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
1075void APInt::lshrSlowCase(
unsigned ShiftAmt) {
1087void APInt::shlSlowCase(
unsigned ShiftAmt) {
1097 APInt rot = rotateAmt;
1114 rotateAmt %= BitWidth;
1117 return shl(rotateAmt) |
lshr(BitWidth - rotateAmt);
1127 rotateAmt %= BitWidth;
1130 return lshr(rotateAmt) |
shl(BitWidth - rotateAmt);
1159 return lg +
unsigned((*
this)[lg - 1]);
1176 if (magnitude <= 5) {
1177 static const uint8_t results[32] = {
1182 4, 4, 4, 4, 4, 4, 4, 4,
1183 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1193 if (magnitude < 52) {
1194 return APInt(BitWidth,
1204 unsigned nbits = BitWidth, i = 4;
1205 APInt testy(BitWidth, 16);
1206 APInt x_old(BitWidth, 1);
1207 APInt x_new(BitWidth, 0);
1208 APInt two(BitWidth, 2);
1211 for (;; i += 2, testy = testy.
shl(2))
1212 if (i >= nbits || this->
ule(testy)) {
1213 x_old = x_old.
shl(i / 2);
1219 x_new = (this->
udiv(x_old) + x_old).
udiv(two);
1220 if (x_old.
ule(x_new))
1231 APInt square(x_old * x_old);
1232 APInt nextSquare((x_old + 1) * (x_old +1));
1233 if (this->
ult(square))
1235 assert(this->
ule(nextSquare) &&
"Error in APInt::sqrt computation");
1236 APInt midpoint((nextSquare - square).
udiv(two));
1237 APInt offset(*
this - square);
1238 if (offset.
ult(midpoint))
1251 assert(
ult(modulo) &&
"This APInt must be smaller than the modulo");
1261 APInt r[2] = { modulo, *
this };
1263 APInt q(BitWidth, 0);
1266 for (i = 0; r[i^1] != 0; i ^= 1) {
1271 udivrem(r[i], r[i^1], q, r[i]);
1280 return APInt(BitWidth, 0);
1289 return std::move(t[i]);
1297 unsigned m,
unsigned n) {
1298 assert(u &&
"Must provide dividend");
1299 assert(v &&
"Must provide divisor");
1300 assert(q &&
"Must provide quotient");
1301 assert(u != v && u != q && v != q &&
"Must use different memory");
1302 assert(n>1 &&
"n must be > 1");
1310#define DEBUG_KNUTH(X) LLVM_DEBUG(X)
1312#define DEBUG_KNUTH(X) do {} while(false)
1333 for (
unsigned i = 0; i < m+n; ++i) {
1334 uint32_t u_tmp = u[i] >> (32 - shift);
1335 u[i] = (u[i] << shift) | u_carry;
1338 for (
unsigned i = 0; i < n; ++i) {
1339 uint32_t v_tmp = v[i] >> (32 - shift);
1340 v[i] = (v[i] << shift) | v_carry;
1368 if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1371 if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1374 DEBUG_KNUTH(
dbgs() <<
"KnuthDiv: qp == " << qp <<
", rp == " << rp <<
'\n');
1385 for (
unsigned i = 0; i < n; ++i) {
1387 int64_t subres = int64_t(u[j+i]) - borrow -
Lo_32(p);
1388 u[j+i] =
Lo_32(subres);
1391 <<
", borrow = " << borrow <<
'\n');
1393 bool isNeg = u[j+n] < borrow;
1394 u[j+n] -=
Lo_32(borrow);
1412 for (
unsigned i = 0; i < n; i++) {
1413 uint32_t limit = std::min(u[j+i],v[i]);
1414 u[j+i] += v[i] + carry;
1415 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1440 for (
int i = n-1; i >= 0; i--) {
1441 r[i] = (u[i] >> shift) | carry;
1442 carry = u[i] << (32 - shift);
1446 for (
int i = n-1; i >= 0; i--) {
1456void APInt::divide(
const WordType *LHS,
unsigned lhsWords,
const WordType *RHS,
1457 unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1458 assert(lhsWords >= rhsWords &&
"Fractional result");
1467 unsigned n = rhsWords * 2;
1468 unsigned m = (lhsWords * 2) - n;
1477 if ((Remainder?4:3)*n+2*m+1 <= 128) {
1480 Q = &SPACE[(m+n+1) + n];
1482 R = &SPACE[(m+n+1) + n + (m+n)];
1492 memset(U, 0, (m+n+1)*
sizeof(
uint32_t));
1493 for (
unsigned i = 0; i < lhsWords; ++i) {
1496 U[i * 2 + 1] =
Hi_32(tmp);
1501 memset(V, 0, (n)*
sizeof(
uint32_t));
1502 for (
unsigned i = 0; i < rhsWords; ++i) {
1505 V[i * 2 + 1] =
Hi_32(tmp);
1509 memset(Q, 0, (m+n) *
sizeof(
uint32_t));
1511 memset(R, 0, n *
sizeof(
uint32_t));
1517 for (
unsigned i = n; i > 0 &&
V[i-1] == 0; i--) {
1521 for (
unsigned i = m+n; i > 0 &&
U[i-1] == 0; i--)
1530 assert(n != 0 &&
"Divide by zero?");
1534 for (
int i = m; i >= 0; i--) {
1536 if (partial_dividend == 0) {
1539 }
else if (partial_dividend < divisor) {
1541 remainder =
Lo_32(partial_dividend);
1542 }
else if (partial_dividend == divisor) {
1546 Q[i] =
Lo_32(partial_dividend / divisor);
1547 remainder =
Lo_32(partial_dividend - (Q[i] * divisor));
1560 for (
unsigned i = 0; i < lhsWords; ++i)
1561 Quotient[i] =
Make_64(Q[i*2+1], Q[i*2]);
1566 for (
unsigned i = 0; i < rhsWords; ++i)
1567 Remainder[i] =
Make_64(R[i*2+1], R[i*2]);
1571 if (U != &SPACE[0]) {
1580 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1584 assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1585 return APInt(BitWidth, U.VAL /
RHS.U.VAL);
1590 unsigned rhsBits =
RHS.getActiveBits();
1592 assert(rhsWords &&
"Divided by zero???");
1597 return APInt(BitWidth, 0);
1601 if (lhsWords < rhsWords || this->
ult(
RHS))
1603 return APInt(BitWidth, 0);
1606 return APInt(BitWidth, 1);
1609 return APInt(BitWidth, this->U.pVal[0] /
RHS.U.pVal[0]);
1612 APInt Quotient(BitWidth, 0);
1613 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
nullptr);
1622 return APInt(BitWidth, U.VAL /
RHS);
1630 return APInt(BitWidth, 0);
1636 return APInt(BitWidth, 0);
1639 return APInt(BitWidth, 1);
1642 return APInt(BitWidth, this->U.pVal[0] / RHS);
1645 APInt Quotient(BitWidth, 0);
1646 divide(U.pVal, lhsWords, &RHS, 1, Quotient.U.pVal,
nullptr);
1652 if (
RHS.isNegative())
1654 return -((-(*this)).
udiv(
RHS));
1656 if (
RHS.isNegative())
1657 return -(this->
udiv(-RHS));
1658 return this->
udiv(RHS);
1665 return -((-(*this)).
udiv(
RHS));
1668 return -(this->
udiv(-RHS));
1669 return this->
udiv(RHS);
1673 assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1675 assert(
RHS.U.VAL != 0 &&
"Remainder by zero?");
1676 return APInt(BitWidth, U.VAL %
RHS.U.VAL);
1683 unsigned rhsBits =
RHS.getActiveBits();
1685 assert(rhsWords &&
"Performing remainder operation by zero ???");
1690 return APInt(BitWidth, 0);
1693 return APInt(BitWidth, 0);
1694 if (lhsWords < rhsWords || this->
ult(
RHS))
1699 return APInt(BitWidth, 0);
1702 return APInt(BitWidth, U.pVal[0] %
RHS.U.pVal[0]);
1705 APInt Remainder(BitWidth, 0);
1706 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords,
nullptr, Remainder.U.
pVal);
1711 assert(
RHS != 0 &&
"Remainder by zero?");
1734 return U.pVal[0] %
RHS;
1738 divide(U.pVal, lhsWords, &
RHS, 1,
nullptr, &Remainder);
1744 if (
RHS.isNegative())
1745 return -((-(*this)).
urem(-
RHS));
1746 return -((-(*this)).
urem(
RHS));
1748 if (
RHS.isNegative())
1749 return this->
urem(-RHS);
1750 return this->
urem(RHS);
1756 return -((-(*this)).
urem(-
RHS));
1757 return -((-(*this)).
urem(
RHS));
1760 return this->
urem(-RHS);
1761 return this->
urem(RHS);
1766 assert(
LHS.BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1767 unsigned BitWidth =
LHS.BitWidth;
1770 if (
LHS.isSingleWord()) {
1771 assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1781 unsigned rhsBits =
RHS.getActiveBits();
1783 assert(rhsWords &&
"Performing divrem operation by zero ???");
1786 if (lhsWords == 0) {
1797 if (lhsWords < rhsWords ||
LHS.ult(
RHS)) {
1816 if (lhsWords == 1) {
1820 Quotient = lhsValue / rhsValue;
1821 Remainder = lhsValue % rhsValue;
1826 divide(
LHS.U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
1829 std::memset(Quotient.U.
pVal + lhsWords, 0,
1831 std::memset(Remainder.U.
pVal + rhsWords, 0,
1838 unsigned BitWidth =
LHS.BitWidth;
1841 if (
LHS.isSingleWord()) {
1843 Remainder =
LHS.U.VAL %
RHS;
1852 if (lhsWords == 0) {
1865 Remainder =
LHS.getZExtValue();
1881 if (lhsWords == 1) {
1884 Quotient = lhsValue /
RHS;
1885 Remainder = lhsValue %
RHS;
1890 divide(
LHS.U.pVal, lhsWords, &
RHS, 1, Quotient.U.
pVal, &Remainder);
1892 std::memset(Quotient.U.
pVal + lhsWords, 0,
1898 if (
LHS.isNegative()) {
1899 if (
RHS.isNegative())
1906 }
else if (
RHS.isNegative()) {
1915 APInt &Quotient, int64_t &Remainder) {
1917 if (
LHS.isNegative()) {
1925 }
else if (
RHS < 0) {
1956 Overflow = Res.
ugt(*
this);
1970 Overflow = Res.
sdiv(
RHS) != *
this ||
2001 return APInt(BitWidth, 0);
2008 return *
this << ShAmt;
2018 return APInt(BitWidth, 0);
2022 return *
this << ShAmt;
2060 return APInt(BitWidth, 0);
2112void APInt::fromString(
unsigned numbits,
StringRef str, uint8_t radix) {
2115 assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2117 "Radix should be 2, 8, 10, 16, or 36!");
2120 size_t slen = str.
size();
2121 bool isNeg = *p ==
'-';
2122 if (*p ==
'-' || *p ==
'+') {
2125 assert(slen &&
"String is only a sign, needs a value.");
2127 assert((slen <= numbits || radix != 2) &&
"Insufficient bit width");
2128 assert(((slen-1)*3 <= numbits || radix != 8) &&
"Insufficient bit width");
2129 assert(((slen-1)*4 <= numbits || radix != 16) &&
"Insufficient bit width");
2130 assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2131 "Insufficient bit width");
2140 unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2144 unsigned digit =
getDigit(*p, radix);
2145 assert(digit < radix &&
"Invalid character in digit string");
2164 bool formatAsCLiteral,
bool UpperCase)
const {
2165 assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2167 "Radix should be 2, 8, 10, 16, or 36!");
2169 const char *Prefix =
"";
2170 if (formatAsCLiteral) {
2193 Str.push_back(*Prefix);
2200 static const char BothDigits[] =
"0123456789abcdefghijklmnopqrstuvwxyz"
2201 "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2202 const char *Digits = BothDigits + (UpperCase ? 36 : 0);
2206 char *BufPtr = std::end(Buffer);
2222 Str.push_back(*Prefix);
2227 *--BufPtr = Digits[
N % Radix];
2230 Str.append(BufPtr, std::end(Buffer));
2245 Str.push_back(*Prefix);
2250 unsigned StartDig = Str.size();
2255 if (Radix == 2 || Radix == 8 || Radix == 16) {
2257 unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2258 unsigned MaskAmt = Radix - 1;
2262 Str.push_back(Digits[Digit]);
2268 udivrem(Tmp, Radix, Tmp, Digit);
2269 assert(Digit < Radix &&
"divide failed");
2270 Str.push_back(Digits[Digit]);
2275 std::reverse(Str.begin()+StartDig, Str.end());
2278#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2283 dbgs() <<
"APInt(" << BitWidth <<
"b, "
2284 << U <<
"u " << S <<
"s)\n";
2300 "Part width must be divisible by 2!");
2324 for (
unsigned i = 1; i < parts; i++)
2330 for (
unsigned i = 0; i < parts; i++)
2336 for (
unsigned i = 0; i < parts; i++)
2345 return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2350 parts[whichWord(bit)] |= maskBit(bit);
2355 parts[whichWord(bit)] &= ~maskBit(bit);
2361 for (
unsigned i = 0; i < n; i++) {
2362 if (parts[i] != 0) {
2377 if (parts[n] != 0) {
2378 static_assert(
sizeof(parts[n]) <=
sizeof(
uint64_t));
2394 unsigned srcBits,
unsigned srcLSB) {
2396 assert(dstParts <= dstCount);
2399 tcAssign(dst, src + firstSrcPart, dstParts);
2410 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2412 }
else if (n > srcBits) {
2418 while (dstParts < dstCount)
2419 dst[dstParts++] = 0;
2427 for (
unsigned i = 0; i < parts; i++) {
2430 dst[i] += rhs[i] + 1;
2447 for (
unsigned i = 0; i < parts; ++i) {
2462 for (
unsigned i = 0; i < parts; i++) {
2465 dst[i] -= rhs[i] + 1;
2485 for (
unsigned i = 0; i < parts; ++i) {
2513 unsigned srcParts,
unsigned dstParts,
2516 assert(dst <= src || dst >= src + srcParts);
2517 assert(dstParts <= srcParts + 1);
2520 unsigned n = std::min(dstParts, srcParts);
2522 for (
unsigned i = 0; i < n; i++) {
2529 if (multiplier == 0 || srcPart == 0) {
2539 if (low + mid < low)
2546 if (low + mid < low)
2551 if (low + carry < low)
2558 if (low + dst[i] < low)
2567 if (srcParts < dstParts) {
2569 assert(srcParts + 1 == dstParts);
2570 dst[srcParts] = carry;
2582 for (
unsigned i = dstParts; i < srcParts; i++)
2595 const WordType *rhs,
unsigned parts) {
2596 assert(dst != lhs && dst != rhs);
2599 tcSet(dst, 0, parts);
2601 for (
unsigned i = 0; i < parts; i++)
2611 const WordType *rhs,
unsigned lhsParts,
2612 unsigned rhsParts) {
2614 if (lhsParts > rhsParts)
2617 assert(dst != lhs && dst != rhs);
2619 tcSet(dst, 0, rhsParts);
2621 for (
unsigned i = 0; i < lhsParts; i++)
2622 tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1,
true);
2637 assert(lhs != remainder && lhs != srhs && remainder != srhs);
2639 unsigned shiftCount =
tcMSB(rhs, parts) + 1;
2640 if (shiftCount == 0)
2650 tcSet(lhs, 0, parts);
2655 int compare =
tcCompare(remainder, srhs, parts);
2661 if (shiftCount == 0)
2665 if ((mask >>= 1) == 0) {
2686 if (BitShift == 0) {
2687 std::memmove(Dst + WordShift, Dst, (Words - WordShift) *
APINT_WORD_SIZE);
2689 while (Words-- > WordShift) {
2690 Dst[Words] = Dst[Words - WordShift] << BitShift;
2691 if (Words > WordShift)
2712 unsigned WordsToMove = Words - WordShift;
2714 if (BitShift == 0) {
2717 for (
unsigned i = 0; i != WordsToMove; ++i) {
2718 Dst[i] = Dst[i + WordShift] >> BitShift;
2719 if (i + 1 != WordsToMove)
2733 if (lhs[parts] != rhs[parts])
2734 return (lhs[parts] > rhs[parts]) ? 1 : -1;
2790 unsigned RangeWidth) {
2791 unsigned CoeffWidth =
A.getBitWidth();
2792 assert(CoeffWidth ==
B.getBitWidth() && CoeffWidth ==
C.getBitWidth());
2793 assert(RangeWidth <= CoeffWidth &&
2794 "Value range width should be less than coefficient width");
2795 assert(RangeWidth > 1 &&
"Value range bit width should be > 1");
2798 <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2801 if (
C.sextOrTrunc(RangeWidth).isZero()) {
2803 return APInt(CoeffWidth, 0);
2821 A =
A.sext(CoeffWidth);
2822 B =
B.sext(CoeffWidth);
2823 C =
C.sext(CoeffWidth);
2827 if (
A.isNegative()) {
2861 assert(
A.isStrictlyPositive());
2865 return V.isNegative() ? V+
T : V+(
A-
T);
2870 if (
B.isNonNegative()) {
2876 if (
C.isStrictlyPositive())
2887 LowkR = RoundUp(LowkR, R);
2897 C -= -RoundUp(-
C, R);
2914 LLVM_DEBUG(
dbgs() << __func__ <<
": updated coefficients " <<
A <<
"x^2 + "
2915 <<
B <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2918 assert(
D.isNonNegative() &&
"Negative discriminant");
2922 bool InexactSQ = Q !=
D;
2945 assert(
X.isNonNegative() &&
"Solution should be non-negative");
2947 if (!InexactSQ && Rem.
isZero()) {
2952 assert((SQ*SQ).sle(
D) &&
"SQ = |_sqrt(D)_|, so SQ*SQ <= D");
2970 return std::nullopt;
2978std::optional<unsigned>
2980 assert(
A.getBitWidth() ==
B.getBitWidth() &&
"Must have the same bitwidth");
2982 return std::nullopt;
2987 bool MatchAllBits) {
2988 unsigned OldBitWidth =
A.getBitWidth();
2989 assert((((OldBitWidth % NewBitWidth) == 0) ||
2990 ((NewBitWidth % OldBitWidth) == 0)) &&
2991 "One size should be a multiple of the other one. "
2992 "Can't do fractional scaling.");
2995 if (OldBitWidth == NewBitWidth)
3004 if (NewBitWidth > OldBitWidth) {
3006 unsigned Scale = NewBitWidth / OldBitWidth;
3007 for (
unsigned i = 0; i != OldBitWidth; ++i)
3009 NewA.
setBits(i * Scale, (i + 1) * Scale);
3011 unsigned Scale = OldBitWidth / NewBitWidth;
3012 for (
unsigned i = 0; i != NewBitWidth; ++i) {
3014 if (
A.extractBits(Scale, i * Scale).isAllOnes())
3017 if (!
A.extractBits(Scale, i * Scale).isZero())
3029 unsigned StoreBytes) {
3030 assert((IntVal.getBitWidth()+7)/8 >= StoreBytes &&
"Integer too small!");
3031 const uint8_t *Src = (
const uint8_t *)IntVal.getRawData();
3036 memcpy(Dst, Src, StoreBytes);
3041 while (StoreBytes >
sizeof(
uint64_t)) {
3044 memcpy(Dst + StoreBytes, Src,
sizeof(
uint64_t));
3048 memcpy(Dst, Src +
sizeof(
uint64_t) - StoreBytes, StoreBytes);
3055 unsigned LoadBytes) {
3056 assert((IntVal.getBitWidth()+7)/8 >= LoadBytes &&
"Integer too small!");
3057 uint8_t *Dst =
reinterpret_cast<uint8_t *
>(
3058 const_cast<uint64_t *
>(IntVal.getRawData()));
3063 memcpy(Dst, Src, LoadBytes);
3069 while (LoadBytes >
sizeof(
uint64_t)) {
3072 memcpy(Dst, Src + LoadBytes,
sizeof(
uint64_t));
3076 memcpy(Dst +
sizeof(
uint64_t) - LoadBytes, Src, LoadBytes);
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 bool isNeg(Value *V)
Returns true if the operation is a negation of V, and it works for both integers and floats.
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.
bool isAligned(Align A) const
Checks if this APInt -interpreted as an address- is aligned to the provided value.
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.
unsigned countr_zero() const
Count the number of trailing zero bits.
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 toString(SmallVectorImpl< char > &Str, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true) const
Converts an APInt to a string and append it to Str.
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.
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.
unsigned Log2(Align A)
Returns the log2 of the alignment.
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.
This struct is a compact representation of a valid (non-zero power of two) alignment.
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)