Vendor import of clang trunk r126079:

http://llvm.org/svn/llvm-project/cfe/trunk@126079

1 files changed, 409 insertions, 204 deletions

diff --git a/lib/CodeGen/CGRecordLayoutBuilder.cpp b/lib/CodeGen/CGRecordLayoutBuilder.cpp
index 77a319f..4b19aef 100644
--- a/lib/CodeGen/CGRecordLayoutBuilder.cpp
+++ b/lib/CodeGen/CGRecordLayoutBuilder.cpp
@@ -14,6 +14,7 @@
 #include "CGRecordLayout.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Attr.h"
+#include "clang/AST/CXXInheritance.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/RecordLayout.h"
@@ -27,28 +28,52 @@
 using namespace clang;
 using namespace CodeGen;
 
-namespace clang {
-namespace CodeGen {
+namespace {
 
 class CGRecordLayoutBuilder {
 public:
   /// FieldTypes - Holds the LLVM types that the struct is created from.
+  /// 
   std::vector<const llvm::Type *> FieldTypes;
 
-  /// LLVMFieldInfo - Holds a field and its corresponding LLVM field number.
-  typedef std::pair<const FieldDecl *, unsigned> LLVMFieldInfo;
-  llvm::SmallVector<LLVMFieldInfo, 16> LLVMFields;
-
-  /// LLVMBitFieldInfo - Holds location and size information about a bit field.
-  typedef std::pair<const FieldDecl *, CGBitFieldInfo> LLVMBitFieldInfo;
-  llvm::SmallVector<LLVMBitFieldInfo, 16> LLVMBitFields;
-
-  typedef std::pair<const CXXRecordDecl *, unsigned> LLVMBaseInfo;
-  llvm::SmallVector<LLVMBaseInfo, 16> LLVMNonVirtualBases;
+  /// BaseSubobjectType - Holds the LLVM type for the non-virtual part
+  /// of the struct. For example, consider:
+  ///
+  /// struct A { int i; };
+  /// struct B { void *v; };
+  /// struct C : virtual A, B { };
+  ///
+  /// The LLVM type of C will be
+  /// %struct.C = type { i32 (...)**, %struct.A, i32, %struct.B }
+  ///
+  /// And the LLVM type of the non-virtual base struct will be
+  /// %struct.C.base = type { i32 (...)**, %struct.A, i32 }
+  ///
+  /// This only gets initialized if the base subobject type is
+  /// different from the complete-object type.
+  const llvm::StructType *BaseSubobjectType;
+
+  /// FieldInfo - Holds a field and its corresponding LLVM field number.
+  llvm::DenseMap<const FieldDecl *, unsigned> Fields;
+
+  /// BitFieldInfo - Holds location and size information about a bit field.
+  llvm::DenseMap<const FieldDecl *, CGBitFieldInfo> BitFields;
+
+  llvm::DenseMap<const CXXRecordDecl *, unsigned> NonVirtualBases;
+  llvm::DenseMap<const CXXRecordDecl *, unsigned> VirtualBases;
+
+  /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
+  /// primary base classes for some other direct or indirect base class.
+  CXXIndirectPrimaryBaseSet IndirectPrimaryBases;
+
+  /// LaidOutVirtualBases - A set of all laid out virtual bases, used to avoid
+  /// avoid laying out virtual bases more than once.
+  llvm::SmallPtrSet<const CXXRecordDecl *, 4> LaidOutVirtualBases;
   
   /// IsZeroInitializable - Whether this struct can be C++
   /// zero-initialized with an LLVM zeroinitializer.
   bool IsZeroInitializable;
+  bool IsZeroInitializableAsBase;
 
   /// Packed - Whether the resulting LLVM struct will be packed or not.
   bool Packed;
@@ -59,18 +84,14 @@ private:
   /// Alignment - Contains the alignment of the RecordDecl.
   //
   // FIXME: This is not needed and should be removed.
-  unsigned Alignment;
-
-  /// AlignmentAsLLVMStruct - Will contain the maximum alignment of all the
-  /// LLVM types.
-  unsigned AlignmentAsLLVMStruct;
+  CharUnits Alignment;
 
   /// BitsAvailableInLastField - If a bit field spans only part of a LLVM field,
   /// this will have the number of bits still available in the field.
   char BitsAvailableInLastField;
 
-  /// NextFieldOffsetInBytes - Holds the next field offset in bytes.
-  uint64_t NextFieldOffsetInBytes;
+  /// NextFieldOffset - Holds the next field offset.
+  CharUnits NextFieldOffset;
 
   /// LayoutUnionField - Will layout a field in an union and return the type
   /// that the field will have.
@@ -84,14 +105,30 @@ private:
   /// Returns false if the operation failed because the struct is not packed.
   bool LayoutFields(const RecordDecl *D);
 
+  /// Layout a single base, virtual or non-virtual
+  void LayoutBase(const CXXRecordDecl *base,
+                  const CGRecordLayout &baseLayout,
+                  CharUnits baseOffset);
+
+  /// LayoutVirtualBase - layout a single virtual base.
+  void LayoutVirtualBase(const CXXRecordDecl *base,
+                         CharUnits baseOffset);
+
+  /// LayoutVirtualBases - layout the virtual bases of a record decl.
+  void LayoutVirtualBases(const CXXRecordDecl *RD,
+                          const ASTRecordLayout &Layout);
+  
   /// LayoutNonVirtualBase - layout a single non-virtual base.
-  void LayoutNonVirtualBase(const CXXRecordDecl *BaseDecl,
-                            uint64_t BaseOffset);
+  void LayoutNonVirtualBase(const CXXRecordDecl *base,
+                            CharUnits baseOffset);
   
-  /// LayoutNonVirtualBases - layout the non-virtual bases of a record decl.
+  /// LayoutNonVirtualBases - layout the virtual bases of a record decl.
   void LayoutNonVirtualBases(const CXXRecordDecl *RD, 
                              const ASTRecordLayout &Layout);
 
+  /// ComputeNonVirtualBaseType - Compute the non-virtual base field types.
+  bool ComputeNonVirtualBaseType(const CXXRecordDecl *RD);
+  
   /// LayoutField - layout a single field. Returns false if the operation failed
   /// because the current struct is not packed.
   bool LayoutField(const FieldDecl *D, uint64_t FieldOffset);
@@ -100,41 +137,47 @@ private:
   void LayoutBitField(const FieldDecl *D, uint64_t FieldOffset);
 
   /// AppendField - Appends a field with the given offset and type.
-  void AppendField(uint64_t FieldOffsetInBytes, const llvm::Type *FieldTy);
+  void AppendField(CharUnits fieldOffset, const llvm::Type *FieldTy);
 
   /// AppendPadding - Appends enough padding bytes so that the total
   /// struct size is a multiple of the field alignment.
-  void AppendPadding(uint64_t FieldOffsetInBytes, unsigned FieldAlignment);
+  void AppendPadding(CharUnits fieldOffset, CharUnits fieldAlignment);
 
+  /// getByteArrayType - Returns a byte array type with the given number of
+  /// elements.
+  const llvm::Type *getByteArrayType(CharUnits NumBytes);
+  
   /// AppendBytes - Append a given number of bytes to the record.
-  void AppendBytes(uint64_t NumBytes);
+  void AppendBytes(CharUnits numBytes);
 
   /// AppendTailPadding - Append enough tail padding so that the type will have
   /// the passed size.
   void AppendTailPadding(uint64_t RecordSize);
 
-  unsigned getTypeAlignment(const llvm::Type *Ty) const;
+  CharUnits getTypeAlignment(const llvm::Type *Ty) const;
+
+  /// getAlignmentAsLLVMStruct - Returns the maximum alignment of all the
+  /// LLVM element types.
+  CharUnits getAlignmentAsLLVMStruct() const;
 
   /// CheckZeroInitializable - Check if the given type contains a pointer
   /// to data member.
   void CheckZeroInitializable(QualType T);
-  void CheckZeroInitializable(const CXXRecordDecl *RD);
 
 public:
   CGRecordLayoutBuilder(CodeGenTypes &Types)
-    : IsZeroInitializable(true), Packed(false), Types(Types),
-      Alignment(0), AlignmentAsLLVMStruct(1),
-      BitsAvailableInLastField(0), NextFieldOffsetInBytes(0) { }
+    : BaseSubobjectType(0),
+      IsZeroInitializable(true), IsZeroInitializableAsBase(true),
+      Packed(false), Types(Types), BitsAvailableInLastField(0) { }
 
   /// Layout - Will layout a RecordDecl.
   void Layout(const RecordDecl *D);
 };
 
 }
-}
 
 void CGRecordLayoutBuilder::Layout(const RecordDecl *D) {
-  Alignment = Types.getContext().getASTRecordLayout(D).getAlignment() / 8;
+  Alignment = Types.getContext().getASTRecordLayout(D).getAlignment();
   Packed = D->hasAttr<PackedAttr>();
 
   if (D->isUnion()) {
@@ -147,12 +190,12 @@ void CGRecordLayoutBuilder::Layout(const RecordDecl *D) {
 
   // We weren't able to layout the struct. Try again with a packed struct
   Packed = true;
-  AlignmentAsLLVMStruct = 1;
-  NextFieldOffsetInBytes = 0;
+  NextFieldOffset = CharUnits::Zero();
   FieldTypes.clear();
-  LLVMFields.clear();
-  LLVMBitFields.clear();
-  LLVMNonVirtualBases.clear();
+  Fields.clear();
+  BitFields.clear();
+  NonVirtualBases.clear();
+  VirtualBases.clear();
 
   LayoutFields(D);
 }
@@ -182,6 +225,12 @@ CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
     FieldSize = TypeSizeInBits;
   }
 
+  // in big-endian machines the first fields are in higher bit positions,
+  // so revert the offset. The byte offsets are reversed(back) later.
+  if (Types.getTargetData().isBigEndian()) {
+    FieldOffset = ((ContainingTypeSizeInBits)-FieldOffset-FieldSize);
+  }
+
   // Compute the access components. The policy we use is to start by attempting
   // to access using the width of the bit-field type itself and to always access
   // at aligned indices of that type. If such an access would fail because it
@@ -189,7 +238,6 @@ CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
   // power of two and retry. The current algorithm assumes pow2 sized types,
   // although this is easy to fix.
   //
-  // FIXME: This algorithm is wrong on big-endian systems, I think.
   assert(llvm::isPowerOf2_32(TypeSizeInBits) && "Unexpected type size!");
   CGBitFieldInfo::AccessInfo Components[3];
   unsigned NumComponents = 0;
@@ -237,7 +285,15 @@ CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
     // FIXME: We still follow the old access pattern of only using the field
     // byte offset. We should switch this once we fix the struct layout to be
     // pretty.
-    AI.FieldByteOffset = AccessStart / 8;
+
+    // on big-endian machines we reverted the bit offset because first fields are
+    // in higher bits. But this also reverts the bytes, so fix this here by reverting
+    // the byte offset on big-endian machines.
+    if (Types.getTargetData().isBigEndian()) {
+      AI.FieldByteOffset = (ContainingTypeSizeInBits - AccessStart - AccessWidth )/8;
+    } else {
+      AI.FieldByteOffset = AccessStart / 8;
+    }
     AI.FieldBitStart = AccessBitsInFieldStart - AccessStart;
     AI.AccessWidth = AccessWidth;
     AI.AccessAlignment = llvm::MinAlign(ContainingTypeAlign, AccessStart) / 8;
@@ -258,56 +314,54 @@ CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
                                         uint64_t FieldSize) {
   const RecordDecl *RD = FD->getParent();
   const ASTRecordLayout &RL = Types.getContext().getASTRecordLayout(RD);
-  uint64_t ContainingTypeSizeInBits = RL.getSize();
-  unsigned ContainingTypeAlign = RL.getAlignment();
+  uint64_t ContainingTypeSizeInBits = Types.getContext().toBits(RL.getSize());
+  unsigned ContainingTypeAlign = Types.getContext().toBits(RL.getAlignment());
 
   return MakeInfo(Types, FD, FieldOffset, FieldSize, ContainingTypeSizeInBits,
                   ContainingTypeAlign);
 }
 
 void CGRecordLayoutBuilder::LayoutBitField(const FieldDecl *D,
-                                           uint64_t FieldOffset) {
-  uint64_t FieldSize =
+                                           uint64_t fieldOffset) {
+  uint64_t fieldSize =
     D->getBitWidth()->EvaluateAsInt(Types.getContext()).getZExtValue();
 
-  if (FieldSize == 0)
+  if (fieldSize == 0)
     return;
 
-  uint64_t NextFieldOffset = NextFieldOffsetInBytes * 8;
-  unsigned NumBytesToAppend;
+  uint64_t nextFieldOffsetInBits = NextFieldOffset.getQuantity() * 8;
+  unsigned numBytesToAppend;
 
-  if (FieldOffset < NextFieldOffset) {
+  if (fieldOffset < nextFieldOffsetInBits) {
     assert(BitsAvailableInLastField && "Bitfield size mismatch!");
-    assert(NextFieldOffsetInBytes && "Must have laid out at least one byte!");
+    assert(!NextFieldOffset.isZero() && "Must have laid out at least one byte");
 
     // The bitfield begins in the previous bit-field.
-    NumBytesToAppend =
-      llvm::RoundUpToAlignment(FieldSize - BitsAvailableInLastField, 8) / 8;
+    numBytesToAppend =
+      llvm::RoundUpToAlignment(fieldSize - BitsAvailableInLastField, 8) / 8;
   } else {
-    assert(FieldOffset % 8 == 0 && "Field offset not aligned correctly");
+    assert(fieldOffset % 8 == 0 && "Field offset not aligned correctly");
 
     // Append padding if necessary.
-    AppendBytes((FieldOffset - NextFieldOffset) / 8);
+    AppendPadding(CharUnits::fromQuantity(fieldOffset / 8), CharUnits::One());
 
-    NumBytesToAppend =
-      llvm::RoundUpToAlignment(FieldSize, 8) / 8;
+    numBytesToAppend = llvm::RoundUpToAlignment(fieldSize, 8) / 8;
 
-    assert(NumBytesToAppend && "No bytes to append!");
+    assert(numBytesToAppend && "No bytes to append!");
   }
 
   // Add the bit field info.
-  LLVMBitFields.push_back(
-    LLVMBitFieldInfo(D, CGBitFieldInfo::MakeInfo(Types, D, FieldOffset,
-                                                 FieldSize)));
+  BitFields.insert(std::make_pair(D,
+                   CGBitFieldInfo::MakeInfo(Types, D, fieldOffset, fieldSize)));
 
-  AppendBytes(NumBytesToAppend);
+  AppendBytes(CharUnits::fromQuantity(numBytesToAppend));
 
   BitsAvailableInLastField =
-    NextFieldOffsetInBytes * 8 - (FieldOffset + FieldSize);
+    NextFieldOffset.getQuantity() * 8 - (fieldOffset + fieldSize);
 }
 
 bool CGRecordLayoutBuilder::LayoutField(const FieldDecl *D,
-                                        uint64_t FieldOffset) {
+                                        uint64_t fieldOffset) {
   // If the field is packed, then we need a packed struct.
   if (!Packed && D->hasAttr<PackedAttr>())
     return false;
@@ -318,54 +372,50 @@ bool CGRecordLayoutBuilder::LayoutField(const FieldDecl *D,
     if (!Packed && !D->getDeclName())
       return false;
 
-    LayoutBitField(D, FieldOffset);
+    LayoutBitField(D, fieldOffset);
     return true;
   }
 
   CheckZeroInitializable(D->getType());
 
-  assert(FieldOffset % 8 == 0 && "FieldOffset is not on a byte boundary!");
-  uint64_t FieldOffsetInBytes = FieldOffset / 8;
+  assert(fieldOffset % 8 == 0 && "FieldOffset is not on a byte boundary!");
+  CharUnits fieldOffsetInBytes = CharUnits::fromQuantity(fieldOffset / 8);
 
   const llvm::Type *Ty = Types.ConvertTypeForMemRecursive(D->getType());
-  unsigned TypeAlignment = getTypeAlignment(Ty);
+  CharUnits typeAlignment = getTypeAlignment(Ty);
 
   // If the type alignment is larger then the struct alignment, we must use
   // a packed struct.
-  if (TypeAlignment > Alignment) {
+  if (typeAlignment > Alignment) {
     assert(!Packed && "Alignment is wrong even with packed struct!");
     return false;
   }
 
-  if (const RecordType *RT = D->getType()->getAs<RecordType>()) {
-    const RecordDecl *RD = cast<RecordDecl>(RT->getDecl());
-    if (const MaxFieldAlignmentAttr *MFAA =
-          RD->getAttr<MaxFieldAlignmentAttr>()) {
-      if (MFAA->getAlignment() != TypeAlignment * 8 && !Packed)
-        return false;
+  if (!Packed) {
+    if (const RecordType *RT = D->getType()->getAs<RecordType>()) {
+      const RecordDecl *RD = cast<RecordDecl>(RT->getDecl());
+      if (const MaxFieldAlignmentAttr *MFAA =
+            RD->getAttr<MaxFieldAlignmentAttr>()) {
+        if (MFAA->getAlignment() != typeAlignment.getQuantity() * 8)
+          return false;
+      }
     }
   }
 
   // Round up the field offset to the alignment of the field type.
-  uint64_t AlignedNextFieldOffsetInBytes =
-    llvm::RoundUpToAlignment(NextFieldOffsetInBytes, TypeAlignment);
+  CharUnits alignedNextFieldOffsetInBytes =
+    NextFieldOffset.RoundUpToAlignment(typeAlignment);
 
-  if (FieldOffsetInBytes < AlignedNextFieldOffsetInBytes) {
+  if (fieldOffsetInBytes < alignedNextFieldOffsetInBytes) {
     assert(!Packed && "Could not place field even with packed struct!");
     return false;
   }
 
-  if (AlignedNextFieldOffsetInBytes < FieldOffsetInBytes) {
-    // Even with alignment, the field offset is not at the right place,
-    // insert padding.
-    uint64_t PaddingInBytes = FieldOffsetInBytes - NextFieldOffsetInBytes;
-
-    AppendBytes(PaddingInBytes);
-  }
+  AppendPadding(fieldOffsetInBytes, typeAlignment);
 
   // Now append the field.
-  LLVMFields.push_back(LLVMFieldInfo(D, FieldTypes.size()));
-  AppendField(FieldOffsetInBytes, Ty);
+  Fields[D] = FieldTypes.size();
+  AppendField(fieldOffsetInBytes, Ty);
 
   return true;
 }
@@ -389,95 +439,167 @@ CGRecordLayoutBuilder::LayoutUnionField(const FieldDecl *Field,
       FieldTy = llvm::ArrayType::get(FieldTy, NumBytesToAppend);
 
     // Add the bit field info.
-    LLVMBitFields.push_back(
-      LLVMBitFieldInfo(Field, CGBitFieldInfo::MakeInfo(Types, Field,
-                                                       0, FieldSize)));
+    BitFields.insert(std::make_pair(Field,
+                         CGBitFieldInfo::MakeInfo(Types, Field, 0, FieldSize)));
     return FieldTy;
   }
 
   // This is a regular union field.
-  LLVMFields.push_back(LLVMFieldInfo(Field, 0));
+  Fields[Field] = 0;
   return Types.ConvertTypeForMemRecursive(Field->getType());
 }
 
 void CGRecordLayoutBuilder::LayoutUnion(const RecordDecl *D) {
   assert(D->isUnion() && "Can't call LayoutUnion on a non-union record!");
 
-  const ASTRecordLayout &Layout = Types.getContext().getASTRecordLayout(D);
+  const ASTRecordLayout &layout = Types.getContext().getASTRecordLayout(D);
 
-  const llvm::Type *Ty = 0;
-  uint64_t Size = 0;
-  unsigned Align = 0;
+  const llvm::Type *unionType = 0;
+  CharUnits unionSize = CharUnits::Zero();
+  CharUnits unionAlign = CharUnits::Zero();
 
-  bool HasOnlyZeroSizedBitFields = true;
+  bool hasOnlyZeroSizedBitFields = true;
 
-  unsigned FieldNo = 0;
-  for (RecordDecl::field_iterator Field = D->field_begin(),
-       FieldEnd = D->field_end(); Field != FieldEnd; ++Field, ++FieldNo) {
-    assert(Layout.getFieldOffset(FieldNo) == 0 &&
+  unsigned fieldNo = 0;
+  for (RecordDecl::field_iterator field = D->field_begin(),
+       fieldEnd = D->field_end(); field != fieldEnd; ++field, ++fieldNo) {
+    assert(layout.getFieldOffset(fieldNo) == 0 &&
           "Union field offset did not start at the beginning of record!");
-    const llvm::Type *FieldTy = LayoutUnionField(*Field, Layout);
+    const llvm::Type *fieldType = LayoutUnionField(*field, layout);
 
-    if (!FieldTy)
+    if (!fieldType)
       continue;
 
-    HasOnlyZeroSizedBitFields = false;
+    hasOnlyZeroSizedBitFields = false;
 
-    unsigned FieldAlign = Types.getTargetData().getABITypeAlignment(FieldTy);
-    uint64_t FieldSize = Types.getTargetData().getTypeAllocSize(FieldTy);
+    CharUnits fieldAlign = CharUnits::fromQuantity(
+                          Types.getTargetData().getABITypeAlignment(fieldType));
+    CharUnits fieldSize = CharUnits::fromQuantity(
+                             Types.getTargetData().getTypeAllocSize(fieldType));
 
-    if (FieldAlign < Align)
+    if (fieldAlign < unionAlign)
       continue;
 
-    if (FieldAlign > Align || FieldSize > Size) {
-      Ty = FieldTy;
-      Align = FieldAlign;
-      Size = FieldSize;
+    if (fieldAlign > unionAlign || fieldSize > unionSize) {
+      unionType = fieldType;
+      unionAlign = fieldAlign;
+      unionSize = fieldSize;
     }
   }
 
   // Now add our field.
-  if (Ty) {
-    AppendField(0, Ty);
+  if (unionType) {
+    AppendField(CharUnits::Zero(), unionType);
 
-    if (getTypeAlignment(Ty) > Layout.getAlignment() / 8) {
+    if (getTypeAlignment(unionType) > layout.getAlignment()) {
       // We need a packed struct.
       Packed = true;
-      Align = 1;
+      unionAlign = CharUnits::One();
     }
   }
-  if (!Align) {
-    assert(HasOnlyZeroSizedBitFields &&
+  if (unionAlign.isZero()) {
+    assert(hasOnlyZeroSizedBitFields &&
            "0-align record did not have all zero-sized bit-fields!");
-    Align = 1;
+    unionAlign = CharUnits::One();
   }
 
   // Append tail padding.
-  if (Layout.getSize() / 8 > Size)
-    AppendPadding(Layout.getSize() / 8, Align);
+  CharUnits recordSize = layout.getSize();
+  if (recordSize > unionSize)
+    AppendPadding(recordSize, unionAlign);
+}
+
+void CGRecordLayoutBuilder::LayoutBase(const CXXRecordDecl *base,
+                                       const CGRecordLayout &baseLayout,
+                                       CharUnits baseOffset) {
+  AppendPadding(baseOffset, CharUnits::One());
+
+  const ASTRecordLayout &baseASTLayout
+    = Types.getContext().getASTRecordLayout(base);
+
+  // Fields and bases can be laid out in the tail padding of previous
+  // bases.  If this happens, we need to allocate the base as an i8
+  // array; otherwise, we can use the subobject type.  However,
+  // actually doing that would require knowledge of what immediately
+  // follows this base in the layout, so instead we do a conservative
+  // approximation, which is to use the base subobject type if it
+  // has the same LLVM storage size as the nvsize.
+
+  // The nvsize, i.e. the unpadded size of the base class.
+  CharUnits nvsize = baseASTLayout.getNonVirtualSize();
+
+#if 0
+  const llvm::StructType *subobjectType = baseLayout.getBaseSubobjectLLVMType();
+  const llvm::StructLayout *baseLLVMLayout =
+    Types.getTargetData().getStructLayout(subobjectType);
+  CharUnits stsize = CharUnits::fromQuantity(baseLLVMLayout->getSizeInBytes());
+
+  if (nvsize == stsize)
+    AppendField(baseOffset, subobjectType);
+  else 
+#endif
+    AppendBytes(nvsize);
 }
 
-void CGRecordLayoutBuilder::LayoutNonVirtualBase(const CXXRecordDecl *BaseDecl,
-                                                 uint64_t BaseOffset) {
-  const ASTRecordLayout &Layout = 
-    Types.getContext().getASTRecordLayout(BaseDecl);
+void CGRecordLayoutBuilder::LayoutNonVirtualBase(const CXXRecordDecl *base,
+                                                 CharUnits baseOffset) {
+  // Ignore empty bases.
+  if (base->isEmpty()) return;
 
-  uint64_t NonVirtualSize = Layout.getNonVirtualSize();
+  const CGRecordLayout &baseLayout = Types.getCGRecordLayout(base);
+  if (IsZeroInitializableAsBase) {
+    assert(IsZeroInitializable &&
+           "class zero-initializable as base but not as complete object");
 
-  if (BaseDecl->isEmpty()) {
-    // FIXME: Lay out empty bases.
-    return;
+    IsZeroInitializable = IsZeroInitializableAsBase =
+      baseLayout.isZeroInitializableAsBase();
   }
 
-  CheckZeroInitializable(BaseDecl);
+  LayoutBase(base, baseLayout, baseOffset);
+  NonVirtualBases[base] = (FieldTypes.size() - 1);
+}
 
-  // FIXME: Actually use a better type than [sizeof(BaseDecl) x i8] when we can.
-  AppendPadding(BaseOffset / 8, 1);
-  
-  // Append the base field.
-  LLVMNonVirtualBases.push_back(LLVMBaseInfo(BaseDecl, FieldTypes.size()));
+void
+CGRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *base,
+                                         CharUnits baseOffset) {
+  // Ignore empty bases.
+  if (base->isEmpty()) return;
+
+  const CGRecordLayout &baseLayout = Types.getCGRecordLayout(base);
+  if (IsZeroInitializable)
+    IsZeroInitializable = baseLayout.isZeroInitializableAsBase();
+
+  LayoutBase(base, baseLayout, baseOffset);
+  VirtualBases[base] = (FieldTypes.size() - 1);
+}
 
-  AppendBytes(NonVirtualSize / 8);
+/// LayoutVirtualBases - layout the non-virtual bases of a record decl.
+void
+CGRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
+                                          const ASTRecordLayout &Layout) {
+  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
+       E = RD->bases_end(); I != E; ++I) {
+    const CXXRecordDecl *BaseDecl = 
+      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
+
+    // We only want to lay out virtual bases that aren't indirect primary bases
+    // of some other base.
+    if (I->isVirtual() && !IndirectPrimaryBases.count(BaseDecl)) {
+      // Only lay out the base once.
+      if (!LaidOutVirtualBases.insert(BaseDecl))
+        continue;
+
+      CharUnits vbaseOffset = Layout.getVBaseClassOffset(BaseDecl);
+      LayoutVirtualBase(BaseDecl, vbaseOffset);
+    }
+
+    if (!BaseDecl->getNumVBases()) {
+      // This base isn't interesting since it doesn't have any virtual bases.
+      continue;
+    }
+    
+    LayoutVirtualBases(BaseDecl, Layout);
+  }
 }
 
 void
@@ -493,13 +615,14 @@ CGRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD,
                                 /*isVarArg=*/true);
       const llvm::Type *VTableTy = FunctionType->getPointerTo();
 
-      assert(NextFieldOffsetInBytes == 0 &&
+      assert(NextFieldOffset.isZero() &&
              "VTable pointer must come first!");
-      AppendField(NextFieldOffsetInBytes, VTableTy->getPointerTo());
+      AppendField(CharUnits::Zero(), VTableTy->getPointerTo());
     } else {
-      // FIXME: Handle a virtual primary base.
-      if (!Layout.getPrimaryBaseWasVirtual())
-        LayoutNonVirtualBase(PrimaryBase, 0);
+      if (!Layout.isPrimaryBaseVirtual())
+        LayoutNonVirtualBase(PrimaryBase, CharUnits::Zero());
+      else
+        LayoutVirtualBase(PrimaryBase, CharUnits::Zero());
     }
   }
 
@@ -513,20 +636,61 @@ CGRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD,
       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 
     // We've already laid out the primary base.
-    if (BaseDecl == PrimaryBase && !Layout.getPrimaryBaseWasVirtual())
+    if (BaseDecl == PrimaryBase && !Layout.isPrimaryBaseVirtual())
       continue;
 
     LayoutNonVirtualBase(BaseDecl, Layout.getBaseClassOffset(BaseDecl));
   }
 }
 
+bool
+CGRecordLayoutBuilder::ComputeNonVirtualBaseType(const CXXRecordDecl *RD) {
+  const ASTRecordLayout &Layout = Types.getContext().getASTRecordLayout(RD);
+
+  CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
+  CharUnits NonVirtualAlign = Layout.getNonVirtualAlign();
+  CharUnits AlignedNonVirtualTypeSize =
+    NonVirtualSize.RoundUpToAlignment(NonVirtualAlign);
+  
+  // First check if we can use the same fields as for the complete class.
+  CharUnits RecordSize = Layout.getSize();
+  if (AlignedNonVirtualTypeSize == RecordSize)
+    return true;
+
+  // Check if we need padding.
+  CharUnits AlignedNextFieldOffset =
+    NextFieldOffset.RoundUpToAlignment(getAlignmentAsLLVMStruct());
+
+  if (AlignedNextFieldOffset > AlignedNonVirtualTypeSize) {
+    assert(!Packed && "cannot layout even as packed struct");
+    return false; // Needs packing.
+  }
+
+  bool needsPadding = (AlignedNonVirtualTypeSize != AlignedNextFieldOffset);
+  if (needsPadding) {
+    CharUnits NumBytes = AlignedNonVirtualTypeSize - AlignedNextFieldOffset;
+    FieldTypes.push_back(getByteArrayType(NumBytes));
+  }
+
+  BaseSubobjectType = llvm::StructType::get(Types.getLLVMContext(),
+                                            FieldTypes, Packed);
+
+  if (needsPadding) {
+    // Pull the padding back off.
+    FieldTypes.pop_back();
+  }
+
+  return true;
+}
+
 bool CGRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
   assert(!D->isUnion() && "Can't call LayoutFields on a union!");
-  assert(Alignment && "Did not set alignment!");
+  assert(!Alignment.isZero() && "Did not set alignment!");
 
   const ASTRecordLayout &Layout = Types.getContext().getASTRecordLayout(D);
 
-  if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D))
+  const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D);
+  if (RD)
     LayoutNonVirtualBases(RD, Layout);
 
   unsigned FieldNo = 0;
@@ -540,8 +704,23 @@ bool CGRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
     }
   }
 
+  if (RD) {
+    // We've laid out the non-virtual bases and the fields, now compute the
+    // non-virtual base field types.
+    if (!ComputeNonVirtualBaseType(RD)) {
+      assert(!Packed && "Could not layout even with a packed LLVM struct!");
+      return false;
+    }
+
+    // And lay out the virtual bases.
+    RD->getIndirectPrimaryBases(IndirectPrimaryBases);
+    if (Layout.isPrimaryBaseVirtual())
+      IndirectPrimaryBases.insert(Layout.getPrimaryBase());
+    LayoutVirtualBases(RD, Layout);
+  }
+  
   // Append tail padding if necessary.
-  AppendTailPadding(Layout.getSize());
+  AppendTailPadding(Types.getContext().toBits(Layout.getSize()));
 
   return true;
 }
@@ -549,129 +728,137 @@ bool CGRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
 void CGRecordLayoutBuilder::AppendTailPadding(uint64_t RecordSize) {
   assert(RecordSize % 8 == 0 && "Invalid record size!");
 
-  uint64_t RecordSizeInBytes = RecordSize / 8;
-  assert(NextFieldOffsetInBytes <= RecordSizeInBytes && "Size mismatch!");
+  CharUnits RecordSizeInBytes = CharUnits::fromQuantity(RecordSize / 8);
+  assert(NextFieldOffset <= RecordSizeInBytes && "Size mismatch!");
 
-  uint64_t AlignedNextFieldOffset =
-    llvm::RoundUpToAlignment(NextFieldOffsetInBytes, AlignmentAsLLVMStruct);
+  CharUnits AlignedNextFieldOffset =
+    NextFieldOffset.RoundUpToAlignment(getAlignmentAsLLVMStruct());
 
   if (AlignedNextFieldOffset == RecordSizeInBytes) {
     // We don't need any padding.
     return;
   }
 
-  unsigned NumPadBytes = RecordSizeInBytes - NextFieldOffsetInBytes;
+  CharUnits NumPadBytes = RecordSizeInBytes - NextFieldOffset;
   AppendBytes(NumPadBytes);
 }
 
-void CGRecordLayoutBuilder::AppendField(uint64_t FieldOffsetInBytes,
-                                        const llvm::Type *FieldTy) {
-  AlignmentAsLLVMStruct = std::max(AlignmentAsLLVMStruct,
-                                   getTypeAlignment(FieldTy));
+void CGRecordLayoutBuilder::AppendField(CharUnits fieldOffset,
+                                        const llvm::Type *fieldType) {
+  CharUnits fieldSize =
+    CharUnits::fromQuantity(Types.getTargetData().getTypeAllocSize(fieldType));
 
-  uint64_t FieldSizeInBytes = Types.getTargetData().getTypeAllocSize(FieldTy);
+  FieldTypes.push_back(fieldType);
 
-  FieldTypes.push_back(FieldTy);
-
-  NextFieldOffsetInBytes = FieldOffsetInBytes + FieldSizeInBytes;
+  NextFieldOffset = fieldOffset + fieldSize;
   BitsAvailableInLastField = 0;
 }
 
-void CGRecordLayoutBuilder::AppendPadding(uint64_t FieldOffsetInBytes,
-                                          unsigned FieldAlignment) {
-  assert(NextFieldOffsetInBytes <= FieldOffsetInBytes &&
+void CGRecordLayoutBuilder::AppendPadding(CharUnits fieldOffset,
+                                          CharUnits fieldAlignment) {
+  assert(NextFieldOffset <= fieldOffset &&
          "Incorrect field layout!");
 
   // Round up the field offset to the alignment of the field type.
-  uint64_t AlignedNextFieldOffsetInBytes =
-    llvm::RoundUpToAlignment(NextFieldOffsetInBytes, FieldAlignment);
+  CharUnits alignedNextFieldOffset =
+    NextFieldOffset.RoundUpToAlignment(fieldAlignment);
 
-  if (AlignedNextFieldOffsetInBytes < FieldOffsetInBytes) {
+  if (alignedNextFieldOffset < fieldOffset) {
     // Even with alignment, the field offset is not at the right place,
     // insert padding.
-    uint64_t PaddingInBytes = FieldOffsetInBytes - NextFieldOffsetInBytes;
+    CharUnits padding = fieldOffset - NextFieldOffset;
 
-    AppendBytes(PaddingInBytes);
+    AppendBytes(padding);
   }
 }
 
-void CGRecordLayoutBuilder::AppendBytes(uint64_t NumBytes) {
-  if (NumBytes == 0)
-    return;
+const llvm::Type *CGRecordLayoutBuilder::getByteArrayType(CharUnits numBytes) {
+  assert(!numBytes.isZero() && "Empty byte arrays aren't allowed.");
 
   const llvm::Type *Ty = llvm::Type::getInt8Ty(Types.getLLVMContext());
-  if (NumBytes > 1)
-    Ty = llvm::ArrayType::get(Ty, NumBytes);
+  if (numBytes > CharUnits::One())
+    Ty = llvm::ArrayType::get(Ty, numBytes.getQuantity());
+
+  return Ty;
+}
+
+void CGRecordLayoutBuilder::AppendBytes(CharUnits numBytes) {
+  if (numBytes.isZero())
+    return;
 
   // Append the padding field
-  AppendField(NextFieldOffsetInBytes, Ty);
+  AppendField(NextFieldOffset, getByteArrayType(numBytes));
 }
 
-unsigned CGRecordLayoutBuilder::getTypeAlignment(const llvm::Type *Ty) const {
+CharUnits CGRecordLayoutBuilder::getTypeAlignment(const llvm::Type *Ty) const {
   if (Packed)
-    return 1;
+    return CharUnits::One();
 
-  return Types.getTargetData().getABITypeAlignment(Ty);
+  return CharUnits::fromQuantity(Types.getTargetData().getABITypeAlignment(Ty));
 }
 
+CharUnits CGRecordLayoutBuilder::getAlignmentAsLLVMStruct() const {
+  if (Packed)
+    return CharUnits::One();
+
+  CharUnits maxAlignment = CharUnits::One();
+  for (size_t i = 0; i != FieldTypes.size(); ++i)
+    maxAlignment = std::max(maxAlignment, getTypeAlignment(FieldTypes[i]));
+
+  return maxAlignment;
+}
+
+/// Merge in whether a field of the given type is zero-initializable.
 void CGRecordLayoutBuilder::CheckZeroInitializable(QualType T) {
   // This record already contains a member pointer.
-  if (!IsZeroInitializable)
+  if (!IsZeroInitializableAsBase)
     return;
 
   // Can only have member pointers if we're compiling C++.
   if (!Types.getContext().getLangOptions().CPlusPlus)
     return;
 
-  T = Types.getContext().getBaseElementType(T);
+  const Type *elementType = T->getBaseElementTypeUnsafe();
 
-  if (const MemberPointerType *MPT = T->getAs<MemberPointerType>()) {
+  if (const MemberPointerType *MPT = elementType->getAs<MemberPointerType>()) {
     if (!Types.getCXXABI().isZeroInitializable(MPT))
-      IsZeroInitializable = false;
-  } else if (const RecordType *RT = T->getAs<RecordType>()) {
+      IsZeroInitializable = IsZeroInitializableAsBase = false;
+  } else if (const RecordType *RT = elementType->getAs<RecordType>()) {
     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
-    CheckZeroInitializable(RD);
+    const CGRecordLayout &Layout = Types.getCGRecordLayout(RD);
+    if (!Layout.isZeroInitializable())
+      IsZeroInitializable = IsZeroInitializableAsBase = false;
   }
 }
 
-void CGRecordLayoutBuilder::CheckZeroInitializable(const CXXRecordDecl *RD) {
-  // This record already contains a member pointer.
-  if (!IsZeroInitializable)
-    return;
-
-  // FIXME: It would be better if there was a way to explicitly compute the
-  // record layout instead of converting to a type.
-  Types.ConvertTagDeclType(RD);
-  
-  const CGRecordLayout &Layout = Types.getCGRecordLayout(RD);
-  
-  if (!Layout.isZeroInitializable())
-    IsZeroInitializable = false;
-}
-
 CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D) {
   CGRecordLayoutBuilder Builder(*this);
 
   Builder.Layout(D);
 
-  const llvm::Type *Ty = llvm::StructType::get(getLLVMContext(),
-                                               Builder.FieldTypes,
-                                               Builder.Packed);
+  const llvm::StructType *Ty = llvm::StructType::get(getLLVMContext(),
+                                                     Builder.FieldTypes,
+                                                     Builder.Packed);
+
+  // If we're in C++, compute the base subobject type.
+  const llvm::StructType *BaseTy = 0;
+  if (isa<CXXRecordDecl>(D)) {
+    BaseTy = Builder.BaseSubobjectType;
+    if (!BaseTy) BaseTy = Ty;
+  }
 
   CGRecordLayout *RL =
-    new CGRecordLayout(Ty, Builder.IsZeroInitializable);
+    new CGRecordLayout(Ty, BaseTy, Builder.IsZeroInitializable,
+                       Builder.IsZeroInitializableAsBase);
 
-  // Add all the non-virtual base field numbers.
-  RL->NonVirtualBaseFields.insert(Builder.LLVMNonVirtualBases.begin(),
-                                  Builder.LLVMNonVirtualBases.end());
+  RL->NonVirtualBases.swap(Builder.NonVirtualBases);
+  RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases);
 
   // Add all the field numbers.
-  RL->FieldInfo.insert(Builder.LLVMFields.begin(),
-                       Builder.LLVMFields.end());
+  RL->FieldInfo.swap(Builder.Fields);
 
   // Add bitfield info.
-  RL->BitFields.insert(Builder.LLVMBitFields.begin(),
-                       Builder.LLVMBitFields.end());
+  RL->BitFields.swap(Builder.BitFields);
 
   // Dump the layout, if requested.
   if (getContext().getLangOptions().DumpRecordLayouts) {
@@ -684,10 +871,26 @@ CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D) {
 
 #ifndef NDEBUG
   // Verify that the computed LLVM struct size matches the AST layout size.
-  uint64_t TypeSizeInBits = getContext().getASTRecordLayout(D).getSize();
+  const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D);
+
+  uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize());
   assert(TypeSizeInBits == getTargetData().getTypeAllocSizeInBits(Ty) &&
          "Type size mismatch!");
 
+  if (BaseTy) {
+    CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
+    CharUnits NonVirtualAlign = Layout.getNonVirtualAlign();
+    CharUnits AlignedNonVirtualTypeSize = 
+      NonVirtualSize.RoundUpToAlignment(NonVirtualAlign);
+
+    uint64_t AlignedNonVirtualTypeSizeInBits = 
+      getContext().toBits(AlignedNonVirtualTypeSize);
+
+    assert(AlignedNonVirtualTypeSizeInBits == 
+           getTargetData().getTypeAllocSizeInBits(BaseTy) &&
+           "Type size mismatch!");
+  }
+                                     
   // Verify that the LLVM and AST field offsets agree.
   const llvm::StructType *ST =
     dyn_cast<llvm::StructType>(RL->getLLVMType());
@@ -729,7 +932,9 @@ CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D) {
 
 void CGRecordLayout::print(llvm::raw_ostream &OS) const {
   OS << "<CGRecordLayout\n";
-  OS << "  LLVMType:" << *LLVMType << "\n";
+  OS << "  LLVMType:" << *CompleteObjectType << "\n";
+  if (BaseSubobjectType)
+    OS << "  NonVirtualBaseLLVMType:" << *BaseSubobjectType << "\n"; 
   OS << "  IsZeroInitializable:" << IsZeroInitializable << "\n";
   OS << "  BitFields:[\n";