Add support to the alignment support header for conjuring a character

array of a suitable size and alignment for any of a number of different
types to be stored into the character array.

The mechanisms for producing an explicitly aligned type are fairly
complex because this operation is poorly supported on all compilers.
We've spent a fairly significant amount of time experimenting with
different implementations inside of Google, and the one using explicitly
expanded templates has been the most robust.

Credit goes to Nick Lewycky for writing the first 20 versions or so of
this logic we had inside of Google. I based this on the only one to
actually survive. In case anyone is worried, yes we are both explicitly
re-contributing and re-licensing it for LLVM. =]

Once the issues with actually specifying the alignment are finished, it
turns out that most compilers don't in turn align anything the way they
are instructed. Testing of this logic against both Clang and GCC
indicate that the alignment constraints are largely ignored by both
compilers! I've come up with and used a work-around by wrapping each
alignment-hinted type directly in a struct, and using that struct to
align the character array through a union. This elaborate hackery is
terrifying, but I've included testing that caught a terrifying number of
bugs in every other technique I've tried.

All of this in order to implement a poor C++98 programmers emulation of
C++11 unrestricted unions in classes such as SmallDenseMap.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158597 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 249 insertions, 0 deletions

diff --git a/unittests/CMakeLists.txt b/unittests/CMakeLists.txt
index 11a5a5ac97..bfb05edade 100644
--- a/unittests/CMakeLists.txt
+++ b/unittests/CMakeLists.txt
@@ -166,6 +166,7 @@ set(LLVM_LINK_COMPONENTS
   )
 
 add_llvm_unittest(Support
+  Support/AlignOfTest.cpp
   Support/AllocatorTest.cpp
   Support/Casting.cpp
   Support/CommandLineTest.cpp
diff --git a/unittests/Support/AlignOfTest.cpp b/unittests/Support/AlignOfTest.cpp
new file mode 100644
index 0000000000..b86f2bd9c5
--- /dev/null
+++ b/unittests/Support/AlignOfTest.cpp
@@ -0,0 +1,248 @@
+//===- llvm/unittest/Support/AlignOfTest.cpp - Alignment utility tests ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Support/AlignOf.h"
+#include "llvm/Support/Compiler.h"
+
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+// Define some fixed alignment types to use in these tests.
+#if __cplusplus == 201103L || __has_feature(cxx_alignas)
+typedef char alignas(1) A1;
+typedef char alignas(2) A2;
+typedef char alignas(4) A4;
+typedef char alignas(8) A8;
+#elif defined(__clang__) || defined(__GNUC__)
+typedef char A1 __attribute__((aligned(1)));
+typedef char A2 __attribute__((aligned(2)));
+typedef char A4 __attribute__((aligned(4)));
+typedef char A8 __attribute__((aligned(8)));
+#elif defined(_MSC_VER)
+typedef __declspec(align(1)) char A1;
+typedef __declspec(align(2)) char A2;
+typedef __declspec(align(4)) char A4;
+typedef __declspec(align(8)) char A8;
+#else
+# error No supported align as directive.
+#endif
+
+// Wrap the forced aligned types in structs to hack around compiler bugs.
+struct SA1 { A1 a; };
+struct SA2 { A2 a; };
+struct SA4 { A4 a; };
+struct SA8 { A8 a; };
+
+struct S1 {};
+struct S2 { char a; };
+struct S3 { int x; };
+struct S4 { double y; };
+struct S5 { A1 a1; A2 a2; A4 a4; A8 a8; };
+struct S6 { double f(); };
+struct D1 : S1 {};
+struct D2 : S6 { float g(); };
+struct D3 : S2 {};
+struct D4 : S2 { int x; };
+struct D5 : S3 { char c; };
+struct D6 : S2, S3 {};
+struct D7 : S1, S3 {};
+struct D8 : S1, D4, D5 { double x[2]; };
+struct D9 : S1, D1 { S1 s1; };
+struct V1 { virtual ~V1(); };
+struct V2 { int x; virtual ~V2(); };
+struct V3 : V1 { virtual ~V3(); };
+struct V4 : virtual V2 { int y; virtual ~V4(); };
+struct V5 : V4, V3 { double z; virtual ~V5(); };
+struct V6 : S1 { virtual ~V6(); };
+struct V7 : virtual V2, virtual V6 { virtual ~V7(); };
+struct V8 : V5, virtual V6, V7 { double zz; virtual ~V8(); };
+
+// Ensure alignment is a compile-time constant.
+char LLVM_ATTRIBUTE_UNUSED test_arr
+  [AlignOf<char>::Alignment]
+  [AlignOf<short>::Alignment]
+  [AlignOf<int>::Alignment]
+  [AlignOf<long>::Alignment]
+  [AlignOf<long long>::Alignment]
+  [AlignOf<float>::Alignment]
+  [AlignOf<double>::Alignment]
+  [AlignOf<long double>::Alignment]
+  [AlignOf<void *>::Alignment]
+  [AlignOf<int *>::Alignment]
+  [AlignOf<double (*)(double)>::Alignment]
+  [AlignOf<double (S6::*)()>::Alignment]
+  [AlignOf<A1>::Alignment]
+  [AlignOf<A2>::Alignment]
+  [AlignOf<A4>::Alignment]
+  [AlignOf<A8>::Alignment]
+  [AlignOf<SA1>::Alignment]
+  [AlignOf<SA2>::Alignment]
+  [AlignOf<SA4>::Alignment]
+  [AlignOf<SA8>::Alignment]
+  [AlignOf<S1>::Alignment]
+  [AlignOf<S2>::Alignment]
+  [AlignOf<S3>::Alignment]
+  [AlignOf<S4>::Alignment]
+  [AlignOf<S5>::Alignment]
+  [AlignOf<S6>::Alignment]
+  [AlignOf<D1>::Alignment]
+  [AlignOf<D2>::Alignment]
+  [AlignOf<D3>::Alignment]
+  [AlignOf<D4>::Alignment]
+  [AlignOf<D5>::Alignment]
+  [AlignOf<D6>::Alignment]
+  [AlignOf<D7>::Alignment]
+  [AlignOf<D8>::Alignment]
+  [AlignOf<D9>::Alignment]
+  [AlignOf<V1>::Alignment]
+  [AlignOf<V2>::Alignment]
+  [AlignOf<V3>::Alignment]
+  [AlignOf<V4>::Alignment]
+  [AlignOf<V5>::Alignment]
+  [AlignOf<V6>::Alignment]
+  [AlignOf<V7>::Alignment]
+  [AlignOf<V8>::Alignment];
+
+TEST(AlignOfTest, BasicAlignmentInvariants) {
+  // For a very strange reason, many compilers do not support this. Both Clang
+  // and GCC fail to align these properly.
+  EXPECT_EQ(1u, alignOf<A1>());
+#if 0
+  EXPECT_EQ(2u, alignOf<A2>());
+  EXPECT_EQ(4u, alignOf<A4>());
+  EXPECT_EQ(8u, alignOf<A8>());
+#endif
+
+  // But once wrapped in structs, the alignment is correctly managed.
+  EXPECT_LE(1u, alignOf<SA1>());
+  EXPECT_LE(2u, alignOf<SA2>());
+  EXPECT_LE(4u, alignOf<SA4>());
+  EXPECT_LE(8u, alignOf<SA8>());
+
+  EXPECT_EQ(1u, alignOf<char>());
+  EXPECT_LE(alignOf<char>(),   alignOf<short>());
+  EXPECT_LE(alignOf<short>(),  alignOf<int>());
+  EXPECT_LE(alignOf<int>(),    alignOf<long>());
+  EXPECT_LE(alignOf<long>(),   alignOf<long long>());
+  EXPECT_LE(alignOf<char>(),   alignOf<float>());
+  EXPECT_LE(alignOf<float>(),  alignOf<double>());
+  EXPECT_LE(alignOf<double>(), alignOf<long double>());
+  EXPECT_LE(alignOf<char>(),   alignOf<void *>());
+  EXPECT_EQ(alignOf<void *>(), alignOf<int *>());
+  EXPECT_LE(alignOf<char>(),   alignOf<S1>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<S2>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<S3>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<S4>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<S5>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<S6>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D1>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D2>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D3>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D4>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D5>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D6>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D7>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D8>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<D9>());
+  EXPECT_LE(alignOf<S1>(),     alignOf<V1>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V2>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V3>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V4>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V5>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V6>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V7>());
+  EXPECT_LE(alignOf<V1>(),     alignOf<V8>());
+}
+
+TEST(AlignOfTest, BasicAlignedArray) {
+  // Note: this code exclusively uses the struct-wrapped arbitrarily aligned
+  // types because of the bugs mentioned above where GCC and Clang both
+  // disregard the arbitrary alignment specifier until the type is used to
+  // declare a member of a struct.
+  EXPECT_LE(1u, alignOf<AlignedCharArray<SA1>::union_type>());
+  EXPECT_LE(2u, alignOf<AlignedCharArray<SA2>::union_type>());
+  EXPECT_LE(4u, alignOf<AlignedCharArray<SA4>::union_type>());
+  EXPECT_LE(8u, alignOf<AlignedCharArray<SA8>::union_type>());
+
+  EXPECT_LE(1u, sizeof(AlignedCharArray<SA1>::union_type));
+  EXPECT_LE(2u, sizeof(AlignedCharArray<SA2>::union_type));
+  EXPECT_LE(4u, sizeof(AlignedCharArray<SA4>::union_type));
+  EXPECT_LE(8u, sizeof(AlignedCharArray<SA8>::union_type));
+
+  EXPECT_EQ(1u, (alignOf<AlignedCharArray<SA1>::union_type>()));
+  EXPECT_EQ(2u, (alignOf<AlignedCharArray<SA1, SA2>::union_type>()));
+  EXPECT_EQ(4u, (alignOf<AlignedCharArray<SA1, SA2, SA4>::union_type>()));
+  EXPECT_EQ(8u, (alignOf<AlignedCharArray<SA1, SA2, SA4, SA8>::union_type>()));
+
+  EXPECT_EQ(1u, sizeof(AlignedCharArray<SA1>::union_type));
+  EXPECT_EQ(2u, sizeof(AlignedCharArray<SA1, SA2>::union_type));
+  EXPECT_EQ(4u, sizeof(AlignedCharArray<SA1, SA2, SA4>::union_type));
+  EXPECT_EQ(8u, sizeof(AlignedCharArray<SA1, SA2, SA4, SA8>::union_type));
+
+  EXPECT_EQ(1u, (alignOf<AlignedCharArray<SA1[1]>::union_type>()));
+  EXPECT_EQ(2u, (alignOf<AlignedCharArray<SA1[2], SA2[1]>::union_type>()));
+  EXPECT_EQ(4u, (alignOf<AlignedCharArray<SA1[42], SA2[55],
+                                          SA4[13]>::union_type>()));
+  EXPECT_EQ(8u, (alignOf<AlignedCharArray<SA1[2], SA2[1],
+                                          SA4, SA8>::union_type>()));
+
+  EXPECT_EQ(1u,  sizeof(AlignedCharArray<SA1[1]>::union_type));
+  EXPECT_EQ(2u,  sizeof(AlignedCharArray<SA1[2], SA2[1]>::union_type));
+  EXPECT_EQ(4u,  sizeof(AlignedCharArray<SA1[3], SA2[2], SA4>::union_type));
+  EXPECT_EQ(16u, sizeof(AlignedCharArray<SA1, SA2[3],
+                                         SA4[3], SA8>::union_type));
+
+  // For other tests we simply assert that the alignment of the union mathes
+  // that of the fundamental type and hope that we have any weird type
+  // productions that would trigger bugs.
+  EXPECT_EQ(alignOf<char>(), alignOf<AlignedCharArray<char>::union_type>());
+  EXPECT_EQ(alignOf<short>(), alignOf<AlignedCharArray<short>::union_type>());
+  EXPECT_EQ(alignOf<int>(), alignOf<AlignedCharArray<int>::union_type>());
+  EXPECT_EQ(alignOf<long>(), alignOf<AlignedCharArray<long>::union_type>());
+  EXPECT_EQ(alignOf<long long>(),
+            alignOf<AlignedCharArray<long long>::union_type>());
+  EXPECT_EQ(alignOf<float>(), alignOf<AlignedCharArray<float>::union_type>());
+  EXPECT_EQ(alignOf<double>(), alignOf<AlignedCharArray<double>::union_type>());
+  EXPECT_EQ(alignOf<long double>(),
+            alignOf<AlignedCharArray<long double>::union_type>());
+  EXPECT_EQ(alignOf<void *>(), alignOf<AlignedCharArray<void *>::union_type>());
+  EXPECT_EQ(alignOf<int *>(), alignOf<AlignedCharArray<int *>::union_type>());
+  EXPECT_EQ(alignOf<double (*)(double)>(),
+            alignOf<AlignedCharArray<double (*)(double)>::union_type>());
+  EXPECT_EQ(alignOf<double (S6::*)()>(),
+            alignOf<AlignedCharArray<double (S6::*)()>::union_type>());
+  EXPECT_EQ(alignOf<S1>(), alignOf<AlignedCharArray<S1>::union_type>());
+  EXPECT_EQ(alignOf<S2>(), alignOf<AlignedCharArray<S2>::union_type>());
+  EXPECT_EQ(alignOf<S3>(), alignOf<AlignedCharArray<S3>::union_type>());
+  EXPECT_EQ(alignOf<S4>(), alignOf<AlignedCharArray<S4>::union_type>());
+  EXPECT_EQ(alignOf<S5>(), alignOf<AlignedCharArray<S5>::union_type>());
+  EXPECT_EQ(alignOf<S6>(), alignOf<AlignedCharArray<S6>::union_type>());
+  EXPECT_EQ(alignOf<D1>(), alignOf<AlignedCharArray<D1>::union_type>());
+  EXPECT_EQ(alignOf<D2>(), alignOf<AlignedCharArray<D2>::union_type>());
+  EXPECT_EQ(alignOf<D3>(), alignOf<AlignedCharArray<D3>::union_type>());
+  EXPECT_EQ(alignOf<D4>(), alignOf<AlignedCharArray<D4>::union_type>());
+  EXPECT_EQ(alignOf<D5>(), alignOf<AlignedCharArray<D5>::union_type>());
+  EXPECT_EQ(alignOf<D6>(), alignOf<AlignedCharArray<D6>::union_type>());
+  EXPECT_EQ(alignOf<D7>(), alignOf<AlignedCharArray<D7>::union_type>());
+  EXPECT_EQ(alignOf<D8>(), alignOf<AlignedCharArray<D8>::union_type>());
+  EXPECT_EQ(alignOf<D9>(), alignOf<AlignedCharArray<D9>::union_type>());
+  EXPECT_EQ(alignOf<V1>(), alignOf<AlignedCharArray<V1>::union_type>());
+  EXPECT_EQ(alignOf<V2>(), alignOf<AlignedCharArray<V2>::union_type>());
+  EXPECT_EQ(alignOf<V3>(), alignOf<AlignedCharArray<V3>::union_type>());
+  EXPECT_EQ(alignOf<V4>(), alignOf<AlignedCharArray<V4>::union_type>());
+  EXPECT_EQ(alignOf<V5>(), alignOf<AlignedCharArray<V5>::union_type>());
+  EXPECT_EQ(alignOf<V6>(), alignOf<AlignedCharArray<V6>::union_type>());
+  EXPECT_EQ(alignOf<V7>(), alignOf<AlignedCharArray<V7>::union_type>());
+  EXPECT_EQ(alignOf<V8>(), alignOf<AlignedCharArray<V8>::union_type>());
+}
+
+}