diff options
Diffstat (limited to 'contrib/llvm-project/llvm/lib/Support/APInt.cpp')
| -rw-r--r-- | contrib/llvm-project/llvm/lib/Support/APInt.cpp | 455 |
1 files changed, 198 insertions, 257 deletions
diff --git a/contrib/llvm-project/llvm/lib/Support/APInt.cpp b/contrib/llvm-project/llvm/lib/Support/APInt.cpp index a8a950f09747..4940b61602d1 100644 --- a/contrib/llvm-project/llvm/lib/Support/APInt.cpp +++ b/contrib/llvm-project/llvm/lib/Support/APInt.cpp @@ -89,7 +89,6 @@ void APInt::initSlowCase(const APInt& that) { } void APInt::initFromArray(ArrayRef<uint64_t> bigVal) { - assert(BitWidth && "Bitwidth too small"); assert(bigVal.data() && "Null pointer detected!"); if (isSingleWord()) U.VAL = bigVal[0]; @@ -105,19 +104,17 @@ void APInt::initFromArray(ArrayRef<uint64_t> bigVal) { clearUnusedBits(); } -APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) - : BitWidth(numBits) { +APInt::APInt(unsigned numBits, ArrayRef<uint64_t> bigVal) : BitWidth(numBits) { initFromArray(bigVal); } APInt::APInt(unsigned numBits, unsigned numWords, const uint64_t bigVal[]) - : BitWidth(numBits) { + : BitWidth(numBits) { initFromArray(makeArrayRef(bigVal, numWords)); } APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix) - : BitWidth(numbits) { - assert(BitWidth && "Bitwidth too small"); + : BitWidth(numbits) { fromString(numbits, Str, radix); } @@ -140,7 +137,7 @@ void APInt::reallocate(unsigned NewBitWidth) { U.pVal = getMemory(getNumWords()); } -void APInt::AssignSlowCase(const APInt& RHS) { +void APInt::assignSlowCase(const APInt &RHS) { // Don't do anything for X = X if (this == &RHS) return; @@ -233,27 +230,30 @@ APInt APInt::operator*(const APInt& RHS) const { return APInt(BitWidth, U.VAL * RHS.U.VAL); APInt Result(getMemory(getNumWords()), getBitWidth()); - tcMultiply(Result.U.pVal, U.pVal, RHS.U.pVal, getNumWords()); - Result.clearUnusedBits(); return Result; } -void APInt::AndAssignSlowCase(const APInt& RHS) { - tcAnd(U.pVal, RHS.U.pVal, getNumWords()); +void APInt::andAssignSlowCase(const APInt &RHS) { + WordType *dst = U.pVal, *rhs = RHS.U.pVal; + for (size_t i = 0, e = getNumWords(); i != e; ++i) + dst[i] &= rhs[i]; } -void APInt::OrAssignSlowCase(const APInt& RHS) { - tcOr(U.pVal, RHS.U.pVal, getNumWords()); +void APInt::orAssignSlowCase(const APInt &RHS) { + WordType *dst = U.pVal, *rhs = RHS.U.pVal; + for (size_t i = 0, e = getNumWords(); i != e; ++i) + dst[i] |= rhs[i]; } -void APInt::XorAssignSlowCase(const APInt& RHS) { - tcXor(U.pVal, RHS.U.pVal, getNumWords()); +void APInt::xorAssignSlowCase(const APInt &RHS) { + WordType *dst = U.pVal, *rhs = RHS.U.pVal; + for (size_t i = 0, e = getNumWords(); i != e; ++i) + dst[i] ^= rhs[i]; } -APInt& APInt::operator*=(const APInt& RHS) { - assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); +APInt &APInt::operator*=(const APInt &RHS) { *this = *this * RHS; return *this; } @@ -268,7 +268,7 @@ APInt& APInt::operator*=(uint64_t RHS) { return clearUnusedBits(); } -bool APInt::EqualSlowCase(const APInt& RHS) const { +bool APInt::equalSlowCase(const APInt &RHS) const { return std::equal(U.pVal, U.pVal + getNumWords(), RHS.U.pVal); } @@ -327,12 +327,29 @@ void APInt::setBitsSlowCase(unsigned loBit, unsigned hiBit) { U.pVal[word] = WORDTYPE_MAX; } +// Complement a bignum in-place. +static void tcComplement(APInt::WordType *dst, unsigned parts) { + for (unsigned i = 0; i < parts; i++) + dst[i] = ~dst[i]; +} + /// Toggle every bit to its opposite value. void APInt::flipAllBitsSlowCase() { tcComplement(U.pVal, getNumWords()); clearUnusedBits(); } +/// Concatenate the bits from "NewLSB" onto the bottom of *this. This is +/// equivalent to: +/// (this->zext(NewWidth) << NewLSB.getBitWidth()) | NewLSB.zext(NewWidth) +/// In the slow case, we know the result is large. +APInt APInt::concatSlowCase(const APInt &NewLSB) const { + unsigned NewWidth = getBitWidth() + NewLSB.getBitWidth(); + APInt Result = NewLSB.zextOrSelf(NewWidth); + Result.insertBits(*this, NewLSB.getBitWidth()); + return Result; +} + /// Toggle a given bit to its opposite value whose position is given /// as "bitPosition". /// Toggles a given bit to its opposite value. @@ -343,8 +360,11 @@ void APInt::flipBit(unsigned bitPosition) { void APInt::insertBits(const APInt &subBits, unsigned bitPosition) { unsigned subBitWidth = subBits.getBitWidth(); - assert(0 < subBitWidth && (subBitWidth + bitPosition) <= BitWidth && - "Illegal bit insertion"); + assert((subBitWidth + bitPosition) <= BitWidth && "Illegal bit insertion"); + + // inserting no bits is a noop. + if (subBitWidth == 0) + return; // Insertion is a direct copy. if (subBitWidth == BitWidth) { @@ -424,7 +444,6 @@ void APInt::insertBits(uint64_t subBits, unsigned bitPosition, unsigned numBits) } APInt APInt::extractBits(unsigned numBits, unsigned bitPosition) const { - assert(numBits > 0 && "Can't extract zero bits"); assert(bitPosition < BitWidth && (numBits + bitPosition) <= BitWidth && "Illegal bit extraction"); @@ -550,7 +569,7 @@ hash_code llvm::hash_value(const APInt &Arg) { hash_combine_range(Arg.U.pVal, Arg.U.pVal + Arg.getNumWords())); } -unsigned DenseMapInfo<APInt>::getHashValue(const APInt &Key) { +unsigned DenseMapInfo<APInt, void>::getHashValue(const APInt &Key) { return static_cast<unsigned>(hash_value(Key)); } @@ -702,6 +721,8 @@ APInt APInt::reverseBits() const { return APInt(BitWidth, llvm::reverseBits<uint16_t>(U.VAL)); case 8: return APInt(BitWidth, llvm::reverseBits<uint8_t>(U.VAL)); + case 0: + return *this; default: break; } @@ -861,7 +882,6 @@ double APInt::roundToDouble(bool isSigned) const { // Truncate to new width. APInt APInt::trunc(unsigned width) const { assert(width < BitWidth && "Invalid APInt Truncate request"); - assert(width && "Can't truncate to 0 bits"); if (width <= APINT_BITS_PER_WORD) return APInt(width, getRawData()[0]); @@ -884,7 +904,6 @@ APInt APInt::trunc(unsigned width) const { // Truncate to new width with unsigned saturation. APInt APInt::truncUSat(unsigned width) const { assert(width < BitWidth && "Invalid APInt Truncate request"); - assert(width && "Can't truncate to 0 bits"); // Can we just losslessly truncate it? if (isIntN(width)) @@ -896,7 +915,6 @@ APInt APInt::truncUSat(unsigned width) const { // Truncate to new width with signed saturation. APInt APInt::truncSSat(unsigned width) const { assert(width < BitWidth && "Invalid APInt Truncate request"); - assert(width && "Can't truncate to 0 bits"); // Can we just losslessly truncate it? if (isSignedIntN(width)) @@ -1059,6 +1077,8 @@ void APInt::shlSlowCase(unsigned ShiftAmt) { // Calculate the rotate amount modulo the bit width. static unsigned rotateModulo(unsigned BitWidth, const APInt &rotateAmt) { + if (LLVM_UNLIKELY(BitWidth == 0)) + return 0; unsigned rotBitWidth = rotateAmt.getBitWidth(); APInt rot = rotateAmt; if (rotBitWidth < BitWidth) { @@ -1075,6 +1095,8 @@ APInt APInt::rotl(const APInt &rotateAmt) const { } APInt APInt::rotl(unsigned rotateAmt) const { + if (LLVM_UNLIKELY(BitWidth == 0)) + return *this; rotateAmt %= BitWidth; if (rotateAmt == 0) return *this; @@ -1086,12 +1108,43 @@ APInt APInt::rotr(const APInt &rotateAmt) const { } APInt APInt::rotr(unsigned rotateAmt) const { + if (BitWidth == 0) + return *this; rotateAmt %= BitWidth; if (rotateAmt == 0) return *this; return lshr(rotateAmt) | shl(BitWidth - rotateAmt); } +/// \returns the nearest log base 2 of this APInt. Ties round up. +/// +/// NOTE: When we have a BitWidth of 1, we define: +/// +/// log2(0) = UINT32_MAX +/// log2(1) = 0 +/// +/// to get around any mathematical concerns resulting from +/// referencing 2 in a space where 2 does no exist. +unsigned APInt::nearestLogBase2() const { + // Special case when we have a bitwidth of 1. If VAL is 1, then we + // get 0. If VAL is 0, we get WORDTYPE_MAX which gets truncated to + // UINT32_MAX. + if (BitWidth == 1) + return U.VAL - 1; + + // Handle the zero case. + if (isZero()) + return UINT32_MAX; + + // The non-zero case is handled by computing: + // + // nearestLogBase2(x) = logBase2(x) + x[logBase2(x)-1]. + // + // where x[i] is referring to the value of the ith bit of x. + unsigned lg = logBase2(); + return lg + unsigned((*this)[lg - 1]); +} + // Square Root - this method computes and returns the square root of "this". // Three mechanisms are used for computation. For small values (<= 5 bits), // a table lookup is done. This gets some performance for common cases. For @@ -1222,98 +1275,6 @@ APInt APInt::multiplicativeInverse(const APInt& modulo) const { return std::move(t[i]); } -/// Calculate the magic numbers required to implement a signed integer division -/// by a constant as a sequence of multiplies, adds and shifts. Requires that -/// the divisor not be 0, 1, or -1. Taken from "Hacker's Delight", Henry S. -/// Warren, Jr., chapter 10. -APInt::ms APInt::magic() const { - const APInt& d = *this; - unsigned p; - APInt ad, anc, delta, q1, r1, q2, r2, t; - APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); - struct ms mag; - - ad = d.abs(); - t = signedMin + (d.lshr(d.getBitWidth() - 1)); - anc = t - 1 - t.urem(ad); // absolute value of nc - p = d.getBitWidth() - 1; // initialize p - q1 = signedMin.udiv(anc); // initialize q1 = 2p/abs(nc) - r1 = signedMin - q1*anc; // initialize r1 = rem(2p,abs(nc)) - q2 = signedMin.udiv(ad); // initialize q2 = 2p/abs(d) - r2 = signedMin - q2*ad; // initialize r2 = rem(2p,abs(d)) - do { - p = p + 1; - q1 = q1<<1; // update q1 = 2p/abs(nc) - r1 = r1<<1; // update r1 = rem(2p/abs(nc)) - if (r1.uge(anc)) { // must be unsigned comparison - q1 = q1 + 1; - r1 = r1 - anc; - } - q2 = q2<<1; // update q2 = 2p/abs(d) - r2 = r2<<1; // update r2 = rem(2p/abs(d)) - if (r2.uge(ad)) { // must be unsigned comparison - q2 = q2 + 1; - r2 = r2 - ad; - } - delta = ad - r2; - } while (q1.ult(delta) || (q1 == delta && r1 == 0)); - - mag.m = q2 + 1; - if (d.isNegative()) mag.m = -mag.m; // resulting magic number - mag.s = p - d.getBitWidth(); // resulting shift - return mag; -} - -/// Calculate the magic numbers required to implement an unsigned integer -/// division by a constant as a sequence of multiplies, adds and shifts. -/// Requires that the divisor not be 0. Taken from "Hacker's Delight", Henry -/// S. Warren, Jr., chapter 10. -/// LeadingZeros can be used to simplify the calculation if the upper bits -/// of the divided value are known zero. -APInt::mu APInt::magicu(unsigned LeadingZeros) const { - const APInt& d = *this; - unsigned p; - APInt nc, delta, q1, r1, q2, r2; - struct mu magu; - magu.a = 0; // initialize "add" indicator - APInt allOnes = APInt::getAllOnesValue(d.getBitWidth()).lshr(LeadingZeros); - APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); - APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); - - nc = allOnes - (allOnes - d).urem(d); - p = d.getBitWidth() - 1; // initialize p - q1 = signedMin.udiv(nc); // initialize q1 = 2p/nc - r1 = signedMin - q1*nc; // initialize r1 = rem(2p,nc) - q2 = signedMax.udiv(d); // initialize q2 = (2p-1)/d - r2 = signedMax - q2*d; // initialize r2 = rem((2p-1),d) - do { - p = p + 1; - if (r1.uge(nc - r1)) { - q1 = q1 + q1 + 1; // update q1 - r1 = r1 + r1 - nc; // update r1 - } - else { - q1 = q1+q1; // update q1 - r1 = r1+r1; // update r1 - } - if ((r2 + 1).uge(d - r2)) { - if (q2.uge(signedMax)) magu.a = 1; - q2 = q2+q2 + 1; // update q2 - r2 = r2+r2 + 1 - d; // update r2 - } - else { - if (q2.uge(signedMin)) magu.a = 1; - q2 = q2+q2; // update q2 - r2 = r2+r2 + 1; // update r2 - } - delta = d - 1 - r2; - } while (p < d.getBitWidth()*2 && - (q1.ult(delta) || (q1 == delta && r1 == 0))); - magu.m = q2 + 1; // resulting magic number - magu.s = p - d.getBitWidth(); // resulting shift - return magu; -} - /// Implementation of Knuth's Algorithm D (Division of nonnegative integers) /// from "Art of Computer Programming, Volume 2", section 4.3.1, p. 272. The /// variables here have the same names as in the algorithm. Comments explain @@ -1984,15 +1945,16 @@ APInt APInt::usub_ov(const APInt &RHS, bool &Overflow) const { APInt APInt::sdiv_ov(const APInt &RHS, bool &Overflow) const { // MININT/-1 --> overflow. - Overflow = isMinSignedValue() && RHS.isAllOnesValue(); + Overflow = isMinSignedValue() && RHS.isAllOnes(); return sdiv(RHS); } APInt APInt::smul_ov(const APInt &RHS, bool &Overflow) const { APInt Res = *this * RHS; - if (*this != 0 && RHS != 0) - Overflow = Res.sdiv(RHS) != *this || Res.sdiv(*this) != RHS; + if (RHS != 0) + Overflow = Res.sdiv(RHS) != *this || + (isMinSignedValue() && RHS.isAllOnes()); else Overflow = false; return Res; @@ -2196,7 +2158,7 @@ void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, } // First, check for a zero value and just short circuit the logic below. - if (*this == 0) { + if (isZero()) { while (*Prefix) { Str.push_back(*Prefix); ++Prefix; @@ -2305,55 +2267,51 @@ void APInt::print(raw_ostream &OS, bool isSigned) const { static_assert(APInt::APINT_BITS_PER_WORD % 2 == 0, "Part width must be divisible by 2!"); -/* Some handy functions local to this file. */ - -/* Returns the integer part with the least significant BITS set. - BITS cannot be zero. */ +// Returns the integer part with the least significant BITS set. +// BITS cannot be zero. static inline APInt::WordType lowBitMask(unsigned bits) { assert(bits != 0 && bits <= APInt::APINT_BITS_PER_WORD); - return ~(APInt::WordType) 0 >> (APInt::APINT_BITS_PER_WORD - bits); } -/* Returns the value of the lower half of PART. */ +/// Returns the value of the lower half of PART. static inline APInt::WordType lowHalf(APInt::WordType part) { return part & lowBitMask(APInt::APINT_BITS_PER_WORD / 2); } -/* Returns the value of the upper half of PART. */ +/// Returns the value of the upper half of PART. static inline APInt::WordType highHalf(APInt::WordType part) { return part >> (APInt::APINT_BITS_PER_WORD / 2); } -/* Returns the bit number of the most significant set bit of a part. - If the input number has no bits set -1U is returned. */ +/// Returns the bit number of the most significant set bit of a part. +/// If the input number has no bits set -1U is returned. static unsigned partMSB(APInt::WordType value) { return findLastSet(value, ZB_Max); } -/* Returns the bit number of the least significant set bit of a - part. If the input number has no bits set -1U is returned. */ +/// Returns the bit number of the least significant set bit of a part. If the +/// input number has no bits set -1U is returned. static unsigned partLSB(APInt::WordType value) { return findFirstSet(value, ZB_Max); } -/* Sets the least significant part of a bignum to the input value, and - zeroes out higher parts. */ +/// Sets the least significant part of a bignum to the input value, and zeroes +/// out higher parts. void APInt::tcSet(WordType *dst, WordType part, unsigned parts) { assert(parts > 0); - dst[0] = part; for (unsigned i = 1; i < parts; i++) dst[i] = 0; } -/* Assign one bignum to another. */ +/// Assign one bignum to another. void APInt::tcAssign(WordType *dst, const WordType *src, unsigned parts) { for (unsigned i = 0; i < parts; i++) dst[i] = src[i]; } -/* Returns true if a bignum is zero, false otherwise. */ +/// Returns true if a bignum is zero, false otherwise. bool APInt::tcIsZero(const WordType *src, unsigned parts) { for (unsigned i = 0; i < parts; i++) if (src[i]) @@ -2362,28 +2320,27 @@ bool APInt::tcIsZero(const WordType *src, unsigned parts) { return true; } -/* Extract the given bit of a bignum; returns 0 or 1. */ +/// Extract the given bit of a bignum; returns 0 or 1. int APInt::tcExtractBit(const WordType *parts, unsigned bit) { return (parts[whichWord(bit)] & maskBit(bit)) != 0; } -/* Set the given bit of a bignum. */ +/// Set the given bit of a bignum. void APInt::tcSetBit(WordType *parts, unsigned bit) { parts[whichWord(bit)] |= maskBit(bit); } -/* Clears the given bit of a bignum. */ +/// Clears the given bit of a bignum. void APInt::tcClearBit(WordType *parts, unsigned bit) { parts[whichWord(bit)] &= ~maskBit(bit); } -/* Returns the bit number of the least significant set bit of a - number. If the input number has no bits set -1U is returned. */ +/// Returns the bit number of the least significant set bit of a number. If the +/// input number has no bits set -1U is returned. unsigned APInt::tcLSB(const WordType *parts, unsigned n) { for (unsigned i = 0; i < n; i++) { if (parts[i] != 0) { unsigned lsb = partLSB(parts[i]); - return lsb + i * APINT_BITS_PER_WORD; } } @@ -2391,8 +2348,8 @@ unsigned APInt::tcLSB(const WordType *parts, unsigned n) { return -1U; } -/* Returns the bit number of the most significant set bit of a number. - If the input number has no bits set -1U is returned. */ +/// Returns the bit number of the most significant set bit of a number. +/// If the input number has no bits set -1U is returned. unsigned APInt::tcMSB(const WordType *parts, unsigned n) { do { --n; @@ -2407,10 +2364,10 @@ unsigned APInt::tcMSB(const WordType *parts, unsigned n) { return -1U; } -/* Copy the bit vector of width srcBITS from SRC, starting at bit - srcLSB, to DST, of dstCOUNT parts, such that the bit srcLSB becomes - the least significant bit of DST. All high bits above srcBITS in - DST are zero-filled. */ +/// Copy the bit vector of width srcBITS from SRC, starting at bit srcLSB, to +/// DST, of dstCOUNT parts, such that the bit srcLSB becomes the least +/// significant bit of DST. All high bits above srcBITS in DST are zero-filled. +/// */ void APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src, unsigned srcBits, unsigned srcLSB) { @@ -2418,14 +2375,14 @@ APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src, assert(dstParts <= dstCount); unsigned firstSrcPart = srcLSB / APINT_BITS_PER_WORD; - tcAssign (dst, src + firstSrcPart, dstParts); + tcAssign(dst, src + firstSrcPart, dstParts); unsigned shift = srcLSB % APINT_BITS_PER_WORD; - tcShiftRight (dst, dstParts, shift); + tcShiftRight(dst, dstParts, shift); - /* We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC - in DST. If this is less that srcBits, append the rest, else - clear the high bits. */ + // We now have (dstParts * APINT_BITS_PER_WORD - shift) bits from SRC + // in DST. If this is less that srcBits, append the rest, else + // clear the high bits. unsigned n = dstParts * APINT_BITS_PER_WORD - shift; if (n < srcBits) { WordType mask = lowBitMask (srcBits - n); @@ -2436,12 +2393,12 @@ APInt::tcExtract(WordType *dst, unsigned dstCount, const WordType *src, dst[dstParts - 1] &= lowBitMask (srcBits % APINT_BITS_PER_WORD); } - /* Clear high parts. */ + // Clear high parts. while (dstParts < dstCount) dst[dstParts++] = 0; } -/* DST += RHS + C where C is zero or one. Returns the carry flag. */ +//// DST += RHS + C where C is zero or one. Returns the carry flag. APInt::WordType APInt::tcAdd(WordType *dst, const WordType *rhs, WordType c, unsigned parts) { assert(c <= 1); @@ -2476,7 +2433,7 @@ APInt::WordType APInt::tcAddPart(WordType *dst, WordType src, return 1; } -/* DST -= RHS + C where C is zero or one. Returns the carry flag. */ +/// DST -= RHS + C where C is zero or one. Returns the carry flag. APInt::WordType APInt::tcSubtract(WordType *dst, const WordType *rhs, WordType c, unsigned parts) { assert(c <= 1); @@ -2515,47 +2472,39 @@ APInt::WordType APInt::tcSubtractPart(WordType *dst, WordType src, return 1; } -/* Negate a bignum in-place. */ +/// Negate a bignum in-place. void APInt::tcNegate(WordType *dst, unsigned parts) { tcComplement(dst, parts); tcIncrement(dst, parts); } -/* DST += SRC * MULTIPLIER + CARRY if add is true - DST = SRC * MULTIPLIER + CARRY if add is false - - Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC - they must start at the same point, i.e. DST == SRC. - - If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is - returned. Otherwise DST is filled with the least significant - DSTPARTS parts of the result, and if all of the omitted higher - parts were zero return zero, otherwise overflow occurred and - return one. */ +/// DST += SRC * MULTIPLIER + CARRY if add is true +/// DST = SRC * MULTIPLIER + CARRY if add is false +/// Requires 0 <= DSTPARTS <= SRCPARTS + 1. If DST overlaps SRC +/// they must start at the same point, i.e. DST == SRC. +/// If DSTPARTS == SRCPARTS + 1 no overflow occurs and zero is +/// returned. Otherwise DST is filled with the least significant +/// DSTPARTS parts of the result, and if all of the omitted higher +/// parts were zero return zero, otherwise overflow occurred and +/// return one. int APInt::tcMultiplyPart(WordType *dst, const WordType *src, WordType multiplier, WordType carry, unsigned srcParts, unsigned dstParts, bool add) { - /* Otherwise our writes of DST kill our later reads of SRC. */ + // Otherwise our writes of DST kill our later reads of SRC. assert(dst <= src || dst >= src + srcParts); assert(dstParts <= srcParts + 1); - /* N loops; minimum of dstParts and srcParts. */ + // N loops; minimum of dstParts and srcParts. unsigned n = std::min(dstParts, srcParts); for (unsigned i = 0; i < n; i++) { - WordType low, mid, high, srcPart; - - /* [ LOW, HIGH ] = MULTIPLIER * SRC[i] + DST[i] + CARRY. - - This cannot overflow, because - - (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) - - which is less than n^2. */ - - srcPart = src[i]; - + // [LOW, HIGH] = MULTIPLIER * SRC[i] + DST[i] + CARRY. + // This cannot overflow, because: + // (n - 1) * (n - 1) + 2 (n - 1) = (n - 1) * (n + 1) + // which is less than n^2. + WordType srcPart = src[i]; + WordType low, mid, high; if (multiplier == 0 || srcPart == 0) { low = carry; high = 0; @@ -2577,14 +2526,14 @@ int APInt::tcMultiplyPart(WordType *dst, const WordType *src, high++; low += mid; - /* Now add carry. */ + // Now add carry. if (low + carry < low) high++; low += carry; } if (add) { - /* And now DST[i], and store the new low part there. */ + // And now DST[i], and store the new low part there. if (low + dst[i] < low) high++; dst[i] += low; @@ -2595,32 +2544,32 @@ int APInt::tcMultiplyPart(WordType *dst, const WordType *src, } if (srcParts < dstParts) { - /* Full multiplication, there is no overflow. */ + // Full multiplication, there is no overflow. assert(srcParts + 1 == dstParts); dst[srcParts] = carry; return 0; } - /* We overflowed if there is carry. */ + // We overflowed if there is carry. if (carry) return 1; - /* We would overflow if any significant unwritten parts would be - non-zero. This is true if any remaining src parts are non-zero - and the multiplier is non-zero. */ + // We would overflow if any significant unwritten parts would be + // non-zero. This is true if any remaining src parts are non-zero + // and the multiplier is non-zero. if (multiplier) for (unsigned i = dstParts; i < srcParts; i++) if (src[i]) return 1; - /* We fitted in the narrow destination. */ + // We fitted in the narrow destination. return 0; } -/* DST = LHS * RHS, where DST has the same width as the operands and - is filled with the least significant parts of the result. Returns - one if overflow occurred, otherwise zero. DST must be disjoint - from both operands. */ +/// DST = LHS * RHS, where DST has the same width as the operands and +/// is filled with the least significant parts of the result. Returns +/// one if overflow occurred, otherwise zero. DST must be disjoint +/// from both operands. int APInt::tcMultiply(WordType *dst, const WordType *lhs, const WordType *rhs, unsigned parts) { assert(dst != lhs && dst != rhs); @@ -2640,7 +2589,7 @@ int APInt::tcMultiply(WordType *dst, const WordType *lhs, void APInt::tcFullMultiply(WordType *dst, const WordType *lhs, const WordType *rhs, unsigned lhsParts, unsigned rhsParts) { - /* Put the narrower number on the LHS for less loops below. */ + // Put the narrower number on the LHS for less loops below. if (lhsParts > rhsParts) return tcFullMultiply (dst, rhs, lhs, rhsParts, lhsParts); @@ -2652,16 +2601,15 @@ void APInt::tcFullMultiply(WordType *dst, const WordType *lhs, tcMultiplyPart(&dst[i], rhs, lhs[i], 0, rhsParts, rhsParts + 1, true); } -/* If RHS is zero LHS and REMAINDER are left unchanged, return one. - Otherwise set LHS to LHS / RHS with the fractional part discarded, - set REMAINDER to the remainder, return zero. i.e. - - OLD_LHS = RHS * LHS + REMAINDER - - SCRATCH is a bignum of the same size as the operands and result for - use by the routine; its contents need not be initialized and are - destroyed. LHS, REMAINDER and SCRATCH must be distinct. -*/ +// If RHS is zero LHS and REMAINDER are left unchanged, return one. +// Otherwise set LHS to LHS / RHS with the fractional part discarded, +// set REMAINDER to the remainder, return zero. i.e. +// +// OLD_LHS = RHS * LHS + REMAINDER +// +// SCRATCH is a bignum of the same size as the operands and result for +// use by the routine; its contents need not be initialized and are +// destroyed. LHS, REMAINDER and SCRATCH must be distinct. int APInt::tcDivide(WordType *lhs, const WordType *rhs, WordType *remainder, WordType *srhs, unsigned parts) { @@ -2680,8 +2628,8 @@ int APInt::tcDivide(WordType *lhs, const WordType *rhs, tcAssign(remainder, lhs, parts); tcSet(lhs, 0, parts); - /* Loop, subtracting SRHS if REMAINDER is greater and adding that to - the total. */ + // Loop, subtracting SRHS if REMAINDER is greater and adding that to the + // total. for (;;) { int compare = tcCompare(remainder, srhs, parts); if (compare >= 0) { @@ -2756,31 +2704,7 @@ void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) { std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE); } -/* Bitwise and of two bignums. */ -void APInt::tcAnd(WordType *dst, const WordType *rhs, unsigned parts) { - for (unsigned i = 0; i < parts; i++) - dst[i] &= rhs[i]; -} - -/* Bitwise inclusive or of two bignums. */ -void APInt::tcOr(WordType *dst, const WordType *rhs, unsigned parts) { - for (unsigned i = 0; i < parts; i++) - dst[i] |= rhs[i]; -} - -/* Bitwise exclusive or of two bignums. */ -void APInt::tcXor(WordType *dst, const WordType *rhs, unsigned parts) { - for (unsigned i = 0; i < parts; i++) - dst[i] ^= rhs[i]; -} - -/* Complement a bignum in-place. */ -void APInt::tcComplement(WordType *dst, unsigned parts) { - for (unsigned i = 0; i < parts; i++) - dst[i] = ~dst[i]; -} - -/* Comparison (unsigned) of two bignums. */ +// Comparison (unsigned) of two bignums. int APInt::tcCompare(const WordType *lhs, const WordType *rhs, unsigned parts) { while (parts) { @@ -2792,23 +2716,6 @@ int APInt::tcCompare(const WordType *lhs, const WordType *rhs, return 0; } -/* Set the least significant BITS bits of a bignum, clear the - rest. */ -void APInt::tcSetLeastSignificantBits(WordType *dst, unsigned parts, - unsigned bits) { - unsigned i = 0; - while (bits > APINT_BITS_PER_WORD) { - dst[i++] = ~(WordType) 0; - bits -= APINT_BITS_PER_WORD; - } - - if (bits) - dst[i++] = ~(WordType) 0 >> (APINT_BITS_PER_WORD - bits); - - while (i < parts) - dst[i++] = 0; -} - APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM) { // Currently udivrem always rounds down. @@ -2819,7 +2726,7 @@ APInt llvm::APIntOps::RoundingUDiv(const APInt &A, const APInt &B, case APInt::Rounding::UP: { APInt Quo, Rem; APInt::udivrem(A, B, Quo, Rem); - if (Rem == 0) + if (Rem.isZero()) return Quo; return Quo + 1; } @@ -2834,7 +2741,7 @@ APInt llvm::APIntOps::RoundingSDiv(const APInt &A, const APInt &B, case APInt::Rounding::UP: { APInt Quo, Rem; APInt::sdivrem(A, B, Quo, Rem); - if (Rem == 0) + if (Rem.isZero()) return Quo; // This algorithm deals with arbitrary rounding mode used by sdivrem. // We want to check whether the non-integer part of the mathematical value @@ -2870,7 +2777,7 @@ llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, << "x + " << C << ", rw:" << RangeWidth << '\n'); // Identify 0 as a (non)solution immediately. - if (C.sextOrTrunc(RangeWidth).isNullValue() ) { + if (C.sextOrTrunc(RangeWidth).isZero()) { LLVM_DEBUG(dbgs() << __func__ << ": zero solution\n"); return APInt(CoeffWidth, 0); } @@ -2932,7 +2839,7 @@ llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, auto RoundUp = [] (const APInt &V, const APInt &A) -> APInt { assert(A.isStrictlyPositive()); APInt T = V.abs().urem(A); - if (T.isNullValue()) + if (T.isZero()) return V; return V.isNegative() ? V+T : V+(A-T); }; @@ -3016,7 +2923,7 @@ llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, // can be 0, but cannot be negative. assert(X.isNonNegative() && "Solution should be non-negative"); - if (!InexactSQ && Rem.isNullValue()) { + if (!InexactSQ && Rem.isZero()) { LLVM_DEBUG(dbgs() << __func__ << ": solution (root): " << X << '\n'); return X; } @@ -3032,8 +2939,8 @@ llvm::APIntOps::SolveQuadraticEquationWrap(APInt A, APInt B, APInt C, APInt VX = (A*X + B)*X + C; APInt VY = VX + TwoA*X + A + B; - bool SignChange = VX.isNegative() != VY.isNegative() || - VX.isNullValue() != VY.isNullValue(); + bool SignChange = + VX.isNegative() != VY.isNegative() || VX.isZero() != VY.isZero(); // If the sign did not change between X and X+1, X is not a valid solution. // This could happen when the actual (exact) roots don't have an integer // between them, so they would both be contained between X and X+1. @@ -3055,6 +2962,40 @@ llvm::APIntOps::GetMostSignificantDifferentBit(const APInt &A, const APInt &B) { return A.getBitWidth() - ((A ^ B).countLeadingZeros() + 1); } +APInt llvm::APIntOps::ScaleBitMask(const APInt &A, unsigned NewBitWidth) { + unsigned OldBitWidth = A.getBitWidth(); + assert((((OldBitWidth % NewBitWidth) == 0) || + ((NewBitWidth % OldBitWidth) == 0)) && + "One size should be a multiple of the other one. " + "Can't do fractional scaling."); + + // Check for matching bitwidths. + if (OldBitWidth == NewBitWidth) + return A; + + APInt NewA = APInt::getZero(NewBitWidth); + + // Check for null input. + if (A.isZero()) + return NewA; + + if (NewBitWidth > OldBitWidth) { + // Repeat bits. + unsigned Scale = NewBitWidth / OldBitWidth; + for (unsigned i = 0; i != OldBitWidth; ++i) + if (A[i]) + NewA.setBits(i * Scale, (i + 1) * Scale); + } else { + // Merge bits - if any old bit is set, then set scale equivalent new bit. + unsigned Scale = OldBitWidth / NewBitWidth; + for (unsigned i = 0; i != NewBitWidth; ++i) + if (!A.extractBits(Scale, i * Scale).isZero()) + NewA.setBit(i); + } + + return NewA; +} + /// StoreIntToMemory - Fills the StoreBytes bytes of memory starting from Dst /// with the integer held in IntVal. void llvm::StoreIntToMemory(const APInt &IntVal, uint8_t *Dst, |