[BitVector] Define BitWord as uintptr_t

[ekatz]

Summary

Define BitVector::BitWord as uintptr_t instead of unsigned long, as long does not necessarily translates to a pointer size (especially on 64-bit Visual Studio).

[lebedev.ri]

llvm/include/llvm/ADT/BitVector.h

74

It may be better to split NFC cleanup (rest of the patch) and this change into two separate patches.

[ekatz]

llvm/include/llvm/ADT/BitVector.h

74

It is no cleanup, but the same change. It used to be unsigned long, and therefore the numbers (changed) had the suffix UL (unsigned long). As there is no appropriate suffix for size_t, we need to apply casting instead.

[kparzysz]

There is no guarantee that size_t will match the size of a pointer either. Why do you want that anyway?

[lebedev.ri]

llvm/include/llvm/ADT/BitVector.h

74

I think the point i was making was missed.
The suffix->cast cleanup is valid regardless, it can be done beforehand,
and then this patch becomes a single line change.

[ekatz]

llvm/include/llvm/ADT/BitVector.h

74

OK, as there are already other places, in the current version, where the cast to BitWord is made, then this sounds reasonable. Is there a way to post 2 patches in a single review using Phabricator? Or should I open a separate review?

[ekatz]

In D69336#1719048, @kparzysz wrote:

There is no guarantee that size_t will match the size of a pointer either. Why do you want that anyway?

Correct. I will change it to uintptr_t.
This is needed for the heavy usage of countPopulation, countTrailingZeros and countLeadingZeros.

[lebedev.ri]

llvm/include/llvm/ADT/BitVector.h

74

Separate review (that new patch should be the first one, this D69336 should be based on it)

[kparzysz]

There are custom implementations of these functions for 64-bit unsigned values, so you should make it uint64_t. There is no connection with the pointer size.

[ekatz]

In D69336#1719215, @kparzysz wrote:

There are custom implementations of these functions for 64-bit unsigned values, so you should make it uint64_t. There is no connection with the pointer size.

Some intrinsics only available for specific architectures. For example, on Windows, _BitScanReverse64 is only available in a 64-bit build (refer to LeadingZerosCounter<T,8> in MathExtras.h).

[lattner]

This looks like progress to me. I personally would go with size_t even despite the (theoretical IMO) concern about size_t being a different size, but either way works for me, and both are better than ulong.

[ekatz]

I cannot commit this patch myself. Please commit it (and the parent change, of course) in my behalf.

Author: Ehud Katz <[e-mail]>

Thanks.

llvm/include/llvm/ADT/BitVector.h

public:
   bool operator!=(const const_set_bits_iterator_impl &Other) const {
     assert(&Parent == &Other.Parent &&
            "Comparing iterators from different BitVectors");
     return Current != Other.Current;
   }
 };
 
 class BitVector {
-  typedef unsigned long BitWord;
+  typedef size_t BitWord;
 
   enum { BITWORD_SIZE = (unsigned)sizeof(BitWord) * CHAR_BIT };
 
   static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
   MutableArrayRef<BitWord> Bits; // Actual bits.
   unsigned Size;                 // Size of bitvector in bits.
for (unsigned i = 0; i < NumBitWords(size()); ++i)
       if (Bits[i] != 0)
         return true;
     return false;
   }
 
   /// all - Returns true if all bits are set.
   bool all() const {
     for (unsigned i = 0; i < Size / BITWORD_SIZE; ++i)
-      if (Bits[i] != ~0UL)
+      if (Bits[i] != ~BitWord(0))
         return false;
 
     // If bits remain check that they are ones. The unused bits are always zero.
     if (unsigned Remainder = Size % BITWORD_SIZE)
-      return Bits[Size / BITWORD_SIZE] == (1UL << Remainder) - 1;
+      return Bits[Size / BITWORD_SIZE] == (BitWord(1) << Remainder) - 1;
 
     return true;
   }
 
   /// none - Returns true if none of the bits are set.
   bool none() const {
     return !any();
   }
for (unsigned i = FirstWord; i <= LastWord; ++i) {
         unsigned FirstBit = Begin % BITWORD_SIZE;
         Copy |= maskTrailingOnes<BitWord>(FirstBit);
       }
 
       if (i == LastWord) {
         unsigned LastBit = (End - 1) % BITWORD_SIZE;
         Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
       }
-      if (Copy != ~0UL) {
+      if (Copy != ~BitWord(0)) {
         unsigned Result = i * BITWORD_SIZE + countTrailingOnes(Copy);
         return Result < size() ? Result : -1;
       }
     }
     return -1;
   }
 
   /// find_last_unset_in - Returns the index of the last unset bit in the
