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

1 files changed, 90 insertions, 0 deletions

diff --git a/include/llvm/Support/AlignOf.h b/include/llvm/Support/AlignOf.h
index cebfa79..b63e75f 100644
--- a/include/llvm/Support/AlignOf.h
+++ b/include/llvm/Support/AlignOf.h
@@ -15,6 +15,9 @@
 #ifndef LLVM_SUPPORT_ALIGNOF_H
 #define LLVM_SUPPORT_ALIGNOF_H
 
+#include "llvm/Support/Compiler.h"
+#include <cstddef>
+
 namespace llvm {
 
 template <typename T>
@@ -56,5 +59,92 @@ struct AlignOf {
 template <typename T>
 static inline unsigned alignOf() { return AlignOf<T>::Alignment; }
 
+
+/// \brief Helper for building an aligned character array type.
+///
+/// This template is used to explicitly build up a collection of aligned
+/// character types. We have to build these up using a macro and explicit
+/// specialization to cope with old versions of MSVC and GCC where only an
+/// integer literal can be used to specify an alignment constraint. Once built
+/// up here, we can then begin to indirect between these using normal C++
+/// template parameters.
+template <size_t Alignment> struct AlignedCharArrayImpl {};
+template <> struct AlignedCharArrayImpl<0> {
+  typedef char type;
+};
+#if __cplusplus == 201103L || __has_feature(cxx_alignas)
+#define LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(x) \
+  template <> struct AlignedCharArrayImpl<x> { \
+    typedef char alignas(x) type; \
+  }
+#elif defined(__clang__) || defined(__GNUC__)
+#define LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(x) \
+  template <> struct AlignedCharArrayImpl<x> { \
+    typedef char type __attribute__((aligned(x))); \
+  }
+#elif defined(_MSC_VER)
+#define LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(x) \
+  template <> struct AlignedCharArrayImpl<x> { \
+    typedef __declspec(align(x)) char type; \
+  }
+#else
+# error No supported align as directive.
+#endif
+
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(1);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(2);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(4);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(8);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(16);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(32);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(64);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(128);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(512);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(1024);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(2048);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(4096);
+LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT(8192);
+// Any larger and MSVC complains.
+#undef LLVM_ALIGNEDCHARARRAY_TEMPLATE_ALIGNMENT
+
+/// \brief This class template exposes a typedef for type containing a suitable
+/// aligned character array to hold elements of any of up to four types.
+///
+/// These types may be arrays, structs, or any other types. The goal is to
+/// produce a union type containing a character array which, when used, forms
+/// storage suitable to placement new any of these types over. Support for more
+/// than four types can be added at the cost of more boiler plate.
+template <typename T1,
+          typename T2 = char, typename T3 = char, typename T4 = char>
+class AlignedCharArray {
+  class AlignerImpl {
+    T1 t1; T2 t2; T3 t3; T4 t4;
+
+    AlignerImpl(); // Never defined or instantiated.
+  };
+  union SizerImpl {
+    char arr1[sizeof(T1)], arr2[sizeof(T2)], arr3[sizeof(T3)], arr4[sizeof(T4)];
+  };
+
+public:
+  // Sadly, Clang and GCC both fail to align a character array properly even
+  // with an explicit alignment attribute. To work around this, we union
+  // the character array that will actually be used with a struct that contains
+  // a single aligned character member. Tests seem to indicate that both Clang
+  // and GCC will properly register the alignment of a struct containing an
+  // aligned member, and this alignment should carry over to the character
+  // array in the union.
+  union union_type {
+    // This is the only member of the union which should be used by clients:
+    char buffer[sizeof(SizerImpl)];
+
+    // This member of the union only exists to force the alignment.
+    struct {
+      typename llvm::AlignedCharArrayImpl<AlignOf<AlignerImpl>::Alignment>::type
+        nonce_inner_member;
+    } nonce_member;
+  };
+};
+
 } // end namespace llvm
 #endif