LLVM  14.0.0git
SparseBitVector.h
Go to the documentation of this file.
1 //===- llvm/ADT/SparseBitVector.h - Efficient Sparse BitVector --*- 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 defines the SparseBitVector class. See the doxygen comment for
10 // SparseBitVector for more details on the algorithm used.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ADT_SPARSEBITVECTOR_H
15 #define LLVM_ADT_SPARSEBITVECTOR_H
16 
20 #include <cassert>
21 #include <climits>
22 #include <cstring>
23 #include <iterator>
24 #include <list>
25 
26 namespace llvm {
27 
28 /// SparseBitVector is an implementation of a bitvector that is sparse by only
29 /// storing the elements that have non-zero bits set. In order to make this
30 /// fast for the most common cases, SparseBitVector is implemented as a linked
31 /// list of SparseBitVectorElements. We maintain a pointer to the last
32 /// SparseBitVectorElement accessed (in the form of a list iterator), in order
33 /// to make multiple in-order test/set constant time after the first one is
34 /// executed. Note that using vectors to store SparseBitVectorElement's does
35 /// not work out very well because it causes insertion in the middle to take
36 /// enormous amounts of time with a large amount of bits. Other structures that
37 /// have better worst cases for insertion in the middle (various balanced trees,
38 /// etc) do not perform as well in practice as a linked list with this iterator
39 /// kept up to date. They are also significantly more memory intensive.
40 
41 template <unsigned ElementSize = 128> struct SparseBitVectorElement {
42 public:
43  using BitWord = unsigned long;
44  using size_type = unsigned;
45  enum {
46  BITWORD_SIZE = sizeof(BitWord) * CHAR_BIT,
48  BITS_PER_ELEMENT = ElementSize
49  };
50 
51 private:
52  // Index of Element in terms of where first bit starts.
53  unsigned ElementIndex;
55 
57  ElementIndex = ~0U;
58  memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
59  }
60 
61 public:
62  explicit SparseBitVectorElement(unsigned Idx) {
63  ElementIndex = Idx;
64  memset(&Bits[0], 0, sizeof (BitWord) * BITWORDS_PER_ELEMENT);
65  }
66 
67  // Comparison.
68  bool operator==(const SparseBitVectorElement &RHS) const {
69  if (ElementIndex != RHS.ElementIndex)
70  return false;
71  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
72  if (Bits[i] != RHS.Bits[i])
73  return false;
74  return true;
75  }
76 
77  bool operator!=(const SparseBitVectorElement &RHS) const {
78  return !(*this == RHS);
79  }
80 
81  // Return the bits that make up word Idx in our element.
82  BitWord word(unsigned Idx) const {
84  return Bits[Idx];
85  }
86 
87  unsigned index() const {
88  return ElementIndex;
89  }
90 
91  bool empty() const {
92  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
93  if (Bits[i])
94  return false;
95  return true;
96  }
97 
98  void set(unsigned Idx) {
99  Bits[Idx / BITWORD_SIZE] |= 1L << (Idx % BITWORD_SIZE);
100  }
101 
102  bool test_and_set(unsigned Idx) {
103  bool old = test(Idx);
104  if (!old) {
105  set(Idx);
106  return true;
107  }
108  return false;
109  }
110 
111  void reset(unsigned Idx) {
112  Bits[Idx / BITWORD_SIZE] &= ~(1L << (Idx % BITWORD_SIZE));
113  }
114 
115  bool test(unsigned Idx) const {
116  return Bits[Idx / BITWORD_SIZE] & (1L << (Idx % BITWORD_SIZE));
117  }
118 
119  size_type count() const {
120  unsigned NumBits = 0;
121  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
122  NumBits += countPopulation(Bits[i]);
123  return NumBits;
124  }
125 
126  /// find_first - Returns the index of the first set bit.
127  int find_first() const {
128  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i)
129  if (Bits[i] != 0)
130  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
131  llvm_unreachable("Illegal empty element");
132  }
133 
134  /// find_last - Returns the index of the last set bit.
135  int find_last() const {
136  for (unsigned I = 0; I < BITWORDS_PER_ELEMENT; ++I) {
137  unsigned Idx = BITWORDS_PER_ELEMENT - I - 1;
138  if (Bits[Idx] != 0)
139  return Idx * BITWORD_SIZE + BITWORD_SIZE -
140  countLeadingZeros(Bits[Idx]) - 1;
141  }
142  llvm_unreachable("Illegal empty element");
143  }
144 
145  /// find_next - Returns the index of the next set bit starting from the
146  /// "Curr" bit. Returns -1 if the next set bit is not found.
147  int find_next(unsigned Curr) const {
148  if (Curr >= BITS_PER_ELEMENT)
149  return -1;
150 
151  unsigned WordPos = Curr / BITWORD_SIZE;
152  unsigned BitPos = Curr % BITWORD_SIZE;
153  BitWord Copy = Bits[WordPos];
154  assert(WordPos <= BITWORDS_PER_ELEMENT
155  && "Word Position outside of element");
156 
157  // Mask off previous bits.
158  Copy &= ~0UL << BitPos;
159 
160  if (Copy != 0)
161  return WordPos * BITWORD_SIZE + countTrailingZeros(Copy);
162 
163  // Check subsequent words.
164  for (unsigned i = WordPos+1; i < BITWORDS_PER_ELEMENT; ++i)
165  if (Bits[i] != 0)
166  return i * BITWORD_SIZE + countTrailingZeros(Bits[i]);
167  return -1;
168  }
169 
170  // Union this element with RHS and return true if this one changed.
172  bool changed = false;
173  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
174  BitWord old = changed ? 0 : Bits[i];
175 
176  Bits[i] |= RHS.Bits[i];
177  if (!changed && old != Bits[i])
178  changed = true;
179  }
180  return changed;
181  }
182 
183  // Return true if we have any bits in common with RHS
184  bool intersects(const SparseBitVectorElement &RHS) const {
185  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
186  if (RHS.Bits[i] & Bits[i])
187  return true;
188  }
189  return false;
190  }
191 
192  // Intersect this Element with RHS and return true if this one changed.
193  // BecameZero is set to true if this element became all-zero bits.
195  bool &BecameZero) {
196  bool changed = false;
197  bool allzero = true;
198 
199  BecameZero = false;
200  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
201  BitWord old = changed ? 0 : Bits[i];
202 
203  Bits[i] &= RHS.Bits[i];
204  if (Bits[i] != 0)
205  allzero = false;
206 
207  if (!changed && old != Bits[i])
208  changed = true;
209  }
210  BecameZero = allzero;
211  return changed;
212  }
213 
214  // Intersect this Element with the complement of RHS and return true if this
215  // one changed. BecameZero is set to true if this element became all-zero
216  // bits.
218  bool &BecameZero) {
219  bool changed = false;
220  bool allzero = true;
221 
222  BecameZero = false;
223  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
224  BitWord old = changed ? 0 : Bits[i];
225 
226  Bits[i] &= ~RHS.Bits[i];
227  if (Bits[i] != 0)
228  allzero = false;
229 
230  if (!changed && old != Bits[i])
231  changed = true;
232  }
233  BecameZero = allzero;
234  return changed;
235  }
236 
237  // Three argument version of intersectWithComplement that intersects
238  // RHS1 & ~RHS2 into this element
240  const SparseBitVectorElement &RHS2,
241  bool &BecameZero) {
242  bool allzero = true;
243 
244  BecameZero = false;
245  for (unsigned i = 0; i < BITWORDS_PER_ELEMENT; ++i) {
246  Bits[i] = RHS1.Bits[i] & ~RHS2.Bits[i];
247  if (Bits[i] != 0)
248  allzero = false;
249  }
250  BecameZero = allzero;
251  }
252 };
253 
254 template <unsigned ElementSize = 128>
256  using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
257  using ElementListIter = typename ElementList::iterator;
258  using ElementListConstIter = typename ElementList::const_iterator;
259  enum {
261  };
262 
263  ElementList Elements;
264  // Pointer to our current Element. This has no visible effect on the external
265  // state of a SparseBitVector, it's just used to improve performance in the
266  // common case of testing/modifying bits with similar indices.
267  mutable ElementListIter CurrElementIter;
268 
269  // This is like std::lower_bound, except we do linear searching from the
270  // current position.
271  ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
272 
273  // We cache a non-const iterator so we're forced to resort to const_cast to
274  // get the begin/end in the case where 'this' is const. To avoid duplication
275  // of code with the only difference being whether the const cast is present
276  // 'this' is always const in this particular function and we sort out the
277  // difference in FindLowerBound and FindLowerBoundConst.
278  ElementListIter Begin =
279  const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
280  ElementListIter End =
281  const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
282 
283  if (Elements.empty()) {
284  CurrElementIter = Begin;
285  return CurrElementIter;
286  }
287 
288  // Make sure our current iterator is valid.
289  if (CurrElementIter == End)
290  --CurrElementIter;
291 
292  // Search from our current iterator, either backwards or forwards,
293  // depending on what element we are looking for.
294  ElementListIter ElementIter = CurrElementIter;
295  if (CurrElementIter->index() == ElementIndex) {
296  return ElementIter;
297  } else if (CurrElementIter->index() > ElementIndex) {
298  while (ElementIter != Begin
299  && ElementIter->index() > ElementIndex)
300  --ElementIter;
301  } else {
302  while (ElementIter != End &&
303  ElementIter->index() < ElementIndex)
304  ++ElementIter;
305  }
306  CurrElementIter = ElementIter;
307  return ElementIter;
308  }
309  ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
310  return FindLowerBoundImpl(ElementIndex);
311  }
312  ElementListIter FindLowerBound(unsigned ElementIndex) {
313  return FindLowerBoundImpl(ElementIndex);
314  }
315 
316  // Iterator to walk set bits in the bitmap. This iterator is a lot uglier
317  // than it would be, in order to be efficient.
318  class SparseBitVectorIterator {
319  private:
320  bool AtEnd;
321 
322  const SparseBitVector<ElementSize> *BitVector = nullptr;
323 
324  // Current element inside of bitmap.
325  ElementListConstIter Iter;
326 
327  // Current bit number inside of our bitmap.
328  unsigned BitNumber;
329 
330  // Current word number inside of our element.
331  unsigned WordNumber;
332 
333  // Current bits from the element.
335 
336  // Move our iterator to the first non-zero bit in the bitmap.
337  void AdvanceToFirstNonZero() {
338  if (AtEnd)
339  return;
340  if (BitVector->Elements.empty()) {
341  AtEnd = true;
342  return;
343  }
344  Iter = BitVector->Elements.begin();
345  BitNumber = Iter->index() * ElementSize;
346  unsigned BitPos = Iter->find_first();
347  BitNumber += BitPos;
348  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
349  Bits = Iter->word(WordNumber);
350  Bits >>= BitPos % BITWORD_SIZE;
351  }
352 
353  // Move our iterator to the next non-zero bit.
354  void AdvanceToNextNonZero() {
355  if (AtEnd)
356  return;
357 
358  while (Bits && !(Bits & 1)) {
359  Bits >>= 1;
360  BitNumber += 1;
361  }
362 
363  // See if we ran out of Bits in this word.
364  if (!Bits) {
365  int NextSetBitNumber = Iter->find_next(BitNumber % ElementSize) ;
366  // If we ran out of set bits in this element, move to next element.
367  if (NextSetBitNumber == -1 || (BitNumber % ElementSize == 0)) {
368  ++Iter;
369  WordNumber = 0;
370 
371  // We may run out of elements in the bitmap.
372  if (Iter == BitVector->Elements.end()) {
373  AtEnd = true;
374  return;
375  }
376  // Set up for next non-zero word in bitmap.
377  BitNumber = Iter->index() * ElementSize;
378  NextSetBitNumber = Iter->find_first();
379  BitNumber += NextSetBitNumber;
380  WordNumber = (BitNumber % ElementSize) / BITWORD_SIZE;
381  Bits = Iter->word(WordNumber);
382  Bits >>= NextSetBitNumber % BITWORD_SIZE;
383  } else {
384  WordNumber = (NextSetBitNumber % ElementSize) / BITWORD_SIZE;
385  Bits = Iter->word(WordNumber);
386  Bits >>= NextSetBitNumber % BITWORD_SIZE;
387  BitNumber = Iter->index() * ElementSize;
388  BitNumber += NextSetBitNumber;
389  }
390  }
391  }
392 
393  public:
394  SparseBitVectorIterator() = default;
395 
396  SparseBitVectorIterator(const SparseBitVector<ElementSize> *RHS,
397  bool end = false):BitVector(RHS) {
398  Iter = BitVector->Elements.begin();
399  BitNumber = 0;
400  Bits = 0;
401  WordNumber = ~0;
402  AtEnd = end;
403  AdvanceToFirstNonZero();
404  }
405 
406  // Preincrement.
407  inline SparseBitVectorIterator& operator++() {
408  ++BitNumber;
409  Bits >>= 1;
410  AdvanceToNextNonZero();
411  return *this;
412  }
413 
414  // Postincrement.
415  inline SparseBitVectorIterator operator++(int) {
416  SparseBitVectorIterator tmp = *this;
417  ++*this;
418  return tmp;
419  }
420 
421  // Return the current set bit number.
422  unsigned operator*() const {
423  return BitNumber;
424  }
425 
426  bool operator==(const SparseBitVectorIterator &RHS) const {
427  // If they are both at the end, ignore the rest of the fields.
428  if (AtEnd && RHS.AtEnd)
429  return true;
430  // Otherwise they are the same if they have the same bit number and
431  // bitmap.
432  return AtEnd == RHS.AtEnd && RHS.BitNumber == BitNumber;
433  }
434 
435  bool operator!=(const SparseBitVectorIterator &RHS) const {
436  return !(*this == RHS);
437  }
438  };
439 
440 public:
441  using iterator = SparseBitVectorIterator;
442 
443  SparseBitVector() : Elements(), CurrElementIter(Elements.begin()) {}
444 
446  : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
448  : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
449 
450  // Clear.
451  void clear() {
452  Elements.clear();
453  }
454 
455  // Assignment
457  if (this == &RHS)
458  return *this;
459 
460  Elements = RHS.Elements;
461  CurrElementIter = Elements.begin();
462  return *this;
463  }
465  Elements = std::move(RHS.Elements);
466  CurrElementIter = Elements.begin();
467  return *this;
468  }
469 
470  // Test, Reset, and Set a bit in the bitmap.
471  bool test(unsigned Idx) const {
472  if (Elements.empty())
473  return false;
474 
475  unsigned ElementIndex = Idx / ElementSize;
476  ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
477 
478  // If we can't find an element that is supposed to contain this bit, there
479  // is nothing more to do.
480  if (ElementIter == Elements.end() ||
481  ElementIter->index() != ElementIndex)
482  return false;
483  return ElementIter->test(Idx % ElementSize);
484  }
485 
486  void reset(unsigned Idx) {
487  if (Elements.empty())
488  return;
489 
490  unsigned ElementIndex = Idx / ElementSize;
491  ElementListIter ElementIter = FindLowerBound(ElementIndex);
492 
493  // If we can't find an element that is supposed to contain this bit, there
494  // is nothing more to do.
495  if (ElementIter == Elements.end() ||
496  ElementIter->index() != ElementIndex)
497  return;
498  ElementIter->reset(Idx % ElementSize);
499 
500  // When the element is zeroed out, delete it.
501  if (ElementIter->empty()) {
502  ++CurrElementIter;
503  Elements.erase(ElementIter);
504  }
505  }
506 
507  void set(unsigned Idx) {
508  unsigned ElementIndex = Idx / ElementSize;
509  ElementListIter ElementIter;
510  if (Elements.empty()) {
511  ElementIter = Elements.emplace(Elements.end(), ElementIndex);
512  } else {
513  ElementIter = FindLowerBound(ElementIndex);
514 
515  if (ElementIter == Elements.end() ||
516  ElementIter->index() != ElementIndex) {
517  // We may have hit the beginning of our SparseBitVector, in which case,
518  // we may need to insert right after this element, which requires moving
519  // the current iterator forward one, because insert does insert before.
520  if (ElementIter != Elements.end() &&
521  ElementIter->index() < ElementIndex)
522  ++ElementIter;
523  ElementIter = Elements.emplace(ElementIter, ElementIndex);
524  }
525  }
526  CurrElementIter = ElementIter;
527 
528  ElementIter->set(Idx % ElementSize);
529  }
530 
531  bool test_and_set(unsigned Idx) {
532  bool old = test(Idx);
533  if (!old) {
534  set(Idx);
535  return true;
536  }
537  return false;
538  }
539 
540  bool operator!=(const SparseBitVector &RHS) const {
541  return !(*this == RHS);
542  }
543 
544  bool operator==(const SparseBitVector &RHS) const {
545  ElementListConstIter Iter1 = Elements.begin();
546  ElementListConstIter Iter2 = RHS.Elements.begin();
547 
548  for (; Iter1 != Elements.end() && Iter2 != RHS.Elements.end();
549  ++Iter1, ++Iter2) {
550  if (*Iter1 != *Iter2)
551  return false;
552  }
553  return Iter1 == Elements.end() && Iter2 == RHS.Elements.end();
554  }
555 
556  // Union our bitmap with the RHS and return true if we changed.
557  bool operator|=(const SparseBitVector &RHS) {
558  if (this == &RHS)
559  return false;
560 
561  bool changed = false;
562  ElementListIter Iter1 = Elements.begin();
563  ElementListConstIter Iter2 = RHS.Elements.begin();
564 
565  // If RHS is empty, we are done
566  if (RHS.Elements.empty())
567  return false;
568 
569  while (Iter2 != RHS.Elements.end()) {
570  if (Iter1 == Elements.end() || Iter1->index() > Iter2->index()) {
571  Elements.insert(Iter1, *Iter2);
572  ++Iter2;
573  changed = true;
574  } else if (Iter1->index() == Iter2->index()) {
575  changed |= Iter1->unionWith(*Iter2);
576  ++Iter1;
577  ++Iter2;
578  } else {
579  ++Iter1;
580  }
581  }
582  CurrElementIter = Elements.begin();
583  return changed;
584  }
585 
586  // Intersect our bitmap with the RHS and return true if ours changed.
587  bool operator&=(const SparseBitVector &RHS) {
588  if (this == &RHS)
589  return false;
590 
591  bool changed = false;
592  ElementListIter Iter1 = Elements.begin();
593  ElementListConstIter Iter2 = RHS.Elements.begin();
594 
595  // Check if both bitmaps are empty.
596  if (Elements.empty() && RHS.Elements.empty())
597  return false;
598 
599  // Loop through, intersecting as we go, erasing elements when necessary.
600  while (Iter2 != RHS.Elements.end()) {
601  if (Iter1 == Elements.end()) {
602  CurrElementIter = Elements.begin();
603  return changed;
604  }
605 
606  if (Iter1->index() > Iter2->index()) {
607  ++Iter2;
608  } else if (Iter1->index() == Iter2->index()) {
609  bool BecameZero;
610  changed |= Iter1->intersectWith(*Iter2, BecameZero);
611  if (BecameZero) {
612  ElementListIter IterTmp = Iter1;
613  ++Iter1;
614  Elements.erase(IterTmp);
615  } else {
616  ++Iter1;
617  }
618  ++Iter2;
619  } else {
620  ElementListIter IterTmp = Iter1;
621  ++Iter1;
622  Elements.erase(IterTmp);
623  changed = true;
624  }
625  }
626  if (Iter1 != Elements.end()) {
627  Elements.erase(Iter1, Elements.end());
628  changed = true;
629  }
630  CurrElementIter = Elements.begin();
631  return changed;
632  }
633 
634  // Intersect our bitmap with the complement of the RHS and return true
635  // if ours changed.
637  if (this == &RHS) {
638  if (!empty()) {
639  clear();
640  return true;
641  }
642  return false;
643  }
644 
645  bool changed = false;
646  ElementListIter Iter1 = Elements.begin();
647  ElementListConstIter Iter2 = RHS.Elements.begin();
648 
649  // If either our bitmap or RHS is empty, we are done
650  if (Elements.empty() || RHS.Elements.empty())
651  return false;
652 
653  // Loop through, intersecting as we go, erasing elements when necessary.
654  while (Iter2 != RHS.Elements.end()) {
655  if (Iter1 == Elements.end()) {
656  CurrElementIter = Elements.begin();
657  return changed;
658  }
659 
660  if (Iter1->index() > Iter2->index()) {
661  ++Iter2;
662  } else if (Iter1->index() == Iter2->index()) {
663  bool BecameZero;
664  changed |= Iter1->intersectWithComplement(*Iter2, BecameZero);
665  if (BecameZero) {
666  ElementListIter IterTmp = Iter1;
667  ++Iter1;
668  Elements.erase(IterTmp);
669  } else {
670  ++Iter1;
671  }
672  ++Iter2;
673  } else {
674  ++Iter1;
675  }
676  }
677  CurrElementIter = Elements.begin();
678  return changed;
679  }
680 
682  return intersectWithComplement(*RHS);
683  }
684 
685  // Three argument version of intersectWithComplement.
686  // Result of RHS1 & ~RHS2 is stored into this bitmap.
688  const SparseBitVector<ElementSize> &RHS2)
689  {
690  if (this == &RHS1) {
692  return;
693  } else if (this == &RHS2) {
694  SparseBitVector RHS2Copy(RHS2);
695  intersectWithComplement(RHS1, RHS2Copy);
696  return;
697  }
698 
699  Elements.clear();
700  CurrElementIter = Elements.begin();
701  ElementListConstIter Iter1 = RHS1.Elements.begin();
702  ElementListConstIter Iter2 = RHS2.Elements.begin();
703 
704  // If RHS1 is empty, we are done
705  // If RHS2 is empty, we still have to copy RHS1
706  if (RHS1.Elements.empty())
707  return;
708 
709  // Loop through, intersecting as we go, erasing elements when necessary.
710  while (Iter2 != RHS2.Elements.end()) {
711  if (Iter1 == RHS1.Elements.end())
712  return;
713 
714  if (Iter1->index() > Iter2->index()) {
715  ++Iter2;
716  } else if (Iter1->index() == Iter2->index()) {
717  bool BecameZero = false;
718  Elements.emplace_back(Iter1->index());
719  Elements.back().intersectWithComplement(*Iter1, *Iter2, BecameZero);
720  if (BecameZero)
721  Elements.pop_back();
722  ++Iter1;
723  ++Iter2;
724  } else {
725  Elements.push_back(*Iter1++);
726  }
727  }
728 
729  // copy the remaining elements
730  std::copy(Iter1, RHS1.Elements.end(), std::back_inserter(Elements));
731  }
732 
734  const SparseBitVector<ElementSize> *RHS2) {
735  intersectWithComplement(*RHS1, *RHS2);
736  }
737 
738  bool intersects(const SparseBitVector<ElementSize> *RHS) const {
739  return intersects(*RHS);
740  }
741 
742  // Return true if we share any bits in common with RHS
743  bool intersects(const SparseBitVector<ElementSize> &RHS) const {
744  ElementListConstIter Iter1 = Elements.begin();
745  ElementListConstIter Iter2 = RHS.Elements.begin();
746 
747  // Check if both bitmaps are empty.
748  if (Elements.empty() && RHS.Elements.empty())
749  return false;
750 
751  // Loop through, intersecting stopping when we hit bits in common.
752  while (Iter2 != RHS.Elements.end()) {
753  if (Iter1 == Elements.end())
754  return false;
755 
756  if (Iter1->index() > Iter2->index()) {
757  ++Iter2;
758  } else if (Iter1->index() == Iter2->index()) {
759  if (Iter1->intersects(*Iter2))
760  return true;
761  ++Iter1;
762  ++Iter2;
763  } else {
764  ++Iter1;
765  }
766  }
767  return false;
768  }
769 
770  // Return true iff all bits set in this SparseBitVector are
771  // also set in RHS.
772  bool contains(const SparseBitVector<ElementSize> &RHS) const {
773  SparseBitVector<ElementSize> Result(*this);
774  Result &= RHS;
775  return (Result == RHS);
776  }
777 
778  // Return the first set bit in the bitmap. Return -1 if no bits are set.
779  int find_first() const {
780  if (Elements.empty())
781  return -1;
782  const SparseBitVectorElement<ElementSize> &First = *(Elements.begin());
783  return (First.index() * ElementSize) + First.find_first();
784  }
785 
786  // Return the last set bit in the bitmap. Return -1 if no bits are set.
787  int find_last() const {
788  if (Elements.empty())
789  return -1;
790  const SparseBitVectorElement<ElementSize> &Last = *(Elements.rbegin());
791  return (Last.index() * ElementSize) + Last.find_last();
792  }
793 
794  // Return true if the SparseBitVector is empty
795  bool empty() const {
796  return Elements.empty();
797  }
798 
799  unsigned count() const {
800  unsigned BitCount = 0;
801  for (ElementListConstIter Iter = Elements.begin();
802  Iter != Elements.end();
803  ++Iter)
804  BitCount += Iter->count();
805 
806  return BitCount;
807  }
808 
809  iterator begin() const {
810  return iterator(this);
811  }
812 
813  iterator end() const {
814  return iterator(this, true);
815  }
816 };
817 
818 // Convenience functions to allow Or and And without dereferencing in the user
819 // code.
820 
821 template <unsigned ElementSize>
823  const SparseBitVector<ElementSize> *RHS) {
824  return LHS |= *RHS;
825 }
826 
827 template <unsigned ElementSize>
829  const SparseBitVector<ElementSize> &RHS) {
830  return LHS->operator|=(RHS);
831 }
832 
833 template <unsigned ElementSize>
835  const SparseBitVector<ElementSize> &RHS) {
836  return LHS->operator&=(RHS);
837 }
838 
839 template <unsigned ElementSize>
841  const SparseBitVector<ElementSize> *RHS) {
842  return LHS &= *RHS;
843 }
844 
845 // Convenience functions for infix union, intersection, difference operators.
846 
847 template <unsigned ElementSize>
848 inline SparseBitVector<ElementSize>
850  const SparseBitVector<ElementSize> &RHS) {
851  SparseBitVector<ElementSize> Result(LHS);
852  Result |= RHS;
853  return Result;
854 }
855 
856 template <unsigned ElementSize>
857 inline SparseBitVector<ElementSize>
859  const SparseBitVector<ElementSize> &RHS) {
860  SparseBitVector<ElementSize> Result(LHS);
861  Result &= RHS;
862  return Result;
863 }
864 
865 template <unsigned ElementSize>
866 inline SparseBitVector<ElementSize>
868  const SparseBitVector<ElementSize> &RHS) {
870  Result.intersectWithComplement(LHS, RHS);
871  return Result;
872 }
873 
874 // Dump a SparseBitVector to a stream
875 template <unsigned ElementSize>
877  out << "[";
878 
879  typename SparseBitVector<ElementSize>::iterator bi = LHS.begin(),
880  be = LHS.end();
881  if (bi != be) {
882  out << *bi;
883  for (++bi; bi != be; ++bi) {
884  out << " " << *bi;
885  }
886  }
887  out << "]\n";
888 }
889 
890 } // end namespace llvm
891 
892 #endif // LLVM_ADT_SPARSEBITVECTOR_H
llvm::SparseBitVectorElement::index
unsigned index() const
Definition: SparseBitVector.h:87
i
i
Definition: README.txt:29
llvm::SparseBitVector::intersectWithComplement
void intersectWithComplement(const SparseBitVector< ElementSize > &RHS1, const SparseBitVector< ElementSize > &RHS2)
Definition: SparseBitVector.h:687
MathExtras.h
llvm::SparseBitVectorElement::operator!=
bool operator!=(const SparseBitVectorElement &RHS) const
Definition: SparseBitVector.h:77
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::SparseBitVectorElement::reset
void reset(unsigned Idx)
Definition: SparseBitVector.h:111
llvm::SparseBitVectorElement::empty
bool empty() const
Definition: SparseBitVector.h:91
llvm::SparseBitVectorElement::count
size_type count() const
Definition: SparseBitVector.h:119
llvm::SparseBitVector::clear
void clear()
Definition: SparseBitVector.h:451
llvm::SparseBitVector::SparseBitVector
SparseBitVector(SparseBitVector &&RHS)
Definition: SparseBitVector.h:447
llvm::SparseBitVector::intersectWithComplement
void intersectWithComplement(const SparseBitVector< ElementSize > *RHS1, const SparseBitVector< ElementSize > *RHS2)
Definition: SparseBitVector.h:733
llvm::SparseBitVector::operator=
SparseBitVector & operator=(const SparseBitVector &RHS)
Definition: SparseBitVector.h:456
llvm::SparseBitVector::count
unsigned count() const
Definition: SparseBitVector.h:799
ErrorHandling.h
llvm::SparseBitVector::begin
iterator begin() const
Definition: SparseBitVector.h:809
llvm::SparseBitVector::find_first
int find_first() const
Definition: SparseBitVector.h:779
llvm::SparseBitVector::reset
void reset(unsigned Idx)
Definition: SparseBitVector.h:486
llvm::tgtok::Bits
@ Bits
Definition: TGLexer.h:50
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::SparseBitVector::intersects
bool intersects(const SparseBitVector< ElementSize > &RHS) const
Definition: SparseBitVector.h:743
llvm::SparseBitVectorElement::BITWORDS_PER_ELEMENT
@ BITWORDS_PER_ELEMENT
Definition: SparseBitVector.h:47
llvm::SparseBitVector::operator|=
bool operator|=(const SparseBitVector &RHS)
Definition: SparseBitVector.h:557
llvm::SparseBitVectorElement::find_last
int find_last() const
find_last - Returns the index of the last set bit.
Definition: SparseBitVector.h:135
llvm::SparseBitVector::empty
bool empty() const
Definition: SparseBitVector.h:795
llvm::SparseBitVectorElement::size_type
unsigned size_type
Definition: SparseBitVector.h:44
llvm::SparseBitVector
Definition: SparseBitVector.h:255
llvm::operator&=
bool operator&=(SparseBitVector< ElementSize > *LHS, const SparseBitVector< ElementSize > &RHS)
Definition: SparseBitVector.h:834
llvm::SparseBitVectorElement::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:115
llvm::SparseBitVectorElement::intersectWith
bool intersectWith(const SparseBitVectorElement &RHS, bool &BecameZero)
Definition: SparseBitVector.h:194
llvm::SparseBitVector::test_and_set
bool test_and_set(unsigned Idx)
Definition: SparseBitVector.h:531
old
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n old
Definition: README.txt:123
llvm::SparseBitVectorElement::intersectWithComplement
bool intersectWithComplement(const SparseBitVectorElement &RHS, bool &BecameZero)
Definition: SparseBitVector.h:217
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
be
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can be
Definition: README.txt:14
llvm::operator-
APInt operator-(APInt)
Definition: APInt.h:2058
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
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::countPopulation
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:567
llvm::SparseBitVectorElement::SparseBitVectorElement
SparseBitVectorElement(unsigned Idx)
Definition: SparseBitVector.h:62
llvm::operator|
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2013
llvm::SparseBitVector::set
void set(unsigned Idx)
Definition: SparseBitVector.h:507
llvm::SparseBitVector::contains
bool contains(const SparseBitVector< ElementSize > &RHS) const
Definition: SparseBitVector.h:772
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
llvm::SparseBitVector::test
bool test(unsigned Idx) const
Definition: SparseBitVector.h:471
I
#define I(x, y, z)
Definition: MD5.cpp:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1609
llvm::SparseBitVector::operator=
SparseBitVector & operator=(SparseBitVector &&RHS)
Definition: SparseBitVector.h:464
llvm::SparseBitVectorElement::BITWORD_SIZE
@ BITWORD_SIZE
Definition: SparseBitVector.h:46
llvm::SparseBitVector::operator!=
bool operator!=(const SparseBitVector &RHS) const
Definition: SparseBitVector.h:540
llvm::SparseBitVector::operator==
bool operator==(const SparseBitVector &RHS) const
Definition: SparseBitVector.h:544
llvm::SparseBitVector::SparseBitVector
SparseBitVector()
Definition: SparseBitVector.h:443
llvm::SparseBitVector::intersects
bool intersects(const SparseBitVector< ElementSize > *RHS) const
Definition: SparseBitVector.h:738
llvm::SparseBitVectorElement::find_next
int find_next(unsigned Curr) const
find_next - Returns the index of the next set bit starting from the "Curr" bit.
Definition: SparseBitVector.h:147
llvm::operator*
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2105
llvm::SparseBitVectorElement::BITS_PER_ELEMENT
@ BITS_PER_ELEMENT
Definition: SparseBitVector.h:48
llvm::SparseBitVector::iterator
SparseBitVectorIterator iterator
Definition: SparseBitVector.h:441
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_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::operator|=
bool operator|=(SparseBitVector< ElementSize > &LHS, const SparseBitVector< ElementSize > *RHS)
Definition: SparseBitVector.h:822
llvm::operator&
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:1993
llvm::SparseBitVectorElement::BitWord
unsigned long BitWord
Definition: SparseBitVector.h:43
std
Definition: BitVector.h:838
llvm::SparseBitVectorElement::intersects
bool intersects(const SparseBitVectorElement &RHS) const
Definition: SparseBitVector.h:184
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::SparseBitVector::operator&=
bool operator&=(const SparseBitVector &RHS)
Definition: SparseBitVector.h:587
llvm::SparseBitVector::intersectWithComplement
bool intersectWithComplement(const SparseBitVector &RHS)
Definition: SparseBitVector.h:636
llvm::SparseBitVector::end
iterator end() const
Definition: SparseBitVector.h:813
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::SparseBitVectorElement::unionWith
bool unionWith(const SparseBitVectorElement &RHS)
Definition: SparseBitVector.h:171
llvm::SparseBitVectorElement::word
BitWord word(unsigned Idx) const
Definition: SparseBitVector.h:82
llvm::SparseBitVector::find_last
int find_last() const
Definition: SparseBitVector.h:787
llvm::SparseBitVectorElement::operator==
bool operator==(const SparseBitVectorElement &RHS) const
Definition: SparseBitVector.h:68
llvm::SparseBitVectorElement::set
void set(unsigned Idx)
Definition: SparseBitVector.h:98
raw_ostream.h
copy
we should consider alternate ways to model stack dependencies Lots of things could be done in WebAssemblyTargetTransformInfo cpp there are numerous optimization related hooks that can be overridden in WebAssemblyTargetLowering Instead of the OptimizeReturned which should consider preserving the returned attribute through to MachineInstrs and extending the MemIntrinsicResults pass to do this optimization on calls too That would also let the WebAssemblyPeephole pass clean up dead defs for such as it does for stores Consider implementing and or getMachineCombinerPatterns Find a clean way to fix the problem which leads to the Shrink Wrapping pass being run after the WebAssembly PEI pass When setting multiple variables to the same we currently get code like const It could be done with a smaller encoding like local tee $pop5 local copy
Definition: README.txt:101
llvm::SparseBitVectorElement::find_first
int find_first() const
find_first - Returns the index of the first set bit.
Definition: SparseBitVector.h:127
llvm::SparseBitVector::intersectWithComplement
bool intersectWithComplement(const SparseBitVector< ElementSize > *RHS) const
Definition: SparseBitVector.h:681
llvm::SparseBitVectorElement::intersectWithComplement
void intersectWithComplement(const SparseBitVectorElement &RHS1, const SparseBitVectorElement &RHS2, bool &BecameZero)
Definition: SparseBitVector.h:239
llvm::SparseBitVectorElement::test_and_set
bool test_and_set(unsigned Idx)
Definition: SparseBitVector.h:102
llvm::SparseBitVector::SparseBitVector
SparseBitVector(const SparseBitVector &RHS)
Definition: SparseBitVector.h:445
llvm::SparseBitVectorElement
SparseBitVector is an implementation of a bitvector that is sparse by only storing the elements that ...
Definition: SparseBitVector.h:41