ADT: Use EBO to shrink SmallVector size 1

[dexonsmith]

Summary

SmallVectorStorage is empty when its size is 1; use inheritance so that the empty base class optimization kicks in, saving a pointer for small SmallVectors.

I assume all compilers support this so the static_assert is valid... or should I only assert under some feature flag?

[rnk]

Thanks for finding that!

[lattner]

nice!

[xbolva00]

Looks fine

[dexonsmith]

Committed in r335421.

llvm/include/llvm/ADT/SmallVector.h

 /// for the case when the array is small.  It contains some number of elements
 /// in-place, which allows it to avoid heap allocation when the actual number of
 /// elements is below that threshold.  This allows normal "small" cases to be
 /// fast without losing generality for large inputs.
 ///
 /// Note that this does not attempt to be exception safe.
 ///
 template <typename T, unsigned N>
-class SmallVector : public SmallVectorImpl<T> {
-  /// Inline space for elements which aren't stored in the base class.
-  SmallVectorStorage<T, N> Storage;
-
+class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
 public:
   SmallVector() : SmallVectorImpl<T>(N) {}
 
   ~SmallVector() {
     // Destroy the constructed elements in the vector.
     this->destroy_range(this->begin(), this->end());
   }
 

llvm/lib/Support/SmallVector.cpp

 //===- llvm/ADT/SmallVector.cpp - 'Normally small' vectors ----------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the SmallVector class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/SmallVector.h"
 using namespace llvm;
 
+// Check that no bytes are wasted.
+static_assert(sizeof(SmallVector<void *, 1>) == sizeof(void *) * 4,
+              "wasted space in SmallVector size 1; missing EBO?");
+
 /// grow_pod - This is an implementation of the grow() method which only works
 /// on POD-like datatypes and is out of line to reduce code duplication.
 void SmallVectorBase::grow_pod(void *FirstEl, size_t MinSizeInBytes,
                                size_t TSize) {
   size_t CurSizeBytes = size_in_bytes();
   size_t NewCapacityInBytes = 2 * capacity_in_bytes() + TSize; // Always grow.
   if (NewCapacityInBytes < MinSizeInBytes)
     NewCapacityInBytes = MinSizeInBytes;