Rewrite ConstStructBuilder with a mechanism that can cope with splitting and updating constants.

[rsmith]

Summary

This adds a ConstantBuilder class that deals with incrementally building
an aggregate constant, including support for overwriting
previously-emitted parts of the aggregate with new values.

This fixes a bunch of cases where we used to be unable to reduce a
DesignatedInitUpdateExpr down to an IR constant, and also lays some
groundwork for emission of class constants with [[no_unique_address]]
members.

[rjmccall]

Isn't [[no_unique_address]] only significant for empty members? I'm not sure why they need significant support from constant-building, since they expand to no meaningful initializer.

We have some code we'll hopefully be upstreaming soon that relies on being able to do things with address-of-position placeholder values; I'm a little worried that the new structure here doesn't really support them.

[rsmith]

In D63371#1546500, @rjmccall wrote:

Isn't [[no_unique_address]] only significant for empty members? I'm not sure why they need significant support from constant-building, since they expand to no meaningful initializer.

It also permits reuse of tail padding for non-static data members, which is the complexity that this patch is dealing with (in addition to improving and generalizing the support for non-trivial designated initializers).

We have some code we'll hopefully be upstreaming soon that relies on being able to do things with address-of-position placeholder values; I'm a little worried that the new structure here doesn't really support them.

Can you say a bit more about that? (Do you want to be able to emit a constant that denotes a pointer to somewhere else within the same constant being emitted, or something like that?) I think this approach should be strictly more general than what we had before, but perhaps that means it can't be extended in the direction you need?

[rjmccall]

In D63371#1546587, @rsmith wrote:

In D63371#1546500, @rjmccall wrote:

Isn't [[no_unique_address]] only significant for empty members? I'm not sure why they need significant support from constant-building, since they expand to no meaningful initializer.

It also permits reuse of tail padding for non-static data members, which is the complexity that this patch is dealing with (in addition to improving and generalizing the support for non-trivial designated initializers).

I see.

We have some code we'll hopefully be upstreaming soon that relies on being able to do things with address-of-position placeholder values; I'm a little worried that the new structure here doesn't really support them.

Can you say a bit more about that? (Do you want to be able to emit a constant that denotes a pointer to somewhere else within the same constant being emitted, or something like that?) I think this approach should be strictly more general than what we had before, but perhaps that means it can't be extended in the direction you need?

We need to be able to construct constant initializers for certain fields in terms of (among other things) a pointer to the current field. My concern was whether this might mess up the indexing to the current field; but it looks like we actually discover the right GEP indices retroactively for these aggregate constants (unlike e.g. ConstantInitBuilder), so the fact that the GEP indices might change as we build the constant is not a problem. As long as the ConstantEmitter is being passed around and used to build the individual fields appropriately, it should be fine.

[rjmccall]

lib/CodeGen/CGExprConstant.cpp

73

This seems like a very generic name for this type.

75

Are there invariants about these? I assume they're parallel arrays; are they kept sorted?

76

This is one past the last byte that's been covered by an actual Constant* value, or does it include unoccupied padding, or does it exclude even occupied padding?

98

Might be worth clarifying what N is here.

190

AllowOversized (which you used in the interface) seems like a better name.

196

OffsetWithinChar?

201

OffsetInChars?

237

Especially in the context of the comment above, I think it would be good to clarify that both of these are hard "we can't emit this constant" bail-outs.

258

Oh, because we're splitting before and after a single-CharUnits range? That seems worthy of a somewhat clearer explanation in the code.

I guess we could have a non-ConstantInt single-byte value. Unlikely but not impossible. :)

375

Does this not come up all the time with bit-fields? I guess we emit them in single-char chunks, so it wouldn't. Probably worth a comment.

[rsmith]

• Address review comments from rjmccall.

lib/CodeGen/CGExprConstant.cpp

73

It is intended to be a very generic type. (I was trying to arrange it so that it could possibly be moved to LLVM eventually. I heard that globalopt would benefit from being able to do this kind of constant splitting / reforming.) Is ConstantAggregateBuilder sufficiently more precise?

75

Added comments to explain.

76

Added comment to explain.

98

Looks like this ended up being unused; removed.

190

AllowOversized is used to mean "the size of the constant may be larger than the size of the type", and is a parameter to build / buildFrom.
AllowOverwrite is used to mean "adding this constant may overwrite something you've already been given", and is a parameter to add / addBits.

I can make these names more different from each other if that would help?

258

Yes. It's not too hard to craft a testcase where we'd get an explicit undef here; added handling for that and for all-zeroes constants, which are both correctly handled by overwriting the whole byte.

375

Done.

We could hit this case for cases such as:

union U { int a; int b : 3; };
struct S { U u; };
S s = {(union U){1234}, .u.b = 5};

(which CodeGen currently rejects with "cannot compile this static initializer yet" in C), and splitting the ConstantInt would allow us to emit that initializer as a constant, but I'm not sure it's worthwhile unless it lets us simplify or improve bitfield emission in general. (The above isn't a case that C requires us to treat as a constant initializer, so rejecting it is not a conformance issue.)

Maybe instead of splitting bitfields into 1-byte chunks like we currently do, we should try to combine them into a single iN, like CGRecordLayoutBuilder does. But splitting to i8 maintains the status quo, which is what I was aiming for in this patch.

[rsmith]

• Fix somewhat-incorrect comment on Size member.

[efriedma]

lib/CodeGen/CGExprConstant.cpp

992

Like the comment here says, we're awfully close to being able to just completely kill off ConstExprEmitter etc. Do we really want to continue to invest effort into this code?

[rsmith]

lib/CodeGen/CGExprConstant.cpp

992

The new code is also the mechanism by which we emit APValue constants, which is the replacement for ConstExprEmitter.

Also I don't think we have a fix for the performance issues we saw from performing frontend evaluation of large InitListExprs yet, which is another blocker for removing ConstExprEmitter in favor of APValue emission (though I don't expect that to be a problem forever; APValue is long overdue an overhaul).

[rjmccall]

Minor requests, then LGTM.

lib/CodeGen/CGExprConstant.cpp

73

Yeah, that makes sense, since it aligns with the LLVM type name. I guess the big blocker there is the lack of a CharUnits equivalent in LLVM.

162

Can these go to STLExtras or somewhere similar?

190

Oh, oops. No, sorry, no need to do anything here.

221

Should this be BitsThisChar for consistency?

258

Ah, yeah, good catch; I was thinking it was okay to be suboptimal if we saw a <1 x i8> or a 1-byte pointer or whatever, but undef and zero are definitely worth covering here.

375

I'm fine with single-byte emission for constant bit-fields; ugliness here shouldn't really have significant consequences. The comment is good enough.

[rsmith]

• Address additional review comments from rjmccall.

[rsmith]

lib/CodeGen/CGExprConstant.cpp

162

Done. The use of offsets here is a bit special-case, so I've moved an iterator version to STLExtras and just left an offsets -> iterators adaptor here.

lib/CodeGen/CGExprConstant.cpp

 #include "CodeGenModule.h"
 #include "ConstantEmitter.h"
 #include "TargetInfo.h"
 #include "clang/AST/APValue.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/RecordLayout.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Basic/Builtins.h"
+#include "llvm/ADT/Sequence.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GlobalVariable.h"
 using namespace clang;
 using namespace CodeGen;
 
 //===----------------------------------------------------------------------===//
