LLVM  13.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 = unsigned;
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_t 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_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
124 
125  void setSmallSize(size_t Size) {
126  setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
127  }
128 
129  // Return the element bits.
130  uintptr_t getSmallBits() const {
131  return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
132  }
133 
134  void setSmallBits(uintptr_t NewBits) {
135  setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) |
136  (getSmallSize() << SmallNumDataBits));
137  }
138 
139 public:
140  /// Creates an empty bitvector.
141  SmallBitVector() = default;
142 
143  /// Creates a bitvector of specified number of bits. All bits are initialized
144  /// to the specified value.
145  explicit SmallBitVector(unsigned s, bool t = false) {
146  if (s <= SmallNumDataBits)
147  switchToSmall(t ? ~uintptr_t(0) : 0, s);
148  else
149  switchToLarge(new BitVector(s, t));
150  }
151 
152  /// SmallBitVector copy ctor.
154  if (RHS.isSmall())
155  X = RHS.X;
156  else
157  switchToLarge(new BitVector(*RHS.getPointer()));
158  }
159 
161  RHS.X = 1;
162  }
163 
165  if (!isSmall())
166  delete getPointer();
167  }
168 
171 
173  return const_set_bits_iterator(*this);
174  }
175 
177  return const_set_bits_iterator(*this, -1);
178  }
179 
182  }
183 
184  bool isSmall() const { return X & uintptr_t(1); }
185 
186  /// Tests whether there are no bits in this bitvector.
187  bool empty() const {
188  return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
189  }
190 
191  /// Returns the number of bits in this bitvector.
192  size_t size() const {
193  return isSmall() ? getSmallSize() : getPointer()->size();
194  }
195 
196  /// Returns the number of bits which are set.
197  size_type count() const {
198  if (isSmall()) {
199  uintptr_t Bits = getSmallBits();
200  return countPopulation(Bits);
201  }
202  return getPointer()->count();
203  }
204 
205  /// Returns true if any bit is set.
206  bool any() const {
207  if (isSmall())
208  return getSmallBits() != 0;
209  return getPointer()->any();
210  }
211 
212  /// Returns true if all bits are set.
213  bool all() const {
214  if (isSmall())
215  return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1;
216  return getPointer()->all();
217  }
218 
219  /// Returns true if none of the bits are set.
220  bool none() const {
221  if (isSmall())
222  return getSmallBits() == 0;
223  return getPointer()->none();
224  }
225 
226  /// Returns the index of the first set bit, -1 if none of the bits are set.
227  int find_first() const {
228  if (isSmall()) {
229  uintptr_t Bits = getSmallBits();
230  if (Bits == 0)
231  return -1;
232  return countTrailingZeros(Bits);
233  }
234  return getPointer()->find_first();
235  }
236 
237  int find_last() const {
238  if (isSmall()) {
239  uintptr_t Bits = getSmallBits();
240  if (Bits == 0)
241  return -1;
242  return NumBaseBits - countLeadingZeros(Bits) - 1;
243  }
244  return getPointer()->find_last();
245  }
246 
247  /// Returns the index of the first unset bit, -1 if all of the bits are set.
248  int find_first_unset() const {
249  if (isSmall()) {
250  if (count() == getSmallSize())
251  return -1;
252 
253  uintptr_t Bits = getSmallBits();
254  return countTrailingOnes(Bits);
255  }
256  return getPointer()->find_first_unset();
257  }
258 
259  int find_last_unset() const {
260  if (isSmall()) {
261  if (count() == getSmallSize())
262  return -1;
263 
264  uintptr_t Bits = getSmallBits();
265  // Set unused bits.
266  Bits |= ~uintptr_t(0) << getSmallSize();
267  return NumBaseBits - countLeadingOnes(Bits) - 1;
268  }
269  return getPointer()->find_last_unset();
270  }
271 
272  /// Returns the index of the next set bit following the "Prev" bit.
273  /// Returns -1 if the next set bit is not found.
274  int find_next(unsigned Prev) const {
275  if (isSmall()) {
276  uintptr_t Bits = getSmallBits();
277  // Mask off previous bits.
278  Bits &= ~uintptr_t(0) << (Prev + 1);
279  if (Bits == 0 || Prev + 1 >= getSmallSize())
280  return -1;
281  return countTrailingZeros(Bits);
282  }
283  return getPointer()->find_next(Prev);
284  }
285 
286  /// Returns the index of the next unset bit following the "Prev" bit.
287  /// Returns -1 if the next unset bit is not found.
288  int find_next_unset(unsigned Prev) const {
289  if (isSmall()) {
290  uintptr_t Bits = getSmallBits();
291  // Mask in previous bits.
292  Bits |= (uintptr_t(1) << (Prev + 1)) - 1;
293  // Mask in unused bits.
294  Bits |= ~uintptr_t(0) << getSmallSize();
295 
296  if (Bits == ~uintptr_t(0) || Prev + 1 >= getSmallSize())
297  return -1;
298  return countTrailingOnes(Bits);
299  }
300  return getPointer()->find_next_unset(Prev);
301  }
302 
303  /// find_prev - Returns the index of the first set bit that precedes the
304  /// the bit at \p PriorTo. Returns -1 if all previous bits are unset.
305  int find_prev(unsigned PriorTo) const {
306  if (isSmall()) {
307  if (PriorTo == 0)
308  return -1;
309 
310  --PriorTo;
311  uintptr_t Bits = getSmallBits();
312  Bits &= maskTrailingOnes<uintptr_t>(PriorTo + 1);
313  if (Bits == 0)
314  return -1;
315 
316  return NumBaseBits - countLeadingZeros(Bits) - 1;
317  }
318  return getPointer()->find_prev(PriorTo);
319  }
320 
321  /// Clear all bits.
322  void clear() {
323  if (!isSmall())
324  delete getPointer();
325  switchToSmall(0, 0);
326  }
327 
328  /// Grow or shrink the bitvector.
329  void resize(unsigned N, bool t = false) {
330  if (!isSmall()) {
331  getPointer()->resize(N, t);
332  } else if (SmallNumDataBits >= N) {
333  uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
334  setSmallSize(N);
335  setSmallBits(NewBits | getSmallBits());
336  } else {
337  BitVector *BV = new BitVector(N, t);
338  uintptr_t OldBits = getSmallBits();
339  for (size_t i = 0, e = getSmallSize(); i != e; ++i)
340  (*BV)[i] = (OldBits >> i) & 1;
341  switchToLarge(BV);
342  }
343  }
344 
345  void reserve(unsigned N) {
346  if (isSmall()) {
347  if (N > SmallNumDataBits) {
348  uintptr_t OldBits = getSmallRawBits();
349  size_t SmallSize = getSmallSize();
350  BitVector *BV = new BitVector(SmallSize);
351  for (size_t i = 0; i < SmallSize; ++i)
352  if ((OldBits >> i) & 1)
353  BV->set(i);
354  BV->reserve(N);
355  switchToLarge(BV);
356  }
357  } else {
358  getPointer()->reserve(N);
359  }
360  }
361 
362  // Set, reset, flip
364  if (isSmall())
365  setSmallBits(~uintptr_t(0));
366  else
367  getPointer()->set();
368  return *this;
369  }
370 
371  SmallBitVector &set(unsigned Idx) {
372  if (isSmall()) {
373  assert(Idx <= static_cast<unsigned>(
374  std::numeric_limits<uintptr_t>::digits) &&
375  "undefined behavior");
376  setSmallBits(getSmallBits() | (uintptr_t(1) << Idx));
377  }
378  else
379  getPointer()->set(Idx);
380  return *this;
381  }
382 
383  /// Efficiently set a range of bits in [I, E)
384  SmallBitVector &set(unsigned I, unsigned E) {
385  assert(I <= E && "Attempted to set backwards range!");
386  assert(E <= size() && "Attempted to set out-of-bounds range!");
387  if (I == E) return *this;
388  if (isSmall()) {
389  uintptr_t EMask = ((uintptr_t)1) << E;
390  uintptr_t IMask = ((uintptr_t)1) << I;
391  uintptr_t Mask = EMask - IMask;
392  setSmallBits(getSmallBits() | Mask);
393  } else
394  getPointer()->set(I, E);
395  return *this;
396  }
397 
399  if (isSmall())
400  setSmallBits(0);
401  else
402  getPointer()->reset();
403  return *this;
404  }
405 
406  SmallBitVector &reset(unsigned Idx) {
407  if (isSmall())
408  setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx));
409  else
410  getPointer()->reset(Idx);
411  return *this;
412  }
413 
414  /// Efficiently reset a range of bits in [I, E)
415  SmallBitVector &reset(unsigned I, unsigned E) {
416  assert(I <= E && "Attempted to reset backwards range!");
417  assert(E <= size() && "Attempted to reset out-of-bounds range!");
418  if (I == E) return *this;
419  if (isSmall()) {
420  uintptr_t EMask = ((uintptr_t)1) << E;
421  uintptr_t IMask = ((uintptr_t)1) << I;
422  uintptr_t Mask = EMask - IMask;
423  setSmallBits(getSmallBits() & ~Mask);
424  } else
425  getPointer()->reset(I, E);
426  return *this;
427  }
428 
430  if (isSmall())
431  setSmallBits(~getSmallBits());
432  else
433  getPointer()->flip();
434  return *this;
435  }
436 
437  SmallBitVector &flip(unsigned Idx) {
438  if (isSmall())
439  setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx));
440  else
441  getPointer()->flip(Idx);
442  return *this;
443  }
444 
445  // No argument flip.
447  return SmallBitVector(*this).flip();
448  }
449 
450  // Indexing.
451  reference operator[](unsigned Idx) {
452  assert(Idx < size() && "Out-of-bounds Bit access.");
453  return reference(*this, Idx);
454  }
455 
456  bool operator[](unsigned Idx) const {
457  assert(Idx < size() && "Out-of-bounds Bit access.");
458  if (isSmall())
459  return ((getSmallBits() >> Idx) & 1) != 0;
460  return getPointer()->operator[](Idx);
461  }
462 
463  bool test(unsigned Idx) const {
464  return (*this)[Idx];
465  }
466 
467  // Push single bit to end of vector.
468  void push_back(bool Val) {
469  resize(size() + 1, Val);
470  }
471 
472  /// Test if any common bits are set.
473  bool anyCommon(const SmallBitVector &RHS) const {
474  if (isSmall() && RHS.isSmall())
475  return (getSmallBits() & RHS.getSmallBits()) != 0;
476  if (!isSmall() && !RHS.isSmall())
477  return getPointer()->anyCommon(*RHS.getPointer());
478 
479  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
480  if (test(i) && RHS.test(i))
481  return true;
482  return false;
483  }
484 
485  // Comparison operators.
486  bool operator==(const SmallBitVector &RHS) const {
487  if (size() != RHS.size())
488  return false;
489  if (isSmall() && RHS.isSmall())
490  return getSmallBits() == RHS.getSmallBits();
491  else if (!isSmall() && !RHS.isSmall())
492  return *getPointer() == *RHS.getPointer();
493  else {
494  for (size_t i = 0, e = size(); i != e; ++i) {
495  if ((*this)[i] != RHS[i])
496  return false;
497  }
498  return true;
499  }
500  }
501 
502  bool operator!=(const SmallBitVector &RHS) const {
503  return !(*this == RHS);
504  }
505 
506  // Intersection, union, disjoint union.
507  // FIXME BitVector::operator&= does not resize the LHS but this does
509  resize(std::max(size(), RHS.size()));
510  if (isSmall() && RHS.isSmall())
511  setSmallBits(getSmallBits() & RHS.getSmallBits());
512  else if (!isSmall() && !RHS.isSmall())
513  getPointer()->operator&=(*RHS.getPointer());
514  else {
515  size_t i, e;
516  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
517  (*this)[i] = test(i) && RHS.test(i);
518  for (e = size(); i != e; ++i)
519  reset(i);
520  }
521  return *this;
522  }
523 
524  /// Reset bits that are set in RHS. Same as *this &= ~RHS.
526  if (isSmall() && RHS.isSmall())
527  setSmallBits(getSmallBits() & ~RHS.getSmallBits());
528  else if (!isSmall() && !RHS.isSmall())
529  getPointer()->reset(*RHS.getPointer());
530  else
531  for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
532  if (RHS.test(i))
533  reset(i);
534 
535  return *this;
536  }
537 
538  /// Check if (This - RHS) is zero. This is the same as reset(RHS) and any().
539  bool test(const SmallBitVector &RHS) const {
540  if (isSmall() && RHS.isSmall())
541  return (getSmallBits() & ~RHS.getSmallBits()) != 0;
542  if (!isSmall() && !RHS.isSmall())
543  return getPointer()->test(*RHS.getPointer());
544 
545  unsigned i, e;
546  for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
547  if (test(i) && !RHS.test(i))
548  return true;
549 
550  for (e = size(); i != e; ++i)
551  if (test(i))
552  return true;
553 
554  return false;
555  }
556 
558  resize(std::max(size(), RHS.size()));
559  if (isSmall() && RHS.isSmall())
560  setSmallBits(getSmallBits() | RHS.getSmallBits());
561  else if (!isSmall() && !RHS.isSmall())
562  getPointer()->operator|=(*RHS.getPointer());
563  else {
564  for (size_t i = 0, e = RHS.size(); i != e; ++i)
565  (*this)[i] = test(i) || RHS.test(i);
566  }
567  return *this;
568  }
569 
571  resize(std::max(size(), RHS.size()));
572  if (isSmall() && RHS.isSmall())
573  setSmallBits(getSmallBits() ^ RHS.getSmallBits());
574  else if (!isSmall() && !RHS.isSmall())
575  getPointer()->operator^=(*RHS.getPointer());
576  else {
577  for (size_t i = 0, e = RHS.size(); i != e; ++i)
578  (*this)[i] = test(i) != RHS.test(i);
579  }
580  return *this;
581  }
582 
584  if (isSmall())
585  setSmallBits(getSmallBits() << N);
586  else
587  getPointer()->operator<<=(N);
588  return *this;
589  }
590 
592  if (isSmall())
593  setSmallBits(getSmallBits() >> N);
594  else
595  getPointer()->operator>>=(N);
596  return *this;
597  }
598 
599  // Assignment operator.
601  if (isSmall()) {
602  if (RHS.isSmall())
603  X = RHS.X;
604  else
605  switchToLarge(new BitVector(*RHS.getPointer()));
606  } else {
607  if (!RHS.isSmall())
608  *getPointer() = *RHS.getPointer();
609  else {
610  delete getPointer();
611  X = RHS.X;
612  }
613  }
614  return *this;
615  }
616 
618  if (this != &RHS) {
619  clear();
620  swap(RHS);
621  }
622  return *this;
623  }
624 
625  void swap(SmallBitVector &RHS) {
626  std::swap(X, RHS.X);
627  }
628 
629  /// Add '1' bits from Mask to this vector. Don't resize.
630  /// This computes "*this |= Mask".
631  void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
632  if (isSmall())
633  applyMask<true, false>(Mask, MaskWords);
634  else
635  getPointer()->setBitsInMask(Mask, MaskWords);
636  }
637 
638  /// Clear any bits in this vector that are set in Mask. Don't resize.
639  /// This computes "*this &= ~Mask".
640  void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
641  if (isSmall())
642  applyMask<false, false>(Mask, MaskWords);
643  else
644  getPointer()->clearBitsInMask(Mask, MaskWords);
645  }
646 
647  /// Add a bit to this vector for every '0' bit in Mask. Don't resize.
648  /// This computes "*this |= ~Mask".
649  void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
650  if (isSmall())
651  applyMask<true, true>(Mask, MaskWords);
652  else
653  getPointer()->setBitsNotInMask(Mask, MaskWords);
654  }
655 
656  /// Clear a bit in this vector for every '0' bit in Mask. Don't resize.
657  /// This computes "*this &= Mask".
658  void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
659  if (isSmall())
660  applyMask<false, true>(Mask, MaskWords);
661  else
662  getPointer()->clearBitsNotInMask(Mask, MaskWords);
663  }
664 
665  void invalid() {
666  assert(empty());
667  X = (uintptr_t)-1;
668  }
669  bool isInvalid() const { return X == (uintptr_t)-1; }
670 
671  ArrayRef<uintptr_t> getData(uintptr_t &Store) const {
672  if (!isSmall())
673  return getPointer()->getData();
674  Store = getSmallBits();
675  return makeArrayRef(Store);
676  }
677 
678 private:
679  template <bool AddBits, bool InvertMask>
680  void applyMask(const uint32_t *Mask, unsigned MaskWords) {
681  assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!");
682  uintptr_t M = Mask[0];
683  if (NumBaseBits == 64)
684  M |= uint64_t(Mask[1]) << 32;
685  if (InvertMask)
686  M = ~M;
687  if (AddBits)
688  setSmallBits(getSmallBits() | M);
689  else
690  setSmallBits(getSmallBits() & ~M);
691  }
692 };
693 
694 inline SmallBitVector
695 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) {
696  SmallBitVector Result(LHS);
697  Result &= RHS;
698  return Result;
699 }
700 
701 inline SmallBitVector
702 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) {
703  SmallBitVector Result(LHS);
704  Result |= RHS;
705  return Result;
706 }
707 
708 inline SmallBitVector
709 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) {
710  SmallBitVector Result(LHS);
711  Result ^= RHS;
712  return Result;
713 }
714 
715 template <> struct DenseMapInfo<SmallBitVector> {
716  static inline SmallBitVector getEmptyKey() { return SmallBitVector(); }
717  static inline SmallBitVector getTombstoneKey() {
718  SmallBitVector V;
719  V.invalid();
720  return V;
721  }
722  static unsigned getHashValue(const SmallBitVector &V) {
723  uintptr_t Store;
725  std::make_pair(V.size(), V.getData(Store)));
726  }
727  static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) {
728  if (LHS.isInvalid() || RHS.isInvalid())
729  return LHS.isInvalid() == RHS.isInvalid();
730  return LHS == RHS;
731  }
732 };
733 } // end namespace llvm
734 
735 namespace std {
736 
737 /// Implement std::swap in terms of BitVector swap.
738 inline void
740  LHS.swap(RHS);
741 }
742 
743 } // end namespace std
744 
745 #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:371
llvm::SmallBitVector::set
SmallBitVector & set()
Definition: SmallBitVector.h:363
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:640
MathExtras.h
llvm
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:557
llvm::BitVector::getData
ArrayRef< BitWord > getData() const
Definition: BitVector.h:671
llvm::SmallBitVector::reset
SmallBitVector & reset()
Definition: SmallBitVector.h:398
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:722
llvm::DenseMapInfo< SmallBitVector >::getEmptyKey
static SmallBitVector getEmptyKey()
Definition: SmallBitVector.h:716
llvm::SmallBitVector::find_last
int find_last() const
Definition: SmallBitVector.h:237
llvm::SmallBitVector::SmallBitVector
SmallBitVector(const SmallBitVector &RHS)
SmallBitVector copy ctor.
Definition: SmallBitVector.h:153
llvm::SmallBitVector::reset
SmallBitVector & reset(unsigned I, unsigned E)
Efficiently reset a range of bits in [I, E)
Definition: SmallBitVector.h:415
llvm::SmallBitVector::setBitsInMask
void setBitsInMask(const uint32_t *Mask, unsigned MaskWords=~0u)
Add '1' bits from Mask to this vector.
Definition: SmallBitVector.h:631
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:227
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:437
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:463
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:220
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:717
llvm::SmallBitVector::flip
SmallBitVector & flip()
Definition: SmallBitVector.h:429
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:649
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:305
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:160
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:259
llvm::SmallBitVector::operator[]
reference operator[](unsigned Idx)
Definition: SmallBitVector.h:451
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:164
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:288
llvm::SmallBitVector::all
bool all() const
Returns true if all bits are set.
Definition: SmallBitVector.h:213
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:384
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:274
llvm::SmallBitVector::clear
void clear()
Clear all bits.
Definition: SmallBitVector.h:322
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:2069
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:248
llvm::SmallBitVector::operator==
bool operator==(const SmallBitVector &RHS) const
Definition: SmallBitVector.h:486
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:591
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SmallBitVector::push_back
void push_back(bool Val)
Definition: SmallBitVector.h:468
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::SmallBitVector::operator<<=
SmallBitVector & operator<<=(unsigned N)
Definition: SmallBitVector.h:583
llvm::SmallBitVector::isInvalid
bool isInvalid() const
Definition: SmallBitVector.h:669
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:406
iterator_range.h
llvm::SmallBitVector::resize
void resize(unsigned N, bool t=false)
Grow or shrink the bitvector.
Definition: SmallBitVector.h:329
llvm::DenseMapInfo< SmallBitVector >::isEqual
static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS)
Definition: SmallBitVector.h:727
llvm::SmallBitVector::empty
bool empty() const
Tests whether there are no bits in this bitvector.
Definition: SmallBitVector.h:187
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:658
llvm::SmallBitVector::invalid
void invalid()
Definition: SmallBitVector.h:665
uint32_t
llvm::SmallBitVector::reference::operator=
reference & operator=(reference t)
Definition: SmallBitVector.h:75
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::SmallBitVector::operator&=
SmallBitVector & operator&=(const SmallBitVector &RHS)
Definition: SmallBitVector.h:508
llvm::operator^
APInt operator^(APInt a, const APInt &b)
Definition: APInt.h:2089
llvm::SmallBitVector::reset
SmallBitVector & reset(const SmallBitVector &RHS)
Reset bits that are set in RHS. Same as *this &= ~RHS.
Definition: SmallBitVector.h:525
llvm::operator&
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:2049
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:197
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:502
llvm::SmallBitVector::swap
void swap(SmallBitVector &RHS)
Definition: SmallBitVector.h:625
llvm::SmallBitVector::isSmall
bool isSmall() const
Definition: SmallBitVector.h:184
llvm::SmallBitVector::operator~
SmallBitVector operator~() const
Definition: SmallBitVector.h:446
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:180
llvm::SmallBitVector::getData
ArrayRef< uintptr_t > getData(uintptr_t &Store) const
Definition: SmallBitVector.h:671
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:473
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::operator=
const SmallBitVector & operator=(SmallBitVector &&RHS)
Definition: SmallBitVector.h:617
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:169
llvm::SmallBitVector::operator=
const SmallBitVector & operator=(const SmallBitVector &RHS)
Definition: SmallBitVector.h:600
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:456
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:350
llvm::iterator_range
A range adaptor for a pair of iterators.
Definition: iterator_range.h:30
llvm::BitVector::anyCommon
bool anyCommon(const BitVector &RHS) const
Test if any common bits are set.
Definition: BitVector.h:469
llvm::SmallBitVector::size
size_t size() const
Returns the number of bits in this bitvector.
Definition: SmallBitVector.h:192
llvm::SmallBitVector::operator^=
SmallBitVector & operator^=(const SmallBitVector &RHS)
Definition: SmallBitVector.h:570
llvm::SmallBitVector::set_bits_begin
const_set_bits_iterator set_bits_begin() const
Definition: SmallBitVector.h:172
llvm::SmallBitVector::SmallBitVector
SmallBitVector(unsigned s, bool t=false)
Creates a bitvector of specified number of bits.
Definition: SmallBitVector.h:145
llvm::SmallBitVector::size_type
unsigned size_type
Definition: SmallBitVector.h:63
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:539
llvm::SmallBitVector::set_bits_end
const_set_bits_iterator set_bits_end() const
Definition: SmallBitVector.h:176
llvm::SmallBitVector::reserve
void reserve(unsigned N)
Definition: SmallBitVector.h:345
llvm::SmallBitVector::any
bool any() const
Returns true if any bit is set.
Definition: SmallBitVector.h:206