Perform dynamic alignment computations so that the data in TypeLocs is

correctly aligned.  Not performing such computations led to misaligned loads,
which crash on some platforms and are generally bad on other platforms.

The implementation of TypeLocBuilder::pushImpl is rather messy; code using
TypeLocBuilder accidentally assumes that partial TypeLocs are
laid out like a complete TypeLoc.  As a followup, I intend to work on
fixing the TypeLocBuilder API to avoid exposing partial TypeLocs; this should
substantially simplify the implemementation.

Fixes PR16144.

llvm-svn: 183466

7 files changed, 197 insertions, 85 deletions

diff --git a/clang/lib/AST/TypeLoc.cpp b/clang/lib/AST/TypeLoc.cpp
index 03d40309f53..c47bde8ddec 100644
--- a/clang/lib/AST/TypeLoc.cpp
+++ b/clang/lib/AST/TypeLoc.cpp
@@ -41,12 +41,30 @@ SourceRange TypeLoc::getLocalSourceRangeImpl(TypeLoc TL) {
 }
 
 namespace {
+  class TypeAligner : public TypeLocVisitor<TypeAligner, unsigned> {
+  public:
+#define ABSTRACT_TYPELOC(CLASS, PARENT)
+#define TYPELOC(CLASS, PARENT) \
+    unsigned Visit##CLASS##TypeLoc(CLASS##TypeLoc TyLoc) { \
+      return TyLoc.getLocalDataAlignment(); \
+    }
+#include "clang/AST/TypeLocNodes.def"
+  };
+}
+
+/// \brief Returns the alignment of the type source info data block.
+unsigned TypeLoc::getLocalAlignmentForType(QualType Ty) {
+  if (Ty.isNull()) return 1;
+  return TypeAligner().Visit(TypeLoc(Ty, 0));
+}
+
+namespace {
   class TypeSizer : public TypeLocVisitor<TypeSizer, unsigned> {
   public:
 #define ABSTRACT_TYPELOC(CLASS, PARENT)
 #define TYPELOC(CLASS, PARENT) \
     unsigned Visit##CLASS##TypeLoc(CLASS##TypeLoc TyLoc) { \
-      return TyLoc.getFullDataSize(); \
+      return TyLoc.getLocalDataSize(); \
     }
 #include "clang/AST/TypeLocNodes.def"
   };
