include/llvm/ADT/SparseBitVector.h

   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
  17 #include "llvm/Support/ErrorHandling.h"
  18 #include "llvm/Support/MathExtras.h"
  19 #include "llvm/Support/raw_ostream.h"
  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,
  47     BITWORDS_PER_ELEMENT = (ElementSize + BITWORD_SIZE - 1) / BITWORD_SIZE,
  48     BITS_PER_ELEMENT = ElementSize
  49   };
  50
  51 private:
  52   // Index of Element in terms of where first bit starts.
  53   unsigned ElementIndex;
  54   BitWord Bits[BITWORDS_PER_ELEMENT];
  55
  56   SparseBitVectorElement() {
  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 {
  83     assert(Idx < BITWORDS_PER_ELEMENT);
  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.
 171   bool unionWith(const SparseBitVectorElement &RHS) {
 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.
 194   bool intersectWith(const SparseBitVectorElement &RHS,
 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.
 217   bool intersectWithComplement(const SparseBitVectorElement &RHS,
 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
 239   void intersectWithComplement(const SparseBitVectorElement &RHS1,
 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>
 255 class SparseBitVector {
 256   using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
 257   using ElementListIter = typename ElementList::iterator;
 258   using ElementListConstIter = typename ElementList::const_iterator;
 259   enum {
 260     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
 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.
 334     typename SparseBitVectorElement<ElementSize>::BitWord Bits;
 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
 445   SparseBitVector(const SparseBitVector &RHS)
 446       : Elements(RHS.Elements), CurrElementIter(Elements.begin()) {}
 447   SparseBitVector(SparseBitVector &&RHS)
 448       : Elements(std::move(RHS.Elements)), CurrElementIter(Elements.begin()) {}
 449
 450   // Clear.
 451   void clear() {
 452     Elements.clear();
 453   }
 454
 455   // Assignment
 456   SparseBitVector& operator=(const SparseBitVector& RHS) {
 457     if (this == &RHS)
 458       return *this;
 459
 460     Elements = RHS.Elements;
 461     CurrElementIter = Elements.begin();
 462     return *this;
 463   }
 464   SparseBitVector &operator=(SparseBitVector &&RHS) {
 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.
 636   bool intersectWithComplement(const SparseBitVector &RHS) {
 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
 681   bool intersectWithComplement(const SparseBitVector<ElementSize> *RHS) const {
 682     return intersectWithComplement(*RHS);
 683   }
 684
 685   //  Three argument version of intersectWithComplement.
 686   //  Result of RHS1 & ~RHS2 is stored into this bitmap.
 687   void intersectWithComplement(const SparseBitVector<ElementSize> &RHS1,
 688                                const SparseBitVector<ElementSize> &RHS2)
 689   {
 690     if (this == &RHS1) {
 691       intersectWithComplement(RHS2);
 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
 733   void intersectWithComplement(const SparseBitVector<ElementSize> *RHS1,
 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>
 822 inline bool operator |=(SparseBitVector<ElementSize> &LHS,
 823                         const SparseBitVector<ElementSize> *RHS) {
 824   return LHS |= *RHS;
 825 }
 826
 827 template <unsigned ElementSize>
 828 inline bool operator |=(SparseBitVector<ElementSize> *LHS,
 829                         const SparseBitVector<ElementSize> &RHS) {
 830   return LHS->operator|=(RHS);
 831 }
 832
 833 template <unsigned ElementSize>
 834 inline bool operator &=(SparseBitVector<ElementSize> *LHS,
 835                         const SparseBitVector<ElementSize> &RHS) {
 836   return LHS->operator&=(RHS);
 837 }
 838
 839 template <unsigned ElementSize>
 840 inline bool operator &=(SparseBitVector<ElementSize> &LHS,
 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>
 849 operator|(const SparseBitVector<ElementSize> &LHS,
 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>
 858 operator&(const SparseBitVector<ElementSize> &LHS,
 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>
 867 operator-(const SparseBitVector<ElementSize> &LHS,
 868           const SparseBitVector<ElementSize> &RHS) {
 869   SparseBitVector<ElementSize> Result;
 870   Result.intersectWithComplement(LHS, RHS);
 871   return Result;
 872 }
 873
 874 // Dump a SparseBitVector to a stream
 875 template <unsigned ElementSize>
 876 void dump(const SparseBitVector<ElementSize> &LHS, raw_ostream &out) {
 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