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