SmallPtrSet: Only initialize NumTombstones when not small anymore.

[MatzeB]

Summary

SmallPtrSets stay small in the majority of cases so this is just another
memory operation that can be avoid in the common case.

[chandlerc]

Nice.

[MatzeB]

Abandoning because this is not compatible anymore with the new version of http://reviews.llvm.org/D16672

include/llvm/ADT/SmallPtrSet.h

protected:
   /// CurArray - This is the current set of buckets.  If equal to SmallArray,
   /// then the set is in 'small mode'.
   const void **CurArray;
   /// CurArraySize - The allocated size of CurArray, always a power of two.
   unsigned CurArraySize;
 
   // If small, this is # elts allocated consecutively
   unsigned NumElements;
+  /// Uninitialized for small sets, otherwise the number of tombstones.
   unsigned NumTombstones;
 
   // Helpers to copy and move construct a SmallPtrSet.
   SmallPtrSetImplBase(const void **SmallStorage,
                       const SmallPtrSetImplBase &that);
   SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
                       SmallPtrSetImplBase &&that);
   explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) :
void clear() {
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
     if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32)
       return shrink_and_clear();
 
     // Fill the array with empty markers.
     memset(CurArray, -1, CurArraySize*sizeof(void*));
     NumElements = 0;
-    NumTombstones = 0;
   }
 
 protected:
   static void *getTombstoneMarker() { return reinterpret_cast<void*>(-2); }
   static void *getEmptyMarker() {
     // Note that -1 is chosen to make clear() efficiently implementable with
     // memset and because it's not a valid pointer value.
     return reinterpret_cast<void*>(-1);

lib/Support/SmallPtrSet.cpp

void SmallPtrSetImplBase::shrink_and_clear() {
   memset(CurArray, -1, CurArraySize*sizeof(void*));
 }
 
 std::pair<const void *const *, bool>
 SmallPtrSetImplBase::insert_imp_big(const void *Ptr) {
   if (LLVM_UNLIKELY(NumElements * 4 >= CurArraySize * 3)) {
     // If more than 3/4 of the array is full, grow.
     Grow(CurArraySize < 64 ? 128 : CurArraySize*2);
-  } else if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) <
+  } else {
+    assert(!isSmall() && "NumTombstones is uninitialized if not small");
+    if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) <
                            CurArraySize / 8)) {
-    // If fewer of 1/8 of the array is empty (meaning that many are filled with
-    // tombstones), rehash.
+      // If fewer of 1/8 of the array is empty (meaning that many are filled
+      // with tombstones), rehash.
       Grow(CurArraySize);
     }
+  }
 
   // Okay, we know we have space.  Find a hash bucket.
   const void **Bucket = const_cast<const void**>(FindBucketFor(Ptr));
   if (*Bucket == Ptr)
     return std::make_pair(Bucket, false); // Already inserted, good.
 
   // Otherwise, insert it!
   if (*Bucket == getTombstoneMarker())
for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize;
          BucketPtr != E; ++BucketPtr) {
       // Copy over the element if it is valid.
       const void *Elt = *BucketPtr;
       if (Elt != getTombstoneMarker() && Elt != getEmptyMarker())
         *const_cast<void**>(FindBucketFor(Elt)) = const_cast<void*>(Elt);
     }
 
     free(OldBuckets);
-    NumTombstones = 0;
   }
+  NumTombstones = 0;
 }
 
 SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage,
                                          const SmallPtrSetImplBase &that) {
   SmallArray = SmallStorage;
 
   // If we're becoming small, prepare to insert into our stack space
   if (that.isSmall()) {

 void SmallPtrSetImplBase::CopyHelper(const SmallPtrSetImplBase &RHS) {
   // Copy over the new array size
   CurArraySize = RHS.CurArraySize;
 
   // Copy over the contents from the other set
   memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize);
 
   NumElements = RHS.NumElements;
+  if (!RHS.isSmall())
     NumTombstones = RHS.NumTombstones;
 }
 
 void SmallPtrSetImplBase::MoveFrom(unsigned SmallSize,
                                    SmallPtrSetImplBase &&RHS) {
   if (!isSmall())
     free(CurArray);
   MoveHelper(SmallSize, std::move(RHS));
 }
 
 void SmallPtrSetImplBase::MoveHelper(unsigned SmallSize,
                                      SmallPtrSetImplBase &&RHS) {
   assert(&RHS != this && "Self-move should be handled by the caller.");
 
   if (RHS.isSmall()) {
     // Copy a small RHS rather than moving.
     CurArray = SmallArray;
     memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize);
   } else {
     CurArray = RHS.CurArray;
     RHS.CurArray = RHS.SmallArray;
+    NumTombstones = RHS.NumTombstones;
   }
 
   // Copy the rest of the trivial members.
   CurArraySize = RHS.CurArraySize;
   NumElements = RHS.NumElements;
-  NumTombstones = RHS.NumTombstones;
 
   // Make the RHS small and empty.
   RHS.CurArraySize = SmallSize;
   assert(RHS.CurArray == RHS.SmallArray);
   RHS.NumElements = 0;
-  RHS.NumTombstones = 0;
 }
 
 void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
   if (this == &RHS) return;
 
   // We can only avoid copying elements if neither set is small.
   if (!this->isSmall() && !RHS.isSmall()) {
     std::swap(this->CurArray, RHS.CurArray);
void SmallPtrSetImplBase::swap(SmallPtrSetImplBase &RHS) {
   if (!this->isSmall() && RHS.isSmall()) {
     std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize,
               this->SmallArray);
     std::swap(this->NumElements, RHS.NumElements);
     std::swap(this->CurArraySize, RHS.CurArraySize);
     RHS.CurArray = this->CurArray;
     RHS.NumTombstones = this->NumTombstones;
     this->CurArray = this->SmallArray;
-    this->NumTombstones = 0;
     return;
   }
 
   // If only LHS is small, copy the small elements into RHS and move the pointer
   // from RHS to LHS.
   if (this->isSmall() && !RHS.isSmall()) {
     std::copy(this->SmallArray, this->SmallArray+this->CurArraySize,
               RHS.SmallArray);
     std::swap(RHS.NumElements, this->NumElements);
     std::swap(RHS.CurArraySize, this->CurArraySize);
     this->CurArray = RHS.CurArray;
-    this->NumTombstones = RHS.NumTombstones;
     RHS.CurArray = RHS.SmallArray;
     RHS.NumTombstones = 0;
     return;
   }
 
   // Both a small, just swap the small elements.
   assert(this->isSmall() && RHS.isSmall());
   assert(this->CurArraySize == RHS.CurArraySize);
   std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize,
                    RHS.SmallArray);
   std::swap(this->NumElements, RHS.NumElements);
 }