Update {Small}BitVector size_type definition

[rengolin]

Summary

SmallBitVector implements a level of indirection over BitVector by
storing a smaller bit-vector in a pointer-sized element, or in case the
number of elements exceeds the bucket size, it creates a new pointer to
a BitVector and uses that as its storage.

However, the functions returning the vector size were using unsigned,
which is ok for BitVector, but not for SmallBitVector, which is actually
uintptr_t.

This commit reuses the size_type definition to more than just count
and propagates them into range iteration, size calculation, etc.

This is a continuation of D108124.

I haven't changed all occurrences of unsigned or uintptr_t to
size_type, just those that were directly related.

[rengolin]

Update with clang-format and clang-tidy hints.

[rengolin]

The last clang-tidy warning (capacity_in_bytes) is pertinent but not for this patch.

A code grep on the whole of LLVM shows that it's never used internally, but both DenseMap and SmallVector have the same interface (although, neither use it externally either).

Clang only seems to use llvm::capacity_in_bytes (defined in Support/Capacity.h), so the public API of these containers can change independently.

In theory, we could change all of them to fit the standard, but given that this isn't the review that looks at that, and we were accidentally touching that code, I'll leave it for another commit.

[serge-sans-paille]

LGTM, thanks for the code cleaning!

llvm/include/llvm/ADT/BitVector.h

static_assert(BITWORD_SIZE == 64 || BITWORD_SIZE == 32,
                 "Unsupported word size");
 
   using Storage = SmallVector<BitWord>;
 
   Storage Bits;  // Actual bits.
   unsigned Size; // Size of bitvector in bits.
 
 public:
-  typedef unsigned size_type;
+  using size_type = unsigned;
 
   // Encapsulation of a single bit.
   class reference {
 
     BitWord *WordRef;
     unsigned BitPos;
 
   public:
public:
   template <class F, class... ArgTys>
   static BitVector &apply(F &&f, BitVector &Out, BitVector const &Arg,
                           ArgTys const &...Args) {
     assert(llvm::all_of(
                std::initializer_list<unsigned>{Args.size()...},
                [&Arg](auto const &BV) { return Arg.size() == BV; }) &&
            "consistent sizes");
     Out.resize(Arg.size());
-    for (size_t i = 0, e = Arg.Bits.size(); i != e; ++i)
+    for (size_type i = 0, e = Arg.Bits.size(); i != e; ++i)
       Out.Bits[i] = f(Arg.Bits[i], Args.Bits[i]...);
     Out.clear_unused_bits();
     return Out;
   }
 
   BitVector &operator|=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
-    for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
+    for (size_type i = 0, e = RHS.Bits.size(); i != e; ++i)
       Bits[i] |= RHS.Bits[i];
     return *this;
   }
 
   BitVector &operator^=(const BitVector &RHS) {
     if (size() < RHS.size())
       resize(RHS.size());
-    for (size_t i = 0, e = RHS.Bits.size(); i != e; ++i)
+    for (size_type i = 0, e = RHS.Bits.size(); i != e; ++i)
       Bits[i] ^= RHS.Bits[i];
     return *this;
   }
 
   BitVector &operator>>=(unsigned N) {
     assert(N <= Size);
     if (LLVM_UNLIKELY(empty() || N == 0))
       return *this;
for (unsigned b = 0; MaskWords; b += 32, --MaskWords) {
       else         Bits[i] &= ~(BitWord(M) << b);
     }
     if (AddBits)
       clear_unused_bits();
   }
 
 public:
   /// Return the size (in bytes) of the bit vector.
-  size_t getMemorySize() const { return Bits.size() * sizeof(BitWord); }
-  size_t getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
+  size_type getMemorySize() const { return Bits.size() * sizeof(BitWord); }
+  size_type getBitCapacity() const { return Bits.size() * BITWORD_SIZE; }
 };
 
