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