X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FAPInt.cpp;h=fa929eb0a556e0054d1209192b121d66b1b070c0;hb=aebcee661e1de0ea8a21dc50891926a91ba78039;hp=1703eeae27fc4825b74c3f03352163d5fb73de78;hpb=7e2c793a2b5c746344652b6579e958ee42fafdcc;p=oota-llvm.git diff --git a/lib/Support/APInt.cpp b/lib/Support/APInt.cpp index 1703eeae27f..fa929eb0a55 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) { @@ -559,12 +560,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 @@ -692,14 +693,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; } } @@ -735,13 +736,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); } @@ -1096,7 +1097,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) { @@ -1512,7 +1513,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) { @@ -1683,10 +1684,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]; @@ -1860,7 +1861,7 @@ APInt APInt::udiv(const APInt& RHS) const { // 0 / X ===> 0 return APInt(BitWidth, 0); else if (lhsWords < rhsWords || this->ult(RHS)) { - // X / Y ===> 0, if X < Y + // X / Y ===> 0, iff X < Y return APInt(BitWidth, 0); } else if (*this == RHS) { // X / X ===> 1 @@ -1872,10 +1873,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()) { @@ -1897,7 +1909,7 @@ APInt APInt::urem(const APInt& RHS) const { // 0 % Y ===> 0 return APInt(BitWidth, 0); } else if (lhsWords < rhsWords || this->ult(RHS)) { - // X % Y ===> X, if X < Y + // X % Y ===> X, iff X < Y return *this; } else if (*this == RHS) { // X % X == 0; @@ -1909,10 +1921,21 @@ 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) { // Get some size facts about the dividend and divisor @@ -1929,8 +1952,8 @@ void APInt::udivrem(const APInt &LHS, const APInt &RHS, } if (lhsWords < rhsWords || LHS.ult(RHS)) { - Remainder = LHS; // X % Y ===> X, if X < Y - Quotient = 0; // X / Y ===> 0, if X < Y + Remainder = LHS; // X % Y ===> X, iff X < Y + Quotient = 0; // X / Y ===> 0, iff X < Y return; } @@ -1953,6 +1976,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() && @@ -2076,7 +2117,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(); } } @@ -2157,7 +2198,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('-'); } @@ -2264,24 +2305,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 @@ -2289,24 +2313,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); } } @@ -2848,6 +2855,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