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 uintptr_t 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] != ~BitWord(0)) 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] == (BitWord(1) << 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 != ~BitWord(0)) { 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 != ~BitWord(0)) { 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 = BitWord(1) << (E % BITWORD_SIZE); 418 BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); 419 BitWord Mask = EMask - IMask; 420 Bits[I / BITWORD_SIZE] |= Mask; 421 return *this; 422 } 423 424 BitWord PrefixMask = ~BitWord(0) << (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] = ~BitWord(0); 430 431 BitWord PostfixMask = (BitWord(1) << (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 = BitWord(1) << (E % BITWORD_SIZE); 457 BitWord IMask = BitWord(1) << (I % BITWORD_SIZE); 458 BitWord Mask = EMask - IMask; 459 Bits[I / BITWORD_SIZE] &= ~Mask; 460 return *this; 461 } 462 463 BitWord PrefixMask = ~BitWord(0) << (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] = BitWord(0); 469 470 BitWord PostfixMask = (BitWord(1) << (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 = ~BitWord(0) << 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 946