1356290Sjkim//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 2290207Sjkim// 3290207Sjkim// The LLVM Compiler Infrastructure 4290207Sjkim// 5290207Sjkim// This file is distributed under the University of Illinois Open Source 6290207Sjkim// License. See LICENSE.TXT for details. 7290207Sjkim// 8290207Sjkim//===----------------------------------------------------------------------===// 9290207Sjkim// 10290207Sjkim// This file implements the SmallBitVector class. 11290207Sjkim// 12290207Sjkim//===----------------------------------------------------------------------===// 13290207Sjkim 14290207Sjkim#ifndef LLVM_ADT_SMALLBITVECTOR_H 15290207Sjkim#define LLVM_ADT_SMALLBITVECTOR_H 16290207Sjkim 17290207Sjkim#include "llvm/ADT/BitVector.h" 18290207Sjkim#include "llvm/Support/Compiler.h" 19290207Sjkim#include "llvm/Support/MathExtras.h" 20290207Sjkim#include <cassert> 21290207Sjkim 22290207Sjkimnamespace llvm { 23290207Sjkim 24290207Sjkim/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 25290207Sjkim/// optimized for the case when the array is small. It contains one 26290207Sjkim/// pointer-sized field, which is directly used as a plain collection of bits 27290207Sjkim/// when possible, or as a pointer to a larger heap-allocated array when 28290207Sjkim/// necessary. This allows normal "small" cases to be fast without losing 29290207Sjkim/// generality for large inputs. 30290207Sjkim/// 31290207Sjkimclass SmallBitVector { 32290207Sjkim // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 33290207Sjkim // unnecessary level of indirection. It would be more efficient to use a 34290207Sjkim // pointer to memory containing size, allocation size, and the array of bits. 35290207Sjkim uintptr_t X; 36290207Sjkim 37290207Sjkim enum { 38290207Sjkim // The number of bits in this class. 39290207Sjkim NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 40290207Sjkim 41290207Sjkim // One bit is used to discriminate between small and large mode. The 42290207Sjkim // remaining bits are used for the small-mode representation. 43290207Sjkim SmallNumRawBits = NumBaseBits - 1, 44290207Sjkim 45290207Sjkim // A few more bits are used to store the size of the bit set in small mode. 46290207Sjkim // Theoretically this is a ceil-log2. These bits are encoded in the most 47290207Sjkim // significant bits of the raw bits. 48290207Sjkim SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 49312826Sjkim NumBaseBits == 64 ? 6 : 50290207Sjkim SmallNumRawBits), 51290207Sjkim 52290207Sjkim // The remaining bits are used to store the actual set in small mode. 53290207Sjkim SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 54290207Sjkim }; 55290207Sjkim 56290207Sjkimpublic: 57344604Sjkim // Encapsulation of a single bit. 58344604Sjkim class reference { 59344604Sjkim SmallBitVector &TheVector; 60344604Sjkim unsigned BitPos; 61344604Sjkim 62344604Sjkim public: 63290207Sjkim reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 64344604Sjkim 65344604Sjkim reference& operator=(reference t) { 66344604Sjkim *this = bool(t); 67344604Sjkim return *this; 68290207Sjkim } 69290207Sjkim 70344604Sjkim reference& operator=(bool t) { 71290207Sjkim if (t) 72290207Sjkim TheVector.set(BitPos); 73290207Sjkim else 74290207Sjkim TheVector.reset(BitPos); 75290207Sjkim return *this; 76290207Sjkim } 77290207Sjkim 78290207Sjkim operator bool() const { 79290207Sjkim return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 80290207Sjkim } 81290207Sjkim }; 82290207Sjkim 83290207Sjkimprivate: 84290207Sjkim bool isSmall() const { 85290207Sjkim return X & uintptr_t(1); 86290207Sjkim } 87290207Sjkim 88290207Sjkim BitVector *getPointer() const { 89290207Sjkim assert(!isSmall()); 90290207Sjkim return reinterpret_cast<BitVector *>(X); 91290207Sjkim } 92290207Sjkim 93290207Sjkim void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 94290207Sjkim X = 1; 95290207Sjkim setSmallSize(NewSize); 96290207Sjkim setSmallBits(NewSmallBits); 97290207Sjkim } 98290207Sjkim 99290207Sjkim void switchToLarge(BitVector *BV) { 100290207Sjkim X = reinterpret_cast<uintptr_t>(BV); 101290207Sjkim assert(!isSmall() && "Tried to use an unaligned pointer"); 102290207Sjkim } 103290207Sjkim 104290207Sjkim // Return all the bits used for the "small" representation; this includes 105290207Sjkim // bits for the size as well as the element bits. 106290207Sjkim uintptr_t getSmallRawBits() const { 107290207Sjkim assert(isSmall()); 108290207Sjkim return X >> 1; 109290207Sjkim } 110290207Sjkim 111290207Sjkim void setSmallRawBits(uintptr_t NewRawBits) { 112290207Sjkim assert(isSmall()); 113290207Sjkim X = (NewRawBits << 1) | uintptr_t(1); 114290207Sjkim } 115290207Sjkim 116290207Sjkim // Return the size. 117290207Sjkim size_t getSmallSize() const { 118290207Sjkim return getSmallRawBits() >> SmallNumDataBits; 119290207Sjkim } 120290207Sjkim 121290207Sjkim void setSmallSize(size_t Size) { 122290207Sjkim setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 123290207Sjkim } 124290207Sjkim 125290207Sjkim // Return the element bits. 126290207Sjkim uintptr_t getSmallBits() const { 127290207Sjkim return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 128290207Sjkim } 129290207Sjkim 130290207Sjkim void setSmallBits(uintptr_t NewBits) { 131290207Sjkim setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 132290207Sjkim (getSmallSize() << SmallNumDataBits)); 133290207Sjkim } 134290207Sjkim 135290207Sjkimpublic: 136356290Sjkim /// SmallBitVector default ctor - Creates an empty bitvector. 137290207Sjkim SmallBitVector() : X(1) {} 138290207Sjkim 139290207Sjkim /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 140290207Sjkim /// bits are initialized to the specified value. 141290207Sjkim explicit SmallBitVector(unsigned s, bool t = false) { 142290207Sjkim if (s <= SmallNumDataBits) 143290207Sjkim switchToSmall(t ? ~uintptr_t(0) : 0, s); 144290207Sjkim else 145290207Sjkim switchToLarge(new BitVector(s, t)); 146290207Sjkim } 147290207Sjkim 148290207Sjkim /// SmallBitVector copy ctor. 149290207Sjkim SmallBitVector(const SmallBitVector &RHS) { 150290207Sjkim if (RHS.isSmall()) 151290207Sjkim X = RHS.X; 152290207Sjkim else 153290207Sjkim switchToLarge(new BitVector(*RHS.getPointer())); 154290207Sjkim } 155344604Sjkim 156290207Sjkim#if LLVM_HAS_RVALUE_REFERENCES 157290207Sjkim SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 158344604Sjkim RHS.X = 1; 159290207Sjkim } 160344604Sjkim#endif 161290207Sjkim 162290207Sjkim ~SmallBitVector() { 163290207Sjkim if (!isSmall()) 164290207Sjkim delete getPointer(); 165290207Sjkim } 166290207Sjkim 167344604Sjkim /// empty - Tests whether there are no bits in this bitvector. 168290207Sjkim bool empty() const { 169344604Sjkim return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 170344604Sjkim } 171290207Sjkim 172290207Sjkim /// size - Returns the number of bits in this bitvector. 173290207Sjkim size_t size() const { 174344604Sjkim return isSmall() ? getSmallSize() : getPointer()->size(); 175344604Sjkim } 176290207Sjkim 177344604Sjkim /// count - Returns the number of bits which are set. 178290207Sjkim unsigned count() const { 179344604Sjkim if (isSmall()) { 180290207Sjkim uintptr_t Bits = getSmallBits(); 181290207Sjkim if (NumBaseBits == 32) 182290207Sjkim return CountPopulation_32(Bits); 183290207Sjkim if (NumBaseBits == 64) 184290207Sjkim return CountPopulation_64(Bits); 185290207Sjkim llvm_unreachable("Unsupported!"); 186290207Sjkim } 187290207Sjkim return getPointer()->count(); 188290207Sjkim } 189290207Sjkim 190290207Sjkim /// any - Returns true if any bit is set. 191290207Sjkim bool any() const { 192290207Sjkim if (isSmall()) 193290207Sjkim return getSmallBits() != 0; 194290207Sjkim return getPointer()->any(); 195290207Sjkim } 196290207Sjkim 197290207Sjkim /// all - Returns true if all bits are set. 198344604Sjkim bool all() const { 199344604Sjkim if (isSmall()) 200344604Sjkim return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 201344604Sjkim return getPointer()->all(); 202 } 203 204 /// none - Returns true if none of the bits are set. 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. 213 int find_first() const { 214 if (isSmall()) { 215 uintptr_t Bits = getSmallBits(); 216 if (Bits == 0) 217 return -1; 218 if (NumBaseBits == 32) 219 return countTrailingZeros(Bits); 220 if (NumBaseBits == 64) 221 return countTrailingZeros(Bits); 222 llvm_unreachable("Unsupported!"); 223 } 224 return getPointer()->find_first(); 225 } 226 227 /// find_next - Returns the index of the next set bit following the 228 /// "Prev" bit. Returns -1 if the next set bit is not found. 229 int find_next(unsigned Prev) const { 230 if (isSmall()) { 231 uintptr_t Bits = getSmallBits(); 232 // Mask off previous bits. 233 Bits &= ~uintptr_t(0) << (Prev + 1); 234 if (Bits == 0 || Prev + 1 >= getSmallSize()) 235 return -1; 236 if (NumBaseBits == 32) 237 return countTrailingZeros(Bits); 238 if (NumBaseBits == 64) 239 return countTrailingZeros(Bits); 240 llvm_unreachable("Unsupported!"); 241 } 242 return getPointer()->find_next(Prev); 243 } 244 245 /// clear - Clear all bits. 246 void clear() { 247 if (!isSmall()) 248 delete getPointer(); 249 switchToSmall(0, 0); 250 } 251 252 /// resize - Grow or shrink the bitvector. 253 void resize(unsigned N, bool t = false) { 254 if (!isSmall()) { 255 getPointer()->resize(N, t); 256 } else if (SmallNumDataBits >= N) { 257 uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 258 setSmallSize(N); 259 setSmallBits(NewBits | getSmallBits()); 260 } else { 261 BitVector *BV = new BitVector(N, t); 262 uintptr_t OldBits = getSmallBits(); 263 for (size_t i = 0, e = getSmallSize(); i != e; ++i) 264 (*BV)[i] = (OldBits >> i) & 1; 265 switchToLarge(BV); 266 } 267 } 268 269 void reserve(unsigned N) { 270 if (isSmall()) { 271 if (N > SmallNumDataBits) { 272 uintptr_t OldBits = getSmallRawBits(); 273 size_t SmallSize = getSmallSize(); 274 BitVector *BV = new BitVector(SmallSize); 275 for (size_t i = 0; i < SmallSize; ++i) 276 if ((OldBits >> i) & 1) 277 BV->set(i); 278 BV->reserve(N); 279 switchToLarge(BV); 280 } 281 } else { 282 getPointer()->reserve(N); 283 } 284 } 285 286 // Set, reset, flip 287 SmallBitVector &set() { 288 if (isSmall()) 289 setSmallBits(~uintptr_t(0)); 290 else 291 getPointer()->set(); 292 return *this; 293 } 294 295 SmallBitVector &set(unsigned Idx) { 296 if (isSmall()) 297 setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 298 else 299 getPointer()->set(Idx); 300 return *this; 301 } 302 303 /// set - Efficiently set a range of bits in [I, E) 304 SmallBitVector &set(unsigned I, unsigned E) { 305 assert(I <= E && "Attempted to set backwards range!"); 306 assert(E <= size() && "Attempted to set out-of-bounds range!"); 307 if (I == E) return *this; 308 if (isSmall()) { 309 uintptr_t EMask = ((uintptr_t)1) << E; 310 uintptr_t IMask = ((uintptr_t)1) << I; 311 uintptr_t Mask = EMask - IMask; 312 setSmallBits(getSmallBits() | Mask); 313 } else 314 getPointer()->set(I, E); 315 return *this; 316 } 317 318 SmallBitVector &reset() { 319 if (isSmall()) 320 setSmallBits(0); 321 else 322 getPointer()->reset(); 323 return *this; 324 } 325 326 SmallBitVector &reset(unsigned Idx) { 327 if (isSmall()) 328 setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 329 else 330 getPointer()->reset(Idx); 331 return *this; 332 } 333 334 /// reset - Efficiently reset a range of bits in [I, E) 335 SmallBitVector &reset(unsigned I, unsigned E) { 336 assert(I <= E && "Attempted to reset backwards range!"); 337 assert(E <= size() && "Attempted to reset out-of-bounds range!"); 338 if (I == E) return *this; 339 if (isSmall()) { 340 uintptr_t EMask = ((uintptr_t)1) << E; 341 uintptr_t IMask = ((uintptr_t)1) << I; 342 uintptr_t Mask = EMask - IMask; 343 setSmallBits(getSmallBits() & ~Mask); 344 } else 345 getPointer()->reset(I, E); 346 return *this; 347 } 348 349 SmallBitVector &flip() { 350 if (isSmall()) 351 setSmallBits(~getSmallBits()); 352 else 353 getPointer()->flip(); 354 return *this; 355 } 356 357 SmallBitVector &flip(unsigned Idx) { 358 if (isSmall()) 359 setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 360 else 361 getPointer()->flip(Idx); 362 return *this; 363 } 364 365 // No argument flip. 366 SmallBitVector operator~() const { 367 return SmallBitVector(*this).flip(); 368 } 369 370 // Indexing. 371 reference operator[](unsigned Idx) { 372 assert(Idx < size() && "Out-of-bounds Bit access."); 373 return reference(*this, Idx); 374 } 375 376 bool operator[](unsigned Idx) const { 377 assert(Idx < size() && "Out-of-bounds Bit access."); 378 if (isSmall()) 379 return ((getSmallBits() >> Idx) & 1) != 0; 380 return getPointer()->operator[](Idx); 381 } 382 383 bool test(unsigned Idx) const { 384 return (*this)[Idx]; 385 } 386 387 /// Test if any common bits are set. 388 bool anyCommon(const SmallBitVector &RHS) const { 389 if (isSmall() && RHS.isSmall()) 390 return (getSmallBits() & RHS.getSmallBits()) != 0; 391 if (!isSmall() && !RHS.isSmall()) 392 return getPointer()->anyCommon(*RHS.getPointer()); 393 394 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 395 if (test(i) && RHS.test(i)) 396 return true; 397 return false; 398 } 399 400 // Comparison operators. 401 bool operator==(const SmallBitVector &RHS) const { 402 if (size() != RHS.size()) 403 return false; 404 if (isSmall()) 405 return getSmallBits() == RHS.getSmallBits(); 406 else 407 return *getPointer() == *RHS.getPointer(); 408 } 409 410 bool operator!=(const SmallBitVector &RHS) const { 411 return !(*this == RHS); 412 } 413 414 // Intersection, union, disjoint union. 415 SmallBitVector &operator&=(const SmallBitVector &RHS) { 416 resize(std::max(size(), RHS.size())); 417 if (isSmall()) 418 setSmallBits(getSmallBits() & RHS.getSmallBits()); 419 else if (!RHS.isSmall()) 420 getPointer()->operator&=(*RHS.getPointer()); 421 else { 422 SmallBitVector Copy = RHS; 423 Copy.resize(size()); 424 getPointer()->operator&=(*Copy.getPointer()); 425 } 426 return *this; 427 } 428 429 /// reset - Reset bits that are set in RHS. Same as *this &= ~RHS. 430 SmallBitVector &reset(const SmallBitVector &RHS) { 431 if (isSmall() && RHS.isSmall()) 432 setSmallBits(getSmallBits() & ~RHS.getSmallBits()); 433 else if (!isSmall() && !RHS.isSmall()) 434 getPointer()->reset(*RHS.getPointer()); 435 else 436 for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 437 if (RHS.test(i)) 438 reset(i); 439 440 return *this; 441 } 442 443 /// test - Check if (This - RHS) is zero. 444 /// This is the same as reset(RHS) and any(). 445 bool test(const SmallBitVector &RHS) const { 446 if (isSmall() && RHS.isSmall()) 447 return (getSmallBits() & ~RHS.getSmallBits()) != 0; 448 if (!isSmall() && !RHS.isSmall()) 449 return getPointer()->test(*RHS.getPointer()); 450 451 unsigned i, e; 452 for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 453 if (test(i) && !RHS.test(i)) 454 return true; 455 456 for (e = size(); i != e; ++i) 457 if (test(i)) 458 return true; 459 460 return false; 461 } 462 463 SmallBitVector &operator|=(const SmallBitVector &RHS) { 464 resize(std::max(size(), RHS.size())); 465 if (isSmall()) 466 setSmallBits(getSmallBits() | RHS.getSmallBits()); 467 else if (!RHS.isSmall()) 468 getPointer()->operator|=(*RHS.getPointer()); 469 else { 470 SmallBitVector Copy = RHS; 471 Copy.resize(size()); 472 getPointer()->operator|=(*Copy.getPointer()); 473 } 474 return *this; 475 } 476 477 SmallBitVector &operator^=(const SmallBitVector &RHS) { 478 resize(std::max(size(), RHS.size())); 479 if (isSmall()) 480 setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 481 else if (!RHS.isSmall()) 482 getPointer()->operator^=(*RHS.getPointer()); 483 else { 484 SmallBitVector Copy = RHS; 485 Copy.resize(size()); 486 getPointer()->operator^=(*Copy.getPointer()); 487 } 488 return *this; 489 } 490 491 // Assignment operator. 492 const SmallBitVector &operator=(const SmallBitVector &RHS) { 493 if (isSmall()) { 494 if (RHS.isSmall()) 495 X = RHS.X; 496 else 497 switchToLarge(new BitVector(*RHS.getPointer())); 498 } else { 499 if (!RHS.isSmall()) 500 *getPointer() = *RHS.getPointer(); 501 else { 502 delete getPointer(); 503 X = RHS.X; 504 } 505 } 506 return *this; 507 } 508 509#if LLVM_HAS_RVALUE_REFERENCES 510 const SmallBitVector &operator=(SmallBitVector &&RHS) { 511 if (this != &RHS) { 512 clear(); 513 swap(RHS); 514 } 515 return *this; 516 } 517#endif 518 519 void swap(SmallBitVector &RHS) { 520 std::swap(X, RHS.X); 521 } 522 523 /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 524 /// This computes "*this |= Mask". 525 void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 526 if (isSmall()) 527 applyMask<true, false>(Mask, MaskWords); 528 else 529 getPointer()->setBitsInMask(Mask, MaskWords); 530 } 531 532 /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 533 /// Don't resize. This computes "*this &= ~Mask". 534 void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 535 if (isSmall()) 536 applyMask<false, false>(Mask, MaskWords); 537 else 538 getPointer()->clearBitsInMask(Mask, MaskWords); 539 } 540 541 /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 542 /// Don't resize. This computes "*this |= ~Mask". 543 void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 544 if (isSmall()) 545 applyMask<true, true>(Mask, MaskWords); 546 else 547 getPointer()->setBitsNotInMask(Mask, MaskWords); 548 } 549 550 /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 551 /// Don't resize. This computes "*this &= Mask". 552 void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 553 if (isSmall()) 554 applyMask<false, true>(Mask, MaskWords); 555 else 556 getPointer()->clearBitsNotInMask(Mask, MaskWords); 557 } 558 559private: 560 template<bool AddBits, bool InvertMask> 561 void applyMask(const uint32_t *Mask, unsigned MaskWords) { 562 assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); 563 if (NumBaseBits == 64 && MaskWords >= 2) { 564 uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); 565 if (InvertMask) M = ~M; 566 if (AddBits) setSmallBits(getSmallBits() | M); 567 else setSmallBits(getSmallBits() & ~M); 568 } else { 569 uint32_t M = Mask[0]; 570 if (InvertMask) M = ~M; 571 if (AddBits) setSmallBits(getSmallBits() | M); 572 else setSmallBits(getSmallBits() & ~M); 573 } 574 } 575}; 576 577inline SmallBitVector 578operator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 579 SmallBitVector Result(LHS); 580 Result &= RHS; 581 return Result; 582} 583 584inline SmallBitVector 585operator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 586 SmallBitVector Result(LHS); 587 Result |= RHS; 588 return Result; 589} 590 591inline SmallBitVector 592operator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 593 SmallBitVector Result(LHS); 594 Result ^= RHS; 595 return Result; 596} 597 598} // End llvm namespace 599 600namespace std { 601 /// Implement std::swap in terms of BitVector swap. 602 inline void 603 swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 604 LHS.swap(RHS); 605 } 606} 607 608#endif 609