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

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 size 0 by the larger of sizeof(void*) and sizeof(T),
and we're not even using the storage.

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.

llvm-svn: 337820

1 files changed, 21 insertions, 2 deletions

diff --git a/llvm/lib/Support/SmallVector.cpp b/llvm/lib/Support/SmallVector.cpp
index 7208572d08d..1070c6672ed 100644
--- a/llvm/lib/Support/SmallVector.cpp
+++ b/llvm/lib/Support/SmallVector.cpp
@@ -14,10 +14,29 @@
 #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;
+};
+struct Struct32B {
+  alignas(32) 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>) >= alignof(Struct16B),
+              "wrong alignment for 16-byte aligned T");
+static_assert(alignof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
+              "wrong alignment for 32-byte aligned T");
+static_assert(sizeof(SmallVector<Struct16B, 0>) >= alignof(Struct16B),
+              "missing padding for 16-byte aligned T");
+static_assert(sizeof(SmallVector<Struct32B, 0>) >= alignof(Struct32B),
+              "missing padding for 32-byte aligned T");
 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.