1cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===- llvm/ADT/SmallBitVector.h - 'Normally small' bit vectors -*- C++ -*-===// 2cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 3cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// The LLVM Compiler Infrastructure 4cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 5cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// This file is distributed under the University of Illinois Open Source 6cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// License. See LICENSE.TXT for details. 7cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 8cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===----------------------------------------------------------------------===// 9cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 10cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// This file implements the SmallBitVector class. 11cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman// 12cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman//===----------------------------------------------------------------------===// 13cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 14cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#ifndef LLVM_ADT_SMALLBITVECTOR_H 15cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#define LLVM_ADT_SMALLBITVECTOR_H 16cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 17cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include "llvm/ADT/BitVector.h" 18693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#include "llvm/Support/Compiler.h" 19cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include "llvm/Support/MathExtras.h" 20cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#include <cassert> 21cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 22cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace llvm { 23cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 24cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// SmallBitVector - This is a 'bitvector' (really, a variable-sized bit array), 25cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// optimized for the case when the array is small. It contains one 26cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// pointer-sized field, which is directly used as a plain collection of bits 27cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// when possible, or as a pointer to a larger heap-allocated array when 28cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// necessary. This allows normal "small" cases to be fast without losing 29cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// generality for large inputs. 30cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman/// 31cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanclass SmallBitVector { 32cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // TODO: In "large" mode, a pointer to a BitVector is used, leading to an 33cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // unnecessary level of indirection. It would be more efficient to use a 34cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // pointer to memory containing size, allocation size, and the array of bits. 351e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer uintptr_t X; 36cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 371e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer enum { 381e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // The number of bits in this class. 391e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer NumBaseBits = sizeof(uintptr_t) * CHAR_BIT, 40cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 411e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // One bit is used to discriminate between small and large mode. The 421e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // remaining bits are used for the small-mode representation. 431e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumRawBits = NumBaseBits - 1, 44cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 451e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // A few more bits are used to store the size of the bit set in small mode. 461e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // Theoretically this is a ceil-log2. These bits are encoded in the most 471e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // significant bits of the raw bits. 481e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumSizeBits = (NumBaseBits == 32 ? 5 : 491e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer NumBaseBits == 64 ? 6 : 501e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumRawBits), 51cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 521e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer // The remaining bits are used to store the actual set in small mode. 531e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits 541e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer }; 55cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 56b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramerpublic: 57b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer // Encapsulation of a single bit. 58b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer class reference { 59b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer SmallBitVector &TheVector; 60b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer unsigned BitPos; 61b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 62b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer public: 63b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {} 64b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 65b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference& operator=(reference t) { 66b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer *this = bool(t); 67b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return *this; 68b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 69b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 70b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference& operator=(bool t) { 71b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer if (t) 72b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer TheVector.set(BitPos); 73b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer else 74b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer TheVector.reset(BitPos); 75b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return *this; 76b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 77b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 78b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer operator bool() const { 79b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return const_cast<const SmallBitVector &>(TheVector).operator[](BitPos); 80b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 81b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer }; 82b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 83b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramerprivate: 84cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool isSmall() const { 851e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return X & uintptr_t(1); 861e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer } 871e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer 881e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer BitVector *getPointer() const { 891e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(!isSmall()); 901e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return reinterpret_cast<BitVector *>(X); 91cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 92cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 93cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) { 941e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer X = 1; 95cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallSize(NewSize); 96cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(NewSmallBits); 97cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 98cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 99cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void switchToLarge(BitVector *BV) { 1001e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer X = reinterpret_cast<uintptr_t>(BV); 1011e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(!isSmall() && "Tried to use an unaligned pointer"); 102cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 103cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 104cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return all the bits used for the "small" representation; this includes 105cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // bits for the size as well as the element bits. 106cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t getSmallRawBits() const { 1071e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(isSmall()); 1081e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return X >> 1; 109cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 110cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 111cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallRawBits(uintptr_t NewRawBits) { 1121e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer assert(isSmall()); 113b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer X = (NewRawBits << 1) | uintptr_t(1); 114cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 115cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 116cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return the size. 117cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t getSmallSize() const { 118cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallRawBits() >> SmallNumDataBits; 119cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 120cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 121cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallSize(size_t Size) { 122cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits)); 123cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 124cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 125cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Return the element bits. 126cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t getSmallBits() const { 1271e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize()); 128cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 129cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 130cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void setSmallBits(uintptr_t NewBits) { 131b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer setSmallRawBits((NewBits & ~(~uintptr_t(0) << getSmallSize())) | 1321e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer (getSmallSize() << SmallNumDataBits)); 133cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 134cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 135cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanpublic: 136cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector default ctor - Creates an empty bitvector. 1371e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer SmallBitVector() : X(1) {} 138cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 139cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector ctor - Creates a bitvector of specified number of bits. All 140cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// bits are initialized to the specified value. 1411e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer explicit SmallBitVector(unsigned s, bool t = false) { 1421e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer if (s <= SmallNumDataBits) 143cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToSmall(t ? ~uintptr_t(0) : 0, s); 144cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 145cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(new BitVector(s, t)); 146cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 147cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 148cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// SmallBitVector copy ctor. 149cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector(const SmallBitVector &RHS) { 150cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (RHS.isSmall()) 151cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 152cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 1531e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer switchToLarge(new BitVector(*RHS.getPointer())); 154cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 155cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 1564334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 157693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer SmallBitVector(SmallBitVector &&RHS) : X(RHS.X) { 158693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer RHS.X = 1; 159693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 160693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#endif 161693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 162cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman ~SmallBitVector() { 163cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) 1641e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 165cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 166cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 167cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// empty - Tests whether there are no bits in this bitvector. 168cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool empty() const { 1691e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return isSmall() ? getSmallSize() == 0 : getPointer()->empty(); 170cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 171cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 172cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// size - Returns the number of bits in this bitvector. 173cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t size() const { 1741e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return isSmall() ? getSmallSize() : getPointer()->size(); 175cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 176cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 177cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// count - Returns the number of bits which are set. 178cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman unsigned count() const { 179cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 180cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 181d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 182cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return CountPopulation_32(Bits); 183d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 184cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return CountPopulation_64(Bits); 18550bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 186cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 1871e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->count(); 188cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 189cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 190cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// any - Returns true if any bit is set. 191cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool any() const { 192cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 193cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() != 0; 1941e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->any(); 195cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 196cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 197fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman /// all - Returns true if all bits are set. 198fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman bool all() const { 199fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman if (isSmall()) 200fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman return getSmallBits() == (uintptr_t(1) << getSmallSize()) - 1; 201fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman return getPointer()->all(); 202fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman } 203fab4c9e9df1aeb33b55cfcfa174fac8d61df96fdDan Gohman 204cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// none - Returns true if none of the bits are set. 205cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool none() const { 206cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 207cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() == 0; 2081e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->none(); 209cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 210cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 211cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// find_first - Returns the index of the first set bit, -1 if none 212cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// of the bits are set. 213cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman int find_first() const { 214cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 215cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 2166340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer if (Bits == 0) 2176340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return -1; 218d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 2196340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return CountTrailingZeros_32(Bits); 220d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 2216340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return CountTrailingZeros_64(Bits); 22250bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 223cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 2241e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->find_first(); 225cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 226cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 227cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// find_next - Returns the index of the next set bit following the 228cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// "Prev" bit. Returns -1 if the next set bit is not found. 229cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman int find_next(unsigned Prev) const { 230cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 231cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t Bits = getSmallBits(); 232cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Mask off previous bits. 2331e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer Bits &= ~uintptr_t(0) << (Prev + 1); 2346340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer if (Bits == 0 || Prev + 1 >= getSmallSize()) 2356340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return -1; 236d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 32) 2376340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return CountTrailingZeros_32(Bits); 238d455d4f4576059606823920150e0fc89a73412e1Craig Topper if (NumBaseBits == 64) 2396340722d1751841a00e791a44d8f2f5e481b8c61Benjamin Kramer return CountTrailingZeros_64(Bits); 24050bee42b54cd9aec5f49566307df2b0cf23afcf6Craig Topper llvm_unreachable("Unsupported!"); 241cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 2421e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->find_next(Prev); 243cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 244cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 245cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// clear - Clear all bits. 246cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void clear() { 247cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) 2481e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 249cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToSmall(0, 0); 250cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 251cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 252cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// resize - Grow or shrink the bitvector. 253cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void resize(unsigned N, bool t = false) { 254cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!isSmall()) { 2551e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->resize(N, t); 2561e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer } else if (SmallNumDataBits >= N) { 2571e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0; 258cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallSize(N); 2591e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer setSmallBits(NewBits | getSmallBits()); 260cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 261cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BitVector *BV = new BitVector(N, t); 262cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t OldBits = getSmallBits(); 263cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman for (size_t i = 0, e = getSmallSize(); i != e; ++i) 264cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman (*BV)[i] = (OldBits >> i) & 1; 265cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(BV); 266cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 267cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 268cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 269cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void reserve(unsigned N) { 270cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 271cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (N > SmallNumDataBits) { 272cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman uintptr_t OldBits = getSmallRawBits(); 273cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman size_t SmallSize = getSmallSize(); 274cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BitVector *BV = new BitVector(SmallSize); 275cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman for (size_t i = 0; i < SmallSize; ++i) 276cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if ((OldBits >> i) & 1) 277cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BV->set(i); 278cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman BV->reserve(N); 279cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman switchToLarge(BV); 280cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 281cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 2821e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reserve(N); 283cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 284cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 285cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 286cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Set, reset, flip 287cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &set() { 288cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 289cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(~uintptr_t(0)); 290cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 2911e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->set(); 292cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 293cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 294cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 295cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &set(unsigned Idx) { 296cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 297cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() | (uintptr_t(1) << Idx)); 298cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 2991e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->set(Idx); 300cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 301cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 302cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 3033a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// set - Efficiently set a range of bits in [I, E) 3043a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson SmallBitVector &set(unsigned I, unsigned E) { 3053a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to set backwards range!"); 3063a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to set out-of-bounds range!"); 3073a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 3083a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (isSmall()) { 30982e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t EMask = ((uintptr_t)1) << E; 31082e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t IMask = ((uintptr_t)1) << I; 3113a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson uintptr_t Mask = EMask - IMask; 3123a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson setSmallBits(getSmallBits() | Mask); 3133a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } else 3143a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson getPointer()->set(I, E); 3153a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 3163a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 3173a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 318cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &reset() { 319cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 320cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(0); 321cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3221e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reset(); 323cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 324cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 325cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 326cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &reset(unsigned Idx) { 327cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 328cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() & ~(uintptr_t(1) << Idx)); 329cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3301e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->reset(Idx); 331cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 332cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 333cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 3343a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson /// reset - Efficiently reset a range of bits in [I, E) 3353a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson SmallBitVector &reset(unsigned I, unsigned E) { 3363a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(I <= E && "Attempted to reset backwards range!"); 3373a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson assert(E <= size() && "Attempted to reset out-of-bounds range!"); 3383a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (I == E) return *this; 3393a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson if (isSmall()) { 34082e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t EMask = ((uintptr_t)1) << E; 34182e9bc2f57c00c200d7227b94891f272462d9292Owen Anderson uintptr_t IMask = ((uintptr_t)1) << I; 3423a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson uintptr_t Mask = EMask - IMask; 3433a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson setSmallBits(getSmallBits() & ~Mask); 3443a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } else 3453a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson getPointer()->reset(I, E); 3463a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson return *this; 3473a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson } 3483a1c35afbd02b012690c35ec827424c27792ec3fOwen Anderson 349cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &flip() { 350cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 351cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(~getSmallBits()); 352cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3531e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->flip(); 354cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 355cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 356cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 357cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector &flip(unsigned Idx) { 358cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 359cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman setSmallBits(getSmallBits() ^ (uintptr_t(1) << Idx)); 360cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 3611e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->flip(Idx); 362cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 363cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 364cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 365cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // No argument flip. 366cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector operator~() const { 367cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return SmallBitVector(*this).flip(); 368cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 369cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 370cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Indexing. 371b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer reference operator[](unsigned Idx) { 372b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer assert(Idx < size() && "Out-of-bounds Bit access."); 373b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer return reference(*this, Idx); 374b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer } 375b252fbd179c494b3c6220f6f7e42f3ff5d15bda6Benjamin Kramer 376cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator[](unsigned Idx) const { 377cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman assert(Idx < size() && "Out-of-bounds Bit access."); 378cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 379cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return ((getSmallBits() >> Idx) & 1) != 0; 3801e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return getPointer()->operator[](Idx); 381cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 382cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 383cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool test(unsigned Idx) const { 384cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return (*this)[Idx]; 385cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 386cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 387904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Test if any common bits are set. 388904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer bool anyCommon(const SmallBitVector &RHS) const { 389904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall() && RHS.isSmall()) 390904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return (getSmallBits() & RHS.getSmallBits()) != 0; 391904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (!isSmall() && !RHS.isSmall()) 392904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return getPointer()->anyCommon(*RHS.getPointer()); 393904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 394904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i) 395904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (test(i) && RHS.test(i)) 396904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return true; 397904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer return false; 398904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 399904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 400cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Comparison operators. 401cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator==(const SmallBitVector &RHS) const { 402cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (size() != RHS.size()) 403cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return false; 404cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) 405cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return getSmallBits() == RHS.getSmallBits(); 406cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 4071e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer return *getPointer() == *RHS.getPointer(); 408cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 409cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 410cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman bool operator!=(const SmallBitVector &RHS) const { 411cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return !(*this == RHS); 412cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 413cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 414cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Intersection, union, disjoint union. 415e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator&=(const SmallBitVector &RHS) { 416e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 417e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 418e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() & RHS.getSmallBits()); 419e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4201e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator&=(*RHS.getPointer()); 421e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 422e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 423e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4241e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator&=(*Copy.getPointer()); 425e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 426e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 427e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 428cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 429e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator|=(const SmallBitVector &RHS) { 430e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 431e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 432e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() | RHS.getSmallBits()); 433e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4341e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator|=(*RHS.getPointer()); 435e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 436e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 437e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4381e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator|=(*Copy.getPointer()); 439e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 440e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 441e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 442cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 443e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector &operator^=(const SmallBitVector &RHS) { 444e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman resize(std::max(size(), RHS.size())); 445e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman if (isSmall()) 446e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman setSmallBits(getSmallBits() ^ RHS.getSmallBits()); 447e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else if (!RHS.isSmall()) 4481e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator^=(*RHS.getPointer()); 449e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman else { 450e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman SmallBitVector Copy = RHS; 451e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman Copy.resize(size()); 4521e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer getPointer()->operator^=(*Copy.getPointer()); 453e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 454e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman return *this; 455e7962c9897cf3ac5fc731702d5e5d8963fc5c723Dan Gohman } 456cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 457cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman // Assignment operator. 458cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman const SmallBitVector &operator=(const SmallBitVector &RHS) { 459cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (isSmall()) { 460cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (RHS.isSmall()) 461cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 462cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else 4631e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer switchToLarge(new BitVector(*RHS.getPointer())); 464cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } else { 465cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman if (!RHS.isSmall()) 4661e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer *getPointer() = *RHS.getPointer(); 467cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman else { 4681e44aa0412473297994afb8b707d0326472fd2a4Benjamin Kramer delete getPointer(); 469cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman X = RHS.X; 470cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 471cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 472cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return *this; 473cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 474cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 4754334dd96a9e622fdcf2825a8f73a2d941d67be72Chandler Carruth#if LLVM_HAS_RVALUE_REFERENCES 476693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer const SmallBitVector &operator=(SmallBitVector &&RHS) { 477693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer if (this != &RHS) { 478693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer clear(); 479693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer swap(RHS); 480693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 481693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer return *this; 482693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer } 483693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer#endif 484693e3ee0c2d2a2cb6f691222694a788dd595c108Benjamin Kramer 485cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman void swap(SmallBitVector &RHS) { 486cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman std::swap(X, RHS.X); 487cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 488904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 489904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// setBitsInMask - Add '1' bits from Mask to this vector. Don't resize. 490904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// This computes "*this |= Mask". 491904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void setBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 492904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 493904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<true, false>(Mask, MaskWords); 494904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 495904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->setBitsInMask(Mask, MaskWords); 496904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 497904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 498904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// clearBitsInMask - Clear any bits in this vector that are set in Mask. 499904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this &= ~Mask". 500904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void clearBitsInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 501904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 502904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<false, false>(Mask, MaskWords); 503904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 504904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->clearBitsInMask(Mask, MaskWords); 505904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 506904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 507904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// setBitsNotInMask - Add a bit to this vector for every '0' bit in Mask. 508904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this |= ~Mask". 509904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void setBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 510904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 511904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<true, true>(Mask, MaskWords); 512904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 513904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->setBitsNotInMask(Mask, MaskWords); 514904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 515904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 516904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// clearBitsNotInMask - Clear a bit in this vector for every '0' bit in Mask. 517904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer /// Don't resize. This computes "*this &= Mask". 518904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void clearBitsNotInMask(const uint32_t *Mask, unsigned MaskWords = ~0u) { 519904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (isSmall()) 520904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer applyMask<false, true>(Mask, MaskWords); 521904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else 522904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer getPointer()->clearBitsNotInMask(Mask, MaskWords); 523904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 524904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer 525904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramerprivate: 526904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer template<bool AddBits, bool InvertMask> 527904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer void applyMask(const uint32_t *Mask, unsigned MaskWords) { 528904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer assert((NumBaseBits == 64 || NumBaseBits == 32) && "Unsupported word size"); 529904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (NumBaseBits == 64 && MaskWords >= 2) { 530904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer uint64_t M = Mask[0] | (uint64_t(Mask[1]) << 32); 531904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (InvertMask) M = ~M; 532904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (AddBits) setSmallBits(getSmallBits() | M); 533904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else setSmallBits(getSmallBits() & ~M); 534904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } else { 535904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer uint32_t M = Mask[0]; 536904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (InvertMask) M = ~M; 537904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer if (AddBits) setSmallBits(getSmallBits() | M); 538904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer else setSmallBits(getSmallBits() & ~M); 539904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 540904cf82f270b9d7bd26df2261f8776efdc9e2fa2Benjamin Kramer } 541cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman}; 542cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 543cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 544cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator&(const SmallBitVector &LHS, const SmallBitVector &RHS) { 545cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 546cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result &= RHS; 547cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 548cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 549cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 550cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 551cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator|(const SmallBitVector &LHS, const SmallBitVector &RHS) { 552cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 553cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result |= RHS; 554cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 555cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 556cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 557cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmaninline SmallBitVector 558cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmanoperator^(const SmallBitVector &LHS, const SmallBitVector &RHS) { 559cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman SmallBitVector Result(LHS); 560cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman Result ^= RHS; 561cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman return Result; 562cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 563cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 564cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} // End llvm namespace 565cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 566cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohmannamespace std { 567cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman /// Implement std::swap in terms of BitVector swap. 568cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman inline void 569cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman swap(llvm::SmallBitVector &LHS, llvm::SmallBitVector &RHS) { 570cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman LHS.swap(RHS); 571cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman } 572cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman} 573cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman 574cb89afc965c66029ae38712d1c52f5bbe4dee942Dan Gohman#endif 575