SmallPtrSet: Put the part of insert() on small sets into the header

[MatzeB]

Summary

Most of the time we only hit the small case, so it is beneficial to pull
it out of insert_imp(). This improves compile time at least for non-LTO builds.

[chandlerc]

Yea, this seems like obvious goodness.

[reames]

LGTM to me as well. Thanks!

llvm/trunk/include/llvm/ADT/SmallPtrSet.h

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);
   }
 
   /// insert_imp - This returns true if the pointer was new to the set, false if
   /// it was already in the set.  This is hidden from the client so that the
   /// derived class can check that the right type of pointer is passed in.
-  std::pair<const void *const *, bool> insert_imp(const void *Ptr);
+  std::pair<const void *const *, bool> insert_imp(const void *Ptr) {
+    if (isSmall()) {
+      // Check to see if it is already in the set.
+      for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
+           APtr != E; ++APtr)
+        if (*APtr == Ptr)
+          return std::make_pair(APtr, false);
+
+      // Nope, there isn't.  If we stay small, just 'pushback' now.
+      if (NumElements < CurArraySize) {
+        SmallArray[NumElements++] = Ptr;
+        return std::make_pair(SmallArray + (NumElements - 1), true);
+      }
+      // Otherwise, hit the big set case, which will call grow.
+    }
+    return insert_imp_big(Ptr);
+  }
 
   /// erase_imp - If the set contains the specified pointer, remove it and
   /// return true, otherwise return false.  This is hidden from the client so
   /// that the derived class can check that the right type of pointer is passed
   /// in.
   bool erase_imp(const void * Ptr);
 
   bool count_imp(const void * Ptr) const {
     if (isSmall()) {
       // Linear search for the item.
       for (const void *const *APtr = SmallArray,
                       *const *E = SmallArray+NumElements; APtr != E; ++APtr)
         if (*APtr == Ptr)
           return true;
       return false;
     }
 
     // Big set case.
     return *FindBucketFor(Ptr) == Ptr;
   }
 
 private:
   bool isSmall() const { return CurArray == SmallArray; }
 
+  std::pair<const void *const *, bool> insert_imp_big(const void *Ptr);
+
   const void * const *FindBucketFor(const void *Ptr) const;
   void shrink_and_clear();
 
   /// Grow - Allocate a larger backing store for the buckets and move it over.
   void Grow(unsigned NewSize);
 
   void operator=(const SmallPtrSetImplBase &RHS) = delete;
 

llvm/trunk/lib/Support/SmallPtrSet.cpp

void SmallPtrSetImplBase::shrink_and_clear() {
 
   // Install the new array.  Clear all the buckets to empty.
   CurArray = (const void**)malloc(sizeof(void*) * CurArraySize);
   assert(CurArray && "Failed to allocate memory?");
   memset(CurArray, -1, CurArraySize*sizeof(void*));
 }
 
 std::pair<const void *const *, bool>
-SmallPtrSetImplBase::insert_imp(const void *Ptr) {
-  if (isSmall()) {
-    // Check to see if it is already in the set.
-    for (const void **APtr = SmallArray, **E = SmallArray+NumElements;
-         APtr != E; ++APtr)
-      if (*APtr == Ptr)
-        return std::make_pair(APtr, false);
-
-    // Nope, there isn't.  If we stay small, just 'pushback' now.
-    if (NumElements < CurArraySize) {
-      SmallArray[NumElements++] = Ptr;
-      return std::make_pair(SmallArray + (NumElements - 1), true);
-    }
-    // Otherwise, hit the big set case, which will call grow.
-  }
-
+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) <
                            CurArraySize / 8)) {
     // If fewer of 1/8 of the array is empty (meaning that many are filled with
     // tombstones), rehash.
     Grow(CurArraySize);