Line data Source code
1 : //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the BitVector class.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ADT_BITVECTOR_H
15 : #define LLVM_ADT_BITVECTOR_H
16 :
17 : #include "llvm/ADT/ArrayRef.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 :
36 0 : void advance() {
37 : assert(Current != -1 && "Trying to advance past end.");
38 49699 : Current = Parent.find_next(Current);
39 0 : }
40 0 :
41 : public:
42 0 : const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
43 0 : : Parent(Parent), Current(Current) {}
44 0 : explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
45 29659 : : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
46 0 : const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
47 0 :
48 : const_set_bits_iterator_impl operator++(int) {
49 : auto Prev = *this;
50 : advance();
51 : return Prev;
52 : }
53 8 :
54 : const_set_bits_iterator_impl &operator++() {
55 : advance();
56 : return *this;
57 : }
58 :
59 46268602 : 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 29 : bool operator!=(const const_set_bits_iterator_impl &Other) const {
68 : assert(&Parent == &Other.Parent &&
69 0 : "Comparing iterators from different BitVectors");
70 0 : return Current != Other.Current;
71 : }
72 0 : };
73 :
74 0 : class BitVector {
75 : typedef unsigned long BitWord;
76 :
77 0 : enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
78 :
79 0 : static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
80 : "Unsupported word size");
81 :
82 0 : MutableArrayRef<BitWord> Bits; // Actual bits.
83 : unsigned Size; // Size of bitvector in bits.
84 :
85 0 : public:
86 : typedef unsigned size_type;
87 : // Encapsulation of a single bit.
88 0 : class reference {
89 : friend class BitVector;
90 0 :
91 : BitWord *WordRef;
92 : unsigned BitPos;
93 0 :
94 : public:
95 0 : reference(BitVector &b, unsigned Idx) {
96 524862358 : WordRef = &b.Bits[Idx / BITWORD_SIZE];
97 524877279 : BitPos = Idx % BITWORD_SIZE;
98 0 : }
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 2293986 : if (t)
110 10693521 : *WordRef |= BitWord(1) << BitPos;
111 : else
112 4730815 : *WordRef &= ~(BitWord(1) << BitPos);
113 : return *this;
114 : }
115 :
116 0 : operator bool() const {
117 517456798 : 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 :
124 584 : const_set_bits_iterator set_bits_begin() const {
125 65 : return const_set_bits_iterator(*this);
126 : }
127 : const_set_bits_iterator set_bits_end() const {
128 : return const_set_bits_iterator(*this, -1);
129 : }
130 : iterator_range<const_set_bits_iterator> set_bits() const {
131 0 : return make_range(set_bits_begin(), set_bits_end());
132 0 : }
133 0 :
134 : /// BitVector default ctor - Creates an empty bitvector.
135 27162548 : BitVector() : Size(0) {}
136 :
137 208 : /// BitVector ctor - Creates a bitvector of specified number of bits. All
138 61 : /// bits are initialized to the specified value.
139 37788351 : explicit BitVector(unsigned s, bool t = false) : Size(s) {
140 37788501 : size_t Capacity = NumBitWords(s);
141 37788346 : Bits = allocate(Capacity);
142 37788346 : init_words(Bits, t);
143 37788346 : if (t)
144 0 : clear_unused_bits();
145 37788735 : }
146 :
147 : /// BitVector copy ctor.
148 3313161 : BitVector(const BitVector &RHS) : Size(RHS.size()) {
149 3313161 : if (Size == 0) {
150 52813 : Bits = MutableArrayRef<BitWord>();
151 52813 : return;
152 : }
153 :
154 6520696 : size_t Capacity = NumBitWords(RHS.size());
155 3260348 : Bits = allocate(Capacity);
156 3260348 : std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
157 : }
158 :
159 682917 : BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
160 679160 : RHS.Bits = MutableArrayRef<BitWord>();
161 243282 : RHS.Size = 0;
162 : }
163 61 :
164 19744821 : ~BitVector() { std::free(Bits.data()); }
165 :
166 : /// empty - Tests whether there are no bits in this bitvector.
167 38 : bool empty() const { return Size == 0; }
168 36 :
169 36 : /// size - Returns the number of bits in this bitvector.
170 36 : size_type size() const { return Size; }
171 36 :
172 : /// count - Returns the number of bits which are set.
173 36 : size_type count() const {
174 : unsigned NumBits = 0;
175 2155517 : for (unsigned i = 0; i < NumBitWords(size()); ++i)
176 1876426 : NumBits += countPopulation(Bits[i]);
177 7 : return NumBits;
178 1 : }
179 1 :
180 : /// any - Returns true if any bit is set.
181 : bool any() const {
182 618817 : for (unsigned i = 0; i < NumBitWords(size()); ++i)
183 1617600 : if (Bits[i] != 0)
184 6 : return true;
185 : return false;
186 : }
187 1 :
188 1 : /// all - Returns true if all bits are set.
189 38449 : bool all() const {
190 38448 : for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
191 0 : if (Bits[i] != ~0UL)
192 42 : return false;
193 :
194 : // If bits remain check that they are ones. The unused bits are always zero.
195 38461 : if (unsigned Remainder = Size % BITWORD_SIZE)
196 76896 : return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
197 :
198 0 : return true;
199 : }
200 :
201 : /// none - Returns true if none of the bits are set.
202 : bool none() const {
203 64350 : return !any();
204 342 : }
205 :
206 : /// find_first_in - Returns the index of the first set bit in the range
207 : /// [Begin, End). Returns -1 if all bits in the range are unset.
208 53338270 : int find_first_in(unsigned Begin, unsigned End) const {
209 : assert(Begin <= End && End <= Size);
210 53338294 : if (Begin == End)
211 76 : return -1;
212 :
213 53065876 : unsigned FirstWord = Begin / BITWORD_SIZE;
214 53065876 : unsigned LastWord = (End - 1) / BITWORD_SIZE;
215 :
216 : // Check subsequent words.
217 92680555 : for (unsigned i = FirstWord; i <= LastWord; ++i) {
218 89585718 : BitWord Copy = Bits[i];
219 20 :
220 89585691 : if (i == FirstWord) {
221 53065876 : unsigned FirstBit = Begin % BITWORD_SIZE;
222 : Copy &= maskTrailingZeros<BitWord>(FirstBit);
223 17 : }
224 12 :
225 89585691 : if (i == LastWord) {
226 8890774 : unsigned LastBit = (End - 1) % BITWORD_SIZE;
227 17781548 : Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
228 : }
229 89585691 : if (Copy != 0)
230 99942066 : return i * BITWORD_SIZE + countTrailingZeros(Copy);
231 21 : }
232 : return -1;
233 : }
234 :
235 : /// find_last_in - Returns the index of the last set bit in the range
236 184 : /// [Begin, End). Returns -1 if all bits in the range are unset.
237 18 : int find_last_in(unsigned Begin, unsigned End) const {
238 184 : assert(Begin <= End && End <= Size);
239 18 : if (Begin == End)
240 : return -1;
241 172 :
242 190 : unsigned LastWord = (End - 1) / BITWORD_SIZE;
243 18 : unsigned FirstWord = Begin / BITWORD_SIZE;
244 :
245 256 : for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
246 209 : unsigned CurrentWord = i - 1;
247 :
248 209 : BitWord Copy = Bits[CurrentWord];
249 191 : if (CurrentWord == LastWord) {
250 22 : unsigned LastBit = (End - 1) % BITWORD_SIZE;
251 36 : Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
252 : }
253 190 :
254 85 : if (CurrentWord == FirstWord) {
255 151 : unsigned FirstBit = Begin % BITWORD_SIZE;
256 18 : Copy &= maskTrailingZeros<BitWord>(FirstBit);
257 201 : }
258 330 :
259 19 : if (Copy != 0)
260 0 : return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
261 : }
262 :
263 : return -1;
264 : }
265 25 :
266 : /// find_first_unset_in - Returns the index of the first unset bit in the
267 25 : /// range [Begin, End). Returns -1 if all bits in the range are set.
268 18 : int find_first_unset_in(unsigned Begin, unsigned End) const {
269 : assert(Begin <= End && End <= Size);
270 42 : if (Begin == End)
271 24 : return -1;
272 :
273 72 : unsigned FirstWord = Begin / BITWORD_SIZE;
274 51 : unsigned LastWord = (End - 1) / BITWORD_SIZE;
275 :
276 33 : // Check subsequent words.
277 51 : for (unsigned i = FirstWord; i <= LastWord; ++i) {
278 42 : BitWord Copy = Bits[i];
279 52 :
280 18 : if (i == FirstWord) {
281 18 : unsigned FirstBit = Begin % BITWORD_SIZE;
282 51 : Copy |= maskTrailingOnes<BitWord>(FirstBit);
283 18 : }
284 19 :
285 18 : if (i == LastWord) {
286 17 : unsigned LastBit = (End - 1) % BITWORD_SIZE;
287 78 : Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
288 50 : }
289 18 : if (Copy != ~0UL) {
290 18 : unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
291 18 : return Result < size() ? Result : -1;
292 : }
293 : }
294 : return -1;
295 : }
296 59 :
297 : /// find_last_unset_in - Returns the index of the last unset bit in the
298 59 : /// range [Begin, End). Returns -1 if all bits in the range are set.
299 : int find_last_unset_in(unsigned Begin, unsigned End) const {
300 : assert(Begin <= End && End <= Size);
301 52 : if (Begin == End)
302 52 : return -1;
303 :
304 : unsigned LastWord = (End - 1) / BITWORD_SIZE;
305 58 : unsigned FirstWord = Begin / BITWORD_SIZE;
306 54 :
307 : for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
308 54 : unsigned CurrentWord = i - 1;
309 52 :
310 52 : BitWord Copy = Bits[CurrentWord];
311 : if (CurrentWord == LastWord) {
312 : unsigned LastBit = (End - 1) % BITWORD_SIZE;
313 54 : Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
314 34 : }
315 68 :
316 : if (CurrentWord == FirstWord) {
317 54 : unsigned FirstBit = Begin % BITWORD_SIZE;
318 48 : Copy |= maskTrailingOnes<BitWord>(FirstBit);
319 48 : }
320 :
321 : if (Copy != ~0UL) {
322 : unsigned Result =
323 : (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
324 : return Result < Size ? Result : -1;
325 : }
326 : }
327 36 : return -1;
328 : }
329 36 :
330 : /// find_first - Returns the index of the first set bit, -1 if none
331 : /// of the bits are set.
332 3462940 : int find_first() const { return find_first_in(0, Size); }
333 31 :
334 : /// find_last - Returns the index of the last set bit, -1 if none of the bits
335 37 : /// are set.
336 33 : int find_last() const { return find_last_in(0, Size); }
337 :
338 33 : /// find_next - Returns the index of the next set bit following the
339 33 : /// "Prev" bit. Returns -1 if the next set bit is not found.
340 49828834 : int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
341 62 :
342 : /// find_prev - Returns the index of the first set bit that precedes the
343 : /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
344 33 : int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
345 21 :
346 21 : /// find_first_unset - Returns the index of the first unset bit, -1 if all
347 : /// of the bits are set.
348 18 : int find_first_unset() const { return find_first_unset_in(0, Size); }
349 33 :
350 : /// find_next_unset - Returns the index of the next unset bit following the
351 27 : /// "Prev" bit. Returns -1 if all remaining bits are set.
352 27 : int find_next_unset(unsigned Prev) const {
353 0 : return find_first_unset_in(Prev + 1, Size);
354 : }
355 :
356 : /// find_last_unset - Returns the index of the last unset bit, -1 if all of
357 : /// the bits are set.
358 : int find_last_unset() const { return find_last_unset_in(0, Size); }
359 :
360 41 : /// find_prev_unset - Returns the index of the first unset bit that precedes
361 : /// the bit at \p PriorTo. Returns -1 if all previous bits are set.
362 : int find_prev_unset(unsigned PriorTo) {
363 : return find_last_unset_in(0, PriorTo);
364 7 : }
365 :
366 : /// clear - Removes all bits from the bitvector. Does not change capacity.
367 0 : void clear() {
368 18632624 : Size = 0;
369 0 : }
370 :
371 : /// resize - Grow or shrink the bitvector.
372 14872494 : void resize(unsigned N, bool t = false) {
373 29744956 : if (N > getBitCapacity()) {
374 : unsigned OldCapacity = Bits.size();
375 6171081 : grow(N);
376 6171092 : init_words(Bits.drop_front(OldCapacity), t);
377 : }
378 :
379 : // Set any old unused bits that are now included in the BitVector. This
380 : // may set bits that are not included in the new vector, but we will clear
381 24 : // them back out below.
382 14872480 : if (N > Size)
383 13998999 : set_unused_bits(t);
384 :
385 : // Update the size, and clear out any bits that are now unused
386 14872489 : unsigned OldSize = Size;
387 14872480 : Size = N;
388 14872480 : if (t || N < OldSize)
389 : clear_unused_bits();
390 14872480 : }
391 :
392 : void reserve(unsigned N) {
393 : if (N > getBitCapacity())
394 : grow(N);
395 0 : }
396 2 :
397 0 : // Set, reset, flip
398 8 : BitVector &set() {
399 : init_words(Bits, true);
400 229 : clear_unused_bits();
401 466 : return *this;
402 : }
403 44 :
404 44 : BitVector &set(unsigned Idx) {
405 : assert(Bits.data() && "Bits never allocated");
406 376524849 : Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
407 : return *this;
408 : }
409 :
410 229 : /// set - Efficiently set a range of bits in [I, E)
411 2428 : BitVector &set(unsigned I, unsigned E) {
412 : assert(I <= E && "Attempted to set backwards range!");
413 : assert(E <= size() && "Attempted to set out-of-bounds range!");
414 229 :
415 2435 : if (I == E) return *this;
416 229 :
417 2206 : if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
418 2361 : BitWord EMask = 1UL << (E % BITWORD_SIZE);
419 2132 : BitWord IMask = 1UL << (I % BITWORD_SIZE);
420 2132 : BitWord Mask = EMask - IMask;
421 2132 : Bits[I / BITWORD_SIZE] |= Mask;
422 2132 : return *this;
423 : }
424 :
425 74 : BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
426 82 : Bits[I / BITWORD_SIZE] |= PrefixMask;
427 148 : I = alignTo(I, BITWORD_SIZE);
428 :
429 135 : for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
430 106 : Bits[I / BITWORD_SIZE] = ~0UL;
431 :
432 74 : BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
433 74 : if (I < E)
434 264 : Bits[I / BITWORD_SIZE] |= PostfixMask;
435 :
436 : return *this;
437 : }
438 :
439 65 : BitVector &reset() {
440 : init_words(Bits, false);
441 : return *this;
442 : }
443 65 :
444 : BitVector &reset(unsigned Idx) {
445 52083481 : Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
446 42 : return *this;
447 42 : }
448 42 :
449 42 : /// reset - Efficiently reset a range of bits in [I, E)
450 880 : BitVector &reset(unsigned I, unsigned E) {
451 : assert(I <= E && "Attempted to reset backwards range!");
452 : assert(E <= size() && "Attempted to reset out-of-bounds range!");
453 23 :
454 861 : if (I == E) return *this;
455 46 :
456 838 : if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
457 844 : BitWord EMask = 1UL << (E % BITWORD_SIZE);
458 829 : BitWord IMask = 1UL << (I % BITWORD_SIZE);
459 813 : BitWord Mask = EMask - IMask;
460 836 : Bits[I / BITWORD_SIZE] &= ~Mask;
461 836 : return *this;
462 42 : }
463 :
464 25 : BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
465 25 : Bits[I / BITWORD_SIZE] &= ~PrefixMask;
466 50 : I = alignTo(I, BITWORD_SIZE);
467 :
468 26 : for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
469 2 : Bits[I / BITWORD_SIZE] = 0UL;
470 :
471 25 : BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
472 25 : if (I < E)
473 116 : Bits[I / BITWORD_SIZE] &= ~PostfixMask;
474 :
475 : return *this;
476 : }
477 :
478 10181 : BitVector &flip() {
479 150392 : for (unsigned i = 0; i < NumBitWords(size()); ++i)
480 86696 : Bits[i] = ~Bits[i];
481 : clear_unused_bits();
482 10181 : return *this;
483 : }
484 7 :
485 1 : BitVector &flip(unsigned Idx) {
486 1 : Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
487 1 : return *this;
488 1 : }
489 1 :
490 : // Indexing.
491 : reference operator[](unsigned Idx) {
492 6 : assert (Idx < Size && "Out-of-bounds Bit access.");
493 6 : return reference(*this, Idx);
494 12 : }
495 :
496 14 : bool operator[](unsigned Idx) const {
497 16 : assert (Idx < Size && "Out-of-bounds Bit access.");
498 901117227 : BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
499 1998572051 : return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
500 6 : }
501 8 :
502 : bool test(unsigned Idx) const {
503 : return (*this)[Idx];
504 : }
505 :
506 9 : // Push single bit to end of vector.
507 190485720 : void push_back(bool Val) {
508 190485686 : unsigned OldSize = Size;
509 190485654 : unsigned NewSize = Size + 1;
510 9 :
511 : // Resize, which will insert zeros.
512 : // If we already fit then the unused bits will be already zero.
513 380971308 : if (NewSize > getBitCapacity())
514 160045 : resize(NewSize, false);
515 : else
516 190325615 : Size = NewSize;
517 :
518 : // If true, set single bit.
519 190485654 : if (Val)
520 : set(OldSize);
521 190485654 : }
522 :
523 : /// Test if any common bits are set.
524 3951598 : bool anyCommon(const BitVector &RHS) const {
525 7903196 : unsigned ThisWords = NumBitWords(size());
526 7903261 : unsigned RHSWords = NumBitWords(RHS.size());
527 7593365 : for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
528 11900376 : if (Bits[i] & RHS.Bits[i])
529 : return true;
530 : return false;
531 : }
532 :
533 : // Comparison operators.
534 1351302 : bool operator==(const BitVector &RHS) const {
535 2702807 : unsigned ThisWords = NumBitWords(size());
536 2702807 : unsigned RHSWords = NumBitWords(RHS.size());
537 203 : unsigned i;
538 19065898 : for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
539 26935077 : if (Bits[i] != RHS.Bits[i])
540 : return false;
541 406 :
542 2 : // Verify that any extra words are all zeros.
543 1230241 : if (i != ThisWords) {
544 201 : for (; i != ThisWords; ++i)
545 0 : if (Bits[i])
546 : return false;
547 1230444 : } else if (i != RHSWords) {
548 0 : for (; i != RHSWords; ++i)
549 203 : if (RHS.Bits[i])
550 : return false;
551 : }
552 18 : return true;
553 36 : }
554 36 :
555 30 : bool operator!=(const BitVector &RHS) const {
556 1266004 : return !(*this == RHS);
557 : }
558 :
559 : /// Intersection, union, disjoint union.
560 43812 : BitVector &operator&=(const BitVector &RHS) {
561 87624 : unsigned ThisWords = NumBitWords(size());
562 87661 : unsigned RHSWords = NumBitWords(RHS.size());
563 74 : unsigned i;
564 166911 : for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
565 369075 : Bits[i] &= RHS.Bits[i];
566 171 :
567 213 : // Any bits that are just in this bitvector become zero, because they aren't
568 : // in the RHS bit vector. Any words only in RHS are ignored because they
569 : // are already zero in the LHS.
570 43812 : for (; i != ThisWords; ++i)
571 33 : Bits[i] = 0;
572 0 :
573 43812 : return *this;
574 : }
575 33 :
576 0 : /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
577 28777618 : BitVector &reset(const BitVector &RHS) {
578 57555236 : unsigned ThisWords = NumBitWords(size());
579 57555236 : unsigned RHSWords = NumBitWords(RHS.size());
580 : unsigned i;
581 57845374 : for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
582 87203268 : Bits[i] &= ~RHS.Bits[i];
583 28777618 : return *this;
584 2 : }
585 :
586 : /// test - Check if (This - RHS) is zero.
587 : /// This is the same as reset(RHS) and any().
588 762283 : bool test(const BitVector &RHS) const {
589 1524566 : unsigned ThisWords = NumBitWords(size());
590 1524566 : unsigned RHSWords = NumBitWords(RHS.size());
591 : unsigned i;
592 2013384 : for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
593 1885302 : if ((Bits[i] & ~RHS.Bits[i]) != 0)
594 : return true;
595 :
596 791665 : for (; i != ThisWords ; ++i)
597 633366 : if (Bits[i] != 0)
598 1 : return true;
599 0 :
600 : return false;
601 1 : }
602 :
603 30124994 : BitVector &operator|=(const BitVector &RHS) {
604 30124994 : if (size() < RHS.size())
605 880028 : resize(RHS.size());
606 61436087 : for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
607 62622170 : Bits[i] |= RHS.Bits[i];
608 30124994 : return *this;
609 17 : }
610 27 :
611 8 : BitVector &operator^=(const BitVector &RHS) {
612 : if (size() < RHS.size())
613 : resize(RHS.size());
614 : for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
615 : Bits[i] ^= RHS.Bits[i];
616 14 : return *this;
617 28 : }
618 28 :
619 : BitVector &operator>>=(unsigned N) {
620 34 : assert(N <= Size);
621 48 : if (LLVM_UNLIKELY(empty() || N == 0))
622 : return *this;
623 :
624 8 : unsigned NumWords = NumBitWords(Size);
625 0 : assert(NumWords >= 1);
626 :
627 : wordShr(N / BITWORD_SIZE);
628 :
629 : unsigned BitDistance = N % BITWORD_SIZE;
630 : if (BitDistance == 0)
631 1 : return *this;
632 1 :
633 1 : // When the shift size is not a multiple of the word size, then we have
634 2 : // a tricky situation where each word in succession needs to extract some
635 2 : // of the bits from the next word and or them into this word while
636 1 : // shifting this word to make room for the new bits. This has to be done
637 : // for every word in the array.
638 :
639 2 : // Since we're shifting each word right, some bits will fall off the end
640 2 : // of each word to the right, and empty space will be created on the left.
641 1 : // The final word in the array will lose bits permanently, so starting at
642 6 : // the beginning, work forwards shifting each word to the right, and
643 8 : // OR'ing in the bits from the end of the next word to the beginning of
644 2 : // the current word.
645 :
646 : // Example:
647 8 : // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
648 : // by 4 bits.
649 8 : // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
650 : // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
651 : // Step 3: Word[1] >>= 4 ; 0x0EEFF001
652 : // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
653 : // Step 5: Word[2] >>= 4 ; 0x02334455
654 : // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
655 8 : const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
656 : const unsigned LSH = BITWORD_SIZE - BitDistance;
657 8 :
658 8 : for (unsigned I = 0; I < NumWords - 1; ++I) {
659 : Bits[I] >>= BitDistance;
660 : Bits[I] |= (Bits[I + 1] & Mask) << LSH;
661 : }
662 :
663 : Bits[NumWords - 1] >>= BitDistance;
664 :
665 : return *this;
666 : }
667 :
668 0 : BitVector &operator<<=(unsigned N) {
669 : assert(N <= Size);
670 0 : if (LLVM_UNLIKELY(empty() || N == 0))
671 : return *this;
672 :
673 : unsigned NumWords = NumBitWords(Size);
674 : assert(NumWords >= 1);
675 :
676 0 : wordShl(N / BITWORD_SIZE);
677 :
678 0 : unsigned BitDistance = N % BITWORD_SIZE;
679 0 : if (BitDistance == 0)
680 : return *this;
681 :
682 : // When the shift size is not a multiple of the word size, then we have
683 : // a tricky situation where each word in succession needs to extract some
684 6 : // of the bits from the previous word and or them into this word while
685 : // shifting this word to make room for the new bits. This has to be done
686 14 : // for every word in the array. This is similar to the algorithm outlined
687 8 : // in operator>>=, but backwards.
688 16 :
689 : // Since we're shifting each word left, some bits will fall off the end
690 : // of each word to the left, and empty space will be created on the right.
691 6 : // The first word in the array will lose bits permanently, so starting at
692 : // the end, work backwards shifting each word to the left, and OR'ing
693 6 : // in the bits from the end of the next word to the beginning of the
694 : // current word.
695 :
696 9 : // Example:
697 : // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
698 9 : // by 4 bits.
699 : // Step 1: Word[2] <<= 4 ; 0x23344550
700 : // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
701 : // Step 3: Word[1] <<= 4 ; 0xEFF00110
702 : // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
703 : // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
704 9 : // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
705 : const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
706 9 : const unsigned RSH = BITWORD_SIZE - BitDistance;
707 9 :
708 0 : for (int I = NumWords - 1; I > 0; --I) {
709 0 : Bits[I] <<= BitDistance;
710 0 : Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
711 : }
712 0 : Bits[0] <<= BitDistance;
713 : clear_unused_bits();
714 :
715 0 : return *this;
716 : }
717 :
718 : // Assignment operator.
719 3029385 : const BitVector &operator=(const BitVector &RHS) {
720 3029385 : if (this == &RHS) return *this;
721 :
722 3029385 : Size = RHS.size();
723 : unsigned RHSWords = NumBitWords(Size);
724 6058770 : if (Size <= getBitCapacity()) {
725 1198296 : if (Size)
726 2396552 : std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
727 : clear_unused_bits();
728 1198296 : return *this;
729 : }
730 :
731 : // Grow the bitvector to have enough elements.
732 : unsigned NewCapacity = RHSWords;
733 : assert(NewCapacity > 0 && "negative capacity?");
734 1831096 : auto NewBits = allocate(NewCapacity);
735 1831090 : std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
736 23 :
737 16 : // Destroy the old bits.
738 1831122 : std::free(Bits.data());
739 1831090 : Bits = NewBits;
740 7 :
741 1831090 : return *this;
742 : }
743 7 :
744 : const BitVector &operator=(BitVector &&RHS) {
745 1792 : if (this == &RHS) return *this;
746 :
747 7673477 : std::free(Bits.data());
748 7673493 : Bits = RHS.Bits;
749 3101022 : Size = RHS.Size;
750 11 :
751 1621 : RHS.Bits = MutableArrayRef<BitWord>();
752 673 : RHS.Size = 0;
753 9 :
754 14 : return *this;
755 : }
756 9 :
757 : void swap(BitVector &RHS) {
758 : std::swap(Bits, RHS.Bits);
759 : std::swap(Size, RHS.Size);
760 : }
761 :
762 2 : //===--------------------------------------------------------------------===//
763 2 : // Portable bit mask operations.
764 : //===--------------------------------------------------------------------===//
765 : //
766 2 : // These methods all operate on arrays of uint32_t, each holding 32 bits. The
767 2 : // fixed word size makes it easier to work with literal bit vector constants
768 : // in portable code.
769 2 : //
770 : // The LSB in each word is the lowest numbered bit. The size of a portable
771 : // bit mask is always a whole multiple of 32 bits. If no bit mask size is
772 : // given, the bit mask is assumed to cover the entire BitVector.
773 :
774 : /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
775 2 : /// This computes "*this |= Mask".
776 3 : void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
777 2036633 : applyMask<true, false>(Mask, MaskWords);
778 : }
779 1 :
780 1 : /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
781 : /// Don't resize. This computes "*this &= ~Mask".
782 : void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
783 : applyMask<false, false>(Mask, MaskWords);
784 : }
785 :
786 : /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
787 : /// Don't resize. This computes "*this |= ~Mask".
788 : void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
789 2271461 : applyMask<true, true>(Mask, MaskWords);
790 : }
791 :
792 : /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
793 : /// Don't resize. This computes "*this &= Mask".
794 : void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
795 1637378 : applyMask<false, true>(Mask, MaskWords);
796 : }
797 :
798 : private:
799 : /// Perform a logical left shift of \p Count words by moving everything
800 : /// \p Count words to the right in memory.
801 : ///
802 : /// While confusing, words are stored from least significant at Bits[0] to
803 : /// most significant at Bits[NumWords-1]. A logical shift left, however,
804 : /// moves the current least significant bit to a higher logical index, and
805 7 : /// fills the previous least significant bits with 0. Thus, we actually
806 : /// need to move the bytes of the memory to the right, not to the left.
807 : /// Example:
808 : /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
809 : /// represents a BitVector where 0xBBBBAAAA contain the least significant
810 : /// bits. So if we want to shift the BitVector left by 2 words, we need to
811 : /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
812 : /// memmove which moves right, not left.
813 0 : void wordShl(uint32_t Count) {
814 0 : if (Count == 0)
815 : return;
816 :
817 6 : uint32_t NumWords = NumBitWords(Size);
818 :
819 0 : auto Src = Bits.take_front(NumWords).drop_back(Count);
820 : auto Dest = Bits.take_front(NumWords).drop_front(Count);
821 :
822 : // Since we always move Word-sized chunks of data with src and dest both
823 2 : // aligned to a word-boundary, we don't need to worry about endianness
824 : // here.
825 0 : std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
826 0 : std::memset(Bits.data(), 0, Count * sizeof(BitWord));
827 : clear_unused_bits();
828 : }
829 :
830 : /// Perform a logical right shift of \p Count words by moving those
831 : /// words to the left in memory. See wordShl for more information.
832 : ///
833 : void wordShr(uint32_t Count) {
834 : if (Count == 0)
835 : return;
836 :
837 : uint32_t NumWords = NumBitWords(Size);
838 :
839 : auto Src = Bits.take_front(NumWords).drop_front(Count);
840 : auto Dest = Bits.take_front(NumWords).drop_back(Count);
841 9 : assert(Dest.size() == Src.size());
842 9 :
843 : std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
844 : std::memset(Dest.end(), 0, Count * sizeof(BitWord));
845 4 : }
846 :
847 4 : MutableArrayRef<BitWord> allocate(size_t NumWords) {
848 : BitWord *RawBits = static_cast<BitWord *>(
849 1831089 : safe_malloc(NumWords * sizeof(BitWord)));
850 0 : return MutableArrayRef<BitWord>(RawBits, NumWords);
851 : }
852 :
853 4 : int next_unset_in_word(int WordIndex, BitWord Word) const {
854 4 : unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
855 : return Result < size() ? Result : -1;
856 : }
857 :
858 0 : unsigned NumBitWords(unsigned S) const {
859 122852608 : return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
860 : }
861 8 :
862 8 : // Set the unused bits in the high words.
863 26230382 : void set_unused_bits(bool t = true) {
864 : // Set high words first.
865 26230386 : unsigned UsedWords = NumBitWords(Size);
866 26230382 : if (Bits.size() > UsedWords)
867 20038993 : init_words(Bits.drop_front(UsedWords), t);
868 :
869 : // Then set any stray high bits of the last used word.
870 26230382 : unsigned ExtraBits = Size % BITWORD_SIZE;
871 26230386 : if (ExtraBits) {
872 6213432 : BitWord ExtraBitMask = ~0UL << ExtraBits;
873 6213428 : if (t)
874 2704 : Bits[UsedWords-1] |= ExtraBitMask;
875 0 : else
876 12424152 : Bits[UsedWords-1] &= ~ExtraBitMask;
877 2 : }
878 26230382 : }
879 :
880 : // Clear the unused bits in the high words.
881 : void clear_unused_bits() {
882 6060305 : set_unused_bits(false);
883 : }
884 :
885 6171082 : void grow(unsigned NewSize) {
886 6171082 : size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
887 422 : assert(NewCapacity > 0 && "realloc-ing zero space");
888 : BitWord *NewBits = static_cast<BitWord *>(
889 12342164 : safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
890 6171081 : Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
891 421 : clear_unused_bits();
892 6171083 : }
893 421 :
894 421 : void init_words(MutableArrayRef<BitWord> B, bool t) {
895 65522844 : if (B.size() > 0)
896 65455807 : memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
897 : }
898 421 :
899 421 : template<bool AddBits, bool InvertMask>
900 5945799 : void applyMask(const uint32_t *Mask, unsigned MaskWords) {
901 329 : static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
902 11891114 : MaskWords = std::min(MaskWords, (size() + 31) / 32);
903 : const unsigned Scale = BITWORD_SIZE / 32;
904 484 : unsigned i;
905 25013364 : for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
906 38136209 : BitWord BW = Bits[i];
907 : // This inner loop should unroll completely when BITWORD_SIZE > 32.
908 57203682 : for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
909 38135788 : uint32_t M = *Mask++;
910 31918058 : if (InvertMask) M = ~M;
911 24480900 : if (AddBits) BW |= BitWord(M) << b;
912 13654888 : else BW &= ~(BitWord(M) << b);
913 44 : }
914 19067938 : Bits[i] = BW;
915 : }
916 9910015 : for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
917 3964633 : uint32_t M = *Mask++;
918 3800840 : if (InvertMask) M = ~M;
919 4845730 : if (AddBits) Bits[i] |= BitWord(M) << b;
920 3083404 : else Bits[i] &= ~(BitWord(M) << b);
921 : }
922 : if (AddBits)
923 293 : clear_unused_bits();
924 5945763 : }
925 :
926 : public:
927 : /// Return the size (in bytes) of the bit vector.
928 16 : size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
929 208387517 : size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
930 15 : };
931 :
932 : inline size_t capacity_in_bytes(const BitVector &X) {
933 23 : return X.getMemorySize();
934 16 : }
935 :
936 24 : } // end namespace llvm
937 16 :
938 8 : namespace std {
939 16 : /// Implement std::swap in terms of BitVector swap.
940 0 : inline void
941 : swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
942 8 : LHS.swap(RHS);
943 : }
944 28 : } // end namespace std
945 13 :
946 8 : #endif // LLVM_ADT_BITVECTOR_H
|
