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