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