contrib/llvm/tools/clang/lib/CodeGen/CGRecordLayoutBuilder.cpp

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