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