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