//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "apint"
#include "llvm/ADT/APInt.h"
-#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/Hashing.h"
#include "llvm/ADT/SmallString.h"
+#include "llvm/ADT/StringRef.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <cmath>
-#include <limits>
-#include <cstring>
#include <cstdlib>
+#include <cstring>
+#include <limits>
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) {
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 {
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 {
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 {
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
}
}
-// From http://www.burtleburtle.net, byBob Jenkins.
-// When targeting x86, both GCC and LLVM seem to recognize this as a
-// rotate instruction.
-#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
-
-// From http://www.burtleburtle.net, by Bob Jenkins.
-#define mix(a,b,c) \
- { \
- a -= c; a ^= rot(c, 4); c += b; \
- b -= a; b ^= rot(a, 6); a += c; \
- c -= b; c ^= rot(b, 8); b += a; \
- a -= c; a ^= rot(c,16); c += b; \
- b -= a; b ^= rot(a,19); a += c; \
- c -= b; c ^= rot(b, 4); b += a; \
- }
-
-// From http://www.burtleburtle.net, by Bob Jenkins.
-#define final(a,b,c) \
- { \
- c ^= b; c -= rot(b,14); \
- a ^= c; a -= rot(c,11); \
- b ^= a; b -= rot(a,25); \
- c ^= b; c -= rot(b,16); \
- a ^= c; a -= rot(c,4); \
- b ^= a; b -= rot(a,14); \
- c ^= b; c -= rot(b,24); \
- }
-
-// hashword() was adapted from http://www.burtleburtle.net, by Bob
-// Jenkins. k is a pointer to an array of uint32_t values; length is
-// the length of the key, in 32-bit chunks. This version only handles
-// keys that are a multiple of 32 bits in size.
-static inline uint32_t hashword(const uint64_t *k64, size_t length)
-{
- const uint32_t *k = reinterpret_cast<const uint32_t *>(k64);
- uint32_t a,b,c;
-
- /* Set up the internal state */
- a = b = c = 0xdeadbeef + (((uint32_t)length)<<2);
-
- /*------------------------------------------------- handle most of the key */
- while (length > 3) {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- length -= 3;
- k += 3;
- }
-
- /*------------------------------------------- handle the last 3 uint32_t's */
- switch (length) { /* all the case statements fall through */
- case 3 : c+=k[2];
- case 2 : b+=k[1];
- case 1 : a+=k[0];
- final(a,b,c);
- case 0: /* case 0: nothing left to add */
- break;
- }
- /*------------------------------------------------------ report the result */
- return c;
-}
-
-// hashword8() was adapted from http://www.burtleburtle.net, by Bob
-// Jenkins. This computes a 32-bit hash from one 64-bit word. When
-// targeting x86 (32 or 64 bit), both LLVM and GCC compile this
-// function into about 35 instructions when inlined.
-static inline uint32_t hashword8(const uint64_t k64)
-{
- uint32_t a,b,c;
- a = b = c = 0xdeadbeef + 4;
- b += k64 >> 32;
- a += k64 & 0xffffffff;
- final(a,b,c);
- return c;
-}
-#undef final
-#undef mix
-#undef rot
+hash_code llvm::hash_value(const APInt &Arg) {
+ if (Arg.isSingleWord())
+ return hash_combine(Arg.VAL);
-uint64_t APInt::getHashValue() const {
- uint64_t hash;
- if (isSingleWord())
- hash = hashword8(VAL);
- else
- hash = hashword(pVal, getNumWords()*2);
- return hash;
+ return hash_combine_range(Arg.pVal, Arg.pVal + Arg.getNumWords());
}
/// HiBits - This function returns the high "numBits" bits of this APInt.
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;
}
}
return Count;
}
-static unsigned countLeadingOnes_64(uint64_t V, unsigned skip) {
- unsigned Count = 0;
- if (skip)
- V <<= skip;
- while (V && (V & (1ULL << 63))) {
- Count++;
- V <<= 1;
- }
- return Count;
-}
-
unsigned APInt::countLeadingOnes() const {
if (isSingleWord())
- return countLeadingOnes_64(VAL, APINT_BITS_PER_WORD - BitWidth);
+ return CountLeadingOnes_64(VAL << (APINT_BITS_PER_WORD - BitWidth));
unsigned highWordBits = BitWidth % APINT_BITS_PER_WORD;
unsigned shift;
shift = APINT_BITS_PER_WORD - highWordBits;
}
int i = getNumWords() - 1;
- unsigned Count = countLeadingOnes_64(pVal[i], shift);
+ unsigned Count = CountLeadingOnes_64(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], 0);
+ Count += CountLeadingOnes_64(pVal[i]);
break;
}
}
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);
}
// 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) {
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.
// 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
// 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
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
// 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.
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
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.
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 {
// 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;
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)
// 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) {
// 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];
// 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()) {
// 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
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() &&
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;
+}
+
}
// If its negative, put it in two's complement form
if (isNeg) {
- (*this)--;
+ --(*this);
this->flipAllBits();
}
}
// 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('-');
}
// 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 {
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
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);
}
}
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
projects / oota-llvm.git / blobdiff