1 //===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the SmallBitVector class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_ADT_SMALLBITVECTOR_H 15 #define LLVM_ADT_SMALLBITVECTOR_H 16 17 #include "llvm/ADT/BitVector.h" 18 #include "llvm/Support/Compiler.h" 19 #include "llvm/Support/MathExtras.h" 20 #include <cassert> 21 22 namespace llvm { 23 24 /// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 25 /// optimized for the case when the array is small. It contains one 26 /// pointer-sized field, which is directly used as a plain collection of bits 27 /// when possible, or as a pointer to a larger heap-allocated array when 28 /// necessary. This allows normal "small" cases to be fast without losing 29 /// generality for large inputs. 30 /// 31 class SmallBitVector { 32 // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 33 // unnecessary level of indirection. It would be more efficient to use a 34 // pointer to memory containing size, allocation size, and the array of bits. 35 uintptr_t X; 36 37 enum { 38 // The number of bits in this class. 39 NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 40 41 // One bit is used to discriminate between small and large mode. The 42 // remaining bits are used for the small-mode representation. 43 SmallNumRawBits = NumBaseBits - 1, 44 45 // A few more bits are used to store the size of the bit set in small mode. 46 // Theoretically this is a ceil-log2. These bits are encoded in the most 47 // significant bits of the raw bits. 48 SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 49 NumBaseBits == 64 ? 6 : 50 SmallNumRawBits), 51 52 // The remaining bits are used to store the actual set in small mode. 53 SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 54 }; 55 56 static_assert(NumBaseBits == 64 || NumBaseBits == 32, 57 "Unsupported word size"); 58 59 public: 60 typedef unsigned size_type; 61 // Encapsulation of a single bit. 62 class reference { 63 SmallBitVector &TheVector; 64 unsigned BitPos; 65 66 public: reference(SmallBitVector & b,unsigned Idx)67 reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 68 69 reference(const reference&) = default; 70 71 reference& operator=(reference t) { 72 *this = bool(t); 73 return *this; 74 } 75 76 reference& operator=(bool t) { 77 if (t) 78 TheVector.set(BitPos); 79 else 80 TheVector.reset(BitPos); 81 return *this; 82 } 83 84 operator bool() const { 85 return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 86 } 87 }; 88 89 private: isSmall()90 bool isSmall() const { 91 return X & uintptr_t(1); 92 } 93 getPointer()94 BitVector *getPointer() const { 95 assert(!isSmall()); 96 return reinterpret_cast<BitVector *>(X); 97 } 98 switchToSmall(uintptr_t NewSmallBits,size_t NewSize)99 void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 100 X = 1; 101 setSmallSize(NewSize); 102 setSmallBits(NewSmallBits); 103 } 104 switchToLarge(BitVector * BV)105 void switchToLarge(BitVector *BV) { 106 X = reinterpret_cast<uintptr_t>(BV); 107 assert(!isSmall() && "Tried to use an unaligned pointer"); 108 } 109 110 // Return all the bits used for the "small" representation; this includes 111 // bits for the size as well as the element bits. getSmallRawBits()112 uintptr_t getSmallRawBits() const { 113 assert(isSmall()); 114 return X >> 1; 115 } 116 setSmallRawBits(uintptr_t NewRawBits)117 void setSmallRawBits(uintptr_t NewRawBits) { 118 assert(isSmall()); 119 X = (NewRawBits << 1) | uintptr_t(1); 120 } 121 122 // Return the size. getSmallSize()123 size_t getSmallSize() const { 124 return getSmallRawBits() >> SmallNumDataBits; 125 } 126 setSmallSize(size_t Size)127 void setSmallSize(size_t Size) { 128 setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 129 } 130 131 // Return the element bits. getSmallBits()132 uintptr_t getSmallBits() const { 133 return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 134 } 135 setSmallBits(uintptr_t NewBits)136 void setSmallBits(uintptr_t NewBits) { 137 setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 138 (getSmallSize() << SmallNumDataBits)); 139 } 140 141 public: 142 /// SmallBitVector default ctor - Creates an empty bitvector. SmallBitVector()143 SmallBitVector() : X(1) {} 144 145 /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 146 /// bits are initialized to the specified value. 147 explicit SmallBitVector(unsigned s, bool t = false) { 148 if (s <= SmallNumDataBits) 149 switchToSmall(t ? ~uintptr_t(0) : 0, s); 150 else 151 switchToLarge(new BitVector(s, t)); 152 } 153 154 /// SmallBitVector copy ctor. SmallBitVector(const SmallBitVector & RHS)155 SmallBitVector(const SmallBitVector &RHS) { 156 if (RHS.isSmall()) 157 X = RHS.X; 158 else 159 switchToLarge(new BitVector(*RHS.getPointer())); 160 } 161 SmallBitVector(SmallBitVector && RHS)162 SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 163 RHS.X = 1; 164 } 165 ~SmallBitVector()166 ~SmallBitVector() { 167 if (!isSmall()) 168 delete getPointer(); 169 } 170 171 /// empty - Tests whether there are no bits in this bitvector. empty()172 bool empty() const { 173 return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 174 } 175 176 /// size - Returns the number of bits in this bitvector. size()177 size_t size() const { 178 return isSmall() ? getSmallSize() : getPointer()->size(); 179 } 180 181 /// count - Returns the number of bits which are set. count()182 size_type count() const { 183 if (isSmall()) { 184 uintptr_t Bits = getSmallBits(); 185 return countPopulation(Bits); 186 } 187 return getPointer()->count(); 188 } 189 190 /// any - Returns true if any bit is set. any()191 bool any() const { 192 if (isSmall()) 193 return getSmallBits() != 0; 194 return getPointer()->any(); 195 } 196 197 /// all - Returns true if all bits are set. all()198 bool all() const { 199 if (isSmall()) 200 return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 201 return getPointer()->all(); 202 } 203 204 /// none - Returns true if none of the bits are set. none()205 bool none() const { 206 if (isSmall()) 207 return getSmallBits() == 0; 208 return getPointer()->none(); 209 } 210 211 /// find_first - Returns the index of the first set bit, -1 if none 212 /// of the bits are set. find_first()213 int find_first() const { 214 if (isSmall()) { 215 uintptr_t Bits = getSmallBits(); 216 if (Bits == 0) 217 return -1; 218 return countTrailingZeros(Bits); 219 } 220 return getPointer()->find_first(); 221 } 222 223 /// find_next - Returns the index of the next set bit following the 224 /// "Prev" bit. Returns -1 if the next set bit is not found. find_next(unsigned Prev)225 int find_next(unsigned Prev) const { 226 if (isSmall()) { 227 uintptr_t Bits = getSmallBits(); 228 // Mask off previous bits. 229 Bits &= ~uintptr_t(0) << (Prev + 1); 230 if (Bits == 0 || Prev + 1 >= getSmallSize()) 231 return -1; 232 return countTrailingZeros(Bits); 233 } 234 return getPointer()->find_next(Prev); 235 } 236 237 /// clear - Clear all bits. clear()238 void clear() { 239 if (!isSmall()) 240 delete getPointer(); 241 switchToSmall(0, 0); 242 } 243 244 /// resize - Grow or shrink the bitvector. 245 void resize(unsigned N, bool t = false) { 246 if (!isSmall()) { 247 getPointer()->resize(N, t); 248 } else if (SmallNumDataBits >= N) { 249 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 250 setSmallSize(N); 251 setSmallBits(NewBits | getSmallBits()); 252 } else { 253 BitVector *BV = new BitVector(N, t); 254 uintptr_t OldBits = getSmallBits(); 255 for (size_t i = 0, e = getSmallSize(); i != e; ++i) 256 (*BV)[i] = (OldBits >> i) & 1; 257 switchToLarge(BV); 258 } 259 } 260 reserve(unsigned N)261 void reserve(unsigned N) { 262 if (isSmall()) { 263 if (N > SmallNumDataBits) { 264 uintptr_t OldBits = getSmallRawBits(); 265 size_t SmallSize = getSmallSize(); 266 BitVector *BV = new BitVector(SmallSize); 267 for (size_t i = 0; i < SmallSize; ++i) 268 if ((OldBits >> i) & 1) 269 BV->set(i); 270 BV->reserve(N); 271 switchToLarge(BV); 272 } 273 } else { 274 getPointer()->reserve(N); 275 } 276 } 277 278 // Set, reset, flip set()279 SmallBitVector &set() { 280 if (isSmall()) 281 setSmallBits(~uintptr_t(0)); 282 else 283 getPointer()->set(); 284 return *this; 285 } 286 set(unsigned Idx)287 SmallBitVector &set(unsigned Idx) { 288 if (isSmall()) { 289 assert(Idx <= static_cast<unsigned>( 290 std::numeric_limits<uintptr_t>::digits) && 291 "undefined behavior"); 292 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 293 } 294 else 295 getPointer()->set(Idx); 296 return *this; 297 } 298 299 /// set - Efficiently set a range of bits in [I, E) set(unsigned I,unsigned E)300 SmallBitVector &set(unsigned I, unsigned E) { 301 assert(I <= E && "Attempted to set backwards range!"); 302 assert(E <= size() && "Attempted to set out-of-bounds range!"); 303 if (I == E) return *this; 304 if (isSmall()) { 305 uintptr_t EMask = ((uintptr_t)1) << E; 306 uintptr_t IMask = ((uintptr_t)1) << I; 307 uintptr_t Mask = EMask - IMask; 308 setSmallBits(getSmallBits() | Mask); 309 } else 310 getPointer()->set(I, E); 311 return *this; 312 } 313 reset()314 SmallBitVector &reset() { 315 if (isSmall()) 316 setSmallBits(0); 317 else 318 getPointer()->reset(); 319 return *this; 320 } 321 reset(unsigned Idx)322 SmallBitVector &reset(unsigned Idx) { 323 if (isSmall()) 324 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 325 else 326 getPointer()->reset(Idx); 327 return *this; 328 } 329 330 /// reset - Efficiently reset a range of bits in [I, E) reset(unsigned I,unsigned E)331 SmallBitVector &reset(unsigned I, unsigned E) { 332 assert(I <= E && "Attempted to reset backwards range!"); 333 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 334 if (I == E) return *this; 335 if (isSmall()) { 336 uintptr_t EMask = ((uintptr_t)1) << E; 337 uintptr_t IMask = ((uintptr_t)1) << I; 338 uintptr_t Mask = EMask - IMask; 339 setSmallBits(getSmallBits() & ~Mask); 340 } else 341 getPointer()->reset(I, E); 342 return *this; 343 } 344 flip()345 SmallBitVector &flip() { 346 if (isSmall()) 347 setSmallBits(~getSmallBits()); 348 else 349 getPointer()->flip(); 350 return *this; 351 } 352 flip(unsigned Idx)353 SmallBitVector &flip(unsigned Idx) { 354 if (isSmall()) 355 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 356 else 357 getPointer()->flip(Idx); 358 return *this; 359 } 360 361 // No argument flip. 362 SmallBitVector operator~() const { 363 return SmallBitVector(*this).flip(); 364 } 365 366 // Indexing. 367 reference operator[](unsigned Idx) { 368 assert(Idx < size() && "Out-of-bounds Bit access."); 369 return reference(*this, Idx); 370 } 371 372 bool operator[](unsigned Idx) const { 373 assert(Idx < size() && "Out-of-bounds Bit access."); 374 if (isSmall()) 375 return ((getSmallBits() >> Idx) & 1) != 0; 376 return getPointer()->operator[](Idx); 377 } 378 test(unsigned Idx)379 bool test(unsigned Idx) const { 380 return (*this)[Idx]; 381 } 382 383 /// Test if any common bits are set. anyCommon(const SmallBitVector & RHS)384 bool anyCommon(const SmallBitVector &RHS) const { 385 if (isSmall() && RHS.isSmall()) 386 return (getSmallBits() & RHS.getSmallBits()) != 0; 387 if (!isSmall() && !RHS.isSmall()) 388 return getPointer()->anyCommon(*RHS.getPointer()); 389 390 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 391 if (test(i) && RHS.test(i)) 392 return true; 393 return false; 394 } 395 396 // Comparison operators. 397 bool operator==(const SmallBitVector &RHS) const { 398 if (size() != RHS.size()) 399 return false; 400 if (isSmall()) 401 return getSmallBits() == RHS.getSmallBits(); 402 else 403 return *getPointer() == *RHS.getPointer(); 404 } 405 406 bool operator!=(const SmallBitVector &RHS) const { 407 return !(*this == RHS); 408 } 409 410 // Intersection, union, disjoint union. 411 SmallBitVector &operator&=(const SmallBitVector &RHS) { 412 resize(std::max(size(), RHS.size())); 413 if (isSmall()) 414 setSmallBits(getSmallBits() & RHS.getSmallBits()); 415 else if (!RHS.isSmall()) 416 getPointer()->operator&=(*RHS.getPointer()); 417 else { 418 SmallBitVector Copy = RHS; 419 Copy.resize(size()); 420 getPointer()->operator&=(*Copy.getPointer()); 421 } 422 return *this; 423 } 424 425 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. reset(const SmallBitVector & RHS)426 SmallBitVector &reset(const SmallBitVector &RHS) { 427 if (isSmall() && RHS.isSmall()) 428 setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 429 else if (!isSmall() && !RHS.isSmall()) 430 getPointer()->reset(*RHS.getPointer()); 431 else 432 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 433 if (RHS.test(i)) 434 reset(i); 435 436 return *this; 437 } 438 439 /// test - Check if (This - RHS) is zero. 440 /// This is the same as reset(RHS) and any(). test(const SmallBitVector & RHS)441 bool test(const SmallBitVector &RHS) const { 442 if (isSmall() && RHS.isSmall()) 443 return (getSmallBits() & ~RHS.getSmallBits()) != 0; 444 if (!isSmall() && !RHS.isSmall()) 445 return getPointer()->test(*RHS.getPointer()); 446 447 unsigned i, e; 448 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 449 if (test(i) && !RHS.test(i)) 450 return true; 451 452 for (e = size(); i != e; ++i) 453 if (test(i)) 454 return true; 455 456 return false; 457 } 458 459 SmallBitVector &operator|=(const SmallBitVector &RHS) { 460 resize(std::max(size(), RHS.size())); 461 if (isSmall()) 462 setSmallBits(getSmallBits() | RHS.getSmallBits()); 463 else if (!RHS.isSmall()) 464 getPointer()->operator|=(*RHS.getPointer()); 465 else { 466 SmallBitVector Copy = RHS; 467 Copy.resize(size()); 468 getPointer()->operator|=(*Copy.getPointer()); 469 } 470 return *this; 471 } 472 473 SmallBitVector &operator^=(const SmallBitVector &RHS) { 474 resize(std::max(size(), RHS.size())); 475 if (isSmall()) 476 setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 477 else if (!RHS.isSmall()) 478 getPointer()->operator^=(*RHS.getPointer()); 479 else { 480 SmallBitVector Copy = RHS; 481 Copy.resize(size()); 482 getPointer()->operator^=(*Copy.getPointer()); 483 } 484 return *this; 485 } 486 487 // Assignment operator. 488 const SmallBitVector &operator=(const SmallBitVector &RHS) { 489 if (isSmall()) { 490 if (RHS.isSmall()) 491 X = RHS.X; 492 else 493 switchToLarge(new BitVector(*RHS.getPointer())); 494 } else { 495 if (!RHS.isSmall()) 496 *getPointer() = *RHS.getPointer(); 497 else { 498 delete getPointer(); 499 X = RHS.X; 500 } 501 } 502 return *this; 503 } 504 505 const SmallBitVector &operator=(SmallBitVector &&RHS) { 506 if (this != &RHS) { 507 clear(); 508 swap(RHS); 509 } 510 return *this; 511 } 512 swap(SmallBitVector & RHS)513 void swap(SmallBitVector &RHS) { 514 std::swap(X, RHS.X); 515 } 516 517 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 518 /// This computes "*this |= Mask". 519 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 520 if (isSmall()) 521 applyMask<true, false>(Mask, MaskWords); 522 else 523 getPointer()->setBitsInMask(Mask, MaskWords); 524 } 525 526 /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 527 /// Don't resize. This computes "*this &= ~Mask". 528 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 529 if (isSmall()) 530 applyMask<false, false>(Mask, MaskWords); 531 else 532 getPointer()->clearBitsInMask(Mask, MaskWords); 533 } 534 535 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 536 /// Don't resize. This computes "*this |= ~Mask". 537 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 538 if (isSmall()) 539 applyMask<true, true>(Mask, MaskWords); 540 else 541 getPointer()->setBitsNotInMask(Mask, MaskWords); 542 } 543 544 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 545 /// Don't resize. This computes "*this &= Mask". 546 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 547 if (isSmall()) 548 applyMask<false, true>(Mask, MaskWords); 549 else 550 getPointer()->clearBitsNotInMask(Mask, MaskWords); 551 } 552 553 private: 554 template <bool AddBits, bool InvertMask> applyMask(const uint32_t * Mask,unsigned MaskWords)555 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 556 assert(MaskWords <= sizeof(uintptr_t) && "Mask is larger than base!"); 557 uintptr_t M = Mask[0]; 558 if (NumBaseBits == 64) 559 M |= uint64_t(Mask[1]) << 32; 560 if (InvertMask) 561 M = ~M; 562 if (AddBits) 563 setSmallBits(getSmallBits() | M); 564 else 565 setSmallBits(getSmallBits() & ~M); 566 } 567 }; 568 569 inline SmallBitVector 570 operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 571 SmallBitVector Result(LHS); 572 Result &= RHS; 573 return Result; 574 } 575 576 inline SmallBitVector 577 operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 578 SmallBitVector Result(LHS); 579 Result |= RHS; 580 return Result; 581 } 582 583 inline SmallBitVector 584 operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 585 SmallBitVector Result(LHS); 586 Result ^= RHS; 587 return Result; 588 } 589 590 } // End llvm namespace 591 592 namespace std { 593 /// Implement std::swap in terms of BitVector swap. 594 inline void swap(llvm::SmallBitVector & LHS,llvm::SmallBitVector & RHS)595 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 596 LHS.swap(RHS); 597 } 598 } 599 600 #endif 601