Go to the documentation of this file.
13 #ifndef LLVM_ADT_BITVECTOR_H
14 #define LLVM_ADT_BITVECTOR_H
33 const BitVectorT &Parent;
37 assert(Current != -1 &&
"Trying to advance past end.");
38 Current = Parent.find_next(Current);
43 : Parent(Parent), Current(Current) {}
63 "Comparing iterators from different BitVectors");
64 return Current ==
Other.Current;
69 "Comparing iterators from different BitVectors");
70 return Current !=
Other.Current;
75 typedef uintptr_t BitWord;
77 enum { BITWORD_SIZE = (unsigned)
sizeof(BitWord) * CHAR_BIT };
79 static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
80 "Unsupported word size");
96 WordRef = &
b.Bits[Idx / BITWORD_SIZE];
97 BitPos = Idx % BITWORD_SIZE;
110 *WordRef |= BitWord(1) << BitPos;
112 *WordRef &= ~(BitWord(1) << BitPos);
116 operator bool()
const {
117 return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
140 size_t Capacity = NumBitWords(
s);
141 Bits = allocate(Capacity);
154 size_t Capacity = NumBitWords(RHS.
size());
155 Bits = allocate(Capacity);
174 unsigned NumBits = 0;
175 for (
unsigned i = 0;
i < NumBitWords(
size()); ++
i)
182 for (
unsigned i = 0;
i < NumBitWords(
size()); ++
i)
190 for (
unsigned i = 0;
i <
Size / BITWORD_SIZE; ++
i)
191 if (
Bits[
i] != ~BitWord(0))
195 if (
unsigned Remainder =
Size % BITWORD_SIZE)
196 return Bits[
Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
214 unsigned FirstWord = Begin / BITWORD_SIZE;
215 unsigned LastWord = (End - 1) / BITWORD_SIZE;
222 for (
unsigned i = FirstWord;
i <= LastWord; ++
i) {
223 BitWord Copy =
Bits[
i];
227 if (
i == FirstWord) {
228 unsigned FirstBit = Begin % BITWORD_SIZE;
229 Copy &= maskTrailingZeros<BitWord>(FirstBit);
233 unsigned LastBit = (End - 1) % BITWORD_SIZE;
234 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
249 unsigned LastWord = (End - 1) / BITWORD_SIZE;
250 unsigned FirstWord = Begin / BITWORD_SIZE;
252 for (
unsigned i = LastWord + 1;
i >= FirstWord + 1; --
i) {
253 unsigned CurrentWord =
i - 1;
255 BitWord Copy =
Bits[CurrentWord];
256 if (CurrentWord == LastWord) {
257 unsigned LastBit = (End - 1) % BITWORD_SIZE;
258 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
261 if (CurrentWord == FirstWord) {
262 unsigned FirstBit = Begin % BITWORD_SIZE;
263 Copy &= maskTrailingZeros<BitWord>(FirstBit);
286 unsigned LastWord = (End - 1) / BITWORD_SIZE;
287 unsigned FirstWord = Begin / BITWORD_SIZE;
289 for (
unsigned i = LastWord + 1;
i >= FirstWord + 1; --
i) {
290 unsigned CurrentWord =
i - 1;
292 BitWord Copy =
Bits[CurrentWord];
293 if (CurrentWord == LastWord) {
294 unsigned LastBit = (End - 1) % BITWORD_SIZE;
295 Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
298 if (CurrentWord == FirstWord) {
299 unsigned FirstBit = Begin % BITWORD_SIZE;
300 Copy |= maskTrailingOnes<BitWord>(FirstBit);
303 if (Copy != ~BitWord(0)) {
306 return Result <
Size ? Result : -1;
356 unsigned OldCapacity =
Bits.size();
358 init_words(
Bits.drop_front(OldCapacity),
t);
368 unsigned OldSize =
Size;
370 if (
t ||
N < OldSize)
381 init_words(
Bits,
true);
387 assert(
Bits.data() &&
"Bits never allocated");
388 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
394 assert(
I <=
E &&
"Attempted to set backwards range!");
395 assert(
E <=
size() &&
"Attempted to set out-of-bounds range!");
397 if (
I ==
E)
return *
this;
399 if (
I / BITWORD_SIZE ==
E / BITWORD_SIZE) {
400 BitWord EMask = BitWord(1) << (
E % BITWORD_SIZE);
401 BitWord IMask = BitWord(1) << (
I % BITWORD_SIZE);
402 BitWord
Mask = EMask - IMask;
407 BitWord PrefixMask = ~BitWord(0) << (
I % BITWORD_SIZE);
408 Bits[
I / BITWORD_SIZE] |= PrefixMask;
411 for (;
I + BITWORD_SIZE <=
E;
I += BITWORD_SIZE)
412 Bits[
I / BITWORD_SIZE] = ~BitWord(0);
414 BitWord PostfixMask = (BitWord(1) << (
E % BITWORD_SIZE)) - 1;
416 Bits[
I / BITWORD_SIZE] |= PostfixMask;
422 init_words(
Bits,
false);
427 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
433 assert(
I <=
E &&
"Attempted to reset backwards range!");
434 assert(
E <=
size() &&
"Attempted to reset out-of-bounds range!");
436 if (
I ==
E)
return *
this;
438 if (
I / BITWORD_SIZE ==
E / BITWORD_SIZE) {
439 BitWord EMask = BitWord(1) << (
E % BITWORD_SIZE);
440 BitWord IMask = BitWord(1) << (
I % BITWORD_SIZE);
441 BitWord
Mask = EMask - IMask;
446 BitWord PrefixMask = ~BitWord(0) << (
I % BITWORD_SIZE);
447 Bits[
I / BITWORD_SIZE] &= ~PrefixMask;
450 for (;
I + BITWORD_SIZE <=
E;
I += BITWORD_SIZE)
451 Bits[
I / BITWORD_SIZE] = BitWord(0);
453 BitWord PostfixMask = (BitWord(1) << (
E % BITWORD_SIZE)) - 1;
455 Bits[
I / BITWORD_SIZE] &= ~PostfixMask;
461 for (
unsigned i = 0;
i < NumBitWords(
size()); ++
i)
468 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
474 assert (Idx <
Size &&
"Out-of-bounds Bit access.");
479 assert (Idx <
Size &&
"Out-of-bounds Bit access.");
480 BitWord
Mask = BitWord(1) << (Idx % BITWORD_SIZE);
481 return (
Bits[Idx / BITWORD_SIZE] &
Mask) != 0;
484 bool test(
unsigned Idx)
const {
490 unsigned OldSize =
Size;
491 unsigned NewSize =
Size + 1;
507 unsigned ThisWords = NumBitWords(
size());
508 unsigned RHSWords = NumBitWords(RHS.
size());
509 for (
unsigned i = 0,
e =
std::min(ThisWords, RHSWords);
i !=
e; ++
i)
510 if (
Bits[
i] & RHS.Bits[
i])
519 unsigned NumWords = NumBitWords(
size());
520 return Bits.take_front(NumWords) == RHS.Bits.
take_front(NumWords);
524 return !(*
this == RHS);
529 unsigned ThisWords = NumBitWords(
size());
530 unsigned RHSWords = NumBitWords(RHS.
size());
532 for (
i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
538 for (;
i != ThisWords; ++
i)
546 unsigned ThisWords = NumBitWords(
size());
547 unsigned RHSWords = NumBitWords(RHS.
size());
549 for (
i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
557 unsigned ThisWords = NumBitWords(
size());
558 unsigned RHSWords = NumBitWords(RHS.
size());
560 for (
i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
561 if ((
Bits[
i] & ~RHS.Bits[
i]) != 0)
564 for (;
i != ThisWords ; ++
i)
574 for (
size_t i = 0,
e = NumBitWords(RHS.
size());
i !=
e; ++
i)
582 for (
size_t i = 0,
e = NumBitWords(RHS.
size());
i !=
e; ++
i)
592 unsigned NumWords = NumBitWords(
Size);
595 wordShr(
N / BITWORD_SIZE);
597 unsigned BitDistance =
N % BITWORD_SIZE;
598 if (BitDistance == 0)
623 const BitWord
Mask = maskTrailingOnes<BitWord>(BitDistance);
624 const unsigned LSH = BITWORD_SIZE - BitDistance;
626 for (
unsigned I = 0;
I < NumWords - 1; ++
I) {
627 Bits[
I] >>= BitDistance;
631 Bits[NumWords - 1] >>= BitDistance;
641 unsigned NumWords = NumBitWords(
Size);
644 wordShl(
N / BITWORD_SIZE);
646 unsigned BitDistance =
N % BITWORD_SIZE;
647 if (BitDistance == 0)
673 const BitWord
Mask = maskLeadingOnes<BitWord>(BitDistance);
674 const unsigned RSH = BITWORD_SIZE - BitDistance;
676 for (
int I = NumWords - 1;
I > 0; --
I) {
677 Bits[
I] <<= BitDistance;
680 Bits[0] <<= BitDistance;
688 if (
this == &RHS)
return *
this;
694 std::free(
Bits.data());
699 unsigned RHSWords = NumBitWords(
Size);
708 unsigned NewCapacity = RHSWords;
709 assert(NewCapacity > 0 &&
"negative capacity?");
710 auto NewBits = allocate(NewCapacity);
711 std::memcpy(NewBits.data(), RHS.Bits.
data(), NewCapacity *
sizeof(BitWord));
714 std::free(
Bits.data());
721 if (
this == &RHS)
return *
this;
723 std::free(
Bits.data());
745 return Bits.take_front(NumBitWords(
size()));
763 applyMask<true, false>(
Mask, MaskWords);
769 applyMask<false, false>(
Mask, MaskWords);
775 applyMask<true, true>(
Mask, MaskWords);
781 applyMask<false, true>(
Mask, MaskWords);
805 auto Src =
Bits.take_front(NumWords).drop_back(Count);
806 auto Dest =
Bits.take_front(NumWords).drop_front(Count);
811 std::memmove(Dest.begin(), Src.begin(), Dest.size() *
sizeof(BitWord));
812 std::memset(
Bits.data(), 0, Count *
sizeof(BitWord));
825 auto Src =
Bits.take_front(NumWords).drop_front(Count);
826 auto Dest =
Bits.take_front(NumWords).drop_back(Count);
827 assert(Dest.size() == Src.size());
829 std::memmove(Dest.begin(), Src.begin(), Dest.size() *
sizeof(BitWord));
830 std::memset(Dest.end(), 0, Count *
sizeof(BitWord));
833 MutableArrayRef<BitWord> allocate(
size_t NumWords) {
834 BitWord *RawBits =
static_cast<BitWord *
>(
836 return MutableArrayRef<BitWord>(RawBits, NumWords);
839 int next_unset_in_word(
int WordIndex, BitWord
Word)
const {
844 unsigned NumBitWords(
unsigned S)
const {
845 return (
S + BITWORD_SIZE-1) / BITWORD_SIZE;
849 void set_unused_bits(
bool t =
true) {
851 unsigned UsedWords = NumBitWords(
Size);
852 if (
Bits.size() > UsedWords)
853 init_words(
Bits.drop_front(UsedWords),
t);
856 unsigned ExtraBits =
Size % BITWORD_SIZE;
858 BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
860 Bits[UsedWords-1] |= ExtraBitMask;
862 Bits[UsedWords-1] &= ~ExtraBitMask;
867 void clear_unused_bits() {
868 set_unused_bits(
false);
871 void grow(
unsigned NewSize) {
872 size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize),
Bits.size() * 2);
873 assert(NewCapacity > 0 &&
"realloc-ing zero space");
874 BitWord *NewBits =
static_cast<BitWord *
>(
876 Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
880 void init_words(MutableArrayRef<BitWord>
B,
bool t) {
882 memset(
B.data(), 0 - (
int)
t,
B.size() *
sizeof(BitWord));
885 template<
bool AddBits,
bool InvertMask>
886 void applyMask(
const uint32_t *
Mask,
unsigned MaskWords) {
887 static_assert(BITWORD_SIZE % 32 == 0,
"Unsupported BitWord size.");
889 const unsigned Scale = BITWORD_SIZE / 32;
891 for (
i = 0; MaskWords >= Scale; ++
i, MaskWords -= Scale) {
892 BitWord BW =
Bits[
i];
894 for (
unsigned b = 0;
b != BITWORD_SIZE;
b += 32) {
896 if (InvertMask)
M = ~
M;
897 if (AddBits) BW |= BitWord(
M) <<
b;
898 else BW &= ~(BitWord(
M) <<
b);
902 for (
unsigned b = 0; MaskWords;
b += 32, --MaskWords) {
904 if (InvertMask)
M = ~
M;
905 if (AddBits)
Bits[
i] |= BitWord(
M) <<
b;
906 else Bits[
i] &= ~(BitWord(
M) <<
b);
919 return X.getMemorySize();
949 #endif // LLVM_ADT_BITVECTOR_H
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
reference operator[](unsigned Idx)
This class represents lattice values for constants.
const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
BitVector(const BitVector &RHS)
BitVector copy ctor.
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.
bool operator[](unsigned Idx) const
reference(BitVector &b, unsigned Idx)
ArrayRef< BitWord > getData() const
int find_last_unset_in(unsigned Begin, unsigned End) const
find_last_unset_in - Returns the index of the last unset bit in the range [Begin, End).
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
BitVector & operator|=(const BitVector &RHS)
bool none() const
none - Returns true if none of the bits are set.
iterator_range< const_set_bits_iterator > set_bits() const
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
reference & operator=(bool t)
static bool isEqual(const BitVector &LHS, const BitVector &RHS)
static BitVector getEmptyKey()
int find_next_unset(unsigned Prev) const
find_next_unset - Returns the index of the next unset bit following the "Prev" bit.
const_set_bits_iterator set_bits_begin() const
int find_first_in(unsigned Begin, unsigned End, bool Set=true) const
find_first_in - Returns the index of the first set / unset bit, depending on Set, in the range [Begin...
bool test(const BitVector &RHS) const
test - Check if (This - RHS) is zero.
unsigned countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
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.
BitVector & set(unsigned Idx)
int find_last() const
find_last - Returns the index of the last set bit, -1 if none of the bits are set.
bool operator==(const BitVector &RHS) const
bool operator!=(const const_set_bits_iterator_impl &Other) const
bool all() const
all - Returns true if all bits are set.
BitVector & operator^=(const BitVector &RHS)
int find_first_unset() const
find_first_unset - Returns the index of the first unset bit, -1 if all of the bits are set.
const_set_bits_iterator_impl(const BitVectorT &Parent)
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
BitVector()
BitVector default ctor - Creates an empty bitvector.
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.
void swap(BitVector &RHS)
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.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static unsigned getHashValue(const BitVector &V)
BitVector & operator<<=(unsigned N)
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
bool operator!=(const BitVector &RHS) const
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
bool empty() const
empty - Tests whether there are no bits in this bitvector.
unsigned countPopulation(T Value)
Count the number of set bits in a value.
BitVector & reset(unsigned Idx)
bool any() const
any - Returns true if any bit is set.
BitVector & reset(unsigned I, unsigned E)
reset - Efficiently reset a range of bits in [I, E)
multiplies can be turned into SHL s
BitVector & 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.
const_set_bits_iterator_impl operator++(int)
const_set_bits_iterator_impl & operator++()
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
const BitVector & operator=(BitVector &&RHS)
int find_last_in(unsigned Begin, unsigned End) const
find_last_in - Returns the index of the last set bit in the range [Begin, End).
support::ulittle32_t Word
size_t getMemorySize() const
Return the size (in bytes) of the bit vector.
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.
reference & operator=(reference t)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
size_t capacity_in_bytes(const BitVector &X)
this could be done in SelectionDAGISel along with other special for
BitVector & reset(const BitVector &RHS)
reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
BitVector & operator&=(const BitVector &RHS)
Intersection, union, disjoint union.
const_set_bits_iterator_impl< BitVector > const_set_bits_iterator
int find_prev_unset(unsigned PriorTo)
find_prev_unset - Returns the index of the first unset bit that precedes the bit at PriorTo.
bool test(unsigned Idx) const
BitVector(unsigned s, bool t=false)
BitVector ctor - Creates a bitvector of specified number of bits.
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsInMask - Add '1' bits from Mask to this vector.
MutableArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
const_set_bits_iterator set_bits_end() const
const_set_bits_iterator set_iterator
int find_last_unset() const
find_last_unset - Returns the index of the last unset bit, -1 if all of the 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.
const BitVector & operator=(const BitVector &RHS)
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)
BitVector & flip(unsigned Idx)
size_t getBitCapacity() const
static BitVector getTombstoneKey()
BitVector & set(unsigned I, unsigned E)
set - Efficiently set a range of bits in [I, E)
int find_first() const
find_first - Returns the index of the first set bit, -1 if none of the bits are set.
A range adaptor for a pair of iterators.
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
bool operator==(const const_set_bits_iterator_impl &Other) const
#define LLVM_UNLIKELY(EXPR)
ForwardIterator for the bits that are set.
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
BitVector(BitVector &&RHS)
Optional< std::vector< StOtherPiece > > Other
int find_first_unset_in(unsigned Begin, unsigned End) const
find_first_unset_in - Returns the index of the first unset bit in the range [Begin,...
unsigned operator*() const