Go to the documentation of this file.
14 #ifndef LLVM_ADT_BITVECTOR_H
15 #define LLVM_ADT_BITVECTOR_H
34 const BitVectorT &Parent;
38 assert(Current != -1 &&
"Trying to advance past end.");
39 Current = Parent.find_next(Current);
44 : Parent(Parent), Current(Current) {}
64 "Comparing iterators from different BitVectors");
65 return Current ==
Other.Current;
70 "Comparing iterators from different BitVectors");
71 return Current !=
Other.Current;
76 typedef uintptr_t BitWord;
78 enum { BITWORD_SIZE = (unsigned)
sizeof(BitWord) * CHAR_BIT };
80 static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
81 "Unsupported word size");
99 WordRef = &
b.Bits[Idx / BITWORD_SIZE];
100 BitPos = Idx % BITWORD_SIZE;
113 *WordRef |= BitWord(1) << BitPos;
115 *WordRef &= ~(BitWord(1) << BitPos);
119 operator bool()
const {
120 return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
143 : Bits(NumBitWords(
s), 0 - (BitWord)
t), Size(
s) {
149 bool empty()
const {
return Size == 0; }
156 unsigned NumBits = 0;
157 for (
auto Bit : Bits)
164 return any_of(Bits, [](BitWord
Bit) {
return Bit != 0; });
169 for (
unsigned i = 0;
i < Size / BITWORD_SIZE; ++
i)
170 if (Bits[
i] != ~BitWord(0))
174 if (
unsigned Remainder = Size % BITWORD_SIZE)
175 return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
189 assert(Begin <= End && End <= Size);
193 unsigned FirstWord = Begin / BITWORD_SIZE;
194 unsigned LastWord = (End - 1) / BITWORD_SIZE;
201 for (
unsigned i = FirstWord;
i <= LastWord; ++
i) {
202 BitWord Copy = Bits[
i];
206 if (
i == FirstWord) {
207 unsigned FirstBit = Begin % BITWORD_SIZE;
208 Copy &= maskTrailingZeros<BitWord>(FirstBit);
212 unsigned LastBit = (End - 1) % BITWORD_SIZE;
213 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
224 assert(Begin <= End && End <= Size);
228 unsigned LastWord = (End - 1) / BITWORD_SIZE;
229 unsigned FirstWord = Begin / BITWORD_SIZE;
231 for (
unsigned i = LastWord + 1;
i >= FirstWord + 1; --
i) {
232 unsigned CurrentWord =
i - 1;
234 BitWord Copy = Bits[CurrentWord];
235 if (CurrentWord == LastWord) {
236 unsigned LastBit = (End - 1) % BITWORD_SIZE;
237 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
240 if (CurrentWord == FirstWord) {
241 unsigned FirstBit = Begin % BITWORD_SIZE;
242 Copy &= maskTrailingZeros<BitWord>(FirstBit);
261 assert(Begin <= End && End <= Size);
265 unsigned LastWord = (End - 1) / BITWORD_SIZE;
266 unsigned FirstWord = Begin / BITWORD_SIZE;
268 for (
unsigned i = LastWord + 1;
i >= FirstWord + 1; --
i) {
269 unsigned CurrentWord =
i - 1;
271 BitWord Copy = Bits[CurrentWord];
272 if (CurrentWord == LastWord) {
273 unsigned LastBit = (End - 1) % BITWORD_SIZE;
274 Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
277 if (CurrentWord == FirstWord) {
278 unsigned FirstBit = Begin % BITWORD_SIZE;
279 Copy |= maskTrailingOnes<BitWord>(FirstBit);
282 if (Copy != ~BitWord(0)) {
285 return Result < Size ? Result : -1;
337 Bits.resize(NumBitWords(
N), 0 - BitWord(
t));
341 void reserve(
unsigned N) { Bits.reserve(NumBitWords(
N)); }
351 assert(Idx < Size &&
"access in bound");
352 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
358 assert(
I <=
E &&
"Attempted to set backwards range!");
359 assert(
E <=
size() &&
"Attempted to set out-of-bounds range!");
361 if (
I ==
E)
return *
this;
363 if (
I / BITWORD_SIZE ==
E / BITWORD_SIZE) {
364 BitWord EMask = BitWord(1) << (
E % BITWORD_SIZE);
365 BitWord IMask = BitWord(1) << (
I % BITWORD_SIZE);
366 BitWord
Mask = EMask - IMask;
367 Bits[
I / BITWORD_SIZE] |=
Mask;
371 BitWord PrefixMask = ~BitWord(0) << (
I % BITWORD_SIZE);
372 Bits[
I / BITWORD_SIZE] |= PrefixMask;
375 for (;
I + BITWORD_SIZE <=
E;
I += BITWORD_SIZE)
376 Bits[
I / BITWORD_SIZE] = ~BitWord(0);
378 BitWord PostfixMask = (BitWord(1) << (
E % BITWORD_SIZE)) - 1;
380 Bits[
I / BITWORD_SIZE] |= PostfixMask;
391 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
397 assert(
I <=
E &&
"Attempted to reset backwards range!");
398 assert(
E <=
size() &&
"Attempted to reset out-of-bounds range!");
400 if (
I ==
E)
return *
this;
402 if (
I / BITWORD_SIZE ==
E / BITWORD_SIZE) {
403 BitWord EMask = BitWord(1) << (
E % BITWORD_SIZE);
404 BitWord IMask = BitWord(1) << (
I % BITWORD_SIZE);
405 BitWord
Mask = EMask - IMask;
406 Bits[
I / BITWORD_SIZE] &= ~
Mask;
410 BitWord PrefixMask = ~BitWord(0) << (
I % BITWORD_SIZE);
411 Bits[
I / BITWORD_SIZE] &= ~PrefixMask;
414 for (;
I + BITWORD_SIZE <=
E;
I += BITWORD_SIZE)
415 Bits[
I / BITWORD_SIZE] = BitWord(0);
417 BitWord PostfixMask = (BitWord(1) << (
E % BITWORD_SIZE)) - 1;
419 Bits[
I / BITWORD_SIZE] &= ~PostfixMask;
425 for (
auto &
Bit : Bits)
432 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
438 assert (Idx < Size &&
"Out-of-bounds Bit access.");
443 assert (Idx < Size &&
"Out-of-bounds Bit access.");
444 BitWord
Mask = BitWord(1) << (Idx % BITWORD_SIZE);
445 return (Bits[Idx / BITWORD_SIZE] &
Mask) != 0;
450 assert(!
empty() &&
"Getting last element of empty vector.");
451 return (*
this)[
size() - 1];
454 bool test(
unsigned Idx)
const {
460 unsigned OldSize = Size;
461 unsigned NewSize = Size + 1;
477 assert(!
empty() &&
"Empty vector has no element to pop.");
483 unsigned ThisWords = Bits.size();
484 unsigned RHSWords =
RHS.Bits.size();
485 for (
unsigned i = 0,
e =
std::min(ThisWords, RHSWords);
i !=
e; ++
i)
486 if (Bits[
i] &
RHS.Bits[
i])
495 unsigned NumWords = Bits.size();
496 return std::equal(Bits.begin(), Bits.begin() + NumWords,
RHS.Bits.begin());
503 unsigned ThisWords = Bits.size();
504 unsigned RHSWords =
RHS.Bits.size();
506 for (
i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
507 Bits[
i] &=
RHS.Bits[
i];
512 for (;
i != ThisWords; ++
i)
520 unsigned ThisWords = Bits.size();
521 unsigned RHSWords =
RHS.Bits.size();
522 for (
unsigned i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
523 Bits[
i] &= ~
RHS.Bits[
i];
530 unsigned ThisWords = Bits.size();
531 unsigned RHSWords =
RHS.Bits.size();
533 for (
i = 0;
i !=
std::min(ThisWords, RHSWords); ++
i)
534 if ((Bits[
i] & ~
RHS.Bits[
i]) != 0)
537 for (;
i != ThisWords ; ++
i)
544 template <
class F,
class... ArgTys>
546 ArgTys
const &...
Args) {
548 std::initializer_list<unsigned>{
Args.size()...},
549 [&
Arg](
auto const &BV) {
return Arg.size() == BV; }) &&
554 Out.clear_unused_bits();
562 Bits[
I] |=
RHS.Bits[
I];
570 Bits[
I] ^=
RHS.Bits[
I];
579 unsigned NumWords = Bits.size();
582 wordShr(
N / BITWORD_SIZE);
584 unsigned BitDistance =
N % BITWORD_SIZE;
585 if (BitDistance == 0)
610 const BitWord
Mask = maskTrailingOnes<BitWord>(BitDistance);
611 const unsigned LSH = BITWORD_SIZE - BitDistance;
613 for (
unsigned I = 0;
I < NumWords - 1; ++
I) {
614 Bits[
I] >>= BitDistance;
615 Bits[
I] |= (Bits[
I + 1] &
Mask) << LSH;
618 Bits[NumWords - 1] >>= BitDistance;
628 unsigned NumWords = Bits.size();
631 wordShl(
N / BITWORD_SIZE);
633 unsigned BitDistance =
N % BITWORD_SIZE;
634 if (BitDistance == 0)
660 const BitWord
Mask = maskLeadingOnes<BitWord>(BitDistance);
661 const unsigned RSH = BITWORD_SIZE - BitDistance;
663 for (
int I = NumWords - 1;
I > 0; --
I) {
664 Bits[
I] <<= BitDistance;
665 Bits[
I] |= (Bits[
I - 1] &
Mask) >> RSH;
667 Bits[0] <<= BitDistance;
679 assert(!Size && Bits.empty());
701 applyMask<true, false>(
Mask, MaskWords);
707 applyMask<false, false>(
Mask, MaskWords);
713 applyMask<true, true>(
Mask, MaskWords);
719 applyMask<false, true>(
Mask, MaskWords);
746 std::copy(Bits.begin(), Bits.begin() + NumWords - Count,
747 Bits.begin() + Count);
748 std::fill(Bits.begin(), Bits.begin() + Count, 0);
761 std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin());
762 std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0);
765 int next_unset_in_word(
int WordIndex, BitWord
Word)
const {
770 unsigned NumBitWords(
unsigned S)
const {
771 return (
S + BITWORD_SIZE-1) / BITWORD_SIZE;
775 void set_unused_bits(
bool t =
true) {
777 if (
unsigned ExtraBits = Size % BITWORD_SIZE) {
778 BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
780 Bits.back() |= ExtraBitMask;
782 Bits.back() &= ~ExtraBitMask;
787 void clear_unused_bits() {
788 set_unused_bits(
false);
791 void init_words(
bool t) {
792 std::fill(
Bits.begin(),
Bits.end(), 0 - (BitWord)
t);
795 template<
bool AddBits,
bool InvertMask>
796 void applyMask(
const uint32_t *
Mask,
unsigned MaskWords) {
797 static_assert(BITWORD_SIZE % 32 == 0,
"Unsupported BitWord size.");
799 const unsigned Scale = BITWORD_SIZE / 32;
801 for (
i = 0; MaskWords >= Scale; ++
i, MaskWords -= Scale) {
802 BitWord BW =
Bits[
i];
804 for (
unsigned b = 0;
b != BITWORD_SIZE;
b += 32) {
806 if (InvertMask)
M = ~
M;
807 if (AddBits) BW |= BitWord(M) <<
b;
808 else BW &= ~(BitWord(M) <<
b);
812 for (
unsigned b = 0; MaskWords;
b += 32, --MaskWords) {
814 if (InvertMask)
M = ~
M;
815 if (AddBits)
Bits[
i] |= BitWord(M) <<
b;
816 else Bits[
i] &= ~(BitWord(M) <<
b);
829 return X.getMemorySize();
841 getHashValue(std::make_pair(V.
size(), V.
getData()));
844 if (
LHS.isInvalid() ||
RHS.isInvalid())
845 return LHS.isInvalid() ==
RHS.isInvalid();
856 #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)
void pop_back()
Pop one bit from the end of the vector.
This is an optimization pass for GlobalISel generic memory operations.
const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
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.
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
BitVector::size_type capacity_in_bytes(const BitVector &X)
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.
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
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
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...
BitVector & operator^=(const BitVector &RHS)
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
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)
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
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.
size_type getMemorySize() const
Return the size (in bytes) of the bit vector.
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.
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
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
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
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.
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.
size_type getBitCapacity() const
BitVector & flip(unsigned Idx)
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
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
#define LLVM_UNLIKELY(EXPR)
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
static BitVector & apply(F &&f, BitVector &Out, BitVector const &Arg, ArgTys const &...Args)
bool back() const
Return the last element in the vector.
ForwardIterator for the bits that are set.
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