ADT: Shrink SmallVector size 0 to 16B on 64-bit platforms

[dexonsmith]

Summary

SmallVectorTemplateCommon wants to know the address of the first element so it can detect whether it's in "small size" mode.

The old implementation split the small array, creating the storage for the first element in SmallVectorTemplateCommon, and pulling the rest into SmallVectorStorage where we know the size of the array. This bloats SmallVector small-size 0 by the larger of sizeof(void*) and sizeof(T) unnecessarily.

The new implementation leaves the full small storage to SmallVectorStorage. To calculate the offset of the first element in SmallVectorTemplateCommon, we just need to know how far to jump, which we can calculate out-of-band. One subtlety is that we need SmallVectorStorage to be properly aligned even when the size is 0, to be sure that (for large alignments) we actually have the padding and it's well defined to do the pointer math.

[rnk]

@rsmith, what's the least bad way to do what SmallVector is trying to do?

llvm/include/llvm/ADT/SmallVector.h

90

This assumes that base classes are laid out more or less the same as fields, but we were already assuming that there wouldn't be padding between FirstEl and InlineElts, so this seems like an improvement.

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

90

What about this?

struct SmallVectorAlignmentAndSizeBase {
  AlignedCharArrayUnion<SmallVectorBase> Base;
};
template <class T>
struct SmallVectorAlignmentAndSize : SmallVectorAlignmentAndSizeBase {
  AlignedCharArrayUnion<T> FirstEl;
};

// still doing this later:
  void *getFirstEl() const {
    return const_cast<void *>(reinterpret_cast<const void *>(
        reinterpret_cast<const char *>(this) +
        offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
  }

[dexonsmith]

llvm/include/llvm/ADT/SmallVector.h

90

we were already assuming that there wouldn't be padding between FirstEl and InlineElts

BTW, I don't think we had to assuming that there wouldn't be padding. As long as there's enough otherwise-unused storage after FirstEl, we won't overflow the allocation.

[rnk]

lgtm, I was hoping @rsmith would have a better suggestion, but we don't need to wait on it.

llvm/include/llvm/ADT/SmallVector.h

90

I think there are interesting differences between multiple inheritance and single inheritance, so I don't think this is an improvement over the simpler offsetof calculation that you have now.

[dexonsmith]

Committed in r337820.

llvm/include/llvm/ADT/SmallVector.h

public:
   /// update the size later. This avoids the cost of value initializing elements
   /// which will only be overwritten.
   void set_size(size_t Size) {
     assert(Size <= capacity());
     this->Size = Size;
   }
 };
 
+/// Figure out the offset of the first element.
+template <class T, typename = void> struct SmallVectorAlignmentAndSize {
+  AlignedCharArrayUnion<SmallVectorBase> Base;
+  AlignedCharArrayUnion<T> FirstEl;
+};
+
 /// This is the part of SmallVectorTemplateBase which does not depend on whether
 /// the type T is a POD. The extra dummy template argument is used by ArrayRef
 /// to avoid unnecessarily requiring T to be complete.
 template <typename T, typename = void>
 class SmallVectorTemplateCommon : public SmallVectorBase {
-private:
-  template <typename, unsigned> friend struct SmallVectorStorage;
-
-  // Allocate raw space for N elements of type T.  If T has a ctor or dtor, we
-  // don't want it to be automatically run, so we need to represent the space as
-  // something else.  Use an array of char of sufficient alignment.
-  using U = AlignedCharArrayUnion<T>;
-  U FirstEl;
+  /// Find the address of the first element.  For this pointer math to be valid
+  /// with small-size of 0 for T with lots of alignment, it's important that
+  /// SmallVectorStorage is properly-aligned even for small-size of 0.
+  void *getFirstEl() const {
+    return const_cast<void *>(reinterpret_cast<const void *>(
+        reinterpret_cast<const char *>(this) +
+        offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)));
+  }
   // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
 
 protected:
-  SmallVectorTemplateCommon(size_t Size) : SmallVectorBase(&FirstEl, Size) {}
+  SmallVectorTemplateCommon(size_t Size)
+      : SmallVectorBase(getFirstEl(), Size) {}
 
   void grow_pod(size_t MinCapacity, size_t TSize) {
-    SmallVectorBase::grow_pod(&FirstEl, MinCapacity, TSize);
+    SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
   }
 
   /// Return true if this is a smallvector which has not had dynamic
   /// memory allocated for it.
-  bool isSmall() const {
-    return BeginX == static_cast<const void*>(&FirstEl);
-  }
+  bool isSmall() const { return BeginX == getFirstEl(); }
 
   /// Put this vector in a state of being small.
   void resetToSmall() {
-    BeginX = &FirstEl;
+    BeginX = getFirstEl();
     Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
   }
 
 public:
   using size_type = size_t;
   using difference_type = ptrdiff_t;
   using value_type = T;
   using iterator = T *;
SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
 
   // Set end.
   this->set_size(RHSSize);
 
   RHS.clear();
   return *this;
 }
 
-/// Storage for the SmallVector elements which aren't contained in
-/// SmallVectorTemplateCommon. There are 'N-1' elements here. The remaining '1'
-/// element is in the base class. This is specialized for the N=1 and N=0 cases
+/// Storage for the SmallVector elements.  This is specialized for the N=0 case
 /// to avoid allocating unnecessary storage.
 template <typename T, unsigned N>
 struct SmallVectorStorage {
-  typename SmallVectorTemplateCommon<T>::U InlineElts[N - 1];
+  AlignedCharArrayUnion<T> InlineElts[N];
 };
-template <typename T> struct SmallVectorStorage<T, 1> {};
-template <typename T> struct SmallVectorStorage<T, 0> {};
+
+/// We need the storage to be properly aligned even for small-size of 0 so that
+/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
+/// well-defined.
+template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
 
 /// This is a 'vector' (really, a variable-sized array), optimized
 /// 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.

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.
+// Check that no bytes are wasted and everything is well-aligned.
+namespace {
+struct Struct16B {
+  alignas(16) void *X;
+};
+}
+static_assert(sizeof(SmallVector<void *, 0>) ==
+                  sizeof(unsigned) * 2 + sizeof(void *),
+              "wasted space in SmallVector size 0");
+static_assert(alignof(SmallVector<Struct16B, 0>) == 16,
+              "wrong alignment with no small size");
+static_assert(sizeof(SmallVector<Struct16B, 0>) == 16,
+              "missing padding with no small size");
 static_assert(sizeof(SmallVector<void *, 1>) ==
                   sizeof(unsigned) * 2 + sizeof(void *) * 2,
-              "wasted space in SmallVector size 1; missing EBO?");
+              "wasted space in SmallVector size 1");
 
 /// 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 MinCapacity,
                                size_t TSize) {
   // Ensure we can fit the new capacity in 32 bits.
   if (MinCapacity > UINT32_MAX)
     report_bad_alloc_error("SmallVector capacity overflow during allocation");