-inline size_t capacity_in_bytes(const BitVector &X) {
+inline BitVector::size_type capacity_in_bytes(const BitVector &X) {
   return X.getMemorySize();
 }
 
 template <> struct DenseMapInfo<BitVector> {
   static inline BitVector getEmptyKey() { return {}; }
   static inline BitVector getTombstoneKey() {
     BitVector V;
     V.invalid();
     return V;
   }
   static unsigned getHashValue(const BitVector &V) {
-    return DenseMapInfo<std::pair<unsigned, ArrayRef<uintptr_t>>>::getHashValue(
-        std::make_pair(V.size(), V.getData()));
+    return DenseMapInfo<std::pair<BitVector::size_type, ArrayRef<uintptr_t>>>::
+        getHashValue(std::make_pair(V.size(), V.getData()));
   }
   static bool isEqual(const BitVector &LHS, const BitVector &RHS) {
     if (LHS.isInvalid() || RHS.isInvalid())
       return LHS.isInvalid() == RHS.isInvalid();
     return LHS == RHS;
   }
 };
 } // end namespace llvm
 
 namespace std {
   /// Implement std::swap in terms of BitVector swap.
 inline void swap(llvm::BitVector &LHS, llvm::BitVector &RHS) { LHS.swap(RHS); }
 } // end namespace std
 
 #endif // LLVM_ADT_BITVECTOR_H

llvm/include/llvm/ADT/SmallBitVector.h

enum {
     // The remaining bits are used to store the actual set in small mode.
     SmallNumDataBits = SmallNumRawBits - SmallNumSizeBits
   };
 
   static_assert(NumBaseBits == 64 || NumBaseBits == 32,
                 "Unsupported word size");
 
 public:
-  using size_type = unsigned;
+  using size_type = uintptr_t;
 
   // Encapsulation of a single bit.
   class reference {
     SmallBitVector &TheVector;
     unsigned BitPos;
 
   public:
     reference(SmallBitVector &b, unsigned Idx) : TheVector(b), BitPos(Idx) {}
public:
   };
 
 private:
   BitVector *getPointer() const {
     assert(!isSmall());
     return reinterpret_cast<BitVector *>(X);
   }
 
