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 MutableArrayRef<BitWord> Bits; // Actual bits.
83 unsigned Size; // Size of bitvector in bits.
84
85 public:
86 typedef unsigned size_type;
87 // Encapsulation of a single bit.
88 class reference {
89 friend class BitVector;
90
91 BitWord *WordRef;
92 unsigned BitPos;
93
94 public:
reference(BitVector & b,unsigned Idx)95 reference(BitVector &b, unsigned Idx) {
96 WordRef = &b.Bits[Idx / BITWORD_SIZE];
97 BitPos = Idx % BITWORD_SIZE;
98 }
99
100 reference() = delete;
101 reference(const reference&) = default;
102
103 reference &operator=(reference t) {
104 *this = bool(t);
105 return *this;
106 }
107
108 reference& operator=(bool t) {
109 if (t)
110 *WordRef |= BitWord(1) << BitPos;
111 else
112 *WordRef &= ~(BitWord(1) << BitPos);
113 return *this;
114 }
115
116 operator bool() const {
117 return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
118 }
119 };
120
121 typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
122 typedef const_set_bits_iterator set_iterator;
123
set_bits_begin()124 const_set_bits_iterator set_bits_begin() const {
125 return const_set_bits_iterator(*this);
126 }
set_bits_end()127 const_set_bits_iterator set_bits_end() const {
128 return const_set_bits_iterator(*this, -1);
129 }
set_bits()130 iterator_range<const_set_bits_iterator> set_bits() const {
131 return make_range(set_bits_begin(), set_bits_end());
132 }
133
134 /// BitVector default ctor - Creates an empty bitvector.
BitVector()135 BitVector() : Size(0) {}
136
137 /// BitVector ctor - Creates a bitvector of specified number of bits. All
138 /// bits are initialized to the specified value.
Size(s)139 explicit BitVector(unsigned s, bool t = false) : Size(s) {
140 size_t Capacity = NumBitWords(s);
141 Bits = allocate(Capacity);
142 init_words(Bits, t);
143 if (t)
144 clear_unused_bits();
145 }
146
147 /// BitVector copy ctor.
BitVector(const BitVector & RHS)148 BitVector(const BitVector &RHS) : Size(RHS.size()) {
149 if (Size == 0) {
150 Bits = MutableArrayRef<BitWord>();
151 return;
152 }
153
154 size_t Capacity = NumBitWords(RHS.size());
155 Bits = allocate(Capacity);
156 std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
157 }
158
BitVector(BitVector && RHS)159 BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
160 RHS.Bits = MutableArrayRef<BitWord>();
161 RHS.Size = 0;
162 }
163
~BitVector()164 ~BitVector() { std::free(Bits.data()); }
165
166 /// empty - Tests whether there are no bits in this bitvector.
empty()167 bool empty() const { return Size == 0; }
168
169 /// size - Returns the number of bits in this bitvector.
size()170 size_type size() const { return Size; }
171
172 /// count - Returns the number of bits which are set.
count()173 size_type count() const {
174 unsigned NumBits = 0;
175 for (unsigned i = 0; i < NumBitWords(size()); ++i)
176 NumBits += countPopulation(Bits[i]);
177 return NumBits;
178 }
179
180 /// any - Returns true if any bit is set.
any()181 bool any() const {
182 for (unsigned i = 0; i < NumBitWords(size()); ++i)
183 if (Bits[i] != 0)
184 return true;
185 return false;
186 }
187
188 /// all - Returns true if all bits are set.
all()189 bool all() const {
190 for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
191 if (Bits[i] != ~BitWord(0))
192 return false;
193
194 // If bits remain check that they are ones. The unused bits are always zero.
195 if (unsigned Remainder = Size % BITWORD_SIZE)
196 return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
197
198 return true;
199 }
200
201 /// none - Returns true if none of the bits are set.
none()202 bool none() const {
203 return !any();
204 }
205
206 /// find_first_in - Returns the index of the first set / unset bit,
207 /// depending on \p Set, in the range [Begin, End).
208 /// Returns -1 if all bits in the range are unset / set.
209 int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
210 assert(Begin <= End && End <= Size);
211 if (Begin == End)
212 return -1;
213
214 unsigned FirstWord = Begin / BITWORD_SIZE;
215 unsigned LastWord = (End - 1) / BITWORD_SIZE;
216
217 // Check subsequent words.
218 // The code below is based on search for the first _set_ bit. If
219 // we're searching for the first _unset_, we just take the
220 // complement of each word before we use it and apply
221 // the same method.
222 for (unsigned i = FirstWord; i <= LastWord; ++i) {
223 BitWord Copy = Bits[i];
224 if (!Set)
225 Copy = ~Copy;
226
227 if (i == FirstWord) {
228 unsigned FirstBit = Begin % BITWORD_SIZE;
229 Copy &= maskTrailingZeros<BitWord>(FirstBit);
230 }
231
232 if (i == LastWord) {
233 unsigned LastBit = (End - 1) % BITWORD_SIZE;
234 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
235 }
236 if (Copy != 0)
237 return i * BITWORD_SIZE + countTrailingZeros(Copy);
238 }
239 return -1;
240 }
241
242 /// find_last_in - Returns the index of the last set bit in the range
243 /// [Begin, End). Returns -1 if all bits in the range are unset.
find_last_in(unsigned Begin,unsigned End)244 int find_last_in(unsigned Begin, unsigned End) const {
245 assert(Begin <= End && End <= Size);
246 if (Begin == End)
247 return -1;
248
249 unsigned LastWord = (End - 1) / BITWORD_SIZE;
250 unsigned FirstWord = Begin / BITWORD_SIZE;
251
252 for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
253 unsigned CurrentWord = i - 1;
254
255 BitWord Copy = Bits[CurrentWord];
256 if (CurrentWord == LastWord) {
257 unsigned LastBit = (End - 1) % BITWORD_SIZE;
258 Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
259 }
260
261 if (CurrentWord == FirstWord) {
262 unsigned FirstBit = Begin % BITWORD_SIZE;
263 Copy &= maskTrailingZeros<BitWord>(FirstBit);
264 }
265
266 if (Copy != 0)
267 return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
268 }
269
270 return -1;
271 }
272
273 /// find_first_unset_in - Returns the index of the first unset bit in the
274 /// range [Begin, End). Returns -1 if all bits in the range are set.
find_first_unset_in(unsigned Begin,unsigned End)275 int find_first_unset_in(unsigned Begin, unsigned End) const {
276 return find_first_in(Begin, End, /* Set = */ false);
277 }
278
279 /// find_last_unset_in - Returns the index of the last unset bit in the
280 /// range [Begin, End). Returns -1 if all bits in the range are set.
find_last_unset_in(unsigned Begin,unsigned End)281 int find_last_unset_in(unsigned Begin, unsigned End) const {
282 assert(Begin <= End && End <= Size);
283 if (Begin == End)
284 return -1;
285
286 unsigned LastWord = (End - 1) / BITWORD_SIZE;
287 unsigned FirstWord = Begin / BITWORD_SIZE;
288
289 for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
290 unsigned CurrentWord = i - 1;
291
292 BitWord Copy = Bits[CurrentWord];
293 if (CurrentWord == LastWord) {
294 unsigned LastBit = (End - 1) % BITWORD_SIZE;
295 Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
296 }
297
298 if (CurrentWord == FirstWord) {
299 unsigned FirstBit = Begin % BITWORD_SIZE;
300 Copy |= maskTrailingOnes<BitWord>(FirstBit);
301 }
302
303 if (Copy != ~BitWord(0)) {
304 unsigned Result =
305 (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
306 return Result < Size ? Result : -1;
307 }
308 }
309 return -1;
310 }
311
312 /// find_first - Returns the index of the first set bit, -1 if none
313 /// of the bits are set.
find_first()314 int find_first() const { return find_first_in(0, Size); }
315
316 /// find_last - Returns the index of the last set bit, -1 if none of the bits
317 /// are set.
find_last()318 int find_last() const { return find_last_in(0, Size); }
319
320 /// find_next - Returns the index of the next set bit following the
321 /// "Prev" bit. Returns -1 if the next set bit is not found.
find_next(unsigned Prev)322 int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
323
324 /// find_prev - Returns the index of the first set bit that precedes the
325 /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
find_prev(unsigned PriorTo)326 int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
327
328 /// find_first_unset - Returns the index of the first unset bit, -1 if all
329 /// of the bits are set.
find_first_unset()330 int find_first_unset() const { return find_first_unset_in(0, Size); }
331
332 /// find_next_unset - Returns the index of the next unset bit following the
333 /// "Prev" bit. Returns -1 if all remaining bits are set.
find_next_unset(unsigned Prev)334 int find_next_unset(unsigned Prev) const {
335 return find_first_unset_in(Prev + 1, Size);
336 }
337
338 /// find_last_unset - Returns the index of the last unset bit, -1 if all of
339 /// the bits are set.
find_last_unset()340 int find_last_unset() const { return find_last_unset_in(0, Size); }
341
342 /// find_prev_unset - Returns the index of the first unset bit that precedes
343 /// the bit at \p PriorTo. Returns -1 if all previous bits are set.
find_prev_unset(unsigned PriorTo)344 int find_prev_unset(unsigned PriorTo) {
345 return find_last_unset_in(0, PriorTo);
346 }
347
348 /// clear - Removes all bits from the bitvector. Does not change capacity.
clear()349 void clear() {
350 Size = 0;
351 }
352
353 /// resize - Grow or shrink the bitvector.
354 void resize(unsigned N, bool t = false) {
355 if (N > getBitCapacity()) {
356 unsigned OldCapacity = Bits.size();
357 grow(N);
358 init_words(Bits.drop_front(OldCapacity), t);
359 }
360
361 // Set any old unused bits that are now included in the BitVector. This
362 // may set bits that are not included in the new vector, but we will clear
363 // them back out below.
364 if (N > Size)
365 set_unused_bits(t);
366
367 // Update the size, and clear out any bits that are now unused
368 unsigned OldSize = Size;
369 Size = N;
370 if (t || N < OldSize)
371 clear_unused_bits();
372 }
373
reserve(unsigned N)374 void reserve(unsigned N) {
375 if (N > getBitCapacity())
376 grow(N);
377 }
378
379 // Set, reset, flip
set()380 BitVector &set() {
381 init_words(Bits, true);
382 clear_unused_bits();
383 return *this;
384 }
385
set(unsigned Idx)386 BitVector &set(unsigned Idx) {
387 assert(Bits.data() && "Bits never allocated");
388 Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
389 return *this;
390 }
391
392 /// set - Efficiently set a range of bits in [I, E)
set(unsigned I,unsigned E)393 BitVector &set(unsigned I, unsigned E) {
394 assert(I <= E && "Attempted to set backwards range!");
395 assert(E <= size() && "Attempted to set out-of-bounds range!");
396
397 if (I == E) return *this;
398
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;
403 Bits[I / BITWORD_SIZE] |= Mask;
404 return *this;
405 }
406
407 BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
408 Bits[I / BITWORD_SIZE] |= PrefixMask;
409 I = alignTo(I, BITWORD_SIZE);
410
411 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
412 Bits[I / BITWORD_SIZE] = ~BitWord(0);
413
414 BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
415 if (I < E)
416 Bits[I / BITWORD_SIZE] |= PostfixMask;
417
418 return *this;
419 }
420
reset()421 BitVector &reset() {
422 init_words(Bits, false);
423 return *this;
424 }
425
reset(unsigned Idx)426 BitVector &reset(unsigned Idx) {
427 Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
428 return *this;
429 }
430
431 /// reset - Efficiently reset a range of bits in [I, E)
reset(unsigned I,unsigned E)432 BitVector &reset(unsigned I, unsigned E) {
433 assert(I <= E && "Attempted to reset backwards range!");
434 assert(E <= size() && "Attempted to reset out-of-bounds range!");
435
436 if (I == E) return *this;
437
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;
442 Bits[I / BITWORD_SIZE] &= ~Mask;
443 return *this;
444 }
445
446 BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
447 Bits[I / BITWORD_SIZE] &= ~PrefixMask;
448 I = alignTo(I, BITWORD_SIZE);
449
450 for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
451 Bits[I / BITWORD_SIZE] = BitWord(0);
452
453 BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
454 if (I < E)
455 Bits[I / BITWORD_SIZE] &= ~PostfixMask;
456
457 return *this;
458 }
459
flip()460 BitVector &flip() {
461 for (unsigned i = 0; i < NumBitWords(size()); ++i)
462 Bits[i] = ~Bits[i];
463 clear_unused_bits();
464 return *this;
465 }
466
flip(unsigned Idx)467 BitVector &flip(unsigned Idx) {
468 Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
469 return *this;
470 }
471
472 // Indexing.
473 reference operator[](unsigned Idx) {
474 assert (Idx < Size && "Out-of-bounds Bit access.");
475 return reference(*this, Idx);
476 }
477
478 bool operator[](unsigned Idx) const {
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;
482 }
483
test(unsigned Idx)484 bool test(unsigned Idx) const {
485 return (*this)[Idx];
486 }
487
488 // Push single bit to end of vector.
push_back(bool Val)489 void push_back(bool Val) {
490 unsigned OldSize = Size;
491 unsigned NewSize = Size + 1;
492
493 // Resize, which will insert zeros.
494 // If we already fit then the unused bits will be already zero.
495 if (NewSize > getBitCapacity())
496 resize(NewSize, false);
497 else
498 Size = NewSize;
499
500 // If true, set single bit.
501 if (Val)
502 set(OldSize);
503 }
504
505 /// Test if any common bits are set.
anyCommon(const BitVector & RHS)506 bool anyCommon(const BitVector &RHS) const {
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])
511 return true;
512 return false;
513 }
514
515 // Comparison operators.
516 bool operator==(const BitVector &RHS) const {
517 if (size() != RHS.size())
518 return false;
519 unsigned NumWords = NumBitWords(size());
520 return Bits.take_front(NumWords) == RHS.Bits.take_front(NumWords);
521 }
522
523 bool operator!=(const BitVector &RHS) const {
524 return !(*this == RHS);
525 }
526
527 /// Intersection, union, disjoint union.
528 BitVector &operator&=(const BitVector &RHS) {
529 unsigned ThisWords = NumBitWords(size());
530 unsigned RHSWords = NumBitWords(RHS.size());
531 unsigned i;
532 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
533 Bits[i] &= RHS.Bits[i];
534
535 // Any bits that are just in this bitvector become zero, because they aren't
536 // in the RHS bit vector. Any words only in RHS are ignored because they
537 // are already zero in the LHS.
538 for (; i != ThisWords; ++i)
539 Bits[i] = 0;
540
541 return *this;
542 }
543
544 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
reset(const BitVector & RHS)545 BitVector &reset(const BitVector &RHS) {
546 unsigned ThisWords = NumBitWords(size());
547 unsigned RHSWords = NumBitWords(RHS.size());
548 unsigned i;
549 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
550 Bits[i] &= ~RHS.Bits[i];
551 return *this;
552 }
553
554 /// test - Check if (This - RHS) is zero.
555 /// This is the same as reset(RHS) and any().
test(const BitVector & RHS)556 bool test(const BitVector &RHS) const {
557 unsigned ThisWords = NumBitWords(size());
558 unsigned RHSWords = NumBitWords(RHS.size());
559 unsigned i;
560 for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
561 if ((Bits[i] & ~RHS.Bits[i]) != 0)
562 return true;
563
564 for (; i != ThisWords ; ++i)
565 if (Bits[i] != 0)
566 return true;
567
568 return false;
569 }
570
571 BitVector &operator|=(const BitVector &RHS) {
572 if (size() < RHS.size())
573 resize(RHS.size());
574 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
575 Bits[i] |= RHS.Bits[i];
576 return *this;
577 }
578
579 BitVector &operator^=(const BitVector &RHS) {
580 if (size() < RHS.size())
581 resize(RHS.size());
582 for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
583 Bits[i] ^= RHS.Bits[i];
584 return *this;
585 }
586
587 BitVector &operator>>=(unsigned N) {
588 assert(N <= Size);
589 if (LLVM_UNLIKELY(empty() || N == 0))
590 return *this;
591
592 unsigned NumWords = NumBitWords(Size);
593 assert(NumWords >= 1);
594
595 wordShr(N / BITWORD_SIZE);
596
597 unsigned BitDistance = N % BITWORD_SIZE;
598 if (BitDistance == 0)
599 return *this;
600
601 // When the shift size is not a multiple of the word size, then we have
602 // a tricky situation where each word in succession needs to extract some
603 // of the bits from the next word and or them into this word while
604 // shifting this word to make room for the new bits. This has to be done
605 // for every word in the array.
606
607 // Since we're shifting each word right, some bits will fall off the end
608 // of each word to the right, and empty space will be created on the left.
609 // The final word in the array will lose bits permanently, so starting at
610 // the beginning, work forwards shifting each word to the right, and
611 // OR'ing in the bits from the end of the next word to the beginning of
612 // the current word.
613
614 // Example:
615 // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
616 // by 4 bits.
617 // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
618 // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
619 // Step 3: Word[1] >>= 4 ; 0x0EEFF001
620 // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
621 // Step 5: Word[2] >>= 4 ; 0x02334455
622 // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
623 const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
624 const unsigned LSH = BITWORD_SIZE - BitDistance;
625
626 for (unsigned I = 0; I < NumWords - 1; ++I) {
627 Bits[I] >>= BitDistance;
628 Bits[I] |= (Bits[I + 1] & Mask) << LSH;
629 }
630
631 Bits[NumWords - 1] >>= BitDistance;
632
633 return *this;
634 }
635
636 BitVector &operator<<=(unsigned N) {
637 assert(N <= Size);
638 if (LLVM_UNLIKELY(empty() || N == 0))
639 return *this;
640
641 unsigned NumWords = NumBitWords(Size);
642 assert(NumWords >= 1);
643
644 wordShl(N / BITWORD_SIZE);
645
646 unsigned BitDistance = N % BITWORD_SIZE;
647 if (BitDistance == 0)
648 return *this;
649
650 // When the shift size is not a multiple of the word size, then we have
651 // a tricky situation where each word in succession needs to extract some
652 // of the bits from the previous word and or them into this word while
653 // shifting this word to make room for the new bits. This has to be done
654 // for every word in the array. This is similar to the algorithm outlined
655 // in operator>>=, but backwards.
656
657 // Since we're shifting each word left, some bits will fall off the end
658 // of each word to the left, and empty space will be created on the right.
659 // The first word in the array will lose bits permanently, so starting at
660 // the end, work backwards shifting each word to the left, and OR'ing
661 // in the bits from the end of the next word to the beginning of the
662 // current word.
663
664 // Example:
665 // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
666 // by 4 bits.
667 // Step 1: Word[2] <<= 4 ; 0x23344550
668 // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
669 // Step 3: Word[1] <<= 4 ; 0xEFF00110
670 // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
671 // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
672 // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
673 const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
674 const unsigned RSH = BITWORD_SIZE - BitDistance;
675
676 for (int I = NumWords - 1; I > 0; --I) {
677 Bits[I] <<= BitDistance;
678 Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
679 }
680 Bits[0] <<= BitDistance;
681 clear_unused_bits();
682
683 return *this;
684 }
685
686 // Assignment operator.
687 const BitVector &operator=(const BitVector &RHS) {
688 if (this == &RHS) return *this;
689
690 Size = RHS.size();
691
692 // Handle tombstone when the BitVector is a key of a DenseHash.
693 if (RHS.isInvalid()) {
694 std::free(Bits.data());
695 Bits = None;
696 return *this;
697 }
698
699 unsigned RHSWords = NumBitWords(Size);
700 if (Size <= getBitCapacity()) {
701 if (Size)
702 std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
703 clear_unused_bits();
704 return *this;
705 }
706
707 // Grow the bitvector to have enough elements.
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));
712
713 // Destroy the old bits.
714 std::free(Bits.data());
715 Bits = NewBits;
716
717 return *this;
718 }
719
720 const BitVector &operator=(BitVector &&RHS) {
721 if (this == &RHS) return *this;
722
723 std::free(Bits.data());
724 Bits = RHS.Bits;
725 Size = RHS.Size;
726
727 RHS.Bits = MutableArrayRef<BitWord>();
728 RHS.Size = 0;
729
730 return *this;
731 }
732
swap(BitVector & RHS)733 void swap(BitVector &RHS) {
734 std::swap(Bits, RHS.Bits);
735 std::swap(Size, RHS.Size);
736 }
737
invalid()738 void invalid() {
739 assert(!Size && Bits.empty());
740 Size = (unsigned)-1;
741 }
isInvalid()742 bool isInvalid() const { return Size == (unsigned)-1; }
743
getData()744 ArrayRef<BitWord> getData() const {
745 return Bits.take_front(NumBitWords(size()));
746 }
747
748 //===--------------------------------------------------------------------===//
749 // Portable bit mask operations.
750 //===--------------------------------------------------------------------===//
751 //
752 // These methods all operate on arrays of uint32_t, each holding 32 bits. The
753 // fixed word size makes it easier to work with literal bit vector constants
754 // in portable code.
755 //
756 // The LSB in each word is the lowest numbered bit. The size of a portable
757 // bit mask is always a whole multiple of 32 bits. If no bit mask size is
758 // given, the bit mask is assumed to cover the entire BitVector.
759
760 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
761 /// This computes "*this |= Mask".
762 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
763 applyMask<true, false>(Mask, MaskWords);
764 }
765
766 /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
767 /// Don't resize. This computes "*this &= ~Mask".
768 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
769 applyMask<false, false>(Mask, MaskWords);
770 }
771
772 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
773 /// Don't resize. This computes "*this |= ~Mask".
774 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
775 applyMask<true, true>(Mask, MaskWords);
776 }
777
778 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
779 /// Don't resize. This computes "*this &= Mask".
780 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
781 applyMask<false, true>(Mask, MaskWords);
782 }
783
784 private:
785 /// Perform a logical left shift of \p Count words by moving everything
786 /// \p Count words to the right in memory.
787 ///
788 /// While confusing, words are stored from least significant at Bits[0] to
789 /// most significant at Bits[NumWords-1]. A logical shift left, however,
790 /// moves the current least significant bit to a higher logical index, and
791 /// fills the previous least significant bits with 0. Thus, we actually
792 /// need to move the bytes of the memory to the right, not to the left.
793 /// Example:
794 /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
795 /// represents a BitVector where 0xBBBBAAAA contain the least significant
796 /// bits. So if we want to shift the BitVector left by 2 words, we need to
797 /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
798 /// memmove which moves right, not left.
wordShl(uint32_t Count)799 void wordShl(uint32_t Count) {
800 if (Count == 0)
801 return;
802
803 uint32_t NumWords = NumBitWords(Size);
804
805 auto Src = Bits.take_front(NumWords).drop_back(Count);
806 auto Dest = Bits.take_front(NumWords).drop_front(Count);
807
808 // Since we always move Word-sized chunks of data with src and dest both
809 // aligned to a word-boundary, we don't need to worry about endianness
810 // here.
811 std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
812 std::memset(Bits.data(), 0, Count * sizeof(BitWord));
813 clear_unused_bits();
814 }
815
816 /// Perform a logical right shift of \p Count words by moving those
817 /// words to the left in memory. See wordShl for more information.
818 ///
wordShr(uint32_t Count)819 void wordShr(uint32_t Count) {
820 if (Count == 0)
821 return;
822
823 uint32_t NumWords = NumBitWords(Size);
824
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());
828
829 std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
830 std::memset(Dest.end(), 0, Count * sizeof(BitWord));
831 }
832
allocate(size_t NumWords)833 MutableArrayRef<BitWord> allocate(size_t NumWords) {
834 BitWord *RawBits = static_cast<BitWord *>(
835 safe_malloc(NumWords * sizeof(BitWord)));
836 return MutableArrayRef<BitWord>(RawBits, NumWords);
837 }
838
next_unset_in_word(int WordIndex,BitWord Word)839 int next_unset_in_word(int WordIndex, BitWord Word) const {
840 unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
841 return Result < size() ? Result : -1;
842 }
843
NumBitWords(unsigned S)844 unsigned NumBitWords(unsigned S) const {
845 return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
846 }
847
848 // Set the unused bits in the high words.
849 void set_unused_bits(bool t = true) {
850 // Set high words first.
851 unsigned UsedWords = NumBitWords(Size);
852 if (Bits.size() > UsedWords)
853 init_words(Bits.drop_front(UsedWords), t);
854
855 // Then set any stray high bits of the last used word.
856 unsigned ExtraBits = Size % BITWORD_SIZE;
857 if (ExtraBits) {
858 BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
859 if (t)
860 Bits[UsedWords-1] |= ExtraBitMask;
861 else
862 Bits[UsedWords-1] &= ~ExtraBitMask;
863 }
864 }
865
866 // Clear the unused bits in the high words.
clear_unused_bits()867 void clear_unused_bits() {
868 set_unused_bits(false);
869 }
870
grow(unsigned NewSize)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 *>(
875 safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
876 Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
877 clear_unused_bits();
878 }
879
init_words(MutableArrayRef<BitWord> B,bool t)880 void init_words(MutableArrayRef<BitWord> B, bool t) {
881 if (B.size() > 0)
882 memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
883 }
884
885 template<bool AddBits, bool InvertMask>
applyMask(const uint32_t * Mask,unsigned MaskWords)886 void applyMask(const uint32_t *Mask, unsigned MaskWords) {
887 static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
888 MaskWords = std::min(MaskWords, (size() + 31) / 32);
889 const unsigned Scale = BITWORD_SIZE / 32;
890 unsigned i;
891 for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
892 BitWord BW = Bits[i];
893 // This inner loop should unroll completely when BITWORD_SIZE > 32.
894 for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
895 uint32_t M = *Mask++;
896 if (InvertMask) M = ~M;
897 if (AddBits) BW |= BitWord(M) << b;
898 else BW &= ~(BitWord(M) << b);
899 }
900 Bits[i] = BW;
901 }
902 for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
903 uint32_t M = *Mask++;
904 if (InvertMask) M = ~M;
905 if (AddBits) Bits[i] |= BitWord(M) << b;
906 else Bits[i] &= ~(BitWord(M) << b);
907 }
908 if (AddBits)
909 clear_unused_bits();
910 }
911
912 public:
913 /// Return the size (in bytes) of the bit vector.
getMemorySize()914 size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
getBitCapacity()915 size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
916 };
917
capacity_in_bytes(const BitVector & X)918 inline size_t capacity_in_bytes(const BitVector &X) {
919 return X.getMemorySize();
920 }
921
922 template <> struct DenseMapInfo<BitVector> {
923 static inline BitVector getEmptyKey() { return BitVector(); }
924 static inline BitVector getTombstoneKey() {
925 BitVector V;
926 V.invalid();
927 return V;
928 }
929 static unsigned getHashValue(const BitVector &V) {
930 return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
931 std::make_pair(V.size(), V.getData()));
932 }
933 static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
934 if (LHS.isInvalid() || RHS.isInvalid())
935 return LHS.isInvalid() == RHS.isInvalid();
936 return LHS == RHS;
937 }
938 };
939 } // end namespace llvm
940
941 namespace std {
942 /// Implement std::swap in terms of BitVector swap.
943 inline void
944 swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
945 LHS.swap(RHS);
946 }
947 } // end namespace std
948
949 #endif // LLVM_ADT_BITVECTOR_H
950