diff options
Diffstat (limited to 'contrib/llvm/lib/Support/APInt.cpp')
-rw-r--r-- | contrib/llvm/lib/Support/APInt.cpp | 256 |
1 files changed, 77 insertions, 179 deletions
diff --git a/contrib/llvm/lib/Support/APInt.cpp b/contrib/llvm/lib/Support/APInt.cpp index 0c7da1dad0d2..2d049a1cff85 100644 --- a/contrib/llvm/lib/Support/APInt.cpp +++ b/contrib/llvm/lib/Support/APInt.cpp @@ -125,16 +125,16 @@ APInt::APInt(unsigned numbits, StringRef Str, uint8_t radix) fromString(numbits, Str, radix); } -APInt& APInt::AssignSlowCase(const APInt& RHS) { +void APInt::AssignSlowCase(const APInt& RHS) { // Don't do anything for X = X if (this == &RHS) - return *this; + return; if (BitWidth == RHS.getBitWidth()) { // assume same bit-width single-word case is already handled assert(!isSingleWord()); memcpy(pVal, RHS.pVal, getNumWords() * APINT_WORD_SIZE); - return *this; + return; } if (isSingleWord()) { @@ -154,7 +154,7 @@ APInt& APInt::AssignSlowCase(const APInt& RHS) { memcpy(pVal, RHS.pVal, RHS.getNumWords() * APINT_WORD_SIZE); } BitWidth = RHS.BitWidth; - return clearUnusedBits(); + clearUnusedBits(); } /// This method 'profiles' an APInt for use with FoldingSet. @@ -339,19 +339,16 @@ APInt& APInt::operator*=(const APInt& RHS) { return *this; } -APInt& APInt::AndAssignSlowCase(const APInt& RHS) { +void APInt::AndAssignSlowCase(const APInt& RHS) { tcAnd(pVal, RHS.pVal, getNumWords()); - return *this; } -APInt& APInt::OrAssignSlowCase(const APInt& RHS) { +void APInt::OrAssignSlowCase(const APInt& RHS) { tcOr(pVal, RHS.pVal, getNumWords()); - return *this; } -APInt& APInt::XorAssignSlowCase(const APInt& RHS) { +void APInt::XorAssignSlowCase(const APInt& RHS) { tcXor(pVal, RHS.pVal, getNumWords()); - return *this; } APInt APInt::operator*(const APInt& RHS) const { @@ -367,14 +364,6 @@ bool APInt::EqualSlowCase(const APInt& RHS) const { return std::equal(pVal, pVal + getNumWords(), RHS.pVal); } -bool APInt::EqualSlowCase(uint64_t Val) const { - unsigned n = getActiveBits(); - if (n <= APINT_BITS_PER_WORD) - return pVal[0] == Val; - else - return false; -} - bool APInt::ult(const APInt& RHS) const { assert(BitWidth == RHS.BitWidth && "Bit widths must be same for comparison"); if (isSingleWord()) @@ -733,6 +722,22 @@ unsigned APInt::countPopulationSlowCase() const { return Count; } +bool APInt::intersectsSlowCase(const APInt &RHS) const { + for (unsigned i = 0, e = getNumWords(); i != e; ++i) + if ((pVal[i] & RHS.pVal[i]) != 0) + return true; + + return false; +} + +bool APInt::isSubsetOfSlowCase(const APInt &RHS) const { + for (unsigned i = 0, e = getNumWords(); i != e; ++i) + if ((pVal[i] & ~RHS.pVal[i]) != 0) + return false; + + return true; +} + APInt APInt::byteSwap() const { assert(BitWidth >= 16 && BitWidth % 16 == 0 && "Cannot byteswap!"); if (BitWidth == 16) @@ -774,14 +779,12 @@ APInt APInt::reverseBits() const { } APInt Val(*this); - APInt Reversed(*this); - int S = BitWidth - 1; - - const APInt One(BitWidth, 1); + APInt Reversed(BitWidth, 0); + unsigned S = BitWidth; - for ((Val = Val.lshr(1)); Val != 0; (Val = Val.lshr(1))) { + for (; Val != 0; Val.lshrInPlace(1)) { Reversed <<= 1; - Reversed |= (Val & One); + Reversed |= Val[0]; --S; } @@ -1136,63 +1139,14 @@ APInt APInt::ashr(unsigned shiftAmt) const { /// Logical right-shift this APInt by shiftAmt. /// @brief Logical right-shift function. -APInt APInt::lshr(const APInt &shiftAmt) const { - return lshr((unsigned)shiftAmt.getLimitedValue(BitWidth)); -} - -/// Perform a logical right-shift from Src to Dst of Words words, by Shift, -/// which must be less than 64. If the source and destination ranges overlap, -/// we require that Src >= Dst (put another way, we require that the overall -/// operation is a right shift on the combined range). -static void lshrWords(APInt::WordType *Dst, APInt::WordType *Src, - unsigned Words, unsigned Shift) { - assert(Shift < APInt::APINT_BITS_PER_WORD); - - if (!Words) - return; - - if (Shift == 0) { - std::memmove(Dst, Src, Words * APInt::APINT_WORD_SIZE); - return; - } - - uint64_t Low = Src[0]; - for (unsigned I = 1; I != Words; ++I) { - uint64_t High = Src[I]; - Dst[I - 1] = - (Low >> Shift) | (High << (APInt::APINT_BITS_PER_WORD - Shift)); - Low = High; - } - Dst[Words - 1] = Low >> Shift; +void APInt::lshrInPlace(const APInt &shiftAmt) { + lshrInPlace((unsigned)shiftAmt.getLimitedValue(BitWidth)); } /// Logical right-shift this APInt by shiftAmt. /// @brief Logical right-shift function. -void APInt::lshrInPlace(unsigned shiftAmt) { - if (isSingleWord()) { - if (shiftAmt >= BitWidth) - VAL = 0; - else - VAL >>= shiftAmt; - return; - } - - // Don't bother performing a no-op shift. - if (!shiftAmt) - return; - - // Find number of complete words being shifted out and zeroed. - const unsigned Words = getNumWords(); - const unsigned ShiftFullWords = - std::min(shiftAmt / APINT_BITS_PER_WORD, Words); - - // Fill in first Words - ShiftFullWords by shifting. - lshrWords(pVal, pVal + ShiftFullWords, Words - ShiftFullWords, - shiftAmt % APINT_BITS_PER_WORD); - - // The remaining high words are all zero. - for (unsigned I = Words - ShiftFullWords; I != Words; ++I) - pVal[I] = 0; +void APInt::lshrSlowCase(unsigned ShiftAmt) { + tcShiftRight(pVal, getNumWords(), ShiftAmt); } /// Left-shift this APInt by shiftAmt. @@ -1202,60 +1156,9 @@ APInt APInt::shl(const APInt &shiftAmt) const { return shl((unsigned)shiftAmt.getLimitedValue(BitWidth)); } -APInt APInt::shlSlowCase(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) - return APInt(BitWidth, 0); - - // If none of the bits are shifted out, the result is *this. This avoids a - // lshr by the words size in the loop below which can produce incorrect - // results. It also avoids the expensive computation below for a common case. - if (shiftAmt == 0) - return *this; - - // Create some space for the result. - uint64_t * val = new uint64_t[getNumWords()]; - - // If we are shifting less than a word, do it the easy way - if (shiftAmt < APINT_BITS_PER_WORD) { - uint64_t carry = 0; - for (unsigned i = 0; i < getNumWords(); i++) { - val[i] = pVal[i] << shiftAmt | carry; - carry = pVal[i] >> (APINT_BITS_PER_WORD - shiftAmt); - } - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; - } - - // Compute some values needed by the remaining shift algorithms - unsigned wordShift = shiftAmt % APINT_BITS_PER_WORD; - unsigned offset = shiftAmt / APINT_BITS_PER_WORD; - - // If we are shifting whole words, just move whole words - if (wordShift == 0) { - for (unsigned i = 0; i < offset; i++) - val[i] = 0; - for (unsigned i = offset; i < getNumWords(); i++) - val[i] = pVal[i-offset]; - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; - } - - // Copy whole words from this to Result. - unsigned i = getNumWords() - 1; - for (; i > offset; --i) - val[i] = pVal[i-offset] << wordShift | - pVal[i-offset-1] >> (APINT_BITS_PER_WORD - wordShift); - val[offset] = pVal[0] << wordShift; - for (i = 0; i < offset; ++i) - val[i] = 0; - APInt Result(val, BitWidth); - Result.clearUnusedBits(); - return Result; +void APInt::shlSlowCase(unsigned ShiftAmt) { + tcShiftLeft(pVal, getNumWords(), ShiftAmt); + clearUnusedBits(); } // Calculate the rotate amount modulo the bit width. @@ -2239,7 +2142,7 @@ void APInt::toString(SmallVectorImpl<char> &Str, unsigned Radix, while (Tmp != 0) { unsigned Digit = unsigned(Tmp.getRawData()[0]) & MaskAmt; Str.push_back(Digits[Digit]); - Tmp = Tmp.lshr(ShiftAmt); + Tmp.lshrInPlace(ShiftAmt); } } else { APInt divisor(Radix == 10? 4 : 8, Radix); @@ -2698,63 +2601,58 @@ int APInt::tcDivide(WordType *lhs, const WordType *rhs, return false; } -/* Shift a bignum left COUNT bits in-place. Shifted in bits are zero. - There are no restrictions on COUNT. */ -void APInt::tcShiftLeft(WordType *dst, unsigned parts, unsigned count) { - if (count) { - /* Jump is the inter-part jump; shift is is intra-part shift. */ - unsigned jump = count / APINT_BITS_PER_WORD; - unsigned shift = count % APINT_BITS_PER_WORD; - - while (parts > jump) { - WordType part; +/// Shift a bignum left Cound bits in-place. Shifted in bits are zero. There are +/// no restrictions on Count. +void APInt::tcShiftLeft(WordType *Dst, unsigned Words, unsigned Count) { + // Don't bother performing a no-op shift. + if (!Count) + return; - parts--; + /* WordShift is the inter-part shift; BitShift is is intra-part shift. */ + unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words); + unsigned BitShift = Count % APINT_BITS_PER_WORD; - /* dst[i] comes from the two parts src[i - jump] and, if we have - an intra-part shift, src[i - jump - 1]. */ - part = dst[parts - jump]; - if (shift) { - part <<= shift; - if (parts >= jump + 1) - part |= dst[parts - jump - 1] >> (APINT_BITS_PER_WORD - shift); - } - - dst[parts] = part; + // Fastpath for moving by whole words. + if (BitShift == 0) { + std::memmove(Dst + WordShift, Dst, (Words - WordShift) * APINT_WORD_SIZE); + } else { + while (Words-- > WordShift) { + Dst[Words] = Dst[Words - WordShift] << BitShift; + if (Words > WordShift) + Dst[Words] |= + Dst[Words - WordShift - 1] >> (APINT_BITS_PER_WORD - BitShift); } - - while (parts > 0) - dst[--parts] = 0; } + + // Fill in the remainder with 0s. + std::memset(Dst, 0, WordShift * APINT_WORD_SIZE); } -/* Shift a bignum right COUNT bits in-place. Shifted in bits are - zero. There are no restrictions on COUNT. */ -void APInt::tcShiftRight(WordType *dst, unsigned parts, unsigned count) { - if (count) { - /* Jump is the inter-part jump; shift is is intra-part shift. */ - unsigned jump = count / APINT_BITS_PER_WORD; - unsigned shift = count % APINT_BITS_PER_WORD; +/// Shift a bignum right Count bits in-place. Shifted in bits are zero. There +/// are no restrictions on Count. +void APInt::tcShiftRight(WordType *Dst, unsigned Words, unsigned Count) { + // Don't bother performing a no-op shift. + if (!Count) + return; - /* Perform the shift. This leaves the most significant COUNT bits - of the result at zero. */ - for (unsigned i = 0; i < parts; i++) { - WordType part; + // WordShift is the inter-part shift; BitShift is is intra-part shift. + unsigned WordShift = std::min(Count / APINT_BITS_PER_WORD, Words); + unsigned BitShift = Count % APINT_BITS_PER_WORD; - if (i + jump >= parts) { - part = 0; - } else { - part = dst[i + jump]; - if (shift) { - part >>= shift; - if (i + jump + 1 < parts) - part |= dst[i + jump + 1] << (APINT_BITS_PER_WORD - shift); - } - } - - dst[i] = part; + unsigned WordsToMove = Words - WordShift; + // Fastpath for moving by whole words. + if (BitShift == 0) { + std::memmove(Dst, Dst + WordShift, WordsToMove * APINT_WORD_SIZE); + } else { + for (unsigned i = 0; i != WordsToMove; ++i) { + Dst[i] = Dst[i + WordShift] >> BitShift; + if (i + 1 != WordsToMove) + Dst[i] |= Dst[i + WordShift + 1] << (APINT_BITS_PER_WORD - BitShift); } } + + // Fill in the remainder with 0s. + std::memset(Dst + WordsToMove, 0, WordShift * APINT_WORD_SIZE); } /* Bitwise and of two bignums. */ |