1 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the BitVector class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #ifndef LLVM_ADT_BITVECTOR_H
14 #define LLVM_ADT_BITVECTOR_H
15
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMapInfo.h"
18 #include "llvm/ADT/iterator_range.h"
19 #include "llvm/Support/MathExtras.h"
20 #include <algorithm>
21 #include <cassert>
22 #include <climits>
23 #include <cstdint>
24 #include <cstdlib>
25 #include <cstring>
26 #include <utility>
27
28 namespace llvm {
29
30 /// ForwardIterator for the bits that are set.
31 /// Iterators get invalidated when resize / reserve is called.
32 template <typename BitVectorT> class const_set_bits_iterator_impl {
33 const BitVectorT &Parent;
34 int Current = 0;
35
advance()36 void advance() {
37 assert(Current != -1 && "Trying to advance past end.");
38 Current = Parent.find_next(Current);
39 }
40
41 public:
const_set_bits_iterator_impl(const BitVectorT & Parent,int Current)42 const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
43 : Parent(Parent), Current(Current) {}
const_set_bits_iterator_impl(const BitVectorT & Parent)44 explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
45 : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
46 const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
47
48 const_set_bits_iterator_impl operator++(int) {
49 auto Prev = *this;
50 advance();
51 return Prev;
52 }
53
54 const_set_bits_iterator_impl &operator++() {
55 advance();
56 return *this;
57 }
58
59 unsigned operator*() const { return Current; }
60
61 bool operator==(const const_set_bits_iterator_impl &Other) const {
62 assert(&Parent == &Other.Parent &&
63 "Comparing iterators from different BitVectors");
64 return Current == Other.Current;
65 }
66
67 bool operator!=(const const_set_bits_iterator_impl &Other) const {
68 assert(&Parent == &Other.Parent &&
69 "Comparing iterators from different BitVectors");
70 return Current != Other.Current;
71 }
72 };
73
74 class BitVector {
75 typedef uintptr_t BitWord;
76
77 enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
78
79 static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
80 "Unsupported word size");
81
82 using Storage = SmallVector<BitWord>;
83
84 Storage Bits; // Actual bits.
85 unsigned Size; // Size of bitvector in bits.
86
87 public:
88 typedef unsigned size_type;
89
90 // Encapsulation of a single bit.
91 class reference {
92
93 BitWord *WordRef;
94 unsigned BitPos;
95
96 public:
reference(BitVector & b,unsigned Idx)97 reference(BitVector &b, unsigned Idx) {
98 WordRef = &b.Bits[Idx / BITWORD_SIZE];
99 BitPos = Idx % BITWORD_SIZE;
100 }
101
102 reference() = delete;
103 reference(const reference&) = default;
104
105 reference &operator=(reference t) {
106 *this = bool(t);
107 return *this;
108 }
109
110 reference& operator=(bool t) {
111 if (t)
112 *WordRef |= BitWord(1) << BitPos;
113 else
114 *WordRef &= ~(BitWord(1) << BitPos);
115 return *this;
116 }
117
118 operator bool() const {
119 return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
120 }
121 };
122
123 typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
124 typedef const_set_bits_iterator set_iterator;
125
set_bits_begin()126 const_set_bits_iterator set_bits_begin() const {
127 return const_set_bits_iterator(*this);
128 }
set_bits_end()129 const_set_bits_iterator set_bits_end() const {
130 return const_set_bits_iterator(*this, -1);
131 }
set_bits()132 iterator_range<const_set_bits_iterator> set_bits() const {
133 return make_range(set_bits_begin(), set_bits_end());
134 }
135
136 /// BitVector default ctor - Creates an empty bitvector.
BitVector()137 BitVector() : Size(0) {}
138
139 /// BitVector ctor - Creates a bitvector of specified number of bits. All
140 /// bits are initialized to the specified value.
141 explicit BitVector(unsigned s, bool t = false)
NumBitWords(s)142 : Bits(NumBitWords(s), 0 - (BitWord)t), Size(s) {
143 if (t)
144 clear_unused_bits();
145 }
146
147 /// empty - Tests whether there are no bits in this bitvector.
empty()148 bool empty() const { return Size == 0; }
149
150 /// size - Returns the number of bits in this bitvector.
size()151 size_type size() const { return Size; }
152
153 /// count - Returns the number of bits which are set.
count()154 size_type count() const {
155 unsigned NumBits = 0;
156 for (auto Bit : Bits)
157 NumBits += countPopulation(Bit);
158 return NumBits;
159 }
160
161 /// any - Returns true if any bit is set.
any()162 bool any() const {
163 return any_of(Bits, [](BitWord Bit) { return Bit != 0; });
164 }
165
166 /// all - Returns true if all bits are set.
all()167 bool all() const {
168 for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
169 if (Bits[i] != ~BitWord(0))
170 return false;
171
172 // If bits remain check that they are ones. The unused bits are always zero.
173 if (unsigned Remainder = Size % BITWORD_SIZE)
174 return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
175
176 return true;
177 }
178
179 /// none - Returns true if none of the bits are set.
none()180 bool none() const {
181 return !any();
182 }
183
184 /// find_first_in - Returns the index of the first set / unset bit,
185 /// depending on \p Set, in the range [Begin, End).
186 /// Returns -1 if all bits in the range are unset / set.
187 int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
188 assert(Begin <= End && End <= Size);
189 if (Begin == End)
190 return -1;
191
192 unsigned FirstWord = Begin / BITWORD_SIZE;
193 unsigned LastWord = (End - 1) / BITWORD_SIZE;
194
195 // Check subsequent words.
196 // The code below is based on search for the first _set_ bit. If
197 // we're searching for the first _unset_, we just take the
198 // complement of each word before we use it and apply
199 // the same method.
200 for (unsigned i = FirstWord; i <= LastWord; ++i) {
201 BitWord Copy = Bits[i];
202 if (!Set)
203 Copy = ~Copy;
204
205 if (i == FirstWord) {
206 unsigned FirstBit = Begin % BITWORD_SIZE;
207 Copy &= maskTrailingZeros<BitWord>(FirstBit);
208 }
209
210 if (i == LastWord) {
211 unsigned LastBit = (End - 1) % BITWORD_SIZE;
212 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
213 }
214 if (Copy != 0)
215 return i * BITWORD_SIZE + countTrailingZeros(Copy);
216 }
217 return -1;
218 }
219
220 /// find_last_in - Returns the index of the last set bit in the range
221 /// [Begin, End). Returns -1 if all bits in the range are unset.
find_last_in(unsigned Begin,unsigned End)222 int find_last_in(unsigned Begin, unsigned End) const {
223 assert(Begin <= End && End <= Size);
224 if (Begin == End)
225 return -1;
226
227 unsigned LastWord = (End - 1) / BITWORD_SIZE;
228 unsigned FirstWord = Begin / BITWORD_SIZE;
229
230 for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
231 unsigned CurrentWord = i - 1;
232
233 BitWord Copy = Bits[CurrentWord];
234 if (CurrentWord == LastWord) {
235 unsigned LastBit = (End - 1) % BITWORD_SIZE;
236 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
237 }
238
239 if (CurrentWord == FirstWord) {
240 unsigned FirstBit = Begin % BITWORD_SIZE;
241 Copy &= maskTrailingZeros<BitWord>(FirstBit);
242 }
243
244 if (Copy != 0)
245 return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
246 }
247
248 return -1;
249 }
250
251 /// find_first_unset_in - Returns the index of the first unset bit in the
252 /// range [Begin, End). Returns -1 if all bits in the range are set.
find_first_unset_in(unsigned Begin,unsigned End)253 int find_first_unset_in(unsigned Begin, unsigned End) const {
254 return find_first_in(Begin, End, /* Set = */ false);
255 }
256
257 /// find_last_unset_in - Returns the index of the last unset bit in the
258 /// range [Begin, End). Returns -1 if all bits in the range are set.
find_last_unset_in(unsigned Begin,unsigned End)259 int find_last_unset_in(unsigned Begin, unsigned End) const {
260 assert(Begin <= End && End <= Size);
261 if (Begin == End)
262 return -1;
263
264 unsigned LastWord = (End - 1) / BITWORD_SIZE;
265 unsigned FirstWord = Begin / BITWORD_SIZE;
266
267 for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
268 unsigned CurrentWord = i - 1;
269
270 BitWord Copy = Bits[CurrentWord];
271 if (CurrentWord == LastWord) {
272 unsigned LastBit = (End - 1) % BITWORD_SIZE;
273 Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
274 }
275
276 if (CurrentWord == FirstWord) {
277 unsigned FirstBit = Begin % BITWORD_SIZE;
278 Copy |= maskTrailingOnes<BitWord>(FirstBit);
279 }
280
281 if (Copy != ~BitWord(0)) {
282 unsigned Result =
283 (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
284 return Result < Size ? Result : -1;
285 }
286 }
287 return -1;
288 }
289
290 /// find_first - Returns the index of the first set bit, -1 if none
291 /// of the bits are set.
find_first()292 int find_first() const { return find_first_in(0, Size); }
293
294 /// find_last - Returns the index of the last set bit, -1 if none of the bits
295 /// are set.
find_last()296 int find_last() const { return find_last_in(0, Size); }
297
298 /// find_next - Returns the index of the next set bit following the
299 /// "Prev" bit. Returns -1 if the next set bit is not found.
find_next(unsigned Prev)300 int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
301
302 /// find_prev - Returns the index of the first set bit that precedes the
303 /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
find_prev(unsigned PriorTo)304 int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
305
306 /// find_first_unset - Returns the index of the first unset bit, -1 if all
307 /// of the bits are set.
find_first_unset()308 int find_first_unset() const { return find_first_unset_in(0, Size); }
309
310 /// find_next_unset - Returns the index of the next unset bit following the
311 /// "Prev" bit. Returns -1 if all remaining bits are set.
find_next_unset(unsigned Prev)312 int find_next_unset(unsigned Prev) const {
313 return find_first_unset_in(Prev + 1, Size);
314 }
315
316 /// find_last_unset - Returns the index of the last unset bit, -1 if all of
317 /// the bits are set.
find_last_unset()318 int find_last_unset() const { return find_last_unset_in(0, Size); }
319
320 /// find_prev_unset - Returns the index of the first unset bit that precedes
321 /// the bit at \p PriorTo. Returns -1 if all previous bits are set.
find_prev_unset(unsigned PriorTo)322 int find_prev_unset(unsigned PriorTo) {
323 return find_last_unset_in(0, PriorTo);
324 }
325
326 /// clear - Removes all bits from the bitvector.
clear()327 void clear() {
328 Size = 0;
329 Bits.clear();
330 }
331
332 /// resize - Grow or shrink the bitvector.
333 void resize(unsigned N, bool t = false) {
334 set_unused_bits(t);
335 Size = N;
336 Bits.resize(NumBitWords(N), 0 - BitWord(t));
337 clear_unused_bits();
338 }
339
reserve(unsigned N)340 void reserve(unsigned N) { Bits.reserve(NumBitWords(N)); }
341
342 // Set, reset, flip
set()343 BitVector &set() {
344 init_words(true);
345 clear_unused_bits();
346 return *this;
347 }
348
set(unsigned Idx)349 BitVector &set(unsigned Idx) {
350 assert(Idx < Size && "access in bound");
351 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
352 return *this;
353 }
354
355 /// set - Efficiently set a range of bits in [I, E)
set(unsigned I,unsigned E)356 BitVector &set(unsigned I, unsigned E) {
357 assert(I <= E && "Attempted to set backwards range!");
358 assert(E <= size() && "Attempted to set out-of-bounds range!");
359
360 if (I == E) return *this;
361
362 if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
363 BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
364 BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
365 BitWord Mask = EMask - IMask;
366 Bits[I / BITWORD_SIZE] |= Mask;
367 return *this;
368 }
369
370 BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
371 Bits[I / BITWORD_SIZE] |= PrefixMask;
372 I = alignTo(I, BITWORD_SIZE);
373
374 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
375 Bits[I / BITWORD_SIZE] = ~BitWord(0);
376
377 BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
378 if (I < E)
379 Bits[I / BITWORD_SIZE] |= PostfixMask;
380
381 return *this;
382 }
383
reset()384 BitVector &reset() {
385 init_words(false);
386 return *this;
387 }
388
reset(unsigned Idx)389 BitVector &reset(unsigned Idx) {
390 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
391 return *this;
392 }
393
394 /// reset - Efficiently reset a range of bits in [I, E)
reset(unsigned I,unsigned E)395 BitVector &reset(unsigned I, unsigned E) {
396 assert(I <= E && "Attempted to reset backwards range!");
397 assert(E <= size() && "Attempted to reset out-of-bounds range!");
398
399 if (I == E) return *this;
400
401 if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
402 BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
403 BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
404 BitWord Mask = EMask - IMask;
405 Bits[I / BITWORD_SIZE] &= ~Mask;
406 return *this;
407 }
408
409 BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
410 Bits[I / BITWORD_SIZE] &= ~PrefixMask;
411 I = alignTo(I, BITWORD_SIZE);
412
413 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
414 Bits[I / BITWORD_SIZE] = BitWord(0);
415
416 BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
417 if (I < E)
418 Bits[I / BITWORD_SIZE] &= ~PostfixMask;
419
420 return *this;
421 }
422
flip()423 BitVector &flip() {
424 for (auto &Bit : Bits)
425 Bit = ~Bit;
426 clear_unused_bits();
427 return *this;
428 }
429
flip(unsigned Idx)430 BitVector &flip(unsigned Idx) {
431 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
432 return *this;
433 }
434
435 // Indexing.
436 reference operator[](unsigned Idx) {
437 assert (Idx < Size && "Out-of-bounds Bit access.");
438 return reference(*this, Idx);
439 }
440
441 bool operator[](unsigned Idx) const {
442 assert (Idx < Size && "Out-of-bounds Bit access.");
443 BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
444 return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
445 }
446
test(unsigned Idx)447 bool test(unsigned Idx) const {
448 return (*this)[Idx];
449 }
450
451 // Push single bit to end of vector.
push_back(bool Val)452 void push_back(bool Val) {
453 unsigned OldSize = Size;
454 unsigned NewSize = Size + 1;
455
456 // Resize, which will insert zeros.
457 // If we already fit then the unused bits will be already zero.
458 if (NewSize > getBitCapacity())
459 resize(NewSize, false);
460 else
461 Size = NewSize;
462
463 // If true, set single bit.
464 if (Val)
465 set(OldSize);
466 }
467
468 /// Test if any common bits are set.
anyCommon(const BitVector & RHS)469 bool anyCommon(const BitVector &RHS) const {
470 unsigned ThisWords = Bits.size();
471 unsigned RHSWords = RHS.Bits.size();
472 for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
473 if (Bits[i] & RHS.Bits[i])
474 return true;
475 return false;
476 }
477
478 // Comparison operators.
479 bool operator==(const BitVector &RHS) const {
480 if (size() != RHS.size())
481 return false;
482 unsigned NumWords = Bits.size();
483 return std::equal(Bits.begin(), Bits.begin() + NumWords, RHS.Bits.begin());
484 }
485
486 bool operator!=(const BitVector &RHS) const { return !(*this == RHS); }
487
488 /// Intersection, union, disjoint union.
489 BitVector &operator&=(const BitVector &RHS) {
490 unsigned ThisWords = Bits.size();
491 unsigned RHSWords = RHS.Bits.size();
492 unsigned i;
493 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
494 Bits[i] &= RHS.Bits[i];
495
496 // Any bits that are just in this bitvector become zero, because they aren't
497 // in the RHS bit vector. Any words only in RHS are ignored because they
498 // are already zero in the LHS.
499 for (; i != ThisWords; ++i)
500 Bits[i] = 0;
501
502 return *this;
503 }
504
505 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
reset(const BitVector & RHS)506 BitVector &reset(const BitVector &RHS) {
507 unsigned ThisWords = Bits.size();
508 unsigned RHSWords = RHS.Bits.size();
509 for (unsigned i = 0; i != std::min(ThisWords, RHSWords); ++i)
510 Bits[i] &= ~RHS.Bits[i];
511 return *this;
512 }
513
514 /// test - Check if (This - RHS) is zero.
515 /// This is the same as reset(RHS) and any().
test(const BitVector & RHS)516 bool test(const BitVector &RHS) const {
517 unsigned ThisWords = Bits.size();
518 unsigned RHSWords = RHS.Bits.size();
519 unsigned i;
520 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
521 if ((Bits[i] & ~RHS.Bits[i]) != 0)
522 return true;
523
524 for (; i != ThisWords ; ++i)
525 if (Bits[i] != 0)
526 return true;
527
528 return false;
529 }
530
531 template <class F, class... ArgTys>
apply(F && f,BitVector & Out,BitVector const & Arg,ArgTys const &...Args)532 static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
533 ArgTys const &...Args) {
534 assert(llvm::all_of(
535 std::initializer_list<unsigned>{Args.size()...},
536 [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
537 "consistent sizes");
538 Out.resize(Arg.size());
539 for (size_t i = 0, e = Arg.Bits.size(); i != e; ++i)
540 Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...);
541 Out.clear_unused_bits();
542 return Out;
543 }
544
545 BitVector &operator|=(const BitVector &RHS) {
546 if (size() < RHS.size())
547 resize(RHS.size());
548 for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
549 Bits[i] |= RHS.Bits[i];
550 return *this;
551 }
552
553 BitVector &operator^=(const BitVector &RHS) {
554 if (size() < RHS.size())
555 resize(RHS.size());
556 for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
557 Bits[i] ^= RHS.Bits[i];
558 return *this;
559 }
560
561 BitVector &operator>>=(unsigned N) {
562 assert(N <= Size);
563 if (LLVM_UNLIKELY(empty() || N == 0))
564 return *this;
565
566 unsigned NumWords = Bits.size();
567 assert(NumWords >= 1);
568
569 wordShr(N / BITWORD_SIZE);
570
571 unsigned BitDistance = N % BITWORD_SIZE;
572 if (BitDistance == 0)
573 return *this;
574
575 // When the shift size is not a multiple of the word size, then we have
576 // a tricky situation where each word in succession needs to extract some
577 // of the bits from the next word and or them into this word while
578 // shifting this word to make room for the new bits. This has to be done
579 // for every word in the array.
580
581 // Since we're shifting each word right, some bits will fall off the end
582 // of each word to the right, and empty space will be created on the left.
583 // The final word in the array will lose bits permanently, so starting at
584 // the beginning, work forwards shifting each word to the right, and
585 // OR'ing in the bits from the end of the next word to the beginning of
586 // the current word.
587
588 // Example:
589 // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
590 // by 4 bits.
591 // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
592 // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
593 // Step 3: Word[1] >>= 4 ; 0x0EEFF001
594 // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
595 // Step 5: Word[2] >>= 4 ; 0x02334455
596 // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
597 const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
598 const unsigned LSH = BITWORD_SIZE - BitDistance;
599
600 for (unsigned I = 0; I < NumWords - 1; ++I) {
601 Bits[I] >>= BitDistance;
602 Bits[I] |= (Bits[I + 1] & Mask) << LSH;
603 }
604
605 Bits[NumWords - 1] >>= BitDistance;
606
607 return *this;
608 }
609
610 BitVector &operator<<=(unsigned N) {
611 assert(N <= Size);
612 if (LLVM_UNLIKELY(empty() || N == 0))
613 return *this;
614
615 unsigned NumWords = Bits.size();
616 assert(NumWords >= 1);
617
618 wordShl(N / BITWORD_SIZE);
619
620 unsigned BitDistance = N % BITWORD_SIZE;
621 if (BitDistance == 0)
622 return *this;
623
624 // When the shift size is not a multiple of the word size, then we have
625 // a tricky situation where each word in succession needs to extract some
626 // of the bits from the previous word and or them into this word while
627 // shifting this word to make room for the new bits. This has to be done
628 // for every word in the array. This is similar to the algorithm outlined
629 // in operator>>=, but backwards.
630
631 // Since we're shifting each word left, some bits will fall off the end
632 // of each word to the left, and empty space will be created on the right.
633 // The first word in the array will lose bits permanently, so starting at
634 // the end, work backwards shifting each word to the left, and OR'ing
635 // in the bits from the end of the next word to the beginning of the
636 // current word.
637
638 // Example:
639 // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
640 // by 4 bits.
641 // Step 1: Word[2] <<= 4 ; 0x23344550
642 // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
643 // Step 3: Word[1] <<= 4 ; 0xEFF00110
644 // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
645 // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
646 // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
647 const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
648 const unsigned RSH = BITWORD_SIZE - BitDistance;
649
650 for (int I = NumWords - 1; I > 0; --I) {
651 Bits[I] <<= BitDistance;
652 Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
653 }
654 Bits[0] <<= BitDistance;
655 clear_unused_bits();
656
657 return *this;
658 }
659
swap(BitVector & RHS)660 void swap(BitVector &RHS) {
661 std::swap(Bits, RHS.Bits);
662 std::swap(Size, RHS.Size);
663 }
664
invalid()665 void invalid() {
666 assert(!Size && Bits.empty());
667 Size = (unsigned)-1;
668 }
isInvalid()669 bool isInvalid() const { return Size == (unsigned)-1; }
670
getData()671 ArrayRef<BitWord> getData() const { return {&Bits[0], Bits.size()}; }
672
673 //===--------------------------------------------------------------------===//
674 // Portable bit mask operations.
675 //===--------------------------------------------------------------------===//
676 //
677 // These methods all operate on arrays of uint32_t, each holding 32 bits. The
678 // fixed word size makes it easier to work with literal bit vector constants
679 // in portable code.
680 //
681 // The LSB in each word is the lowest numbered bit. The size of a portable
682 // bit mask is always a whole multiple of 32 bits. If no bit mask size is
683 // given, the bit mask is assumed to cover the entire BitVector.
684
685 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
686 /// This computes "*this |= Mask".
687 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
688 applyMask<true, false>(Mask, MaskWords);
689 }
690
691 /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
692 /// Don't resize. This computes "*this &= ~Mask".
693 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
694 applyMask<false, false>(Mask, MaskWords);
695 }
696
697 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
698 /// Don't resize. This computes "*this |= ~Mask".
699 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
700 applyMask<true, true>(Mask, MaskWords);
701 }
702
703 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
704 /// Don't resize. This computes "*this &= Mask".
705 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
706 applyMask<false, true>(Mask, MaskWords);
707 }
708
709 private:
710 /// Perform a logical left shift of \p Count words by moving everything
711 /// \p Count words to the right in memory.
712 ///
713 /// While confusing, words are stored from least significant at Bits[0] to
714 /// most significant at Bits[NumWords-1]. A logical shift left, however,
715 /// moves the current least significant bit to a higher logical index, and
716 /// fills the previous least significant bits with 0. Thus, we actually
717 /// need to move the bytes of the memory to the right, not to the left.
718 /// Example:
719 /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
720 /// represents a BitVector where 0xBBBBAAAA contain the least significant
721 /// bits. So if we want to shift the BitVector left by 2 words, we need
722 /// to turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
723 /// memmove which moves right, not left.
wordShl(uint32_t Count)724 void wordShl(uint32_t Count) {
725 if (Count == 0)
726 return;
727
728 uint32_t NumWords = Bits.size();
729
730 // Since we always move Word-sized chunks of data with src and dest both
731 // aligned to a word-boundary, we don't need to worry about endianness
732 // here.
733 std::copy(Bits.begin(), Bits.begin() + NumWords - Count,
734 Bits.begin() + Count);
735 std::fill(Bits.begin(), Bits.begin() + Count, 0);
736 clear_unused_bits();
737 }
738
739 /// Perform a logical right shift of \p Count words by moving those
740 /// words to the left in memory. See wordShl for more information.
741 ///
wordShr(uint32_t Count)742 void wordShr(uint32_t Count) {
743 if (Count == 0)
744 return;
745
746 uint32_t NumWords = Bits.size();
747
748 std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin());
749 std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0);
750 }
751
next_unset_in_word(int WordIndex,BitWord Word)752 int next_unset_in_word(int WordIndex, BitWord Word) const {
753 unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
754 return Result < size() ? Result : -1;
755 }
756
NumBitWords(unsigned S)757 unsigned NumBitWords(unsigned S) const {
758 return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
759 }
760
761 // Set the unused bits in the high words.
762 void set_unused_bits(bool t = true) {
763 // Then set any stray high bits of the last used word.
764 if (unsigned ExtraBits = Size % BITWORD_SIZE) {
765 BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
766 if (t)
767 Bits.back() |= ExtraBitMask;
768 else
769 Bits.back() &= ~ExtraBitMask;
770 }
771 }
772
773 // Clear the unused bits in the high words.
clear_unused_bits()774 void clear_unused_bits() {
775 set_unused_bits(false);
776 }
777
init_words(bool t)778 void init_words(bool t) {
779 std::fill(Bits.begin(), Bits.end(), 0 - (BitWord)t);
780 }
781
782 template<bool AddBits, bool InvertMask>
applyMask(const uint32_t * Mask,unsigned MaskWords)783 void applyMask(const uint32_t *Mask, unsigned MaskWords) {
784 static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
785 MaskWords = std::min(MaskWords, (size() + 31) / 32);
786 const unsigned Scale = BITWORD_SIZE / 32;
787 unsigned i;
788 for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
789 BitWord BW = Bits[i];
790 // This inner loop should unroll completely when BITWORD_SIZE > 32.
791 for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
792 uint32_t M = *Mask++;
793 if (InvertMask) M = ~M;
794 if (AddBits) BW |= BitWord(M) << b;
795 else BW &= ~(BitWord(M) << b);
796 }
797 Bits[i] = BW;
798 }
799 for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
800 uint32_t M = *Mask++;
801 if (InvertMask) M = ~M;
802 if (AddBits) Bits[i] |= BitWord(M) << b;
803 else Bits[i] &= ~(BitWord(M) << b);
804 }
805 if (AddBits)
806 clear_unused_bits();
807 }
808
809 public:
810 /// Return the size (in bytes) of the bit vector.
getMemorySize()811 size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
getBitCapacity()812 size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
813 };
814
capacity_in_bytes(const BitVector & X)815 inline size_t capacity_in_bytes(const BitVector &X) {
816 return X.getMemorySize();
817 }
818
819 template <> struct DenseMapInfo<BitVector> {
820 static inline BitVector getEmptyKey() { return {}; }
821 static inline BitVector getTombstoneKey() {
822 BitVector V;
823 V.invalid();
824 return V;
825 }
826 static unsigned getHashValue(const BitVector &V) {
827 return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
828 std::make_pair(V.size(), V.getData()));
829 }
830 static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
831 if (LHS.isInvalid() || RHS.isInvalid())
832 return LHS.isInvalid() == RHS.isInvalid();
833 return LHS == RHS;
834 }
835 };
836 } // end namespace llvm
837
838 namespace std {
839 /// Implement std::swap in terms of BitVector swap.
840 inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); }
841 } // end namespace std
842
843 #endif // LLVM_ADT_BITVECTOR_H
844