for (unsigned i = LastWord + 1; i >= FirstWord + 1; --i) {
         Copy |= maskTrailingZeros<BitWord>(LastBit + 1);
       }
 
       if (CurrentWord == FirstWord) {
         unsigned FirstBit = Begin % BITWORD_SIZE;
         Copy |= maskTrailingOnes<BitWord>(FirstBit);
       }
 
-      if (Copy != ~0UL) {
+      if (Copy != ~BitWord(0)) {
         unsigned Result =
             (CurrentWord + 1) * BITWORD_SIZE - countLeadingOnes(Copy) - 1;
         return Result < Size ? Result : -1;
       }
     }
     return -1;
   }
 
public:
   /// set - Efficiently set a range of bits in [I, E)
   BitVector &set(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to set backwards range!");
     assert(E <= size() && "Attempted to set out-of-bounds range!");
 
     if (I == E) return *this;
 
     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
-      BitWord EMask = 1UL << (E % BITWORD_SIZE);
-      BitWord IMask = 1UL << (I % BITWORD_SIZE);
+      BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
+      BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
       BitWord Mask = EMask - IMask;
       Bits[I / BITWORD_SIZE] |= Mask;
       return *this;
     }
 
-    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
+    BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
     Bits[I / BITWORD_SIZE] |= PrefixMask;
     I = alignTo(I, BITWORD_SIZE);
 
     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
-      Bits[I / BITWORD_SIZE] = ~0UL;
+      Bits[I / BITWORD_SIZE] = ~BitWord(0);
 
-    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
+    BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] |= PostfixMask;
 
     return *this;
   }
 
   BitVector &reset() {
     init_words(Bits, false);
     return *this;
   }
 
   BitVector &reset(unsigned Idx) {
     Bits[Idx / BITWORD_SIZE] &= ~(BitWord(1) << (Idx % BITWORD_SIZE));
     return *this;
   }
 
   /// reset - Efficiently reset a range of bits in [I, E)
   BitVector &reset(unsigned I, unsigned E) {
     assert(I <= E && "Attempted to reset backwards range!");
     assert(E <= size() && "Attempted to reset out-of-bounds range!");
 
     if (I == E) return *this;
 
     if (I / BITWORD_SIZE == E / BITWORD_SIZE) {
-      BitWord EMask = 1UL << (E % BITWORD_SIZE);
-      BitWord IMask = 1UL << (I % BITWORD_SIZE);
+      BitWord EMask = BitWord(1) << (E % BITWORD_SIZE);
+      BitWord IMask = BitWord(1) << (I % BITWORD_SIZE);
       BitWord Mask = EMask - IMask;
       Bits[I / BITWORD_SIZE] &= ~Mask;
       return *this;
     }
 
-    BitWord PrefixMask = ~0UL << (I % BITWORD_SIZE);
+    BitWord PrefixMask = ~BitWord(0) << (I % BITWORD_SIZE);
     Bits[I / BITWORD_SIZE] &= ~PrefixMask;
     I = alignTo(I, BITWORD_SIZE);
 
     for (; I + BITWORD_SIZE <= E; I += BITWORD_SIZE)
-      Bits[I / BITWORD_SIZE] = 0UL;
+      Bits[I / BITWORD_SIZE] = BitWord(0);
 
-    BitWord PostfixMask = (1UL << (E % BITWORD_SIZE)) - 1;
+    BitWord PostfixMask = (BitWord(1) << (E % BITWORD_SIZE)) - 1;
     if (I < E)
       Bits[I / BITWORD_SIZE] &= ~PostfixMask;
 
     return *this;
   }
 
   BitVector &flip() {
     for (unsigned i = 0; i < NumBitWords(size()); ++i)
void set_unused_bits(bool t = true) {
     //  Set high words first.
     unsigned UsedWords = NumBitWords(Size);
     if (Bits.size() > UsedWords)
       init_words(Bits.drop_front(UsedWords), t);
 
     //  Then set any stray high bits of the last used word.
     unsigned ExtraBits = Size % BITWORD_SIZE;
     if (ExtraBits) {
-      BitWord ExtraBitMask = ~0UL << ExtraBits;
+      BitWord ExtraBitMask = ~BitWord(0) << ExtraBits;
       if (t)
         Bits[UsedWords-1] |= ExtraBitMask;
       else
         Bits[UsedWords-1] &= ~ExtraBitMask;
     }
   }
 
   // Clear the unused bits in the high words.