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