LLVM  13.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 // This file implements the BitVector class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LLVM_ADT_BITVECTOR_H
14 #define LLVM_ADT_BITVECTOR_H
15 
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMapInfo.h"
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  void advance() {
37  assert(Current != -1 && "Trying to advance past end.");
38  Current = Parent.find_next(Current);
39  }
40 
41 public:
42  const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
43  : Parent(Parent), Current(Current) {}
44  explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
45  : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
47 
49  auto Prev = *this;
50  advance();
51  return Prev;
52  }
53 
55  advance();
56  return *this;
57  }
58 
59  unsigned operator*() const { return Current; }
60 
61  bool operator==(const const_set_bits_iterator_impl &Other) const {
62  assert(&Parent == &Other.Parent &&
63  "Comparing iterators from different BitVectors");
64  return Current == Other.Current;
65  }
66 
67  bool operator!=(const const_set_bits_iterator_impl &Other) const {
68  assert(&Parent == &Other.Parent &&
69  "Comparing iterators from different BitVectors");
70  return Current != Other.Current;
71  }
72 };
73 
74 class BitVector {
75  typedef uintptr_t BitWord;
76 
77  enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
78 
79  static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
80  "Unsupported word size");
81 
82  MutableArrayRef<BitWord> Bits; // Actual bits.
83  unsigned Size; // Size of bitvector in bits.
84 
85 public:
86  typedef unsigned size_type;
87  // Encapsulation of a single bit.
88  class reference {
89  friend class BitVector;
90 
91  BitWord *WordRef;
92  unsigned BitPos;
93 
94  public:
95  reference(BitVector &b, unsigned Idx) {
96  WordRef = &b.Bits[Idx / BITWORD_SIZE];
97  BitPos = Idx % BITWORD_SIZE;
98  }
99 
100  reference() = delete;
101  reference(const reference&) = default;
102 
104  *this = bool(t);
105  return *this;
106  }
107 
109  if (t)
110  *WordRef |= BitWord(1) << BitPos;
111  else
112  *WordRef &= ~(BitWord(1) << BitPos);
113  return *this;
114  }
115 
116  operator bool() const {
117  return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
118  }
119  };
120 
123 
125  return const_set_bits_iterator(*this);
126  }
128  return const_set_bits_iterator(*this, -1);
129  }
132  }
133 
134  /// BitVector default ctor - Creates an empty bitvector.
135  BitVector() : Size(0) {}
136 
137  /// BitVector ctor - Creates a bitvector of specified number of bits. All
138  /// bits are initialized to the specified value.
139  explicit BitVector(unsigned s, bool t = false) : Size(s) {
140  size_t Capacity = NumBitWords(s);
141  Bits = allocate(Capacity);
142  init_words(Bits, t);
143  if (t)
144  clear_unused_bits();
145  }
146 
147  /// BitVector copy ctor.
148  BitVector(const BitVector &RHS) : Size(RHS.size()) {
149  if (Size == 0) {
151  return;
152  }
153 
154  size_t Capacity = NumBitWords(RHS.size());
155  Bits = allocate(Capacity);
156  std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
157  }
158 
159  BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
160  RHS.Bits = MutableArrayRef<BitWord>();
161  RHS.Size = 0;
162  }
163 
164  ~BitVector() { std::free(Bits.data()); }
165 
166  /// empty - Tests whether there are no bits in this bitvector.
167  bool empty() const { return Size == 0; }
168 
169  /// size - Returns the number of bits in this bitvector.
170  size_type size() const { return Size; }
171 
172  /// count - Returns the number of bits which are set.
173  size_type count() const {
174  unsigned NumBits = 0;
175  for (unsigned i = 0; i < NumBitWords(size()); ++i)
176  NumBits += countPopulation(Bits[i]);
177  return NumBits;
178  }
179 
180  /// any - Returns true if any bit is set.
181  bool any() const {
182  for (unsigned i = 0; i < NumBitWords(size()); ++i)
183  if (Bits[i] != 0)
184  return true;
185  return false;
186  }
187 
188  /// all - Returns true if all bits are set.
189  bool all() const {
190  for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
191  if (Bits[i] != ~BitWord(0))
192  return false;
193 
194  // If bits remain check that they are ones. The unused bits are always zero.
195  if (unsigned Remainder = Size % BITWORD_SIZE)
196  return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
197 
198  return true;
199  }
200 
201  /// none - Returns true if none of the bits are set.
202  bool none() const {
203  return !any();
204  }
205 
206  /// find_first_in - Returns the index of the first set / unset bit,
207  /// depending on \p Set, in the range [Begin, End).
208  /// Returns -1 if all bits in the range are unset / set.
209  int find_first_in(unsigned Begin, unsigned End, bool Set = true) const {
210  assert(Begin <= End && End <= Size);
211  if (Begin == End)
212  return -1;
213 
214  unsigned FirstWord = Begin / BITWORD_SIZE;
215  unsigned LastWord = (End - 1) / BITWORD_SIZE;
216 
217  // Check subsequent words.
218  // The code below is based on search for the first _set_ bit. If
219  // we're searching for the first _unset_, we just take the
220  // complement of each word before we use it and apply
221  // the same method.
222  for (unsigned i = FirstWord; i <= LastWord; ++i) {
223  BitWord Copy = Bits[i];
224  if (!Set)
225  Copy = ~Copy;
226 
227  if (i == FirstWord) {
228  unsigned FirstBit = Begin % BITWORD_SIZE;
229  Copy &= maskTrailingZeros<BitWord>(FirstBit);
230  }
231 
232  if (i == LastWord) {
233  unsigned LastBit = (End - 1) % BITWORD_SIZE;
234  Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
235  }
236  if (Copy != 0)
237  return i * BITWORD_SIZE + countTrailingZeros(Copy);
238  }
239  return -1;
240  }
241 
242  /// find_last_in - Returns the index of the last set bit in the range
243  /// [Begin, End). Returns -1 if all bits in the range are unset.
244  int find_last_in(unsigned Begin, unsigned End) const {
245  assert(Begin <= End && End <= Size);
246  if (Begin == End)
247  return -1;
248 
249  unsigned LastWord = (End - 1) / BITWORD_SIZE;
250  unsigned FirstWord = Begin / BITWORD_SIZE;
251 
252  for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
253  unsigned CurrentWord = i - 1;
254 
255  BitWord Copy = Bits[CurrentWord];
256  if (CurrentWord == LastWord) {
257  unsigned LastBit = (End - 1) % BITWORD_SIZE;
258  Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
259  }
260 
261  if (CurrentWord == FirstWord) {
262  unsigned FirstBit = Begin % BITWORD_SIZE;
263  Copy &= maskTrailingZeros<BitWord>(FirstBit);
264  }
265 
266  if (Copy != 0)
267  return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
268  }
269 
270  return -1;
271  }
272 
273  /// find_first_unset_in - Returns the index of the first unset bit in the
274  /// range [Begin, End). Returns -1 if all bits in the range are set.
275  int find_first_unset_in(unsigned Begin, unsigned End) const {
276  return find_first_in(Begin, End, /* Set = */ false);
277  }
278 
279  /// find_last_unset_in - Returns the index of the last unset bit in the
280  /// range [Begin, End). Returns -1 if all bits in the range are set.
281  int find_last_unset_in(unsigned Begin, unsigned End) const {
282  assert(Begin <= End && End <= Size);
283  if (Begin == End)
284  return -1;
285 
286  unsigned LastWord = (End - 1) / BITWORD_SIZE;
287  unsigned FirstWord = Begin / BITWORD_SIZE;
288 
289  for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
290  unsigned CurrentWord = i - 1;
291 
292  BitWord Copy = Bits[CurrentWord];
293  if (CurrentWord == LastWord) {
294  unsigned LastBit = (End - 1) % BITWORD_SIZE;
295  Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
296  }
297 
298  if (CurrentWord == FirstWord) {
299  unsigned FirstBit = Begin % BITWORD_SIZE;
300  Copy |= maskTrailingOnes<BitWord>(FirstBit);
301  }
302 
303  if (Copy != ~BitWord(0)) {
304  unsigned Result =
305  (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
306  return Result < Size ? Result : -1;
307  }
308  }
309  return -1;
310  }
311 
312  /// find_first - Returns the index of the first set bit, -1 if none
313  /// of the bits are set.
314  int find_first() const { return find_first_in(0, Size); }
315 
316  /// find_last - Returns the index of the last set bit, -1 if none of the bits
317  /// are set.
318  int find_last() const { return find_last_in(0, Size); }
319 
320  /// find_next - Returns the index of the next set bit following the
321  /// "Prev" bit. Returns -1 if the next set bit is not found.
322  int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
323 
324  /// find_prev - Returns the index of the first set bit that precedes the
325  /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
326  int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
327 
328  /// find_first_unset - Returns the index of the first unset bit, -1 if all
329  /// of the bits are set.
330  int find_first_unset() const { return find_first_unset_in(0, Size); }
331 
332  /// find_next_unset - Returns the index of the next unset bit following the
333  /// "Prev" bit. Returns -1 if all remaining bits are set.
334  int find_next_unset(unsigned Prev) const {
335  return find_first_unset_in(Prev + 1, Size);
336  }
337 
338  /// find_last_unset - Returns the index of the last unset bit, -1 if all of
339  /// the bits are set.
340  int find_last_unset() const { return find_last_unset_in(0, Size); }
341 
342  /// find_prev_unset - Returns the index of the first unset bit that precedes
343  /// the bit at \p PriorTo. Returns -1 if all previous bits are set.
344  int find_prev_unset(unsigned PriorTo) {
345  return find_last_unset_in(0, PriorTo);
346  }
347 
348  /// clear - Removes all bits from the bitvector. Does not change capacity.
349  void clear() {
350  Size = 0;
351  }
352 
353  /// resize - Grow or shrink the bitvector.
354  void resize(unsigned N, bool t = false) {
355  if (N > getBitCapacity()) {
356  unsigned OldCapacity = Bits.size();
357  grow(N);
358  init_words(Bits.drop_front(OldCapacity), t);
359  }
360 
361  // Set any old unused bits that are now included in the BitVector. This
362  // may set bits that are not included in the new vector, but we will clear
363  // them back out below.
364  if (N > Size)
365  set_unused_bits(t);
366 
367  // Update the size, and clear out any bits that are now unused
368  unsigned OldSize = Size;
369  Size = N;
370  if (t || N < OldSize)
371  clear_unused_bits();
372  }
373 
374  void reserve(unsigned N) {
375  if (N > getBitCapacity())
376  grow(N);
377  }
378 
379  // Set, reset, flip
381  init_words(Bits, true);
382  clear_unused_bits();
383  return *this;
384  }
385 
386  BitVector &set(unsigned Idx) {
387  assert(Bits.data() && "Bits never allocated");
388  Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
389  return *this;
390  }
391 
392  /// set - Efficiently set a range of bits in [I, E)
393  BitVector &set(unsigned I, unsigned E) {
394  assert(I <= E && "Attempted to set backwards range!");
395  assert(E <= size() && "Attempted to set out-of-bounds range!");
396 
397  if (I == E) return *this;
398 
399  if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
400  BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
401  BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
402  BitWord Mask = EMask - IMask;
403  Bits[I / BITWORD_SIZE] |= Mask;
404  return *this;
405  }
406 
407  BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
408  Bits[I / BITWORD_SIZE] |= PrefixMask;
409  I = alignTo(I, BITWORD_SIZE);
410 
411  for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
412  Bits[I / BITWORD_SIZE] = ~BitWord(0);
413 
414  BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
415  if (I < E)
416  Bits[I / BITWORD_SIZE] |= PostfixMask;
417 
418  return *this;
419  }
420 
422  init_words(Bits, false);
423  return *this;
424  }
425 
426  BitVector &reset(unsigned Idx) {
427  Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
428  return *this;
429  }
430 
431  /// reset - Efficiently reset a range of bits in [I, E)
432  BitVector &reset(unsigned I, unsigned E) {
433  assert(I <= E && "Attempted to reset backwards range!");
434  assert(E <= size() && "Attempted to reset out-of-bounds range!");
435 
436  if (I == E) return *this;
437 
438  if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
439  BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
440  BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
441  BitWord Mask = EMask - IMask;
442  Bits[I / BITWORD_SIZE] &= ~Mask;
443  return *this;
444  }
445 
446  BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
447  Bits[I / BITWORD_SIZE] &= ~PrefixMask;
448  I = alignTo(I, BITWORD_SIZE);
449 
450  for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
451  Bits[I / BITWORD_SIZE] = BitWord(0);
452 
453  BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
454  if (I < E)
455  Bits[I / BITWORD_SIZE] &= ~PostfixMask;
456 
457  return *this;
458  }
459 
461  for (unsigned i = 0; i < NumBitWords(size()); ++i)
462  Bits[i] = ~Bits[i];
463  clear_unused_bits();
464  return *this;
465  }
466 
467  BitVector &flip(unsigned Idx) {
468  Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
469  return *this;
470  }
471 
472  // Indexing.
473  reference operator[](unsigned Idx) {
474  assert (Idx < Size && "Out-of-bounds Bit access.");
475  return reference(*this, Idx);
476  }
477 
478  bool operator[](unsigned Idx) const {
479  assert (Idx < Size && "Out-of-bounds Bit access.");
480  BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
481  return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
482  }
483 
484  bool test(unsigned Idx) const {
485  return (*this)[Idx];
486  }
487 
488  // Push single bit to end of vector.
489  void push_back(bool Val) {
490  unsigned OldSize = Size;
491  unsigned NewSize = Size + 1;
492 
493  // Resize, which will insert zeros.
494  // If we already fit then the unused bits will be already zero.
495  if (NewSize > getBitCapacity())
496  resize(NewSize, false);
497  else
498  Size = NewSize;
499 
500  // If true, set single bit.
501  if (Val)
502  set(OldSize);
503  }
504 
505  /// Test if any common bits are set.
506  bool anyCommon(const BitVector &RHS) const {
507  unsigned ThisWords = NumBitWords(size());
508  unsigned RHSWords = NumBitWords(RHS.size());
509  for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
510  if (Bits[i] & RHS.Bits[i])
511  return true;
512  return false;
513  }
514 
515  // Comparison operators.
516  bool operator==(const BitVector &RHS) const {
517  if (size() != RHS.size())
518  return false;
519  unsigned NumWords = NumBitWords(size());
520  return Bits.take_front(NumWords) == RHS.Bits.take_front(NumWords);
521  }
522 
523  bool operator!=(const BitVector &RHS) const {
524  return !(*this == RHS);
525  }
526 
527  /// Intersection, union, disjoint union.
529  unsigned ThisWords = NumBitWords(size());
530  unsigned RHSWords = NumBitWords(RHS.size());
531  unsigned i;
532  for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
533  Bits[i] &= RHS.Bits[i];
534 
535  // Any bits that are just in this bitvector become zero, because they aren't
536  // in the RHS bit vector. Any words only in RHS are ignored because they
537  // are already zero in the LHS.
538  for (; i != ThisWords; ++i)
539  Bits[i] = 0;
540 
541  return *this;
542  }
543 
544  /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
545  BitVector &reset(const BitVector &RHS) {
546  unsigned ThisWords = NumBitWords(size());
547  unsigned RHSWords = NumBitWords(RHS.size());
548  unsigned i;
549  for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
550  Bits[i] &= ~RHS.Bits[i];
551  return *this;
552  }
553 
554  /// test - Check if (This - RHS) is zero.
555  /// This is the same as reset(RHS) and any().
556  bool test(const BitVector &RHS) const {
557  unsigned ThisWords = NumBitWords(size());
558  unsigned RHSWords = NumBitWords(RHS.size());
559  unsigned i;
560  for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
561  if ((Bits[i] & ~RHS.Bits[i]) != 0)
562  return true;
563 
564  for (; i != ThisWords ; ++i)
565  if (Bits[i] != 0)
566  return true;
567 
568  return false;
569  }
570 
572  if (size() < RHS.size())
573  resize(RHS.size());
574  for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
575  Bits[i] |= RHS.Bits[i];
576  return *this;
577  }
578 
580  if (size() < RHS.size())
581  resize(RHS.size());
582  for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
583  Bits[i] ^= RHS.Bits[i];
584  return *this;
585  }
586 
587  BitVector &operator>>=(unsigned N) {
588  assert(N <= Size);
589  if (LLVM_UNLIKELY(empty() || N == 0))
590  return *this;
591 
592  unsigned NumWords = NumBitWords(Size);
593  assert(NumWords >= 1);
594 
595  wordShr(N / BITWORD_SIZE);
596 
597  unsigned BitDistance = N % BITWORD_SIZE;
598  if (BitDistance == 0)
599  return *this;
600 
601  // When the shift size is not a multiple of the word size, then we have
602  // a tricky situation where each word in succession needs to extract some
603  // of the bits from the next word and or them into this word while
604  // shifting this word to make room for the new bits. This has to be done
605  // for every word in the array.
606 
607  // Since we're shifting each word right, some bits will fall off the end
608  // of each word to the right, and empty space will be created on the left.
609  // The final word in the array will lose bits permanently, so starting at
610  // the beginning, work forwards shifting each word to the right, and
611  // OR'ing in the bits from the end of the next word to the beginning of
612  // the current word.
613 
614  // Example:
615  // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
616  // by 4 bits.
617  // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
618  // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
619  // Step 3: Word[1] >>= 4 ; 0x0EEFF001
620  // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
621  // Step 5: Word[2] >>= 4 ; 0x02334455
622  // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
623  const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
624  const unsigned LSH = BITWORD_SIZE - BitDistance;
625 
626  for (unsigned I = 0; I < NumWords - 1; ++I) {
627  Bits[I] >>= BitDistance;
628  Bits[I] |= (Bits[I + 1] & Mask) << LSH;
629  }
630 
631  Bits[NumWords - 1] >>= BitDistance;
632 
633  return *this;
634  }
635 
636  BitVector &operator<<=(unsigned N) {
637  assert(N <= Size);
638  if (LLVM_UNLIKELY(empty() || N == 0))
639  return *this;
640 
641  unsigned NumWords = NumBitWords(Size);
642  assert(NumWords >= 1);
643 
644  wordShl(N / BITWORD_SIZE);
645 
646  unsigned BitDistance = N % BITWORD_SIZE;
647  if (BitDistance == 0)
648  return *this;
649 
650  // When the shift size is not a multiple of the word size, then we have
651  // a tricky situation where each word in succession needs to extract some
652  // of the bits from the previous word and or them into this word while
653  // shifting this word to make room for the new bits. This has to be done
654  // for every word in the array. This is similar to the algorithm outlined
655  // in operator>>=, but backwards.
656 
657  // Since we're shifting each word left, some bits will fall off the end
658  // of each word to the left, and empty space will be created on the right.
659  // The first word in the array will lose bits permanently, so starting at
660  // the end, work backwards shifting each word to the left, and OR'ing
661  // in the bits from the end of the next word to the beginning of the
662  // current word.
663 
664  // Example:
665  // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
666  // by 4 bits.
667  // Step 1: Word[2] <<= 4 ; 0x23344550
668  // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
669  // Step 3: Word[1] <<= 4 ; 0xEFF00110
670  // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
671  // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
672  // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
673  const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
674  const unsigned RSH = BITWORD_SIZE - BitDistance;
675 
676  for (int I = NumWords - 1; I > 0; --I) {
677  Bits[I] <<= BitDistance;
678  Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
679  }
680  Bits[0] <<= BitDistance;
681  clear_unused_bits();
682 
683  return *this;
684  }
685 
686  // Assignment operator.
687  const BitVector &operator=(const BitVector &RHS) {
688  if (this == &RHS) return *this;
689 
690  Size = RHS.size();
691 
692  // Handle tombstone when the BitVector is a key of a DenseHash.
693  if (RHS.isInvalid()) {
694  std::free(Bits.data());
695  Bits = None;
696  return *this;
697  }
698 
699  unsigned RHSWords = NumBitWords(Size);
700  if (Size <= getBitCapacity()) {
701  if (Size)
702  std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
703  clear_unused_bits();
704  return *this;
705  }
706 
707  // Grow the bitvector to have enough elements.
708  unsigned NewCapacity = RHSWords;
709  assert(NewCapacity > 0 && "negative capacity?");
710  auto NewBits = allocate(NewCapacity);
711  std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
712 
713  // Destroy the old bits.
714  std::free(Bits.data());
715  Bits = NewBits;
716 
717  return *this;
718  }
719 
720  const BitVector &operator=(BitVector &&RHS) {
721  if (this == &RHS) return *this;
722 
723  std::free(Bits.data());
724  Bits = RHS.Bits;
725  Size = RHS.Size;
726 
727  RHS.Bits = MutableArrayRef<BitWord>();
728  RHS.Size = 0;
729 
730  return *this;
731  }
732 
733  void swap(BitVector &RHS) {
734  std::swap(Bits, RHS.Bits);
735  std::swap(Size, RHS.Size);
736  }
737 
738  void invalid() {
739  assert(!Size && Bits.empty());
740  Size = (unsigned)-1;
741  }
742  bool isInvalid() const { return Size == (unsigned)-1; }
743 
745  return Bits.take_front(NumBitWords(size()));
746  }
747 
748  //===--------------------------------------------------------------------===//
749  // Portable bit mask operations.
750  //===--------------------------------------------------------------------===//
751  //
752  // These methods all operate on arrays of uint32_t, each holding 32 bits. The
753  // fixed word size makes it easier to work with literal bit vector constants
754  // in portable code.
755  //
756  // The LSB in each word is the lowest numbered bit. The size of a portable
757  // bit mask is always a whole multiple of 32 bits. If no bit mask size is
758  // given, the bit mask is assumed to cover the entire BitVector.
759 
760  /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
761  /// This computes "*this |= Mask".
762  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
763  applyMask<true, false>(Mask, MaskWords);
764  }
765 
766  /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
767  /// Don't resize. This computes "*this &= ~Mask".
768  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
769  applyMask<false, false>(Mask, MaskWords);
770  }
771 
772  /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
773  /// Don't resize. This computes "*this |= ~Mask".
774  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
775  applyMask<true, true>(Mask, MaskWords);
776  }
777 
778  /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
779  /// Don't resize. This computes "*this &= Mask".
780  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
781  applyMask<false, true>(Mask, MaskWords);
782  }
783 
784 private:
785  /// Perform a logical left shift of \p Count words by moving everything
786  /// \p Count words to the right in memory.
787  ///
788  /// While confusing, words are stored from least significant at Bits[0] to
789  /// most significant at Bits[NumWords-1]. A logical shift left, however,
790  /// moves the current least significant bit to a higher logical index, and
791  /// fills the previous least significant bits with 0. Thus, we actually
792  /// need to move the bytes of the memory to the right, not to the left.
793  /// Example:
794  /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
795  /// represents a BitVector where 0xBBBBAAAA contain the least significant
796  /// bits. So if we want to shift the BitVector left by 2 words, we need to
797  /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
798  /// memmove which moves right, not left.
799  void wordShl(uint32_t Count) {
800  if (Count == 0)
801  return;
802 
803  uint32_t NumWords = NumBitWords(Size);
804 
805  auto Src = Bits.take_front(NumWords).drop_back(Count);
806  auto Dest = Bits.take_front(NumWords).drop_front(Count);
807 
808  // Since we always move Word-sized chunks of data with src and dest both
809  // aligned to a word-boundary, we don't need to worry about endianness
810  // here.
811  std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
812  std::memset(Bits.data(), 0, Count * sizeof(BitWord));
813  clear_unused_bits();
814  }
815 
816  /// Perform a logical right shift of \p Count words by moving those
817  /// words to the left in memory. See wordShl for more information.
818  ///
819  void wordShr(uint32_t Count) {
820  if (Count == 0)
821  return;
822 
823  uint32_t NumWords = NumBitWords(Size);
824 
825  auto Src = Bits.take_front(NumWords).drop_front(Count);
826  auto Dest = Bits.take_front(NumWords).drop_back(Count);
827  assert(Dest.size() == Src.size());
828 
829  std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
830  std::memset(Dest.end(), 0, Count * sizeof(BitWord));
831  }
832 
833  MutableArrayRef<BitWord> allocate(size_t NumWords) {
834  BitWord *RawBits = static_cast<BitWord *>(
835  safe_malloc(NumWords * sizeof(BitWord)));
836  return MutableArrayRef<BitWord>(RawBits, NumWords);
837  }
838 
839  int next_unset_in_word(int WordIndex, BitWord Word) const {
840  unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
841  return Result < size() ? Result : -1;
842  }
843 
844  unsigned NumBitWords(unsigned S) const {
845  return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
846  }
847 
848  // Set the unused bits in the high words.
849  void set_unused_bits(bool t = true) {
850  // Set high words first.
851  unsigned UsedWords = NumBitWords(Size);
852  if (Bits.size() > UsedWords)
853  init_words(Bits.drop_front(UsedWords), t);
854 
855  // Then set any stray high bits of the last used word.
856  unsigned ExtraBits = Size % BITWORD_SIZE;
857  if (ExtraBits) {
858  BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
859  if (t)
860  Bits[UsedWords-1] |= ExtraBitMask;
861  else
862  Bits[UsedWords-1] &= ~ExtraBitMask;
863  }
864  }
865 
866  // Clear the unused bits in the high words.
867  void clear_unused_bits() {
868  set_unused_bits(false);
869  }
870 
871  void grow(unsigned NewSize) {
872  size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
873  assert(NewCapacity > 0 && "realloc-ing zero space");
874  BitWord *NewBits = static_cast<BitWord *>(
875  safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
876  Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
877  clear_unused_bits();
878  }
879 
880  void init_words(MutableArrayRef<BitWord> B, bool t) {
881  if (B.size() > 0)
882  memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
883  }
884 
885  template<bool AddBits, bool InvertMask>
886  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
887  static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
888  MaskWords = std::min(MaskWords, (size() + 31) / 32);
889  const unsigned Scale = BITWORD_SIZE / 32;
890  unsigned i;
891  for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
892  BitWord BW = Bits[i];
893  // This inner loop should unroll completely when BITWORD_SIZE > 32.
894  for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
895  uint32_t M = *Mask++;
896  if (InvertMask) M = ~M;
897  if (AddBits) BW |= BitWord(M) << b;
898  else BW &= ~(BitWord(M) << b);
899  }
900  Bits[i] = BW;
901  }
902  for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
903  uint32_t M = *Mask++;
904  if (InvertMask) M = ~M;
905  if (AddBits) Bits[i] |= BitWord(M) << b;
906  else Bits[i] &= ~(BitWord(M) << b);
907  }
908  if (AddBits)
909  clear_unused_bits();
910  }
911 
912 public:
913  /// Return the size (in bytes) of the bit vector.
914  size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
915  size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
916 };
917 
918 inline size_t capacity_in_bytes(const BitVector &X) {
919  return X.getMemorySize();
920 }
921 
922 template <> struct DenseMapInfo<BitVector> {
923  static inline BitVector getEmptyKey() { return BitVector(); }
924  static inline BitVector getTombstoneKey() {
925  BitVector V;
926  V.invalid();
927  return V;
928  }
929  static unsigned getHashValue(const BitVector &V) {
931  std::make_pair(V.size(), V.getData()));
932  }
933  static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
934  if (LHS.isInvalid() || RHS.isInvalid())
935  return LHS.isInvalid() == RHS.isInvalid();
936  return LHS == RHS;
937  }
938 };
939 } // end namespace llvm
940 
941 namespace std {
942  /// Implement std::swap in terms of BitVector swap.
943  inline void
945  LHS.swap(RHS);
946  }
947 } // end namespace std
948 
949 #endif // LLVM_ADT_BITVECTOR_H
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
i
i
Definition: README.txt:29
llvm::alignTo
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:158
llvm::BitVector::operator[]
reference operator[](unsigned Idx)
Definition: BitVector.h:473
llvm::BitVector::push_back
void push_back(bool Val)
Definition: BitVector.h:489
MathExtras.h
llvm
This class represents lattice values for constants.
Definition: AllocatorList.h:23
llvm::const_set_bits_iterator_impl::const_set_bits_iterator_impl
const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
Definition: BitVector.h:42
llvm::BitVector::BitVector
BitVector(const BitVector &RHS)
BitVector copy ctor.
Definition: BitVector.h:148
llvm::BitVector::setBitsNotInMask
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:774
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::BitVector::operator[]
bool operator[](unsigned Idx) const
Definition: BitVector.h:478
llvm::BitVector::reference::reference
reference(BitVector &b, unsigned Idx)
Definition: BitVector.h:95
llvm::BitVector::getData
ArrayRef< BitWord > getData() const
Definition: BitVector.h:744
llvm::BitVector::find_last_unset_in
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:281
llvm::BitVector::reserve
void reserve(unsigned N)
Definition: BitVector.h:374
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:380
llvm::BitVector::clear
void clear()
clear - Removes all bits from the bitvector. Does not change capacity.
Definition: BitVector.h:349
llvm::BitVector::operator|=
BitVector & operator|=(const BitVector &RHS)
Definition: BitVector.h:571
llvm::BitVector::none
bool none() const
none - Returns true if none of the bits are set.
Definition: BitVector.h:202
llvm::BitVector::set_bits
iterator_range< const_set_bits_iterator > set_bits() const
Definition: BitVector.h:130
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:354
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::BitVector::reference::operator=
reference & operator=(bool t)
Definition: BitVector.h:108
llvm::DenseMapInfo< BitVector >::isEqual
static bool isEqual(const BitVector &LHS, const BitVector &RHS)
Definition: BitVector.h:933
llvm::DenseMapInfo< BitVector >::getEmptyKey
static BitVector getEmptyKey()
Definition: BitVector.h:923
llvm::BitVector::find_next_unset
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:334
llvm::BitVector::set_bits_begin
const_set_bits_iterator set_bits_begin() const
Definition: BitVector.h:124
llvm::BitVector::reference
Definition: BitVector.h:88
llvm::BitVector::find_first_in
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:209
llvm::BitVector::test
bool test(const BitVector &RHS) const
test - Check if (This - RHS) is zero.
Definition: BitVector.h:556
llvm::countLeadingOnes
unsigned 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:510
llvm::BitmaskEnumDetail::Mask
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
llvm::BitVector::set
BitVector & set(unsigned Idx)
Definition: BitVector.h:386
llvm::BitVector::~BitVector
~BitVector()
Definition: BitVector.h:164
llvm::BitVector::find_last
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:318
llvm::BitVector::operator==
bool operator==(const BitVector &RHS) const
Definition: BitVector.h:516
llvm::const_set_bits_iterator_impl::operator!=
bool operator!=(const const_set_bits_iterator_impl &Other) const
Definition: BitVector.h:67
llvm::BitVector::all
bool all() const
all - Returns true if all bits are set.
Definition: BitVector.h:189
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::BitVector::operator^=
BitVector & operator^=(const BitVector &RHS)
Definition: BitVector.h:579
llvm::BitVector::find_first_unset
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:330
llvm::const_set_bits_iterator_impl::const_set_bits_iterator_impl
const_set_bits_iterator_impl(const BitVectorT &Parent)
Definition: BitVector.h:44
llvm::MutableArrayRef< BitWord >
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::BitVector::BitVector
BitVector()
BitVector default ctor - Creates an empty bitvector.
Definition: BitVector.h:135
llvm::BitVector::count
size_type count() const
count - Returns the number of bits which are set.
Definition: BitVector.h:173
llvm::BitVector::size
size_type size() const
size - Returns the number of bits in this bitvector.
Definition: BitVector.h:170
llvm::BitVector::swap
void swap(BitVector &RHS)
Definition: BitVector.h:733
llvm::BitVector::invalid
void invalid()
Definition: BitVector.h:738
t
bitcast float %x to i32 %s=and i32 %t, 2147483647 %d=bitcast i32 %s to float ret float %d } declare float @fabsf(float %n) define float @bar(float %x) nounwind { %d=call float @fabsf(float %x) ret float %d } This IR(from PR6194):target datalayout="e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple="x86_64-apple-darwin10.0.0" %0=type { double, double } %struct.float3=type { float, float, float } define void @test(%0, %struct.float3 *nocapture %res) nounwind noinline ssp { entry:%tmp18=extractvalue %0 %0, 0 t
Definition: README-SSE.txt:788
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
llvm::BitVector::find_prev
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:326
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::DenseMapInfo< BitVector >::getHashValue
static unsigned getHashValue(const BitVector &V)
Definition: BitVector.h:929
llvm::BitVector::operator<<=
BitVector & operator<<=(unsigned N)
Definition: BitVector.h:636
llvm::BitVector::size_type
unsigned size_type
Definition: BitVector.h:86
llvm::BitVector::clearBitsNotInMask
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:780
llvm::BitVector
Definition: BitVector.h:74
llvm::BitVector::operator!=
bool operator!=(const BitVector &RHS) const
Definition: BitVector.h:523
llvm::None
const NoneType None
Definition: None.h:23
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::BitVector::empty
bool empty() const
empty - Tests whether there are no bits in this bitvector.
Definition: BitVector.h:167
llvm::countPopulation
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:568
llvm::BitVector::reset
BitVector & reset(unsigned Idx)
Definition: BitVector.h:426
llvm::BitVector::any
bool any() const
any - Returns true if any bit is set.
Definition: BitVector.h:181
llvm::BitVector::reset
BitVector & reset(unsigned I, unsigned E)
reset - Efficiently reset a range of bits in [I, E)
Definition: BitVector.h:432
s
multiplies can be turned into SHL s
Definition: README.txt:370
llvm::BitVector::operator>>=
BitVector & operator>>=(unsigned N)
Definition: BitVector.h:587
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:58
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::countTrailingOnes
unsigned 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:526
llvm::const_set_bits_iterator_impl::operator++
const_set_bits_iterator_impl operator++(int)
Definition: BitVector.h:48
ArrayRef.h
llvm::BitVector::flip
BitVector & flip()
Definition: BitVector.h:460
llvm::const_set_bits_iterator_impl::operator++
const_set_bits_iterator_impl & operator++()
Definition: BitVector.h:54
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:944
memcpy
<%struct.s * > cast struct s *S to sbyte *< sbyte * > sbyte uint cast struct s *agg result to sbyte *< sbyte * > sbyte uint cast struct s *memtmp to sbyte *< sbyte * > sbyte uint ret void llc ends up issuing two memcpy or custom lower memcpy(of small size) to be ldmia/stmia. I think option 2 is better but the current register allocator cannot allocate a chunk of registers at a time. A feasible temporary solution is to use specific physical registers at the lowering time for small(<
llvm::BitVector::operator=
const BitVector & operator=(BitVector &&RHS)
Definition: BitVector.h:720
iterator_range.h
llvm::BitVector::find_last_in
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:244
llvm::irsymtab::storage::Word
support::ulittle32_t Word
Definition: IRSymtab.h:51
llvm::BitVector::getMemorySize
size_t getMemorySize() const
Return the size (in bytes) of the bit vector.
Definition: BitVector.h:914
llvm::ArrayRef< BitWord >
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:339
llvm::countTrailingZeros
unsigned countTrailingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the least significant bit to the most stopping at the first 1.
Definition: MathExtras.h:157
llvm::BitVector::clearBitsInMask
void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
clearBitsInMask - Clear any bits in this vector that are set in Mask.
Definition: BitVector.h:768
uint32_t
llvm::BitVector::reference::operator=
reference & operator=(reference t)
Definition: BitVector.h:103
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::capacity_in_bytes
size_t capacity_in_bytes(const BitVector &X)
Definition: BitVector.h:918
llvm::MutableArrayRef::data
T * data() const
Definition: ArrayRef.h:352
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::BitVector::reset
BitVector & reset(const BitVector &RHS)
reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
Definition: BitVector.h:545
llvm::BitVector::operator&=
BitVector & operator&=(const BitVector &RHS)
Intersection, union, disjoint union.
Definition: BitVector.h:528
llvm::BitVector::const_set_bits_iterator
const_set_bits_iterator_impl< BitVector > const_set_bits_iterator
Definition: BitVector.h:121
llvm::BitVector::find_prev_unset
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:344
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:484
std
Definition: BitVector.h:941
llvm::BitVector::BitVector
BitVector(unsigned s, bool t=false)
BitVector ctor - Creates a bitvector of specified number of bits.
Definition: BitVector.h:139
llvm::BitVector::setBitsInMask
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
setBitsInMask - Add '1' bits from Mask to this vector.
Definition: BitVector.h:762
llvm::MutableArrayRef::take_front
MutableArrayRef< T > take_front(size_t N=1) const
Return a copy of *this with only the first N elements.
Definition: ArrayRef.h:410
llvm::BitVector::reference::reference
reference()=delete
llvm::BitVector::set_bits_end
const_set_bits_iterator set_bits_end() const
Definition: BitVector.h:127
llvm::BitVector::set_iterator
const_set_bits_iterator set_iterator
Definition: BitVector.h:122
llvm::BitVector::find_last_unset
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:340
llvm::BitVector::find_next
int find_next(unsigned Prev) const
find_next - Returns the index of the next set bit following the "Prev" bit.
Definition: BitVector.h:322
llvm::countLeadingZeros
unsigned countLeadingZeros(T Val, ZeroBehavior ZB=ZB_Width)
Count number of 0's from the most significant bit to the least stopping at the first 1.
Definition: MathExtras.h:226
llvm::BitVector::operator=
const BitVector & operator=(const BitVector &RHS)
Definition: BitVector.h:687
llvm::safe_realloc
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_realloc(void *Ptr, size_t Sz)
Definition: MemAlloc.h:52
llvm::BitVector::reset
BitVector & reset()
Definition: BitVector.h:421
llvm::BitVector::flip
BitVector & flip(unsigned Idx)
Definition: BitVector.h:467
llvm::BitVector::getBitCapacity
size_t getBitCapacity() const
Definition: BitVector.h:915
llvm::BitVector::isInvalid
bool isInvalid() const
Definition: BitVector.h:742
llvm::DenseMapInfo< BitVector >::getTombstoneKey
static BitVector getTombstoneKey()
Definition: BitVector.h:924
llvm::BitVector::set
BitVector & set(unsigned I, unsigned E)
set - Efficiently set a range of bits in [I, E)
Definition: BitVector.h:393
N
#define N
llvm::BitVector::find_first
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:314
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
DenseMapInfo.h
llvm::BitVector::anyCommon
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:506
llvm::const_set_bits_iterator_impl::operator==
bool operator==(const const_set_bits_iterator_impl &Other) const
Definition: BitVector.h:61
LLVM_UNLIKELY
#define LLVM_UNLIKELY(EXPR)
Definition: Compiler.h:219
llvm::const_set_bits_iterator_impl
ForwardIterator for the bits that are set.
Definition: BitVector.h:32
llvm::safe_malloc
LLVM_ATTRIBUTE_RETURNS_NONNULL void * safe_malloc(size_t Sz)
Definition: MemAlloc.h:25
llvm::BitVector::BitVector
BitVector(BitVector &&RHS)
Definition: BitVector.h:159
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1131
llvm::BitVector::find_first_unset_in
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:275
llvm::const_set_bits_iterator_impl::operator*
unsigned operator*() const
Definition: BitVector.h:59