@@ -54,8 +72,18 @@ namespace {
 
 /// \brief Returns the size of the type source info data block.
 unsigned TypeLoc::getFullDataSizeForType(QualType Ty) {
-  if (Ty.isNull()) return 0;
-  return TypeSizer().Visit(TypeLoc(Ty, 0));
+  unsigned Total = 0;
+  TypeLoc TyLoc(Ty, 0);
+  unsigned MaxAlign = 1;
+  while (!TyLoc.isNull()) {
+    unsigned Align = getLocalAlignmentForType(TyLoc.getType());
+    MaxAlign = std::max(Align, MaxAlign);
+    Total = llvm::RoundUpToAlignment(Total, Align);
+    Total += TypeSizer().Visit(TyLoc);
+    TyLoc = TyLoc.getNextTypeLoc();
+  }
+  Total = llvm::RoundUpToAlignment(Total, MaxAlign);
+  return Total;
 }
 
 namespace {
diff --git a/clang/lib/Sema/CMakeLists.txt b/clang/lib/Sema/CMakeLists.txt
index e92f7671342..836d1259785 100644
--- a/clang/lib/Sema/CMakeLists.txt
+++ b/clang/lib/Sema/CMakeLists.txt
@@ -51,6 +51,7 @@ add_clang_library(clangSema
   SemaTemplateVariadic.cpp
   SemaType.cpp
   TargetAttributesSema.cpp
+  TypeLocBuilder.cpp
   )
 
 add_dependencies(clangSema
diff --git a/clang/lib/Sema/SemaLambda.cpp b/clang/lib/Sema/SemaLambda.cpp
index d647be37616..3402f220625 100644
--- a/clang/lib/Sema/SemaLambda.cpp
+++ b/clang/lib/Sema/SemaLambda.cpp
@@ -445,6 +445,7 @@ FieldDecl *Sema::checkInitCapture(SourceLocation Loc, bool ByRef,
     assert(!DeductType.isNull() && "can't build reference to auto");
     TLB.push<ReferenceTypeLoc>(DeductType).setSigilLoc(Loc);
   }
+  TypeSourceInfo *TSI = TLB.getTypeSourceInfo(Context, DeductType);
 
   InitializationKind InitKind = InitializationKind::CreateDefault(Loc);
   Expr *Init = InitExpr;
@@ -476,8 +477,7 @@ FieldDecl *Sema::checkInitCapture(SourceLocation Loc, bool ByRef,
   else
     InitKind = InitializationKind::CreateCopy(Loc, Loc);
   QualType DeducedType;
-  if (DeduceAutoType(TLB.getTemporaryTypeLoc(DeductType),
-                     Init, DeducedType) == DAR_Failed) {
+  if (DeduceAutoType(TSI, Init, DeducedType) == DAR_Failed) {
     if (isa<InitListExpr>(Init))
       Diag(Loc, diag::err_init_capture_deduction_failure_from_init_list)
           << Id << Init->getSourceRange();
@@ -492,7 +492,7 @@ FieldDecl *Sema::checkInitCapture(SourceLocation Loc, bool ByRef,
   //   the closure type. This member is not a bit-field and not mutable.
   // Core issue: the member is (probably...) public.
   FieldDecl *NewFD = CheckFieldDecl(
-      Id, DeducedType, TLB.getTypeSourceInfo(Context, DeductType), LSI->Lambda,
+      Id, DeducedType, TSI, LSI->Lambda,
       Loc, /*Mutable*/ false, /*BitWidth*/ 0, ICIS_NoInit,
       Loc, AS_public, /*PrevDecl*/ 0, /*Declarator*/ 0);
   LSI->Lambda->addDecl(NewFD);
diff --git a/clang/lib/Sema/SemaTemplateVariadic.cpp b/clang/lib/Sema/SemaTemplateVariadic.cpp
index 3b8228016c5..cb6f4c19de0 100644
--- a/clang/lib/Sema/SemaTemplateVariadic.cpp
+++ b/clang/lib/Sema/SemaTemplateVariadic.cpp
@@ -18,6 +18,7 @@
 #include "clang/Sema/ScopeInfo.h"
 #include "clang/Sema/SemaInternal.h"
 #include "clang/Sema/Template.h"
+#include "TypeLocBuilder.h"
 
 using namespace clang;
 
@@ -463,17 +464,13 @@ Sema::CheckPackExpansion(TypeSourceInfo *Pattern, SourceLocation EllipsisLoc,
                                        EllipsisLoc, NumExpansions);
   if (Result.isNull())
     return 0;
-  
-  TypeSourceInfo *TSResult = Context.CreateTypeSourceInfo(Result);
-  PackExpansionTypeLoc TL =
-      TSResult->getTypeLoc().castAs<PackExpansionTypeLoc>();
+
+  TypeLocBuilder TLB;
+  TLB.pushFullCopy(Pattern->getTypeLoc());
+  PackExpansionTypeLoc TL = TLB.push<PackExpansionTypeLoc>(Result);
   TL.setEllipsisLoc(EllipsisLoc);
-  
-  // Copy over the source-location information from the type.
-  memcpy(TL.getNextTypeLoc().getOpaqueData(),
-         Pattern->getTypeLoc().getOpaqueData(),
-         Pattern->getTypeLoc().getFullDataSize());
-  return TSResult;
+
+  return TLB.getTypeSourceInfo(Context, Result);
 }
 
 QualType Sema::CheckPackExpansion(QualType Pattern, SourceRange PatternRange,
diff --git a/clang/lib/Sema/TreeTransform.h b/clang/lib/Sema/TreeTransform.h
index 4ebcfa292f2..7d225cc7922 100644
--- a/clang/lib/Sema/TreeTransform.h
+++ b/clang/lib/Sema/TreeTransform.h
@@ -3427,7 +3427,7 @@ TreeTransform<Derived>::TransformQualifiedType(TypeLocBuilder &TLB,
       } else {
         // Otherwise, complain about the addition of a qualifier to an
         // already-qualified type.
-        SourceRange R = TLB.getTemporaryTypeLoc(Result).getSourceRange();
+        SourceRange R = T.getUnqualifiedLoc().getSourceRange();
         SemaRef.Diag(R.getBegin(), diag::err_attr_objc_ownership_redundant)
           << Result << R;
 
diff --git a/clang/lib/Sema/TypeLocBuilder.cpp b/clang/lib/Sema/TypeLocBuilder.cpp
new file mode 100644
index 00000000000..c7d43b70469
--- /dev/null
+++ b/clang/lib/Sema/TypeLocBuilder.cpp
@@ -0,0 +1,136 @@
+//===--- TypeLocBuilder.cpp - Type Source Info collector ------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This files defines TypeLocBuilder, a class for building TypeLocs
+//  bottom-up.
+//
+//===----------------------------------------------------------------------===//
+
+#include "TypeLocBuilder.h"
+
+using namespace clang;
+
+void TypeLocBuilder::pushFullCopy(TypeLoc L) {
+  size_t Size = L.getFullDataSize();
+  reserve(Size);
+
+  SmallVector<TypeLoc, 4> TypeLocs;
+  TypeLoc CurTL = L;
+  while (CurTL) {
+    TypeLocs.push_back(CurTL);
+    CurTL = CurTL.getNextTypeLoc();
+  }
+
+  for (unsigned i = 0, e = TypeLocs.size(); i < e; ++i) {
+    TypeLoc CurTL = TypeLocs[e-i-1];
+    switch (CurTL.getTypeLocClass()) {
+#define ABSTRACT_TYPELOC(CLASS, PARENT)
+#define TYPELOC(CLASS, PARENT) \
+    case TypeLoc::CLASS: { \
+      CLASS##TypeLoc NewTL = push<class CLASS##TypeLoc>(CurTL.getType()); \
+      memcpy(NewTL.getOpaqueData(), CurTL.getOpaqueData(), NewTL.getLocalDataSize()); \
+      break; \
+    }
+#include "clang/AST/TypeLocNodes.def"
+    }
+  }
+}
+
+void TypeLocBuilder::grow(size_t NewCapacity) {
+  assert(NewCapacity > Capacity);
+
+  // Allocate the new buffer and copy the old data into it.
+  char *NewBuffer = new char[NewCapacity];
+  unsigned NewIndex = Index + NewCapacity - Capacity;
+  memcpy(&NewBuffer[NewIndex],
+         &Buffer[Index],
+         Capacity - Index);
+
+  if (Buffer != InlineBuffer.buffer)
+    delete[] Buffer;
+
+  Buffer = NewBuffer;
+  Capacity = NewCapacity;
+  Index = NewIndex;
+}
+
+TypeLoc TypeLocBuilder::pushImpl(QualType T, size_t LocalSize, unsigned LocalAlignment) {
+#ifndef NDEBUG
+  QualType TLast = TypeLoc(T, 0).getNextTypeLoc().getType();
+  assert(TLast == LastTy &&
+         "mismatch between last type and new type's inner type");
+  LastTy = T;
+#endif
+
+  assert(LocalAlignment <= BufferMaxAlignment && "Unexpected alignment");
+
+  // If we need to grow, grow by a factor of 2.
+  if (LocalSize > Index) {
+    size_t RequiredCapacity = Capacity + (LocalSize - Index);
+    size_t NewCapacity = Capacity * 2;
+    while (RequiredCapacity > NewCapacity)
+      NewCapacity *= 2;
+    grow(NewCapacity);
+  }
+
+  // Because we're adding elements to the TypeLoc backwards, we have to
+  // do some extra work to keep everything aligned appropriately.
+  // FIXME: This algorithm is a absolute mess because every TypeLoc returned
+  // needs to be valid.  Partial TypeLocs are a terrible idea.
+  // FIXME: 4 and 8 are sufficient at the moment, but it's pretty ugly to
+  // hardcode them.
+  if (LocalAlignment == 4) {
+    if (NumBytesAtAlign8 == 0) {
+      NumBytesAtAlign4 += LocalSize;
+    } else {
+      unsigned Padding = NumBytesAtAlign4 % 8;
+      if (Padding == 0) {
+        if (LocalSize % 8 == 0) {
+          // Everything is set: there's no padding and we don't need to add
+          // any.
+        } else {
+          assert(LocalSize % 8 == 4);
+          // No existing padding; add in 4 bytes padding
+          memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
+          Index -= 4;
+        }
+      } else {
+        assert(Padding == 4);
+        if (LocalSize % 8 == 0) {
+          // Everything is set: there's 4 bytes padding and we don't need
+          // to add any.
+        } else {
+          assert(LocalSize % 8 == 4);
+          // There are 4 bytes padding, but we don't need any; remove it.
+          memmove(&Buffer[Index + 4], &Buffer[Index], NumBytesAtAlign4);
+          Index += 4;
+        }
+      }
+      NumBytesAtAlign4 += LocalSize;
+    }
+  } else if (LocalAlignment == 8) {
+    if (!NumBytesAtAlign8 && NumBytesAtAlign4 % 8 != 0) {
+      // No existing padding and misaligned members; add in 4 bytes padding
+      memmove(&Buffer[Index - 4], &Buffer[Index], NumBytesAtAlign4);
+      Index -= 4;
+    }
+    // Forget about any padding.
+    NumBytesAtAlign4 = 0;
+    NumBytesAtAlign8 += LocalSize;
+  } else {
+    assert(LocalSize == 0);
+  }
+
+  Index -= LocalSize;
+
+  assert(Capacity - Index == TypeLoc::getFullDataSizeForType(T) &&
+         "incorrect data size provided to CreateTypeSourceInfo!");
+
+  return getTemporaryTypeLoc(T);
+}
diff --git a/clang/lib/Sema/TypeLocBuilder.h b/clang/lib/Sema/TypeLocBuilder.h
index f36ec9f3e20..b1e909859b2 100644
--- a/clang/lib/Sema/TypeLocBuilder.h
+++ b/clang/lib/Sema/TypeLocBuilder.h
@@ -39,14 +39,19 @@ class TypeLocBuilder {
 #endif
     
   /// The inline buffer.
-  char InlineBuffer[InlineCapacity];
+  enum { BufferMaxAlignment = llvm::AlignOf<void*>::Alignment };
+  llvm::AlignedCharArray<BufferMaxAlignment, InlineCapacity> InlineBuffer;
+  unsigned NumBytesAtAlign4, NumBytesAtAlign8;
 
  public:
   TypeLocBuilder()
-    : Buffer(InlineBuffer), Capacity(InlineCapacity), Index(InlineCapacity) {}
+    : Buffer(InlineBuffer.buffer), Capacity(InlineCapacity),
+      Index(InlineCapacity), NumBytesAtAlign4(0), NumBytesAtAlign8(0)
+  {
+  }
 
   ~TypeLocBuilder() {
-    if (Buffer != InlineBuffer)
+    if (Buffer != InlineBuffer.buffer)
       delete[] Buffer;
   }
 
@@ -59,23 +64,14 @@ class TypeLocBuilder {
 
   /// Pushes a copy of the given TypeLoc onto this builder.  The builder
   /// must be empty for this to work.
-  void pushFullCopy(TypeLoc L) {
-    size_t Size = L.getFullDataSize();
-    TypeLoc Copy = pushFullUninitializedImpl(L.getType(), Size);
-    memcpy(Copy.getOpaqueData(), L.getOpaqueData(), Size);
-  }
-
-  /// Pushes uninitialized space for the given type.  The builder must
-  /// be empty.
-  TypeLoc pushFullUninitialized(QualType T) {
-    return pushFullUninitializedImpl(T, TypeLoc::getFullDataSizeForType(T));
-  }
+  void pushFullCopy(TypeLoc L);
 
   /// Pushes space for a typespec TypeLoc.  Invalidates any TypeLocs
   /// previously retrieved from this builder.
   TypeSpecTypeLoc pushTypeSpec(QualType T) {
     size_t LocalSize = TypeSpecTypeLoc::LocalDataSize;
-    return pushImpl(T, LocalSize).castAs<TypeSpecTypeLoc>();
+    unsigned LocalAlign = TypeSpecTypeLoc::LocalDataAlignment;
+    return pushImpl(T, LocalSize, LocalAlign).castAs<TypeSpecTypeLoc>();
   }
 
   /// Resets this builder to the newly-initialized state.
@@ -84,6 +80,7 @@ class TypeLocBuilder {
     LastTy = QualType();
 #endif
     Index = Capacity;
+    NumBytesAtAlign4 = NumBytesAtAlign8 = 0;
   }  
 
   /// \brief Tell the TypeLocBuilder that the type it is storing has been
@@ -97,8 +94,10 @@ class TypeLocBuilder {
   /// Pushes space for a new TypeLoc of the given type.  Invalidates
   /// any TypeLocs previously retrieved from this builder.
   template <class TyLocType> TyLocType push(QualType T) {
-    size_t LocalSize = TypeLoc(T, 0).castAs<TyLocType>().getLocalDataSize();
-    return pushImpl(T, LocalSize).castAs<TyLocType>();
+    TyLocType Loc = TypeLoc(T, 0).castAs<TyLocType>();
+    size_t LocalSize = Loc.getLocalDataSize();
+    unsigned LocalAlign = Loc.getLocalDataAlignment();
+    return pushImpl(T, LocalSize, LocalAlign).castAs<TyLocType>();
   }
 
   /// Creates a TypeSourceInfo for the given type.
@@ -127,61 +126,12 @@ class TypeLocBuilder {
   }
 
 private:
-  TypeLoc pushImpl(QualType T, size_t LocalSize) {
-#ifndef NDEBUG
-    QualType TLast = TypeLoc(T, 0).getNextTypeLoc().getType();
-    assert(TLast == LastTy &&
-           "mismatch between last type and new type's inner type");
-    LastTy = T;
-#endif
-
-    // If we need to grow, grow by a factor of 2.
-    if (LocalSize > Index) {
-      size_t RequiredCapacity = Capacity + (LocalSize - Index);
-      size_t NewCapacity = Capacity * 2;
-      while (RequiredCapacity > NewCapacity)
-        NewCapacity *= 2;
-      grow(NewCapacity);
-    }
 
-    Index -= LocalSize;
-
-    return getTemporaryTypeLoc(T);
-  }
+  TypeLoc pushImpl(QualType T, size_t LocalSize, unsigned LocalAlignment);
 
   /// Grow to the given capacity.
-  void grow(size_t NewCapacity) {
-    assert(NewCapacity > Capacity);
-
-    // Allocate the new buffer and copy the old data into it.
-    char *NewBuffer = new char[NewCapacity];
-    unsigned NewIndex = Index + NewCapacity - Capacity;
-    memcpy(&NewBuffer[NewIndex],
-           &Buffer[Index],
-           Capacity - Index);
-
-    if (Buffer != InlineBuffer)
-      delete[] Buffer;
-
-    Buffer = NewBuffer;
-    Capacity = NewCapacity;
-    Index = NewIndex;
-  }
-
-  TypeLoc pushFullUninitializedImpl(QualType T, size_t Size) {
-#ifndef NDEBUG
-    assert(LastTy.isNull() && "pushing full on non-empty TypeLocBuilder");
-    LastTy = T;
-#endif
-    assert(Index == Capacity && "pushing full on non-empty TypeLocBuilder");
-
-    reserve(Size);
-    Index -= Size;
-
-    return getTemporaryTypeLoc(T);
-  }
+  void grow(size_t NewCapacity);
 
-public:
   /// \brief Retrieve a temporary TypeLoc that refers into this \c TypeLocBuilder
   /// object.
   ///