-//                            ConstStructBuilder
+//                            ConstantAggregateBuilder
 //===----------------------------------------------------------------------===//
 
 namespace {
 class ConstExprEmitter;
-class ConstStructBuilder {
-  CodeGenModule &CGM;
-  ConstantEmitter &Emitter;
 
-  bool Packed;
-  CharUnits NextFieldOffsetInChars;
-  CharUnits LLVMStructAlignment;
-  SmallVector<llvm::Constant *, 32> Elements;
-public:
-  static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
-                                     ConstExprEmitter *ExprEmitter,
-                                     llvm::Constant *Base,
-                                     InitListExpr *Updater,
-                                     QualType ValTy);
-  static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
-                                     InitListExpr *ILE, QualType StructTy);
-  static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
-                                     const APValue &Value, QualType ValTy);
-
-private:
-  ConstStructBuilder(ConstantEmitter &emitter)
-    : CGM(emitter.CGM), Emitter(emitter), Packed(false),
-    NextFieldOffsetInChars(CharUnits::Zero()),
-    LLVMStructAlignment(CharUnits::One()) { }
-
-  void AppendField(const FieldDecl *Field, uint64_t FieldOffset,
-                   llvm::Constant *InitExpr);
-
-  void AppendBytes(CharUnits FieldOffsetInChars, llvm::Constant *InitCst);
-
-  void AppendBitField(const FieldDecl *Field, uint64_t FieldOffset,
-                      llvm::ConstantInt *InitExpr);
-
-  void AppendPadding(CharUnits PadSize);
-
-  void AppendTailPadding(CharUnits RecordSize);
+struct ConstantAggregateBuilderUtils {
+  CodeGenModule &CGM;
 
-  void ConvertStructToPacked();
-
-  bool Build(InitListExpr *ILE);
-  bool Build(ConstExprEmitter *Emitter, llvm::Constant *Base,
-             InitListExpr *Updater);
-  bool Build(const APValue &Val, const RecordDecl *RD, bool IsPrimaryBase,
-             const CXXRecordDecl *VTableClass, CharUnits BaseOffset);
-  llvm::Constant *Finalize(QualType Ty);
+  ConstantAggregateBuilderUtils(CodeGenModule &CGM) : CGM(CGM) {}
 
   CharUnits getAlignment(const llvm::Constant *C) const {
-    if (Packed)  return CharUnits::One();
     return CharUnits::fromQuantity(
         CGM.getDataLayout().getABITypeAlignment(C->getType()));
   }
 
-  CharUnits getSizeInChars(const llvm::Constant *C) const {
-    return CharUnits::fromQuantity(
-        CGM.getDataLayout().getTypeAllocSize(C->getType()));
+  CharUnits getSize(llvm::Type *Ty) const {
+    return CharUnits::fromQuantity(CGM.getDataLayout().getTypeAllocSize(Ty));
   }
-};
 
-void ConstStructBuilder::
-AppendField(const FieldDecl *Field, uint64_t FieldOffset,
-            llvm::Constant *InitCst) {
-  const ASTContext &Context = CGM.getContext();
+  CharUnits getSize(const llvm::Constant *C) const {
+    return getSize(C->getType());
+  }
 
-  CharUnits FieldOffsetInChars = Context.toCharUnitsFromBits(FieldOffset);
+  llvm::Constant *getPadding(CharUnits PadSize) const {
+    llvm::Type *Ty = CGM.Int8Ty;
+    if (PadSize > CharUnits::One())
+      Ty = llvm::ArrayType::get(Ty, PadSize.getQuantity());
+    return llvm::UndefValue::get(Ty);
+  }
 
-  AppendBytes(FieldOffsetInChars, InitCst);
+  llvm::Constant *getZeroes(CharUnits ZeroSize) const {
+    llvm::Type *Ty = llvm::ArrayType::get(CGM.Int8Ty, ZeroSize.getQuantity());
+    return llvm::ConstantAggregateZero::get(Ty);
   }
+};
 
-void ConstStructBuilder::
-AppendBytes(CharUnits FieldOffsetInChars, llvm::Constant *InitCst) {
+/// Incremental builder for an llvm::Constant* holding a struct or array
+/// constant.
+class ConstantAggregateBuilder : private ConstantAggregateBuilderUtils {
+  /// The elements of the constant. These two arrays must have the same size;
+  /// Offsets[i] describes the offset of Elems[i] within the constant. The
+  /// elements are kept in increasing offset order, and we ensure that there
+  /// is no overlap: Offsets[i+1] >= Offsets[i] + getSize(Elemes[i]).
+  ///
+  /// This may contain explicit padding elements (in order to create a
+  /// natural layout), but need not. Gaps between elements are implicitly
+  /// considered to be filled with undef.
+  llvm::SmallVector<llvm::Constant*, 32> Elems;
+  llvm::SmallVector<CharUnits, 32> Offsets;
+  /// The cached size of the constant; equal to Offsets.back() +
+  /// getSize(Elems.back()) (or zero if we have no elements).
+  CharUnits Size = CharUnits::Zero();
+
+  /// This is true only if laying out Elems in order as the elements of a
+  /// non-packed LLVM struct will give the correct layout.
+  bool NaturalLayout = true;
+
+  bool split(size_t Index, CharUnits Hint);
+  Optional<size_t> splitAt(CharUnits Pos);
+
+  static llvm::Constant *buildFrom(CodeGenModule &CGM,
+                                   ArrayRef<llvm::Constant *> Elems,
+                                   ArrayRef<CharUnits> Offsets,
+                                   CharUnits StartOffset, CharUnits Size,
+                                   bool NaturalLayout, llvm::Type *DesiredTy,
+                                   bool AllowOversized);
 
-  assert(NextFieldOffsetInChars <= FieldOffsetInChars
-         && "Field offset mismatch!");
+public:
+  ConstantAggregateBuilder(CodeGenModule &CGM)
+      : ConstantAggregateBuilderUtils(CGM) {}
 
-  CharUnits FieldAlignment = getAlignment(InitCst);
+  /// Update or overwrite the value starting at \p Offset with \c C.
+  ///
+  /// \param AllowOverwrite If \c true, this constant might overwrite (part of)
+  ///        a constant that has already been added. This flag is only used to
+  ///        detect bugs.
+  bool add(llvm::Constant *C, CharUnits Offset, bool AllowOverwrite);
+
+  /// Update or overwrite the bits starting at \p OffsetInBits with \p Bits.
+  bool addBits(llvm::APInt Bits, uint64_t OffsetInBits, bool AllowOverwrite);
+
+  /// Attempt to condense the value starting at \p Offset to a constant of type
+  /// \p DesiredTy.
+  void condense(CharUnits Offset, llvm::Type *DesiredTy);
+
+  /// Produce a constant representing the entire accumulated value, ideally of
+  /// the specified type. If \p AllowOversized, the constant might be larger
+  /// than implied by \p DesiredTy (eg, if there is a flexible array member).
+  /// Otherwise, the constant will be of exactly the same size as \p DesiredTy
+  /// even if we can't represent it as that type.
+  llvm::Constant *build(llvm::Type *DesiredTy, bool AllowOversized) const {
+    return buildFrom(CGM, Elems, Offsets, CharUnits::Zero(), Size,
+                     NaturalLayout, DesiredTy, AllowOversized);
+  }
+};
 
-  // Round up the field offset to the alignment of the field type.
-  CharUnits AlignedNextFieldOffsetInChars =
-      NextFieldOffsetInChars.alignTo(FieldAlignment);
+/// Replace the elements [BeginOff, EndOff) in Vec with [ValIt, ValEnd).
+template<typename Vector, typename RandomAccessIterator>
+static void replace(Vector &Vec, size_t BeginOff, size_t EndOff,
+                    RandomAccessIterator ValIt, RandomAccessIterator ValEnd) {
+  assert(BeginOff <= EndOff && "invalid replacement range");
+  auto ReplaceIt = Vec.begin() + BeginOff, ReplaceEnd = Vec.begin() + EndOff;
+  while (true) {
+    if (ValIt == ValEnd) {
+      Vec.erase(ReplaceIt, ReplaceEnd);
+      return;
+    } else if (ReplaceIt == ReplaceEnd) {
+      Vec.insert(ReplaceIt, ValIt, ValEnd);
+      return;
+    }
+    *ReplaceIt++ = *ValIt++;
+  }
+}
 
-  if (AlignedNextFieldOffsetInChars < FieldOffsetInChars) {
-    // We need to append padding.
-    AppendPadding(FieldOffsetInChars - NextFieldOffsetInChars);
+template<typename Vector>
+static void replace(Vector &V, size_t BeginOff, size_t EndOff,
+                    llvm::ArrayRef<typename Vector::value_type> Vals) {
+  return replace(V, BeginOff, EndOff, Vals.begin(), Vals.end());
+}
 
-    assert(NextFieldOffsetInChars == FieldOffsetInChars &&
-           "Did not add enough padding!");
+template<typename Vector, typename RandomAccessIterator>
+static void replace(Vector &V, size_t BeginOff, size_t EndOff,
+                    llvm::iterator_range<RandomAccessIterator> Vals) {
+  return replace(V, BeginOff, EndOff, Vals.begin(), Vals.end());
+}
 
-    AlignedNextFieldOffsetInChars =
-        NextFieldOffsetInChars.alignTo(FieldAlignment);
+bool ConstantAggregateBuilder::add(llvm::Constant *C, CharUnits Offset,
+                          bool AllowOverwrite) {
+  // Common case: appending to a layout.
+  if (Offset >= Size) {
+    CharUnits Align = getAlignment(C);
+    CharUnits AlignedSize = Size.alignTo(Align);
+    if (AlignedSize > Offset || Offset.alignTo(Align) != Offset)
+      NaturalLayout = false;
+    else if (AlignedSize < Offset) {
+      Elems.push_back(getPadding(Offset - Size));
+      Offsets.push_back(Size);
+    }
+    Elems.push_back(C);
+    Offsets.push_back(Offset);
+    Size = Offset + getSize(C);
+    return true;
   }
 
-  if (AlignedNextFieldOffsetInChars > FieldOffsetInChars) {
-    assert(!Packed && "Alignment is wrong even with a packed struct!");
+  // Uncommon case: constant overlaps what we've already created.
+  llvm::Optional<size_t> FirstElemToReplace = splitAt(Offset);
+  if (!FirstElemToReplace)
+    return false;
 
-    // Convert the struct to a packed struct.
-    ConvertStructToPacked();
+  CharUnits CSize = getSize(C);
+  llvm::Optional<size_t> LastElemToReplace = splitAt(Offset + CSize);
+  if (!LastElemToReplace)
+    return false;
 
-    // After we pack the struct, we may need to insert padding.
-    if (NextFieldOffsetInChars < FieldOffsetInChars) {
-      // We need to append padding.
-      AppendPadding(FieldOffsetInChars - NextFieldOffsetInChars);
+  assert((FirstElemToReplace == LastElemToReplace || AllowOverwrite) &&
+         "unexpectedly overwriting field");
 
-      assert(NextFieldOffsetInChars == FieldOffsetInChars &&
-             "Did not add enough padding!");
-    }
-    AlignedNextFieldOffsetInChars = NextFieldOffsetInChars;
+  replace(Elems, *FirstElemToReplace, *LastElemToReplace, {C});
+  replace(Offsets, *FirstElemToReplace, *LastElemToReplace, {Offset});
+  Size = std::max(Size, Offset + CSize);
+  NaturalLayout = false;
+  return true;
+
+bool ConstantAggregateBuilder::addBits(llvm::APInt Bits, uint64_t OffsetInBits,
+                              bool AllowOverwrite) {
+  const ASTContext &Context = CGM.getContext();
+  const uint64_t CharWidth = CGM.getContext().getCharWidth();
+
+  // Offset of where we want the first bit to go within the bits of the
+  // current char.
+  unsigned OffsetWithinChar = OffsetInBits % CharWidth;
+
+  // We split bit-fields up into individual bytes. Walk over the bytes and
+  // update them.
+  for (CharUnits OffsetInChars = Context.toCharUnitsFromBits(OffsetInBits);
+       /**/; ++OffsetInChars) {
+    // Number of bits we want to fill in this byte.
+    unsigned WantedBits =
+        std::min((uint64_t)Bits.getBitWidth(), CharWidth - OffsetWithinChar);
+
+    // Get a byte containing the bits we want in the right places. The other
+    // bits have unspecified values.
+    llvm::APInt BitsThisByte = Bits;
+    if (BitsThisByte.getBitWidth() < CharWidth)
+      BitsThisByte = BitsThisByte.zext(CharWidth);
+    if (CGM.getDataLayout().isBigEndian()) {
+      // Figure out how much to shift by. We may need to left-shift if we have
+      // less than one byte of Bits left.
+      int Shift = Bits.getBitWidth() - CharWidth + OffsetWithinChar;
+      if (Shift > 0)
+        BitsThisByte.lshrInPlace(Shift);
+      else if (Shift < 0)
+        BitsThisByte = BitsThisByte.shl(-Shift);
+    } else {
+      BitsThisByte = BitsThisByte.shl(OffsetWithinChar);
     }
+    if (BitsThisByte.getBitWidth() > CharWidth)
+      BitsThisByte = BitsThisByte.trunc(CharWidth);
 
-  // Add the field.
-  Elements.push_back(InitCst);
-  NextFieldOffsetInChars = AlignedNextFieldOffsetInChars +
-                           getSizeInChars(InitCst);
+    if (WantedBits == CharWidth) {
+      // Got a full byte: just add it directly.
+      add(llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisByte),
+          OffsetInChars, AllowOverwrite);
+    } else {
+      // Partial byte: update the existing integer if there is one. If we
+      // can't split out a 1-CharUnit range to update, then we can't add
+      // these bits and fail the entire constant emission.
+      llvm::Optional<size_t> FirstElemToUpdate = splitAt(OffsetInChars);
+      if (!FirstElemToUpdate)
+        return false;
+      llvm::Optional<size_t> LastElemToUpdate =
+          splitAt(OffsetInChars + CharUnits::One());
+      if (!LastElemToUpdate)
+        return false;
+      assert(*LastElemToUpdate - *FirstElemToUpdate < 2 &&
+             "should have at most one element covering one byte");
 
-  if (Packed)
-    assert(LLVMStructAlignment == CharUnits::One() &&
-           "Packed struct not byte-aligned!");
+      // Figure out which bits we want and discard the rest.
+      llvm::APInt UpdateMask(CharWidth, 0);
+      if (CGM.getDataLayout().isBigEndian())
+        UpdateMask.setBits(CharWidth - OffsetWithinChar - WantedBits,
+                           CharWidth - OffsetWithinChar);
       else
-    LLVMStructAlignment = std::max(LLVMStructAlignment, FieldAlignment);
+        UpdateMask.setBits(OffsetWithinChar, OffsetWithinChar + WantedBits);
+      BitsThisByte &= UpdateMask;
+
+      if (*FirstElemToUpdate == *LastElemToUpdate ||
+          Elems[*FirstElemToUpdate]->isNullValue() ||
+          isa<llvm::UndefValue>(Elems[*FirstElemToUpdate])) {
+        // All existing bits are either zero or undef.
+        add(llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisByte),
+            OffsetInChars, /*AllowOverwrite*/ true);
+      } else {
+        llvm::Constant *&ToUpdate = Elems[*FirstElemToUpdate];
+        // In order to perform a partial update, we need the existing bitwise
+        // value, which we can only extract for a constant int.
+        auto *CI = dyn_cast<llvm::ConstantInt>(ToUpdate);
+        if (!CI)
+          return false;
+        // Because this is a 1-CharUnit range, the constant occupying it must
+        // be exactly one CharUnit wide.
+        assert(CI->getBitWidth() == CharWidth && "splitAt failed");
+        assert((!(CI->getValue() & UpdateMask) || AllowOverwrite) &&
+               "unexpectedly overwriting bitfield");
+        BitsThisByte |= (CI->getValue() & ~UpdateMask);
+        ToUpdate = llvm::ConstantInt::get(CGM.getLLVMContext(), BitsThisByte);
+      }
     }
 
-void ConstStructBuilder::AppendBitField(const FieldDecl *Field,
-                                        uint64_t FieldOffset,
-                                        llvm::ConstantInt *CI) {
-  const ASTContext &Context = CGM.getContext();
-  const uint64_t CharWidth = Context.getCharWidth();
-  uint64_t NextFieldOffsetInBits = Context.toBits(NextFieldOffsetInChars);
-  if (FieldOffset > NextFieldOffsetInBits) {
-    // We need to add padding.
-    CharUnits PadSize = Context.toCharUnitsFromBits(
-        llvm::alignTo(FieldOffset - NextFieldOffsetInBits,
-                      Context.getTargetInfo().getCharAlign()));
+    // Stop if we've added all the bits.
+    if (WantedBits == Bits.getBitWidth())
+      break;
+
+    // Remove the consumed bits from Bits.
+    if (!CGM.getDataLayout().isBigEndian())
+      Bits.lshrInPlace(WantedBits);
+    Bits = Bits.trunc(Bits.getBitWidth() - WantedBits);
 
-    AppendPadding(PadSize);
+    // The remanining bits go at the start of the following bytes.
+    OffsetWithinChar = 0;
   }
 
-  uint64_t FieldSize = Field->getBitWidthValue(Context);
+  return true;
+}
 
-  llvm::APInt FieldValue = CI->getValue();
+/// Returns a position within Elems and Offsets such that all elements
+/// before the returned index end before Pos and all elements at or after
+/// the returned index begin at or after Pos. Splits elements as necessary
+/// to ensure this. Returns None if we find something we can't split.
+Optional<size_t> ConstantAggregateBuilder::splitAt(CharUnits Pos) {
+  if (Pos >= Size)
+    return Offsets.size();
 
-  // Promote the size of FieldValue if necessary
-  // FIXME: This should never occur, but currently it can because initializer
-  // constants are cast to bool, and because clang is not enforcing bitfield
-  // width limits.
-  if (FieldSize > FieldValue.getBitWidth())
-    FieldValue = FieldValue.zext(FieldSize);
+  while (true) {
+    auto FirstAfterPos = std::upper_bound(Offsets.begin(), Offsets.end(), Pos);
+    if (FirstAfterPos == Offsets.begin())
+      return 0;
+
+    // If we already have an element starting at Pos, we're done.
+    size_t LastAtOrBeforePosIndex = FirstAfterPos - Offsets.begin() - 1;
+    if (Offsets[LastAtOrBeforePosIndex] == Pos)
+      return LastAtOrBeforePosIndex;
+
+    // We found an element starting before Pos. Check for overlap.
+    if (Offsets[LastAtOrBeforePosIndex] +
+        getSize(Elems[LastAtOrBeforePosIndex]) <= Pos)
+      return LastAtOrBeforePosIndex + 1;
+
+    // Try to decompose it into smaller constants.
+    if (!split(LastAtOrBeforePosIndex, Pos))
+      return None;
+  }
+}
 
-  // Truncate the size of FieldValue to the bit field size.
-  if (FieldSize < FieldValue.getBitWidth())
-    FieldValue = FieldValue.trunc(FieldSize);
+/// Split the constant at index Index, if possible. Return true if we did.
+/// Hint indicates the location at which we'd like to split, but may be
+/// ignored.
+bool ConstantAggregateBuilder::split(size_t Index, CharUnits Hint) {
+  NaturalLayout = false;
+  llvm::Constant *C = Elems[Index];
+  CharUnits Offset = Offsets[Index];
+
+  if (auto *CA = dyn_cast<llvm::ConstantAggregate>(C)) {
+    replace(Elems, Index, Index + 1,
+            llvm::map_range(llvm::seq(0u, CA->getNumOperands()),
+                            [&](unsigned Op) { return CA->getOperand(Op); }));
+    if (auto *Seq = dyn_cast<llvm::SequentialType>(CA->getType())) {
+      // Array or vector.
+      CharUnits ElemSize = getSize(Seq->getElementType());
+      replace(
+          Offsets, Index, Index + 1,
+          llvm::map_range(llvm::seq(0u, CA->getNumOperands()),
+                          [&](unsigned Op) { return Offset + Op * ElemSize; }));
+    } else {
+      // Must be a struct.
+      auto *ST = cast<llvm::StructType>(CA->getType());
+      const llvm::StructLayout *Layout =
+          CGM.getDataLayout().getStructLayout(ST);
+      replace(Offsets, Index, Index + 1,
+              llvm::map_range(
+                  llvm::seq(0u, CA->getNumOperands()), [&](unsigned Op) {
+                    return Offset + CharUnits::fromQuantity(
+                                        Layout->getElementOffset(Op));
+                  }));
+    }
+    return true;
+  }
 
-  NextFieldOffsetInBits = Context.toBits(NextFieldOffsetInChars);
-  if (FieldOffset < NextFieldOffsetInBits) {
-    // Either part of the field or the entire field can go into the previous
-    // byte.
-    assert(!Elements.empty() && "Elements can't be empty!");
+  if (auto *CDS = dyn_cast<llvm::ConstantDataSequential>(C)) {
+    // FIXME: If possible, split into two ConstantDataSequentials at Hint.
+    CharUnits ElemSize = getSize(CDS->getElementType());
+    replace(Elems, Index, Index + 1,
+            llvm::map_range(llvm::seq(0u, CDS->getNumElements()),
+                            [&](unsigned Elem) {
+                              return CDS->getElementAsConstant(Elem);
+                            }));
+    replace(Offsets, Index, Index + 1,
+            llvm::map_range(
+                llvm::seq(0u, CDS->getNumElements()),
+                [&](unsigned Elem) { return Offset + Elem * ElemSize; }));
+    return true;
+  }
 
-    unsigned BitsInPreviousByte = NextFieldOffsetInBits - FieldOffset;
+  if (auto *CAZ = dyn_cast<llvm::ConstantAggregateZero>(C)) {
+    CharUnits ElemSize = getSize(C);
+    assert(Hint > Offset && Hint < Offset + ElemSize && "nothing to split");
+    replace(Elems, Index, Index + 1,
+            {getZeroes(Hint - Offset), getZeroes(Offset + ElemSize - Hint)});
+    replace(Offsets, Index, Index + 1, {Offset, Hint});
+    return true;
+  }
 
-    bool FitsCompletelyInPreviousByte =
-      BitsInPreviousByte >= FieldValue.getBitWidth();
+  if (isa<llvm::UndefValue>(C)) {
+    replace(Elems, Index, Index + 1, {});
+    replace(Offsets, Index, Index + 1, {});
+    return true;
+  }
 
-    llvm::APInt Tmp = FieldValue;
+  // FIXME: We could split a ConstantInt if the need ever arose.
+  // We don't need to do this to handle bit-fields because we always eagerly
+  // split them into 1-byte chunks.
 
-    if (!FitsCompletelyInPreviousByte) {
-      unsigned NewFieldWidth = FieldSize - BitsInPreviousByte;
+  return false;
+}
 
-      if (CGM.getDataLayout().isBigEndian()) {
-        Tmp.lshrInPlace(NewFieldWidth);
-        Tmp = Tmp.trunc(BitsInPreviousByte);
+static llvm::Constant *
+EmitArrayConstant(CodeGenModule &CGM, llvm::ArrayType *DesiredType,
+                  llvm::Type *CommonElementType, unsigned ArrayBound,
+                  SmallVectorImpl<llvm::Constant *> &Elements,
+                  llvm::Constant *Filler);
 
-        // We want the remaining high bits.
-        FieldValue = FieldValue.trunc(NewFieldWidth);
-      } else {
-        Tmp = Tmp.trunc(BitsInPreviousByte);
+llvm::Constant *ConstantAggregateBuilder::buildFrom(
+    CodeGenModule &CGM, ArrayRef<llvm::Constant *> Elems,
+    ArrayRef<CharUnits> Offsets, CharUnits StartOffset, CharUnits Size,
+    bool NaturalLayout, llvm::Type *DesiredTy, bool AllowOversized) {
+  ConstantAggregateBuilderUtils Utils(CGM);
+
+  if (Elems.empty())
+    return llvm::UndefValue::get(DesiredTy);
+
+  auto Offset = [&](size_t I) { return Offsets[I] - StartOffset; };
+
+  // If we want an array type, see if all the elements are the same type and
+  // appropriately spaced.
+  if (llvm::ArrayType *ATy = dyn_cast<llvm::ArrayType>(DesiredTy)) {
+    assert(!AllowOversized && "oversized array emission not supported");
+
+    bool CanEmitArray = true;
+    llvm::Type *CommonType = Elems[0]->getType();
+    llvm::Constant *Filler = llvm::Constant::getNullValue(CommonType);
+    CharUnits ElemSize = Utils.getSize(ATy->getElementType());
+    SmallVector<llvm::Constant*, 32> ArrayElements;
+    for (size_t I = 0; I != Elems.size(); ++I) {
+      // Skip zeroes; we'll use a zero value as our array filler.
+      if (Elems[I]->isNullValue())
+        continue;
 
-        // We want the remaining low bits.
-        FieldValue.lshrInPlace(BitsInPreviousByte);
-        FieldValue = FieldValue.trunc(NewFieldWidth);
+      // All remaining elements must be the same type.
+      if (Elems[I]->getType() != CommonType ||
+          Offset(I) % ElemSize != 0) {
+        CanEmitArray = false;
+        break;
       }
+      ArrayElements.resize(Offset(I) / ElemSize + 1, Filler);
+      ArrayElements.back() = Elems[I];
     }
 
-    Tmp = Tmp.zext(CharWidth);
-    if (CGM.getDataLayout().isBigEndian()) {
-      if (FitsCompletelyInPreviousByte)
-        Tmp = Tmp.shl(BitsInPreviousByte - FieldValue.getBitWidth());
-    } else {
-      Tmp = Tmp.shl(CharWidth - BitsInPreviousByte);
+    if (CanEmitArray) {
+      return EmitArrayConstant(CGM, ATy, CommonType, ATy->getNumElements(),
+                               ArrayElements, Filler);
     }
 
-    // 'or' in the bits that go into the previous byte.
-    llvm::Value *LastElt = Elements.back();
-    if (llvm::ConstantInt *Val = dyn_cast<llvm::ConstantInt>(LastElt))
-      Tmp |= Val->getValue();
-    else {
-      assert(isa<llvm::UndefValue>(LastElt));
-      // If there is an undef field that we're adding to, it can either be a
-      // scalar undef (in which case, we just replace it with our field) or it
-      // is an array.  If it is an array, we have to pull one byte off the
-      // array so that the other undef bytes stay around.
-      if (!isa<llvm::IntegerType>(LastElt->getType())) {
-        // The undef padding will be a multibyte array, create a new smaller
-        // padding and then an hole for our i8 to get plopped into.
-        assert(isa<llvm::ArrayType>(LastElt->getType()) &&
-               "Expected array padding of undefs");
-        llvm::ArrayType *AT = cast<llvm::ArrayType>(LastElt->getType());
-        assert(AT->getElementType()->isIntegerTy(CharWidth) &&
-               AT->getNumElements() != 0 &&
-               "Expected non-empty array padding of undefs");
-
-        // Remove the padding array.
-        NextFieldOffsetInChars -= CharUnits::fromQuantity(AT->getNumElements());
-        Elements.pop_back();
-
-        // Add the padding back in two chunks.
-        AppendPadding(CharUnits::fromQuantity(AT->getNumElements()-1));
-        AppendPadding(CharUnits::One());
-        assert(isa<llvm::UndefValue>(Elements.back()) &&
-               Elements.back()->getType()->isIntegerTy(CharWidth) &&
-               "Padding addition didn't work right");
-      }
-    }
+    // Can't emit as an array, carry on to emit as a struct.
 
-    Elements.back() = llvm::ConstantInt::get(CGM.getLLVMContext(), Tmp);
+  CharUnits DesiredSize = Utils.getSize(DesiredTy);
+  CharUnits Align = CharUnits::One();
+  for (llvm::Constant *C : Elems)
+    Align = std::max(Align, Utils.getAlignment(C));
+  CharUnits AlignedSize = Size.alignTo(Align);
 
-    if (FitsCompletelyInPreviousByte)
-      return;
+  bool Packed = false;
+  ArrayRef<llvm::Constant*> UnpackedElems = Elems;
+  llvm::SmallVector<llvm::Constant*, 32> UnpackedElemStorage;
+  if ((DesiredSize < AlignedSize && !AllowOversized) ||
+      DesiredSize.alignTo(Align) != DesiredSize) {
+    // The natural layout would be the wrong size; force use of a packed layout.
+    NaturalLayout = false;
+    Packed = true;
+  } else if (DesiredSize > AlignedSize) {
+    // The constant would be too small. Add padding to fix it.
+    UnpackedElemStorage.assign(Elems.begin(), Elems.end());
+    UnpackedElemStorage.push_back(Utils.getPadding(DesiredSize - Size));
+    UnpackedElems = UnpackedElemStorage;
+  }
+
+  // If we don't have a natural layout, insert padding as necessary.
+  // As we go, double-check to see if we can actually just emit Elems
+  // as a non-packed struct and do so opportunistically if possible.
+  llvm::SmallVector<llvm::Constant*, 32> PackedElems;
+  if (!NaturalLayout) {
+    CharUnits SizeSoFar = CharUnits::Zero();
+    for (size_t I = 0; I != Elems.size(); ++I) {
+      CharUnits Align = Utils.getAlignment(Elems[I]);
+      CharUnits NaturalOffset = SizeSoFar.alignTo(Align);
+      CharUnits DesiredOffset = Offset(I);
+      assert(DesiredOffset >= SizeSoFar && "elements out of order");
+
+      if (DesiredOffset != NaturalOffset)
+        Packed = true;
+      if (DesiredOffset != SizeSoFar)
+        PackedElems.push_back(Utils.getPadding(DesiredOffset - SizeSoFar));
+      PackedElems.push_back(Elems[I]);
+      SizeSoFar = DesiredOffset + Utils.getSize(Elems[I]);
+    }
+    // If we're using the packed layout, pad it out to the desired size if
+    // necessary.
+    if (Packed) {
+      assert((SizeSoFar <= DesiredSize || AllowOversized) &&
+             "requested size is too small for contents");
+      if (SizeSoFar < DesiredSize)
+        PackedElems.push_back(Utils.getPadding(DesiredSize - SizeSoFar));
+    }
   }
 
-  while (FieldValue.getBitWidth() > CharWidth) {
-    llvm::APInt Tmp;
+  llvm::StructType *STy = llvm::ConstantStruct::getTypeForElements(
+      CGM.getLLVMContext(), Packed ? PackedElems : UnpackedElems, Packed);
 
-    if (CGM.getDataLayout().isBigEndian()) {
-      // We want the high bits.
-      Tmp =
-        FieldValue.lshr(FieldValue.getBitWidth() - CharWidth).trunc(CharWidth);
-    } else {
-      // We want the low bits.
-      Tmp = FieldValue.trunc(CharWidth);
+  // Pick the type to use.  If the type is layout identical to the desired
+  // type then use it, otherwise use whatever the builder produced for us.
+  if (llvm::StructType *DesiredSTy = dyn_cast<llvm::StructType>(DesiredTy)) {
+    if (DesiredSTy->isLayoutIdentical(STy))
+      STy = DesiredSTy;
+  }
 
-      FieldValue.lshrInPlace(CharWidth);
-    }
+  return llvm::ConstantStruct::get(STy, Packed ? PackedElems : UnpackedElems);
 
-    Elements.push_back(llvm::ConstantInt::get(CGM.getLLVMContext(), Tmp));
-    ++NextFieldOffsetInChars;
+void ConstantAggregateBuilder::condense(CharUnits Offset,
+                                        llvm::Type *DesiredTy) {
+  CharUnits Size = getSize(DesiredTy);
 
-    FieldValue = FieldValue.trunc(FieldValue.getBitWidth() - CharWidth);
-  }
+  llvm::Optional<size_t> FirstElemToReplace = splitAt(Offset);
+  if (!FirstElemToReplace)
+    return;
+  size_t First = *FirstElemToReplace;
 
-  assert(FieldValue.getBitWidth() > 0 &&
-         "Should have at least one bit left!");
-  assert(FieldValue.getBitWidth() <= CharWidth &&
-         "Should not have more than a byte left!");
+  llvm::Optional<size_t> LastElemToReplace = splitAt(Offset + Size);
+  if (!LastElemToReplace)
+    return;
+  size_t Last = *LastElemToReplace;
 
-  if (FieldValue.getBitWidth() < CharWidth) {
-    if (CGM.getDataLayout().isBigEndian()) {
-      unsigned BitWidth = FieldValue.getBitWidth();
+  size_t Length = Last - First;
+  if (Length == 0)
+    return;
 
-      FieldValue = FieldValue.zext(CharWidth) << (CharWidth - BitWidth);
-    } else
-      FieldValue = FieldValue.zext(CharWidth);
+  if (Length == 1 && Offsets[First] == Offset &&
+      getSize(Elems[First]) == Size) {
+    // Re-wrap single element structs if necessary. Otherwise, leave any single
+    // element constant of the right size alone even if it has the wrong type.
+    auto *STy = dyn_cast<llvm::StructType>(DesiredTy);
+    if (STy && STy->getNumElements() == 1 &&
+        STy->getElementType(0) == Elems[First]->getType())
+      Elems[First] = llvm::ConstantStruct::get(STy, Elems[First]);
+    return;
   }
 
-  // Append the last element.
-  Elements.push_back(llvm::ConstantInt::get(CGM.getLLVMContext(),
-                                            FieldValue));
-  ++NextFieldOffsetInChars;
+  llvm::Constant *Replacement = buildFrom(
+      CGM, makeArrayRef(Elems).slice(First, Length),
+      makeArrayRef(Offsets).slice(First, Length), Offset, getSize(DesiredTy),
+      /*known to have natural layout=*/false, DesiredTy, false);
+  replace(Elems, First, Last, {Replacement});
+  replace(Offsets, First, Last, {Offset});
 }
 
-void ConstStructBuilder::AppendPadding(CharUnits PadSize) {
-  if (PadSize.isZero())
-    return;
+//===----------------------------------------------------------------------===//
+//                            ConstStructBuilder
+//===----------------------------------------------------------------------===//
 
-  llvm::Type *Ty = CGM.Int8Ty;
-  if (PadSize > CharUnits::One())
-    Ty = llvm::ArrayType::get(Ty, PadSize.getQuantity());
+class ConstStructBuilder {
+  CodeGenModule &CGM;
+  ConstantEmitter &Emitter;
+  ConstantAggregateBuilder &Builder;
+  CharUnits StartOffset;
 
-  llvm::Constant *C = llvm::UndefValue::get(Ty);
-  Elements.push_back(C);
-  assert(getAlignment(C) == CharUnits::One() &&
-         "Padding must have 1 byte alignment!");
+public:
+  static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
+                                     InitListExpr *ILE, QualType StructTy);
+  static llvm::Constant *BuildStruct(ConstantEmitter &Emitter,
+                                     const APValue &Value, QualType ValTy);
+  static bool UpdateStruct(ConstantEmitter &Emitter,
+                           ConstantAggregateBuilder &Const, CharUnits Offset,
+                           InitListExpr *Updater);
 
-  NextFieldOffsetInChars += getSizeInChars(C);
-}
+private:
+  ConstStructBuilder(ConstantEmitter &Emitter,
+                     ConstantAggregateBuilder &Builder, CharUnits StartOffset)
+      : CGM(Emitter.CGM), Emitter(Emitter), Builder(Builder),
+        StartOffset(StartOffset) {}
 
-void ConstStructBuilder::AppendTailPadding(CharUnits RecordSize) {
-  assert(NextFieldOffsetInChars <= RecordSize &&
-         "Size mismatch!");
+  bool AppendField(const FieldDecl *Field, uint64_t FieldOffset,
+                   llvm::Constant *InitExpr, bool AllowOverwrite = false);
 
-  AppendPadding(RecordSize - NextFieldOffsetInChars);
-}
+  bool AppendBytes(CharUnits FieldOffsetInChars, llvm::Constant *InitCst,
+                   bool AllowOverwrite = false);
 
-void ConstStructBuilder::ConvertStructToPacked() {
-  SmallVector<llvm::Constant *, 16> PackedElements;
-  CharUnits ElementOffsetInChars = CharUnits::Zero();
+  bool AppendBitField(const FieldDecl *Field, uint64_t FieldOffset,
+                      llvm::ConstantInt *InitExpr, bool AllowOverwrite = false);
 
-  for (unsigned i = 0, e = Elements.size(); i != e; ++i) {
-    llvm::Constant *C = Elements[i];
+  bool Build(InitListExpr *ILE, bool AllowOverwrite);
+  bool Build(const APValue &Val, const RecordDecl *RD, bool IsPrimaryBase,
+             const CXXRecordDecl *VTableClass, CharUnits BaseOffset);
+  llvm::Constant *Finalize(QualType Ty);
+};
 
-    CharUnits ElementAlign = CharUnits::fromQuantity(
-      CGM.getDataLayout().getABITypeAlignment(C->getType()));
-    CharUnits AlignedElementOffsetInChars =
-        ElementOffsetInChars.alignTo(ElementAlign);
+bool ConstStructBuilder::AppendField(
+    const FieldDecl *Field, uint64_t FieldOffset, llvm::Constant *InitCst,
+    bool AllowOverwrite) {
+  const ASTContext &Context = CGM.getContext();
 
-    if (AlignedElementOffsetInChars > ElementOffsetInChars) {
-      // We need some padding.
-      CharUnits NumChars =
-        AlignedElementOffsetInChars - ElementOffsetInChars;
+  CharUnits FieldOffsetInChars = Context.toCharUnitsFromBits(FieldOffset);
 
-      llvm::Type *Ty = CGM.Int8Ty;
-      if (NumChars > CharUnits::One())
-        Ty = llvm::ArrayType::get(Ty, NumChars.getQuantity());
+  return AppendBytes(FieldOffsetInChars, InitCst, AllowOverwrite);
+}
 
-      llvm::Constant *Padding = llvm::UndefValue::get(Ty);
-      PackedElements.push_back(Padding);
-      ElementOffsetInChars += getSizeInChars(Padding);
-    }
+bool ConstStructBuilder::AppendBytes(CharUnits FieldOffsetInChars,
+                                     llvm::Constant *InitCst,
+                                     bool AllowOverwrite) {
+  return Builder.add(InitCst, StartOffset + FieldOffsetInChars, AllowOverwrite);
 
-    PackedElements.push_back(C);
-    ElementOffsetInChars += getSizeInChars(C);
-  }
+bool ConstStructBuilder::AppendBitField(
+    const FieldDecl *Field, uint64_t FieldOffset, llvm::ConstantInt *CI,
+    bool AllowOverwrite) {
+  uint64_t FieldSize = Field->getBitWidthValue(CGM.getContext());
+  llvm::APInt FieldValue = CI->getValue();
+
+  // Promote the size of FieldValue if necessary
+  // FIXME: This should never occur, but currently it can because initializer
+  // constants are cast to bool, and because clang is not enforcing bitfield
+  // width limits.
+  if (FieldSize > FieldValue.getBitWidth())
+    FieldValue = FieldValue.zext(FieldSize);
+
+  // Truncate the size of FieldValue to the bit field size.
+  if (FieldSize < FieldValue.getBitWidth())
+    FieldValue = FieldValue.trunc(FieldSize);
+
+  return Builder.addBits(FieldValue,
+                         CGM.getContext().toBits(StartOffset) + FieldOffset,
+                         AllowOverwrite);
 
-  assert(ElementOffsetInChars == NextFieldOffsetInChars &&
-         "Packing the struct changed its size!");
+static bool EmitDesignatedInitUpdater(ConstantEmitter &Emitter,
+                                      ConstantAggregateBuilder &Const,
+                                      CharUnits Offset, QualType Type,
+                                      InitListExpr *Updater) {
+  if (Type->isRecordType())
+    return ConstStructBuilder::UpdateStruct(Emitter, Const, Offset, Updater);
 
-  Elements.swap(PackedElements);
-  LLVMStructAlignment = CharUnits::One();
-  Packed = true;
+  auto CAT = Emitter.CGM.getContext().getAsConstantArrayType(Type);
+  if (!CAT)
+    return false;
+  QualType ElemType = CAT->getElementType();
+  CharUnits ElemSize = Emitter.CGM.getContext().getTypeSizeInChars(ElemType);
+  llvm::Type *ElemTy = Emitter.CGM.getTypes().ConvertTypeForMem(ElemType);
+
+  llvm::Constant *FillC = nullptr;
+  if (Expr *Filler = Updater->getArrayFiller()) {
+    if (!isa<NoInitExpr>(Filler)) {
+      FillC = Emitter.tryEmitAbstractForMemory(Filler, ElemType);
+      if (!FillC)
+        return false;
+    }
   }
 
-bool ConstStructBuilder::Build(InitListExpr *ILE) {
+  unsigned NumElementsToUpdate =
+      FillC ? CAT->getSize().getZExtValue() : Updater->getNumInits();
+  for (unsigned I = 0; I != NumElementsToUpdate; ++I, Offset += ElemSize) {
+    Expr *Init = nullptr;
+    if (I < Updater->getNumInits())
+      Init = Updater->getInit(I);
+
+    if (!Init && FillC) {
+      if (!Const.add(FillC, Offset, true))
+        return false;
+    } else if (!Init || isa<NoInitExpr>(Init)) {
+      continue;
+    } else if (InitListExpr *ChildILE = dyn_cast<InitListExpr>(Init)) {
+      if (!EmitDesignatedInitUpdater(Emitter, Const, Offset, ElemType,
+                                     ChildILE))
+        return false;
+      // Attempt to reduce the array element to a single constant if necessary.
+      Const.condense(Offset, ElemTy);
+    } else {
+      llvm::Constant *Val = Emitter.tryEmitPrivateForMemory(Init, ElemType);
+      if (!Const.add(Val, Offset, true))
+        return false;
+    }
+  }
+
+  return true;
+}
+
+bool ConstStructBuilder::Build(InitListExpr *ILE, bool AllowOverwrite) {
   RecordDecl *RD = ILE->getType()->getAs<RecordType>()->getDecl();
   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
 
-  unsigned FieldNo = 0;
+  unsigned FieldNo = -1;
   unsigned ElementNo = 0;
 
   // Bail out if we have base classes. We could support these, but they only
   // arise in C++1z where we will have already constant folded most interesting
   // cases. FIXME: There are still a few more cases we can handle this way.
   if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD))
     if (CXXRD->getNumBases())
       return false;
 
-  for (RecordDecl::field_iterator Field = RD->field_begin(),
-       FieldEnd = RD->field_end(); Field != FieldEnd; ++Field, ++FieldNo) {
+  for (FieldDecl *Field : RD->fields()) {
+    ++FieldNo;
+
     // If this is a union, skip all the fields that aren't being initialized.
-    if (RD->isUnion() && ILE->getInitializedFieldInUnion() != *Field)
+    if (RD->isUnion() && ILE->getInitializedFieldInUnion() != Field)
       continue;
 
     // Don't emit anonymous bitfields, they just affect layout.
     if (Field->isUnnamedBitfield())
       continue;
 
     // Get the initializer.  A struct can include fields without initializers,
     // we just use explicit null values for them.
-    llvm::Constant *EltInit;
+    Expr *Init = nullptr;
     if (ElementNo < ILE->getNumInits())
-      EltInit = Emitter.tryEmitPrivateForMemory(ILE->getInit(ElementNo++),
-                                                Field->getType());
-    else
-      EltInit = Emitter.emitNullForMemory(Field->getType());
+      Init = ILE->getInit(ElementNo++);
+    if (Init && isa<NoInitExpr>(Init))
+      continue;
+
+    // When emitting a DesignatedInitUpdateExpr, a nested InitListExpr
+    // represents additional overwriting of our current constant value, and not
+    // a new constant to emit independently.
+    if (AllowOverwrite &&
+        (Field->getType()->isArrayType() || Field->getType()->isRecordType())) {
+      if (auto *SubILE = dyn_cast<InitListExpr>(Init)) {
+        CharUnits Offset = CGM.getContext().toCharUnitsFromBits(
+            Layout.getFieldOffset(FieldNo));
+        if (!EmitDesignatedInitUpdater(Emitter, Builder, StartOffset + Offset,
+                                       Field->getType(), SubILE))
+          return false;
+        // If we split apart the field's value, try to collapse it down to a
+        // single value now.
+        Builder.condense(StartOffset + Offset,
+                         CGM.getTypes().ConvertTypeForMem(Field->getType()));
+        continue;
+      }
+    }
 
+    llvm::Constant *EltInit =
+        Init ? Emitter.tryEmitPrivateForMemory(Init, Field->getType())
+             : Emitter.emitNullForMemory(Field->getType());
     if (!EltInit)
       return false;
 
     if (!Field->isBitField()) {
       // Handle non-bitfield members.
-      AppendField(*Field, Layout.getFieldOffset(FieldNo), EltInit);
+      if (!AppendField(Field, Layout.getFieldOffset(FieldNo), EltInit,
+                       AllowOverwrite))
+        return false;
     } else {
       // Otherwise we have a bitfield.
       if (auto *CI = dyn_cast<llvm::ConstantInt>(EltInit)) {
-        AppendBitField(*Field, Layout.getFieldOffset(FieldNo), CI);
+        if (!AppendBitField(Field, Layout.getFieldOffset(FieldNo), CI,
+                            AllowOverwrite))
+          return false;
       } else {
         // We are trying to initialize a bitfield with a non-trivial constant,
         // this must require run-time code.
         return false;
       }
     }
   }
 
bool ConstStructBuilder::Build(const APValue &Val, const RecordDecl *RD,
   const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
 
   if (const CXXRecordDecl *CD = dyn_cast<CXXRecordDecl>(RD)) {
     // Add a vtable pointer, if we need one and it hasn't already been added.
     if (CD->isDynamicClass() && !IsPrimaryBase) {
       llvm::Constant *VTableAddressPoint =
           CGM.getCXXABI().getVTableAddressPointForConstExpr(
               BaseSubobject(CD, Offset), VTableClass);
-      AppendBytes(Offset, VTableAddressPoint);
+      if (!AppendBytes(Offset, VTableAddressPoint))
+        return false;
     }
 
     // Accumulate and sort bases, in order to visit them in address order, which
     // may not be the same as declaration order.
     SmallVector<BaseInfo, 8> Bases;
     Bases.reserve(CD->getNumBases());
     unsigned BaseNo = 0;
     for (CXXRecordDecl::base_class_const_iterator Base = CD->bases_begin(),
const APValue &FieldValue =
       RD->isUnion() ? Val.getUnionValue() : Val.getStructField(FieldNo);
     llvm::Constant *EltInit =
       Emitter.tryEmitPrivateForMemory(FieldValue, Field->getType());
     if (!EltInit)
       return false;
 
     if (!Field->isBitField()) {
       // Handle non-bitfield members.
-      AppendField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits, EltInit);
+      if (!AppendField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits,
+                       EltInit))
+        return false;
     } else {
       // Otherwise we have a bitfield.
-      AppendBitField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits,
-                     cast<llvm::ConstantInt>(EltInit));
+      if (!AppendBitField(*Field, Layout.getFieldOffset(FieldNo) + OffsetBits,
+                          cast<llvm::ConstantInt>(EltInit)))
+        return false;
     }
   }
 
   return true;
 }
 
-llvm::Constant *ConstStructBuilder::Finalize(QualType Ty) {
-  RecordDecl *RD = Ty->getAs<RecordType>()->getDecl();
-  const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
-
-  CharUnits LayoutSizeInChars = Layout.getSize();
-
-  if (NextFieldOffsetInChars > LayoutSizeInChars) {
-    // If the struct is bigger than the size of the record type,
-    // we must have a flexible array member at the end.
-    assert(RD->hasFlexibleArrayMember() &&
-           "Must have flexible array member if struct is bigger than type!");
-
-    // No tail padding is necessary.
-  } else {
-    // Append tail padding if necessary.
-    CharUnits LLVMSizeInChars =
-        NextFieldOffsetInChars.alignTo(LLVMStructAlignment);
-
-    if (LLVMSizeInChars != LayoutSizeInChars)
-      AppendTailPadding(LayoutSizeInChars);
-
-    LLVMSizeInChars = NextFieldOffsetInChars.alignTo(LLVMStructAlignment);
-
-    // Check if we need to convert the struct to a packed struct.
-    if (NextFieldOffsetInChars <= LayoutSizeInChars &&
-        LLVMSizeInChars > LayoutSizeInChars) {
-      assert(!Packed && "Size mismatch!");
-
-      ConvertStructToPacked();
-      assert(NextFieldOffsetInChars <= LayoutSizeInChars &&
-             "Converting to packed did not help!");
-    }
-
-    LLVMSizeInChars = NextFieldOffsetInChars.alignTo(LLVMStructAlignment);
-
-    assert(LayoutSizeInChars == LLVMSizeInChars &&
-           "Tail padding mismatch!");
-  }
-
-  // Pick the type to use.  If the type is layout identical to the ConvertType
-  // type then use it, otherwise use whatever the builder produced for us.
-  llvm::StructType *STy =
-      llvm::ConstantStruct::getTypeForElements(CGM.getLLVMContext(),
-                                               Elements, Packed);
-  llvm::Type *ValTy = CGM.getTypes().ConvertType(Ty);
-  if (llvm::StructType *ValSTy = dyn_cast<llvm::StructType>(ValTy)) {
-    if (ValSTy->isLayoutIdentical(STy))
-      STy = ValSTy;
-  }
-
-  llvm::Constant *Result = llvm::ConstantStruct::get(STy, Elements);
-
-  assert(NextFieldOffsetInChars.alignTo(getAlignment(Result)) ==
-             getSizeInChars(Result) &&
-         "Size mismatch!");
-
-  return Result;
-}
-
-llvm::Constant *ConstStructBuilder::BuildStruct(ConstantEmitter &Emitter,
-                                                ConstExprEmitter *ExprEmitter,
-                                                llvm::Constant *Base,
-                                                InitListExpr *Updater,
-                                                QualType ValTy) {
-  ConstStructBuilder Builder(Emitter);
-  if (!Builder.Build(ExprEmitter, Base, Updater))
-    return nullptr;
-  return Builder.Finalize(ValTy);
+llvm::Constant *ConstStructBuilder::Finalize(QualType Type) {
+  RecordDecl *RD = Type->getAs<RecordType>()->getDecl();
+  llvm::Type *ValTy = CGM.getTypes().ConvertType(Type);
+  return Builder.build(ValTy, RD->hasFlexibleArrayMember());
 }
 
 llvm::Constant *ConstStructBuilder::BuildStruct(ConstantEmitter &Emitter,
                                                 InitListExpr *ILE,
                                                 QualType ValTy) {
-  ConstStructBuilder Builder(Emitter);
+  ConstantAggregateBuilder Const(Emitter.CGM);
+  ConstStructBuilder Builder(Emitter, Const, CharUnits::Zero());
 
-  if (!Builder.Build(ILE))
+  if (!Builder.Build(ILE, /*AllowOverwrite*/false))
     return nullptr;
 
   return Builder.Finalize(ValTy);
 }
 
 llvm::Constant *ConstStructBuilder::BuildStruct(ConstantEmitter &Emitter,
                                                 const APValue &Val,
                                                 QualType ValTy) {
-  ConstStructBuilder Builder(Emitter);
+  ConstantAggregateBuilder Const(Emitter.CGM);
+  ConstStructBuilder Builder(Emitter, Const, CharUnits::Zero());
 
   const RecordDecl *RD = ValTy->castAs<RecordType>()->getDecl();
   const CXXRecordDecl *CD = dyn_cast<CXXRecordDecl>(RD);
   if (!Builder.Build(Val, RD, false, CD, CharUnits::Zero()))
     return nullptr;
 
   return Builder.Finalize(ValTy);
 }
 
+bool ConstStructBuilder::UpdateStruct(ConstantEmitter &Emitter,
+                                      ConstantAggregateBuilder &Const,
+                                      CharUnits Offset, InitListExpr *Updater) {
+  return ConstStructBuilder(Emitter, Const, Offset)
+      .Build(Updater, /*AllowOverwrite*/ true);
+}
 
 //===----------------------------------------------------------------------===//
 //                             ConstExprEmitter
 //===----------------------------------------------------------------------===//
 
 static ConstantAddress tryEmitGlobalCompoundLiteral(CodeGenModule &CGM,
                                                     CodeGenFunction *CGF,
                                               const CompoundLiteralExpr *E) {
auto GV = new llvm::GlobalVariable(CGM.getModule(), C->getType(),
                     CGM.getContext().getTargetAddressSpace(addressSpace));
   emitter.finalize(GV);
   GV->setAlignment(Align.getQuantity());
   CGM.setAddrOfConstantCompoundLiteral(E, GV);
   return ConstantAddress(GV, Align);
 }
 
 static llvm::Constant *
-EmitArrayConstant(CodeGenModule &CGM, const ConstantArrayType *DestType,
+EmitArrayConstant(CodeGenModule &CGM, llvm::ArrayType *DesiredType,
                   llvm::Type *CommonElementType, unsigned ArrayBound,
                   SmallVectorImpl<llvm::Constant *> &Elements,
                   llvm::Constant *Filler) {
   // Figure out how long the initial prefix of non-zero elements is.
   unsigned NonzeroLength = ArrayBound;
   if (Elements.size() < NonzeroLength && Filler->isNullValue())
     NonzeroLength = Elements.size();
   if (NonzeroLength == Elements.size()) {
     while (NonzeroLength > 0 && Elements[NonzeroLength - 1]->isNullValue())
       --NonzeroLength;
   }
 
-  if (NonzeroLength == 0) {
-    return llvm::ConstantAggregateZero::get(
-        CGM.getTypes().ConvertType(QualType(DestType, 0)));
-  }
+  if (NonzeroLength == 0)
+    return llvm::ConstantAggregateZero::get(DesiredType);
 
   // Add a zeroinitializer array filler if we have lots of trailing zeroes.
   unsigned TrailingZeroes = ArrayBound - NonzeroLength;
   if (TrailingZeroes >= 8) {
     assert(Elements.size() >= NonzeroLength &&
            "missing initializer for non-zero element");
 
     // If all the elements had the same type up to the trailing zeroes, emit a
     // struct of two arrays (the nonzero data and the zeroinitializer).
     if (CommonElementType && NonzeroLength >= 8) {
       llvm::Constant *Initial = llvm::ConstantArray::get(
           llvm::ArrayType::get(CommonElementType, NonzeroLength),
           makeArrayRef(Elements).take_front(NonzeroLength));
       Elements.resize(2);
       Elements[0] = Initial;
     } else {
       Elements.resize(NonzeroLength + 1);
     }
 
     auto *FillerType =
-        CommonElementType
-            ? CommonElementType
-            : CGM.getTypes().ConvertType(DestType->getElementType());
+        CommonElementType ? CommonElementType : DesiredType->getElementType();
     FillerType = llvm::ArrayType::get(FillerType, TrailingZeroes);
     Elements.back() = llvm::ConstantAggregateZero::get(FillerType);
     CommonElementType = nullptr;
   } else if (Elements.size() != ArrayBound) {
     // Otherwise pad to the right size with the filler if necessary.
     Elements.resize(ArrayBound, Filler);
     if (Filler->getType() != CommonElementType)
       CommonElementType = nullptr;
EmitArrayConstant(CodeGenModule &CGM, llvm::ArrayType *DesiredType,
   return llvm::ConstantStruct::get(SType, Elements);
 }
 
 // This class only needs to handle arrays, structs and unions. Outside C++11
 // mode, we don't currently constant fold those types.  All other types are
 // handled by constant folding.
 //
 // Constant folding is currently missing support for a few features supported
 // here: CK_ToUnion, CK_ReinterpretMemberPointer, and DesignatedInitUpdateExpr.
 class ConstExprEmitter :
   public StmtVisitor<ConstExprEmitter, llvm::Constant*, QualType> {
   CodeGenModule &CGM;
   ConstantEmitter &Emitter;
   llvm::LLVMContext &VMContext;
 public:
   ConstExprEmitter(ConstantEmitter &emitter)
     : CGM(emitter.CGM), Emitter(emitter), VMContext(CGM.getLLVMContext()) {
for (unsigned i = 0; i < NumInitableElts; ++i) {
         return nullptr;
       if (i == 0)
         CommonElementType = C->getType();
       else if (C->getType() != CommonElementType)
         CommonElementType = nullptr;
       Elts.push_back(C);
     }
 
-    return EmitArrayConstant(CGM, CAT, CommonElementType, NumElements, Elts,
+    llvm::ArrayType *Desired =
+        cast<llvm::ArrayType>(CGM.getTypes().ConvertType(ILE->getType()));
+    return EmitArrayConstant(CGM, Desired, CommonElementType, NumElements, Elts,
                              fillC);
   }
 
   llvm::Constant *EmitRecordInitialization(InitListExpr *ILE, QualType T) {
     return ConstStructBuilder::BuildStruct(Emitter, ILE, T);
   }
 
   llvm::Constant *VisitImplicitValueInitExpr(ImplicitValueInitExpr* E,
if (ILE->getType()->isArrayType())
       return EmitArrayInitialization(ILE, T);
 
     if (ILE->getType()->isRecordType())
       return EmitRecordInitialization(ILE, T);
 
     return nullptr;
   }
 
-  llvm::Constant *EmitDesignatedInitUpdater(llvm::Constant *Base,
-                                            InitListExpr *Updater,
+  llvm::Constant *VisitDesignatedInitUpdateExpr(DesignatedInitUpdateExpr *E,
                                                 QualType destType) {
-    if (auto destAT = CGM.getContext().getAsArrayType(destType)) {
-      llvm::ArrayType *AType = cast<llvm::ArrayType>(ConvertType(destType));
-      llvm::Type *ElemType = AType->getElementType();
-
-      unsigned NumInitElements = Updater->getNumInits();
-      unsigned NumElements = AType->getNumElements();
-
-      std::vector<llvm::Constant *> Elts;
-      Elts.reserve(NumElements);
-
-      QualType destElemType = destAT->getElementType();
-
-      if (auto DataArray = dyn_cast<llvm::ConstantDataArray>(Base))
-        for (unsigned i = 0; i != NumElements; ++i)
-          Elts.push_back(DataArray->getElementAsConstant(i));
-      else if (auto Array = dyn_cast<llvm::ConstantArray>(Base))
-        for (unsigned i = 0; i != NumElements; ++i)
-          Elts.push_back(Array->getOperand(i));
-      else
-        return nullptr; // FIXME: other array types not implemented
-
-      llvm::Constant *fillC = nullptr;
-      if (Expr *filler = Updater->getArrayFiller())
-        if (!isa<NoInitExpr>(filler))
-          fillC = Emitter.tryEmitAbstractForMemory(filler, destElemType);
-      bool RewriteType = (fillC && fillC->getType() != ElemType);
-
-      for (unsigned i = 0; i != NumElements; ++i) {
-        Expr *Init = nullptr;
-        if (i < NumInitElements)
-          Init = Updater->getInit(i);
-
-        if (!Init && fillC)
-          Elts[i] = fillC;
-        else if (!Init || isa<NoInitExpr>(Init))
-          ; // Do nothing.
-        else if (InitListExpr *ChildILE = dyn_cast<InitListExpr>(Init))
-          Elts[i] = EmitDesignatedInitUpdater(Elts[i], ChildILE, destElemType);
-        else
-          Elts[i] = Emitter.tryEmitPrivateForMemory(Init, destElemType);
-
-       if (!Elts[i])
-          return nullptr;
-        RewriteType |= (Elts[i]->getType() != ElemType);
-      }
-
-      if (RewriteType) {
-        std::vector<llvm::Type *> Types;
-        Types.reserve(NumElements);
-        for (unsigned i = 0; i != NumElements; ++i)
-          Types.push_back(Elts[i]->getType());
-        llvm::StructType *SType = llvm::StructType::get(AType->getContext(),
-                                                        Types, true);
-        return llvm::ConstantStruct::get(SType, Elts);
-      }
-
-      return llvm::ConstantArray::get(AType, Elts);
-    }
+    auto C = Visit(E->getBase(), destType);
+    if (!C)
 
-    if (destType->isRecordType())
-      return ConstStructBuilder::BuildStruct(Emitter, this, Base, Updater,
-                                             destType);
+    ConstantAggregateBuilder Const(CGM);
+    Const.add(C, CharUnits::Zero(), false);
 
+    if (!EmitDesignatedInitUpdater(Emitter, Const, CharUnits::Zero(), destType,
+                                   E->getUpdater()))
       return nullptr;
-  }
 
-  llvm::Constant *VisitDesignatedInitUpdateExpr(DesignatedInitUpdateExpr *E,
-                                                QualType destType) {
-    auto C = Visit(E->getBase(), destType);
-    if (!C) return nullptr;
-    return EmitDesignatedInitUpdater(C, E->getUpdater(), destType);
+    llvm::Type *ValTy = CGM.getTypes().ConvertType(destType);
+    bool HasFlexibleArray = false;
+    if (auto *RT = destType->getAs<RecordType>())
+      HasFlexibleArray = RT->getDecl()->hasFlexibleArrayMember();
+    return Const.build(ValTy, HasFlexibleArray);
   }
 
   llvm::Constant *VisitCXXConstructExpr(CXXConstructExpr *E, QualType Ty) {
     if (!E->getConstructor()->isTrivial())
       return nullptr;
 
     // FIXME: We should not have to call getBaseElementType here.
     const RecordType *RT =
public:
   // Utility methods
   llvm::Type *ConvertType(QualType T) {
     return CGM.getTypes().ConvertType(T);
   }
 };
 
 }  // end anonymous namespace.
 
-bool ConstStructBuilder::Build(ConstExprEmitter *ExprEmitter,
-                               llvm::Constant *Base,
-                               InitListExpr *Updater) {
-  assert(Base && "base expression should not be empty");
-
-  QualType ExprType = Updater->getType();
-  RecordDecl *RD = ExprType->getAs<RecordType>()->getDecl();
-  const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(RD);
-  const llvm::StructLayout *BaseLayout = CGM.getDataLayout().getStructLayout(
-      cast<llvm::StructType>(Base->getType()));
-  unsigned FieldNo = -1;
-  unsigned ElementNo = 0;
-
-  // Bail out if we have base classes. We could support these, but they only
-  // arise in C++1z where we will have already constant folded most interesting
-  // cases. FIXME: There are still a few more cases we can handle this way.
-  if (auto *CXXRD = dyn_cast<CXXRecordDecl>(RD))
-    if (CXXRD->getNumBases())
-      return false;
-
-  for (FieldDecl *Field : RD->fields()) {
-    ++FieldNo;
-
-    if (RD->isUnion() && Updater->getInitializedFieldInUnion() != Field)
-      continue;
-
-    // Skip anonymous bitfields.
-    if (Field->isUnnamedBitfield())
-      continue;
-
-    llvm::Constant *EltInit = Base->getAggregateElement(ElementNo);
-
-    // Bail out if the type of the ConstantStruct does not have the same layout
-    // as the type of the InitListExpr.
-    if (CGM.getTypes().ConvertType(Field->getType()) != EltInit->getType() ||
-        Layout.getFieldOffset(ElementNo) !=
-          BaseLayout->getElementOffsetInBits(ElementNo))
-      return false;
-
-    // Get the initializer. If we encounter an empty field or a NoInitExpr,
-    // we use values from the base expression.
-    Expr *Init = nullptr;
-    if (ElementNo < Updater->getNumInits())
-      Init = Updater->getInit(ElementNo);
-
-    if (!Init || isa<NoInitExpr>(Init))
-      ; // Do nothing.
-    else if (InitListExpr *ChildILE = dyn_cast<InitListExpr>(Init))
-      EltInit = ExprEmitter->EmitDesignatedInitUpdater(EltInit, ChildILE,
-                                                       Field->getType());
-    else
-      EltInit = Emitter.tryEmitPrivateForMemory(Init, Field->getType());
-
-    ++ElementNo;
-
-    if (!EltInit)
-      return false;
-
-    if (!Field->isBitField())
-      AppendField(Field, Layout.getFieldOffset(FieldNo), EltInit);
-    else if (llvm::ConstantInt *CI = dyn_cast<llvm::ConstantInt>(EltInit))
-      AppendBitField(Field, Layout.getFieldOffset(FieldNo), CI);
-    else
-      // Initializing a bitfield with a non-trivial constant?
-      return false;
-  }
-
-  return true;
-}
-
 llvm::Constant *ConstantEmitter::validateAndPopAbstract(llvm::Constant *C,
                                                         AbstractState saved) {
   Abstract = saved.OldValue;
 
   assert(saved.OldPlaceholdersSize == PlaceholderAddresses.size() &&
          "created a placeholder while doing an abstract emission?");
 
   // No validation necessary for now.
case APValue::Array: {
     if (CAT == nullptr && CommonElementType == nullptr && !NumInitElts) {
       const ArrayType *AT = CGM.getContext().getAsArrayType(DestType);
       CommonElementType = CGM.getTypes().ConvertType(AT->getElementType());
       llvm::ArrayType *AType = llvm::ArrayType::get(CommonElementType,
                                                     NumElements);
       return llvm::ConstantAggregateZero::get(AType);
     }
 
-    return EmitArrayConstant(CGM, CAT, CommonElementType, NumElements, Elts,
+    llvm::ArrayType *Desired =
+        cast<llvm::ArrayType>(CGM.getTypes().ConvertType(DestType));
+    return EmitArrayConstant(CGM, Desired, CommonElementType, NumElements, Elts,
                              Filler);
   }
   case APValue::MemberPointer:
     return CGM.getCXXABI().EmitMemberPointer(Value, DestType);
   }
   llvm_unreachable("Unknown APValue kind");
 }
 

test/CodeGenCXX/designated-init.cpp

+// RUN: %clang_cc1 -std=c++98 -emit-llvm -o - %s -triple x86_64-linux-gnu | FileCheck %s
+// RUN: %clang_cc1 -std=c++11 -emit-llvm -o - %s -triple x86_64-linux-gnu | FileCheck %s
+
+struct A { int x, y[3]; };
+struct B { A a; };
+
+// CHECK: @b = global %{{[^ ]*}} { %{{[^ ]*}} { i32 1, [3 x i32] [i32 2, i32 5, i32 4] } }
+B b = {(A){1, 2, 3, 4}, .a.y[1] = 5};
+
+union U {
+  int n;
+  float f;
+};
+struct C {
+  int x;
+  U u[3];
+};
+struct D {
+  C c;
+};
+
+// CHECK: @d1 = {{.*}} { i32 1, [3 x %[[U:.*]]] [%[[U]] { i32 2 }, %[[U]] { i32 5 }, %[[U]] { i32 4 }] }
+D d1 = {(C){1, {{.n=2}, {.f=3}, {.n=4}}}, .c.u[1].n = 5};
+
+// CHECK: @d2 = {{.*}} { i32 1, { %[[U]], float, %[[U]] } { %[[U]] { i32 2 }, float 5.{{0*}}e+00, %[[U]] { i32 4 } } }
+D d2 = {(C){1, 2, 3, 4}, .c.u[1].f = 5};
+
+struct Bitfield {
+  int a : 3;
+  int b : 4;
+  int c : 5;
+};
+struct WithBitfield {
+  int n;
+  Bitfield b;
+};
+// CHECK: @bitfield = {{.*}} { i32 1, { i8, i8, [2 x i8] } { i8 42, i8 2, [2 x i8] undef } }
+WithBitfield bitfield = {1, (Bitfield){2, 3, 4}, .b.b = 5};
+
+struct String {
+  const char buffer[12];
+};
+struct WithString {
+  String str;
+};
+// CHECK: @string = {{.*}} [12 x i8] c"Hello World\00" } }
+WithString string = {(String){"hello world"}, .str.buffer[0] = 'H', .str.buffer[6] = 'W'};
+
+struct LargeArray {
+  int arr[4096];
+};
+struct WithLargeArray {
+  LargeArray arr;
+};
+// CHECK: @large = global { { <{ [11 x i32], [4085 x i32] }> } } { { <{ [11 x i32], [4085 x i32] }> } { <{ [11 x i32], [4085 x i32] }> <{ [11 x i32] [i32 1, i32 2, i32 3, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 0, i32 10], [4085 x i32] zeroinitializer }> } }
+WithLargeArray large = {(LargeArray){1, 2, 3}, .arr.arr[10] = 10};
+
+union OverwritePaddingWithBitfield {
+  struct Padding { unsigned : 8; char c; } padding;
+  char bitfield : 3;
+};
+struct WithOverwritePaddingWithBitfield {
+  OverwritePaddingWithBitfield a;
+};
+// CHECK: @overwrite_padding = global { { i8, i8 } } { { i8, i8 } { i8 3, i8 1 } }
+WithOverwritePaddingWithBitfield overwrite_padding = {(OverwritePaddingWithBitfield){1}, .a.bitfield = 3};