X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=23f89bb66f9e562204cd136d5ed21c9ad5f414a4;hb=b3fdcb3739e80e97df1cb59f16d5d9b0fd02d4c3;hp=e5423f153c3e6733984fd9054a629bfd17cdc8e7;hpb=a185362095c0a6138216e61d4a767b930bcc7826;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index e5423f153c3..23f89bb66f9 100644 --- a/lib/Support/APInt.cpp +++ b/lib/Support/APInt.cpp @@ -12,7 +12,6 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "apint" #include "llvm/ADT/APInt.h" #include "llvm/ADT/FoldingSet.h" #include "llvm/ADT/Hashing.h" @@ -23,11 +22,13 @@ #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include -#include -#include #include +#include +#include using namespace llvm; +#define DEBUG_TYPE "apint" + /// A utility function for allocating memory, checking for allocation failures, /// and ensuring the contents are zeroed. inline static uint64_t* getClearedMemory(unsigned numWords) { @@ -161,7 +162,7 @@ APInt& APInt::operator=(uint64_t RHS) { return clearUnusedBits(); } -/// Profile - This method 'profiles' an APInt for use with FoldingSet. +/// This method 'profiles' an APInt for use with FoldingSet. void APInt::Profile(FoldingSetNodeID& ID) const { ID.AddInteger(BitWidth); @@ -175,7 +176,7 @@ void APInt::Profile(FoldingSetNodeID& ID) const { ID.AddInteger(pVal[i]); } -/// add_1 - This function adds a single "digit" integer, y, to the multiple +/// This function adds a single "digit" integer, y, to the multiple /// "digit" integer array, x[]. x[] is modified to reflect the addition and /// 1 is returned if there is a carry out, otherwise 0 is returned. /// @returns the carry of the addition. @@ -201,7 +202,7 @@ APInt& APInt::operator++() { return clearUnusedBits(); } -/// sub_1 - This function subtracts a single "digit" (64-bit word), y, from +/// This function subtracts a single "digit" (64-bit word), y, from /// the multi-digit integer array, x[], propagating the borrowed 1 value until /// no further borrowing is neeeded or it runs out of "digits" in x. The result /// is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. @@ -230,7 +231,7 @@ APInt& APInt::operator--() { return clearUnusedBits(); } -/// add - This function adds the integer array x to the integer array Y and +/// This function adds the integer array x to the integer array Y and /// places the result in dest. /// @returns the carry out from the addition /// @brief General addition of 64-bit integer arrays @@ -453,18 +454,10 @@ APInt APInt::XorSlowCase(const APInt& RHS) const { for (unsigned i = 0; i < numWords; ++i) val[i] = pVal[i] ^ RHS.pVal[i]; + APInt Result(val, getBitWidth()); // 0^0==1 so clear the high bits in case they got set. - return APInt(val, getBitWidth()).clearUnusedBits(); -} - -bool APInt::operator !() const { - if (isSingleWord()) - return !VAL; - - for (unsigned i = 0; i < getNumWords(); ++i) - if (pVal[i]) - return false; - return true; + Result.clearUnusedBits(); + return Result; } APInt APInt::operator*(const APInt& RHS) const { @@ -482,7 +475,8 @@ APInt APInt::operator+(const APInt& RHS) const { return APInt(BitWidth, VAL + RHS.VAL); APInt Result(BitWidth, 0); add(Result.pVal, this->pVal, RHS.pVal, getNumWords()); - return Result.clearUnusedBits(); + Result.clearUnusedBits(); + return Result; } APInt APInt::operator-(const APInt& RHS) const { @@ -491,13 +485,8 @@ APInt APInt::operator-(const APInt& RHS) const { return APInt(BitWidth, VAL - RHS.VAL); APInt Result(BitWidth, 0); sub(Result.pVal, this->pVal, RHS.pVal, getNumWords()); - return Result.clearUnusedBits(); -} - -bool APInt::operator[](unsigned bitPosition) const { - assert(bitPosition < getBitWidth() && "Bit position out of bounds!"); - return (maskBit(bitPosition) & - (isSingleWord() ? VAL : pVal[whichWord(bitPosition)])) != 0; + Result.clearUnusedBits(); + return Result; } bool APInt::EqualSlowCase(const APInt& RHS) const { @@ -575,12 +564,12 @@ bool APInt::slt(const APInt& RHS) const { if (lhsNeg) { // Sign bit is set so perform two's complement to make it positive lhs.flipAllBits(); - lhs++; + ++lhs; } if (rhsNeg) { // Sign bit is set so perform two's complement to make it positive rhs.flipAllBits(); - rhs++; + ++rhs; } // Now we have unsigned values to compare so do the comparison if necessary @@ -683,12 +672,20 @@ hash_code llvm::hash_value(const APInt &Arg) { return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords()); } -/// HiBits - This function returns the high "numBits" bits of this APInt. +bool APInt::isSplat(unsigned SplatSizeInBits) const { + assert(getBitWidth() % SplatSizeInBits == 0 && + "SplatSizeInBits must divide width!"); + // We can check that all parts of an integer are equal by making use of a + // little trick: rotate and check if it's still the same value. + return *this == rotl(SplatSizeInBits); +} + +/// This function returns the high "numBits" bits of this APInt. APInt APInt::getHiBits(unsigned numBits) const { return APIntOps::lshr(*this, BitWidth - numBits); } -/// LoBits - This function returns the low "numBits" bits of this APInt. +/// This function returns the low "numBits" bits of this APInt. APInt APInt::getLoBits(unsigned numBits) const { return APIntOps::lshr(APIntOps::shl(*this, BitWidth - numBits), BitWidth - numBits); @@ -708,14 +705,14 @@ unsigned APInt::countLeadingZerosSlowCase() const { unsigned i = getNumWords(); integerPart MSW = pVal[i-1] & MSWMask; if (MSW) - return CountLeadingZeros_64(MSW) - (APINT_BITS_PER_WORD - BitsInMSW); + return llvm::countLeadingZeros(MSW) - (APINT_BITS_PER_WORD - BitsInMSW); unsigned Count = BitsInMSW; for (--i; i > 0u; --i) { if (pVal[i-1] == 0) Count += APINT_BITS_PER_WORD; else { - Count += CountLeadingZeros_64(pVal[i-1]); + Count += llvm::countLeadingZeros(pVal[i-1]); break; } } @@ -724,7 +721,7 @@ unsigned APInt::countLeadingZerosSlowCase() const { unsigned APInt::countLeadingOnes() const { if (isSingleWord()) - return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth)); + return llvm::countLeadingOnes(VAL << (APINT_BITS_PER_WORD - BitWidth)); unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD; unsigned shift; @@ -735,13 +732,13 @@ unsigned APInt::countLeadingOnes() const { shift = APINT_BITS_PER_WORD - highWordBits; } int i = getNumWords() - 1; - unsigned Count = CountLeadingOnes_64(pVal[i] << shift); + unsigned Count = llvm::countLeadingOnes(pVal[i] << shift); if (Count == highWordBits) { for (i--; i >= 0; --i) { if (pVal[i] == -1ULL) Count += APINT_BITS_PER_WORD; else { - Count += CountLeadingOnes_64(pVal[i]); + Count += llvm::countLeadingOnes(pVal[i]); break; } } @@ -751,13 +748,13 @@ unsigned APInt::countLeadingOnes() const { unsigned APInt::countTrailingZeros() const { if (isSingleWord()) - return std::min(unsigned(CountTrailingZeros_64(VAL)), BitWidth); + return std::min(unsigned(llvm::countTrailingZeros(VAL)), BitWidth); unsigned Count = 0; unsigned i = 0; for (; i < getNumWords() && pVal[i] == 0; ++i) Count += APINT_BITS_PER_WORD; if (i < getNumWords()) - Count += CountTrailingZeros_64(pVal[i]); + Count += llvm::countTrailingZeros(pVal[i]); return std::min(Count, BitWidth); } @@ -767,14 +764,14 @@ unsigned APInt::countTrailingOnesSlowCase() const { for (; i < getNumWords() && pVal[i] == -1ULL; ++i) Count += APINT_BITS_PER_WORD; if (i < getNumWords()) - Count += CountTrailingOnes_64(pVal[i]); + Count += llvm::countTrailingOnes(pVal[i]); return std::min(Count, BitWidth); } unsigned APInt::countPopulationSlowCase() const { unsigned Count = 0; for (unsigned i = 0; i < getNumWords(); ++i) - Count += CountPopulation_64(pVal[i]); + Count += llvm::countPopulation(pVal[i]); return Count; } @@ -864,7 +861,7 @@ APInt llvm::APIntOps::RoundDoubleToAPInt(double Double, unsigned width) { return isNeg ? -Tmp : Tmp; } -/// RoundToDouble - This function converts this APInt to a double. +/// This function converts this APInt to a double. /// The layout for double is as following (IEEE Standard 754): /// -------------------------------------- /// | Sign Exponent Fraction Bias | @@ -1112,7 +1109,7 @@ APInt APInt::ashr(unsigned shiftAmt) const { // to include in this word. val[breakWord] = pVal[breakWord+offset] >> wordShift; - // Deal with sign extenstion in the break word, and possibly the word before + // Deal with sign extension in the break word, and possibly the word before // it. if (isNegative()) { if (wordShift > bitsInWord) { @@ -1129,7 +1126,9 @@ APInt APInt::ashr(unsigned shiftAmt) const { uint64_t fillValue = (isNegative() ? -1ULL : 0); for (unsigned i = breakWord+1; i < getNumWords(); ++i) val[i] = fillValue; - return APInt(val, BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } /// Logical right-shift this APInt by shiftAmt. @@ -1151,7 +1150,7 @@ APInt APInt::lshr(unsigned shiftAmt) const { // If all the bits were shifted out, the result is 0. This avoids issues // with shifting by the size of the integer type, which produces undefined // results. We define these "undefined results" to always be 0. - if (shiftAmt == BitWidth) + if (shiftAmt >= BitWidth) return APInt(BitWidth, 0); // If none of the bits are shifted out, the result is *this. This avoids @@ -1166,7 +1165,9 @@ APInt APInt::lshr(unsigned shiftAmt) const { // If we are shifting less than a word, compute the shift with a simple carry if (shiftAmt < APINT_BITS_PER_WORD) { lshrNear(val, pVal, getNumWords(), shiftAmt); - return APInt(val, BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } // Compute some values needed by the remaining shift algorithms @@ -1179,7 +1180,9 @@ APInt APInt::lshr(unsigned shiftAmt) const { val[i] = pVal[i+offset]; for (unsigned i = getNumWords()-offset; i < getNumWords(); i++) val[i] = 0; - return APInt(val,BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } // Shift the low order words @@ -1193,7 +1196,9 @@ APInt APInt::lshr(unsigned shiftAmt) const { // Remaining words are 0 for (unsigned i = breakWord+1; i < getNumWords(); ++i) val[i] = 0; - return APInt(val, BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } /// Left-shift this APInt by shiftAmt. @@ -1226,7 +1231,9 @@ APInt APInt::shlSlowCase(unsigned shiftAmt) const { val[i] = pVal[i] << shiftAmt | carry; carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); } - return APInt(val, BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } // Compute some values needed by the remaining shift algorithms @@ -1239,7 +1246,9 @@ APInt APInt::shlSlowCase(unsigned shiftAmt) const { val[i] = 0; for (unsigned i = offset; i < getNumWords(); i++) val[i] = pVal[i-offset]; - return APInt(val,BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } // Copy whole words from this to Result. @@ -1250,7 +1259,9 @@ APInt APInt::shlSlowCase(unsigned shiftAmt) const { val[offset] = pVal[0] << wordShift; for (i = 0; i < offset; ++i) val[i] = 0; - return APInt(val, BitWidth).clearUnusedBits(); + APInt Result(val, BitWidth); + Result.clearUnusedBits(); + return Result; } APInt APInt::rotl(const APInt &rotateAmt) const { @@ -1307,18 +1318,13 @@ APInt APInt::sqrt() const { // libc sqrt function which will probably use a hardware sqrt computation. // This should be faster than the algorithm below. if (magnitude < 52) { -#if HAVE_ROUND return APInt(BitWidth, uint64_t(::round(::sqrt(double(isSingleWord()?VAL:pVal[0]))))); -#else - return APInt(BitWidth, - uint64_t(::sqrt(double(isSingleWord()?VAL:pVal[0])) + 0.5)); -#endif } // Okay, all the short cuts are exhausted. We must compute it. The following // is a classical Babylonian method for computing the square root. This code - // was adapted to APINt from a wikipedia article on such computations. + // was adapted to APInt from a wikipedia article on such computations. // See http://www.wikipedia.org/ and go to the page named // Calculate_an_integer_square_root. unsigned nbits = BitWidth, i = 4; @@ -1462,7 +1468,7 @@ APInt::mu APInt::magicu(unsigned LeadingZeros) const { APInt signedMin = APInt::getSignedMinValue(d.getBitWidth()); APInt signedMax = APInt::getSignedMaxValue(d.getBitWidth()); - nc = allOnes - (-d).urem(d); + 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) @@ -1505,21 +1511,18 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, assert(u && "Must provide dividend"); assert(v && "Must provide divisor"); assert(q && "Must provide quotient"); - assert(u != v && u != q && v != q && "Must us different memory"); + assert(u != v && u != q && v != q && "Must use different memory"); assert(n>1 && "n must be > 1"); - // Knuth uses the value b as the base of the number system. In our case b - // is 2^31 so we just set it to -1u. - uint64_t b = uint64_t(1) << 32; + // b denotes the base of the number system. In our case b is 2^32. + LLVM_CONSTEXPR uint64_t b = uint64_t(1) << 32; -#if 0 DEBUG(dbgs() << "KnuthDiv: m=" << m << " n=" << n << '\n'); DEBUG(dbgs() << "KnuthDiv: original:"); DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); DEBUG(dbgs() << " by"); DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); DEBUG(dbgs() << '\n'); -#endif // D1. [Normalize.] Set d = b / (v[n-1] + 1) and multiply all the digits of // u and v by d. Note that we have taken Knuth's advice here to use a power // of 2 value for d such that d * v[n-1] >= b/2 (b is the base). A power of @@ -1528,7 +1531,7 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, // and v so that its high bits are shifted to the top of v's range without // overflow. Note that this can require an extra word in u so that u must // be of length m+n+1. - unsigned shift = CountLeadingZeros_32(v[n-1]); + unsigned shift = countLeadingZeros(v[n-1]); unsigned v_carry = 0; unsigned u_carry = 0; if (shift) { @@ -1544,13 +1547,12 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, } } u[m+n] = u_carry; -#if 0 + DEBUG(dbgs() << "KnuthDiv: normal:"); DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); DEBUG(dbgs() << " by"); DEBUG(for (int i = n; i >0; i--) dbgs() << " " << v[i-1]); DEBUG(dbgs() << '\n'); -#endif // D2. [Initialize j.] Set j to m. This is the loop counter over the places. int j = m; @@ -1580,44 +1582,23 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, // (u[j+n]u[j+n-1]..u[j]) - qp * (v[n-1]...v[1]v[0]). This computation // consists of a simple multiplication by a one-place number, combined with // a subtraction. - bool isNeg = false; - for (unsigned i = 0; i < n; ++i) { - uint64_t u_tmp = uint64_t(u[j+i]) | (uint64_t(u[j+i+1]) << 32); - uint64_t subtrahend = uint64_t(qp) * uint64_t(v[i]); - bool borrow = subtrahend > u_tmp; - DEBUG(dbgs() << "KnuthDiv: u_tmp == " << u_tmp - << ", subtrahend == " << subtrahend - << ", borrow = " << borrow << '\n'); - - uint64_t result = u_tmp - subtrahend; - unsigned k = j + i; - u[k++] = (unsigned)(result & (b-1)); // subtract low word - u[k++] = (unsigned)(result >> 32); // subtract high word - while (borrow && k <= m+n) { // deal with borrow to the left - borrow = u[k] == 0; - u[k]--; - k++; - } - isNeg |= borrow; - DEBUG(dbgs() << "KnuthDiv: u[j+i] == " << u[j+i] << ", u[j+i+1] == " << - u[j+i+1] << '\n'); - } - DEBUG(dbgs() << "KnuthDiv: after subtraction:"); - DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); - DEBUG(dbgs() << '\n'); // The digits (u[j+n]...u[j]) should be kept positive; if the result of // this step is actually negative, (u[j+n]...u[j]) should be left as the // true value plus b**(n+1), namely as the b's complement of // the true value, and a "borrow" to the left should be remembered. - // - if (isNeg) { - bool carry = true; // true because b's complement is "complement + 1" - for (unsigned i = 0; i <= m+n; ++i) { - u[i] = ~u[i] + carry; // b's complement - carry = carry && u[i] == 0; - } + int64_t borrow = 0; + for (unsigned i = 0; i < n; ++i) { + uint64_t p = uint64_t(qp) * uint64_t(v[i]); + int64_t subres = int64_t(u[j+i]) - borrow - (unsigned)p; + u[j+i] = (unsigned)subres; + borrow = (p >> 32) - (subres >> 32); + DEBUG(dbgs() << "KnuthDiv: u[j+i] = " << u[j+i] + << ", borrow = " << borrow << '\n'); } - DEBUG(dbgs() << "KnuthDiv: after complement:"); + bool isNeg = u[j+n] < borrow; + u[j+n] -= (unsigned)borrow; + + DEBUG(dbgs() << "KnuthDiv: after subtraction:"); DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); DEBUG(dbgs() << '\n'); @@ -1641,7 +1622,7 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, u[j+n] += carry; } DEBUG(dbgs() << "KnuthDiv: after correction:"); - DEBUG(for (int i = m+n; i >=0; i--) dbgs() <<" " << u[i]); + DEBUG(for (int i = m+n; i >=0; i--) dbgs() << " " << u[i]); DEBUG(dbgs() << "\nKnuthDiv: digit result = " << q[j] << '\n'); // D7. [Loop on j.] Decrease j by one. Now if j >= 0, go back to D3. @@ -1674,9 +1655,7 @@ static void KnuthDiv(unsigned *u, unsigned *v, unsigned *q, unsigned* r, } DEBUG(dbgs() << '\n'); } -#if 0 DEBUG(dbgs() << '\n'); -#endif } void APInt::divide(const APInt LHS, unsigned lhsWords, @@ -1699,10 +1678,10 @@ void APInt::divide(const APInt LHS, unsigned lhsWords, // Allocate space for the temporary values we need either on the stack, if // it will fit, or on the heap if it won't. unsigned SPACE[128]; - unsigned *U = 0; - unsigned *V = 0; - unsigned *Q = 0; - unsigned *R = 0; + unsigned *U = nullptr; + unsigned *V = nullptr; + unsigned *Q = nullptr; + unsigned *R = nullptr; if ((Remainder?4:3)*n+2*m+1 <= 128) { U = &SPACE[0]; V = &SPACE[m+n+1]; @@ -1800,6 +1779,8 @@ void APInt::divide(const APInt LHS, unsigned lhsWords, // The quotient is in Q. Reconstitute the quotient into Quotient's low // order words. + // This case is currently dead as all users of divide() handle trivial cases + // earlier. if (lhsWords == 1) { uint64_t tmp = uint64_t(Q[0]) | (uint64_t(Q[1]) << (APINT_BITS_PER_WORD / 2)); @@ -1888,10 +1869,21 @@ APInt APInt::udiv(const APInt& RHS) const { // We have to compute it the hard way. Invoke the Knuth divide algorithm. APInt Quotient(1,0); // to hold result. - divide(*this, lhsWords, RHS, rhsWords, &Quotient, 0); + divide(*this, lhsWords, RHS, rhsWords, &Quotient, nullptr); return Quotient; } +APInt APInt::sdiv(const APInt &RHS) const { + if (isNegative()) { + if (RHS.isNegative()) + return (-(*this)).udiv(-RHS); + return -((-(*this)).udiv(RHS)); + } + if (RHS.isNegative()) + return -(this->udiv(-RHS)); + return this->udiv(RHS); +} + APInt APInt::urem(const APInt& RHS) const { assert(BitWidth == RHS.BitWidth && "Bit widths must be the same"); if (isSingleWord()) { @@ -1925,12 +1917,35 @@ APInt APInt::urem(const APInt& RHS) const { // We have to compute it the hard way. Invoke the Knuth divide algorithm. APInt Remainder(1,0); - divide(*this, lhsWords, RHS, rhsWords, 0, &Remainder); + divide(*this, lhsWords, RHS, rhsWords, nullptr, &Remainder); return Remainder; } +APInt APInt::srem(const APInt &RHS) const { + if (isNegative()) { + if (RHS.isNegative()) + return -((-(*this)).urem(-RHS)); + return -((-(*this)).urem(RHS)); + } + if (RHS.isNegative()) + return this->urem(-RHS); + return this->urem(RHS); +} + void APInt::udivrem(const APInt &LHS, const APInt &RHS, APInt &Quotient, APInt &Remainder) { + assert(LHS.BitWidth == RHS.BitWidth && "Bit widths must be the same"); + + // First, deal with the easy case + if (LHS.isSingleWord()) { + assert(RHS.VAL != 0 && "Divide by zero?"); + uint64_t QuotVal = LHS.VAL / RHS.VAL; + uint64_t RemVal = LHS.VAL % RHS.VAL; + Quotient = APInt(LHS.BitWidth, QuotVal); + Remainder = APInt(LHS.BitWidth, RemVal); + return; + } + // Get some size facts about the dividend and divisor unsigned lhsBits = LHS.getActiveBits(); unsigned lhsWords = !lhsBits ? 0 : (APInt::whichWord(lhsBits - 1) + 1); @@ -1969,6 +1984,24 @@ void APInt::udivrem(const APInt &LHS, const APInt &RHS, divide(LHS, lhsWords, RHS, rhsWords, &Quotient, &Remainder); } +void APInt::sdivrem(const APInt &LHS, const APInt &RHS, + APInt &Quotient, APInt &Remainder) { + if (LHS.isNegative()) { + if (RHS.isNegative()) + APInt::udivrem(-LHS, -RHS, Quotient, Remainder); + else { + APInt::udivrem(-LHS, RHS, Quotient, Remainder); + Quotient = -Quotient; + } + Remainder = -Remainder; + } else if (RHS.isNegative()) { + APInt::udivrem(LHS, -RHS, Quotient, Remainder); + Quotient = -Quotient; + } else { + APInt::udivrem(LHS, RHS, Quotient, Remainder); + } +} + APInt APInt::sadd_ov(const APInt &RHS, bool &Overflow) const { APInt Res = *this+RHS; Overflow = isNonNegative() == RHS.isNonNegative() && @@ -2021,19 +2054,29 @@ APInt APInt::umul_ov(const APInt &RHS, bool &Overflow) const { return Res; } -APInt APInt::sshl_ov(unsigned ShAmt, bool &Overflow) const { - Overflow = ShAmt >= getBitWidth(); +APInt APInt::sshl_ov(const APInt &ShAmt, bool &Overflow) const { + Overflow = ShAmt.uge(getBitWidth()); if (Overflow) - ShAmt = getBitWidth()-1; + return APInt(BitWidth, 0); if (isNonNegative()) // Don't allow sign change. - Overflow = ShAmt >= countLeadingZeros(); + Overflow = ShAmt.uge(countLeadingZeros()); else - Overflow = ShAmt >= countLeadingOnes(); + Overflow = ShAmt.uge(countLeadingOnes()); return *this << ShAmt; } +APInt APInt::ushl_ov(const APInt &ShAmt, bool &Overflow) const { + Overflow = ShAmt.uge(getBitWidth()); + if (Overflow) + return APInt(BitWidth, 0); + + Overflow = ShAmt.ugt(countLeadingZeros()); + + return *this << ShAmt; +} + @@ -2092,7 +2135,7 @@ void APInt::fromString(unsigned numbits, StringRef str, uint8_t radix) { } // If its negative, put it in two's complement form if (isNeg) { - (*this)--; + --(*this); this->flipAllBits(); } } @@ -2173,7 +2216,7 @@ void APInt::toString(SmallVectorImpl &Str, unsigned Radix, // Flip the bits and add one to turn it into the equivalent positive // value and put a '-' in the result. Tmp.flipAllBits(); - Tmp++; + ++Tmp; Str.push_back('-'); } @@ -2216,9 +2259,8 @@ void APInt::toString(SmallVectorImpl &Str, unsigned Radix, std::reverse(Str.begin()+StartDig, Str.end()); } -/// toString - This returns the APInt as a std::string. Note that this is an -/// inefficient method. It is better to pass in a SmallVector/SmallString -/// to the methods above. +/// Returns the APInt as a std::string. Note that this is an inefficient method. +/// It is better to pass in a SmallVector/SmallString to the methods above. std::string APInt::toString(unsigned Radix = 10, bool Signed = true) const { SmallString<40> S; toString(S, Radix, Signed, /* formatAsCLiteral = */false); @@ -2231,13 +2273,13 @@ void APInt::dump() const { this->toStringUnsigned(U); this->toStringSigned(S); dbgs() << "APInt(" << BitWidth << "b, " - << U.str() << "u " << S.str() << "s)"; + << U << "u " << S << "s)"; } void APInt::print(raw_ostream &OS, bool isSigned) const { SmallString<40> S; this->toString(S, 10, isSigned, /* formatAsCLiteral = */false); - OS << S.str(); + OS << S; } // This implements a variety of operations on a representation of @@ -2245,8 +2287,7 @@ void APInt::print(raw_ostream &OS, bool isSigned) const { // Assumed by lowHalf, highHalf, partMSB and partLSB. A fairly safe // and unrestricting assumption. -#define COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1] -COMPILE_TIME_ASSERT(integerPartWidth % 2 == 0); +static_assert(integerPartWidth % 2 == 0, "Part width must be divisible by 2!"); /* Some handy functions local to this file. */ namespace { @@ -2280,24 +2321,7 @@ namespace { static unsigned int partMSB(integerPart value) { - unsigned int n, msb; - - if (value == 0) - return -1U; - - n = integerPartWidth / 2; - - msb = 0; - do { - if (value >> n) { - value >>= n; - msb += n; - } - - n >>= 1; - } while (n); - - return msb; + return findLastSet(value, ZB_Max); } /* Returns the bit number of the least significant set bit of a @@ -2305,24 +2329,7 @@ namespace { static unsigned int partLSB(integerPart value) { - unsigned int n, lsb; - - if (value == 0) - return -1U; - - lsb = integerPartWidth - 1; - n = integerPartWidth / 2; - - do { - if (value << n) { - value <<= n; - lsb -= n; - } - - n >>= 1; - } while (n); - - return lsb; + return findFirstSet(value, ZB_Max); } } @@ -2864,6 +2871,20 @@ APInt::tcIncrement(integerPart *dst, unsigned int parts) return i == parts; } +/* Decrement a bignum in-place, return the borrow flag. */ +integerPart +APInt::tcDecrement(integerPart *dst, unsigned int parts) { + for (unsigned int i = 0; i < parts; i++) { + // If the current word is non-zero, then the decrement has no effect on the + // higher-order words of the integer and no borrow can occur. Exit early. + if (dst[i]--) + return 0; + } + // If every word was zero, then there is a borrow. + return 1; +} + + /* Set the least significant BITS bits of a bignum, clear the rest. */ void