LLVM  9.0.0svn
SmallBitVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/SmallBitVector.h - 'Normally small' 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 SmallBitVector class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_SMALLBITVECTOR_H
14 #define LLVM_ADT_SMALLBITVECTOR_H
15 
16 #include "llvm/ADT/BitVector.h"
19 #include <algorithm>
20 #include <cassert>
21 #include <climits>
22 #include <cstddef>
23 #include <cstdint>
24 #include <limits>
25 #include <utility>
26 
27 namespace llvm {
28 
29 /// This is a 'bitvector' (really, a variable-sized bit array), optimized for
30 /// the case when the array is small. It contains one pointer-sized field, which
31 /// is directly used as a plain collection of bits when possible, or as a
32 /// pointer to a larger heap-allocated array when necessary. This allows normal
33 /// "small" cases to be fast without losing generality for large inputs.
35  // TODO: In "large" mode, a pointer to a BitVector is used, leading to an
36  // unnecessary level of indirection. It would be more efficient to use a
37  // pointer to memory containing size, allocation size, and the array of bits.
38  uintptr_t X = 1;
39 
40  enum {
41  // The number of bits in this class.
42  NumBaseBits = sizeof(uintptr_t) * CHAR_BIT,
43 
44  // One bit is used to discriminate between small and large mode. The
45  // remaining bits are used for the small-mode representation.
46  SmallNumRawBits = NumBaseBits - 1,
47 
48  // A few more bits are used to store the size of the bit set in small mode.
49  // Theoretically this is a ceil-log2. These bits are encoded in the most
50  // significant bits of the raw bits.
51  SmallNumSizeBits = (NumBaseBits == 32 ? 5 :
52  NumBaseBits == 64 ? 6 :
53  SmallNumRawBits),
54 
55  // The remaining bits are used to store the actual set in small mode.
56  SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
57  };
58 
59  static_assert(NumBaseBits == 64 || NumBaseBits == 32,
60  "Unsupported word size");
61 
62 public:
64 
65  // Encapsulation of a single bit.
66  class reference {
67  SmallBitVector &TheVector;
68  unsigned BitPos;
69 
70  public:
71  reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
72 
73  reference(const reference&) = default;
74 
76  *this = bool(t);
77  return *this;
78  }
79 
80  reference& operator=(bool t) {
81  if (t)
82  TheVector.set(BitPos);
83  else
84  TheVector.reset(BitPos);
85  return *this;
86  }
87 
88  operator bool() const {
89  return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos);
90  }
91  };
92 
93 private:
94  BitVector *getPointer() const {
95  assert(!isSmall());
96  return reinterpret_cast<BitVector *>(X);
97  }
98 
99  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
100  X = 1;
101  setSmallSize(NewSize);
102  setSmallBits(NewSmallBits);
103  }
104 
105  void switchToLarge(BitVector *BV) {
106  X = reinterpret_cast<uintptr_t>(BV);
107  assert(!isSmall() && "Tried to use an unaligned pointer");
108  }
109 
110  // Return all the bits used for the "small" representation; this includes
111  // bits for the size as well as the element bits.
112  uintptr_t getSmallRawBits() const {
113  assert(isSmall());
114  return X >> 1;
115  }
116 
117  void setSmallRawBits(uintptr_t NewRawBits) {
118  assert(isSmall());
119  X = (NewRawBits << 1) | uintptr_t(1);
120  }
121 
122  // Return the size.
123  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
124 
125  void setSmallSize(size_t Size) {
126  setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
127  }
128 
129  // Return the element bits.
130  uintptr_t getSmallBits() const {
131  return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
132  }
133 
134  void setSmallBits(uintptr_t NewBits) {
135  setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
136  (getSmallSize() << SmallNumDataBits));
137  }
138 
139 public:
140  /// Creates an empty bitvector.
141  SmallBitVector() = default;
142 
143  /// Creates a bitvector of specified number of bits. All bits are initialized
144  /// to the specified value.
145  explicit SmallBitVector(unsigned s, bool t = false) {
146  if (s <= SmallNumDataBits)
147  switchToSmall(t ? ~uintptr_t(0) : 0, s);
148  else
149  switchToLarge(new BitVector(s, t));
150  }
151 
152  /// SmallBitVector copy ctor.
154  if (RHS.isSmall())
155  X = RHS.X;
156  else
157  switchToLarge(new BitVector(*RHS.getPointer()));
158  }
159 
160  SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) {
161  RHS.X = 1;
162  }
163 
165  if (!isSmall())
166  delete getPointer();
167  }
168 
171 
173  return const_set_bits_iterator(*this);
174  }
175 
177  return const_set_bits_iterator(*this, -1);
178  }
179 
182  }
183 
184  bool isSmall() const { return X & uintptr_t(1); }
185 
186  /// Tests whether there are no bits in this bitvector.
187  bool empty() const {
188  return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
189  }
190 
191  /// Returns the number of bits in this bitvector.
192  size_t size() const {
193  return isSmall() ? getSmallSize() : getPointer()->size();
194  }
195 
196  /// Returns the number of bits which are set.
197  size_type count() const {
198  if (isSmall()) {
199  uintptr_t Bits = getSmallBits();
200  return countPopulation(Bits);
201  }
202  return getPointer()->count();
203  }
204 
205  /// Returns true if any bit is set.
206  bool any() const {
207  if (isSmall())
208  return getSmallBits() != 0;
209  return getPointer()->any();
210  }
211 
212  /// Returns true if all bits are set.
213  bool all() const {
214  if (isSmall())
215  return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
216  return getPointer()->all();
217  }
218 
219  /// Returns true if none of the bits are set.
220  bool none() const {
221  if (isSmall())
222  return getSmallBits() == 0;
223  return getPointer()->none();
224  }
225 
226  /// Returns the index of the first set bit, -1 if none of the bits are set.
227  int find_first() const {
228  if (isSmall()) {
229  uintptr_t Bits = getSmallBits();
230  if (Bits == 0)
231  return -1;
232  return countTrailingZeros(Bits);
233  }
234  return getPointer()->find_first();
235  }
236 
237  int find_last() const {
238  if (isSmall()) {
239  uintptr_t Bits = getSmallBits();
240  if (Bits == 0)
241  return -1;
242  return NumBaseBits - countLeadingZeros(Bits) - 1;
243  }
244  return getPointer()->find_last();
245  }
246 
247  /// Returns the index of the first unset bit, -1 if all of the bits are set.
248  int find_first_unset() const {
249  if (isSmall()) {
250  if (count() == getSmallSize())
251  return -1;
252 
253  uintptr_t Bits = getSmallBits();
254  return countTrailingOnes(Bits);
255  }
256  return getPointer()->find_first_unset();
257  }
258 
259  int find_last_unset() const {
260  if (isSmall()) {
261  if (count() == getSmallSize())
262  return -1;
263 
264  uintptr_t Bits = getSmallBits();
265  // Set unused bits.
266  Bits |= ~uintptr_t(0) << getSmallSize();
267  return NumBaseBits - countLeadingOnes(Bits) - 1;
268  }
269  return getPointer()->find_last_unset();
270  }
271 
272  /// Returns the index of the next set bit following the "Prev" bit.
273  /// Returns -1 if the next set bit is not found.
274  int find_next(unsigned Prev) const {
275  if (isSmall()) {
276  uintptr_t Bits = getSmallBits();
277  // Mask off previous bits.
278  Bits &= ~uintptr_t(0) << (Prev + 1);
279  if (Bits == 0 || Prev + 1 >= getSmallSize())
280  return -1;
281  return countTrailingZeros(Bits);
282  }
283  return getPointer()->find_next(Prev);
284  }
285 
286  /// Returns the index of the next unset bit following the "Prev" bit.
287  /// Returns -1 if the next unset bit is not found.
288  int find_next_unset(unsigned Prev) const {
289  if (isSmall()) {
290  ++Prev;
291  uintptr_t Bits = getSmallBits();
292  // Mask in previous bits.
293  uintptr_t Mask = (1 << Prev) - 1;
294  Bits |= Mask;
295 
296  if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
297  return -1;
298  return countTrailingOnes(Bits);
299  }
300  return getPointer()->find_next_unset(Prev);
301  }
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 {
306  if (isSmall()) {
307  if (PriorTo == 0)
308  return -1;
309 
310  --PriorTo;
311  uintptr_t Bits = getSmallBits();
312  Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
313  if (Bits == 0)
314  return -1;
315 
316  return NumBaseBits - countLeadingZeros(Bits) - 1;
317  }
318  return getPointer()->find_prev(PriorTo);
319  }
320 
321  /// Clear all bits.
322  void clear() {
323  if (!isSmall())
324  delete getPointer();
325  switchToSmall(0, 0);
326  }
327 
328  /// Grow or shrink the bitvector.
329  void resize(unsigned N, bool t = false) {
330  if (!isSmall()) {
331  getPointer()->resize(N, t);
332  } else if (SmallNumDataBits >= N) {
333  uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
334  setSmallSize(N);
335  setSmallBits(NewBits | getSmallBits());
336  } else {
337  BitVector *BV = new BitVector(N, t);
338  uintptr_t OldBits = getSmallBits();
339  for (size_t i = 0, e = getSmallSize(); i != e; ++i)
340  (*BV)[i] = (OldBits >> i) & 1;
341  switchToLarge(BV);
342  }
343  }
344 
345  void reserve(unsigned N) {
346  if (isSmall()) {
347  if (N > SmallNumDataBits) {
348  uintptr_t OldBits = getSmallRawBits();
349  size_t SmallSize = getSmallSize();
350  BitVector *BV = new BitVector(SmallSize);
351  for (size_t i = 0; i < SmallSize; ++i)
352  if ((OldBits >> i) & 1)
353  BV->set(i);
354  BV->reserve(N);
355  switchToLarge(BV);
356  }
357  } else {
358  getPointer()->reserve(N);
359  }
360  }
361 
362  // Set, reset, flip
363  SmallBitVector &set() {
364  if (isSmall())
365  setSmallBits(~uintptr_t(0));
366  else
367  getPointer()->set();
368  return *this;
369  }
370 
371  SmallBitVector &set(unsigned Idx) {
372  if (isSmall()) {
373  assert(Idx <= static_cast<unsigned>(
374  std::numeric_limits<uintptr_t>::digits) &&
375  "undefined behavior");
376  setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
377  }
378  else
379  getPointer()->set(Idx);
380  return *this;
381  }
382 
383  /// Efficiently set a range of bits in [I, E)
384  SmallBitVector &set(unsigned I, unsigned E) {
385  assert(I <= E && "Attempted to set backwards range!");
386  assert(E <= size() && "Attempted to set out-of-bounds range!");
387  if (I == E) return *this;
388  if (isSmall()) {
389  uintptr_t EMask = ((uintptr_t)1) << E;
390  uintptr_t IMask = ((uintptr_t)1) << I;
391  uintptr_t Mask = EMask - IMask;
392  setSmallBits(getSmallBits() | Mask);
393  } else
394  getPointer()->set(I, E);
395  return *this;
396  }
397 
399  if (isSmall())
400  setSmallBits(0);
401  else
402  getPointer()->reset();
403  return *this;
404  }
405 
406  SmallBitVector &reset(unsigned Idx) {
407  if (isSmall())
408  setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
409  else
410  getPointer()->reset(Idx);
411  return *this;
412  }
413 
414  /// Efficiently reset a range of bits in [I, E)
415  SmallBitVector &reset(unsigned I, unsigned E) {
416  assert(I <= E && "Attempted to reset backwards range!");
417  assert(E <= size() && "Attempted to reset out-of-bounds range!");
418  if (I == E) return *this;
419  if (isSmall()) {
420  uintptr_t EMask = ((uintptr_t)1) << E;
421  uintptr_t IMask = ((uintptr_t)1) << I;
422  uintptr_t Mask = EMask - IMask;
423  setSmallBits(getSmallBits() & ~Mask);
424  } else
425  getPointer()->reset(I, E);
426  return *this;
427  }
428 
430  if (isSmall())
431  setSmallBits(~getSmallBits());
432  else
433  getPointer()->flip();
434  return *this;
435  }
436 
437  SmallBitVector &flip(unsigned Idx) {
438  if (isSmall())
439  setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
440  else
441  getPointer()->flip(Idx);
442  return *this;
443  }
444 
445  // No argument flip.
447  return SmallBitVector(*this).flip();
448  }
449 
450  // Indexing.
451  reference operator[](unsigned Idx) {
452  assert(Idx < size() && "Out-of-bounds Bit access.");
453  return reference(*this, Idx);
454  }
455 
456  bool operator[](unsigned Idx) const {
457  assert(Idx < size() && "Out-of-bounds Bit access.");
458  if (isSmall())
459  return ((getSmallBits() >> Idx) & 1) != 0;
460  return getPointer()->operator[](Idx);
461  }
462 
463  bool test(unsigned Idx) const {
464  return (*this)[Idx];
465  }
466 
467  // Push single bit to end of vector.
468  void push_back(bool Val) {
469  resize(size() + 1, Val);
470  }
471 
472  /// Test if any common bits are set.
473  bool anyCommon(const SmallBitVector &RHS) const {
474  if (isSmall() && RHS.isSmall())
475  return (getSmallBits() & RHS.getSmallBits()) != 0;
476  if (!isSmall() && !RHS.isSmall())
477  return getPointer()->anyCommon(*RHS.getPointer());
478 
479  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
480  if (test(i) && RHS.test(i))
481  return true;
482  return false;
483  }
484 
485  // Comparison operators.
486  bool operator==(const SmallBitVector &RHS) const {
487  if (size() != RHS.size())
488  return false;
489  if (isSmall() && RHS.isSmall())
490  return getSmallBits() == RHS.getSmallBits();
491  else if (!isSmall() && !RHS.isSmall())
492  return *getPointer() == *RHS.getPointer();
493  else {
494  for (size_t i = 0, e = size(); i != e; ++i) {
495  if ((*this)[i] != RHS[i])
496  return false;
497  }
498  return true;
499  }
500  }
501 
502  bool operator!=(const SmallBitVector &RHS) const {
503  return !(*this == RHS);
504  }
505 
506  // Intersection, union, disjoint union.
507  // FIXME BitVector::operator&= does not resize the LHS but this does
509  resize(std::max(size(), RHS.size()));
510  if (isSmall() && RHS.isSmall())
511  setSmallBits(getSmallBits() & RHS.getSmallBits());
512  else if (!isSmall() && !RHS.isSmall())
513  getPointer()->operator&=(*RHS.getPointer());
514  else {
515  size_t i, e;
516  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
517  (*this)[i] = test(i) && RHS.test(i);
518  for (e = size(); i != e; ++i)
519  reset(i);
520  }
521  return *this;
522  }
523 
524  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
526  if (isSmall() && RHS.isSmall())
527  setSmallBits(getSmallBits() & ~RHS.getSmallBits());
528  else if (!isSmall() && !RHS.isSmall())
529  getPointer()->reset(*RHS.getPointer());
530  else
531  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
532  if (RHS.test(i))
533  reset(i);
534 
535  return *this;
536  }
537 
538  /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
539  bool test(const SmallBitVector &RHS) const {
540  if (isSmall() && RHS.isSmall())
541  return (getSmallBits() & ~RHS.getSmallBits()) != 0;
542  if (!isSmall() && !RHS.isSmall())
543  return getPointer()->test(*RHS.getPointer());
544 
545  unsigned i, e;
546  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
547  if (test(i) && !RHS.test(i))
548  return true;
549 
550  for (e = size(); i != e; ++i)
551  if (test(i))
552  return true;
553 
554  return false;
555  }
556 
558  resize(std::max(size(), RHS.size()));
559  if (isSmall() && RHS.isSmall())
560  setSmallBits(getSmallBits() | RHS.getSmallBits());
561  else if (!isSmall() && !RHS.isSmall())
562  getPointer()->operator|=(*RHS.getPointer());
563  else {
564  for (size_t i = 0, e = RHS.size(); i != e; ++i)
565  (*this)[i] = test(i) || RHS.test(i);
566  }
567  return *this;
568  }
569 
571  resize(std::max(size(), RHS.size()));
572  if (isSmall() && RHS.isSmall())
573  setSmallBits(getSmallBits() ^ RHS.getSmallBits());
574  else if (!isSmall() && !RHS.isSmall())
575  getPointer()->operator^=(*RHS.getPointer());
576  else {
577  for (size_t i = 0, e = RHS.size(); i != e; ++i)
578  (*this)[i] = test(i) != RHS.test(i);
579  }
580  return *this;
581  }
582 
584  if (isSmall())
585  setSmallBits(getSmallBits() << N);
586  else
587  getPointer()->operator<<=(N);
588  return *this;
589  }
590 
592  if (isSmall())
593  setSmallBits(getSmallBits() >> N);
594  else
595  getPointer()->operator>>=(N);
596  return *this;
597  }
598 
599  // Assignment operator.
601  if (isSmall()) {
602  if (RHS.isSmall())
603  X = RHS.X;
604  else
605  switchToLarge(new BitVector(*RHS.getPointer()));
606  } else {
607  if (!RHS.isSmall())
608  *getPointer() = *RHS.getPointer();
609  else {
610  delete getPointer();
611  X = RHS.X;
612  }
613  }
614  return *this;
615  }
616 
618  if (this != &RHS) {
619  clear();
620  swap(RHS);
621  }
622  return *this;
623  }
624 
625  void swap(SmallBitVector &RHS) {
626  std::swap(X, RHS.X);
627  }
628 
629  /// Add '1' bits from Mask to this vector. Don't resize.
630  /// This computes "*this |= Mask".
631  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
632  if (isSmall())
633  applyMask<true, false>(Mask, MaskWords);
634  else
635  getPointer()->setBitsInMask(Mask, MaskWords);
636  }
637 
638  /// Clear any bits in this vector that are set in Mask. Don't resize.
639  /// This computes "*this &= ~Mask".
640  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
641  if (isSmall())
642  applyMask<false, false>(Mask, MaskWords);
643  else
644  getPointer()->clearBitsInMask(Mask, MaskWords);
645  }
646 
647  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
648  /// This computes "*this |= ~Mask".
649  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
650  if (isSmall())
651  applyMask<true, true>(Mask, MaskWords);
652  else
653  getPointer()->setBitsNotInMask(Mask, MaskWords);
654  }
655 
656  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
657  /// This computes "*this &= Mask".
658  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
659  if (isSmall())
660  applyMask<false, true>(Mask, MaskWords);
661  else
662  getPointer()->clearBitsNotInMask(Mask, MaskWords);
663  }
664 
665 private:
666  template <bool AddBits, bool InvertMask>
667  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
668  assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
669  uintptr_t M = Mask[0];
670  if (NumBaseBits == 64)
671  M |= uint64_t(Mask[1]) << 32;
672  if (InvertMask)
673  M = ~M;
674  if (AddBits)
675  setSmallBits(getSmallBits() | M);
676  else
677  setSmallBits(getSmallBits() & ~M);
678  }
679 };
680 
681 inline SmallBitVector
682 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
683  SmallBitVector Result(LHS);
684  Result &= RHS;
685  return Result;
686 }
687 
688 inline SmallBitVector
689 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
690  SmallBitVector Result(LHS);
691  Result |= RHS;
692  return Result;
693 }
694 
695 inline SmallBitVector
696 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
697  SmallBitVector Result(LHS);
698  Result ^= RHS;
699  return Result;
700 }
701 
702 } // end namespace llvm
703 
704 namespace std {
705 
706 /// Implement std::swap in terms of BitVector swap.
707 inline void
709  LHS.swap(RHS);
710 }
711 
712 } // end namespace std
713 
714 #endif // LLVM_ADT_SMALLBITVECTOR_H
void reserve(unsigned N)
Definition: BitVector.h:391
void reserve(unsigned N)
BitVector & set()
Definition: BitVector.h:397
bool none() const
Returns true if none of the bits are set.
void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Clear any bits in this vector that are set in Mask.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
int find_first_unset() const
Returns the index of the first unset bit, -1 if all of the bits are set.
This is a &#39;bitvector&#39; (really, a variable-sized bit array), optimized for the case when the array is ...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const SmallBitVector & operator=(SmallBitVector &&RHS)
reference operator[](unsigned Idx)
SmallBitVector & reset(unsigned I, unsigned E)
Efficiently reset a range of bits in [I, E)
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
const SmallBitVector & operator=(const SmallBitVector &RHS)
APInt operator^(APInt a, const APInt &b)
Definition: APInt.h:2018
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
APInt operator &(APInt a, const APInt &b)
Definition: APInt.h:1978
bool operator!=(const SmallBitVector &RHS) const
int find_prev(unsigned PriorTo) const
find_prev - Returns the index of the first set bit that precedes the the bit at PriorTo.
std::size_t countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the most significant bit to the least stopping at the first 1...
Definition: MathExtras.h:188
SmallBitVector & flip(unsigned Idx)
bool test(unsigned Idx) const
Definition: BitVector.h:937
SmallBitVector(unsigned s, bool t=false)
Creates a bitvector of specified number of bits.
std::size_t countTrailingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the least significant bit to the first zero bit.
Definition: MathExtras.h:477
reference & operator=(reference t)
SmallBitVector & reset(unsigned Idx)
bool operator==(const SmallBitVector &RHS) const
SmallBitVector & reset(const SmallBitVector &RHS)
Reset bits that are set in RHS. Same as *this &= ~RHS.
iterator_range< const_set_bits_iterator > set_bits() const
SmallBitVector operator~() const
reference & operator=(bool t)
SmallBitVector()=default
Creates an empty bitvector.
reference(SmallBitVector &b, unsigned Idx)
std::size_t countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0&#39;s from the least significant bit to the most stopping at the first 1...
Definition: MathExtras.h:119
void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Clear a bit in this vector for every &#39;0&#39; bit in Mask.
void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Add a bit to this vector for every &#39;0&#39; bit in Mask.
const_set_bits_iterator set_bits_begin() const
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const_set_bits_iterator_impl< SmallBitVector > const_set_bits_iterator
const_set_bits_iterator set_bits_end() const
int find_next_unset(unsigned Prev) const
Returns the index of the next unset bit following the "Prev" bit.
bool anyCommon(const SmallBitVector &RHS) const
Test if any common bits are set.
ForwardIterator for the bits that are set.
Definition: BitVector.h:31
SmallBitVector & set()
SmallBitVector & reset()
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void clear()
Clear all bits.
SmallBitVector & operator^=(const SmallBitVector &RHS)
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:519
SmallBitVector(const SmallBitVector &RHS)
SmallBitVector copy ctor.
bool test(const SmallBitVector &RHS) const
Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
SmallBitVector & operator &=(const SmallBitVector &RHS)
size_t size() const
Returns the number of bits in this bitvector.
int find_next(unsigned Prev) const
Returns the index of the next set bit following the "Prev" bit.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
A range adaptor for a pair of iterators.
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Add &#39;1&#39; bits from Mask to this vector.
SmallBitVector & operator<<=(unsigned N)
void swap(SmallBitVector &RHS)
SmallBitVector & flip()
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
bool all() const
Returns true if all bits are set.
uint32_t Size
Definition: Profile.cpp:46
int find_last_unset() const
int find_first() const
Returns the index of the first set bit, -1 if none of the bits are set.
bool operator[](unsigned Idx) const
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SmallBitVector & operator>>=(unsigned N)
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
bool any() const
Returns true if any bit is set.
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:1998
bool empty() const
Tests whether there are no bits in this bitvector.
std::size_t countLeadingOnes(T Value, ZeroBehavior ZB=ZB_Width)
Count the number of ones from the most significant bit to the first zero bit.
Definition: MathExtras.h:461
void push_back(bool Val)
size_type count() const
Returns the number of bits which are set.
SmallBitVector & operator|=(const SmallBitVector &RHS)
SmallBitVector(SmallBitVector &&RHS)