summaryrefslogtreecommitdiff
path: root/include/llvm/ADT
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/ADT')
-rw-r--r--include/llvm/ADT/APInt.h201
-rw-r--r--include/llvm/ADT/BitVector.h149
-rw-r--r--include/llvm/ADT/SmallBitVector.h16
3 files changed, 288 insertions, 78 deletions
diff --git a/include/llvm/ADT/APInt.h b/include/llvm/ADT/APInt.h
index ab23130b137d..ceb623d34531 100644
--- a/include/llvm/ADT/APInt.h
+++ b/include/llvm/ADT/APInt.h
@@ -189,17 +189,17 @@ private:
void initSlowCase(const APInt &that);
/// out-of-line slow case for shl
- APInt shlSlowCase(unsigned shiftAmt) const;
+ void shlSlowCase(unsigned ShiftAmt);
+
+ /// out-of-line slow case for lshr.
+ void lshrSlowCase(unsigned ShiftAmt);
/// out-of-line slow case for operator=
- APInt &AssignSlowCase(const APInt &RHS);
+ void AssignSlowCase(const APInt &RHS);
/// out-of-line slow case for operator==
bool EqualSlowCase(const APInt &RHS) const LLVM_READONLY;
- /// out-of-line slow case for operator==
- bool EqualSlowCase(uint64_t Val) const LLVM_READONLY;
-
/// out-of-line slow case for countLeadingZeros
unsigned countLeadingZerosSlowCase() const LLVM_READONLY;
@@ -209,6 +209,12 @@ private:
/// out-of-line slow case for countPopulation
unsigned countPopulationSlowCase() const LLVM_READONLY;
+ /// out-of-line slow case for intersects.
+ bool intersectsSlowCase(const APInt &RHS) const LLVM_READONLY;
+
+ /// out-of-line slow case for isSubsetOf.
+ bool isSubsetOfSlowCase(const APInt &RHS) const LLVM_READONLY;
+
/// out-of-line slow case for setBits.
void setBitsSlowCase(unsigned loBit, unsigned hiBit);
@@ -216,13 +222,13 @@ private:
void flipAllBitsSlowCase();
/// out-of-line slow case for operator&=.
- APInt& AndAssignSlowCase(const APInt& RHS);
+ void AndAssignSlowCase(const APInt& RHS);
/// out-of-line slow case for operator|=.
- APInt& OrAssignSlowCase(const APInt& RHS);
+ void OrAssignSlowCase(const APInt& RHS);
/// out-of-line slow case for operator^=.
- APInt& XorAssignSlowCase(const APInt& RHS);
+ void XorAssignSlowCase(const APInt& RHS);
public:
/// \name Constructors
@@ -330,6 +336,20 @@ public:
/// This tests the high bit of the APInt to determine if it is unset.
bool isNonNegative() const { return !isNegative(); }
+ /// \brief Determine if sign bit of this APInt is set.
+ ///
+ /// This tests the high bit of this APInt to determine if it is set.
+ ///
+ /// \returns true if this APInt has its sign bit set, false otherwise.
+ bool isSignBitSet() const { return (*this)[BitWidth-1]; }
+
+ /// \brief Determine if sign bit of this APInt is clear.
+ ///
+ /// This tests the high bit of this APInt to determine if it is clear.
+ ///
+ /// \returns true if this APInt has its sign bit clear, false otherwise.
+ bool isSignBitClear() const { return !isSignBitSet(); }
+
/// \brief Determine if this APInt Value is positive.
///
/// This tests if the value of this APInt is positive (> 0). Note
@@ -396,10 +416,10 @@ public:
return countPopulationSlowCase() == 1;
}
- /// \brief Check if the APInt's value is returned by getSignBit.
+ /// \brief Check if the APInt's value is returned by getSignMask.
///
- /// \returns true if this is the value returned by getSignBit.
- bool isSignBit() const { return isMinSignedValue(); }
+ /// \returns true if this is the value returned by getSignMask.
+ bool isSignMask() const { return isMinSignedValue(); }
/// \brief Convert APInt to a boolean value.
///
@@ -409,8 +429,7 @@ public:
/// If this value is smaller than the specified limit, return it, otherwise
/// return the limit value. This causes the value to saturate to the limit.
uint64_t getLimitedValue(uint64_t Limit = UINT64_MAX) const {
- return (getActiveBits() > 64 || getZExtValue() > Limit) ? Limit
- : getZExtValue();
+ return ugt(Limit) ? Limit : getZExtValue();
}
/// \brief Check if the APInt consists of a repeated bit pattern.
@@ -427,8 +446,9 @@ public:
assert(numBits <= BitWidth && "numBits out of range");
if (isSingleWord())
return VAL == (UINT64_MAX >> (APINT_BITS_PER_WORD - numBits));
- unsigned Ones = countTrailingOnes();
- return (numBits == Ones) && ((Ones + countLeadingZeros()) == BitWidth);
+ unsigned Ones = countTrailingOnesSlowCase();
+ return (numBits == Ones) &&
+ ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}
/// \returns true if this APInt is a non-empty sequence of ones starting at
@@ -437,8 +457,8 @@ public:
bool isMask() const {
if (isSingleWord())
return isMask_64(VAL);
- unsigned Ones = countTrailingOnes();
- return (Ones > 0) && ((Ones + countLeadingZeros()) == BitWidth);
+ unsigned Ones = countTrailingOnesSlowCase();
+ return (Ones > 0) && ((Ones + countLeadingZerosSlowCase()) == BitWidth);
}
/// \brief Return true if this APInt value contains a sequence of ones with
@@ -446,8 +466,9 @@ public:
bool isShiftedMask() const {
if (isSingleWord())
return isShiftedMask_64(VAL);
- unsigned Ones = countPopulation();
- return (Ones + countTrailingZeros() + countLeadingZeros()) == BitWidth;
+ unsigned Ones = countPopulationSlowCase();
+ unsigned LeadZ = countLeadingZerosSlowCase();
+ return (Ones + LeadZ + countTrailingZeros()) == BitWidth;
}
/// @}
@@ -476,11 +497,11 @@ public:
return API;
}
- /// \brief Get the SignBit for a specific bit width.
+ /// \brief Get the SignMask for a specific bit width.
///
/// This is just a wrapper function of getSignedMinValue(), and it helps code
- /// readability when we want to get a SignBit.
- static APInt getSignBit(unsigned BitWidth) {
+ /// readability when we want to get a SignMask.
+ static APInt getSignMask(unsigned BitWidth) {
return getSignedMinValue(BitWidth);
}
@@ -674,29 +695,22 @@ public:
return clearUnusedBits();
}
- return AssignSlowCase(RHS);
+ AssignSlowCase(RHS);
+ return *this;
}
/// @brief Move assignment operator.
APInt &operator=(APInt &&that) {
- if (!isSingleWord()) {
- // The MSVC STL shipped in 2013 requires that self move assignment be a
- // no-op. Otherwise algorithms like stable_sort will produce answers
- // where half of the output is left in a moved-from state.
- if (this == &that)
- return *this;
+ assert(this != &that && "Self-move not supported");
+ if (!isSingleWord())
delete[] pVal;
- }
// Use memcpy so that type based alias analysis sees both VAL and pVal
// as modified.
memcpy(&VAL, &that.VAL, sizeof(uint64_t));
- // If 'this == &that', avoid zeroing our own bitwidth by storing to 'that'
- // first.
- unsigned ThatBitWidth = that.BitWidth;
+ BitWidth = that.BitWidth;
that.BitWidth = 0;
- BitWidth = ThatBitWidth;
return *this;
}
@@ -727,11 +741,11 @@ public:
/// \returns *this after ANDing with RHS.
APInt &operator&=(const APInt &RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
- if (isSingleWord()) {
+ if (isSingleWord())
VAL &= RHS.VAL;
- return *this;
- }
- return AndAssignSlowCase(RHS);
+ else
+ AndAssignSlowCase(RHS);
+ return *this;
}
/// \brief Bitwise AND assignment operator.
@@ -757,11 +771,11 @@ public:
/// \returns *this after ORing with RHS.
APInt &operator|=(const APInt &RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
- if (isSingleWord()) {
+ if (isSingleWord())
VAL |= RHS.VAL;
- return *this;
- }
- return OrAssignSlowCase(RHS);
+ else
+ OrAssignSlowCase(RHS);
+ return *this;
}
/// \brief Bitwise OR assignment operator.
@@ -787,11 +801,11 @@ public:
/// \returns *this after XORing with RHS.
APInt &operator^=(const APInt &RHS) {
assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
- if (isSingleWord()) {
+ if (isSingleWord())
VAL ^= RHS.VAL;
- return *this;
- }
- return XorAssignSlowCase(RHS);
+ else
+ XorAssignSlowCase(RHS);
+ return *this;
}
/// \brief Bitwise XOR assignment operator.
@@ -836,9 +850,17 @@ public:
///
/// Shifts *this left by shiftAmt and assigns the result to *this.
///
- /// \returns *this after shifting left by shiftAmt
- APInt &operator<<=(unsigned shiftAmt) {
- *this = shl(shiftAmt);
+ /// \returns *this after shifting left by ShiftAmt
+ APInt &operator<<=(unsigned ShiftAmt) {
+ assert(ShiftAmt <= BitWidth && "Invalid shift amount");
+ if (isSingleWord()) {
+ if (ShiftAmt == BitWidth)
+ VAL = 0;
+ else
+ VAL <<= ShiftAmt;
+ return clearUnusedBits();
+ }
+ shlSlowCase(ShiftAmt);
return *this;
}
@@ -875,20 +897,26 @@ public:
return R;
}
- /// Logical right-shift this APInt by shiftAmt in place.
- void lshrInPlace(unsigned shiftAmt);
+ /// Logical right-shift this APInt by ShiftAmt in place.
+ void lshrInPlace(unsigned ShiftAmt) {
+ assert(ShiftAmt <= BitWidth && "Invalid shift amount");
+ if (isSingleWord()) {
+ if (ShiftAmt == BitWidth)
+ VAL = 0;
+ else
+ VAL >>= ShiftAmt;
+ return;
+ }
+ lshrSlowCase(ShiftAmt);
+ }
/// \brief Left-shift function.
///
/// Left-shift this APInt by shiftAmt.
APInt shl(unsigned shiftAmt) const {
- assert(shiftAmt <= BitWidth && "Invalid shift amount");
- if (isSingleWord()) {
- if (shiftAmt >= BitWidth)
- return APInt(BitWidth, 0); // avoid undefined shift results
- return APInt(BitWidth, VAL << shiftAmt);
- }
- return shlSlowCase(shiftAmt);
+ APInt R(*this);
+ R <<= shiftAmt;
+ return R;
}
/// \brief Rotate left by rotateAmt.
@@ -905,7 +933,14 @@ public:
/// \brief Logical right-shift function.
///
/// Logical right-shift this APInt by shiftAmt.
- APInt lshr(const APInt &shiftAmt) const;
+ APInt lshr(const APInt &ShiftAmt) const {
+ APInt R(*this);
+ R.lshrInPlace(ShiftAmt);
+ return R;
+ }
+
+ /// Logical right-shift this APInt by ShiftAmt in place.
+ void lshrInPlace(const APInt &ShiftAmt);
/// \brief Left-shift function.
///
@@ -1003,9 +1038,7 @@ public:
///
/// \returns true if *this == Val
bool operator==(uint64_t Val) const {
- if (isSingleWord())
- return VAL == Val;
- return EqualSlowCase(Val);
+ return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() == Val;
}
/// \brief Equality comparison.
@@ -1055,7 +1088,8 @@ public:
///
/// \returns true if *this < RHS when considered unsigned.
bool ult(uint64_t RHS) const {
- return getActiveBits() > 64 ? false : getZExtValue() < RHS;
+ // Only need to check active bits if not a single word.
+ return (isSingleWord() || getActiveBits() <= 64) && getZExtValue() < RHS;
}
/// \brief Signed less than comparison
@@ -1073,7 +1107,8 @@ public:
///
/// \returns true if *this < RHS when considered signed.
bool slt(int64_t RHS) const {
- return getMinSignedBits() > 64 ? isNegative() : getSExtValue() < RHS;
+ return (!isSingleWord() && getMinSignedBits() > 64) ? isNegative()
+ : getSExtValue() < RHS;
}
/// \brief Unsigned less or equal comparison
@@ -1123,7 +1158,8 @@ public:
///
/// \returns true if *this > RHS when considered unsigned.
bool ugt(uint64_t RHS) const {
- return getActiveBits() > 64 ? true : getZExtValue() > RHS;
+ // Only need to check active bits if not a single word.
+ return (!isSingleWord() && getActiveBits() > 64) || getZExtValue() > RHS;
}
/// \brief Signed greather than comparison
@@ -1141,7 +1177,8 @@ public:
///
/// \returns true if *this > RHS when considered signed.
bool sgt(int64_t RHS) const {
- return getMinSignedBits() > 64 ? !isNegative() : getSExtValue() > RHS;
+ return (!isSingleWord() && getMinSignedBits() > 64) ? !isNegative()
+ : getSExtValue() > RHS;
}
/// \brief Unsigned greater or equal comparison
@@ -1179,9 +1216,18 @@ public:
/// This operation tests if there are any pairs of corresponding bits
/// between this APInt and RHS that are both set.
bool intersects(const APInt &RHS) const {
- APInt temp(*this);
- temp &= RHS;
- return temp != 0;
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return (VAL & RHS.VAL) != 0;
+ return intersectsSlowCase(RHS);
+ }
+
+ /// This operation checks that all bits set in this APInt are also set in RHS.
+ bool isSubsetOf(const APInt &RHS) const {
+ assert(BitWidth == RHS.BitWidth && "Bit widths must be the same");
+ if (isSingleWord())
+ return (VAL & ~RHS.VAL) == 0;
+ return isSubsetOfSlowCase(RHS);
}
/// @}
@@ -1404,8 +1450,7 @@ public:
/// int64_t. Otherwise an assertion will result.
int64_t getSExtValue() const {
if (isSingleWord())
- return int64_t(VAL << (APINT_BITS_PER_WORD - BitWidth)) >>
- (APINT_BITS_PER_WORD - BitWidth);
+ return SignExtend64(VAL, BitWidth);
assert(getMinSignedBits() <= 64 && "Too many bits for int64_t");
return int64_t(pVal[0]);
}
@@ -1759,13 +1804,13 @@ public:
WordType *remainder, WordType *scratch,
unsigned parts);
- /// Shift a bignum left COUNT bits. Shifted in bits are zero. There are no
- /// restrictions on COUNT.
- static void tcShiftLeft(WordType *, unsigned parts, unsigned count);
+ /// Shift a bignum left Count bits. Shifted in bits are zero. There are no
+ /// restrictions on Count.
+ static void tcShiftLeft(WordType *, unsigned Words, unsigned Count);
- /// Shift a bignum right COUNT bits. Shifted in bits are zero. There are no
- /// restrictions on COUNT.
- static void tcShiftRight(WordType *, unsigned parts, unsigned count);
+ /// Shift a bignum right Count bits. Shifted in bits are zero. There are no
+ /// restrictions on Count.
+ static void tcShiftRight(WordType *, unsigned Words, unsigned Count);
/// The obvious AND, OR and XOR and complement operations.
static void tcAnd(WordType *, const WordType *, unsigned);
@@ -1959,7 +2004,7 @@ inline const APInt &umax(const APInt &A, const APInt &B) {
/// \brief Compute GCD of two unsigned APInt values.
///
/// This function returns the greatest common divisor of the two APInt values
-/// using Euclid's algorithm.
+/// using Stein's algorithm.
///
/// \returns the greatest common divisor of A and B.
APInt GreatestCommonDivisor(APInt A, APInt B);
diff --git a/include/llvm/ADT/BitVector.h b/include/llvm/ADT/BitVector.h
index 8240d01ae977..e48c023ae7df 100644
--- a/include/llvm/ADT/BitVector.h
+++ b/include/llvm/ADT/BitVector.h
@@ -14,6 +14,8 @@
#ifndef LLVM_ADT_BITVECTOR_H
#define LLVM_ADT_BITVECTOR_H
+#include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/MathExtras.h"
#include <algorithm>
#include <cassert>
@@ -455,6 +457,105 @@ public:
return *this;
}
+ BitVector &operator>>=(unsigned N) {
+ assert(N <= Size);
+ if (LLVM_UNLIKELY(empty() || N == 0))
+ return *this;
+
+ unsigned NumWords = NumBitWords(Size);
+ assert(NumWords >= 1);
+
+ wordShr(N / BITWORD_SIZE);
+
+ unsigned BitDistance = N % BITWORD_SIZE;
+ if (BitDistance == 0)
+ return *this;
+
+ // When the shift size is not a multiple of the word size, then we have
+ // a tricky situation where each word in succession needs to extract some
+ // of the bits from the next word and or them into this word while
+ // shifting this word to make room for the new bits. This has to be done
+ // for every word in the array.
+
+ // Since we're shifting each word right, some bits will fall off the end
+ // of each word to the right, and empty space will be created on the left.
+ // The final word in the array will lose bits permanently, so starting at
+ // the beginning, work forwards shifting each word to the right, and
+ // OR'ing in the bits from the end of the next word to the beginning of
+ // the current word.
+
+ // Example:
+ // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
+ // by 4 bits.
+ // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
+ // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
+ // Step 3: Word[1] >>= 4 ; 0x0EEFF001
+ // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
+ // Step 5: Word[2] >>= 4 ; 0x02334455
+ // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
+ const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
+ const unsigned LSH = BITWORD_SIZE - BitDistance;
+
+ for (unsigned I = 0; I < NumWords - 1; ++I) {
+ Bits[I] >>= BitDistance;
+ Bits[I] |= (Bits[I + 1] & Mask) << LSH;
+ }
+
+ Bits[NumWords - 1] >>= BitDistance;
+
+ return *this;
+ }
+
+ BitVector &operator<<=(unsigned N) {
+ assert(N <= Size);
+ if (LLVM_UNLIKELY(empty() || N == 0))
+ return *this;
+
+ unsigned NumWords = NumBitWords(Size);
+ assert(NumWords >= 1);
+
+ wordShl(N / BITWORD_SIZE);
+
+ unsigned BitDistance = N % BITWORD_SIZE;
+ if (BitDistance == 0)
+ return *this;
+
+ // When the shift size is not a multiple of the word size, then we have
+ // a tricky situation where each word in succession needs to extract some
+ // of the bits from the previous word and or them into this word while
+ // shifting this word to make room for the new bits. This has to be done
+ // for every word in the array. This is similar to the algorithm outlined
+ // in operator>>=, but backwards.
+
+ // Since we're shifting each word left, some bits will fall off the end
+ // of each word to the left, and empty space will be created on the right.
+ // The first word in the array will lose bits permanently, so starting at
+ // the end, work backwards shifting each word to the left, and OR'ing
+ // in the bits from the end of the next word to the beginning of the
+ // current word.
+
+ // Example:
+ // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
+ // by 4 bits.
+ // Step 1: Word[2] <<= 4 ; 0x23344550
+ // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
+ // Step 3: Word[1] <<= 4 ; 0xEFF00110
+ // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
+ // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
+ // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
+ const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
+ const unsigned RSH = BITWORD_SIZE - BitDistance;
+
+ for (int I = NumWords - 1; I > 0; --I) {
+ Bits[I] <<= BitDistance;
+ Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
+ }
+ Bits[0] <<= BitDistance;
+ clear_unused_bits();
+
+ return *this;
+ }
+
// Assignment operator.
const BitVector &operator=(const BitVector &RHS) {
if (this == &RHS) return *this;
@@ -538,6 +639,54 @@ public:
}
private:
+ /// \brief Perform a logical left shift of \p Count words by moving everything
+ /// \p Count words to the right in memory.
+ ///
+ /// While confusing, words are stored from least significant at Bits[0] to
+ /// most significant at Bits[NumWords-1]. A logical shift left, however,
+ /// moves the current least significant bit to a higher logical index, and
+ /// fills the previous least significant bits with 0. Thus, we actually
+ /// need to move the bytes of the memory to the right, not to the left.
+ /// Example:
+ /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
+ /// represents a BitVector where 0xBBBBAAAA contain the least significant
+ /// bits. So if we want to shift the BitVector left by 2 words, we need to
+ /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
+ /// memmove which moves right, not left.
+ void wordShl(uint32_t Count) {
+ if (Count == 0)
+ return;
+
+ uint32_t NumWords = NumBitWords(Size);
+
+ auto Src = ArrayRef<BitWord>(Bits, NumWords).drop_back(Count);
+ auto Dest = MutableArrayRef<BitWord>(Bits, NumWords).drop_front(Count);
+
+ // Since we always move Word-sized chunks of data with src and dest both
+ // aligned to a word-boundary, we don't need to worry about endianness
+ // here.
+ std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
+ std::memset(Bits, 0, Count * sizeof(BitWord));
+ clear_unused_bits();
+ }
+
+ /// \brief Perform a logical right shift of \p Count words by moving those
+ /// words to the left in memory. See wordShl for more information.
+ ///
+ void wordShr(uint32_t Count) {
+ if (Count == 0)
+ return;
+
+ uint32_t NumWords = NumBitWords(Size);
+
+ auto Src = ArrayRef<BitWord>(Bits, NumWords).drop_front(Count);
+ auto Dest = MutableArrayRef<BitWord>(Bits, NumWords).drop_back(Count);
+ assert(Dest.size() == Src.size());
+
+ std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
+ std::memset(Dest.end(), 0, Count * sizeof(BitWord));
+ }
+
int next_unset_in_word(int WordIndex, BitWord Word) const {
unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
return Result < size() ? Result : -1;
diff --git a/include/llvm/ADT/SmallBitVector.h b/include/llvm/ADT/SmallBitVector.h
index edb37da38da1..607e040a606c 100644
--- a/include/llvm/ADT/SmallBitVector.h
+++ b/include/llvm/ADT/SmallBitVector.h
@@ -508,6 +508,22 @@ public:
return *this;
}
+ SmallBitVector &operator<<=(unsigned N) {
+ if (isSmall())
+ setSmallBits(getSmallBits() << N);
+ else
+ getPointer()->operator<<=(N);
+ return *this;
+ }
+
+ SmallBitVector &operator>>=(unsigned N) {
+ if (isSmall())
+ setSmallBits(getSmallBits() >> N);
+ else
+ getPointer()->operator>>=(N);
+ return *this;
+ }
+
// Assignment operator.
const SmallBitVector &operator=(const SmallBitVector &RHS) {
if (isSmall()) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-11 06:56:08 +0000