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  bool test(unsigned Idx) const {
448  return (*this)[Idx];
449  }
450 
451  // Push single bit to end of vector.
452  void push_back(bool Val) {
453  unsigned OldSize = Size;
454  unsigned NewSize = Size + 1;
455 
456  // Resize, which will insert zeros.
457  // If we already fit then the unused bits will be already zero.
458  if (NewSize > getBitCapacity())
459  resize(NewSize, false);
460  else
461  Size = NewSize;
462 
463  // If true, set single bit.
464  if (Val)
465  set(OldSize);
466  }
467 
468  /// Test if any common bits are set.
469  bool anyCommon(const BitVector &RHS) const {
470  unsigned ThisWords = Bits.size();
471  unsigned RHSWords = RHS.Bits.size();
472  for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
473  if (Bits[i] & RHS.Bits[i])
474  return true;
475  return false;
476  }
477 
478  // Comparison operators.
479  bool operator==(const BitVector &RHS) const {
480  if (size() != RHS.size())
481  return false;
482  unsigned NumWords = Bits.size();
483  return std::equal(Bits.begin(), Bits.begin() + NumWords, RHS.Bits.begin());
484  }
485 
486  bool operator!=(const BitVector &RHS) const { return !(*this == RHS); }
487 
488  /// Intersection, union, disjoint union.
490  unsigned ThisWords = Bits.size();
491  unsigned RHSWords = RHS.Bits.size();
492  unsigned i;
493  for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
494  Bits[i] &= RHS.Bits[i];
495 
496  // Any bits that are just in this bitvector become zero, because they aren't
497  // in the RHS bit vector. Any words only in RHS are ignored because they
498  // are already zero in the LHS.
499  for (; i != ThisWords; ++i)
500  Bits[i] = 0;
501 
502  return *this;
503  }
504 
505  /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
506  BitVector &reset(const BitVector &RHS) {
507  unsigned ThisWords = Bits.size();
508  unsigned RHSWords = RHS.Bits.size();
509  for (unsigned i = 0; i != std::min(ThisWords, RHSWords); ++i)
510  Bits[i] &= ~RHS.Bits[i];
511  return *this;
512  }
513 
514  /// test - Check if (This - RHS) is zero.
515  /// This is the same as reset(RHS) and any().
516  bool test(const BitVector &RHS) const {
517  unsigned ThisWords = Bits.size();
518  unsigned RHSWords = RHS.Bits.size();
519  unsigned i;
520  for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
521  if ((Bits[i] & ~RHS.Bits[i]) != 0)
522  return true;
523 
524  for (; i != ThisWords ; ++i)
525  if (Bits[i] != 0)
526  return true;
527 
528  return false;
529  }
530 
531  template <class F, class... ArgTys>
532  static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
533  ArgTys const &...Args) {
535  std::initializer_list<unsigned>{Args.size()...},
536  [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
537  "consistent sizes");
538  Out.resize(Arg.size());
539  for (size_type I = 0, E = Arg.Bits.size(); I != E; ++I)
540  Out.Bits[I] = f(Arg.Bits[I], Args.Bits[I]...);
541  Out.clear_unused_bits();
542  return Out;
543  }
544 
546  if (size() < RHS.size())
547  resize(RHS.size());
548  for (size_type I = 0, E = RHS.Bits.size(); I != E; ++I)
549  Bits[I] |= RHS.Bits[I];
550  return *this;
551  }
552 
554  if (size() < RHS.size())
555  resize(RHS.size());
556  for (size_type I = 0, E = RHS.Bits.size(); I != E; ++I)
557  Bits[I] ^= RHS.Bits[I];
558  return *this;
559  }
560 
561  BitVector &operator>>=(unsigned N) {
562  assert(N <= Size);
563  if (LLVM_UNLIKELY(empty() || N == 0))
564  return *this;
565 
566  unsigned NumWords = Bits.size();
567  assert(NumWords >= 1);
568 
569  wordShr(N / BITWORD_SIZE);
570 
571  unsigned BitDistance = N % BITWORD_SIZE;
572  if (BitDistance == 0)
573  return *this;
574 
575  // When the shift size is not a multiple of the word size, then we have
576  // a tricky situation where each word in succession needs to extract some
577  // of the bits from the next word and or them into this word while
578  // shifting this word to make room for the new bits. This has to be done
579  // for every word in the array.
580 
581  // Since we're shifting each word right, some bits will fall off the end
582  // of each word to the right, and empty space will be created on the left.
583  // The final word in the array will lose bits permanently, so starting at
584  // the beginning, work forwards shifting each word to the right, and
585  // OR'ing in the bits from the end of the next word to the beginning of
586  // the current word.
587 
588  // Example:
589  // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
590  // by 4 bits.
591  // Step 1: Word[0] >>= 4 ; 0x0ABBCCDD
592  // Step 2: Word[0] |= 0x10000000 ; 0x1ABBCCDD
593  // Step 3: Word[1] >>= 4 ; 0x0EEFF001
594  // Step 4: Word[1] |= 0x50000000 ; 0x5EEFF001
595  // Step 5: Word[2] >>= 4 ; 0x02334455
596  // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
597  const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
598  const unsigned LSH = BITWORD_SIZE - BitDistance;
599 
600  for (unsigned I = 0; I < NumWords - 1; ++I) {
601  Bits[I] >>= BitDistance;
602  Bits[I] |= (Bits[I + 1] & Mask) << LSH;
603  }
604 
605  Bits[NumWords - 1] >>= BitDistance;
606 
607  return *this;
608  }
609 
610  BitVector &operator<<=(unsigned N) {
611  assert(N <= Size);
612  if (LLVM_UNLIKELY(empty() || N == 0))
613  return *this;
614 
615  unsigned NumWords = Bits.size();
616  assert(NumWords >= 1);
617 
618  wordShl(N / BITWORD_SIZE);
619 
620  unsigned BitDistance = N % BITWORD_SIZE;
621  if (BitDistance == 0)
622  return *this;
623 
624  // When the shift size is not a multiple of the word size, then we have
625  // a tricky situation where each word in succession needs to extract some
626  // of the bits from the previous word and or them into this word while
627  // shifting this word to make room for the new bits. This has to be done
628  // for every word in the array. This is similar to the algorithm outlined
629  // in operator>>=, but backwards.
630 
631  // Since we're shifting each word left, some bits will fall off the end
632  // of each word to the left, and empty space will be created on the right.
633  // The first word in the array will lose bits permanently, so starting at
634  // the end, work backwards shifting each word to the left, and OR'ing
635  // in the bits from the end of the next word to the beginning of the
636  // current word.
637 
638  // Example:
639  // Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
640  // by 4 bits.
641  // Step 1: Word[2] <<= 4 ; 0x23344550
642  // Step 2: Word[2] |= 0x0000000E ; 0x2334455E
643  // Step 3: Word[1] <<= 4 ; 0xEFF00110
644  // Step 4: Word[1] |= 0x0000000A ; 0xEFF0011A
645  // Step 5: Word[0] <<= 4 ; 0xABBCCDD0
646  // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
647  const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
648  const unsigned RSH = BITWORD_SIZE - BitDistance;
649 
650  for (int I = NumWords - 1; I > 0; --I) {
651  Bits[I] <<= BitDistance;
652  Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
653  }
654  Bits[0] <<= BitDistance;
655  clear_unused_bits();
656 
657  return *this;
658  }
659 
660  void swap(BitVector &RHS) {
661  std::swap(Bits, RHS.Bits);
662  std::swap(Size, RHS.Size);
663  }
664 
665  void invalid() {
666  assert(!Size && Bits.empty());
667  Size = (unsigned)-1;
668  }
669  bool isInvalid() const { return Size == (unsigned)-1; }
670 
671  ArrayRef<BitWord> getData() const { return {&Bits[0], Bits.size()}; }
672 
673  //===--------------------------------------------------------------------===//
674  // Portable bit mask operations.
675  //===--------------------------------------------------------------------===//
676  //
677  // These methods all operate on arrays of uint32_t, each holding 32 bits. The
678  // fixed word size makes it easier to work with literal bit vector constants
679  // in portable code.
680  //
681  // The LSB in each word is the lowest numbered bit. The size of a portable
682  // bit mask is always a whole multiple of 32 bits. If no bit mask size is
683  // given, the bit mask is assumed to cover the entire BitVector.
684 
685  /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
686  /// This computes "*this |= Mask".
687  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
688  applyMask<true, false>(Mask, MaskWords);
689  }
690 
691  /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
692  /// Don't resize. This computes "*this &= ~Mask".
693  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
694  applyMask<false, false>(Mask, MaskWords);
695  }
696 
697  /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
698  /// Don't resize. This computes "*this |= ~Mask".
699  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
700  applyMask<true, true>(Mask, MaskWords);
701  }
702 
703  /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
704  /// Don't resize. This computes "*this &= Mask".
705  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
706  applyMask<false, true>(Mask, MaskWords);
707  }
708 
709 private:
710  /// Perform a logical left shift of \p Count words by moving everything
711  /// \p Count words to the right in memory.
712  ///
713  /// While confusing, words are stored from least significant at Bits[0] to
714  /// most significant at Bits[NumWords-1]. A logical shift left, however,
715  /// moves the current least significant bit to a higher logical index, and
716  /// fills the previous least significant bits with 0. Thus, we actually
717  /// need to move the bytes of the memory to the right, not to the left.
718  /// Example:
719  /// Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
720  /// represents a BitVector where 0xBBBBAAAA contain the least significant
721  /// bits. So if we want to shift the BitVector left by 2 words, we need
722  /// to turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
723  /// memmove which moves right, not left.
724  void wordShl(uint32_t Count) {
725  if (Count == 0)
726  return;
727 
728  uint32_t NumWords = Bits.size();
729 
730  // Since we always move Word-sized chunks of data with src and dest both
731  // aligned to a word-boundary, we don't need to worry about endianness
732  // here.
733  std::copy(Bits.begin(), Bits.begin() + NumWords - Count,
734  Bits.begin() + Count);
735  std::fill(Bits.begin(), Bits.begin() + Count, 0);
736  clear_unused_bits();
737  }
738 
739  /// Perform a logical right shift of \p Count words by moving those
740  /// words to the left in memory. See wordShl for more information.
741  ///
742  void wordShr(uint32_t Count) {
743  if (Count == 0)
744  return;
745 
746  uint32_t NumWords = Bits.size();
747 
748  std::copy(Bits.begin() + Count, Bits.begin() + NumWords, Bits.begin());
749  std::fill(Bits.begin() + NumWords - Count, Bits.begin() + NumWords, 0);
750  }
751 
752  int next_unset_in_word(int WordIndex, BitWord Word) const {
753  unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
754  return Result < size() ? Result : -1;
755  }
756 
757  unsigned NumBitWords(unsigned S) const {
758  return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
759  }
760 
761  // Set the unused bits in the high words.
762  void set_unused_bits(bool t = true) {
763  // Then set any stray high bits of the last used word.
764  if (unsigned ExtraBits = Size % BITWORD_SIZE) {
765  BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
766  if (t)
767  Bits.back() |= ExtraBitMask;
768  else
769  Bits.back() &= ~ExtraBitMask;
770  }
771  }
772 
773  // Clear the unused bits in the high words.
774  void clear_unused_bits() {
775  set_unused_bits(false);
776  }
777 
778  void init_words(bool t) {
779  std::fill(Bits.begin(), Bits.end(), 0 - (BitWord)t);
780  }
781 
782  template<bool AddBits, bool InvertMask>
783  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
784  static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
785  MaskWords = std::min(MaskWords, (size() + 31) / 32);
786  const unsigned Scale = BITWORD_SIZE / 32;
787  unsigned i;
788  for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
789  BitWord BW = Bits[i];
790  // This inner loop should unroll completely when BITWORD_SIZE > 32.
791  for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
792  uint32_t M = *Mask++;
793  if (InvertMask) M = ~M;
794  if (AddBits) BW |= BitWord(M) << b;
795  else BW &= ~(BitWord(M) << b);
796  }
797  Bits[i] = BW;
798  }
799  for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
800  uint32_t M = *Mask++;
801  if (InvertMask) M = ~M;
802  if (AddBits) Bits[i] |= BitWord(M) << b;
803  else Bits[i] &= ~(BitWord(M) << b);
804  }
805  if (AddBits)
806  clear_unused_bits();
807  }
808 
809 public:
810  /// Return the size (in bytes) of the bit vector.
811  size_type getMemorySize() const { return Bits.size() * sizeof(BitWord); }
812  size_type getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
813 };
814 
816  return X.getMemorySize();
817 }
818 
819 template <> struct DenseMapInfo<BitVector> {
820  static inline BitVector getEmptyKey() { return {}; }
821  static inline BitVector getTombstoneKey() {
822  BitVector V;
823  V.invalid();
824  return V;
825  }
826  static unsigned getHashValue(const BitVector &V) {
828  getHashValue(std::make_pair(V.size(), V.getData()));
829  }
830  static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
831  if (LHS.isInvalid() || RHS.isInvalid())
832  return LHS.isInvalid() == RHS.isInvalid();
833  return LHS == RHS;
834  }
835 };
836 } // end namespace llvm
837 
838 namespace std {
839  /// Implement std::swap in terms of BitVector swap.
840 inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); }
841 } // end namespace std
842 
843 #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::push_back
void push_back(bool Val)
Definition: BitVector.h:452
MathExtras.h
llvm
This file implements support for optimizing divisions by a constant.
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::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:699
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:671
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:545
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:815
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:830
llvm::DenseMapInfo< BitVector >::getEmptyKey
static BitVector getEmptyKey()
Definition: BitVector.h:820
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
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:516
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:56
llvm::lltok::equal
@ equal
Definition: LLToken.h:25
llvm::BitVector::operator==
bool operator==(const BitVector &RHS) const
Definition: BitVector.h:479
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:206
llvm::BitVector::all
bool all() const
all - Returns true if all bits are set.
Definition: BitVector.h:167
llvm::DenseMapInfo
Definition: APInt.h:34
llvm::BitVector::operator^=
BitVector & operator^=(const BitVector &RHS)
Definition: BitVector.h:553
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:1551
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:660
llvm::BitVector::invalid
void invalid()
Definition: BitVector.h:665
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:811
llvm::DenseMapInfo< BitVector >::getHashValue
static unsigned getHashValue(const BitVector &V)
Definition: BitVector.h:826
llvm::BitVector::operator<<=
BitVector & operator<<=(unsigned N)
Definition: BitVector.h:610
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:705
llvm::BitVector
Definition: BitVector.h:74
llvm::BitVector::operator!=
bool operator!=(const BitVector &RHS) const
Definition: BitVector.h:486
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:561
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
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: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:840
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:1558
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:693
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:506
llvm::BitVector::operator&=
BitVector & operator&=(const BitVector &RHS)
Intersection, union, disjoint union.
Definition: BitVector.h:489
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:447
std
Definition: BitVector.h:838
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:687
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:812
llvm::BitVector::flip
BitVector & flip(unsigned Idx)
Definition: BitVector.h:430
llvm::BitVector::isInvalid
bool isInvalid() const
Definition: BitVector.h:669
llvm::DenseMapInfo< BitVector >::getTombstoneKey
static BitVector getTombstoneKey()
Definition: BitVector.h:821
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:469
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:226
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:532
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:1184
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