Home | History | Annotate | Download | only in CodeGen 
      1 //===--- CGRecordLayoutBuilder.cpp - CGRecordLayout builder  ----*- C++ -*-===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // Builder implementation for CGRecordLayout objects.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #include "CGRecordLayout.h"
     15 #include "CGCXXABI.h"
     16 #include "CodeGenTypes.h"
     17 #include "clang/AST/ASTContext.h"
     18 #include "clang/AST/Attr.h"
     19 #include "clang/AST/CXXInheritance.h"
     20 #include "clang/AST/DeclCXX.h"
     21 #include "clang/AST/Expr.h"
     22 #include "clang/AST/RecordLayout.h"
     23 #include "clang/Frontend/CodeGenOptions.h"
     24 #include "llvm/IR/DataLayout.h"
     25 #include "llvm/IR/DerivedTypes.h"
     26 #include "llvm/IR/Type.h"
     27 #include "llvm/Support/Debug.h"
     28 #include "llvm/Support/raw_ostream.h"
     29 using namespace clang;
     30 using namespace CodeGen;
     31 
     32 namespace {
     33 
     34 class CGRecordLayoutBuilder {
     35 public:
     36   /// FieldTypes - Holds the LLVM types that the struct is created from.
     37   ///
     38   SmallVector<llvm::Type *, 16> FieldTypes;
     39 
     40   /// BaseSubobjectType - Holds the LLVM type for the non-virtual part
     41   /// of the struct. For example, consider:
     42   ///
     43   /// struct A { int i; };
     44   /// struct B { void *v; };
     45   /// struct C : virtual A, B { };
     46   ///
     47   /// The LLVM type of C will be
     48   /// %struct.C = type { i32 (...)**, %struct.A, i32, %struct.B }
     49   ///
     50   /// And the LLVM type of the non-virtual base struct will be
     51   /// %struct.C.base = type { i32 (...)**, %struct.A, i32 }
     52   ///
     53   /// This only gets initialized if the base subobject type is
     54   /// different from the complete-object type.
     55   llvm::StructType *BaseSubobjectType;
     56 
     57   /// FieldInfo - Holds a field and its corresponding LLVM field number.
     58   llvm::DenseMap<const FieldDecl *, unsigned> Fields;
     59 
     60   /// BitFieldInfo - Holds location and size information about a bit field.
     61   llvm::DenseMap<const FieldDecl *, CGBitFieldInfo> BitFields;
     62 
     63   llvm::DenseMap<const CXXRecordDecl *, unsigned> NonVirtualBases;
     64   llvm::DenseMap<const CXXRecordDecl *, unsigned> VirtualBases;
     65 
     66   /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
     67   /// primary base classes for some other direct or indirect base class.
     68   CXXIndirectPrimaryBaseSet IndirectPrimaryBases;
     69 
     70   /// LaidOutVirtualBases - A set of all laid out virtual bases, used to avoid
     71   /// avoid laying out virtual bases more than once.
     72   llvm::SmallPtrSet<const CXXRecordDecl *, 4> LaidOutVirtualBases;
     73 
     74   /// IsZeroInitializable - Whether this struct can be C++
     75   /// zero-initialized with an LLVM zeroinitializer.
     76   bool IsZeroInitializable;
     77   bool IsZeroInitializableAsBase;
     78 
     79   /// Packed - Whether the resulting LLVM struct will be packed or not.
     80   bool Packed;
     81 
     82   /// IsMsStruct - Whether ms_struct is in effect or not
     83   bool IsMsStruct;
     84 
     85 private:
     86   CodeGenTypes &Types;
     87 
     88   /// LastLaidOutBaseInfo - Contains the offset and non-virtual size of the
     89   /// last base laid out. Used so that we can replace the last laid out base
     90   /// type with an i8 array if needed.
     91   struct LastLaidOutBaseInfo {
     92     CharUnits Offset;
     93     CharUnits NonVirtualSize;
     94 
     95     bool isValid() const { return !NonVirtualSize.isZero(); }
     96     void invalidate() { NonVirtualSize = CharUnits::Zero(); }
     97 
     98   } LastLaidOutBase;
     99 
    100   /// Alignment - Contains the alignment of the RecordDecl.
    101   CharUnits Alignment;
    102 
    103   /// NextFieldOffset - Holds the next field offset.
    104   CharUnits NextFieldOffset;
    105 
    106   /// LayoutUnionField - Will layout a field in an union and return the type
    107   /// that the field will have.
    108   llvm::Type *LayoutUnionField(const FieldDecl *Field,
    109                                const ASTRecordLayout &Layout);
    110 
    111   /// LayoutUnion - Will layout a union RecordDecl.
    112   void LayoutUnion(const RecordDecl *D);
    113 
    114   /// Lay out a sequence of contiguous bitfields.
    115   bool LayoutBitfields(const ASTRecordLayout &Layout,
    116                        unsigned &FirstFieldNo,
    117                        RecordDecl::field_iterator &FI,
    118                        RecordDecl::field_iterator FE);
    119 
    120   /// LayoutField - try to layout all fields in the record decl.
    121   /// Returns false if the operation failed because the struct is not packed.
    122   bool LayoutFields(const RecordDecl *D);
    123 
    124   /// Layout a single base, virtual or non-virtual
    125   bool LayoutBase(const CXXRecordDecl *base,
    126                   const CGRecordLayout &baseLayout,
    127                   CharUnits baseOffset);
    128 
    129   /// LayoutVirtualBase - layout a single virtual base.
    130   bool LayoutVirtualBase(const CXXRecordDecl *base,
    131                          CharUnits baseOffset);
    132 
    133   /// LayoutVirtualBases - layout the virtual bases of a record decl.
    134   bool LayoutVirtualBases(const CXXRecordDecl *RD,
    135                           const ASTRecordLayout &Layout);
    136 
    137   /// MSLayoutVirtualBases - layout the virtual bases of a record decl,
    138   /// like MSVC.
    139   bool MSLayoutVirtualBases(const CXXRecordDecl *RD,
    140                             const ASTRecordLayout &Layout);
    141 
    142   /// LayoutNonVirtualBase - layout a single non-virtual base.
    143   bool LayoutNonVirtualBase(const CXXRecordDecl *base,
    144                             CharUnits baseOffset);
    145 
    146   /// LayoutNonVirtualBases - layout the virtual bases of a record decl.
    147   bool LayoutNonVirtualBases(const CXXRecordDecl *RD,
    148                              const ASTRecordLayout &Layout);
    149 
    150   /// ComputeNonVirtualBaseType - Compute the non-virtual base field types.
    151   bool ComputeNonVirtualBaseType(const CXXRecordDecl *RD);
    152 
    153   /// LayoutField - layout a single field. Returns false if the operation failed
    154   /// because the current struct is not packed.
    155   bool LayoutField(const FieldDecl *D, uint64_t FieldOffset);
    156 
    157   /// LayoutBitField - layout a single bit field.
    158   void LayoutBitField(const FieldDecl *D, uint64_t FieldOffset);
    159 
    160   /// AppendField - Appends a field with the given offset and type.
    161   void AppendField(CharUnits fieldOffset, llvm::Type *FieldTy);
    162 
    163   /// AppendPadding - Appends enough padding bytes so that the total
    164   /// struct size is a multiple of the field alignment.
    165   void AppendPadding(CharUnits fieldOffset, CharUnits fieldAlignment);
    166 
    167   /// ResizeLastBaseFieldIfNecessary - Fields and bases can be laid out in the
    168   /// tail padding of a previous base. If this happens, the type of the previous
    169   /// base needs to be changed to an array of i8. Returns true if the last
    170   /// laid out base was resized.
    171   bool ResizeLastBaseFieldIfNecessary(CharUnits offset);
    172 
    173   /// getByteArrayType - Returns a byte array type with the given number of
    174   /// elements.
    175   llvm::Type *getByteArrayType(CharUnits NumBytes);
    176 
    177   /// AppendBytes - Append a given number of bytes to the record.
    178   void AppendBytes(CharUnits numBytes);
    179 
    180   /// AppendTailPadding - Append enough tail padding so that the type will have
    181   /// the passed size.
    182   void AppendTailPadding(CharUnits RecordSize);
    183 
    184   CharUnits getTypeAlignment(llvm::Type *Ty) const;
    185 
    186   /// getAlignmentAsLLVMStruct - Returns the maximum alignment of all the
    187   /// LLVM element types.
    188   CharUnits getAlignmentAsLLVMStruct() const;
    189 
    190   /// CheckZeroInitializable - Check if the given type contains a pointer
    191   /// to data member.
    192   void CheckZeroInitializable(QualType T);
    193 
    194 public:
    195   CGRecordLayoutBuilder(CodeGenTypes &Types)
    196     : BaseSubobjectType(0),
    197       IsZeroInitializable(true), IsZeroInitializableAsBase(true),
    198       Packed(false), IsMsStruct(false),
    199       Types(Types) { }
    200 
    201   /// Layout - Will layout a RecordDecl.
    202   void Layout(const RecordDecl *D);
    203 };
    204 
    205 }
    206 
    207 void CGRecordLayoutBuilder::Layout(const RecordDecl *D) {
    208   Alignment = Types.getContext().getASTRecordLayout(D).getAlignment();
    209   Packed = D->hasAttr<PackedAttr>();
    210 
    211   IsMsStruct = D->isMsStruct(Types.getContext());
    212 
    213   if (D->isUnion()) {
    214     LayoutUnion(D);
    215     return;
    216   }
    217 
    218   if (LayoutFields(D))
    219     return;
    220 
    221   // We weren't able to layout the struct. Try again with a packed struct
    222   Packed = true;
    223   LastLaidOutBase.invalidate();
    224   NextFieldOffset = CharUnits::Zero();
    225   FieldTypes.clear();
    226   Fields.clear();
    227   BitFields.clear();
    228   NonVirtualBases.clear();
    229   VirtualBases.clear();
    230 
    231   LayoutFields(D);
    232 }
    233 
    234 CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
    235                                         const FieldDecl *FD,
    236                                         uint64_t Offset, uint64_t Size,
    237                                         uint64_t StorageSize,
    238                                         uint64_t StorageAlignment) {
    239   llvm::Type *Ty = Types.ConvertTypeForMem(FD->getType());
    240   CharUnits TypeSizeInBytes =
    241     CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(Ty));
    242   uint64_t TypeSizeInBits = Types.getContext().toBits(TypeSizeInBytes);
    243 
    244   bool IsSigned = FD->getType()->isSignedIntegerOrEnumerationType();
    245 
    246   if (Size > TypeSizeInBits) {
    247     // We have a wide bit-field. The extra bits are only used for padding, so
    248     // if we have a bitfield of type T, with size N:
    249     //
    250     // T t : N;
    251     //
    252     // We can just assume that it's:
    253     //
    254     // T t : sizeof(T);
    255     //
    256     Size = TypeSizeInBits;
    257   }
    258 
    259   // Reverse the bit offsets for big endian machines. Because we represent
    260   // a bitfield as a single large integer load, we can imagine the bits
    261   // counting from the most-significant-bit instead of the
    262   // least-significant-bit.
    263   if (Types.getDataLayout().isBigEndian()) {
    264     Offset = StorageSize - (Offset + Size);
    265   }
    266 
    267   return CGBitFieldInfo(Offset, Size, IsSigned, StorageSize, StorageAlignment);
    268 }
    269 
    270 /// \brief Layout the range of bitfields from BFI to BFE as contiguous storage.
    271 bool CGRecordLayoutBuilder::LayoutBitfields(const ASTRecordLayout &Layout,
    272                                             unsigned &FirstFieldNo,
    273                                             RecordDecl::field_iterator &FI,
    274                                             RecordDecl::field_iterator FE) {
    275   assert(FI != FE);
    276   uint64_t FirstFieldOffset = Layout.getFieldOffset(FirstFieldNo);
    277   uint64_t NextFieldOffsetInBits = Types.getContext().toBits(NextFieldOffset);
    278 
    279   unsigned CharAlign = Types.getContext().getTargetInfo().getCharAlign();
    280   assert(FirstFieldOffset % CharAlign == 0 &&
    281          "First field offset is misaligned");
    282   CharUnits FirstFieldOffsetInBytes
    283     = Types.getContext().toCharUnitsFromBits(FirstFieldOffset);
    284 
    285   unsigned StorageAlignment
    286     = llvm::MinAlign(Alignment.getQuantity(),
    287                      FirstFieldOffsetInBytes.getQuantity());
    288 
    289   if (FirstFieldOffset < NextFieldOffsetInBits) {
    290     CharUnits FieldOffsetInCharUnits =
    291       Types.getContext().toCharUnitsFromBits(FirstFieldOffset);
    292 
    293     // Try to resize the last base field.
    294     if (!ResizeLastBaseFieldIfNecessary(FieldOffsetInCharUnits))
    295       llvm_unreachable("We must be able to resize the last base if we need to "
    296                        "pack bits into it.");
    297 
    298     NextFieldOffsetInBits = Types.getContext().toBits(NextFieldOffset);
    299     assert(FirstFieldOffset >= NextFieldOffsetInBits);
    300   }
    301 
    302   // Append padding if necessary.
    303   AppendPadding(Types.getContext().toCharUnitsFromBits(FirstFieldOffset),
    304                 CharUnits::One());
    305 
    306   // Find the last bitfield in a contiguous run of bitfields.
    307   RecordDecl::field_iterator BFI = FI;
    308   unsigned LastFieldNo = FirstFieldNo;
    309   uint64_t NextContiguousFieldOffset = FirstFieldOffset;
    310   for (RecordDecl::field_iterator FJ = FI;
    311        (FJ != FE && (*FJ)->isBitField() &&
    312         NextContiguousFieldOffset == Layout.getFieldOffset(LastFieldNo) &&
    313         (*FJ)->getBitWidthValue(Types.getContext()) != 0); FI = FJ++) {
    314     NextContiguousFieldOffset += (*FJ)->getBitWidthValue(Types.getContext());
    315     ++LastFieldNo;
    316 
    317     // We must use packed structs for packed fields, and also unnamed bit
    318     // fields since they don't affect the struct alignment.
    319     if (!Packed && ((*FJ)->hasAttr<PackedAttr>() || !(*FJ)->getDeclName()))
    320       return false;
    321   }
    322   RecordDecl::field_iterator BFE = llvm::next(FI);
    323   --LastFieldNo;
    324   assert(LastFieldNo >= FirstFieldNo && "Empty run of contiguous bitfields");
    325   FieldDecl *LastFD = *FI;
    326 
    327   // Find the last bitfield's offset, add its size, and round it up to the
    328   // character alignment to compute the storage required.
    329   uint64_t LastFieldOffset = Layout.getFieldOffset(LastFieldNo);
    330   uint64_t LastFieldSize = LastFD->getBitWidthValue(Types.getContext());
    331   uint64_t TotalBits = (LastFieldOffset + LastFieldSize) - FirstFieldOffset;
    332   CharUnits StorageBytes = Types.getContext().toCharUnitsFromBits(
    333     llvm::RoundUpToAlignment(TotalBits, CharAlign));
    334   uint64_t StorageBits = Types.getContext().toBits(StorageBytes);
    335 
    336   // Grow the storage to encompass any known padding in the layout when doing
    337   // so will make the storage a power-of-two. There are two cases when we can
    338   // do this. The first is when we have a subsequent field and can widen up to
    339   // its offset. The second is when the data size of the AST record layout is
    340   // past the end of the current storage. The latter is true when there is tail
    341   // padding on a struct and no members of a super class can be packed into it.
    342   //
    343   // Note that we widen the storage as much as possible here to express the
    344   // maximum latitude the language provides, and rely on the backend to lower
    345   // these in conjunction with shifts and masks to narrower operations where
    346   // beneficial.
    347   uint64_t EndOffset = Types.getContext().toBits(Layout.getDataSize());
    348   if (BFE != FE)
    349     // If there are more fields to be laid out, the offset at the end of the
    350     // bitfield is the offset of the next field in the record.
    351     EndOffset = Layout.getFieldOffset(LastFieldNo + 1);
    352   assert(EndOffset >= (FirstFieldOffset + TotalBits) &&
    353          "End offset is not past the end of the known storage bits.");
    354   uint64_t SpaceBits = EndOffset - FirstFieldOffset;
    355   uint64_t LongBits = Types.getContext().getTargetInfo().getLongWidth();
    356   uint64_t WidenedBits = (StorageBits / LongBits) * LongBits +
    357                          llvm::NextPowerOf2(StorageBits % LongBits - 1);
    358   assert(WidenedBits >= StorageBits && "Widening shrunk the bits!");
    359   if (WidenedBits <= SpaceBits) {
    360     StorageBits = WidenedBits;
    361     StorageBytes = Types.getContext().toCharUnitsFromBits(StorageBits);
    362     assert(StorageBits == (uint64_t)Types.getContext().toBits(StorageBytes));
    363   }
    364 
    365   unsigned FieldIndex = FieldTypes.size();
    366   AppendBytes(StorageBytes);
    367 
    368   // Now walk the bitfields associating them with this field of storage and
    369   // building up the bitfield specific info.
    370   unsigned FieldNo = FirstFieldNo;
    371   for (; BFI != BFE; ++BFI, ++FieldNo) {
    372     FieldDecl *FD = *BFI;
    373     uint64_t FieldOffset = Layout.getFieldOffset(FieldNo) - FirstFieldOffset;
    374     uint64_t FieldSize = FD->getBitWidthValue(Types.getContext());
    375     Fields[FD] = FieldIndex;
    376     BitFields[FD] = CGBitFieldInfo::MakeInfo(Types, FD, FieldOffset, FieldSize,
    377                                              StorageBits, StorageAlignment);
    378   }
    379   FirstFieldNo = LastFieldNo;
    380   return true;
    381 }
    382 
    383 bool CGRecordLayoutBuilder::LayoutField(const FieldDecl *D,
    384                                         uint64_t fieldOffset) {
    385   // If the field is packed, then we need a packed struct.
    386   if (!Packed && D->hasAttr<PackedAttr>())
    387     return false;
    388 
    389   assert(!D->isBitField() && "Bitfields should be laid out seperately.");
    390 
    391   CheckZeroInitializable(D->getType());
    392 
    393   assert(fieldOffset % Types.getTarget().getCharWidth() == 0
    394          && "field offset is not on a byte boundary!");
    395   CharUnits fieldOffsetInBytes
    396     = Types.getContext().toCharUnitsFromBits(fieldOffset);
    397 
    398   llvm::Type *Ty = Types.ConvertTypeForMem(D->getType());
    399   CharUnits typeAlignment = getTypeAlignment(Ty);
    400 
    401   // If the type alignment is larger then the struct alignment, we must use
    402   // a packed struct.
    403   if (typeAlignment > Alignment) {
    404     assert(!Packed && "Alignment is wrong even with packed struct!");
    405     return false;
    406   }
    407 
    408   if (!Packed) {
    409     if (const RecordType *RT = D->getType()->getAs<RecordType>()) {
    410       const RecordDecl *RD = cast<RecordDecl>(RT->getDecl());
    411       if (const MaxFieldAlignmentAttr *MFAA =
    412             RD->getAttr<MaxFieldAlignmentAttr>()) {
    413         if (MFAA->getAlignment() != Types.getContext().toBits(typeAlignment))
    414           return false;
    415       }
    416     }
    417   }
    418 
    419   // Round up the field offset to the alignment of the field type.
    420   CharUnits alignedNextFieldOffsetInBytes =
    421     NextFieldOffset.RoundUpToAlignment(typeAlignment);
    422 
    423   if (fieldOffsetInBytes < alignedNextFieldOffsetInBytes) {
    424     // Try to resize the last base field.
    425     if (ResizeLastBaseFieldIfNecessary(fieldOffsetInBytes)) {
    426       alignedNextFieldOffsetInBytes =
    427         NextFieldOffset.RoundUpToAlignment(typeAlignment);
    428     }
    429   }
    430 
    431   if (fieldOffsetInBytes < alignedNextFieldOffsetInBytes) {
    432     assert(!Packed && "Could not place field even with packed struct!");
    433     return false;
    434   }
    435 
    436   AppendPadding(fieldOffsetInBytes, typeAlignment);
    437 
    438   // Now append the field.
    439   Fields[D] = FieldTypes.size();
    440   AppendField(fieldOffsetInBytes, Ty);
    441 
    442   LastLaidOutBase.invalidate();
    443   return true;
    444 }
    445 
    446 llvm::Type *
    447 CGRecordLayoutBuilder::LayoutUnionField(const FieldDecl *Field,
    448                                         const ASTRecordLayout &Layout) {
    449   Fields[Field] = 0;
    450   if (Field->isBitField()) {
    451     uint64_t FieldSize = Field->getBitWidthValue(Types.getContext());
    452 
    453     // Ignore zero sized bit fields.
    454     if (FieldSize == 0)
    455       return 0;
    456 
    457     unsigned StorageBits = llvm::RoundUpToAlignment(
    458       FieldSize, Types.getContext().getTargetInfo().getCharAlign());
    459     CharUnits NumBytesToAppend
    460       = Types.getContext().toCharUnitsFromBits(StorageBits);
    461 
    462     llvm::Type *FieldTy = llvm::Type::getInt8Ty(Types.getLLVMContext());
    463     if (NumBytesToAppend > CharUnits::One())
    464       FieldTy = llvm::ArrayType::get(FieldTy, NumBytesToAppend.getQuantity());
    465 
    466     // Add the bit field info.
    467     BitFields[Field] = CGBitFieldInfo::MakeInfo(Types, Field, 0, FieldSize,
    468                                                 StorageBits,
    469                                                 Alignment.getQuantity());
    470     return FieldTy;
    471   }
    472 
    473   // This is a regular union field.
    474   return Types.ConvertTypeForMem(Field->getType());
    475 }
    476 
    477 void CGRecordLayoutBuilder::LayoutUnion(const RecordDecl *D) {
    478   assert(D->isUnion() && "Can't call LayoutUnion on a non-union record!");
    479 
    480   const ASTRecordLayout &layout = Types.getContext().getASTRecordLayout(D);
    481 
    482   llvm::Type *unionType = 0;
    483   CharUnits unionSize = CharUnits::Zero();
    484   CharUnits unionAlign = CharUnits::Zero();
    485 
    486   bool hasOnlyZeroSizedBitFields = true;
    487   bool checkedFirstFieldZeroInit = false;
    488 
    489   unsigned fieldNo = 0;
    490   for (RecordDecl::field_iterator field = D->field_begin(),
    491        fieldEnd = D->field_end(); field != fieldEnd; ++field, ++fieldNo) {
    492     assert(layout.getFieldOffset(fieldNo) == 0 &&
    493           "Union field offset did not start at the beginning of record!");
    494     llvm::Type *fieldType = LayoutUnionField(*field, layout);
    495 
    496     if (!fieldType)
    497       continue;
    498 
    499     if (field->getDeclName() && !checkedFirstFieldZeroInit) {
    500       CheckZeroInitializable(field->getType());
    501       checkedFirstFieldZeroInit = true;
    502     }
    503 
    504     hasOnlyZeroSizedBitFields = false;
    505 
    506     CharUnits fieldAlign = CharUnits::fromQuantity(
    507                           Types.getDataLayout().getABITypeAlignment(fieldType));
    508     CharUnits fieldSize = CharUnits::fromQuantity(
    509                              Types.getDataLayout().getTypeAllocSize(fieldType));
    510 
    511     if (fieldAlign < unionAlign)
    512       continue;
    513 
    514     if (fieldAlign > unionAlign || fieldSize > unionSize) {
    515       unionType = fieldType;
    516       unionAlign = fieldAlign;
    517       unionSize = fieldSize;
    518     }
    519   }
    520 
    521   // Now add our field.
    522   if (unionType) {
    523     AppendField(CharUnits::Zero(), unionType);
    524 
    525     if (getTypeAlignment(unionType) > layout.getAlignment()) {
    526       // We need a packed struct.
    527       Packed = true;
    528       unionAlign = CharUnits::One();
    529     }
    530   }
    531   if (unionAlign.isZero()) {
    532     (void)hasOnlyZeroSizedBitFields;
    533     assert(hasOnlyZeroSizedBitFields &&
    534            "0-align record did not have all zero-sized bit-fields!");
    535     unionAlign = CharUnits::One();
    536   }
    537 
    538   // Append tail padding.
    539   CharUnits recordSize = layout.getSize();
    540   if (recordSize > unionSize)
    541     AppendPadding(recordSize, unionAlign);
    542 }
    543 
    544 bool CGRecordLayoutBuilder::LayoutBase(const CXXRecordDecl *base,
    545                                        const CGRecordLayout &baseLayout,
    546                                        CharUnits baseOffset) {
    547   ResizeLastBaseFieldIfNecessary(baseOffset);
    548 
    549   AppendPadding(baseOffset, CharUnits::One());
    550 
    551   const ASTRecordLayout &baseASTLayout
    552     = Types.getContext().getASTRecordLayout(base);
    553 
    554   LastLaidOutBase.Offset = NextFieldOffset;
    555   LastLaidOutBase.NonVirtualSize = baseASTLayout.getNonVirtualSize();
    556 
    557   llvm::StructType *subobjectType = baseLayout.getBaseSubobjectLLVMType();
    558   if (getTypeAlignment(subobjectType) > Alignment)
    559     return false;
    560 
    561   AppendField(baseOffset, subobjectType);
    562   return true;
    563 }
    564 
    565 bool CGRecordLayoutBuilder::LayoutNonVirtualBase(const CXXRecordDecl *base,
    566                                                  CharUnits baseOffset) {
    567   // Ignore empty bases.
    568   if (base->isEmpty()) return true;
    569 
    570   const CGRecordLayout &baseLayout = Types.getCGRecordLayout(base);
    571   if (IsZeroInitializableAsBase) {
    572     assert(IsZeroInitializable &&
    573            "class zero-initializable as base but not as complete object");
    574 
    575     IsZeroInitializable = IsZeroInitializableAsBase =
    576       baseLayout.isZeroInitializableAsBase();
    577   }
    578 
    579   if (!LayoutBase(base, baseLayout, baseOffset))
    580     return false;
    581   NonVirtualBases[base] = (FieldTypes.size() - 1);
    582   return true;
    583 }
    584 
    585 bool
    586 CGRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *base,
    587                                          CharUnits baseOffset) {
    588   // Ignore empty bases.
    589   if (base->isEmpty()) return true;
    590 
    591   const CGRecordLayout &baseLayout = Types.getCGRecordLayout(base);
    592   if (IsZeroInitializable)
    593     IsZeroInitializable = baseLayout.isZeroInitializableAsBase();
    594 
    595   if (!LayoutBase(base, baseLayout, baseOffset))
    596     return false;
    597   VirtualBases[base] = (FieldTypes.size() - 1);
    598   return true;
    599 }
    600 
    601 bool
    602 CGRecordLayoutBuilder::MSLayoutVirtualBases(const CXXRecordDecl *RD,
    603                                           const ASTRecordLayout &Layout) {
    604   if (!RD->getNumVBases())
    605     return true;
    606 
    607   // The vbases list is uniqued and ordered by a depth-first
    608   // traversal, which is what we need here.
    609   for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
    610         E = RD->vbases_end(); I != E; ++I) {
    611 
    612     const CXXRecordDecl *BaseDecl =
    613       cast<CXXRecordDecl>(I->getType()->castAs<RecordType>()->getDecl());
    614 
    615     CharUnits vbaseOffset = Layout.getVBaseClassOffset(BaseDecl);
    616     if (!LayoutVirtualBase(BaseDecl, vbaseOffset))
    617       return false;
    618   }
    619   return true;
    620 }
    621 
    622 /// LayoutVirtualBases - layout the non-virtual bases of a record decl.
    623 bool
    624 CGRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
    625                                           const ASTRecordLayout &Layout) {
    626   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
    627        E = RD->bases_end(); I != E; ++I) {
    628     const CXXRecordDecl *BaseDecl =
    629       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
    630 
    631     // We only want to lay out virtual bases that aren't indirect primary bases
    632     // of some other base.
    633     if (I->isVirtual() && !IndirectPrimaryBases.count(BaseDecl)) {
    634       // Only lay out the base once.
    635       if (!LaidOutVirtualBases.insert(BaseDecl))
    636         continue;
    637 
    638       CharUnits vbaseOffset = Layout.getVBaseClassOffset(BaseDecl);
    639       if (!LayoutVirtualBase(BaseDecl, vbaseOffset))
    640         return false;
    641     }
    642 
    643     if (!BaseDecl->getNumVBases()) {
    644       // This base isn't interesting since it doesn't have any virtual bases.
    645       continue;
    646     }
    647 
    648     if (!LayoutVirtualBases(BaseDecl, Layout))
    649       return false;
    650   }
    651   return true;
    652 }
    653 
    654 bool
    655 CGRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD,
    656                                              const ASTRecordLayout &Layout) {
    657   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
    658 
    659   // If we have a primary base, lay it out first.
    660   if (PrimaryBase) {
    661     if (!Layout.isPrimaryBaseVirtual()) {
    662       if (!LayoutNonVirtualBase(PrimaryBase, CharUnits::Zero()))
    663         return false;
    664     } else {
    665       if (!LayoutVirtualBase(PrimaryBase, CharUnits::Zero()))
    666         return false;
    667     }
    668 
    669   // Otherwise, add a vtable / vf-table if the layout says to do so.
    670   } else if (Layout.hasOwnVFPtr()) {
    671     llvm::Type *FunctionType =
    672       llvm::FunctionType::get(llvm::Type::getInt32Ty(Types.getLLVMContext()),
    673                               /*isVarArg=*/true);
    674     llvm::Type *VTableTy = FunctionType->getPointerTo();
    675 
    676     if (getTypeAlignment(VTableTy) > Alignment) {
    677       // FIXME: Should we allow this to happen in Sema?
    678       assert(!Packed && "Alignment is wrong even with packed struct!");
    679       return false;
    680     }
    681 
    682     assert(NextFieldOffset.isZero() &&
    683            "VTable pointer must come first!");
    684     AppendField(CharUnits::Zero(), VTableTy->getPointerTo());
    685   }
    686 
    687   // Layout the non-virtual bases.
    688   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
    689        E = RD->bases_end(); I != E; ++I) {
    690     if (I->isVirtual())
    691       continue;
    692 
    693     const CXXRecordDecl *BaseDecl =
    694       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
    695 
    696     // We've already laid out the primary base.
    697     if (BaseDecl == PrimaryBase && !Layout.isPrimaryBaseVirtual())
    698       continue;
    699 
    700     if (!LayoutNonVirtualBase(BaseDecl, Layout.getBaseClassOffset(BaseDecl)))
    701       return false;
    702   }
    703 
    704   // Add a vb-table pointer if the layout insists.
    705   if (Layout.getVBPtrOffset() != CharUnits::fromQuantity(-1)) {
    706     CharUnits VBPtrOffset = Layout.getVBPtrOffset();
    707     llvm::Type *Vbptr = llvm::Type::getInt32PtrTy(Types.getLLVMContext());
    708     AppendPadding(VBPtrOffset, getTypeAlignment(Vbptr));
    709     AppendField(VBPtrOffset, Vbptr);
    710   }
    711 
    712   return true;
    713 }
    714 
    715 bool
    716 CGRecordLayoutBuilder::ComputeNonVirtualBaseType(const CXXRecordDecl *RD) {
    717   const ASTRecordLayout &Layout = Types.getContext().getASTRecordLayout(RD);
    718 
    719   CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
    720   CharUnits NonVirtualAlign = Layout.getNonVirtualAlign();
    721   CharUnits AlignedNonVirtualTypeSize =
    722     NonVirtualSize.RoundUpToAlignment(NonVirtualAlign);
    723 
    724   // First check if we can use the same fields as for the complete class.
    725   CharUnits RecordSize = Layout.getSize();
    726   if (AlignedNonVirtualTypeSize == RecordSize)
    727     return true;
    728 
    729   // Check if we need padding.
    730   CharUnits AlignedNextFieldOffset =
    731     NextFieldOffset.RoundUpToAlignment(getAlignmentAsLLVMStruct());
    732 
    733   if (AlignedNextFieldOffset > AlignedNonVirtualTypeSize) {
    734     assert(!Packed && "cannot layout even as packed struct");
    735     return false; // Needs packing.
    736   }
    737 
    738   bool needsPadding = (AlignedNonVirtualTypeSize != AlignedNextFieldOffset);
    739   if (needsPadding) {
    740     CharUnits NumBytes = AlignedNonVirtualTypeSize - AlignedNextFieldOffset;
    741     FieldTypes.push_back(getByteArrayType(NumBytes));
    742   }
    743 
    744   BaseSubobjectType = llvm::StructType::create(Types.getLLVMContext(),
    745                                                FieldTypes, "", Packed);
    746   Types.addRecordTypeName(RD, BaseSubobjectType, ".base");
    747 
    748   // Pull the padding back off.
    749   if (needsPadding)
    750     FieldTypes.pop_back();
    751 
    752   return true;
    753 }
    754 
    755 bool CGRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
    756   assert(!D->isUnion() && "Can't call LayoutFields on a union!");
    757   assert(!Alignment.isZero() && "Did not set alignment!");
    758 
    759   const ASTRecordLayout &Layout = Types.getContext().getASTRecordLayout(D);
    760 
    761   const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D);
    762   if (RD)
    763     if (!LayoutNonVirtualBases(RD, Layout))
    764       return false;
    765 
    766   unsigned FieldNo = 0;
    767   const FieldDecl *LastFD = 0;
    768 
    769   for (RecordDecl::field_iterator FI = D->field_begin(), FE = D->field_end();
    770        FI != FE; ++FI, ++FieldNo) {
    771     FieldDecl *FD = *FI;
    772     if (IsMsStruct) {
    773       // Zero-length bitfields following non-bitfield members are
    774       // ignored:
    775       if (Types.getContext().ZeroBitfieldFollowsNonBitfield(FD, LastFD)) {
    776         --FieldNo;
    777         continue;
    778       }
    779       LastFD = FD;
    780     }
    781 
    782     // If this field is a bitfield, layout all of the consecutive
    783     // non-zero-length bitfields and the last zero-length bitfield; these will
    784     // all share storage.
    785     if (FD->isBitField()) {
    786       // If all we have is a zero-width bitfield, skip it.
    787       if (FD->getBitWidthValue(Types.getContext()) == 0)
    788         continue;
    789 
    790       // Layout this range of bitfields.
    791       if (!LayoutBitfields(Layout, FieldNo, FI, FE)) {
    792         assert(!Packed &&
    793                "Could not layout bitfields even with a packed LLVM struct!");
    794         return false;
    795       }
    796       assert(FI != FE && "Advanced past the last bitfield");
    797       continue;
    798     }
    799 
    800     if (!LayoutField(FD, Layout.getFieldOffset(FieldNo))) {
    801       assert(!Packed &&
    802              "Could not layout fields even with a packed LLVM struct!");
    803       return false;
    804     }
    805   }
    806 
    807   if (RD) {
    808     // We've laid out the non-virtual bases and the fields, now compute the
    809     // non-virtual base field types.
    810     if (!ComputeNonVirtualBaseType(RD)) {
    811       assert(!Packed && "Could not layout even with a packed LLVM struct!");
    812       return false;
    813     }
    814 
    815     // Lay out the virtual bases.  The MS ABI uses a different
    816     // algorithm here due to the lack of primary virtual bases.
    817     if (Types.getContext().getTargetInfo().getCXXABI().hasPrimaryVBases()) {
    818       RD->getIndirectPrimaryBases(IndirectPrimaryBases);
    819       if (Layout.isPrimaryBaseVirtual())
    820         IndirectPrimaryBases.insert(Layout.getPrimaryBase());
    821 
    822       if (!LayoutVirtualBases(RD, Layout))
    823         return false;
    824     } else {
    825       if (!MSLayoutVirtualBases(RD, Layout))
    826         return false;
    827     }
    828   }
    829 
    830   // Append tail padding if necessary.
    831   AppendTailPadding(Layout.getSize());
    832 
    833   return true;
    834 }
    835 
    836 void CGRecordLayoutBuilder::AppendTailPadding(CharUnits RecordSize) {
    837   ResizeLastBaseFieldIfNecessary(RecordSize);
    838 
    839   assert(NextFieldOffset <= RecordSize && "Size mismatch!");
    840 
    841   CharUnits AlignedNextFieldOffset =
    842     NextFieldOffset.RoundUpToAlignment(getAlignmentAsLLVMStruct());
    843 
    844   if (AlignedNextFieldOffset == RecordSize) {
    845     // We don't need any padding.
    846     return;
    847   }
    848 
    849   CharUnits NumPadBytes = RecordSize - NextFieldOffset;
    850   AppendBytes(NumPadBytes);
    851 }
    852 
    853 void CGRecordLayoutBuilder::AppendField(CharUnits fieldOffset,
    854                                         llvm::Type *fieldType) {
    855   CharUnits fieldSize =
    856     CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(fieldType));
    857 
    858   FieldTypes.push_back(fieldType);
    859 
    860   NextFieldOffset = fieldOffset + fieldSize;
    861 }
    862 
    863 void CGRecordLayoutBuilder::AppendPadding(CharUnits fieldOffset,
    864                                           CharUnits fieldAlignment) {
    865   assert(NextFieldOffset <= fieldOffset &&
    866          "Incorrect field layout!");
    867 
    868   // Do nothing if we're already at the right offset.
    869   if (fieldOffset == NextFieldOffset) return;
    870 
    871   // If we're not emitting a packed LLVM type, try to avoid adding
    872   // unnecessary padding fields.
    873   if (!Packed) {
    874     // Round up the field offset to the alignment of the field type.
    875     CharUnits alignedNextFieldOffset =
    876       NextFieldOffset.RoundUpToAlignment(fieldAlignment);
    877     assert(alignedNextFieldOffset <= fieldOffset);
    878 
    879     // If that's the right offset, we're done.
    880     if (alignedNextFieldOffset == fieldOffset) return;
    881   }
    882 
    883   // Otherwise we need explicit padding.
    884   CharUnits padding = fieldOffset - NextFieldOffset;
    885   AppendBytes(padding);
    886 }
    887 
    888 bool CGRecordLayoutBuilder::ResizeLastBaseFieldIfNecessary(CharUnits offset) {
    889   // Check if we have a base to resize.
    890   if (!LastLaidOutBase.isValid())
    891     return false;
    892 
    893   // This offset does not overlap with the tail padding.
    894   if (offset >= NextFieldOffset)
    895     return false;
    896 
    897   // Restore the field offset and append an i8 array instead.
    898   FieldTypes.pop_back();
    899   NextFieldOffset = LastLaidOutBase.Offset;
    900   AppendBytes(LastLaidOutBase.NonVirtualSize);
    901   LastLaidOutBase.invalidate();
    902 
    903   return true;
    904 }
    905 
    906 llvm::Type *CGRecordLayoutBuilder::getByteArrayType(CharUnits numBytes) {
    907   assert(!numBytes.isZero() && "Empty byte arrays aren't allowed.");
    908 
    909   llvm::Type *Ty = llvm::Type::getInt8Ty(Types.getLLVMContext());
    910   if (numBytes > CharUnits::One())
    911     Ty = llvm::ArrayType::get(Ty, numBytes.getQuantity());
    912 
    913   return Ty;
    914 }
    915 
    916 void CGRecordLayoutBuilder::AppendBytes(CharUnits numBytes) {
    917   if (numBytes.isZero())
    918     return;
    919 
    920   // Append the padding field
    921   AppendField(NextFieldOffset, getByteArrayType(numBytes));
    922 }
    923 
    924 CharUnits CGRecordLayoutBuilder::getTypeAlignment(llvm::Type *Ty) const {
    925   if (Packed)
    926     return CharUnits::One();
    927 
    928   return CharUnits::fromQuantity(Types.getDataLayout().getABITypeAlignment(Ty));
    929 }
    930 
    931 CharUnits CGRecordLayoutBuilder::getAlignmentAsLLVMStruct() const {
    932   if (Packed)
    933     return CharUnits::One();
    934 
    935   CharUnits maxAlignment = CharUnits::One();
    936   for (size_t i = 0; i != FieldTypes.size(); ++i)
    937     maxAlignment = std::max(maxAlignment, getTypeAlignment(FieldTypes[i]));
    938 
    939   return maxAlignment;
    940 }
    941 
    942 /// Merge in whether a field of the given type is zero-initializable.
    943 void CGRecordLayoutBuilder::CheckZeroInitializable(QualType T) {
    944   // This record already contains a member pointer.
    945   if (!IsZeroInitializableAsBase)
    946     return;
    947 
    948   // Can only have member pointers if we're compiling C++.
    949   if (!Types.getContext().getLangOpts().CPlusPlus)
    950     return;
    951 
    952   const Type *elementType = T->getBaseElementTypeUnsafe();
    953 
    954   if (const MemberPointerType *MPT = elementType->getAs<MemberPointerType>()) {
    955     if (!Types.getCXXABI().isZeroInitializable(MPT))
    956       IsZeroInitializable = IsZeroInitializableAsBase = false;
    957   } else if (const RecordType *RT = elementType->getAs<RecordType>()) {
    958     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
    959     const CGRecordLayout &Layout = Types.getCGRecordLayout(RD);
    960     if (!Layout.isZeroInitializable())
    961       IsZeroInitializable = IsZeroInitializableAsBase = false;
    962   }
    963 }
    964 
    965 CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D,
    966                                                   llvm::StructType *Ty) {
    967   CGRecordLayoutBuilder Builder(*this);
    968 
    969   Builder.Layout(D);
    970 
    971   Ty->setBody(Builder.FieldTypes, Builder.Packed);
    972 
    973   // If we're in C++, compute the base subobject type.
    974   llvm::StructType *BaseTy = 0;
    975   if (isa<CXXRecordDecl>(D) && !D->isUnion()) {
    976     BaseTy = Builder.BaseSubobjectType;
    977     if (!BaseTy) BaseTy = Ty;
    978   }
    979 
    980   CGRecordLayout *RL =
    981     new CGRecordLayout(Ty, BaseTy, Builder.IsZeroInitializable,
    982                        Builder.IsZeroInitializableAsBase);
    983 
    984   RL->NonVirtualBases.swap(Builder.NonVirtualBases);
    985   RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases);
    986 
    987   // Add all the field numbers.
    988   RL->FieldInfo.swap(Builder.Fields);
    989 
    990   // Add bitfield info.
    991   RL->BitFields.swap(Builder.BitFields);
    992 
    993   // Dump the layout, if requested.
    994   if (getContext().getLangOpts().DumpRecordLayouts) {
    995     llvm::errs() << "\n*** Dumping IRgen Record Layout\n";
    996     llvm::errs() << "Record: ";
    997     D->dump();
    998     llvm::errs() << "\nLayout: ";
    999     RL->dump();
   1000   }
   1001 
   1002 #ifndef NDEBUG
   1003   // Verify that the computed LLVM struct size matches the AST layout size.
   1004   const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D);
   1005 
   1006   uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize());
   1007   assert(TypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(Ty) &&
   1008          "Type size mismatch!");
   1009 
   1010   if (BaseTy) {
   1011     CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
   1012     CharUnits NonVirtualAlign = Layout.getNonVirtualAlign();
   1013     CharUnits AlignedNonVirtualTypeSize =
   1014       NonVirtualSize.RoundUpToAlignment(NonVirtualAlign);
   1015 
   1016     uint64_t AlignedNonVirtualTypeSizeInBits =
   1017       getContext().toBits(AlignedNonVirtualTypeSize);
   1018 
   1019     assert(AlignedNonVirtualTypeSizeInBits ==
   1020            getDataLayout().getTypeAllocSizeInBits(BaseTy) &&
   1021            "Type size mismatch!");
   1022   }
   1023 
   1024   // Verify that the LLVM and AST field offsets agree.
   1025   llvm::StructType *ST =
   1026     dyn_cast<llvm::StructType>(RL->getLLVMType());
   1027   const llvm::StructLayout *SL = getDataLayout().getStructLayout(ST);
   1028 
   1029   const ASTRecordLayout &AST_RL = getContext().getASTRecordLayout(D);
   1030   RecordDecl::field_iterator it = D->field_begin();
   1031   const FieldDecl *LastFD = 0;
   1032   bool IsMsStruct = D->isMsStruct(getContext());
   1033   for (unsigned i = 0, e = AST_RL.getFieldCount(); i != e; ++i, ++it) {
   1034     const FieldDecl *FD = *it;
   1035 
   1036     // For non-bit-fields, just check that the LLVM struct offset matches the
   1037     // AST offset.
   1038     if (!FD->isBitField()) {
   1039       unsigned FieldNo = RL->getLLVMFieldNo(FD);
   1040       assert(AST_RL.getFieldOffset(i) == SL->getElementOffsetInBits(FieldNo) &&
   1041              "Invalid field offset!");
   1042       LastFD = FD;
   1043       continue;
   1044     }
   1045 
   1046     if (IsMsStruct) {
   1047       // Zero-length bitfields following non-bitfield members are
   1048       // ignored:
   1049       if (getContext().ZeroBitfieldFollowsNonBitfield(FD, LastFD)) {
   1050         --i;
   1051         continue;
   1052       }
   1053       LastFD = FD;
   1054     }
   1055 
   1056     // Ignore unnamed bit-fields.
   1057     if (!FD->getDeclName()) {
   1058       LastFD = FD;
   1059       continue;
   1060     }
   1061 
   1062     // Don't inspect zero-length bitfields.
   1063     if (FD->getBitWidthValue(getContext()) == 0)
   1064       continue;
   1065 
   1066     const CGBitFieldInfo &Info = RL->getBitFieldInfo(FD);
   1067     llvm::Type *ElementTy = ST->getTypeAtIndex(RL->getLLVMFieldNo(FD));
   1068 
   1069     // Unions have overlapping elements dictating their layout, but for
   1070     // non-unions we can verify that this section of the layout is the exact
   1071     // expected size.
   1072     if (D->isUnion()) {
   1073       // For unions we verify that the start is zero and the size
   1074       // is in-bounds. However, on BE systems, the offset may be non-zero, but
   1075       // the size + offset should match the storage size in that case as it
   1076       // "starts" at the back.
   1077       if (getDataLayout().isBigEndian())
   1078         assert(static_cast<unsigned>(Info.Offset + Info.Size) ==
   1079                Info.StorageSize &&
   1080                "Big endian union bitfield does not end at the back");
   1081       else
   1082         assert(Info.Offset == 0 &&
   1083                "Little endian union bitfield with a non-zero offset");
   1084       assert(Info.StorageSize <= SL->getSizeInBits() &&
   1085              "Union not large enough for bitfield storage");
   1086     } else {
   1087       assert(Info.StorageSize ==
   1088              getDataLayout().getTypeAllocSizeInBits(ElementTy) &&
   1089              "Storage size does not match the element type size");
   1090     }
   1091     assert(Info.Size > 0 && "Empty bitfield!");
   1092     assert(static_cast<unsigned>(Info.Offset) + Info.Size <= Info.StorageSize &&
   1093            "Bitfield outside of its allocated storage");
   1094   }
   1095 #endif
   1096 
   1097   return RL;
   1098 }
   1099 
   1100 void CGRecordLayout::print(raw_ostream &OS) const {
   1101   OS << "<CGRecordLayout\n";
   1102   OS << "  LLVMType:" << *CompleteObjectType << "\n";
   1103   if (BaseSubobjectType)
   1104     OS << "  NonVirtualBaseLLVMType:" << *BaseSubobjectType << "\n";
   1105   OS << "  IsZeroInitializable:" << IsZeroInitializable << "\n";
   1106   OS << "  BitFields:[\n";
   1107 
   1108   // Print bit-field infos in declaration order.
   1109   std::vector<std::pair<unsigned, const CGBitFieldInfo*> > BFIs;
   1110   for (llvm::DenseMap<const FieldDecl*, CGBitFieldInfo>::const_iterator
   1111          it = BitFields.begin(), ie = BitFields.end();
   1112        it != ie; ++it) {
   1113     const RecordDecl *RD = it->first->getParent();
   1114     unsigned Index = 0;
   1115     for (RecordDecl::field_iterator
   1116            it2 = RD->field_begin(); *it2 != it->first; ++it2)
   1117       ++Index;
   1118     BFIs.push_back(std::make_pair(Index, &it->second));
   1119   }
   1120   llvm::array_pod_sort(BFIs.begin(), BFIs.end());
   1121   for (unsigned i = 0, e = BFIs.size(); i != e; ++i) {
   1122     OS.indent(4);
   1123     BFIs[i].second->print(OS);
   1124     OS << "\n";
   1125   }
   1126 
   1127   OS << "]>\n";
   1128 }
   1129 
   1130 void CGRecordLayout::dump() const {
   1131   print(llvm::errs());
   1132 }
   1133 
   1134 void CGBitFieldInfo::print(raw_ostream &OS) const {
   1135   OS << "<CGBitFieldInfo"
   1136      << " Offset:" << Offset
   1137      << " Size:" << Size
   1138      << " IsSigned:" << IsSigned
   1139      << " StorageSize:" << StorageSize
   1140      << " StorageAlignment:" << StorageAlignment << ">";
   1141 }
   1142 
   1143 void CGBitFieldInfo::dump() const {
   1144   print(llvm::errs());
   1145 }
   1146