1//===-- APInt.cpp - Implement APInt class ---------------------------------===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This file implements a class to represent arbitrary precision integer 10// constant values and provide a variety of arithmetic operations on them. 12//===----------------------------------------------------------------------===// 21#include "llvm/Config/llvm-config.h" 32#define DEBUG_TYPE "apint" 34/// A utility function for allocating memory, checking for allocation failures, 35/// and ensuring the contents are zeroed. 40/// A utility function for allocating memory and checking for allocation 41/// failure. The content is not zeroed. 46/// A utility function that converts a character to a digit. 50if (radix == 16 || radix == 36) {
86void APInt::initSlowCase(
constAPInt& that) {
92assert(bigVal.
data() &&
"Null pointer detected!");
96// Get memory, cleared to 0 98// Calculate the number of words to copy 100// Copy the words from bigVal to pVal 103// Make sure unused high bits are cleared 108 initFromArray(bigVal);
113 initFromArray(
ArrayRef(bigVal, numWords));
118 fromString(numbits, Str, radix);
121void APInt::reallocate(
unsigned NewBitWidth) {
122// If the number of words is the same we can just change the width and stop. 124 BitWidth = NewBitWidth;
128// If we have an allocation, delete it. 133 BitWidth = NewBitWidth;
135// If we are supposed to have an allocation, create it. 140void APInt::assignSlowCase(
constAPInt &RHS) {
141// Don't do anything for X = X 145// Adjust the bit width and handle allocations as necessary. 146 reallocate(
RHS.getBitWidth());
155/// This method 'profiles' an APInt for use with FoldingSet. 157ID.AddInteger(BitWidth);
165for (
unsigned i = 0; i < NumWords; ++i)
166ID.AddInteger(U.pVal[i]);
173constunsigned MinimumTrailingZeroes =
Log2(
A);
174return TrailingZeroes >= MinimumTrailingZeroes;
177/// Prefix increment operator. Increments the APInt by one. 183return clearUnusedBits();
186/// Prefix decrement operator. Decrements the APInt by one. 192return clearUnusedBits();
195/// Adds the RHS APInt to this APInt. 196/// @returns this, after addition of RHS. 197/// Addition assignment operator. 199assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
204return clearUnusedBits();
212return clearUnusedBits();
215/// Subtracts the RHS APInt from this APInt 216/// @returns this, after subtraction 217/// Subtraction assignment operator. 219assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
224return clearUnusedBits();
232return clearUnusedBits();
236assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
238returnAPInt(BitWidth, U.VAL *
RHS.U.VAL,
/*isSigned=*/false,
239/*implicitTrunc=*/true);
243 Result.clearUnusedBits();
247void APInt::andAssignSlowCase(
constAPInt &RHS) {
253void APInt::orAssignSlowCase(
constAPInt &RHS) {
259void APInt::xorAssignSlowCase(
constAPInt &RHS) {
277return clearUnusedBits();
280bool APInt::equalSlowCase(
constAPInt &RHS)
const{
284int APInt::compare(
constAPInt& RHS)
const{
285assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
287return U.VAL <
RHS.U.VAL ? -1 : U.VAL >
RHS.U.VAL;
292int APInt::compareSigned(
constAPInt& RHS)
const{
293assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be same for comparison");
297return lhsSext < rhsSext ? -1 : lhsSext > rhsSext;
301bool rhsNeg =
RHS.isNegative();
303// If the sign bits don't match, then (LHS < RHS) if LHS is negative 305return lhsNeg ? -1 : 1;
307// Otherwise we can just use an unsigned comparison, because even negative 308// numbers compare correctly this way if both have the same signed-ness. 312void APInt::setBitsSlowCase(
unsigned loBit,
unsigned hiBit) {
313unsigned loWord = whichWord(loBit);
314unsigned hiWord = whichWord(hiBit);
316// Create an initial mask for the low word with zeros below loBit. 319// If hiBit is not aligned, we need a high mask. 320unsigned hiShiftAmt = whichBit(hiBit);
321if (hiShiftAmt != 0) {
322// Create a high mask with zeros above hiBit. 324// If loWord and hiWord are equal, then we combine the masks. Otherwise, 325// set the bits in hiWord. 329 U.pVal[hiWord] |= hiMask;
331// Apply the mask to the low word. 332 U.pVal[loWord] |= loMask;
334// Fill any words between loWord and hiWord with all ones. 335for (
unsigned word = loWord + 1; word < hiWord; ++word)
339// Complement a bignum in-place. 341for (
unsigned i = 0; i < parts; i++)
345/// Toggle every bit to its opposite value. 346void APInt::flipAllBitsSlowCase() {
351/// Concatenate the bits from "NewLSB" onto the bottom of *this. This is 353/// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth) 354/// In the slow case, we know the result is large. 355APInt APInt::concatSlowCase(
constAPInt &NewLSB)
const{
362/// Toggle a given bit to its opposite value whose position is given 364/// Toggles a given bit to its opposite value. 366assert(bitPosition < BitWidth &&
"Out of the bit-width range!");
367setBitVal(bitPosition, !(*
this)[bitPosition]);
372assert((subBitWidth + bitPosition) <= BitWidth &&
"Illegal bit insertion");
374// inserting no bits is a noop. 378// Insertion is a direct copy. 379if (subBitWidth == BitWidth) {
384// Single word result can be done as a direct bitmask. 387 U.VAL &= ~(mask << bitPosition);
388 U.VAL |= (subBits.U.
VAL << bitPosition);
392unsigned loBit = whichBit(bitPosition);
393unsigned loWord = whichWord(bitPosition);
394unsigned hi1Word = whichWord(bitPosition + subBitWidth - 1);
396// Insertion within a single word can be done as a direct bitmask. 397if (loWord == hi1Word) {
399 U.pVal[loWord] &= ~(mask << loBit);
400 U.pVal[loWord] |= (subBits.U.
VAL << loBit);
404// Insert on word boundaries. 406// Direct copy whole words. 411// Mask+insert remaining bits. 413if (remainingBits != 0) {
415 U.pVal[hi1Word] &= ~mask;
416 U.pVal[hi1Word] |= subBits.getWord(subBitWidth - 1);
421// General case - set/clear individual bits in dst based on src. 422// TODO - there is scope for optimization here, but at the moment this code 423// path is barely used so prefer readability over performance. 424for (
unsigned i = 0; i != subBitWidth; ++i)
429uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
432 U.VAL &= ~(maskBits << bitPosition);
433 U.VAL |= subBits << bitPosition;
437unsigned loBit = whichBit(bitPosition);
438unsigned loWord = whichWord(bitPosition);
439unsigned hiWord = whichWord(bitPosition + numBits - 1);
440if (loWord == hiWord) {
441 U.pVal[loWord] &= ~(maskBits << loBit);
442 U.pVal[loWord] |= subBits << loBit;
446static_assert(8 *
sizeof(
WordType) <= 64,
"This code assumes only two words affected");
447unsigned wordBits = 8 *
sizeof(
WordType);
448 U.pVal[loWord] &= ~(maskBits << loBit);
449 U.pVal[loWord] |= subBits << loBit;
451 U.pVal[hiWord] &= ~(maskBits >> (wordBits - loBit));
452 U.pVal[hiWord] |= subBits >> (wordBits - loBit);
456assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
457"Illegal bit extraction");
460returnAPInt(numBits, U.VAL >> bitPosition,
/*isSigned=*/false,
461/*implicitTrunc=*/true);
463unsigned loBit = whichBit(bitPosition);
464unsigned loWord = whichWord(bitPosition);
465unsigned hiWord = whichWord(bitPosition + numBits - 1);
467// Single word result extracting bits from a single word source. 469returnAPInt(numBits, U.pVal[loWord] >> loBit,
/*isSigned=*/false,
470/*implicitTrunc=*/true);
472// Extracting bits that start on a source word boundary can be done 473// as a fast memory copy. 475returnAPInt(numBits,
ArrayRef(U.pVal + loWord, 1 + hiWord - loWord));
477// General case - shift + copy source words directly into place. 478APInt Result(numBits, 0);
480unsigned NumDstWords = Result.getNumWords();
482uint64_t *DestPtr = Result.isSingleWord() ? &Result.U.VAL : Result.U.pVal;
483for (
unsigned word = 0; word < NumDstWords; ++word) {
486 (loWord + word + 1) < NumSrcWords ? U.pVal[loWord + word + 1] : 0;
490return Result.clearUnusedBits();
494unsigned bitPosition)
const{
495assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth &&
496"Illegal bit extraction");
497assert(numBits <= 64 &&
"Illegal bit extraction");
499uint64_t maskBits = maskTrailingOnes<uint64_t>(numBits);
501return (U.VAL >> bitPosition) & maskBits;
504"This code assumes only two words affected");
505unsigned loBit = whichBit(bitPosition);
506unsigned loWord = whichWord(bitPosition);
507unsigned hiWord = whichWord(bitPosition + numBits - 1);
509return (U.pVal[loWord] >> loBit) & maskBits;
511uint64_t retBits = U.pVal[loWord] >> loBit;
518assert(!Str.empty() &&
"Invalid string length");
519size_t StrLen = Str.size();
521// Each computation below needs to know if it's negative. 522unsigned IsNegative =
false;
523if (Str[0] ==
'-' || Str[0] ==
'+') {
524 IsNegative = Str[0] ==
'-';
526assert(StrLen &&
"String is only a sign, needs a value.");
529// For radixes of power-of-two values, the bits required is accurately and 532return StrLen + IsNegative;
534return StrLen * 3 + IsNegative;
536return StrLen * 4 + IsNegative;
538// Compute a sufficient number of bits that is always large enough but might 539// be too large. This avoids the assertion in the constructor. This 540// calculation doesn't work appropriately for the numbers 0-9, so just use 4 543return (StrLen == 1 ? 4 : StrLen * 64 / 18) + IsNegative;
546return (StrLen == 1 ? 7 : StrLen * 16 / 3) + IsNegative;
550// Compute a sufficient number of bits that is always large enough but might 554// For bases 2, 8, and 16, the sufficient number of bits is exact and we can 555// return the value directly. For bases 10 and 36, we need to do extra work. 556if (radix == 2 || radix == 8 || radix == 16)
559// This is grossly inefficient but accurate. We could probably do something 560// with a computation of roughly slen*64/20 and then adjust by the value of 561// the first few digits. But, I'm not sure how accurate that could be. 562size_t slen = str.
size();
564// Each computation below needs to know if it's negative. 567if (*p ==
'-' || *p ==
'+') {
570assert(slen &&
"String is only a sign, needs a value.");
574// Convert to the actual binary value. 577// Compute how many bits are required. If the log is infinite, assume we need 578// just bit. If the log is exact and value is negative, then the value is 579// MinSignedValue with (log + 1) bits. 581if (log == (
unsigned)-1) {
605"SplatSizeInBits must divide width!");
606// We can check that all parts of an integer are equal by making use of a 607// little trick: rotate and check if it's still the same value. 608return *
this ==
rotl(SplatSizeInBits);
611/// This function returns the high "numBits" bits of this APInt. 613return this->
lshr(BitWidth - numBits);
616/// This function returns the low "numBits" bits of this APInt. 623/// Return a value containing V broadcasted over NewLen bits. 625assert(NewLen >= V.getBitWidth() &&
"Can't splat to smaller bit width!");
627APInt Val = V.zext(NewLen);
628for (
unsignedI = V.getBitWidth();
I < NewLen;
I <<= 1)
634unsigned APInt::countLeadingZerosSlowCase()
const{
645// Adjust for unused bits in the most significant word (they are zero). 651unsigned APInt::countLeadingOnesSlowCase()
const{
662if (Count == highWordBits) {
663for (i--; i >= 0; --i) {
675unsigned APInt::countTrailingZerosSlowCase()
const{
682return std::min(Count, BitWidth);
685unsigned APInt::countTrailingOnesSlowCase()
const{
696unsigned APInt::countPopulationSlowCase()
const{
703bool APInt::intersectsSlowCase(
constAPInt &RHS)
const{
705if ((U.pVal[i] &
RHS.U.pVal[i]) != 0)
711bool APInt::isSubsetOfSlowCase(
constAPInt &RHS)
const{
713if ((U.pVal[i] & ~
RHS.U.pVal[i]) != 0)
720assert(BitWidth >= 16 && BitWidth % 8 == 0 &&
"Cannot byteswap!");
722returnAPInt(BitWidth, llvm::byteswap<uint16_t>(U.VAL));
724returnAPInt(BitWidth, llvm::byteswap<uint32_t>(U.VAL));
726uint64_t Tmp1 = llvm::byteswap<uint64_t>(U.VAL);
727 Tmp1 >>= (64 - BitWidth);
728returnAPInt(BitWidth, Tmp1);
733 Result.U.pVal[
I] = llvm::byteswap<uint64_t>(U.pVal[
N -
I - 1]);
734if (Result.BitWidth != BitWidth) {
735 Result.lshrInPlace(Result.BitWidth - BitWidth);
736 Result.BitWidth = BitWidth;
744returnAPInt(BitWidth, llvm::reverseBits<uint64_t>(U.VAL));
746returnAPInt(BitWidth, llvm::reverseBits<uint32_t>(U.VAL));
748returnAPInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL));
750returnAPInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL));
758APInt Reversed(BitWidth, 0);
759unsigned S = BitWidth;
772// Fast-path a common case. 775// Corner cases: if either operand is zero, the other is the gcd. 779// Count common powers of 2 and remove all other powers of 2. 782unsigned Pow2_A =
A.countr_zero();
783unsigned Pow2_B =
B.countr_zero();
784if (Pow2_A > Pow2_B) {
785A.lshrInPlace(Pow2_A - Pow2_B);
787 }
elseif (Pow2_B > Pow2_A) {
788B.lshrInPlace(Pow2_B - Pow2_A);
795// Both operands are odd multiples of 2^Pow_2: 797// gcd(a, b) = gcd(|a - b| / 2^i, min(a, b)) 799// This is a modified version of Stein's algorithm, taking advantage of 800// efficient countTrailingZeros(). 804A.lshrInPlace(
A.countr_zero() - Pow2);
807B.lshrInPlace(
B.countr_zero() - Pow2);
817// Get the sign bit from the highest order bit 820// Get the 11-bit exponent and adjust for the 1023 bit bias 821 int64_t exp = ((
I >> 52) & 0x7ff) - 1023;
823// If the exponent is negative, the value is < 0 so just return 0. 825returnAPInt(width, 0u);
827// Extract the mantissa by clearing the top 12 bits (sign + exponent). 828uint64_t mantissa = (
I & (~0ULL >> 12)) | 1ULL << 52;
830// If the exponent doesn't shift all bits out of the mantissa 832returnisNeg ? -
APInt(width, mantissa >> (52 - exp)) :
833APInt(width, mantissa >> (52 - exp));
835// If the client didn't provide enough bits for us to shift the mantissa into 836// then the result is undefined, just return 0 837if (width <= exp - 52)
838returnAPInt(width, 0);
840// Otherwise, we have to shift the mantissa bits up to the right location 841APInt Tmp(width, mantissa);
843returnisNeg ? -Tmp : Tmp;
846/// This function converts this APInt to a double. 847/// The layout for double is as following (IEEE Standard 754): 848/// -------------------------------------- 849/// | Sign Exponent Fraction Bias | 850/// |-------------------------------------- | 851/// | 1[63] 11[62-52] 52[51-00] 1023 | 852/// -------------------------------------- 855// Handle the simple case where the value is contained in one uint64_t. 856// It is wrong to optimize getWord(0) to VAL; there might be more than one word. 862return double(getWord(0));
865// Determine if the value is negative. 868// Construct the absolute value if we're negative. 871// Figure out how many bits we're using. 874// The exponent (without bias normalization) is just the number of bits 875// we are using. Note that the sign bit is gone since we constructed the 879// Return infinity for exponent overflow 882return std::numeric_limits<double>::infinity();
884return -std::numeric_limits<double>::infinity();
886 exp += 1023;
// Increment for 1023 bias 888// Number of bits in mantissa is 52. To obtain the mantissa value, we must 889// extract the high 52 bits from the correct words in pVal. 891unsigned hiWord = whichWord(n-1);
893 mantissa = Tmp.U.
pVal[0];
895 mantissa >>= n - 52;
// shift down, we want the top 52 bits. 897assert(hiWord > 0 &&
"huh?");
900 mantissa = hibits | lobits;
903// The leading bit of mantissa is implicit, so get rid of it. 905uint64_tI = sign | (exp << 52) | mantissa;
906return bit_cast<double>(
I);
909// Truncate to new width. 911assert(width <= BitWidth &&
"Invalid APInt Truncate request");
915/*implicitTrunc=*/true);
917if (width == BitWidth)
925 Result.U.pVal[i] = U.pVal[i];
927// Truncate and copy any partial word. 930 Result.U.pVal[i] = U.pVal[i] << bits >> bits;
935// Truncate to new width with unsigned saturation. 937assert(width <= BitWidth &&
"Invalid APInt Truncate request");
939// Can we just losslessly truncate it? 942// If not, then just return the new limit. 946// Truncate to new width with signed saturation. 948assert(width <= BitWidth &&
"Invalid APInt Truncate request");
950// Can we just losslessly truncate it? 953// If not, then just return the new limits. 958// Sign extend to a new width. 960assert(Width >= BitWidth &&
"Invalid APInt SignExtend request");
965if (Width == BitWidth)
973// Sign extend the last word since there may be unused bits in the input. 978// Fill with sign bits. 981 Result.clearUnusedBits();
985// Zero extend to a new width. 987assert(width >= BitWidth &&
"Invalid APInt ZeroExtend request");
990returnAPInt(width, U.VAL);
992if (width == BitWidth)
1000// Zero remaining words. 1008if (BitWidth < width)
1010if (BitWidth > width)
1016if (BitWidth < width)
1018if (BitWidth > width)
1023/// Arithmetic right-shift this APInt by shiftAmt. 1024/// Arithmetic right-shift function. 1029/// Arithmetic right-shift this APInt by shiftAmt. 1030/// Arithmetic right-shift function. 1031void APInt::ashrSlowCase(
unsigned ShiftAmt) {
1032// Don't bother performing a no-op shift. 1036// Save the original sign bit for later. 1039// WordShift is the inter-part shift; BitShift is intra-part shift. 1044if (WordsToMove != 0) {
1045// Sign extend the last word to fill in the unused bits. 1049// Fastpath for moving by whole words. 1051 std::memmove(U.pVal, U.pVal + WordShift, WordsToMove *
APINT_WORD_SIZE);
1053// Move the words containing significant bits. 1054for (
unsigned i = 0; i != WordsToMove - 1; ++i)
1055 U.pVal[i] = (U.pVal[i + WordShift] >> BitShift) |
1058// Handle the last word which has no high bits to copy. Use an arithmetic 1059// shift to preserve the sign bit. 1060 U.pVal[WordsToMove - 1] =
1061 (int64_t)U.pVal[WordShift + WordsToMove - 1] >> BitShift;
1065// Fill in the remainder based on the original sign. 1066 std::memset(U.pVal + WordsToMove, Negative ? -1 : 0,
1071/// Logical right-shift this APInt by shiftAmt. 1072/// Logical right-shift function. 1077/// Logical right-shift this APInt by shiftAmt. 1078/// Logical right-shift function. 1079void APInt::lshrSlowCase(
unsigned ShiftAmt) {
1083/// Left-shift this APInt by shiftAmt. 1084/// Left-shift function. 1086// It's undefined behavior in C to shift by BitWidth or greater. 1091void APInt::shlSlowCase(
unsigned ShiftAmt) {
1096// Calculate the rotate amount modulo the bit width. 1101APInt rot = rotateAmt;
1103// Extend the rotate APInt, so that the urem doesn't divide by 0. 1104// e.g. APInt(1, 32) would give APInt(1, 0). 1118 rotateAmt %= BitWidth;
1121returnshl(rotateAmt) |
lshr(BitWidth - rotateAmt);
1131 rotateAmt %= BitWidth;
1134returnlshr(rotateAmt) |
shl(BitWidth - rotateAmt);
1137/// \returns the nearest log base 2 of this APInt. Ties round up. 1139/// NOTE: When we have a BitWidth of 1, we define: 1141/// log2(0) = UINT32_MAX 1144/// to get around any mathematical concerns resulting from 1145/// referencing 2 in a space where 2 does no exist. 1147// Special case when we have a bitwidth of 1. If VAL is 1, then we 1148// get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to 1153// Handle the zero case. 1157// The non-zero case is handled by computing: 1159// nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. 1161// where x[i] is referring to the value of the ith bit of x. 1163return lg +
unsigned((*
this)[lg - 1]);
1166// Square Root - this method computes and returns the square root of "this". 1167// Three mechanisms are used for computation. For small values (<= 5 bits), 1168// a table lookup is done. This gets some performance for common cases. For 1169// values using less than 52 bits, the value is converted to double and then 1170// the libc sqrt function is called. The result is rounded and then converted 1171// back to a uint64_t which is then used to construct the result. Finally, 1172// the Babylonian method for computing square roots is used. 1175// Determine the magnitude of the value. 1178// Use a fast table for some small values. This also gets rid of some 1179// rounding errors in libc sqrt for small values. 1180if (magnitude <= 5) {
1181staticconstuint8_t results[32] = {
1184/* 3- 6 */ 2, 2, 2, 2,
1185/* 7-12 */ 3, 3, 3, 3, 3, 3,
1186/* 13-20 */ 4, 4, 4, 4, 4, 4, 4, 4,
1187/* 21-30 */ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
1193// If the magnitude of the value fits in less than 52 bits (the precision of 1194// an IEEE double precision floating point value), then we can use the 1195// libc sqrt function which will probably use a hardware sqrt computation. 1196// This should be faster than the algorithm below. 1197if (magnitude < 52) {
1198returnAPInt(BitWidth,
1203// Okay, all the short cuts are exhausted. We must compute it. The following 1204// is a classical Babylonian method for computing the square root. This code 1205// was adapted to APInt from a wikipedia article on such computations. 1206// See http://www.wikipedia.org/ and go to the page named 1207// Calculate_an_integer_square_root. 1208unsigned nbits = BitWidth, i = 4;
1209APInt testy(BitWidth, 16);
1210APInt x_old(BitWidth, 1);
1211APInt x_new(BitWidth, 0);
1212APInt two(BitWidth, 2);
1214// Select a good starting value using binary logarithms. 1215for (;; i += 2, testy = testy.
shl(2))
1216if (i >= nbits || this->
ule(testy)) {
1217 x_old = x_old.
shl(i / 2);
1221// Use the Babylonian method to arrive at the integer square root: 1223 x_new = (this->
udiv(x_old) + x_old).
udiv(two);
1224if (x_old.
ule(x_new))
1229// Make sure we return the closest approximation 1230// NOTE: The rounding calculation below is correct. It will produce an 1231// off-by-one discrepancy with results from pari/gp. That discrepancy has been 1232// determined to be a rounding issue with pari/gp as it begins to use a 1233// floating point representation after 192 bits. There are no discrepancies 1234// between this algorithm and pari/gp for bit widths < 192 bits. 1235APInt square(x_old * x_old);
1236APInt nextSquare((x_old + 1) * (x_old +1));
1237if (this->
ult(square))
1239assert(this->
ule(nextSquare) &&
"Error in APInt::sqrt computation");
1240APInt midpoint((nextSquare - square).
udiv(two));
1241APInt offset(*
this - square);
1242if (offset.
ult(midpoint))
1247/// \returns the multiplicative inverse of an odd APInt modulo 2^BitWidth. 1250"multiplicative inverse is only defined for odd numbers!");
1252// Use Newton's method. 1253APInt Factor = *
this;
1255while (!(
T = *
this * Factor).
isOne())
1256 Factor *= 2 - std::move(
T);
1260/// Implementation of Knuth's Algorithm D (Division of nonnegative integers) 1261/// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The 1262/// variables here have the same names as in the algorithm. Comments explain 1263/// the algorithm and any deviation from it. 1265unsigned m,
unsigned n) {
1266assert(u &&
"Must provide dividend");
1267assert(v &&
"Must provide divisor");
1268assert(q &&
"Must provide quotient");
1269assert(u != v && u != q && v != q &&
"Must use different memory");
1270assert(n>1 &&
"n must be > 1");
1272// b denotes the base of the number system. In our case b is 2^32. 1275// The DEBUG macros here tend to be spam in the debug output if you're not 1276// debugging this code. Disable them unless KNUTH_DEBUG is defined. 1278#define DEBUG_KNUTH(X) LLVM_DEBUG(X) 1280#define DEBUG_KNUTH(X) do {} while(false) 1289// D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of 1290// u and v by d. Note that we have taken Knuth's advice here to use a power 1291// of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of 1292// 2 allows us to shift instead of multiply and it is easy to determine the 1293// shift amount from the leading zeros. We are basically normalizing the u 1294// and v so that its high bits are shifted to the top of v's range without 1295// overflow. Note that this can require an extra word in u so that u must 1296// be of length m+n+1. 1301for (
unsigned i = 0; i < m+n; ++i) {
1302uint32_t u_tmp = u[i] >> (32 - shift);
1303 u[i] = (u[i] << shift) | u_carry;
1306for (
unsigned i = 0; i < n; ++i) {
1307uint32_t v_tmp = v[i] >> (32 - shift);
1308 v[i] = (v[i] << shift) | v_carry;
1320// D2. [Initialize j.] Set j to m. This is the loop counter over the places. 1324// D3. [Calculate q'.]. 1325// Set qp = (u[j+n]*b + u[j+n-1]) / v[n-1]. (qp=qprime=q') 1326// Set rp = (u[j+n]*b + u[j+n-1]) % v[n-1]. (rp=rprime=r') 1327// Now test if qp == b or qp*v[n-2] > b*rp + u[j+n-2]; if so, decrease 1328// qp by 1, increase rp by v[n-1], and repeat this test if rp < b. The test 1329// on v[n-2] determines at high speed most of the cases in which the trial 1330// value qp is one too large, and it eliminates all cases where qp is two 1336if (qp == b || qp*v[n-2] > b*rp + u[j+n-2]) {
1339if (rp < b && (qp == b || qp*v[n-2] > b*rp + u[j+n-2]))
1342DEBUG_KNUTH(
dbgs() <<
"KnuthDiv: qp == " << qp <<
", rp == " << rp <<
'\n');
1344// D4. [Multiply and subtract.] Replace (u[j+n]u[j+n-1]...u[j]) with 1345// (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation 1346// consists of a simple multiplication by a one-place number, combined with 1348// The digits (u[j+n]...u[j]) should be kept positive; if the result of 1349// this step is actually negative, (u[j+n]...u[j]) should be left as the 1350// true value plus b**(n+1), namely as the b's complement of 1351// the true value, and a "borrow" to the left should be remembered. 1353for (
unsigned i = 0; i < n; ++i) {
1355 int64_t subres = int64_t(u[j+i]) - borrow -
Lo_32(p);
1356 u[j+i] =
Lo_32(subres);
1359 <<
", borrow = " << borrow <<
'\n');
1361boolisNeg = u[j+n] < borrow;
1362 u[j+n] -=
Lo_32(borrow);
1368// D5. [Test remainder.] Set q[j] = qp. If the result of step D4 was 1369// negative, go to step D6; otherwise go on to step D7. 1372// D6. [Add back]. The probability that this step is necessary is very 1373// small, on the order of only 2/b. Make sure that test data accounts for 1374// this possibility. Decrease q[j] by 1 1376// and add (0v[n-1]...v[1]v[0]) to (u[j+n]u[j+n-1]...u[j+1]u[j]). 1377// A carry will occur to the left of u[j+n], and it should be ignored 1378// since it cancels with the borrow that occurred in D4. 1380for (
unsigned i = 0; i < n; i++) {
1381uint32_t limit = std::min(u[j+i],v[i]);
1382 u[j+i] += v[i] + carry;
1383 carry = u[j+i] < limit || (carry && u[j+i] == limit);
1391// D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. 1398// D8. [Unnormalize]. Now q[...] is the desired quotient, and the desired 1399// remainder may be obtained by dividing u[...] by d. If r is non-null we 1400// compute the remainder (urem uses this). 1402// The value d is expressed by the "shift" value above since we avoided 1403// multiplication by d by using a shift left. So, all we have to do is 1408for (
int i = n-1; i >= 0; i--) {
1409 r[i] = (u[i] >> shift) | carry;
1410 carry = u[i] << (32 - shift);
1414for (
int i = n-1; i >= 0; i--) {
1424void APInt::divide(
const WordType *LHS,
unsigned lhsWords,
const WordType *RHS,
1425unsigned rhsWords, WordType *Quotient, WordType *Remainder) {
1426assert(lhsWords >= rhsWords &&
"Fractional result");
1428// First, compose the values into an array of 32-bit words instead of 1429// 64-bit words. This is a necessity of both the "short division" algorithm 1430// and the Knuth "classical algorithm" which requires there to be native 1431// operations for +, -, and * on an m bit value with an m*2 bit result. We 1432// can't use 64-bit operands here because we don't have native results of 1433// 128-bits. Furthermore, casting the 64-bit values to 32-bit values won't 1434// work on large-endian machines. 1435unsigned n = rhsWords * 2;
1436unsigned m = (lhsWords * 2) - n;
1438// Allocate space for the temporary values we need either on the stack, if 1439// it will fit, or on the heap if it won't. 1445if ((Remainder?4:3)*n+2*m+1 <= 128) {
1448 Q = &SPACE[(m+n+1) + n];
1450R = &SPACE[(m+n+1) + n + (m+n)];
1459// Initialize the dividend 1460 memset(U, 0, (m+n+1)*
sizeof(
uint32_t));
1461for (
unsigned i = 0; i < lhsWords; ++i) {
1466U[m+n] = 0;
// this extra word is for "spill" in the Knuth algorithm. 1468// Initialize the divisor 1469 memset(V, 0, (n)*
sizeof(
uint32_t));
1470for (
unsigned i = 0; i < rhsWords; ++i) {
1476// initialize the quotient and remainder 1477 memset(Q, 0, (m+n) *
sizeof(
uint32_t));
1481// Now, adjust m and n for the Knuth division. n is the number of words in 1482// the divisor. m is the number of words by which the dividend exceeds the 1483// divisor (i.e. m+n is the length of the dividend). These sizes must not 1484// contain any zero words or the Knuth algorithm fails. 1485for (
unsigned i = n; i > 0 &&
V[i-1] == 0; i--) {
1489for (
unsigned i = m+n; i > 0 &&
U[i-1] == 0; i--)
1492// If we're left with only a single word for the divisor, Knuth doesn't work 1493// so we implement the short division algorithm here. This is much simpler 1494// and faster because we are certain that we can divide a 64-bit quantity 1495// by a 32-bit quantity at hardware speed and short division is simply a 1496// series of such operations. This is just like doing short division but we 1497// are using base 2^32 instead of base 10. 1498assert(n != 0 &&
"Divide by zero?");
1502for (
int i = m; i >= 0; i--) {
1504if (partial_dividend == 0) {
1507 }
elseif (partial_dividend < divisor) {
1509 remainder =
Lo_32(partial_dividend);
1510 }
elseif (partial_dividend == divisor) {
1514 Q[i] =
Lo_32(partial_dividend / divisor);
1515 remainder =
Lo_32(partial_dividend - (Q[i] * divisor));
1521// Now we're ready to invoke the Knuth classical divide algorithm. In this 1526// If the caller wants the quotient 1528for (
unsigned i = 0; i < lhsWords; ++i)
1529 Quotient[i] =
Make_64(Q[i*2+1], Q[i*2]);
1532// If the caller wants the remainder 1534for (
unsigned i = 0; i < rhsWords; ++i)
1535 Remainder[i] =
Make_64(R[i*2+1], R[i*2]);
1538// Clean up the memory we allocated. 1539if (U != &SPACE[0]) {
1548assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1550// First, deal with the easy case 1552assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1553returnAPInt(BitWidth, U.VAL /
RHS.U.VAL);
1556// Get some facts about the LHS and RHS number of bits and words 1558unsigned rhsBits =
RHS.getActiveBits();
1560assert(rhsWords &&
"Divided by zero???");
1562// Deal with some degenerate cases 1565returnAPInt(BitWidth, 0);
1569if (lhsWords < rhsWords || this->
ult(
RHS))
1570// X / Y ===> 0, iff X < Y 1571returnAPInt(BitWidth, 0);
1574returnAPInt(BitWidth, 1);
1575if (lhsWords == 1)
// rhsWords is 1 if lhsWords is 1. 1576// All high words are zero, just use native divide 1577returnAPInt(BitWidth, this->U.pVal[0] /
RHS.U.pVal[0]);
1579// We have to compute it the hard way. Invoke the Knuth divide algorithm. 1580APInt Quotient(BitWidth, 0);
// to hold result. 1581 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
nullptr);
1588// First, deal with the easy case 1592// Get some facts about the LHS words. 1595// Deal with some degenerate cases 1598returnAPInt(BitWidth, 0);
1603// X / Y ===> 0, iff X < Y 1604returnAPInt(BitWidth, 0);
1607returnAPInt(BitWidth, 1);
1608if (lhsWords == 1)
// rhsWords is 1 if lhsWords is 1. 1609// All high words are zero, just use native divide 1610returnAPInt(BitWidth, this->U.pVal[0] /
RHS);
1612// We have to compute it the hard way. Invoke the Knuth divide algorithm. 1613APInt Quotient(BitWidth, 0);
// to hold result. 1614 divide(U.pVal, lhsWords, &
RHS, 1, Quotient.U.
pVal,
nullptr);
1620if (
RHS.isNegative())
1622return -((-(*this)).
udiv(
RHS));
1624if (
RHS.isNegative())
1625return -(this->
udiv(-RHS));
1626return this->
udiv(RHS);
1633return -((-(*this)).
udiv(
RHS));
1636return -(this->
udiv(-RHS));
1637return this->
udiv(RHS);
1641assert(BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1643assert(
RHS.U.VAL != 0 &&
"Remainder by zero?");
1644returnAPInt(BitWidth, U.VAL %
RHS.U.VAL);
1647// Get some facts about the LHS 1650// Get some facts about the RHS 1651unsigned rhsBits =
RHS.getActiveBits();
1653assert(rhsWords &&
"Performing remainder operation by zero ???");
1655// Check the degenerate cases 1658returnAPInt(BitWidth, 0);
1661returnAPInt(BitWidth, 0);
1662if (lhsWords < rhsWords || this->
ult(
RHS))
1663// X % Y ===> X, iff X < Y 1667returnAPInt(BitWidth, 0);
1669// All high words are zero, just use native remainder 1670returnAPInt(BitWidth, U.pVal[0] %
RHS.U.pVal[0]);
1672// We have to compute it the hard way. Invoke the Knuth divide algorithm. 1673APInt Remainder(BitWidth, 0);
1674 divide(U.pVal, lhsWords,
RHS.U.pVal, rhsWords,
nullptr, Remainder.U.pVal);
1684// Get some facts about the LHS 1687// Check the degenerate cases 1695// X % Y ===> X, iff X < Y 1701// All high words are zero, just use native remainder 1702return U.pVal[0] %
RHS;
1704// We have to compute it the hard way. Invoke the Knuth divide algorithm. 1706 divide(U.pVal, lhsWords, &
RHS, 1,
nullptr, &Remainder);
1712if (
RHS.isNegative())
1713return -((-(*this)).
urem(-
RHS));
1714return -((-(*this)).
urem(
RHS));
1716if (
RHS.isNegative())
1717return this->
urem(-RHS);
1718return this->
urem(RHS);
1724return -((-(*this)).
urem(-
RHS));
1725return -((-(*this)).
urem(
RHS));
1728return this->
urem(-RHS);
1729return this->
urem(RHS);
1734assert(
LHS.BitWidth ==
RHS.BitWidth &&
"Bit widths must be the same");
1735unsigned BitWidth =
LHS.BitWidth;
1737// First, deal with the easy case 1738if (
LHS.isSingleWord()) {
1739assert(
RHS.U.VAL != 0 &&
"Divide by zero?");
1747// Get some size facts about the dividend and divisor 1749unsigned rhsBits =
RHS.getActiveBits();
1751assert(rhsWords &&
"Performing divrem operation by zero ???");
1753// Check the degenerate cases 1761 Quotient =
LHS;
// X / 1 ===> X 1765if (lhsWords < rhsWords ||
LHS.ult(
RHS)) {
1766 Remainder =
LHS;
// X % Y ===> X, iff X < Y 1777// Make sure there is enough space to hold the results. 1778// NOTE: This assumes that reallocate won't affect any bits if it doesn't 1779// change the size. This is necessary if Quotient or Remainder is aliased 1784if (lhsWords == 1) {
// rhsWords is 1 if lhsWords is 1. 1785// There is only one word to consider so use the native versions. 1788 Quotient = lhsValue / rhsValue;
1789 Remainder = lhsValue % rhsValue;
1793// Okay, lets do it the long way 1794 divide(
LHS.U.pVal, lhsWords,
RHS.U.pVal, rhsWords, Quotient.U.
pVal,
1796// Clear the rest of the Quotient and Remainder. 1797 std::memset(Quotient.U.
pVal + lhsWords, 0,
1799 std::memset(Remainder.U.
pVal + rhsWords, 0,
1806unsigned BitWidth =
LHS.BitWidth;
1808// First, deal with the easy case 1809if (
LHS.isSingleWord()) {
1811 Remainder =
LHS.U.VAL %
RHS;
1816// Get some size facts about the dividend and divisor 1819// Check the degenerate cases 1822 Remainder = 0;
// 0 % Y ===> 0 1827 Quotient =
LHS;
// X / 1 ===> X 1828 Remainder = 0;
// X % 1 ===> 0 1833 Remainder =
LHS.getZExtValue();
// X % Y ===> X, iff X < Y 1840 Remainder = 0;
// X % X ===> 0; 1844// Make sure there is enough space to hold the results. 1845// NOTE: This assumes that reallocate won't affect any bits if it doesn't 1846// change the size. This is necessary if Quotient is aliased with LHS. 1849if (lhsWords == 1) {
// rhsWords is 1 if lhsWords is 1. 1850// There is only one word to consider so use the native versions. 1852 Quotient = lhsValue /
RHS;
1853 Remainder = lhsValue %
RHS;
1857// Okay, lets do it the long way 1858 divide(
LHS.U.pVal, lhsWords, &
RHS, 1, Quotient.U.
pVal, &Remainder);
1859// Clear the rest of the Quotient. 1860 std::memset(Quotient.U.
pVal + lhsWords, 0,
1866if (
LHS.isNegative()) {
1867if (
RHS.isNegative())
1874 }
elseif (
RHS.isNegative()) {
1883APInt &Quotient, int64_t &Remainder) {
1885if (
LHS.isNegative()) {
1924 Overflow = Res.
ugt(*
this);
1929// MININT/-1 --> overflow. 1938 Overflow = Res.
sdiv(
RHS) != *
this ||
1969returnAPInt(BitWidth, 0);
1976return *
this << ShAmt;
1986returnAPInt(BitWidth, 0);
1990return *
this << ShAmt;
2035returnAPInt(BitWidth, 0);
2044// The result is negative if one and only one of inputs is negative. 2088// Check our assumptions here 2090assert((radix == 10 || radix == 8 || radix == 16 || radix == 2 ||
2092"Radix should be 2, 8, 10, 16, or 36!");
2095size_t slen = str.
size();
2096boolisNeg = *p ==
'-';
2097if (*p ==
'-' || *p ==
'+') {
2100assert(slen &&
"String is only a sign, needs a value.");
2102assert((slen <= numbits || radix != 2) &&
"Insufficient bit width");
2103assert(((slen-1)*3 <= numbits || radix != 8) &&
"Insufficient bit width");
2104assert(((slen-1)*4 <= numbits || radix != 16) &&
"Insufficient bit width");
2105assert((((slen-1)*64)/22 <= numbits || radix != 10) &&
2106"Insufficient bit width");
2108// Allocate memory if needed 2114// Figure out if we can shift instead of multiply 2115unsigned shift = (radix == 16 ? 4 : radix == 8 ? 3 : radix == 2 ? 1 : 0);
2117// Enter digit traversal loop 2119unsigned digit =
getDigit(*p, radix);
2120assert(digit < radix &&
"Invalid character in digit string");
2122// Shift or multiply the value by the radix 2130// Add in the digit we just interpreted 2133// If its negative, put it in two's complement form 2139bool formatAsCLiteral,
bool UpperCase,
2140bool InsertSeparators)
const{
2141assert((Radix == 10 || Radix == 8 || Radix == 16 || Radix == 2 ||
2143"Radix should be 2, 8, 10, 16, or 36!");
2145constchar *Prefix =
"";
2146if (formatAsCLiteral) {
2149// Binary literals are a non-standard extension added in gcc 4.3: 2150// http://gcc.gnu.org/onlinedocs/gcc-4.3.0/gcc/Binary-constants.html 2166// Number of digits in a group between separators. 2167unsigned Grouping = (Radix == 8 || Radix == 10) ? 3 : 4;
2169// First, check for a zero value and just short circuit the logic below. 2172 Str.push_back(*Prefix);
2179staticconstchar BothDigits[] =
"0123456789abcdefghijklmnopqrstuvwxyz" 2180"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2181constchar *Digits = BothDigits + (UpperCase ? 36 : 0);
2185char *BufPtr = std::end(Buffer);
2201 Str.push_back(*Prefix);
2207if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2209 *--BufPtr = Digits[
N % Radix];
2213 Str.append(BufPtr, std::end(Buffer));
2220// They want to print the signed version and it is a negative value 2221// Flip the bits and add one to turn it into the equivalent positive 2222// value and put a '-' in the result. 2228 Str.push_back(*Prefix);
2232// We insert the digits backward, then reverse them to get the right order. 2233unsigned StartDig = Str.size();
2235// For the 2, 8 and 16 bit cases, we can just shift instead of divide 2236// because the number of bits per digit (1, 3 and 4 respectively) divides 2237// equally. We just shift until the value is zero. 2238if (Radix == 2 || Radix == 8 || Radix == 16) {
2239// Just shift tmp right for each digit width until it becomes zero 2240unsigned ShiftAmt = (Radix == 16 ? 4 : (Radix == 8 ? 3 : 1));
2241unsigned MaskAmt = Radix - 1;
2246if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2247 Str.push_back(
'\'');
2249 Str.push_back(Digits[Digit]);
2257udivrem(Tmp, Radix, Tmp, Digit);
2258assert(Digit < Radix &&
"divide failed");
2259if (InsertSeparators && Pos % Grouping == 0 && Pos > 0)
2260 Str.push_back(
'\'');
2262 Str.push_back(Digits[Digit]);
2267// Reverse the digits before returning. 2268 std::reverse(Str.begin()+StartDig, Str.end());
2271#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2276dbgs() <<
"APInt(" << BitWidth <<
"b, " 2277 << U <<
"u " << S <<
"s)\n";
2287// This implements a variety of operations on a representation of 2288// arbitrary precision, two's-complement, bignum integer values. 2290// Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe 2291// and unrestricting assumption. 2293"Part width must be divisible by 2!");
2295// Returns the integer part with the least significant BITS set. 2296// BITS cannot be zero. 2302/// Returns the value of the lower half of PART. 2307/// Returns the value of the upper half of PART. 2312/// Sets the least significant part of a bignum to the input value, and zeroes 2313/// out higher parts. 2317for (
unsigned i = 1; i < parts; i++)
2321/// Assign one bignum to another. 2323for (
unsigned i = 0; i < parts; i++)
2327/// Returns true if a bignum is zero, false otherwise. 2329for (
unsigned i = 0; i < parts; i++)
2336/// Extract the given bit of a bignum; returns 0 or 1. 2338return (parts[whichWord(bit)] & maskBit(bit)) != 0;
2341/// Set the given bit of a bignum. 2343 parts[whichWord(bit)] |= maskBit(bit);
2346/// Clears the given bit of a bignum. 2348 parts[whichWord(bit)] &= ~maskBit(bit);
2351/// Returns the bit number of the least significant set bit of a number. If the 2352/// input number has no bits set UINT_MAX is returned. 2354for (
unsigned i = 0; i < n; i++) {
2364/// Returns the bit number of the most significant set bit of a number. 2365/// If the input number has no bits set UINT_MAX is returned. 2371static_assert(
sizeof(parts[n]) <=
sizeof(
uint64_t));
2381/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to 2382/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least 2383/// significant bit of DST. All high bits above srcBITS in DST are zero-filled. 2387unsigned srcBits,
unsigned srcLSB) {
2389assert(dstParts <= dstCount);
2392tcAssign(dst, src + firstSrcPart, dstParts);
2397// We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC 2398// in DST. If this is less that srcBits, append the rest, else 2399// clear the high bits. 2403 dst[dstParts - 1] |= ((src[firstSrcPart + dstParts] & mask)
2405 }
elseif (n > srcBits) {
2411while (dstParts < dstCount)
2412 dst[dstParts++] = 0;
2415//// DST += RHS + C where C is zero or one. Returns the carry flag. 2420for (
unsigned i = 0; i < parts; i++) {
2423 dst[i] += rhs[i] + 1;
2434/// This function adds a single "word" integer, src, to the multiple 2435/// "word" integer array, dst[]. dst[] is modified to reflect the addition and 2436/// 1 is returned if there is a carry out, otherwise 0 is returned. 2437/// @returns the carry of the addition. 2440for (
unsigned i = 0; i < parts; ++i) {
2443return 0;
// No need to carry so exit early. 2444 src = 1;
// Carry one to next digit. 2450/// DST -= RHS + C where C is zero or one. Returns the carry flag. 2455for (
unsigned i = 0; i < parts; i++) {
2458 dst[i] -= rhs[i] + 1;
2469/// This function subtracts a single "word" (64-bit word), src, from 2470/// the multi-word integer array, dst[], propagating the borrowed 1 value until 2471/// no further borrowing is needed or it runs out of "words" in dst. The result 2472/// is 1 if "borrowing" exhausted the digits in dst, or 0 if dst was not 2473/// exhausted. In other words, if src > dst then this function returns 1, 2475/// @returns the borrow out of the subtraction 2478for (
unsigned i = 0; i < parts; ++i) {
2482return 0;
// No need to borrow so exit early. 2483 src = 1;
// We have to "borrow 1" from next "word" 2489/// Negate a bignum in-place. 2495/// DST += SRC * MULTIPLIER + CARRY if add is true 2496/// DST = SRC * MULTIPLIER + CARRY if add is false 2497/// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC 2498/// they must start at the same point, i.e. DST == SRC. 2499/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is 2500/// returned. Otherwise DST is filled with the least significant 2501/// DSTPARTS parts of the result, and if all of the omitted higher 2502/// parts were zero return zero, otherwise overflow occurred and 2506unsigned srcParts,
unsigned dstParts,
2508// Otherwise our writes of DST kill our later reads of SRC. 2509assert(dst <= src || dst >= src + srcParts);
2510assert(dstParts <= srcParts + 1);
2512// N loops; minimum of dstParts and srcParts. 2513unsigned n = std::min(dstParts, srcParts);
2515for (
unsigned i = 0; i < n; i++) {
2516// [LOW, HIGH] = MULTIPLIER * SRC[i] + DST[i] + CARRY. 2517// This cannot overflow, because: 2518// (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) 2519// which is less than n^2. 2522if (multiplier == 0 || srcPart == 0) {
2544if (low + carry < low)
2550// And now DST[i], and store the new low part there. 2551if (low + dst[i] < low)
2560if (srcParts < dstParts) {
2561// Full multiplication, there is no overflow. 2562assert(srcParts + 1 == dstParts);
2563 dst[srcParts] = carry;
2567// We overflowed if there is carry. 2571// We would overflow if any significant unwritten parts would be 2572// non-zero. This is true if any remaining src parts are non-zero 2573// and the multiplier is non-zero. 2575for (
unsigned i = dstParts; i < srcParts; i++)
2579// We fitted in the narrow destination. 2583/// DST = LHS * RHS, where DST has the same width as the operands and 2584/// is filled with the least significant parts of the result. Returns 2585/// one if overflow occurred, otherwise zero. DST must be disjoint 2586/// from both operands. 2588constWordType *rhs,
unsigned parts) {
2589assert(dst != lhs && dst != rhs);
2593for (
unsigned i = 0; i < parts; i++) {
2594// Don't accumulate on the first iteration so we don't need to initalize 2597tcMultiplyPart(&dst[i], lhs, rhs[i], 0, parts, parts - i, i != 0);
2603/// DST = LHS * RHS, where DST has width the sum of the widths of the 2604/// operands. No overflow occurs. DST must be disjoint from both operands. 2606constWordType *rhs,
unsigned lhsParts,
2608// Put the narrower number on the LHS for less loops below. 2609if (lhsParts > rhsParts)
2612assert(dst != lhs && dst != rhs);
2614for (
unsigned i = 0; i < lhsParts; i++) {
2615// Don't accumulate on the first iteration so we don't need to initalize 2617tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, i != 0);
2621// If RHS is zero LHS and REMAINDER are left unchanged, return one. 2622// Otherwise set LHS to LHS / RHS with the fractional part discarded, 2623// set REMAINDER to the remainder, return zero. i.e. 2625// OLD_LHS = RHS * LHS + REMAINDER 2627// SCRATCH is a bignum of the same size as the operands and result for 2628// use by the routine; its contents need not be initialized and are 2629// destroyed. LHS, REMAINDER and SCRATCH must be distinct. 2633assert(lhs != remainder && lhs != srhs && remainder != srhs);
2635unsigned shiftCount =
tcMSB(rhs, parts) + 1;
2646tcSet(lhs, 0, parts);
2648// Loop, subtracting SRHS if REMAINDER is greater and adding that to the 2651int compare =
tcCompare(remainder, srhs, parts);
2661if ((mask >>= 1) == 0) {
2670/// Shift a bignum left Count bits in-place. Shifted in bits are zero. There are 2671/// no restrictions on Count. 2673// Don't bother performing a no-op shift. 2677// WordShift is the inter-part shift; BitShift is the intra-part shift. 2681// Fastpath for moving by whole words. 2683 std::memmove(Dst + WordShift, Dst, (Words - WordShift) *
APINT_WORD_SIZE);
2685while (Words-- > WordShift) {
2686 Dst[Words] = Dst[Words - WordShift] << BitShift;
2687if (Words > WordShift)
2693// Fill in the remainder with 0s. 2697/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There 2698/// are no restrictions on Count. 2700// Don't bother performing a no-op shift. 2704// WordShift is the inter-part shift; BitShift is the intra-part shift. 2708unsigned WordsToMove = Words - WordShift;
2709// Fastpath for moving by whole words. 2713for (
unsigned i = 0; i != WordsToMove; ++i) {
2714 Dst[i] = Dst[i + WordShift] >> BitShift;
2715if (i + 1 != WordsToMove)
2720// Fill in the remainder with 0s. 2724// Comparison (unsigned) of two bignums. 2729if (lhs[parts] != rhs[parts])
2730return (lhs[parts] > rhs[parts]) ? 1 : -1;
2738// Currently udivrem always rounds down. 2763// This algorithm deals with arbitrary rounding mode used by sdivrem. 2764// We want to check whether the non-integer part of the mathematical value 2765// is negative or not. If the non-integer part is negative, we need to round 2766// down from Quo; otherwise, if it's positive or 0, we return Quo, as it's 2767// already rounded down. 2777// Currently sdiv rounds towards zero. 2786unsigned RangeWidth) {
2787unsigned CoeffWidth =
A.getBitWidth();
2788assert(CoeffWidth ==
B.getBitWidth() && CoeffWidth ==
C.getBitWidth());
2789assert(RangeWidth <= CoeffWidth &&
2790"Value range width should be less than coefficient width");
2791assert(RangeWidth > 1 &&
"Value range bit width should be > 1");
2794 <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2796// Identify 0 as a (non)solution immediately. 2797if (
C.sextOrTrunc(RangeWidth).isZero()) {
2799returnAPInt(CoeffWidth, 0);
2802// The result of APInt arithmetic has the same bit width as the operands, 2803// so it can actually lose high bits. A product of two n-bit integers needs 2804// 2n-1 bits to represent the full value. 2805// The operation done below (on quadratic coefficients) that can produce 2806// the largest value is the evaluation of the equation during bisection, 2807// which needs 3 times the bitwidth of the coefficient, so the total number 2808// of required bits is 3n. 2810// The purpose of this extension is to simulate the set Z of all integers, 2811// where n+1 > n for all n in Z. In Z it makes sense to talk about positive 2812// and negative numbers (not so much in a modulo arithmetic). The method 2813// used to solve the equation is based on the standard formula for real 2814// numbers, and uses the concepts of "positive" and "negative" with their 2817A =
A.sext(CoeffWidth);
2818B =
B.sext(CoeffWidth);
2819C =
C.sext(CoeffWidth);
2821// Make A > 0 for simplicity. Negate cannot overflow at this point because 2822// the bit width has increased. 2823if (
A.isNegative()) {
2829// Solving an equation q(x) = 0 with coefficients in modular arithmetic 2830// is really solving a set of equations q(x) = kR for k = 0, 1, 2, ..., 2831// and R = 2^BitWidth. 2832// Since we're trying not only to find exact solutions, but also values 2833// that "wrap around", such a set will always have a solution, i.e. an x 2834// that satisfies at least one of the equations, or such that |q(x)| 2835// exceeds kR, while |q(x-1)| for the same k does not. 2837// We need to find a value k, such that Ax^2 + Bx + C = kR will have a 2838// positive solution n (in the above sense), and also such that the n 2839// will be the least among all solutions corresponding to k = 0, 1, ... 2840// (more precisely, the least element in the set 2841// { n(k) | k is such that a solution n(k) exists }). 2843// Consider the parabola (over real numbers) that corresponds to the 2844// quadratic equation. Since A > 0, the arms of the parabola will point 2845// up. Picking different values of k will shift it up and down by R. 2847// We want to shift the parabola in such a way as to reduce the problem 2848// of solving q(x) = kR to solving shifted_q(x) = 0. 2849// (The interesting solutions are the ceilings of the real number 2857assert(
A.isStrictlyPositive());
2861return V.isNegative() ? V+
T : V+(
A-
T);
2864// The vertex of the parabola is at -B/2A, but since A > 0, it's negative 2865// iff B is positive. 2866if (
B.isNonNegative()) {
2867// If B >= 0, the vertex it at a negative location (or at 0), so in 2868// order to have a non-negative solution we need to pick k that makes 2869// C-kR negative. To satisfy all the requirements for the solution 2870// that we are looking for, it needs to be closest to 0 of all k. 2872if (
C.isStrictlyPositive())
2874// Pick the greater solution. 2877// If B < 0, the vertex is at a positive location. For any solution 2878// to exist, the discriminant must be non-negative. This means that 2879// C-kR <= B^2/4A is a necessary condition for k, i.e. there is a 2880// lower bound on values of k: kR >= C - B^2/4A. 2881APInt LowkR =
C - SqrB.
udiv(2*TwoA);
// udiv because all values > 0. 2882// Round LowkR up (towards +inf) to the nearest kR. 2883 LowkR = RoundUp(LowkR, R);
2885// If there exists k meeting the condition above, and such that 2886// C-kR > 0, there will be two positive real number solutions of 2887// q(x) = kR. Out of all such values of k, pick the one that makes 2888// C-kR closest to 0, (i.e. pick maximum k such that C-kR > 0). 2889// In other words, find maximum k such that LowkR <= kR < C. 2891// If LowkR < C, then such a k is guaranteed to exist because 2892// LowkR itself is a multiple of R. 2893C -= -RoundUp(-
C, R);
// C = C - RoundDown(C, R) 2894// Pick the smaller solution. 2897// If C-kR < 0 for all potential k's, it means that one solution 2898// will be negative, while the other will be positive. The positive 2899// solution will shift towards 0 if the parabola is moved up. 2900// Pick the kR closest to the lower bound (i.e. make C-kR closest 2901// to 0, or in other words, out of all parabolas that have solutions, 2902// pick the one that is the farthest "up"). 2903// Since LowkR is itself a multiple of R, simply take C-LowkR. 2905// Pick the greater solution. 2910LLVM_DEBUG(
dbgs() << __func__ <<
": updated coefficients " <<
A <<
"x^2 + " 2911 <<
B <<
"x + " <<
C <<
", rw:" << RangeWidth <<
'\n');
2914assert(
D.isNonNegative() &&
"Negative discriminant");
2918bool InexactSQ = Q !=
D;
2919// The calculated SQ may actually be greater than the exact (non-integer) 2920// value. If that's the case, decrement SQ to get a value that is lower. 2927// SQ is rounded down (i.e SQ * SQ <= D), so the roots may be inexact. 2928// When using the quadratic formula directly, the calculated low root 2929// may be greater than the exact one, since we would be subtracting SQ. 2930// To make sure that the calculated root is not greater than the exact 2931// one, subtract SQ+1 when calculating the low root (for inexact value 2938// The updated coefficients should be such that the (exact) solution is 2939// positive. Since APInt division rounds towards 0, the calculated one 2940// can be 0, but cannot be negative. 2941assert(
X.isNonNegative() &&
"Solution should be non-negative");
2943if (!InexactSQ && Rem.
isZero()) {
2948assert((SQ*SQ).sle(
D) &&
"SQ = |_sqrt(D)_|, so SQ*SQ <= D");
2949// The exact value of the square root of D should be between SQ and SQ+1. 2950// This implies that the solution should be between that corresponding to 2951// SQ (i.e. X) and that corresponding to SQ+1. 2953// The calculated X cannot be greater than the exact (real) solution. 2954// Actually it must be strictly less than the exact solution, while 2955// X+1 will be greater than or equal to it. 2961// If the sign did not change between X and X+1, X is not a valid solution. 2962// This could happen when the actual (exact) roots don't have an integer 2963// between them, so they would both be contained between X and X+1. 2974std::optional<unsigned>
2976assert(
A.getBitWidth() ==
B.getBitWidth() &&
"Must have the same bitwidth");
2984unsigned OldBitWidth =
A.getBitWidth();
2985assert((((OldBitWidth % NewBitWidth) == 0) ||
2986 ((NewBitWidth % OldBitWidth) == 0)) &&
2987"One size should be a multiple of the other one. " 2988"Can't do fractional scaling.");
2990// Check for matching bitwidths. 2991if (OldBitWidth == NewBitWidth)
2996// Check for null input. 3000if (NewBitWidth > OldBitWidth) {
3002unsigned Scale = NewBitWidth / OldBitWidth;
3003for (
unsigned i = 0; i != OldBitWidth; ++i)
3005 NewA.
setBits(i * Scale, (i + 1) * Scale);
3007unsigned Scale = OldBitWidth / NewBitWidth;
3008for (
unsigned i = 0; i != NewBitWidth; ++i) {
3010if (
A.extractBits(Scale, i * Scale).isAllOnes())
3013if (!
A.extractBits(Scale, i * Scale).isZero())
3022/// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst 3023/// with the integer held in IntVal. 3025unsigned StoreBytes) {
3026assert((IntVal.getBitWidth()+7)/8 >= StoreBytes &&
"Integer too small!");
3030// Little-endian host - the source is ordered from LSB to MSB. Order the 3031// destination from LSB to MSB: Do a straight copy. 3032 memcpy(Dst, Src, StoreBytes);
3034// Big-endian host - the source is an array of 64 bit words ordered from 3035// LSW to MSW. Each word is ordered from MSB to LSB. Order the destination 3036// from MSB to LSB: Reverse the word order, but not the bytes in a word. 3037while (StoreBytes >
sizeof(
uint64_t)) {
3039// May not be aligned so use memcpy. 3040 memcpy(Dst + StoreBytes, Src,
sizeof(
uint64_t));
3044 memcpy(Dst, Src +
sizeof(
uint64_t) - StoreBytes, StoreBytes);
3048/// LoadIntFromMemory - Loads the integer stored in the LoadBytes bytes starting 3049/// from Src into IntVal, which is assumed to be wide enough and to hold zero. 3051unsigned LoadBytes) {
3052assert((IntVal.getBitWidth()+7)/8 >= LoadBytes &&
"Integer too small!");
3054const_cast<uint64_t *
>(IntVal.getRawData()));
3057// Little-endian host - the destination must be ordered from LSB to MSB. 3058// The source is ordered from LSB to MSB: Do a straight copy. 3059 memcpy(Dst, Src, LoadBytes);
3061// Big-endian - the destination is an array of 64 bit words ordered from 3062// LSW to MSW. Each word must be ordered from MSB to LSB. The source is 3063// ordered from MSB to LSB: Reverse the word order, but not the bytes in 3065while (LoadBytes >
sizeof(
uint64_t)) {
3067// May not be aligned so use memcpy. 3068 memcpy(Dst, Src + LoadBytes,
sizeof(
uint64_t));
3072 memcpy(Dst +
sizeof(
uint64_t) - LoadBytes, Src, LoadBytes);
3077// Return floor((C1 + C2) / 2) 3078return (C1 & C2) + (C1 ^ C2).ashr(1);
3082// Return floor((C1 + C2) / 2) 3083return (C1 & C2) + (C1 ^ C2).lshr(1);
3087// Return ceil((C1 + C2) / 2) 3088return (C1 | C2) - (C1 ^ C2).ashr(1);
3092// Return ceil((C1 + C2) / 2) 3093return (C1 | C2) - (C1 ^ C2).lshr(1);
3113assert(
N >= 0 &&
"negative exponents not supported.");
3118 int64_t RemainingExponent =
N;
3119while (RemainingExponent > 0) {
3120while (RemainingExponent % 2 == 0) {
3122 RemainingExponent /= 2;
3124 --RemainingExponent;
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,...
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.
static constexpr unsigned APINT_WORD_SIZE
Byte size of a word.
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.
APInt sfloordiv_ov(const APInt &RHS, bool &Overflow) const
Signed integer floor division operation.
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 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.
static constexpr unsigned APINT_BITS_PER_WORD
Bits in a word.
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.
APInt multiplicativeInverse() const
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 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.
bool isOne() const
Determine if this is a value of 1.
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.
void toString(SmallVectorImpl< char > &Str, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false) const
Converts an APInt to a string and append it to Str.
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 mulhu(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on zero-extended operands.
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
APInt avgCeilU(const APInt &C1, const APInt &C2)
Compute the ceil of the unsigned average of C1 and C2.
APInt avgFloorU(const APInt &C1, const APInt &C2)
Compute the floor of the unsigned average of C1 and C2.
APInt mulhs(const APInt &C1, const APInt &C2)
Performs (2*N)-bit multiplication on sign-extended operands.
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
APInt pow(const APInt &X, int64_t N)
Compute X^N for N>=0.
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 avgFloorS(const APInt &C1, const APInt &C2)
Compute the floor of the signed average of C1 and C2.
APInt avgCeilS(const APInt &C1, const APInt &C2)
Compute the ceil of the signed average of C1 and C2.
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)
