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  bool test(unsigned Idx) const {
466  return (*this)[Idx];
467  }
468 
469  // Push single bit to end of vector.
470  void push_back(bool Val) {
471  resize(size() + 1, Val);
472  }
473 
474  /// Test if any common bits are set.
475  bool anyCommon(const SmallBitVector &RHS) const {
476  if (isSmall() && RHS.isSmall())
477  return (getSmallBits() & RHS.getSmallBits()) != 0;
478  if (!isSmall() && !RHS.isSmall())
479  return getPointer()->anyCommon(*RHS.getPointer());
480 
481  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
482  if (test(i) && RHS.test(i))
483  return true;
484  return false;
485  }
486 
487  // Comparison operators.
488  bool operator==(const SmallBitVector &RHS) const {
489  if (size() != RHS.size())
490  return false;
491  if (isSmall() && RHS.isSmall())
492  return getSmallBits() == RHS.getSmallBits();
493  else if (!isSmall() && !RHS.isSmall())
494  return *getPointer() == *RHS.getPointer();
495  else {
496  for (size_type I = 0, E = size(); I != E; ++I) {
497  if ((*this)[I] != RHS[I])
498  return false;
499  }
500  return true;
501  }
502  }
503 
504  bool operator!=(const SmallBitVector &RHS) const {
505  return !(*this == RHS);
506  }
507 
508  // Intersection, union, disjoint union.
509  // FIXME BitVector::operator&= does not resize the LHS but this does
511  resize(std::max(size(), RHS.size()));
512  if (isSmall() && RHS.isSmall())
513  setSmallBits(getSmallBits() & RHS.getSmallBits());
514  else if (!isSmall() && !RHS.isSmall())
515  getPointer()->operator&=(*RHS.getPointer());
516  else {
517  size_type I, E;
518  for (I = 0, E = std::min(size(), RHS.size()); I != E; ++I)
519  (*this)[I] = test(I) && RHS.test(I);
520  for (E = size(); I != E; ++I)
521  reset(I);
522  }
523  return *this;
524  }
525 
526  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
528  if (isSmall() && RHS.isSmall())
529  setSmallBits(getSmallBits() & ~RHS.getSmallBits());
530  else if (!isSmall() && !RHS.isSmall())
531  getPointer()->reset(*RHS.getPointer());
532  else
533  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
534  if (RHS.test(i))
535  reset(i);
536 
537  return *this;
538  }
539 
540  /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
541  bool test(const SmallBitVector &RHS) const {
542  if (isSmall() && RHS.isSmall())
543  return (getSmallBits() & ~RHS.getSmallBits()) != 0;
544  if (!isSmall() && !RHS.isSmall())
545  return getPointer()->test(*RHS.getPointer());
546 
547  unsigned i, e;
548  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
549  if (test(i) && !RHS.test(i))
550  return true;
551 
552  for (e = size(); i != e; ++i)
553  if (test(i))
554  return true;
555 
556  return false;
557  }
558 
560  resize(std::max(size(), RHS.size()));
561  if (isSmall() && RHS.isSmall())
562  setSmallBits(getSmallBits() | RHS.getSmallBits());
563  else if (!isSmall() && !RHS.isSmall())
564  getPointer()->operator|=(*RHS.getPointer());
565  else {
566  for (size_type I = 0, E = RHS.size(); I != E; ++I)
567  (*this)[I] = test(I) || RHS.test(I);
568  }
569  return *this;
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  if (isSmall())
587  setSmallBits(getSmallBits() << N);
588  else
589  getPointer()->operator<<=(N);
590  return *this;
591  }
592 
594  if (isSmall())
595  setSmallBits(getSmallBits() >> N);
596  else
597  getPointer()->operator>>=(N);
598  return *this;
599  }
600 
601  // Assignment operator.
603  if (isSmall()) {
604  if (RHS.isSmall())
605  X = RHS.X;
606  else
607  switchToLarge(new BitVector(*RHS.getPointer()));
608  } else {
609  if (!RHS.isSmall())
610  *getPointer() = *RHS.getPointer();
611  else {
612  delete getPointer();
613  X = RHS.X;
614  }
615  }
616  return *this;
617  }
618 
620  if (this != &RHS) {
621  clear();
622  swap(RHS);
623  }
624  return *this;
625  }
626 
627  void swap(SmallBitVector &RHS) {
628  std::swap(X, RHS.X);
629  }
630 
631  /// Add '1' bits from Mask to this vector. Don't resize.
632  /// This computes "*this |= Mask".
633  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
634  if (isSmall())
635  applyMask<true, false>(Mask, MaskWords);
636  else
637  getPointer()->setBitsInMask(Mask, MaskWords);
638  }
639 
640  /// Clear any bits in this vector that are set in Mask. Don't resize.
641  /// This computes "*this &= ~Mask".
642  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
643  if (isSmall())
644  applyMask<false, false>(Mask, MaskWords);
645  else
646  getPointer()->clearBitsInMask(Mask, MaskWords);
647  }
648 
649  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
650  /// This computes "*this |= ~Mask".
651  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
652  if (isSmall())
653  applyMask<true, true>(Mask, MaskWords);
654  else
655  getPointer()->setBitsNotInMask(Mask, MaskWords);
656  }
657 
658  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
659  /// This computes "*this &= Mask".
660  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
661  if (isSmall())
662  applyMask<false, true>(Mask, MaskWords);
663  else
664  getPointer()->clearBitsNotInMask(Mask, MaskWords);
665  }
666 
667  void invalid() {
668  assert(empty());
669  X = (uintptr_t)-1;
670  }
671  bool isInvalid() const { return X == (uintptr_t)-1; }
672 
673  ArrayRef<uintptr_t> getData(uintptr_t &Store) const {
674  if (!isSmall())
675  return getPointer()->getData();
676  Store = getSmallBits();
677  return makeArrayRef(Store);
678  }
679 
680 private:
681  template <bool AddBits, bool InvertMask>
682  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
683  assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
684  uintptr_t M = Mask[0];
685  if (NumBaseBits == 64)
686  M |= uint64_t(Mask[1]) << 32;
687  if (InvertMask)
688  M = ~M;
689  if (AddBits)
690  setSmallBits(getSmallBits() | M);
691  else
692  setSmallBits(getSmallBits() & ~M);
693  }
694 };
695 
696 inline SmallBitVector
697 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
698  SmallBitVector Result(LHS);
699  Result &= RHS;
700  return Result;
701 }
702 
703 inline SmallBitVector
704 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
705  SmallBitVector Result(LHS);
706  Result |= RHS;
707  return Result;
708 }
709 
710 inline SmallBitVector
711 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
712  SmallBitVector Result(LHS);
713  Result ^= RHS;
714  return Result;
715 }
716 
717 template <> struct DenseMapInfo<SmallBitVector> {
718  static inline SmallBitVector getEmptyKey() { return SmallBitVector(); }
719  static inline SmallBitVector getTombstoneKey() {
720  SmallBitVector V;
721  V.invalid();
722  return V;
723  }
724  static unsigned getHashValue(const SmallBitVector &V) {
725  uintptr_t Store;
726  return DenseMapInfo<
727  std::pair<SmallBitVector::size_type, ArrayRef<uintptr_t>>>::
728  getHashValue(std::make_pair(V.size(), V.getData(Store)));
729  }
730  static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) {
731  if (LHS.isInvalid() || RHS.isInvalid())
732  return LHS.isInvalid() == RHS.isInvalid();
733  return LHS == RHS;
734  }
735 };
736 } // end namespace llvm
737 
738 namespace std {
739 
740 /// Implement std::swap in terms of BitVector swap.
741 inline void
743  LHS.swap(RHS);
744 }
745 
746 } // end namespace std
747 
748 #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:642
MathExtras.h
llvm
This file implements support for optimizing divisions by a constant.
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: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::SmallBitVector::operator|=
SmallBitVector & operator|=(const SmallBitVector &RHS)
Definition: SmallBitVector.h:559
llvm::BitVector::getData
ArrayRef< BitWord > getData() const
Definition: BitVector.h:671
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:724
llvm::DenseMapInfo< SmallBitVector >::getEmptyKey
static SmallBitVector getEmptyKey()
Definition: SmallBitVector.h:718
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:633
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::SmallBitVector::test
bool test(unsigned Idx) const
Definition: SmallBitVector.h:465
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:719
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:651
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
llvm::DenseMapInfo
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:705
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:2002
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:488
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:593
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SmallBitVector::push_back
void push_back(bool Val)
Definition: SmallBitVector.h:470
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::BitVector::flip
BitVector & flip()
Definition: BitVector.h:423
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::SmallBitVector::operator<<=
SmallBitVector & operator<<=(unsigned N)
Definition: SmallBitVector.h:585
llvm::SmallBitVector::isInvalid
bool isInvalid() const
Definition: SmallBitVector.h:671
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:840
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::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:730
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::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:693
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:660
llvm::SmallBitVector::invalid
void invalid()
Definition: SmallBitVector.h:667
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:510
llvm::operator^
APInt operator^(APInt a, const APInt &b)
Definition: APInt.h:2022
llvm::SmallBitVector::reset
SmallBitVector & reset(const SmallBitVector &RHS)
Reset bits that are set in RHS. Same as *this &= ~RHS.
Definition: SmallBitVector.h:527
llvm::operator&
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:1982
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:447
std
Definition: BitVector.h:838
llvm::SmallBitVector::operator!=
bool operator!=(const SmallBitVector &RHS) const
Definition: SmallBitVector.h:504
llvm::SmallBitVector::swap
void swap(SmallBitVector &RHS)
Definition: SmallBitVector.h:627
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:687
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:673
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:475
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:476
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:619
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:602
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:469
llvm::SmallBitVector::operator^=
SmallBitVector & operator^=(const SmallBitVector &RHS)
Definition: SmallBitVector.h:572
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:541
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