-  void switchToSmall(uintptr_t NewSmallBits, size_t NewSize) {
+  void switchToSmall(uintptr_t NewSmallBits, size_type NewSize) {
     X = 1;
     setSmallSize(NewSize);
     setSmallBits(NewSmallBits);
   }
 
   void switchToLarge(BitVector *BV) {
     X = reinterpret_cast<uintptr_t>(BV);
     assert(!isSmall() && "Tried to use an unaligned pointer");
   }
 
   // Return all the bits used for the "small" representation; this includes
   // bits for the size as well as the element bits.
   uintptr_t getSmallRawBits() const {
     assert(isSmall());
     return X >> 1;
   }
 
   void setSmallRawBits(uintptr_t NewRawBits) {
     assert(isSmall());
     X = (NewRawBits << 1) | uintptr_t(1);
   }
 
   // Return the size.
-  size_t getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
+  size_type getSmallSize() const { return getSmallRawBits() >> SmallNumDataBits; }
 
-  void setSmallSize(size_t Size) {
+  void setSmallSize(size_type Size) {
     setSmallRawBits(getSmallBits() | (Size << SmallNumDataBits));
   }
 
   // Return the element bits.
   uintptr_t getSmallBits() const {
     return getSmallRawBits() & ~(~uintptr_t(0) << getSmallSize());
   }
 
public:
   bool isSmall() const { return X & uintptr_t(1); }
 
   /// Tests whether there are no bits in this bitvector.
   bool empty() const {
     return isSmall() ? getSmallSize() == 0 : getPointer()->empty();
   }
 
   /// Returns the number of bits in this bitvector.
-  size_t size() const {
+  size_type size() const {
     return isSmall() ? getSmallSize() : getPointer()->size();
   }
 
   /// Returns the number of bits which are set.
   size_type count() const {
     if (isSmall()) {
       uintptr_t Bits = getSmallBits();
       return countPopulation(Bits);
if (!isSmall()) {
       getPointer()->resize(N, t);
     } else if (SmallNumDataBits >= N) {
       uintptr_t NewBits = t ? ~uintptr_t(0) << getSmallSize() : 0;
       setSmallSize(N);
       setSmallBits(NewBits | getSmallBits());
     } else {
       BitVector *BV = new BitVector(N, t);
       uintptr_t OldBits = getSmallBits();
-      for (size_t i = 0, e = getSmallSize(); i != e; ++i)
+      for (size_type i = 0, e = getSmallSize(); i != e; ++i)
         (*BV)[i] = (OldBits >> i) & 1;
       switchToLarge(BV);
     }
   }
 
   void reserve(unsigned N) {
     if (isSmall()) {
       if (N > SmallNumDataBits) {
         uintptr_t OldBits = getSmallRawBits();
-        size_t SmallSize = getSmallSize();
+        size_type SmallSize = getSmallSize();
         BitVector *BV = new BitVector(SmallSize);
-        for (size_t i = 0; i < SmallSize; ++i)
+        for (size_type i = 0; i < SmallSize; ++i)
           if ((OldBits >> i) & 1)
             BV->set(i);
         BV->reserve(N);
         switchToLarge(BV);
       }
     } else {
       getPointer()->reserve(N);
     }
public:
   bool operator==(const SmallBitVector &RHS) const {
     if (size() != RHS.size())
       return false;
     if (isSmall() && RHS.isSmall())
       return getSmallBits() == RHS.getSmallBits();
     else if (!isSmall() && !RHS.isSmall())
       return *getPointer() == *RHS.getPointer();
     else {
-      for (size_t i = 0, e = size(); i != e; ++i) {
+      for (size_type i = 0, e = size(); i != e; ++i) {
         if ((*this)[i] != RHS[i])
           return false;
       }
       return true;
     }
   }
 
   bool operator!=(const SmallBitVector &RHS) const {
     return !(*this == RHS);
   }
 
   // Intersection, union, disjoint union.
   // FIXME BitVector::operator&= does not resize the LHS but this does
   SmallBitVector &operator&=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
     if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() & RHS.getSmallBits());
     else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator&=(*RHS.getPointer());
     else {
-      size_t i, e;
+      size_type i, e;
       for (i = 0, e = std::min(size(), RHS.size()); i != e; ++i)
         (*this)[i] = test(i) && RHS.test(i);
       for (e = size(); i != e; ++i)
         reset(i);
     }
     return *this;
   }
 
public:
 
   SmallBitVector &operator|=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
     if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() | RHS.getSmallBits());
     else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator|=(*RHS.getPointer());
     else {
-      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+      for (size_type i = 0, e = RHS.size(); i != e; ++i)
         (*this)[i] = test(i) || RHS.test(i);
     }
     return *this;
   }
 
   SmallBitVector &operator^=(const SmallBitVector &RHS) {
     resize(std::max(size(), RHS.size()));
     if (isSmall() && RHS.isSmall())
       setSmallBits(getSmallBits() ^ RHS.getSmallBits());
     else if (!isSmall() && !RHS.isSmall())
       getPointer()->operator^=(*RHS.getPointer());
     else {
-      for (size_t i = 0, e = RHS.size(); i != e; ++i)
+      for (size_type i = 0, e = RHS.size(); i != e; ++i)
         (*this)[i] = test(i) != RHS.test(i);
     }
     return *this;
   }
 
   SmallBitVector &operator<<=(unsigned N) {
     if (isSmall())
       setSmallBits(getSmallBits() << N);
template <> struct DenseMapInfo<SmallBitVector> {
   static inline SmallBitVector getEmptyKey() { return SmallBitVector(); }
   static inline SmallBitVector getTombstoneKey() {
     SmallBitVector V;
     V.invalid();
     return V;
   }
   static unsigned getHashValue(const SmallBitVector &V) {
     uintptr_t Store;
-    return DenseMapInfo<std::pair<size_t, ArrayRef<uintptr_t>>>::getHashValue(
-        std::make_pair(V.size(), V.getData(Store)));
+    return DenseMapInfo<
+        std::pair<SmallBitVector::size_type, ArrayRef<uintptr_t>>>::
+        getHashValue(std::make_pair(V.size(), V.getData(Store)));
   }
   static bool isEqual(const SmallBitVector &LHS, const SmallBitVector &RHS) {
     if (LHS.isInvalid() || RHS.isInvalid())
       return LHS.isInvalid() == RHS.isInvalid();
     return LHS == RHS;
   }
 };
 } // end namespace llvm