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