include/llvm/ADT/BitVector.h

   1 //===- llvm/ADT/BitVector.h - Bit vectors -----------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements the BitVector class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_ADT_BITVECTOR_H
  14 #define LLVM_ADT_BITVECTOR_H
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/iterator_range.h"
  18 #include "llvm/Support/MathExtras.h"
  19 #include <algorithm>
  20 #include <cassert>
  21 #include <climits>
  22 #include <cstdint>
  23 #include <cstdlib>
  24 #include <cstring>
  25 #include <utility>
  26
  27 namespace llvm {
  28
  29 /// ForwardIterator for the bits that are set.
  30 /// Iterators get invalidated when resize / reserve is called.
  31 template <typename BitVectorT> class const_set_bits_iterator_impl {
  32   const BitVectorT &Parent;
  33   int Current = 0;
  34
  35   void advance() {
  36     assert(Current != -1 && "Trying to advance past end.");
  37     Current = Parent.find_next(Current);
  38   }
  39
  40 public:
  41   const_set_bits_iterator_impl(const BitVectorT &Parent, int Current)
  42       : Parent(Parent), Current(Current) {}
  43   explicit const_set_bits_iterator_impl(const BitVectorT &Parent)
  44       : const_set_bits_iterator_impl(Parent, Parent.find_first()) {}
  45   const_set_bits_iterator_impl(const const_set_bits_iterator_impl &) = default;
  46
  47   const_set_bits_iterator_impl operator++(int) {
  48     auto Prev = *this;
  49     advance();
  50     return Prev;
  51   }
  52
  53   const_set_bits_iterator_impl &operator++() {
  54     advance();
  55     return *this;
  56   }
  57
  58   unsigned operator*() const { return Current; }
  59
  60   bool operator==(const const_set_bits_iterator_impl &Other) const {
  61     assert(&Parent == &Other.Parent &&
  62            "Comparing iterators from different BitVectors");
  63     return Current == Other.Current;
  64   }
  65
  66   bool operator!=(const const_set_bits_iterator_impl &Other) const {
  67     assert(&Parent == &Other.Parent &&
  68            "Comparing iterators from different BitVectors");
  69     return Current != Other.Current;
  70   }
  71 };
  72
  73 class BitVector {
  74   typedef unsigned long BitWord;
  75
  76   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
  77
  78   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
  79                 "Unsupported word size");
  80
  81   MutableArrayRef<BitWord> Bits; // Actual bits.
  82   unsigned Size;                 // Size of bitvector in bits.
  83
  84 public:
  85   typedef unsigned size_type;
  86   // Encapsulation of a single bit.
  87   class reference {
  88     friend class BitVector;
  89
  90     BitWord *WordRef;
  91     unsigned BitPos;
  92
  93   public:
  94     reference(BitVector &b, unsigned Idx) {
  95       WordRef = &b.Bits[Idx / BITWORD_SIZE];
  96       BitPos = Idx % BITWORD_SIZE;
  97     }
  98
  99     reference() = delete;
 100     reference(const reference&) = default;
 101
 102     reference &operator=(reference t) {
 103       *this = bool(t);
 104       return *this;
 105     }
 106
 107     reference& operator=(bool t) {
 108       if (t)
 109         *WordRef |= BitWord(1) << BitPos;
 110       else
 111         *WordRef &= ~(BitWord(1) << BitPos);
 112       return *this;
 113     }
 114
 115     operator bool() const {
 116       return ((*WordRef) & (BitWord(1) << BitPos)) != 0;
 117     }
 118   };
 119
 120   typedef const_set_bits_iterator_impl<BitVector> const_set_bits_iterator;
 121   typedef const_set_bits_iterator set_iterator;
 122
 123   const_set_bits_iterator set_bits_begin() const {
 124     return const_set_bits_iterator(*this);
 125   }
 126   const_set_bits_iterator set_bits_end() const {
 127     return const_set_bits_iterator(*this, -1);
 128   }
 129   iterator_range<const_set_bits_iterator> set_bits() const {
 130     return make_range(set_bits_begin(), set_bits_end());
 131   }
 132
 133   /// BitVector default ctor - Creates an empty bitvector.
 134   BitVector() : Size(0) {}
 135
 136   /// BitVector ctor - Creates a bitvector of specified number of bits. All
 137   /// bits are initialized to the specified value.
 138   explicit BitVector(unsigned s, bool t = false) : Size(s) {
 139     size_t Capacity = NumBitWords(s);
 140     Bits = allocate(Capacity);
 141     init_words(Bits, t);
 142     if (t)
 143       clear_unused_bits();
 144   }
 145
 146   /// BitVector copy ctor.
 147   BitVector(const BitVector &RHS) : Size(RHS.size()) {
 148     if (Size == 0) {
 149       Bits = MutableArrayRef<BitWord>();
 150       return;
 151     }
 152
 153     size_t Capacity = NumBitWords(RHS.size());
 154     Bits = allocate(Capacity);
 155     std::memcpy(Bits.data(), RHS.Bits.data(), Capacity * sizeof(BitWord));
 156   }
 157
 158   BitVector(BitVector &&RHS) : Bits(RHS.Bits), Size(RHS.Size) {
 159     RHS.Bits = MutableArrayRef<BitWord>();
 160     RHS.Size = 0;
 161   }
 162
 163   ~BitVector() { std::free(Bits.data()); }
 164
 165   /// empty - Tests whether there are no bits in this bitvector.
 166   bool empty() const { return Size == 0; }
 167
 168   /// size - Returns the number of bits in this bitvector.
 169   size_type size() const { return Size; }
 170
 171   /// count - Returns the number of bits which are set.
 172   size_type count() const {
 173     unsigned NumBits = 0;
 174     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 175       NumBits += countPopulation(Bits[i]);
 176     return NumBits;
 177   }
 178
 179   /// any - Returns true if any bit is set.
 180   bool any() const {
 181     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 182       if (Bits[i] != 0)
 183         return true;
 184     return false;
 185   }
 186
 187   /// all - Returns true if all bits are set.
 188   bool all() const {
 189     for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
 190       if (Bits[i] != ~0UL)
 191         return false;
 192
 193     // If bits remain check that they are ones. The unused bits are always zero.
 194     if (unsigned Remainder = Size % BITWORD_SIZE)
 195       return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
 196
 197     return true;
 198   }
 199
 200   /// none - Returns true if none of the bits are set.
 201   bool none() const {
 202     return !any();
 203   }
 204
 205   /// find_first_in - Returns the index of the first set bit in the range
 206   /// [Begin, End).  Returns -1 if all bits in the range are unset.
 207   int find_first_in(unsigned Begin, unsigned End) const {
 208     assert(Begin <= End && End <= Size);
 209     if (Begin == End)
 210       return -1;
 211
 212     unsigned FirstWord = Begin / BITWORD_SIZE;
 213     unsigned LastWord = (End - 1) / BITWORD_SIZE;
 214
 215     // Check subsequent words.
 216     for (unsigned i = FirstWord; i <= LastWord; ++i) {
 217       BitWord Copy = Bits[i];
 218
 219       if (i == FirstWord) {
 220         unsigned FirstBit = Begin % BITWORD_SIZE;
 221         Copy &= maskTrailingZeros<BitWord>(FirstBit);
 222       }
 223
 224       if (i == LastWord) {
 225         unsigned LastBit = (End - 1) % BITWORD_SIZE;
 226         Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
 227       }
 228       if (Copy != 0)
 229         return i * BITWORD_SIZE + countTrailingZeros(Copy);
 230     }
 231     return -1;
 232   }
 233
 234   /// find_last_in - Returns the index of the last set bit in the range
 235   /// [Begin, End).  Returns -1 if all bits in the range are unset.
 236   int find_last_in(unsigned Begin, unsigned End) const {
 237     assert(Begin <= End && End <= Size);
 238     if (Begin == End)
 239       return -1;
 240
 241     unsigned LastWord = (End - 1) / BITWORD_SIZE;
 242     unsigned FirstWord = Begin / BITWORD_SIZE;
 243
 244     for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
 245       unsigned CurrentWord = i - 1;
 246
 247       BitWord Copy = Bits[CurrentWord];
 248       if (CurrentWord == LastWord) {
 249         unsigned LastBit = (End - 1) % BITWORD_SIZE;
 250         Copy &= maskTrailingOnes<BitWord>(LastBit + 1);
 251       }
 252
 253       if (CurrentWord == FirstWord) {
 254         unsigned FirstBit = Begin % BITWORD_SIZE;
 255         Copy &= maskTrailingZeros<BitWord>(FirstBit);
 256       }
 257
 258       if (Copy != 0)
 259         return (CurrentWord + 1) * BITWORD_SIZE - countLeadingZeros(Copy) - 1;
 260     }
 261
 262     return -1;
 263   }
 264
 265   /// find_first_unset_in - Returns the index of the first unset bit in the
 266   /// range [Begin, End).  Returns -1 if all bits in the range are set.
 267   int find_first_unset_in(unsigned Begin, unsigned End) const {
 268     assert(Begin <= End && End <= Size);
 269     if (Begin == End)
 270       return -1;
 271
 272     unsigned FirstWord = Begin / BITWORD_SIZE;
 273     unsigned LastWord = (End - 1) / BITWORD_SIZE;
 274
 275     // Check subsequent words.
 276     for (unsigned i = FirstWord; i <= LastWord; ++i) {
 277       BitWord Copy = Bits[i];
 278
 279       if (i == FirstWord) {
 280         unsigned FirstBit = Begin % BITWORD_SIZE;
 281         Copy |= maskTrailingOnes<BitWord>(FirstBit);
 282       }
 283
 284       if (i == LastWord) {
 285         unsigned LastBit = (End - 1) % BITWORD_SIZE;
 286         Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
 287       }
 288       if (Copy != ~0UL) {
 289         unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
 290         return Result < size() ? Result : -1;
 291       }
 292     }
 293     return -1;
 294   }
 295
 296   /// find_last_unset_in - Returns the index of the last unset bit in the
 297   /// range [Begin, End).  Returns -1 if all bits in the range are set.
 298   int find_last_unset_in(unsigned Begin, unsigned End) const {
 299     assert(Begin <= End && End <= Size);
 300     if (Begin == End)
 301       return -1;
 302
 303     unsigned LastWord = (End - 1) / BITWORD_SIZE;
 304     unsigned FirstWord = Begin / BITWORD_SIZE;
 305
 306     for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
 307       unsigned CurrentWord = i - 1;
 308
 309       BitWord Copy = Bits[CurrentWord];
 310       if (CurrentWord == LastWord) {
 311         unsigned LastBit = (End - 1) % BITWORD_SIZE;
 312         Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
 313       }
 314
 315       if (CurrentWord == FirstWord) {
 316         unsigned FirstBit = Begin % BITWORD_SIZE;
 317         Copy |= maskTrailingOnes<BitWord>(FirstBit);
 318       }
 319
 320       if (Copy != ~0UL) {
 321         unsigned Result =
 322             (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
 323         return Result < Size ? Result : -1;
 324       }
 325     }
 326     return -1;
 327   }
 328
 329   /// find_first - Returns the index of the first set bit, -1 if none
 330   /// of the bits are set.
 331   int find_first() const { return find_first_in(0, Size); }
 332
 333   /// find_last - Returns the index of the last set bit, -1 if none of the bits
 334   /// are set.
 335   int find_last() const { return find_last_in(0, Size); }
 336
 337   /// find_next - Returns the index of the next set bit following the
 338   /// "Prev" bit. Returns -1 if the next set bit is not found.
 339   int find_next(unsigned Prev) const { return find_first_in(Prev + 1, Size); }
 340
 341   /// find_prev - Returns the index of the first set bit that precedes the
 342   /// the bit at \p PriorTo.  Returns -1 if all previous bits are unset.
 343   int find_prev(unsigned PriorTo) const { return find_last_in(0, PriorTo); }
 344
 345   /// find_first_unset - Returns the index of the first unset bit, -1 if all
 346   /// of the bits are set.
 347   int find_first_unset() const { return find_first_unset_in(0, Size); }
 348
 349   /// find_next_unset - Returns the index of the next unset bit following the
 350   /// "Prev" bit.  Returns -1 if all remaining bits are set.
 351   int find_next_unset(unsigned Prev) const {
 352     return find_first_unset_in(Prev + 1, Size);
 353   }
 354
 355   /// find_last_unset - Returns the index of the last unset bit, -1 if all of
 356   /// the bits are set.
 357   int find_last_unset() const { return find_last_unset_in(0, Size); }
 358
 359   /// find_prev_unset - Returns the index of the first unset bit that precedes
 360   /// the bit at \p PriorTo.  Returns -1 if all previous bits are set.
 361   int find_prev_unset(unsigned PriorTo) {
 362     return find_last_unset_in(0, PriorTo);
 363   }
 364
 365   /// clear - Removes all bits from the bitvector. Does not change capacity.
 366   void clear() {
 367     Size = 0;
 368   }
 369
 370   /// resize - Grow or shrink the bitvector.
 371   void resize(unsigned N, bool t = false) {
 372     if (N > getBitCapacity()) {
 373       unsigned OldCapacity = Bits.size();
 374       grow(N);
 375       init_words(Bits.drop_front(OldCapacity), t);
 376     }
 377
 378     // Set any old unused bits that are now included in the BitVector. This
 379     // may set bits that are not included in the new vector, but we will clear
 380     // them back out below.
 381     if (N > Size)
 382       set_unused_bits(t);
 383
 384     // Update the size, and clear out any bits that are now unused
 385     unsigned OldSize = Size;
 386     Size = N;
 387     if (t || N < OldSize)
 388       clear_unused_bits();
 389   }
 390
 391   void reserve(unsigned N) {
 392     if (N > getBitCapacity())
 393       grow(N);
 394   }
 395
 396   // Set, reset, flip
 397   BitVector &set() {
 398     init_words(Bits, true);
 399     clear_unused_bits();
 400     return *this;
 401   }
 402
 403   BitVector &set(unsigned Idx) {
 404     assert(Bits.data() && "Bits never allocated");
 405     Bits[Idx / BITWORD_SIZE] |= BitWord(1) << (Idx % BITWORD_SIZE);
 406     return *this;
 407   }
 408
 409   /// set - Efficiently set a range of bits in [I, E)
 410   BitVector &set(unsigned I, unsigned E) {
 411     assert(I <= E && "Attempted to set backwards range!");
 412     assert(E <= size() && "Attempted to set out-of-bounds range!");
 413
 414     if (I == E) return *this;
 415
 416     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
 417       BitWord EMask = 1UL << (E % BITWORD_SIZE);
 418       BitWord IMask = 1UL << (I % BITWORD_SIZE);
 419       BitWord Mask = EMask - IMask;
 420       Bits[I / BITWORD_SIZE] |= Mask;
 421       return *this;
 422     }
 423
 424     BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
 425     Bits[I / BITWORD_SIZE] |= PrefixMask;
 426     I = alignTo(I, BITWORD_SIZE);
 427
 428     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
 429       Bits[I / BITWORD_SIZE] = ~0UL;
 430
 431     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
 432     if (I < E)
 433       Bits[I / BITWORD_SIZE] |= PostfixMask;
 434
 435     return *this;
 436   }
 437
 438   BitVector &reset() {
 439     init_words(Bits, false);
 440     return *this;
 441   }
 442
 443   BitVector &reset(unsigned Idx) {
 444     Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
 445     return *this;
 446   }
 447
 448   /// reset - Efficiently reset a range of bits in [I, E)
 449   BitVector &reset(unsigned I, unsigned E) {
 450     assert(I <= E && "Attempted to reset backwards range!");
 451     assert(E <= size() && "Attempted to reset out-of-bounds range!");
 452
 453     if (I == E) return *this;
 454
 455     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
 456       BitWord EMask = 1UL << (E % BITWORD_SIZE);
 457       BitWord IMask = 1UL << (I % BITWORD_SIZE);
 458       BitWord Mask = EMask - IMask;
 459       Bits[I / BITWORD_SIZE] &= ~Mask;
 460       return *this;
 461     }
 462
 463     BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
 464     Bits[I / BITWORD_SIZE] &= ~PrefixMask;
 465     I = alignTo(I, BITWORD_SIZE);
 466
 467     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
 468       Bits[I / BITWORD_SIZE] = 0UL;
 469
 470     BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
 471     if (I < E)
 472       Bits[I / BITWORD_SIZE] &= ~PostfixMask;
 473
 474     return *this;
 475   }
 476
 477   BitVector &flip() {
 478     for (unsigned i = 0; i < NumBitWords(size()); ++i)
 479       Bits[i] = ~Bits[i];
 480     clear_unused_bits();
 481     return *this;
 482   }
 483
 484   BitVector &flip(unsigned Idx) {
 485     Bits[Idx / BITWORD_SIZE] ^= BitWord(1) << (Idx % BITWORD_SIZE);
 486     return *this;
 487   }
 488
 489   // Indexing.
 490   reference operator[](unsigned Idx) {
 491     assert (Idx < Size && "Out-of-bounds Bit access.");
 492     return reference(*this, Idx);
 493   }
 494
 495   bool operator[](unsigned Idx) const {
 496     assert (Idx < Size && "Out-of-bounds Bit access.");
 497     BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
 498     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
 499   }
 500
 501   bool test(unsigned Idx) const {
 502     return (*this)[Idx];
 503   }
 504
 505   // Push single bit to end of vector.
 506   void push_back(bool Val) {
 507     unsigned OldSize = Size;
 508     unsigned NewSize = Size + 1;
 509
 510     // Resize, which will insert zeros.
 511     // If we already fit then the unused bits will be already zero.
 512     if (NewSize > getBitCapacity())
 513       resize(NewSize, false);
 514     else
 515       Size = NewSize;
 516
 517     // If true, set single bit.
 518     if (Val)
 519       set(OldSize);
 520   }
 521
 522   /// Test if any common bits are set.
 523   bool anyCommon(const BitVector &RHS) const {
 524     unsigned ThisWords = NumBitWords(size());
 525     unsigned RHSWords  = NumBitWords(RHS.size());
 526     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
 527       if (Bits[i] & RHS.Bits[i])
 528         return true;
 529     return false;
 530   }
 531
 532   // Comparison operators.
 533   bool operator==(const BitVector &RHS) const {
 534     unsigned ThisWords = NumBitWords(size());
 535     unsigned RHSWords  = NumBitWords(RHS.size());
 536     unsigned i;
 537     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
 538       if (Bits[i] != RHS.Bits[i])
 539         return false;
 540
 541     // Verify that any extra words are all zeros.
 542     if (i != ThisWords) {
 543       for (; i != ThisWords; ++i)
 544         if (Bits[i])
 545           return false;
 546     } else if (i != RHSWords) {
 547       for (; i != RHSWords; ++i)
 548         if (RHS.Bits[i])
 549           return false;
 550     }
 551     return true;
 552   }
 553
 554   bool operator!=(const BitVector &RHS) const {
 555     return !(*this == RHS);
 556   }
 557
 558   /// Intersection, union, disjoint union.
 559   BitVector &operator&=(const BitVector &RHS) {
 560     unsigned ThisWords = NumBitWords(size());
 561     unsigned RHSWords  = NumBitWords(RHS.size());
 562     unsigned i;
 563     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
 564       Bits[i] &= RHS.Bits[i];
 565
 566     // Any bits that are just in this bitvector become zero, because they aren't
 567     // in the RHS bit vector.  Any words only in RHS are ignored because they
 568     // are already zero in the LHS.
 569     for (; i != ThisWords; ++i)
 570       Bits[i] = 0;
 571
 572     return *this;
 573   }
 574
 575   /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS.
 576   BitVector &reset(const BitVector &RHS) {
 577     unsigned ThisWords = NumBitWords(size());
 578     unsigned RHSWords  = NumBitWords(RHS.size());
 579     unsigned i;
 580     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
 581       Bits[i] &= ~RHS.Bits[i];
 582     return *this;
 583   }
 584
 585   /// test - Check if (This - RHS) is zero.
 586   /// This is the same as reset(RHS) and any().
 587   bool test(const BitVector &RHS) const {
 588     unsigned ThisWords = NumBitWords(size());
 589     unsigned RHSWords  = NumBitWords(RHS.size());
 590     unsigned i;
 591     for (i = 0; i != std::min(ThisWords, RHSWords); ++i)
 592       if ((Bits[i] & ~RHS.Bits[i]) != 0)
 593         return true;
 594
 595     for (; i != ThisWords ; ++i)
 596       if (Bits[i] != 0)
 597         return true;
 598
 599     return false;
 600   }
 601
 602   BitVector &operator|=(const BitVector &RHS) {
 603     if (size() < RHS.size())
 604       resize(RHS.size());
 605     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
 606       Bits[i] |= RHS.Bits[i];
 607     return *this;
 608   }
 609
 610   BitVector &operator^=(const BitVector &RHS) {
 611     if (size() < RHS.size())
 612       resize(RHS.size());
 613     for (size_t i = 0, e = NumBitWords(RHS.size()); i != e; ++i)
 614       Bits[i] ^= RHS.Bits[i];
 615     return *this;
 616   }
 617
 618   BitVector &operator>>=(unsigned N) {
 619     assert(N <= Size);
 620     if (LLVM_UNLIKELY(empty() || N == 0))
 621       return *this;
 622
 623     unsigned NumWords = NumBitWords(Size);
 624     assert(NumWords >= 1);
 625
 626     wordShr(N / BITWORD_SIZE);
 627
 628     unsigned BitDistance = N % BITWORD_SIZE;
 629     if (BitDistance == 0)
 630       return *this;
 631
 632     // When the shift size is not a multiple of the word size, then we have
 633     // a tricky situation where each word in succession needs to extract some
 634     // of the bits from the next word and or them into this word while
 635     // shifting this word to make room for the new bits.  This has to be done
 636     // for every word in the array.
 637
 638     // Since we're shifting each word right, some bits will fall off the end
 639     // of each word to the right, and empty space will be created on the left.
 640     // The final word in the array will lose bits permanently, so starting at
 641     // the beginning, work forwards shifting each word to the right, and
 642     // OR'ing in the bits from the end of the next word to the beginning of
 643     // the current word.
 644
 645     // Example:
 646     //   Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting right
 647     //   by 4 bits.
 648     // Step 1: Word[0] >>= 4           ; 0x0ABBCCDD
 649     // Step 2: Word[0] |= 0x10000000   ; 0x1ABBCCDD
 650     // Step 3: Word[1] >>= 4           ; 0x0EEFF001
 651     // Step 4: Word[1] |= 0x50000000   ; 0x5EEFF001
 652     // Step 5: Word[2] >>= 4           ; 0x02334455
 653     // Result: { 0x1ABBCCDD, 0x5EEFF001, 0x02334455 }
 654     const BitWord Mask = maskTrailingOnes<BitWord>(BitDistance);
 655     const unsigned LSH = BITWORD_SIZE - BitDistance;
 656
 657     for (unsigned I = 0; I < NumWords - 1; ++I) {
 658       Bits[I] >>= BitDistance;
 659       Bits[I] |= (Bits[I + 1] & Mask) << LSH;
 660     }
 661
 662     Bits[NumWords - 1] >>= BitDistance;
 663
 664     return *this;
 665   }
 666
 667   BitVector &operator<<=(unsigned N) {
 668     assert(N <= Size);
 669     if (LLVM_UNLIKELY(empty() || N == 0))
 670       return *this;
 671
 672     unsigned NumWords = NumBitWords(Size);
 673     assert(NumWords >= 1);
 674
 675     wordShl(N / BITWORD_SIZE);
 676
 677     unsigned BitDistance = N % BITWORD_SIZE;
 678     if (BitDistance == 0)
 679       return *this;
 680
 681     // When the shift size is not a multiple of the word size, then we have
 682     // a tricky situation where each word in succession needs to extract some
 683     // of the bits from the previous word and or them into this word while
 684     // shifting this word to make room for the new bits.  This has to be done
 685     // for every word in the array.  This is similar to the algorithm outlined
 686     // in operator>>=, but backwards.
 687
 688     // Since we're shifting each word left, some bits will fall off the end
 689     // of each word to the left, and empty space will be created on the right.
 690     // The first word in the array will lose bits permanently, so starting at
 691     // the end, work backwards shifting each word to the left, and OR'ing
 692     // in the bits from the end of the next word to the beginning of the
 693     // current word.
 694
 695     // Example:
 696     //   Starting with {0xAABBCCDD, 0xEEFF0011, 0x22334455} and shifting left
 697     //   by 4 bits.
 698     // Step 1: Word[2] <<= 4           ; 0x23344550
 699     // Step 2: Word[2] |= 0x0000000E   ; 0x2334455E
 700     // Step 3: Word[1] <<= 4           ; 0xEFF00110
 701     // Step 4: Word[1] |= 0x0000000A   ; 0xEFF0011A
 702     // Step 5: Word[0] <<= 4           ; 0xABBCCDD0
 703     // Result: { 0xABBCCDD0, 0xEFF0011A, 0x2334455E }
 704     const BitWord Mask = maskLeadingOnes<BitWord>(BitDistance);
 705     const unsigned RSH = BITWORD_SIZE - BitDistance;
 706
 707     for (int I = NumWords - 1; I > 0; --I) {
 708       Bits[I] <<= BitDistance;
 709       Bits[I] |= (Bits[I - 1] & Mask) >> RSH;
 710     }
 711     Bits[0] <<= BitDistance;
 712     clear_unused_bits();
 713
 714     return *this;
 715   }
 716
 717   // Assignment operator.
 718   const BitVector &operator=(const BitVector &RHS) {
 719     if (this == &RHS) return *this;
 720
 721     Size = RHS.size();
 722     unsigned RHSWords = NumBitWords(Size);
 723     if (Size <= getBitCapacity()) {
 724       if (Size)
 725         std::memcpy(Bits.data(), RHS.Bits.data(), RHSWords * sizeof(BitWord));
 726       clear_unused_bits();
 727       return *this;
 728     }
 729
 730     // Grow the bitvector to have enough elements.
 731     unsigned NewCapacity = RHSWords;
 732     assert(NewCapacity > 0 && "negative capacity?");
 733     auto NewBits = allocate(NewCapacity);
 734     std::memcpy(NewBits.data(), RHS.Bits.data(), NewCapacity * sizeof(BitWord));
 735
 736     // Destroy the old bits.
 737     std::free(Bits.data());
 738     Bits = NewBits;
 739
 740     return *this;
 741   }
 742
 743   const BitVector &operator=(BitVector &&RHS) {
 744     if (this == &RHS) return *this;
 745
 746     std::free(Bits.data());
 747     Bits = RHS.Bits;
 748     Size = RHS.Size;
 749
 750     RHS.Bits = MutableArrayRef<BitWord>();
 751     RHS.Size = 0;
 752
 753     return *this;
 754   }
 755
 756   void swap(BitVector &RHS) {
 757     std::swap(Bits, RHS.Bits);
 758     std::swap(Size, RHS.Size);
 759   }
 760
 761   //===--------------------------------------------------------------------===//
 762   // Portable bit mask operations.
 763   //===--------------------------------------------------------------------===//
 764   //
 765   // These methods all operate on arrays of uint32_t, each holding 32 bits. The
 766   // fixed word size makes it easier to work with literal bit vector constants
 767   // in portable code.
 768   //
 769   // The LSB in each word is the lowest numbered bit.  The size of a portable
 770   // bit mask is always a whole multiple of 32 bits.  If no bit mask size is
 771   // given, the bit mask is assumed to cover the entire BitVector.
 772
 773   /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize.
 774   /// This computes "*this |= Mask".
 775   void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 776     applyMask<true, false>(Mask, MaskWords);
 777   }
 778
 779   /// clearBitsInMask - Clear any bits in this vector that are set in Mask.
 780   /// Don't resize. This computes "*this &= ~Mask".
 781   void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 782     applyMask<false, false>(Mask, MaskWords);
 783   }
 784
 785   /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask.
 786   /// Don't resize.  This computes "*this |= ~Mask".
 787   void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 788     applyMask<true, true>(Mask, MaskWords);
 789   }
 790
 791   /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask.
 792   /// Don't resize.  This computes "*this &= Mask".
 793   void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) {
 794     applyMask<false, true>(Mask, MaskWords);
 795   }
 796
 797 private:
 798   /// Perform a logical left shift of \p Count words by moving everything
 799   /// \p Count words to the right in memory.
 800   ///
 801   /// While confusing, words are stored from least significant at Bits[0] to
 802   /// most significant at Bits[NumWords-1].  A logical shift left, however,
 803   /// moves the current least significant bit to a higher logical index, and
 804   /// fills the previous least significant bits with 0.  Thus, we actually
 805   /// need to move the bytes of the memory to the right, not to the left.
 806   /// Example:
 807   ///   Words = [0xBBBBAAAA, 0xDDDDFFFF, 0x00000000, 0xDDDD0000]
 808   /// represents a BitVector where 0xBBBBAAAA contain the least significant
 809   /// bits.  So if we want to shift the BitVector left by 2 words, we need to
 810   /// turn this into 0x00000000 0x00000000 0xBBBBAAAA 0xDDDDFFFF by using a
 811   /// memmove which moves right, not left.
 812   void wordShl(uint32_t Count) {
 813     if (Count == 0)
 814       return;
 815
 816     uint32_t NumWords = NumBitWords(Size);
 817
 818     auto Src = Bits.take_front(NumWords).drop_back(Count);
 819     auto Dest = Bits.take_front(NumWords).drop_front(Count);
 820
 821     // Since we always move Word-sized chunks of data with src and dest both
 822     // aligned to a word-boundary, we don't need to worry about endianness
 823     // here.
 824     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
 825     std::memset(Bits.data(), 0, Count * sizeof(BitWord));
 826     clear_unused_bits();
 827   }
 828
 829   /// Perform a logical right shift of \p Count words by moving those
 830   /// words to the left in memory.  See wordShl for more information.
 831   ///
 832   void wordShr(uint32_t Count) {
 833     if (Count == 0)
 834       return;
 835
 836     uint32_t NumWords = NumBitWords(Size);
 837
 838     auto Src = Bits.take_front(NumWords).drop_front(Count);
 839     auto Dest = Bits.take_front(NumWords).drop_back(Count);
 840     assert(Dest.size() == Src.size());
 841
 842     std::memmove(Dest.begin(), Src.begin(), Dest.size() * sizeof(BitWord));
 843     std::memset(Dest.end(), 0, Count * sizeof(BitWord));
 844   }
 845
 846   MutableArrayRef<BitWord> allocate(size_t NumWords) {
 847     BitWord *RawBits = static_cast<BitWord *>(
 848         safe_malloc(NumWords * sizeof(BitWord)));
 849     return MutableArrayRef<BitWord>(RawBits, NumWords);
 850   }
 851
 852   int next_unset_in_word(int WordIndex, BitWord Word) const {
 853     unsigned Result = WordIndex * BITWORD_SIZE + countTrailingOnes(Word);
 854     return Result < size() ? Result : -1;
 855   }
 856
 857   unsigned NumBitWords(unsigned S) const {
 858     return (S + BITWORD_SIZE-1) / BITWORD_SIZE;
 859   }
 860
 861   // Set the unused bits in the high words.
 862   void set_unused_bits(bool t = true) {
 863     //  Set high words first.
 864     unsigned UsedWords = NumBitWords(Size);
 865     if (Bits.size() > UsedWords)
 866       init_words(Bits.drop_front(UsedWords), t);
 867
 868     //  Then set any stray high bits of the last used word.
 869     unsigned ExtraBits = Size % BITWORD_SIZE;
 870     if (ExtraBits) {
 871       BitWord ExtraBitMask = ~0UL << ExtraBits;
 872       if (t)
 873         Bits[UsedWords-1] |= ExtraBitMask;
 874       else
 875         Bits[UsedWords-1] &= ~ExtraBitMask;
 876     }
 877   }
 878
 879   // Clear the unused bits in the high words.
 880   void clear_unused_bits() {
 881     set_unused_bits(false);
 882   }
 883
 884   void grow(unsigned NewSize) {
 885     size_t NewCapacity = std::max<size_t>(NumBitWords(NewSize), Bits.size() * 2);
 886     assert(NewCapacity > 0 && "realloc-ing zero space");
 887     BitWord *NewBits = static_cast<BitWord *>(
 888         safe_realloc(Bits.data(), NewCapacity * sizeof(BitWord)));
 889     Bits = MutableArrayRef<BitWord>(NewBits, NewCapacity);
 890     clear_unused_bits();
 891   }
 892
 893   void init_words(MutableArrayRef<BitWord> B, bool t) {
 894     if (B.size() > 0)
 895       memset(B.data(), 0 - (int)t, B.size() * sizeof(BitWord));
 896   }
 897
 898   template<bool AddBits, bool InvertMask>
 899   void applyMask(const uint32_t *Mask, unsigned MaskWords) {
 900     static_assert(BITWORD_SIZE % 32 == 0, "Unsupported BitWord size.");
 901     MaskWords = std::min(MaskWords, (size() + 31) / 32);
 902     const unsigned Scale = BITWORD_SIZE / 32;
 903     unsigned i;
 904     for (i = 0; MaskWords >= Scale; ++i, MaskWords -= Scale) {
 905       BitWord BW = Bits[i];
 906       // This inner loop should unroll completely when BITWORD_SIZE > 32.
 907       for (unsigned b = 0; b != BITWORD_SIZE; b += 32) {
 908         uint32_t M = *Mask++;
 909         if (InvertMask) M = ~M;
 910         if (AddBits) BW |=   BitWord(M) << b;
 911         else         BW &= ~(BitWord(M) << b);
 912       }
 913       Bits[i] = BW;
 914     }
 915     for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
 916       uint32_t M = *Mask++;
 917       if (InvertMask) M = ~M;
 918       if (AddBits) Bits[i] |=   BitWord(M) << b;
 919       else         Bits[i] &= ~(BitWord(M) << b);
 920     }
 921     if (AddBits)
 922       clear_unused_bits();
 923   }
 924
 925 public:
 926   /// Return the size (in bytes) of the bit vector.
 927   size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
 928   size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
 929 };
 930
 931 inline size_t capacity_in_bytes(const BitVector &X) {
 932   return X.getMemorySize();
 933 }
 934
 935 } // end namespace llvm
 936
 937 namespace std {
 938   /// Implement std::swap in terms of BitVector swap.
 939   inline void
 940   swap(llvm::BitVector &LHS, llvm::BitVector &RHS) {
 941     LHS.swap(RHS);
 942   }
 943 } // end namespace std
 944
 945 #endif // LLVM_ADT_BITVECTOR_H