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/Basic/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/MathExtras.h"
  29 #include "llvm/Support/raw_ostream.h"
  30 using namespace clang;
  31 using namespace CodeGen;
  32
  33 namespace {
  34 /// The CGRecordLowering is responsible for lowering an ASTRecordLayout to an
  35 /// llvm::Type.  Some of the lowering is straightforward, some is not.  Here we
  36 /// detail some of the complexities and weirdnesses here.
  37 /// * LLVM does not have unions - Unions can, in theory be represented by any
  38 ///   llvm::Type with correct size.  We choose a field via a specific heuristic
  39 ///   and add padding if necessary.
  40 /// * LLVM does not have bitfields - Bitfields are collected into contiguous
  41 ///   runs and allocated as a single storage type for the run.  ASTRecordLayout
  42 ///   contains enough information to determine where the runs break.  Microsoft
  43 ///   and Itanium follow different rules and use different codepaths.
  44 /// * It is desired that, when possible, bitfields use the appropriate iN type
  45 ///   when lowered to llvm types.  For example unsigned x : 24 gets lowered to
  46 ///   i24.  This isn't always possible because i24 has storage size of 32 bit
  47 ///   and if it is possible to use that extra byte of padding we must use
  48 ///   [i8 x 3] instead of i24.  The function clipTailPadding does this.
  49 ///   C++ examples that require clipping:
  50 ///   struct { int a : 24; char b; }; // a must be clipped, b goes at offset 3
  51 ///   struct A { int a : 24; }; // a must be clipped because a struct like B
  52 //    could exist: struct B : A { char b; }; // b goes at offset 3
  53 /// * Clang ignores 0 sized bitfields and 0 sized bases but *not* zero sized
  54 ///   fields.  The existing asserts suggest that LLVM assumes that *every* field
  55 ///   has an underlying storage type.  Therefore empty structures containing
  56 ///   zero sized subobjects such as empty records or zero sized arrays still get
  57 ///   a zero sized (empty struct) storage type.
  58 /// * Clang reads the complete type rather than the base type when generating
  59 ///   code to access fields.  Bitfields in tail position with tail padding may
  60 ///   be clipped in the base class but not the complete class (we may discover
  61 ///   that the tail padding is not used in the complete class.) However,
  62 ///   because LLVM reads from the complete type it can generate incorrect code
  63 ///   if we do not clip the tail padding off of the bitfield in the complete
  64 ///   layout.  This introduces a somewhat awkward extra unnecessary clip stage.
  65 ///   The location of the clip is stored internally as a sentinel of type
  66 ///   SCISSOR.  If LLVM were updated to read base types (which it probably
  67 ///   should because locations of things such as VBases are bogus in the llvm
  68 ///   type anyway) then we could eliminate the SCISSOR.
  69 /// * Itanium allows nearly empty primary virtual bases.  These bases don't get
  70 ///   get their own storage because they're laid out as part of another base
  71 ///   or at the beginning of the structure.  Determining if a VBase actually
  72 ///   gets storage awkwardly involves a walk of all bases.
  73 /// * VFPtrs and VBPtrs do *not* make a record NotZeroInitializable.
  74 struct CGRecordLowering {
  75   // MemberInfo is a helper structure that contains information about a record
  76   // member.  In additional to the standard member types, there exists a
  77   // sentinel member type that ensures correct rounding.
  78   struct MemberInfo {
  79     CharUnits Offset;
  80     enum InfoKind { VFPtr, VBPtr, Field, Base, VBase, Scissor } Kind;
  81     llvm::Type *Data;
  82     union {
  83       const FieldDecl *FD;
  84       const CXXRecordDecl *RD;
  85     };
  86     MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data,
  87                const FieldDecl *FD = nullptr)
  88       : Offset(Offset), Kind(Kind), Data(Data), FD(FD) {}
  89     MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data,
  90                const CXXRecordDecl *RD)
  91       : Offset(Offset), Kind(Kind), Data(Data), RD(RD) {}
  92     // MemberInfos are sorted so we define a < operator.
  93     bool operator <(const MemberInfo& a) const { return Offset < a.Offset; }
  94   };
  95   // The constructor.
  96   CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed);
  97   // Short helper routines.
  98   /// Constructs a MemberInfo instance from an offset and llvm::Type *.
  99   MemberInfo StorageInfo(CharUnits Offset, llvm::Type *Data) {
 100     return MemberInfo(Offset, MemberInfo::Field, Data);
 101   }
 102
 103   /// The Microsoft bitfield layout rule allocates discrete storage
 104   /// units of the field's formal type and only combines adjacent
 105   /// fields of the same formal type.  We want to emit a layout with
 106   /// these discrete storage units instead of combining them into a
 107   /// continuous run.
 108   bool isDiscreteBitFieldABI() {
 109     return Context.getTargetInfo().getCXXABI().isMicrosoft() ||
 110            D->isMsStruct(Context);
 111   }
 112
 113   /// The Itanium base layout rule allows virtual bases to overlap
 114   /// other bases, which complicates layout in specific ways.
 115   ///
 116   /// Note specifically that the ms_struct attribute doesn't change this.
 117   bool isOverlappingVBaseABI() {
 118     return !Context.getTargetInfo().getCXXABI().isMicrosoft();
 119   }
 120
 121   /// Wraps llvm::Type::getIntNTy with some implicit arguments.
 122   llvm::Type *getIntNType(uint64_t NumBits) {
 123     return llvm::Type::getIntNTy(Types.getLLVMContext(),
 124                                  (unsigned)llvm::alignTo(NumBits, 8));
 125   }
 126   /// Gets an llvm type of size NumBytes and alignment 1.
 127   llvm::Type *getByteArrayType(CharUnits NumBytes) {
 128     assert(!NumBytes.isZero() && "Empty byte arrays aren't allowed.");
 129     llvm::Type *Type = llvm::Type::getInt8Ty(Types.getLLVMContext());
 130     return NumBytes == CharUnits::One() ? Type :
 131         (llvm::Type *)llvm::ArrayType::get(Type, NumBytes.getQuantity());
 132   }
 133   /// Gets the storage type for a field decl and handles storage
 134   /// for itanium bitfields that are smaller than their declared type.
 135   llvm::Type *getStorageType(const FieldDecl *FD) {
 136     llvm::Type *Type = Types.ConvertTypeForMem(FD->getType());
 137     if (!FD->isBitField()) return Type;
 138     if (isDiscreteBitFieldABI()) return Type;
 139     return getIntNType(std::min(FD->getBitWidthValue(Context),
 140                              (unsigned)Context.toBits(getSize(Type))));
 141   }
 142   /// Gets the llvm Basesubobject type from a CXXRecordDecl.
 143   llvm::Type *getStorageType(const CXXRecordDecl *RD) {
 144     return Types.getCGRecordLayout(RD).getBaseSubobjectLLVMType();
 145   }
 146   CharUnits bitsToCharUnits(uint64_t BitOffset) {
 147     return Context.toCharUnitsFromBits(BitOffset);
 148   }
 149   CharUnits getSize(llvm::Type *Type) {
 150     return CharUnits::fromQuantity(DataLayout.getTypeAllocSize(Type));
 151   }
 152   CharUnits getAlignment(llvm::Type *Type) {
 153     return CharUnits::fromQuantity(DataLayout.getABITypeAlignment(Type));
 154   }
 155   bool isZeroInitializable(const FieldDecl *FD) {
 156     return Types.isZeroInitializable(FD->getType());
 157   }
 158   bool isZeroInitializable(const RecordDecl *RD) {
 159     return Types.isZeroInitializable(RD);
 160   }
 161   void appendPaddingBytes(CharUnits Size) {
 162     if (!Size.isZero())
 163       FieldTypes.push_back(getByteArrayType(Size));
 164   }
 165   uint64_t getFieldBitOffset(const FieldDecl *FD) {
 166     return Layout.getFieldOffset(FD->getFieldIndex());
 167   }
 168   // Layout routines.
 169   void setBitFieldInfo(const FieldDecl *FD, CharUnits StartOffset,
 170                        llvm::Type *StorageType);
 171   /// Lowers an ASTRecordLayout to a llvm type.
 172   void lower(bool NonVirtualBaseType);
 173   void lowerUnion();
 174   void accumulateFields();
 175   void accumulateBitFields(RecordDecl::field_iterator Field,
 176                         RecordDecl::field_iterator FieldEnd);
 177   void accumulateBases();
 178   void accumulateVPtrs();
 179   void accumulateVBases();
 180   /// Recursively searches all of the bases to find out if a vbase is
 181   /// not the primary vbase of some base class.
 182   bool hasOwnStorage(const CXXRecordDecl *Decl, const CXXRecordDecl *Query);
 183   void calculateZeroInit();
 184   /// Lowers bitfield storage types to I8 arrays for bitfields with tail
 185   /// padding that is or can potentially be used.
 186   void clipTailPadding();
 187   /// Determines if we need a packed llvm struct.
 188   void determinePacked(bool NVBaseType);
 189   /// Inserts padding everywhere it's needed.
 190   void insertPadding();
 191   /// Fills out the structures that are ultimately consumed.
 192   void fillOutputFields();
 193   // Input memoization fields.
 194   CodeGenTypes &Types;
 195   const ASTContext &Context;
 196   const RecordDecl *D;
 197   const CXXRecordDecl *RD;
 198   const ASTRecordLayout &Layout;
 199   const llvm::DataLayout &DataLayout;
 200   // Helpful intermediate data-structures.
 201   std::vector<MemberInfo> Members;
 202   // Output fields, consumed by CodeGenTypes::ComputeRecordLayout.
 203   SmallVector<llvm::Type *, 16> FieldTypes;
 204   llvm::DenseMap<const FieldDecl *, unsigned> Fields;
 205   llvm::DenseMap<const FieldDecl *, CGBitFieldInfo> BitFields;
 206   llvm::DenseMap<const CXXRecordDecl *, unsigned> NonVirtualBases;
 207   llvm::DenseMap<const CXXRecordDecl *, unsigned> VirtualBases;
 208   bool IsZeroInitializable : 1;
 209   bool IsZeroInitializableAsBase : 1;
 210   bool Packed : 1;
 211 private:
 212   CGRecordLowering(const CGRecordLowering &) = delete;
 213   void operator =(const CGRecordLowering &) = delete;
 214 };
 215 } // namespace {
 216
 217 CGRecordLowering::CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D,
 218                                    bool Packed)
 219     : Types(Types), Context(Types.getContext()), D(D),
 220       RD(dyn_cast<CXXRecordDecl>(D)),
 221       Layout(Types.getContext().getASTRecordLayout(D)),
 222       DataLayout(Types.getDataLayout()), IsZeroInitializable(true),
 223       IsZeroInitializableAsBase(true), Packed(Packed) {}
 224
 225 void CGRecordLowering::setBitFieldInfo(
 226     const FieldDecl *FD, CharUnits StartOffset, llvm::Type *StorageType) {
 227   CGBitFieldInfo &Info = BitFields[FD->getCanonicalDecl()];
 228   Info.IsSigned = FD->getType()->isSignedIntegerOrEnumerationType();
 229   Info.Offset = (unsigned)(getFieldBitOffset(FD) - Context.toBits(StartOffset));
 230   Info.Size = FD->getBitWidthValue(Context);
 231   Info.StorageSize = (unsigned)DataLayout.getTypeAllocSizeInBits(StorageType);
 232   Info.StorageOffset = StartOffset;
 233   if (Info.Size > Info.StorageSize)
 234     Info.Size = Info.StorageSize;
 235   // Reverse the bit offsets for big endian machines. Because we represent
 236   // a bitfield as a single large integer load, we can imagine the bits
 237   // counting from the most-significant-bit instead of the
 238   // least-significant-bit.
 239   if (DataLayout.isBigEndian())
 240     Info.Offset = Info.StorageSize - (Info.Offset + Info.Size);
 241 }
 242
 243 void CGRecordLowering::lower(bool NVBaseType) {
 244   // The lowering process implemented in this function takes a variety of
 245   // carefully ordered phases.
 246   // 1) Store all members (fields and bases) in a list and sort them by offset.
 247   // 2) Add a 1-byte capstone member at the Size of the structure.
 248   // 3) Clip bitfield storages members if their tail padding is or might be
 249   //    used by another field or base.  The clipping process uses the capstone
 250   //    by treating it as another object that occurs after the record.
 251   // 4) Determine if the llvm-struct requires packing.  It's important that this
 252   //    phase occur after clipping, because clipping changes the llvm type.
 253   //    This phase reads the offset of the capstone when determining packedness
 254   //    and updates the alignment of the capstone to be equal of the alignment
 255   //    of the record after doing so.
 256   // 5) Insert padding everywhere it is needed.  This phase requires 'Packed' to
 257   //    have been computed and needs to know the alignment of the record in
 258   //    order to understand if explicit tail padding is needed.
 259   // 6) Remove the capstone, we don't need it anymore.
 260   // 7) Determine if this record can be zero-initialized.  This phase could have
 261   //    been placed anywhere after phase 1.
 262   // 8) Format the complete list of members in a way that can be consumed by
 263   //    CodeGenTypes::ComputeRecordLayout.
 264   CharUnits Size = NVBaseType ? Layout.getNonVirtualSize() : Layout.getSize();
 265   if (D->isUnion())
 266     return lowerUnion();
 267   accumulateFields();
 268   // RD implies C++.
 269   if (RD) {
 270     accumulateVPtrs();
 271     accumulateBases();
 272     if (Members.empty())
 273       return appendPaddingBytes(Size);
 274     if (!NVBaseType)
 275       accumulateVBases();
 276   }
 277   std::stable_sort(Members.begin(), Members.end());
 278   Members.push_back(StorageInfo(Size, getIntNType(8)));
 279   clipTailPadding();
 280   determinePacked(NVBaseType);
 281   insertPadding();
 282   Members.pop_back();
 283   calculateZeroInit();
 284   fillOutputFields();
 285 }
 286
 287 void CGRecordLowering::lowerUnion() {
 288   CharUnits LayoutSize = Layout.getSize();
 289   llvm::Type *StorageType = nullptr;
 290   bool SeenNamedMember = false;
 291   // Iterate through the fields setting bitFieldInfo and the Fields array. Also
 292   // locate the "most appropriate" storage type.  The heuristic for finding the
 293   // storage type isn't necessary, the first (non-0-length-bitfield) field's
 294   // type would work fine and be simpler but would be different than what we've
 295   // been doing and cause lit tests to change.
 296   for (const auto *Field : D->fields()) {
 297     if (Field->isBitField()) {
 298       if (Field->isZeroLengthBitField(Context))
 299         continue;
 300       llvm::Type *FieldType = getStorageType(Field);
 301       if (LayoutSize < getSize(FieldType))
 302         FieldType = getByteArrayType(LayoutSize);
 303       setBitFieldInfo(Field, CharUnits::Zero(), FieldType);
 304     }
 305     Fields[Field->getCanonicalDecl()] = 0;
 306     llvm::Type *FieldType = getStorageType(Field);
 307     // Compute zero-initializable status.
 308     // This union might not be zero initialized: it may contain a pointer to
 309     // data member which might have some exotic initialization sequence.
 310     // If this is the case, then we aught not to try and come up with a "better"
 311     // type, it might not be very easy to come up with a Constant which
 312     // correctly initializes it.
 313     if (!SeenNamedMember) {
 314       SeenNamedMember = Field->getIdentifier();
 315       if (!SeenNamedMember)
 316         if (const auto *FieldRD = Field->getType()->getAsRecordDecl())
 317           SeenNamedMember = FieldRD->findFirstNamedDataMember();
 318       if (SeenNamedMember && !isZeroInitializable(Field)) {
 319         IsZeroInitializable = IsZeroInitializableAsBase = false;
 320         StorageType = FieldType;
 321       }
 322     }
 323     // Because our union isn't zero initializable, we won't be getting a better
 324     // storage type.
 325     if (!IsZeroInitializable)
 326       continue;
 327     // Conditionally update our storage type if we've got a new "better" one.
 328     if (!StorageType ||
 329         getAlignment(FieldType) >  getAlignment(StorageType) ||
 330         (getAlignment(FieldType) == getAlignment(StorageType) &&
 331         getSize(FieldType) > getSize(StorageType)))
 332       StorageType = FieldType;
 333   }
 334   // If we have no storage type just pad to the appropriate size and return.
 335   if (!StorageType)
 336     return appendPaddingBytes(LayoutSize);
 337   // If our storage size was bigger than our required size (can happen in the
 338   // case of packed bitfields on Itanium) then just use an I8 array.
 339   if (LayoutSize < getSize(StorageType))
 340     StorageType = getByteArrayType(LayoutSize);
 341   FieldTypes.push_back(StorageType);
 342   appendPaddingBytes(LayoutSize - getSize(StorageType));
 343   // Set packed if we need it.
 344   if (LayoutSize % getAlignment(StorageType))
 345     Packed = true;
 346 }
 347
 348 void CGRecordLowering::accumulateFields() {
 349   for (RecordDecl::field_iterator Field = D->field_begin(),
 350                                   FieldEnd = D->field_end();
 351     Field != FieldEnd;)
 352     if (Field->isBitField()) {
 353       RecordDecl::field_iterator Start = Field;
 354       // Iterate to gather the list of bitfields.
 355       for (++Field; Field != FieldEnd && Field->isBitField(); ++Field);
 356       accumulateBitFields(Start, Field);
 357     } else {
 358       Members.push_back(MemberInfo(
 359           bitsToCharUnits(getFieldBitOffset(*Field)), MemberInfo::Field,
 360           getStorageType(*Field), *Field));
 361       ++Field;
 362     }
 363 }
 364
 365 void
 366 CGRecordLowering::accumulateBitFields(RecordDecl::field_iterator Field,
 367                                       RecordDecl::field_iterator FieldEnd) {
 368   // Run stores the first element of the current run of bitfields.  FieldEnd is
 369   // used as a special value to note that we don't have a current run.  A
 370   // bitfield run is a contiguous collection of bitfields that can be stored in
 371   // the same storage block.  Zero-sized bitfields and bitfields that would
 372   // cross an alignment boundary break a run and start a new one.
 373   RecordDecl::field_iterator Run = FieldEnd;
 374   // Tail is the offset of the first bit off the end of the current run.  It's
 375   // used to determine if the ASTRecordLayout is treating these two bitfields as
 376   // contiguous.  StartBitOffset is offset of the beginning of the Run.
 377   uint64_t StartBitOffset, Tail = 0;
 378   if (isDiscreteBitFieldABI()) {
 379     for (; Field != FieldEnd; ++Field) {
 380       uint64_t BitOffset = getFieldBitOffset(*Field);
 381       // Zero-width bitfields end runs.
 382       if (Field->isZeroLengthBitField(Context)) {
 383         Run = FieldEnd;
 384         continue;
 385       }
 386       llvm::Type *Type = Types.ConvertTypeForMem(Field->getType());
 387       // If we don't have a run yet, or don't live within the previous run's
 388       // allocated storage then we allocate some storage and start a new run.
 389       if (Run == FieldEnd || BitOffset >= Tail) {
 390         Run = Field;
 391         StartBitOffset = BitOffset;
 392         Tail = StartBitOffset + DataLayout.getTypeAllocSizeInBits(Type);
 393         // Add the storage member to the record.  This must be added to the
 394         // record before the bitfield members so that it gets laid out before
 395         // the bitfields it contains get laid out.
 396         Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type));
 397       }
 398       // Bitfields get the offset of their storage but come afterward and remain
 399       // there after a stable sort.
 400       Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset),
 401                                    MemberInfo::Field, nullptr, *Field));
 402     }
 403     return;
 404   }
 405
 406   // Check if OffsetInRecord is better as a single field run. When OffsetInRecord
 407   // has legal integer width, and its bitfield offset is naturally aligned, it
 408   // is better to make the bitfield a separate storage component so as it can be
 409   // accessed directly with lower cost.
 410   auto IsBetterAsSingleFieldRun = [&](uint64_t OffsetInRecord,
 411                                       uint64_t StartBitOffset) {
 412     if (!Types.getCodeGenOpts().FineGrainedBitfieldAccesses)
 413       return false;
 414     if (!DataLayout.isLegalInteger(OffsetInRecord))
 415       return false;
 416     // Make sure StartBitOffset is natually aligned if it is treated as an
 417     // IType integer.
 418      if (StartBitOffset %
 419             Context.toBits(getAlignment(getIntNType(OffsetInRecord))) !=
 420         0)
 421       return false;
 422     return true;
 423   };
 424
 425   // The start field is better as a single field run.
 426   bool StartFieldAsSingleRun = false;
 427   for (;;) {
 428     // Check to see if we need to start a new run.
 429     if (Run == FieldEnd) {
 430       // If we're out of fields, return.
 431       if (Field == FieldEnd)
 432         break;
 433       // Any non-zero-length bitfield can start a new run.
 434       if (!Field->isZeroLengthBitField(Context)) {
 435         Run = Field;
 436         StartBitOffset = getFieldBitOffset(*Field);
 437         Tail = StartBitOffset + Field->getBitWidthValue(Context);
 438         StartFieldAsSingleRun = IsBetterAsSingleFieldRun(Tail - StartBitOffset,
 439                                                          StartBitOffset);
 440       }
 441       ++Field;
 442       continue;
 443     }
 444
 445     // If the start field of a new run is better as a single run, or
 446     // if current field (or consecutive fields) is better as a single run, or
 447     // if current field has zero width bitfield and either
 448     // UseZeroLengthBitfieldAlignment or UseBitFieldTypeAlignment is set to
 449     // true, or
 450     // if the offset of current field is inconsistent with the offset of
 451     // previous field plus its offset,
 452     // skip the block below and go ahead to emit the storage.
 453     // Otherwise, try to add bitfields to the run.
 454     if (!StartFieldAsSingleRun && Field != FieldEnd &&
 455         !IsBetterAsSingleFieldRun(Tail - StartBitOffset, StartBitOffset) &&
 456         (!Field->isZeroLengthBitField(Context) ||
 457          (!Context.getTargetInfo().useZeroLengthBitfieldAlignment() &&
 458           !Context.getTargetInfo().useBitFieldTypeAlignment())) &&
 459         Tail == getFieldBitOffset(*Field)) {
 460       Tail += Field->getBitWidthValue(Context);
 461       ++Field;
 462       continue;
 463     }
 464
 465     // We've hit a break-point in the run and need to emit a storage field.
 466     llvm::Type *Type = getIntNType(Tail - StartBitOffset);
 467     // Add the storage member to the record and set the bitfield info for all of
 468     // the bitfields in the run.  Bitfields get the offset of their storage but
 469     // come afterward and remain there after a stable sort.
 470     Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type));
 471     for (; Run != Field; ++Run)
 472       Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset),
 473                                    MemberInfo::Field, nullptr, *Run));
 474     Run = FieldEnd;
 475     StartFieldAsSingleRun = false;
 476   }
 477 }
 478
 479 void CGRecordLowering::accumulateBases() {
 480   // If we've got a primary virtual base, we need to add it with the bases.
 481   if (Layout.isPrimaryBaseVirtual()) {
 482     const CXXRecordDecl *BaseDecl = Layout.getPrimaryBase();
 483     Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::Base,
 484                                  getStorageType(BaseDecl), BaseDecl));
 485   }
 486   // Accumulate the non-virtual bases.
 487   for (const auto &Base : RD->bases()) {
 488     if (Base.isVirtual())
 489       continue;
 490
 491     // Bases can be zero-sized even if not technically empty if they
 492     // contain only a trailing array member.
 493     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 494     if (!BaseDecl->isEmpty() &&
 495         !Context.getASTRecordLayout(BaseDecl).getNonVirtualSize().isZero())
 496       Members.push_back(MemberInfo(Layout.getBaseClassOffset(BaseDecl),
 497           MemberInfo::Base, getStorageType(BaseDecl), BaseDecl));
 498   }
 499 }
 500
 501 void CGRecordLowering::accumulateVPtrs() {
 502   if (Layout.hasOwnVFPtr())
 503     Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::VFPtr,
 504         llvm::FunctionType::get(getIntNType(32), /*isVarArg=*/true)->
 505             getPointerTo()->getPointerTo()));
 506   if (Layout.hasOwnVBPtr())
 507     Members.push_back(MemberInfo(Layout.getVBPtrOffset(), MemberInfo::VBPtr,
 508         llvm::Type::getInt32PtrTy(Types.getLLVMContext())));
 509 }
 510
 511 void CGRecordLowering::accumulateVBases() {
 512   CharUnits ScissorOffset = Layout.getNonVirtualSize();
 513   // In the itanium ABI, it's possible to place a vbase at a dsize that is
 514   // smaller than the nvsize.  Here we check to see if such a base is placed
 515   // before the nvsize and set the scissor offset to that, instead of the
 516   // nvsize.
 517   if (isOverlappingVBaseABI())
 518     for (const auto &Base : RD->vbases()) {
 519       const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 520       if (BaseDecl->isEmpty())
 521         continue;
 522       // If the vbase is a primary virtual base of some base, then it doesn't
 523       // get its own storage location but instead lives inside of that base.
 524       if (Context.isNearlyEmpty(BaseDecl) && !hasOwnStorage(RD, BaseDecl))
 525         continue;
 526       ScissorOffset = std::min(ScissorOffset,
 527                                Layout.getVBaseClassOffset(BaseDecl));
 528     }
 529   Members.push_back(MemberInfo(ScissorOffset, MemberInfo::Scissor, nullptr,
 530                                RD));
 531   for (const auto &Base : RD->vbases()) {
 532     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 533     if (BaseDecl->isEmpty())
 534       continue;
 535     CharUnits Offset = Layout.getVBaseClassOffset(BaseDecl);
 536     // If the vbase is a primary virtual base of some base, then it doesn't
 537     // get its own storage location but instead lives inside of that base.
 538     if (isOverlappingVBaseABI() &&
 539         Context.isNearlyEmpty(BaseDecl) &&
 540         !hasOwnStorage(RD, BaseDecl)) {
 541       Members.push_back(MemberInfo(Offset, MemberInfo::VBase, nullptr,
 542                                    BaseDecl));
 543       continue;
 544     }
 545     // If we've got a vtordisp, add it as a storage type.
 546     if (Layout.getVBaseOffsetsMap().find(BaseDecl)->second.hasVtorDisp())
 547       Members.push_back(StorageInfo(Offset - CharUnits::fromQuantity(4),
 548                                     getIntNType(32)));
 549     Members.push_back(MemberInfo(Offset, MemberInfo::VBase,
 550                                  getStorageType(BaseDecl), BaseDecl));
 551   }
 552 }
 553
 554 bool CGRecordLowering::hasOwnStorage(const CXXRecordDecl *Decl,
 555                                      const CXXRecordDecl *Query) {
 556   const ASTRecordLayout &DeclLayout = Context.getASTRecordLayout(Decl);
 557   if (DeclLayout.isPrimaryBaseVirtual() && DeclLayout.getPrimaryBase() == Query)
 558     return false;
 559   for (const auto &Base : Decl->bases())
 560     if (!hasOwnStorage(Base.getType()->getAsCXXRecordDecl(), Query))
 561       return false;
 562   return true;
 563 }
 564
 565 void CGRecordLowering::calculateZeroInit() {
 566   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
 567                                                MemberEnd = Members.end();
 568        IsZeroInitializableAsBase && Member != MemberEnd; ++Member) {
 569     if (Member->Kind == MemberInfo::Field) {
 570       if (!Member->FD || isZeroInitializable(Member->FD))
 571         continue;
 572       IsZeroInitializable = IsZeroInitializableAsBase = false;
 573     } else if (Member->Kind == MemberInfo::Base ||
 574                Member->Kind == MemberInfo::VBase) {
 575       if (isZeroInitializable(Member->RD))
 576         continue;
 577       IsZeroInitializable = false;
 578       if (Member->Kind == MemberInfo::Base)
 579         IsZeroInitializableAsBase = false;
 580     }
 581   }
 582 }
 583
 584 void CGRecordLowering::clipTailPadding() {
 585   std::vector<MemberInfo>::iterator Prior = Members.begin();
 586   CharUnits Tail = getSize(Prior->Data);
 587   for (std::vector<MemberInfo>::iterator Member = Prior + 1,
 588                                          MemberEnd = Members.end();
 589        Member != MemberEnd; ++Member) {
 590     // Only members with data and the scissor can cut into tail padding.
 591     if (!Member->Data && Member->Kind != MemberInfo::Scissor)
 592       continue;
 593     if (Member->Offset < Tail) {
 594       assert(Prior->Kind == MemberInfo::Field && !Prior->FD &&
 595              "Only storage fields have tail padding!");
 596       Prior->Data = getByteArrayType(bitsToCharUnits(llvm::alignTo(
 597           cast<llvm::IntegerType>(Prior->Data)->getIntegerBitWidth(), 8)));
 598     }
 599     if (Member->Data)
 600       Prior = Member;
 601     Tail = Prior->Offset + getSize(Prior->Data);
 602   }
 603 }
 604
 605 void CGRecordLowering::determinePacked(bool NVBaseType) {
 606   if (Packed)
 607     return;
 608   CharUnits Alignment = CharUnits::One();
 609   CharUnits NVAlignment = CharUnits::One();
 610   CharUnits NVSize =
 611       !NVBaseType && RD ? Layout.getNonVirtualSize() : CharUnits::Zero();
 612   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
 613                                                MemberEnd = Members.end();
 614        Member != MemberEnd; ++Member) {
 615     if (!Member->Data)
 616       continue;
 617     // If any member falls at an offset that it not a multiple of its alignment,
 618     // then the entire record must be packed.
 619     if (Member->Offset % getAlignment(Member->Data))
 620       Packed = true;
 621     if (Member->Offset < NVSize)
 622       NVAlignment = std::max(NVAlignment, getAlignment(Member->Data));
 623     Alignment = std::max(Alignment, getAlignment(Member->Data));
 624   }
 625   // If the size of the record (the capstone's offset) is not a multiple of the
 626   // record's alignment, it must be packed.
 627   if (Members.back().Offset % Alignment)
 628     Packed = true;
 629   // If the non-virtual sub-object is not a multiple of the non-virtual
 630   // sub-object's alignment, it must be packed.  We cannot have a packed
 631   // non-virtual sub-object and an unpacked complete object or vise versa.
 632   if (NVSize % NVAlignment)
 633     Packed = true;
 634   // Update the alignment of the sentinel.
 635   if (!Packed)
 636     Members.back().Data = getIntNType(Context.toBits(Alignment));
 637 }
 638
 639 void CGRecordLowering::insertPadding() {
 640   std::vector<std::pair<CharUnits, CharUnits> > Padding;
 641   CharUnits Size = CharUnits::Zero();
 642   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
 643                                                MemberEnd = Members.end();
 644        Member != MemberEnd; ++Member) {
 645     if (!Member->Data)
 646       continue;
 647     CharUnits Offset = Member->Offset;
 648     assert(Offset >= Size);
 649     // Insert padding if we need to.
 650     if (Offset !=
 651         Size.alignTo(Packed ? CharUnits::One() : getAlignment(Member->Data)))
 652       Padding.push_back(std::make_pair(Size, Offset - Size));
 653     Size = Offset + getSize(Member->Data);
 654   }
 655   if (Padding.empty())
 656     return;
 657   // Add the padding to the Members list and sort it.
 658   for (std::vector<std::pair<CharUnits, CharUnits> >::const_iterator
 659         Pad = Padding.begin(), PadEnd = Padding.end();
 660         Pad != PadEnd; ++Pad)
 661     Members.push_back(StorageInfo(Pad->first, getByteArrayType(Pad->second)));
 662   std::stable_sort(Members.begin(), Members.end());
 663 }
 664
 665 void CGRecordLowering::fillOutputFields() {
 666   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
 667                                                MemberEnd = Members.end();
 668        Member != MemberEnd; ++Member) {
 669     if (Member->Data)
 670       FieldTypes.push_back(Member->Data);
 671     if (Member->Kind == MemberInfo::Field) {
 672       if (Member->FD)
 673         Fields[Member->FD->getCanonicalDecl()] = FieldTypes.size() - 1;
 674       // A field without storage must be a bitfield.
 675       if (!Member->Data)
 676         setBitFieldInfo(Member->FD, Member->Offset, FieldTypes.back());
 677     } else if (Member->Kind == MemberInfo::Base)
 678       NonVirtualBases[Member->RD] = FieldTypes.size() - 1;
 679     else if (Member->Kind == MemberInfo::VBase)
 680       VirtualBases[Member->RD] = FieldTypes.size() - 1;
 681   }
 682 }
 683
 684 CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
 685                                         const FieldDecl *FD,
 686                                         uint64_t Offset, uint64_t Size,
 687                                         uint64_t StorageSize,
 688                                         CharUnits StorageOffset) {
 689   // This function is vestigial from CGRecordLayoutBuilder days but is still
 690   // used in GCObjCRuntime.cpp.  That usage has a "fixme" attached to it that
 691   // when addressed will allow for the removal of this function.
 692   llvm::Type *Ty = Types.ConvertTypeForMem(FD->getType());
 693   CharUnits TypeSizeInBytes =
 694     CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(Ty));
 695   uint64_t TypeSizeInBits = Types.getContext().toBits(TypeSizeInBytes);
 696
 697   bool IsSigned = FD->getType()->isSignedIntegerOrEnumerationType();
 698
 699   if (Size > TypeSizeInBits) {
 700     // We have a wide bit-field. The extra bits are only used for padding, so
 701     // if we have a bitfield of type T, with size N:
 702     //
 703     // T t : N;
 704     //
 705     // We can just assume that it's:
 706     //
 707     // T t : sizeof(T);
 708     //
 709     Size = TypeSizeInBits;
 710   }
 711
 712   // Reverse the bit offsets for big endian machines. Because we represent
 713   // a bitfield as a single large integer load, we can imagine the bits
 714   // counting from the most-significant-bit instead of the
 715   // least-significant-bit.
 716   if (Types.getDataLayout().isBigEndian()) {
 717     Offset = StorageSize - (Offset + Size);
 718   }
 719
 720   return CGBitFieldInfo(Offset, Size, IsSigned, StorageSize, StorageOffset);
 721 }
 722
 723 CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D,
 724                                                   llvm::StructType *Ty) {
 725   CGRecordLowering Builder(*this, D, /*Packed=*/false);
 726
 727   Builder.lower(/*NonVirtualBaseType=*/false);
 728
 729   // If we're in C++, compute the base subobject type.
 730   llvm::StructType *BaseTy = nullptr;
 731   if (isa<CXXRecordDecl>(D) && !D->isUnion() && !D->hasAttr<FinalAttr>()) {
 732     BaseTy = Ty;
 733     if (Builder.Layout.getNonVirtualSize() != Builder.Layout.getSize()) {
 734       CGRecordLowering BaseBuilder(*this, D, /*Packed=*/Builder.Packed);
 735       BaseBuilder.lower(/*NonVirtualBaseType=*/true);
 736       BaseTy = llvm::StructType::create(
 737           getLLVMContext(), BaseBuilder.FieldTypes, "", BaseBuilder.Packed);
 738       addRecordTypeName(D, BaseTy, ".base");
 739       // BaseTy and Ty must agree on their packedness for getLLVMFieldNo to work
 740       // on both of them with the same index.
 741       assert(Builder.Packed == BaseBuilder.Packed &&
 742              "Non-virtual and complete types must agree on packedness");
 743     }
 744   }
 745
 746   // Fill in the struct *after* computing the base type.  Filling in the body
 747   // signifies that the type is no longer opaque and record layout is complete,
 748   // but we may need to recursively layout D while laying D out as a base type.
 749   Ty->setBody(Builder.FieldTypes, Builder.Packed);
 750
 751   CGRecordLayout *RL =
 752     new CGRecordLayout(Ty, BaseTy, Builder.IsZeroInitializable,
 753                         Builder.IsZeroInitializableAsBase);
 754
 755   RL->NonVirtualBases.swap(Builder.NonVirtualBases);
 756   RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases);
 757
 758   // Add all the field numbers.
 759   RL->FieldInfo.swap(Builder.Fields);
 760
 761   // Add bitfield info.
 762   RL->BitFields.swap(Builder.BitFields);
 763
 764   // Dump the layout, if requested.
 765   if (getContext().getLangOpts().DumpRecordLayouts) {
 766     llvm::outs() << "\n*** Dumping IRgen Record Layout\n";
 767     llvm::outs() << "Record: ";
 768     D->dump(llvm::outs());
 769     llvm::outs() << "\nLayout: ";
 770     RL->print(llvm::outs());
 771   }
 772
 773 #ifndef NDEBUG
 774   // Verify that the computed LLVM struct size matches the AST layout size.
 775   const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D);
 776
 777   uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize());
 778   assert(TypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(Ty) &&
 779          "Type size mismatch!");
 780
 781   if (BaseTy) {
 782     CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
 783
 784     uint64_t AlignedNonVirtualTypeSizeInBits =
 785       getContext().toBits(NonVirtualSize);
 786
 787     assert(AlignedNonVirtualTypeSizeInBits ==
 788            getDataLayout().getTypeAllocSizeInBits(BaseTy) &&
 789            "Type size mismatch!");
 790   }
 791
 792   // Verify that the LLVM and AST field offsets agree.
 793   llvm::StructType *ST = RL->getLLVMType();
 794   const llvm::StructLayout *SL = getDataLayout().getStructLayout(ST);
 795
 796   const ASTRecordLayout &AST_RL = getContext().getASTRecordLayout(D);
 797   RecordDecl::field_iterator it = D->field_begin();
 798   for (unsigned i = 0, e = AST_RL.getFieldCount(); i != e; ++i, ++it) {
 799     const FieldDecl *FD = *it;
 800
 801     // For non-bit-fields, just check that the LLVM struct offset matches the
 802     // AST offset.
 803     if (!FD->isBitField()) {
 804       unsigned FieldNo = RL->getLLVMFieldNo(FD);
 805       assert(AST_RL.getFieldOffset(i) == SL->getElementOffsetInBits(FieldNo) &&
 806              "Invalid field offset!");
 807       continue;
 808     }
 809
 810     // Ignore unnamed bit-fields.
 811     if (!FD->getDeclName())
 812       continue;
 813
 814     // Don't inspect zero-length bitfields.
 815     if (FD->isZeroLengthBitField(getContext()))
 816       continue;
 817
 818     const CGBitFieldInfo &Info = RL->getBitFieldInfo(FD);
 819     llvm::Type *ElementTy = ST->getTypeAtIndex(RL->getLLVMFieldNo(FD));
 820
 821     // Unions have overlapping elements dictating their layout, but for
 822     // non-unions we can verify that this section of the layout is the exact
 823     // expected size.
 824     if (D->isUnion()) {
 825       // For unions we verify that the start is zero and the size
 826       // is in-bounds. However, on BE systems, the offset may be non-zero, but
 827       // the size + offset should match the storage size in that case as it
 828       // "starts" at the back.
 829       if (getDataLayout().isBigEndian())
 830         assert(static_cast<unsigned>(Info.Offset + Info.Size) ==
 831                Info.StorageSize &&
 832                "Big endian union bitfield does not end at the back");
 833       else
 834         assert(Info.Offset == 0 &&
 835                "Little endian union bitfield with a non-zero offset");
 836       assert(Info.StorageSize <= SL->getSizeInBits() &&
 837              "Union not large enough for bitfield storage");
 838     } else {
 839       assert(Info.StorageSize ==
 840              getDataLayout().getTypeAllocSizeInBits(ElementTy) &&
 841              "Storage size does not match the element type size");
 842     }
 843     assert(Info.Size > 0 && "Empty bitfield!");
 844     assert(static_cast<unsigned>(Info.Offset) + Info.Size <= Info.StorageSize &&
 845            "Bitfield outside of its allocated storage");
 846   }
 847 #endif
 848
 849   return RL;
 850 }
 851
 852 void CGRecordLayout::print(raw_ostream &OS) const {
 853   OS << "<CGRecordLayout\n";
 854   OS << "  LLVMType:" << *CompleteObjectType << "\n";
 855   if (BaseSubobjectType)
 856     OS << "  NonVirtualBaseLLVMType:" << *BaseSubobjectType << "\n";
 857   OS << "  IsZeroInitializable:" << IsZeroInitializable << "\n";
 858   OS << "  BitFields:[\n";
 859
 860   // Print bit-field infos in declaration order.
 861   std::vector<std::pair<unsigned, const CGBitFieldInfo*> > BFIs;
 862   for (llvm::DenseMap<const FieldDecl*, CGBitFieldInfo>::const_iterator
 863          it = BitFields.begin(), ie = BitFields.end();
 864        it != ie; ++it) {
 865     const RecordDecl *RD = it->first->getParent();
 866     unsigned Index = 0;
 867     for (RecordDecl::field_iterator
 868            it2 = RD->field_begin(); *it2 != it->first; ++it2)
 869       ++Index;
 870     BFIs.push_back(std::make_pair(Index, &it->second));
 871   }
 872   llvm::array_pod_sort(BFIs.begin(), BFIs.end());
 873   for (unsigned i = 0, e = BFIs.size(); i != e; ++i) {
 874     OS.indent(4);
 875     BFIs[i].second->print(OS);
 876     OS << "\n";
 877   }
 878
 879   OS << "]>\n";
 880 }
 881
 882 LLVM_DUMP_METHOD void CGRecordLayout::dump() const {
 883   print(llvm::errs());
 884 }
 885
 886 void CGBitFieldInfo::print(raw_ostream &OS) const {
 887   OS << "<CGBitFieldInfo"
 888      << " Offset:" << Offset
 889      << " Size:" << Size
 890      << " IsSigned:" << IsSigned
 891      << " StorageSize:" << StorageSize
 892      << " StorageOffset:" << StorageOffset.getQuantity() << ">";
 893 }
 894
 895 LLVM_DUMP_METHOD void CGBitFieldInfo::dump() const {
 896   print(llvm::errs());
 897 }