Go to the documentation of this file.
14 #ifndef LLVM_ADT_SMALLBITVECTOR_H
15 #define LLVM_ADT_SMALLBITVECTOR_H
43 NumBaseBits =
sizeof(uintptr_t) * CHAR_BIT,
47 SmallNumRawBits = NumBaseBits - 1,
52 SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
53 NumBaseBits == 64 ? 6 :
57 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
60 static_assert(NumBaseBits == 64 || NumBaseBits == 32,
61 "Unsupported word size");
83 TheVector.
set(BitPos);
85 TheVector.
reset(BitPos);
89 operator bool()
const {
90 return const_cast<const SmallBitVector &
>(TheVector).
operator[](BitPos);
100 void switchToSmall(uintptr_t NewSmallBits,
size_type NewSize) {
102 setSmallSize(NewSize);
103 setSmallBits(NewSmallBits);
106 void switchToLarge(BitVector *BV) {
107 X =
reinterpret_cast<uintptr_t
>(BV);
113 uintptr_t getSmallRawBits()
const {
118 void setSmallRawBits(uintptr_t NewRawBits) {
120 X = (NewRawBits << 1) | uintptr_t(1);
125 return getSmallRawBits() >> SmallNumDataBits;
129 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
133 uintptr_t getSmallBits()
const {
134 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
137 void setSmallBits(uintptr_t NewBits) {
138 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
139 (getSmallSize() << SmallNumDataBits));
149 if (
s <= SmallNumDataBits)
150 switchToSmall(
t ? ~uintptr_t(0) : 0,
s);
191 return isSmall() ? getSmallSize() == 0 : getPointer()->
empty();
196 return isSmall() ? getSmallSize() : getPointer()->
size();
202 uintptr_t
Bits = getSmallBits();
205 return getPointer()->
count();
211 return getSmallBits() != 0;
212 return getPointer()->
any();
218 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
219 return getPointer()->
all();
225 return getSmallBits() == 0;
226 return getPointer()->
none();
232 uintptr_t
Bits = getSmallBits();
242 uintptr_t
Bits = getSmallBits();
253 if (
count() == getSmallSize())
256 uintptr_t
Bits = getSmallBits();
264 if (
count() == getSmallSize())
267 uintptr_t
Bits = getSmallBits();
269 Bits |= ~uintptr_t(0) << getSmallSize();
279 uintptr_t
Bits = getSmallBits();
281 Bits &= ~uintptr_t(0) << (Prev + 1);
282 if (
Bits == 0 || Prev + 1 >= getSmallSize())
293 uintptr_t
Bits = getSmallBits();
295 Bits |= (uintptr_t(1) << (Prev + 1)) - 1;
297 Bits |= ~uintptr_t(0) << getSmallSize();
299 if (
Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
314 uintptr_t
Bits = getSmallBits();
315 Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
335 }
else if (SmallNumDataBits >=
N) {
336 uintptr_t NewBits =
t ? ~uintptr_t(0) << getSmallSize() : 0;
338 setSmallBits(NewBits | getSmallBits());
341 uintptr_t OldBits = getSmallBits();
343 (*BV)[
I] = (OldBits >>
I) & 1;
350 if (
N > SmallNumDataBits) {
351 uintptr_t OldBits = getSmallRawBits();
355 if ((OldBits >>
I) & 1)
368 setSmallBits(~uintptr_t(0));
376 assert(Idx <=
static_cast<unsigned>(
377 std::numeric_limits<uintptr_t>::digits) &&
378 "undefined behavior");
379 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
382 getPointer()->
set(Idx);
388 assert(
I <=
E &&
"Attempted to set backwards range!");
389 assert(
E <=
size() &&
"Attempted to set out-of-bounds range!");
390 if (
I ==
E)
return *
this;
392 uintptr_t EMask = ((uintptr_t)1) <<
E;
393 uintptr_t IMask = ((uintptr_t)1) <<
I;
394 uintptr_t
Mask = EMask - IMask;
395 setSmallBits(getSmallBits() |
Mask);
397 getPointer()->
set(
I,
E);
405 getPointer()->
reset();
411 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
413 getPointer()->
reset(Idx);
419 assert(
I <=
E &&
"Attempted to reset backwards range!");
420 assert(
E <=
size() &&
"Attempted to reset out-of-bounds range!");
421 if (
I ==
E)
return *
this;
423 uintptr_t EMask = ((uintptr_t)1) <<
E;
424 uintptr_t IMask = ((uintptr_t)1) <<
I;
425 uintptr_t
Mask = EMask - IMask;
426 setSmallBits(getSmallBits() & ~
Mask);
434 setSmallBits(~getSmallBits());
436 getPointer()->
flip();
442 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
444 getPointer()->
flip(Idx);
455 assert(Idx <
size() &&
"Out-of-bounds Bit access.");
460 assert(Idx <
size() &&
"Out-of-bounds Bit access.");
462 return ((getSmallBits() >> Idx) & 1) != 0;
463 return getPointer()->operator[](Idx);
468 assert(!
empty() &&
"Getting last element of empty vector.");
469 return (*
this)[
size() - 1];
472 bool test(
unsigned Idx)
const {
483 assert(!
empty() &&
"Empty vector has no element to pop.");
490 return (getSmallBits() &
RHS.getSmallBits()) != 0;
505 return getSmallBits() ==
RHS.getSmallBits();
507 return *getPointer() == *
RHS.getPointer();
510 if ((*
this)[
I] !=
RHS[
I])
518 return !(*
this ==
RHS);
526 setSmallBits(getSmallBits() &
RHS.getSmallBits());
528 getPointer()->operator&=(*
RHS.getPointer());
542 setSmallBits(getSmallBits() & ~
RHS.getSmallBits());
544 getPointer()->
reset(*
RHS.getPointer());
556 return (getSmallBits() & ~
RHS.getSmallBits()) != 0;
558 return getPointer()->
test(*
RHS.getPointer());
575 setSmallBits(getSmallBits() |
RHS.getSmallBits());
577 getPointer()->operator|=(*
RHS.getPointer());
588 setSmallBits(getSmallBits() ^
RHS.getSmallBits());
590 getPointer()->operator^=(*
RHS.getPointer());
600 setSmallBits(getSmallBits() <<
N);
602 getPointer()->operator<<=(
N);
608 setSmallBits(getSmallBits() >>
N);
610 getPointer()->operator>>=(
N);
623 *getPointer() = *
RHS.getPointer();
648 applyMask<true, false>(
Mask, MaskWords);
657 applyMask<false, false>(
Mask, MaskWords);
666 applyMask<true, true>(
Mask, MaskWords);
675 applyMask<false, true>(
Mask, MaskWords);
688 return getPointer()->
getData();
689 Store = getSmallBits();
694 template <
bool AddBits,
bool InvertMask>
695 void applyMask(
const uint32_t *
Mask,
unsigned MaskWords) {
696 assert(MaskWords <=
sizeof(uintptr_t) &&
"Mask is larger than base!");
697 uintptr_t
M =
Mask[0];
698 if (NumBaseBits == 64)
703 setSmallBits(getSmallBits() | M);
705 setSmallBits(getSmallBits() & ~M);
709 inline SmallBitVector
716 inline SmallBitVector
723 inline SmallBitVector
740 std::pair<SmallBitVector::size_type, ArrayRef<uintptr_t>>>::
744 if (
LHS.isInvalid() ||
RHS.isInvalid())
745 return LHS.isInvalid() ==
RHS.isInvalid();
761 #endif // LLVM_ADT_SMALLBITVECTOR_H
SmallBitVector & set(unsigned Idx)
void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Clear any bits in this vector that are set in Mask.
This is an optimization pass for GlobalISel generic memory operations.
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
SmallBitVector & operator|=(const SmallBitVector &RHS)
ArrayRef< BitWord > getData() const
bool none() const
none - Returns true if none of the bits are set.
static unsigned getHashValue(const SmallBitVector &V)
static SmallBitVector getEmptyKey()
SmallBitVector(const SmallBitVector &RHS)
SmallBitVector copy ctor.
SmallBitVector & reset(unsigned I, unsigned E)
Efficiently reset a range of bits in [I, E)
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Add '1' bits from Mask to this vector.
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
SmallBitVector & flip(unsigned Idx)
int find_next_unset(unsigned Prev) const
find_next_unset - Returns the index of the next unset bit following the "Prev" bit.
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool test(unsigned Idx) const
unsigned countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
bool none() const
Returns true if none of the bits are set.
int find_last() const
find_last - Returns the index of the last set bit, -1 if none of the bits are set.
static SmallBitVector getTombstoneKey()
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Add a bit to this vector for every '0' bit in Mask.
This is a 'bitvector' (really, a variable-sized bit array), optimized for the case when the array is ...
bool all() const
all - Returns true if all bits are set.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
An information struct used to provide DenseMap with the various necessary components for a given valu...
int find_prev(unsigned PriorTo) const
find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.
int find_first_unset() const
find_first_unset - Returns the index of the first unset bit, -1 if all of the bits are set.
SmallBitVector(SmallBitVector &&RHS)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
size_type count() const
count - Returns the number of bits which are set.
size_type size() const
size - Returns the number of bits in this bitvector.
int find_last_unset() const
reference operator[](unsigned Idx)
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
int find_prev(unsigned PriorTo) const
find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.
int find_next_unset(unsigned Prev) const
Returns the index of the next unset bit following the "Prev" bit.
bool all() const
Returns true if all bits are set.
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
bool empty() const
empty - Tests whether there are no bits in this bitvector.
SmallBitVector & set(unsigned I, unsigned E)
Efficiently set a range of bits in [I, E)
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
void clear()
Clear all bits.
unsigned countPopulation(T Value)
Count the number of set bits in a value.
APInt operator|(APInt a, const APInt &b)
int find_first_unset() const
Returns the index of the first unset bit, -1 if all of the bits are set.
bool operator==(const SmallBitVector &RHS) const
bool any() const
any - Returns true if any bit is set.
multiplies can be turned into SHL s
SmallBitVector & operator>>=(unsigned N)
unsigned countTrailingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the least significant bit to the first zero bit.
SmallBitVector & operator<<=(unsigned N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
reference & operator=(bool t)
SmallBitVector & reset(unsigned Idx)
bool back() const
Return the last element in the vector.
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS)
bool empty() const
Tests whether there are no bits in this bitvector.
Since we know that Vector is byte aligned and we know the element offset of X
void pop_back()
Pop one bit from the end of the vector.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1.
void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsInMask - Clear any bits in this vector that are set in Mask.
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Clear a bit in this vector for every '0' bit in Mask.
reference & operator=(reference t)
SmallBitVector & operator&=(const SmallBitVector &RHS)
APInt operator^(APInt a, const APInt &b)
SmallBitVector & reset(const SmallBitVector &RHS)
Reset bits that are set in RHS. Same as *this &= ~RHS.
APInt operator&(APInt a, const APInt &b)
reference(SmallBitVector &b, unsigned Idx)
size_type count() const
Returns the number of bits which are set.
bool test(unsigned Idx) const
bool operator!=(const SmallBitVector &RHS) const
void swap(SmallBitVector &RHS)
SmallBitVector operator~() const
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsInMask - Add '1' bits from Mask to this vector.
iterator_range< const_set_bits_iterator > set_bits() const
ArrayRef< uintptr_t > getData(uintptr_t &Store) const
int find_last_unset() const
find_last_unset - Returns the index of the last unset bit, -1 if all of the bits are set.
bool anyCommon(const SmallBitVector &RHS) const
Test if any common bits are set.
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1.
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
size_type size() const
Returns the number of bits in this bitvector.
const SmallBitVector & operator=(SmallBitVector &&RHS)
SmallBitVector()=default
Creates an empty bitvector.
const_set_bits_iterator_impl< SmallBitVector > const_set_bits_iterator
const SmallBitVector & operator=(const SmallBitVector &RHS)
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
bool operator[](unsigned Idx) const
A range adaptor for a pair of iterators.
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
SmallBitVector & operator^=(const SmallBitVector &RHS)
const_set_bits_iterator set_bits_begin() const
SmallBitVector(unsigned s, bool t=false)
Creates a bitvector of specified number of bits.
ForwardIterator for the bits that are set.
bool test(const SmallBitVector &RHS) const
Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
const_set_bits_iterator set_bits_end() const
bool any() const
Returns true if any bit is set.