106f32e7eSjoerg //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file implements the BitVector class.
1006f32e7eSjoerg //
1106f32e7eSjoerg //===----------------------------------------------------------------------===//
1206f32e7eSjoerg
1306f32e7eSjoerg #ifndef LLVM_ADT_BITVECTOR_H
1406f32e7eSjoerg #define LLVM_ADT_BITVECTOR_H
1506f32e7eSjoerg
1606f32e7eSjoerg #include "llvm/ADT/ArrayRef.h"
17*da58b97aSjoerg #include "llvm/ADT/DenseMapInfo.h"
1806f32e7eSjoerg #include "llvm/ADT/iterator_range.h"
1906f32e7eSjoerg #include "llvm/Support/MathExtras.h"
2006f32e7eSjoerg #include <algorithm>
2106f32e7eSjoerg #include <cassert>
2206f32e7eSjoerg #include <climits>
2306f32e7eSjoerg #include <cstdint>
2406f32e7eSjoerg #include <cstdlib>
2506f32e7eSjoerg #include <cstring>
2606f32e7eSjoerg #include <utility>
2706f32e7eSjoerg
2806f32e7eSjoerg namespace llvm {
2906f32e7eSjoerg
3006f32e7eSjoerg /// ForwardIterator for the bits that are set.
3106f32e7eSjoerg /// Iterators get invalidated when resize / reserve is called.
3206f32e7eSjoerg template <typename BitVectorT> class const_set_bits_iterator_impl {
3306f32e7eSjoerg const BitVectorT &Parent;
3406f32e7eSjoerg int Current = 0;
3506f32e7eSjoerg
advance()3606f32e7eSjoerg void advance() {
3706f32e7eSjoerg assert(Current != -1 && "Trying to advance past end.");
3806f32e7eSjoerg Current = Parent.find_next(Current);
3906f32e7eSjoerg }
4006f32e7eSjoerg
4106f32e7eSjoerg public:
const_set_bits_iterator_impl(const BitVectorT & Parent,int Current)4206f32e7eSjoerg const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
4306f32e7eSjoerg : Parent(Parent), Current(Current) {}
const_set_bits_iterator_impl(const BitVectorT & Parent)4406f32e7eSjoerg explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
4506f32e7eSjoerg : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
4606f32e7eSjoerg const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
4706f32e7eSjoerg
4806f32e7eSjoerg const_set_bits_iterator_impl operator++(int) {
4906f32e7eSjoerg auto Prev = *this;
5006f32e7eSjoerg advance();
5106f32e7eSjoerg return Prev;
5206f32e7eSjoerg }
5306f32e7eSjoerg
5406f32e7eSjoerg const_set_bits_iterator_impl &operator++() {
5506f32e7eSjoerg advance();
5606f32e7eSjoerg return *this;
5706f32e7eSjoerg }
5806f32e7eSjoerg
5906f32e7eSjoerg unsigned operator*() const { return Current; }
6006f32e7eSjoerg
6106f32e7eSjoerg bool operator==(const const_set_bits_iterator_impl &Other) const {
6206f32e7eSjoerg assert(&Parent == &Other.Parent &&
6306f32e7eSjoerg "Comparing iterators from different BitVectors");
6406f32e7eSjoerg return Current == Other.Current;
6506f32e7eSjoerg }
6606f32e7eSjoerg
6706f32e7eSjoerg bool operator!=(const const_set_bits_iterator_impl &Other) const {
6806f32e7eSjoerg assert(&Parent == &Other.Parent &&
6906f32e7eSjoerg "Comparing iterators from different BitVectors");
7006f32e7eSjoerg return Current != Other.Current;
7106f32e7eSjoerg }
7206f32e7eSjoerg };
7306f32e7eSjoerg
7406f32e7eSjoerg class BitVector {
75*da58b97aSjoerg typedef uintptr_t BitWord;
7606f32e7eSjoerg
7706f32e7eSjoerg enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
7806f32e7eSjoerg
7906f32e7eSjoerg static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
8006f32e7eSjoerg "Unsupported word size");
8106f32e7eSjoerg
82*da58b97aSjoerg using Storage = SmallVector<BitWord>;
83*da58b97aSjoerg
84*da58b97aSjoerg Storage Bits; // Actual bits.
8506f32e7eSjoerg unsigned Size; // Size of bitvector in bits.
8606f32e7eSjoerg
8706f32e7eSjoerg public:
8806f32e7eSjoerg typedef unsigned size_type;
89*da58b97aSjoerg
9006f32e7eSjoerg // Encapsulation of a single bit.
9106f32e7eSjoerg class reference {
9206f32e7eSjoerg
9306f32e7eSjoerg BitWord *WordRef;
9406f32e7eSjoerg unsigned BitPos;
9506f32e7eSjoerg
9606f32e7eSjoerg public:
reference(BitVector & b,unsigned Idx)9706f32e7eSjoerg reference(BitVector &b, unsigned Idx) {
9806f32e7eSjoerg WordRef = &b.Bits[Idx / BITWORD_SIZE];
9906f32e7eSjoerg BitPos = Idx % BITWORD_SIZE;
10006f32e7eSjoerg }
10106f32e7eSjoerg
10206f32e7eSjoerg reference() = delete;
10306f32e7eSjoerg reference(const reference&) = default;
10406f32e7eSjoerg
10506f32e7eSjoerg reference &operator=(reference t) {
10606f32e7eSjoerg *this = bool(t);
10706f32e7eSjoerg return *this;
10806f32e7eSjoerg }
10906f32e7eSjoerg
11006f32e7eSjoerg reference& operator=(bool t) {
11106f32e7eSjoerg if (t)
11206f32e7eSjoerg *WordRef |= BitWord(1) << BitPos;
11306f32e7eSjoerg else
11406f32e7eSjoerg *WordRef &= ~(BitWord(1) << BitPos);
11506f32e7eSjoerg return *this;
11606f32e7eSjoerg }
11706f32e7eSjoerg
11806f32e7eSjoerg operator bool() const {
11906f32e7eSjoerg return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
12006f32e7eSjoerg }
12106f32e7eSjoerg };
12206f32e7eSjoerg
12306f32e7eSjoerg typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
12406f32e7eSjoerg typedef const_set_bits_iterator set_iterator;
12506f32e7eSjoerg
set_bits_begin()12606f32e7eSjoerg const_set_bits_iterator set_bits_begin() const {
12706f32e7eSjoerg return const_set_bits_iterator(*this);
12806f32e7eSjoerg }
set_bits_end()12906f32e7eSjoerg const_set_bits_iterator set_bits_end() const {
13006f32e7eSjoerg return const_set_bits_iterator(*this, -1);
13106f32e7eSjoerg }
set_bits()13206f32e7eSjoerg iterator_range<const_set_bits_iterator> set_bits() const {
13306f32e7eSjoerg return make_range(set_bits_begin(), set_bits_end());
13406f32e7eSjoerg }
13506f32e7eSjoerg
13606f32e7eSjoerg /// BitVector default ctor - Creates an empty bitvector.
BitVector()13706f32e7eSjoerg BitVector() : Size(0) {}
13806f32e7eSjoerg
13906f32e7eSjoerg /// BitVector ctor - Creates a bitvector of specified number of bits. All
14006f32e7eSjoerg /// bits are initialized to the specified value.
141*da58b97aSjoerg explicit BitVector(unsigned s, bool t = false)
NumBitWords(s)142*da58b97aSjoerg : Bits(NumBitWords(s), 0 - (BitWord)t), Size(s) {
14306f32e7eSjoerg if (t)
14406f32e7eSjoerg clear_unused_bits();
14506f32e7eSjoerg }
14606f32e7eSjoerg
14706f32e7eSjoerg /// empty - Tests whether there are no bits in this bitvector.
empty()14806f32e7eSjoerg bool empty() const { return Size == 0; }
14906f32e7eSjoerg
15006f32e7eSjoerg /// size - Returns the number of bits in this bitvector.
size()15106f32e7eSjoerg size_type size() const { return Size; }
15206f32e7eSjoerg
15306f32e7eSjoerg /// count - Returns the number of bits which are set.
count()15406f32e7eSjoerg size_type count() const {
15506f32e7eSjoerg unsigned NumBits = 0;
156*da58b97aSjoerg for (auto Bit : Bits)
157*da58b97aSjoerg NumBits += countPopulation(Bit);
15806f32e7eSjoerg return NumBits;
15906f32e7eSjoerg }
16006f32e7eSjoerg
16106f32e7eSjoerg /// any - Returns true if any bit is set.
any()16206f32e7eSjoerg bool any() const {
163*da58b97aSjoerg return any_of(Bits, [](BitWord Bit) { return Bit != 0; });
16406f32e7eSjoerg }
16506f32e7eSjoerg
16606f32e7eSjoerg /// all - Returns true if all bits are set.
all()16706f32e7eSjoerg bool all() const {
16806f32e7eSjoerg for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
169*da58b97aSjoerg if (Bits[i] != ~BitWord(0))
17006f32e7eSjoerg return false;
17106f32e7eSjoerg
17206f32e7eSjoerg // If bits remain check that they are ones. The unused bits are always zero.
17306f32e7eSjoerg if (unsigned Remainder = Size % BITWORD_SIZE)
174*da58b97aSjoerg return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
17506f32e7eSjoerg
17606f32e7eSjoerg return true;
17706f32e7eSjoerg }
17806f32e7eSjoerg
17906f32e7eSjoerg /// none - Returns true if none of the bits are set.
none()18006f32e7eSjoerg bool none() const {
18106f32e7eSjoerg return !any();
18206f32e7eSjoerg }
18306f32e7eSjoerg
184*da58b97aSjoerg /// find_first_in - Returns the index of the first set / unset bit,
185*da58b97aSjoerg /// depending on \p Set, in the range [Begin, End).
186*da58b97aSjoerg /// Returns -1 if all bits in the range are unset / set.
187*da58b97aSjoerg int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
18806f32e7eSjoerg assert(Begin <= End && End <= Size);
18906f32e7eSjoerg if (Begin == End)
19006f32e7eSjoerg return -1;
19106f32e7eSjoerg
19206f32e7eSjoerg unsigned FirstWord = Begin / BITWORD_SIZE;
19306f32e7eSjoerg unsigned LastWord = (End - 1) / BITWORD_SIZE;
19406f32e7eSjoerg
19506f32e7eSjoerg // Check subsequent words.
196*da58b97aSjoerg // The code below is based on search for the first _set_ bit. If
197*da58b97aSjoerg // we're searching for the first _unset_, we just take the
198*da58b97aSjoerg // complement of each word before we use it and apply
199*da58b97aSjoerg // the same method.
20006f32e7eSjoerg for (unsigned i = FirstWord; i <= LastWord; ++i) {
20106f32e7eSjoerg BitWord Copy = Bits[i];
202*da58b97aSjoerg if (!Set)
203*da58b97aSjoerg Copy = ~Copy;
20406f32e7eSjoerg
20506f32e7eSjoerg if (i == FirstWord) {
20606f32e7eSjoerg unsigned FirstBit = Begin % BITWORD_SIZE;
20706f32e7eSjoerg Copy &= maskTrailingZeros<BitWord>(FirstBit);
20806f32e7eSjoerg }
20906f32e7eSjoerg
21006f32e7eSjoerg if (i == LastWord) {
21106f32e7eSjoerg unsigned LastBit = (End - 1) % BITWORD_SIZE;
21206f32e7eSjoerg Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
21306f32e7eSjoerg }
21406f32e7eSjoerg if (Copy != 0)
21506f32e7eSjoerg return i * BITWORD_SIZE + countTrailingZeros(Copy);
21606f32e7eSjoerg }
21706f32e7eSjoerg return -1;
21806f32e7eSjoerg }
21906f32e7eSjoerg
22006f32e7eSjoerg /// find_last_in - Returns the index of the last set bit in the range
22106f32e7eSjoerg /// [Begin, End). Returns -1 if all bits in the range are unset.
find_last_in(unsigned Begin,unsigned End)22206f32e7eSjoerg int find_last_in(unsigned Begin, unsigned End) const {
22306f32e7eSjoerg assert(Begin <= End && End <= Size);
22406f32e7eSjoerg if (Begin == End)
22506f32e7eSjoerg return -1;
22606f32e7eSjoerg
22706f32e7eSjoerg unsigned LastWord = (End - 1) / BITWORD_SIZE;
22806f32e7eSjoerg unsigned FirstWord = Begin / BITWORD_SIZE;
22906f32e7eSjoerg
23006f32e7eSjoerg for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
23106f32e7eSjoerg unsigned CurrentWord = i - 1;
23206f32e7eSjoerg
23306f32e7eSjoerg BitWord Copy = Bits[CurrentWord];
23406f32e7eSjoerg if (CurrentWord == LastWord) {
23506f32e7eSjoerg unsigned LastBit = (End - 1) % BITWORD_SIZE;
23606f32e7eSjoerg Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
23706f32e7eSjoerg }
23806f32e7eSjoerg
23906f32e7eSjoerg if (CurrentWord == FirstWord) {
24006f32e7eSjoerg unsigned FirstBit = Begin % BITWORD_SIZE;
24106f32e7eSjoerg Copy &= maskTrailingZeros<BitWord>(FirstBit);
24206f32e7eSjoerg }
24306f32e7eSjoerg
24406f32e7eSjoerg if (Copy != 0)
24506f32e7eSjoerg return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
24606f32e7eSjoerg }
24706f32e7eSjoerg
24806f32e7eSjoerg return -1;
24906f32e7eSjoerg }
25006f32e7eSjoerg
25106f32e7eSjoerg /// find_first_unset_in - Returns the index of the first unset bit in the
25206f32e7eSjoerg /// range [Begin, End). Returns -1 if all bits in the range are set.
find_first_unset_in(unsigned Begin,unsigned End)25306f32e7eSjoerg int find_first_unset_in(unsigned Begin, unsigned End) const {
254*da58b97aSjoerg return find_first_in(Begin, End, /* Set = */ false);
25506f32e7eSjoerg }
25606f32e7eSjoerg
25706f32e7eSjoerg /// find_last_unset_in - Returns the index of the last unset bit in the
25806f32e7eSjoerg /// range [Begin, End). Returns -1 if all bits in the range are set.
find_last_unset_in(unsigned Begin,unsigned End)25906f32e7eSjoerg int find_last_unset_in(unsigned Begin, unsigned End) const {
26006f32e7eSjoerg assert(Begin <= End && End <= Size);
26106f32e7eSjoerg if (Begin == End)
26206f32e7eSjoerg return -1;
26306f32e7eSjoerg
26406f32e7eSjoerg unsigned LastWord = (End - 1) / BITWORD_SIZE;
26506f32e7eSjoerg unsigned FirstWord = Begin / BITWORD_SIZE;
26606f32e7eSjoerg
26706f32e7eSjoerg for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
26806f32e7eSjoerg unsigned CurrentWord = i - 1;
26906f32e7eSjoerg
27006f32e7eSjoerg BitWord Copy = Bits[CurrentWord];
27106f32e7eSjoerg if (CurrentWord == LastWord) {
27206f32e7eSjoerg unsigned LastBit = (End - 1) % BITWORD_SIZE;
27306f32e7eSjoerg Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
27406f32e7eSjoerg }
27506f32e7eSjoerg
27606f32e7eSjoerg if (CurrentWord == FirstWord) {
27706f32e7eSjoerg unsigned FirstBit = Begin % BITWORD_SIZE;
27806f32e7eSjoerg Copy |= maskTrailingOnes<BitWord>(FirstBit);
27906f32e7eSjoerg }
28006f32e7eSjoerg
281*da58b97aSjoerg if (Copy != ~BitWord(0)) {
28206f32e7eSjoerg unsigned Result =
28306f32e7eSjoerg (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
28406f32e7eSjoerg return Result < Size ? Result : -1;
28506f32e7eSjoerg }
28606f32e7eSjoerg }
28706f32e7eSjoerg return -1;
28806f32e7eSjoerg }
28906f32e7eSjoerg
29006f32e7eSjoerg /// find_first - Returns the index of the first set bit, -1 if none
29106f32e7eSjoerg /// of the bits are set.
find_first()29206f32e7eSjoerg int find_first() const { return find_first_in(0, Size); }
29306f32e7eSjoerg
29406f32e7eSjoerg /// find_last - Returns the index of the last set bit, -1 if none of the bits
29506f32e7eSjoerg /// are set.
find_last()29606f32e7eSjoerg int find_last() const { return find_last_in(0, Size); }
29706f32e7eSjoerg
29806f32e7eSjoerg /// find_next - Returns the index of the next set bit following the
29906f32e7eSjoerg /// "Prev" bit. Returns -1 if the next set bit is not found.
find_next(unsigned Prev)30006f32e7eSjoerg int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
30106f32e7eSjoerg
30206f32e7eSjoerg /// find_prev - Returns the index of the first set bit that precedes the
30306f32e7eSjoerg /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
find_prev(unsigned PriorTo)30406f32e7eSjoerg int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
30506f32e7eSjoerg
30606f32e7eSjoerg /// find_first_unset - Returns the index of the first unset bit, -1 if all
30706f32e7eSjoerg /// of the bits are set.
find_first_unset()30806f32e7eSjoerg int find_first_unset() const { return find_first_unset_in(0, Size); }
30906f32e7eSjoerg
31006f32e7eSjoerg /// find_next_unset - Returns the index of the next unset bit following the
31106f32e7eSjoerg /// "Prev" bit. Returns -1 if all remaining bits are set.
find_next_unset(unsigned Prev)31206f32e7eSjoerg int find_next_unset(unsigned Prev) const {
31306f32e7eSjoerg return find_first_unset_in(Prev + 1, Size);
31406f32e7eSjoerg }
31506f32e7eSjoerg
31606f32e7eSjoerg /// find_last_unset - Returns the index of the last unset bit, -1 if all of
31706f32e7eSjoerg /// the bits are set.
find_last_unset()31806f32e7eSjoerg int find_last_unset() const { return find_last_unset_in(0, Size); }
31906f32e7eSjoerg
32006f32e7eSjoerg /// find_prev_unset - Returns the index of the first unset bit that precedes
32106f32e7eSjoerg /// the bit at \p PriorTo. Returns -1 if all previous bits are set.
find_prev_unset(unsigned PriorTo)32206f32e7eSjoerg int find_prev_unset(unsigned PriorTo) {
32306f32e7eSjoerg return find_last_unset_in(0, PriorTo);
32406f32e7eSjoerg }
32506f32e7eSjoerg
326*da58b97aSjoerg /// clear - Removes all bits from the bitvector.
clear()32706f32e7eSjoerg void clear() {
32806f32e7eSjoerg Size = 0;
329*da58b97aSjoerg Bits.clear();
33006f32e7eSjoerg }
33106f32e7eSjoerg
33206f32e7eSjoerg /// resize - Grow or shrink the bitvector.
33306f32e7eSjoerg void resize(unsigned N, bool t = false) {
33406f32e7eSjoerg set_unused_bits(t);
33506f32e7eSjoerg Size = N;
336*da58b97aSjoerg Bits.resize(NumBitWords(N), 0 - BitWord(t));
33706f32e7eSjoerg clear_unused_bits();
33806f32e7eSjoerg }
33906f32e7eSjoerg
reserve(unsigned N)340*da58b97aSjoerg void reserve(unsigned N) { Bits.reserve(NumBitWords(N)); }
34106f32e7eSjoerg
34206f32e7eSjoerg // Set, reset, flip
set()34306f32e7eSjoerg BitVector &set() {
344*da58b97aSjoerg init_words(true);
34506f32e7eSjoerg clear_unused_bits();
34606f32e7eSjoerg return *this;
34706f32e7eSjoerg }
34806f32e7eSjoerg
set(unsigned Idx)34906f32e7eSjoerg BitVector &set(unsigned Idx) {
350*da58b97aSjoerg assert(Idx < Size && "access in bound");
35106f32e7eSjoerg Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
35206f32e7eSjoerg return *this;
35306f32e7eSjoerg }
35406f32e7eSjoerg
35506f32e7eSjoerg /// set - Efficiently set a range of bits in [I, E)
set(unsigned I,unsigned E)35606f32e7eSjoerg BitVector &set(unsigned I, unsigned E) {
35706f32e7eSjoerg assert(I <= E && "Attempted to set backwards range!");
35806f32e7eSjoerg assert(E <= size() && "Attempted to set out-of-bounds range!");
35906f32e7eSjoerg
36006f32e7eSjoerg if (I == E) return *this;
36106f32e7eSjoerg
36206f32e7eSjoerg if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
363*da58b97aSjoerg BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
364*da58b97aSjoerg BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
36506f32e7eSjoerg BitWord Mask = EMask - IMask;
36606f32e7eSjoerg Bits[I / BITWORD_SIZE] |= Mask;
36706f32e7eSjoerg return *this;
36806f32e7eSjoerg }
36906f32e7eSjoerg
370*da58b97aSjoerg BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
37106f32e7eSjoerg Bits[I / BITWORD_SIZE] |= PrefixMask;
37206f32e7eSjoerg I = alignTo(I, BITWORD_SIZE);
37306f32e7eSjoerg
37406f32e7eSjoerg for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
375*da58b97aSjoerg Bits[I / BITWORD_SIZE] = ~BitWord(0);
37606f32e7eSjoerg
377*da58b97aSjoerg BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
37806f32e7eSjoerg if (I < E)
37906f32e7eSjoerg Bits[I / BITWORD_SIZE] |= PostfixMask;
38006f32e7eSjoerg
38106f32e7eSjoerg return *this;
38206f32e7eSjoerg }
38306f32e7eSjoerg
reset()38406f32e7eSjoerg BitVector &reset() {
385*da58b97aSjoerg init_words(false);
38606f32e7eSjoerg return *this;
38706f32e7eSjoerg }
38806f32e7eSjoerg
reset(unsigned Idx)38906f32e7eSjoerg BitVector &reset(unsigned Idx) {
39006f32e7eSjoerg Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
39106f32e7eSjoerg return *this;
39206f32e7eSjoerg }
39306f32e7eSjoerg
39406f32e7eSjoerg /// reset - Efficiently reset a range of bits in [I, E)
reset(unsigned I,unsigned E)39506f32e7eSjoerg BitVector &reset(unsigned I, unsigned E) {
39606f32e7eSjoerg assert(I <= E && "Attempted to reset backwards range!");
39706f32e7eSjoerg assert(E <= size() && "Attempted to reset out-of-bounds range!");
39806f32e7eSjoerg
39906f32e7eSjoerg if (I == E) return *this;
40006f32e7eSjoerg
40106f32e7eSjoerg if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
402*da58b97aSjoerg BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
403*da58b97aSjoerg BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
40406f32e7eSjoerg BitWord Mask = EMask - IMask;
40506f32e7eSjoerg Bits[I / BITWORD_SIZE] &= ~Mask;
40606f32e7eSjoerg return *this;
40706f32e7eSjoerg }
40806f32e7eSjoerg
409*da58b97aSjoerg BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
41006f32e7eSjoerg Bits[I / BITWORD_SIZE] &= ~PrefixMask;
41106f32e7eSjoerg I = alignTo(I, BITWORD_SIZE);
41206f32e7eSjoerg
41306f32e7eSjoerg for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
414*da58b97aSjoerg Bits[I / BITWORD_SIZE] = BitWord(0);
41506f32e7eSjoerg
416*da58b97aSjoerg BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
41706f32e7eSjoerg if (I < E)
41806f32e7eSjoerg Bits[I / BITWORD_SIZE] &= ~PostfixMask;
41906f32e7eSjoerg
42006f32e7eSjoerg return *this;
42106f32e7eSjoerg }
42206f32e7eSjoerg
flip()42306f32e7eSjoerg BitVector &flip() {
424*da58b97aSjoerg for (auto &Bit : Bits)
425*da58b97aSjoerg Bit = ~Bit;
42606f32e7eSjoerg clear_unused_bits();
42706f32e7eSjoerg return *this;
42806f32e7eSjoerg }
42906f32e7eSjoerg
flip(unsigned Idx)43006f32e7eSjoerg BitVector &flip(unsigned Idx) {
43106f32e7eSjoerg Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
43206f32e7eSjoerg return *this;
43306f32e7eSjoerg }
43406f32e7eSjoerg
43506f32e7eSjoerg // Indexing.
43606f32e7eSjoerg reference operator[](unsigned Idx) {
43706f32e7eSjoerg assert (Idx < Size && "Out-of-bounds Bit access.");
43806f32e7eSjoerg return reference(*this, Idx);
43906f32e7eSjoerg }
44006f32e7eSjoerg
44106f32e7eSjoerg bool operator[](unsigned Idx) const {
44206f32e7eSjoerg assert (Idx < Size && "Out-of-bounds Bit access.");
44306f32e7eSjoerg BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
44406f32e7eSjoerg return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
44506f32e7eSjoerg }
44606f32e7eSjoerg
test(unsigned Idx)44706f32e7eSjoerg bool test(unsigned Idx) const {
44806f32e7eSjoerg return (*this)[Idx];
44906f32e7eSjoerg }
45006f32e7eSjoerg
45106f32e7eSjoerg // Push single bit to end of vector.
push_back(bool Val)45206f32e7eSjoerg void push_back(bool Val) {
45306f32e7eSjoerg unsigned OldSize = Size;
45406f32e7eSjoerg unsigned NewSize = Size + 1;
45506f32e7eSjoerg
45606f32e7eSjoerg // Resize, which will insert zeros.
45706f32e7eSjoerg // If we already fit then the unused bits will be already zero.
45806f32e7eSjoerg if (NewSize > getBitCapacity())
45906f32e7eSjoerg resize(NewSize, false);
46006f32e7eSjoerg else
46106f32e7eSjoerg Size = NewSize;
46206f32e7eSjoerg
46306f32e7eSjoerg // If true, set single bit.
46406f32e7eSjoerg if (Val)
46506f32e7eSjoerg set(OldSize);
46606f32e7eSjoerg }
46706f32e7eSjoerg
46806f32e7eSjoerg /// Test if any common bits are set.
anyCommon(const BitVector & RHS)46906f32e7eSjoerg bool anyCommon(const BitVector &RHS) const {
470*da58b97aSjoerg unsigned ThisWords = Bits.size();
471*da58b97aSjoerg unsigned RHSWords = RHS.Bits.size();
47206f32e7eSjoerg for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
47306f32e7eSjoerg if (Bits[i] & RHS.Bits[i])
47406f32e7eSjoerg return true;
47506f32e7eSjoerg return false;
47606f32e7eSjoerg }
47706f32e7eSjoerg
47806f32e7eSjoerg // Comparison operators.
47906f32e7eSjoerg bool operator==(const BitVector &RHS) const {
480*da58b97aSjoerg if (size() != RHS.size())
48106f32e7eSjoerg return false;
482*da58b97aSjoerg unsigned NumWords = Bits.size();
483*da58b97aSjoerg return std::equal(Bits.begin(), Bits.begin() + NumWords, RHS.Bits.begin());
48406f32e7eSjoerg }
48506f32e7eSjoerg
486*da58b97aSjoerg bool operator!=(const BitVector &RHS) const { return !(*this == RHS); }
48706f32e7eSjoerg
48806f32e7eSjoerg /// Intersection, union, disjoint union.
48906f32e7eSjoerg BitVector &operator&=(const BitVector &RHS) {
490*da58b97aSjoerg unsigned ThisWords = Bits.size();
491*da58b97aSjoerg unsigned RHSWords = RHS.Bits.size();
49206f32e7eSjoerg unsigned i;
49306f32e7eSjoerg for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
49406f32e7eSjoerg Bits[i] &= RHS.Bits[i];
49506f32e7eSjoerg
49606f32e7eSjoerg // Any bits that are just in this bitvector become zero, because they aren't
49706f32e7eSjoerg // in the RHS bit vector. Any words only in RHS are ignored because they
49806f32e7eSjoerg // are already zero in the LHS.
49906f32e7eSjoerg for (; i != ThisWords; ++i)
50006f32e7eSjoerg Bits[i] = 0;
50106f32e7eSjoerg
50206f32e7eSjoerg return *this;
50306f32e7eSjoerg }
50406f32e7eSjoerg
50506f32e7eSjoerg /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
reset(const BitVector & RHS)50606f32e7eSjoerg BitVector &reset(const BitVector &RHS) {
507*da58b97aSjoerg unsigned ThisWords = Bits.size();
508*da58b97aSjoerg unsigned RHSWords = RHS.Bits.size();
509*da58b97aSjoerg for (unsigned i = 0; i != std::min(ThisWords, RHSWords); ++i)
51006f32e7eSjoerg Bits[i] &= ~RHS.Bits[i];
51106f32e7eSjoerg return *this;
51206f32e7eSjoerg }
51306f32e7eSjoerg
51406f32e7eSjoerg /// test - Check if (This - RHS) is zero.
51506f32e7eSjoerg /// This is the same as reset(RHS) and any().
test(const BitVector & RHS)51606f32e7eSjoerg bool test(const BitVector &RHS) const {
517*da58b97aSjoerg unsigned ThisWords = Bits.size();
518*da58b97aSjoerg unsigned RHSWords = RHS.Bits.size();
51906f32e7eSjoerg unsigned i;
52006f32e7eSjoerg for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
52106f32e7eSjoerg if ((Bits[i] & ~RHS.Bits[i]) != 0)
52206f32e7eSjoerg return true;
52306f32e7eSjoerg
52406f32e7eSjoerg for (; i != ThisWords ; ++i)
52506f32e7eSjoerg if (Bits[i] != 0)
52606f32e7eSjoerg return true;
52706f32e7eSjoerg
52806f32e7eSjoerg return false;
52906f32e7eSjoerg }
53006f32e7eSjoerg
531*da58b97aSjoerg template <class F, class... ArgTys>
apply(F && f,BitVector & Out,BitVector const & Arg,ArgTys const &...Args)532*da58b97aSjoerg static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
533*da58b97aSjoerg ArgTys const &...Args) {
534*da58b97aSjoerg assert(llvm::all_of(
535*da58b97aSjoerg std::initializer_list<unsigned>{Args.size()...},
536*da58b97aSjoerg [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
537*da58b97aSjoerg "consistent sizes");
538*da58b97aSjoerg Out.resize(Arg.size());
539*da58b97aSjoerg for (size_t i = 0, e = Arg.Bits.size(); i != e; ++i)
540*da58b97aSjoerg Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...);
541*da58b97aSjoerg Out.clear_unused_bits();
542*da58b97aSjoerg return Out;
543*da58b97aSjoerg }
544*da58b97aSjoerg
54506f32e7eSjoerg BitVector &operator|=(const BitVector &RHS) {
54606f32e7eSjoerg if (size() < RHS.size())
54706f32e7eSjoerg resize(RHS.size());
548*da58b97aSjoerg for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
54906f32e7eSjoerg Bits[i] |= RHS.Bits[i];
55006f32e7eSjoerg return *this;
55106f32e7eSjoerg }
55206f32e7eSjoerg
55306f32e7eSjoerg BitVector &operator^=(const BitVector &RHS) {
55406f32e7eSjoerg if (size() < RHS.size())
55506f32e7eSjoerg resize(RHS.size());
556*da58b97aSjoerg for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
55706f32e7eSjoerg Bits[i] ^= RHS.Bits[i];
55806f32e7eSjoerg return *this;
55906f32e7eSjoerg }
56006f32e7eSjoerg
56106f32e7eSjoerg BitVector &operator>>=(unsigned N) {
56206f32e7eSjoerg assert(N <= Size);
56306f32e7eSjoerg if (LLVM_UNLIKELY(empty() || N == 0))
56406f32e7eSjoerg return *this;
56506f32e7eSjoerg
566*da58b97aSjoerg unsigned NumWords = Bits.size();
56706f32e7eSjoerg assert(NumWords >= 1);
56806f32e7eSjoerg
56906f32e7eSjoerg wordShr(N / BITWORD_SIZE);
57006f32e7eSjoerg
57106f32e7eSjoerg unsigned BitDistance = N % BITWORD_SIZE;
57206f32e7eSjoerg if (BitDistance == 0)
57306f32e7eSjoerg return *this;
57406f32e7eSjoerg
57506f32e7eSjoerg // When the shift size is not a multiple of the word size, then we have
57606f32e7eSjoerg // a tricky situation where each word in succession needs to extract some
57706f32e7eSjoerg // of the bits from the next word and or them into this word while
57806f32e7eSjoerg // shifting this word to make room for the new bits. This has to be done
57906f32e7eSjoerg // for every word in the array.
58006f32e7eSjoerg
58106f32e7eSjoerg // Since we're shifting each word right, some bits will fall off the end
58206f32e7eSjoerg // of each word to the right, and empty space will be created on the left.
58306f32e7eSjoerg // The final word in the array will lose bits permanently, so starting at
58406f32e7eSjoerg // the beginning, work forwards shifting each word to the right, and
58506f32e7eSjoerg // OR'ing in the bits from the end of the next word to the beginning of
58606f32e7eSjoerg // the current word.
58706f32e7eSjoerg
58806f32e7eSjoerg // Example:
58906f32e7eSjoerg // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
59006f32e7eSjoerg // by 4 bits.
59106f32e7eSjoerg // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
59206f32e7eSjoerg // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
59306f32e7eSjoerg // Step 3: Word[1] >>= 4 ; 0x0EEFF001
59406f32e7eSjoerg // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
59506f32e7eSjoerg // Step 5: Word[2] >>= 4 ; 0x02334455
59606f32e7eSjoerg // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
59706f32e7eSjoerg const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
59806f32e7eSjoerg const unsigned LSH = BITWORD_SIZE - BitDistance;
59906f32e7eSjoerg
60006f32e7eSjoerg for (unsigned I = 0; I < NumWords - 1; ++I) {
60106f32e7eSjoerg Bits[I] >>= BitDistance;
60206f32e7eSjoerg Bits[I] |= (Bits[I + 1] & Mask) << LSH;
60306f32e7eSjoerg }
60406f32e7eSjoerg
60506f32e7eSjoerg Bits[NumWords - 1] >>= BitDistance;
60606f32e7eSjoerg
60706f32e7eSjoerg return *this;
60806f32e7eSjoerg }
60906f32e7eSjoerg
61006f32e7eSjoerg BitVector &operator<<=(unsigned N) {
61106f32e7eSjoerg assert(N <= Size);
61206f32e7eSjoerg if (LLVM_UNLIKELY(empty() || N == 0))
61306f32e7eSjoerg return *this;
61406f32e7eSjoerg
615*da58b97aSjoerg unsigned NumWords = Bits.size();
61606f32e7eSjoerg assert(NumWords >= 1);
61706f32e7eSjoerg
61806f32e7eSjoerg wordShl(N / BITWORD_SIZE);
61906f32e7eSjoerg
62006f32e7eSjoerg unsigned BitDistance = N % BITWORD_SIZE;
62106f32e7eSjoerg if (BitDistance == 0)
62206f32e7eSjoerg return *this;
62306f32e7eSjoerg
62406f32e7eSjoerg // When the shift size is not a multiple of the word size, then we have
62506f32e7eSjoerg // a tricky situation where each word in succession needs to extract some
62606f32e7eSjoerg // of the bits from the previous word and or them into this word while
62706f32e7eSjoerg // shifting this word to make room for the new bits. This has to be done
62806f32e7eSjoerg // for every word in the array. This is similar to the algorithm outlined
62906f32e7eSjoerg // in operator>>=, but backwards.
63006f32e7eSjoerg
63106f32e7eSjoerg // Since we're shifting each word left, some bits will fall off the end
63206f32e7eSjoerg // of each word to the left, and empty space will be created on the right.
63306f32e7eSjoerg // The first word in the array will lose bits permanently, so starting at
63406f32e7eSjoerg // the end, work backwards shifting each word to the left, and OR'ing
63506f32e7eSjoerg // in the bits from the end of the next word to the beginning of the
63606f32e7eSjoerg // current word.
63706f32e7eSjoerg
63806f32e7eSjoerg // Example:
63906f32e7eSjoerg // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
64006f32e7eSjoerg // by 4 bits.
64106f32e7eSjoerg // Step 1: Word[2] <<= 4 ; 0x23344550
64206f32e7eSjoerg // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
64306f32e7eSjoerg // Step 3: Word[1] <<= 4 ; 0xEFF00110
64406f32e7eSjoerg // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
64506f32e7eSjoerg // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
64606f32e7eSjoerg // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
64706f32e7eSjoerg const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
64806f32e7eSjoerg const unsigned RSH = BITWORD_SIZE - BitDistance;
64906f32e7eSjoerg
65006f32e7eSjoerg for (int I = NumWords - 1; I > 0; --I) {
65106f32e7eSjoerg Bits[I] <<= BitDistance;
65206f32e7eSjoerg Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
65306f32e7eSjoerg }
65406f32e7eSjoerg Bits[0] <<= BitDistance;
65506f32e7eSjoerg clear_unused_bits();
65606f32e7eSjoerg
65706f32e7eSjoerg return *this;
65806f32e7eSjoerg }
65906f32e7eSjoerg
swap(BitVector & RHS)66006f32e7eSjoerg void swap(BitVector &RHS) {
66106f32e7eSjoerg std::swap(Bits, RHS.Bits);
66206f32e7eSjoerg std::swap(Size, RHS.Size);
66306f32e7eSjoerg }
66406f32e7eSjoerg
invalid()665*da58b97aSjoerg void invalid() {
666*da58b97aSjoerg assert(!Size && Bits.empty());
667*da58b97aSjoerg Size = (unsigned)-1;
668*da58b97aSjoerg }
isInvalid()669*da58b97aSjoerg bool isInvalid() const { return Size == (unsigned)-1; }
670*da58b97aSjoerg
getData()671*da58b97aSjoerg ArrayRef<BitWord> getData() const { return {&Bits[0], Bits.size()}; }
672*da58b97aSjoerg
67306f32e7eSjoerg //===--------------------------------------------------------------------===//
67406f32e7eSjoerg // Portable bit mask operations.
67506f32e7eSjoerg //===--------------------------------------------------------------------===//
67606f32e7eSjoerg //
67706f32e7eSjoerg // These methods all operate on arrays of uint32_t, each holding 32 bits. The
67806f32e7eSjoerg // fixed word size makes it easier to work with literal bit vector constants
67906f32e7eSjoerg // in portable code.
68006f32e7eSjoerg //
68106f32e7eSjoerg // The LSB in each word is the lowest numbered bit. The size of a portable
68206f32e7eSjoerg // bit mask is always a whole multiple of 32 bits. If no bit mask size is
68306f32e7eSjoerg // given, the bit mask is assumed to cover the entire BitVector.
68406f32e7eSjoerg
68506f32e7eSjoerg /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
68606f32e7eSjoerg /// This computes "*this |= Mask".
68706f32e7eSjoerg void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
68806f32e7eSjoerg applyMask<true, false>(Mask, MaskWords);
68906f32e7eSjoerg }
69006f32e7eSjoerg
69106f32e7eSjoerg /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
69206f32e7eSjoerg /// Don't resize. This computes "*this &= ~Mask".
69306f32e7eSjoerg void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
69406f32e7eSjoerg applyMask<false, false>(Mask, MaskWords);
69506f32e7eSjoerg }
69606f32e7eSjoerg
69706f32e7eSjoerg /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
69806f32e7eSjoerg /// Don't resize. This computes "*this |= ~Mask".
69906f32e7eSjoerg void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
70006f32e7eSjoerg applyMask<true, true>(Mask, MaskWords);
70106f32e7eSjoerg }
70206f32e7eSjoerg
70306f32e7eSjoerg /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
70406f32e7eSjoerg /// Don't resize. This computes "*this &= Mask".
70506f32e7eSjoerg void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
70606f32e7eSjoerg applyMask<false, true>(Mask, MaskWords);
70706f32e7eSjoerg }
70806f32e7eSjoerg
70906f32e7eSjoerg private:
71006f32e7eSjoerg /// Perform a logical left shift of \p Count words by moving everything
71106f32e7eSjoerg /// \p Count words to the right in memory.
71206f32e7eSjoerg ///
71306f32e7eSjoerg /// While confusing, words are stored from least significant at Bits[0] to
71406f32e7eSjoerg /// most significant at Bits[NumWords-1]. A logical shift left, however,
71506f32e7eSjoerg /// moves the current least significant bit to a higher logical index, and
71606f32e7eSjoerg /// fills the previous least significant bits with 0. Thus, we actually
71706f32e7eSjoerg /// need to move the bytes of the memory to the right, not to the left.
71806f32e7eSjoerg /// Example:
71906f32e7eSjoerg /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
72006f32e7eSjoerg /// represents a BitVector where 0xBBBBAAAA contain the least significant
721*da58b97aSjoerg /// bits. So if we want to shift the BitVector left by 2 words, we need
722*da58b97aSjoerg /// to turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
72306f32e7eSjoerg /// memmove which moves right, not left.
wordShl(uint32_t Count)72406f32e7eSjoerg void wordShl(uint32_t Count) {
72506f32e7eSjoerg if (Count == 0)
72606f32e7eSjoerg return;
72706f32e7eSjoerg
728*da58b97aSjoerg uint32_t NumWords = Bits.size();
72906f32e7eSjoerg
73006f32e7eSjoerg // Since we always move Word-sized chunks of data with src and dest both
73106f32e7eSjoerg // aligned to a word-boundary, we don't need to worry about endianness
73206f32e7eSjoerg // here.
733*da58b97aSjoerg std::copy(Bits.begin(), Bits.begin() + NumWords - Count,
734*da58b97aSjoerg Bits.begin() + Count);
735*da58b97aSjoerg std::fill(Bits.begin(), Bits.begin() + Count, 0);
73606f32e7eSjoerg clear_unused_bits();
73706f32e7eSjoerg }
73806f32e7eSjoerg
73906f32e7eSjoerg /// Perform a logical right shift of \p Count words by moving those
74006f32e7eSjoerg /// words to the left in memory. See wordShl for more information.
74106f32e7eSjoerg ///
wordShr(uint32_t Count)74206f32e7eSjoerg void wordShr(uint32_t Count) {
74306f32e7eSjoerg if (Count == 0)
74406f32e7eSjoerg return;
74506f32e7eSjoerg
746*da58b97aSjoerg uint32_t NumWords = Bits.size();
74706f32e7eSjoerg
748*da58b97aSjoerg std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin());
749*da58b97aSjoerg std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0);
75006f32e7eSjoerg }
75106f32e7eSjoerg
next_unset_in_word(int WordIndex,BitWord Word)75206f32e7eSjoerg int next_unset_in_word(int WordIndex, BitWord Word) const {
75306f32e7eSjoerg unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
75406f32e7eSjoerg return Result < size() ? Result : -1;
75506f32e7eSjoerg }
75606f32e7eSjoerg
NumBitWords(unsigned S)75706f32e7eSjoerg unsigned NumBitWords(unsigned S) const {
75806f32e7eSjoerg return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
75906f32e7eSjoerg }
76006f32e7eSjoerg
76106f32e7eSjoerg // Set the unused bits in the high words.
76206f32e7eSjoerg void set_unused_bits(bool t = true) {
76306f32e7eSjoerg // Then set any stray high bits of the last used word.
764*da58b97aSjoerg if (unsigned ExtraBits = Size % BITWORD_SIZE) {
765*da58b97aSjoerg BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
76606f32e7eSjoerg if (t)
767*da58b97aSjoerg Bits.back() |= ExtraBitMask;
76806f32e7eSjoerg else
769*da58b97aSjoerg Bits.back() &= ~ExtraBitMask;
77006f32e7eSjoerg }
77106f32e7eSjoerg }
77206f32e7eSjoerg
77306f32e7eSjoerg // Clear the unused bits in the high words.
clear_unused_bits()77406f32e7eSjoerg void clear_unused_bits() {
77506f32e7eSjoerg set_unused_bits(false);
77606f32e7eSjoerg }
77706f32e7eSjoerg
init_words(bool t)778*da58b97aSjoerg void init_words(bool t) {
779*da58b97aSjoerg std::fill(Bits.begin(), Bits.end(), 0 - (BitWord)t);
78006f32e7eSjoerg }
78106f32e7eSjoerg
78206f32e7eSjoerg template<bool AddBits, bool InvertMask>
applyMask(const uint32_t * Mask,unsigned MaskWords)78306f32e7eSjoerg void applyMask(const uint32_t *Mask, unsigned MaskWords) {
78406f32e7eSjoerg static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
78506f32e7eSjoerg MaskWords = std::min(MaskWords, (size() + 31) / 32);
78606f32e7eSjoerg const unsigned Scale = BITWORD_SIZE / 32;
78706f32e7eSjoerg unsigned i;
78806f32e7eSjoerg for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
78906f32e7eSjoerg BitWord BW = Bits[i];
79006f32e7eSjoerg // This inner loop should unroll completely when BITWORD_SIZE > 32.
79106f32e7eSjoerg for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
79206f32e7eSjoerg uint32_t M = *Mask++;
79306f32e7eSjoerg if (InvertMask) M = ~M;
79406f32e7eSjoerg if (AddBits) BW |= BitWord(M) << b;
79506f32e7eSjoerg else BW &= ~(BitWord(M) << b);
79606f32e7eSjoerg }
79706f32e7eSjoerg Bits[i] = BW;
79806f32e7eSjoerg }
79906f32e7eSjoerg for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
80006f32e7eSjoerg uint32_t M = *Mask++;
80106f32e7eSjoerg if (InvertMask) M = ~M;
80206f32e7eSjoerg if (AddBits) Bits[i] |= BitWord(M) << b;
80306f32e7eSjoerg else Bits[i] &= ~(BitWord(M) << b);
80406f32e7eSjoerg }
80506f32e7eSjoerg if (AddBits)
80606f32e7eSjoerg clear_unused_bits();
80706f32e7eSjoerg }
80806f32e7eSjoerg
80906f32e7eSjoerg public:
81006f32e7eSjoerg /// Return the size (in bytes) of the bit vector.
getMemorySize()81106f32e7eSjoerg size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
getBitCapacity()81206f32e7eSjoerg size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
81306f32e7eSjoerg };
81406f32e7eSjoerg
capacity_in_bytes(const BitVector & X)81506f32e7eSjoerg inline size_t capacity_in_bytes(const BitVector &X) {
81606f32e7eSjoerg return X.getMemorySize();
81706f32e7eSjoerg }
81806f32e7eSjoerg
819*da58b97aSjoerg template <> struct DenseMapInfo<BitVector> {
820*da58b97aSjoerg static inline BitVector getEmptyKey() { return {}; }
821*da58b97aSjoerg static inline BitVector getTombstoneKey() {
822*da58b97aSjoerg BitVector V;
823*da58b97aSjoerg V.invalid();
824*da58b97aSjoerg return V;
825*da58b97aSjoerg }
826*da58b97aSjoerg static unsigned getHashValue(const BitVector &V) {
827*da58b97aSjoerg return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
828*da58b97aSjoerg std::make_pair(V.size(), V.getData()));
829*da58b97aSjoerg }
830*da58b97aSjoerg static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
831*da58b97aSjoerg if (LHS.isInvalid() || RHS.isInvalid())
832*da58b97aSjoerg return LHS.isInvalid() == RHS.isInvalid();
833*da58b97aSjoerg return LHS == RHS;
834*da58b97aSjoerg }
835*da58b97aSjoerg };
83606f32e7eSjoerg } // end namespace llvm
83706f32e7eSjoerg
83806f32e7eSjoerg namespace std {
83906f32e7eSjoerg /// Implement std::swap in terms of BitVector swap.
840*da58b97aSjoerg inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); }
84106f32e7eSjoerg } // end namespace std
84206f32e7eSjoerg
84306f32e7eSjoerg #endif // LLVM_ADT_BITVECTOR_H
844