contrib/llvm/tools/clang/lib/AST/RecordLayoutBuilder.cpp

   1 //=== RecordLayoutBuilder.cpp - Helper class for building record layouts ---==//
   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 #include "clang/AST/RecordLayout.h"
  11 #include "clang/AST/ASTContext.h"
  12 #include "clang/AST/Attr.h"
  13 #include "clang/AST/CXXInheritance.h"
  14 #include "clang/AST/Decl.h"
  15 #include "clang/AST/DeclCXX.h"
  16 #include "clang/AST/DeclObjC.h"
  17 #include "clang/AST/Expr.h"
  18 #include "clang/Basic/TargetInfo.h"
  19 #include "clang/Sema/SemaDiagnostic.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/Support/CrashRecoveryContext.h"
  22 #include "llvm/Support/Format.h"
  23 #include "llvm/Support/MathExtras.h"
  24
  25 using namespace clang;
  26
  27 namespace {
  28
  29 /// BaseSubobjectInfo - Represents a single base subobject in a complete class.
  30 /// For a class hierarchy like
  31 ///
  32 /// class A { };
  33 /// class B : A { };
  34 /// class C : A, B { };
  35 ///
  36 /// The BaseSubobjectInfo graph for C will have three BaseSubobjectInfo
  37 /// instances, one for B and two for A.
  38 ///
  39 /// If a base is virtual, it will only have one BaseSubobjectInfo allocated.
  40 struct BaseSubobjectInfo {
  41   /// Class - The class for this base info.
  42   const CXXRecordDecl *Class;
  43
  44   /// IsVirtual - Whether the BaseInfo represents a virtual base or not.
  45   bool IsVirtual;
  46
  47   /// Bases - Information about the base subobjects.
  48   SmallVector<BaseSubobjectInfo*, 4> Bases;
  49
  50   /// PrimaryVirtualBaseInfo - Holds the base info for the primary virtual base
  51   /// of this base info (if one exists).
  52   BaseSubobjectInfo *PrimaryVirtualBaseInfo;
  53
  54   // FIXME: Document.
  55   const BaseSubobjectInfo *Derived;
  56 };
  57
  58 /// \brief Externally provided layout. Typically used when the AST source, such
  59 /// as DWARF, lacks all the information that was available at compile time, such
  60 /// as alignment attributes on fields and pragmas in effect.
  61 struct ExternalLayout {
  62   ExternalLayout() : Size(0), Align(0) {}
  63
  64   /// \brief Overall record size in bits.
  65   uint64_t Size;
  66
  67   /// \brief Overall record alignment in bits.
  68   uint64_t Align;
  69
  70   /// \brief Record field offsets in bits.
  71   llvm::DenseMap<const FieldDecl *, uint64_t> FieldOffsets;
  72
  73   /// \brief Direct, non-virtual base offsets.
  74   llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsets;
  75
  76   /// \brief Virtual base offsets.
  77   llvm::DenseMap<const CXXRecordDecl *, CharUnits> VirtualBaseOffsets;
  78
  79   /// Get the offset of the given field. The external source must provide
  80   /// entries for all fields in the record.
  81   uint64_t getExternalFieldOffset(const FieldDecl *FD) {
  82     assert(FieldOffsets.count(FD) &&
  83            "Field does not have an external offset");
  84     return FieldOffsets[FD];
  85   }
  86
  87   bool getExternalNVBaseOffset(const CXXRecordDecl *RD, CharUnits &BaseOffset) {
  88     auto Known = BaseOffsets.find(RD);
  89     if (Known == BaseOffsets.end())
  90       return false;
  91     BaseOffset = Known->second;
  92     return true;
  93   }
  94
  95   bool getExternalVBaseOffset(const CXXRecordDecl *RD, CharUnits &BaseOffset) {
  96     auto Known = VirtualBaseOffsets.find(RD);
  97     if (Known == VirtualBaseOffsets.end())
  98       return false;
  99     BaseOffset = Known->second;
 100     return true;
 101   }
 102 };
 103
 104 /// EmptySubobjectMap - Keeps track of which empty subobjects exist at different
 105 /// offsets while laying out a C++ class.
 106 class EmptySubobjectMap {
 107   const ASTContext &Context;
 108   uint64_t CharWidth;
 109
 110   /// Class - The class whose empty entries we're keeping track of.
 111   const CXXRecordDecl *Class;
 112
 113   /// EmptyClassOffsets - A map from offsets to empty record decls.
 114   typedef llvm::TinyPtrVector<const CXXRecordDecl *> ClassVectorTy;
 115   typedef llvm::DenseMap<CharUnits, ClassVectorTy> EmptyClassOffsetsMapTy;
 116   EmptyClassOffsetsMapTy EmptyClassOffsets;
 117
 118   /// MaxEmptyClassOffset - The highest offset known to contain an empty
 119   /// base subobject.
 120   CharUnits MaxEmptyClassOffset;
 121
 122   /// ComputeEmptySubobjectSizes - Compute the size of the largest base or
 123   /// member subobject that is empty.
 124   void ComputeEmptySubobjectSizes();
 125
 126   void AddSubobjectAtOffset(const CXXRecordDecl *RD, CharUnits Offset);
 127
 128   void UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
 129                                  CharUnits Offset, bool PlacingEmptyBase);
 130
 131   void UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD,
 132                                   const CXXRecordDecl *Class,
 133                                   CharUnits Offset);
 134   void UpdateEmptyFieldSubobjects(const FieldDecl *FD, CharUnits Offset);
 135
 136   /// AnyEmptySubobjectsBeyondOffset - Returns whether there are any empty
 137   /// subobjects beyond the given offset.
 138   bool AnyEmptySubobjectsBeyondOffset(CharUnits Offset) const {
 139     return Offset <= MaxEmptyClassOffset;
 140   }
 141
 142   CharUnits
 143   getFieldOffset(const ASTRecordLayout &Layout, unsigned FieldNo) const {
 144     uint64_t FieldOffset = Layout.getFieldOffset(FieldNo);
 145     assert(FieldOffset % CharWidth == 0 &&
 146            "Field offset not at char boundary!");
 147
 148     return Context.toCharUnitsFromBits(FieldOffset);
 149   }
 150
 151 protected:
 152   bool CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
 153                                  CharUnits Offset) const;
 154
 155   bool CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
 156                                      CharUnits Offset);
 157
 158   bool CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
 159                                       const CXXRecordDecl *Class,
 160                                       CharUnits Offset) const;
 161   bool CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
 162                                       CharUnits Offset) const;
 163
 164 public:
 165   /// This holds the size of the largest empty subobject (either a base
 166   /// or a member). Will be zero if the record being built doesn't contain
 167   /// any empty classes.
 168   CharUnits SizeOfLargestEmptySubobject;
 169
 170   EmptySubobjectMap(const ASTContext &Context, const CXXRecordDecl *Class)
 171   : Context(Context), CharWidth(Context.getCharWidth()), Class(Class) {
 172       ComputeEmptySubobjectSizes();
 173   }
 174
 175   /// CanPlaceBaseAtOffset - Return whether the given base class can be placed
 176   /// at the given offset.
 177   /// Returns false if placing the record will result in two components
 178   /// (direct or indirect) of the same type having the same offset.
 179   bool CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
 180                             CharUnits Offset);
 181
 182   /// CanPlaceFieldAtOffset - Return whether a field can be placed at the given
 183   /// offset.
 184   bool CanPlaceFieldAtOffset(const FieldDecl *FD, CharUnits Offset);
 185 };
 186
 187 void EmptySubobjectMap::ComputeEmptySubobjectSizes() {
 188   // Check the bases.
 189   for (const CXXBaseSpecifier &Base : Class->bases()) {
 190     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 191
 192     CharUnits EmptySize;
 193     const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
 194     if (BaseDecl->isEmpty()) {
 195       // If the class decl is empty, get its size.
 196       EmptySize = Layout.getSize();
 197     } else {
 198       // Otherwise, we get the largest empty subobject for the decl.
 199       EmptySize = Layout.getSizeOfLargestEmptySubobject();
 200     }
 201
 202     if (EmptySize > SizeOfLargestEmptySubobject)
 203       SizeOfLargestEmptySubobject = EmptySize;
 204   }
 205
 206   // Check the fields.
 207   for (const FieldDecl *FD : Class->fields()) {
 208     const RecordType *RT =
 209         Context.getBaseElementType(FD->getType())->getAs<RecordType>();
 210
 211     // We only care about record types.
 212     if (!RT)
 213       continue;
 214
 215     CharUnits EmptySize;
 216     const CXXRecordDecl *MemberDecl = RT->getAsCXXRecordDecl();
 217     const ASTRecordLayout &Layout = Context.getASTRecordLayout(MemberDecl);
 218     if (MemberDecl->isEmpty()) {
 219       // If the class decl is empty, get its size.
 220       EmptySize = Layout.getSize();
 221     } else {
 222       // Otherwise, we get the largest empty subobject for the decl.
 223       EmptySize = Layout.getSizeOfLargestEmptySubobject();
 224     }
 225
 226     if (EmptySize > SizeOfLargestEmptySubobject)
 227       SizeOfLargestEmptySubobject = EmptySize;
 228   }
 229 }
 230
 231 bool
 232 EmptySubobjectMap::CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
 233                                              CharUnits Offset) const {
 234   // We only need to check empty bases.
 235   if (!RD->isEmpty())
 236     return true;
 237
 238   EmptyClassOffsetsMapTy::const_iterator I = EmptyClassOffsets.find(Offset);
 239   if (I == EmptyClassOffsets.end())
 240     return true;
 241
 242   const ClassVectorTy &Classes = I->second;
 243   if (std::find(Classes.begin(), Classes.end(), RD) == Classes.end())
 244     return true;
 245
 246   // There is already an empty class of the same type at this offset.
 247   return false;
 248 }
 249
 250 void EmptySubobjectMap::AddSubobjectAtOffset(const CXXRecordDecl *RD,
 251                                              CharUnits Offset) {
 252   // We only care about empty bases.
 253   if (!RD->isEmpty())
 254     return;
 255
 256   // If we have empty structures inside a union, we can assign both
 257   // the same offset. Just avoid pushing them twice in the list.
 258   ClassVectorTy &Classes = EmptyClassOffsets[Offset];
 259   if (std::find(Classes.begin(), Classes.end(), RD) != Classes.end())
 260     return;
 261
 262   Classes.push_back(RD);
 263
 264   // Update the empty class offset.
 265   if (Offset > MaxEmptyClassOffset)
 266     MaxEmptyClassOffset = Offset;
 267 }
 268
 269 bool
 270 EmptySubobjectMap::CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
 271                                                  CharUnits Offset) {
 272   // We don't have to keep looking past the maximum offset that's known to
 273   // contain an empty class.
 274   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 275     return true;
 276
 277   if (!CanPlaceSubobjectAtOffset(Info->Class, Offset))
 278     return false;
 279
 280   // Traverse all non-virtual bases.
 281   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
 282   for (const BaseSubobjectInfo *Base : Info->Bases) {
 283     if (Base->IsVirtual)
 284       continue;
 285
 286     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
 287
 288     if (!CanPlaceBaseSubobjectAtOffset(Base, BaseOffset))
 289       return false;
 290   }
 291
 292   if (Info->PrimaryVirtualBaseInfo) {
 293     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
 294
 295     if (Info == PrimaryVirtualBaseInfo->Derived) {
 296       if (!CanPlaceBaseSubobjectAtOffset(PrimaryVirtualBaseInfo, Offset))
 297         return false;
 298     }
 299   }
 300
 301   // Traverse all member variables.
 302   unsigned FieldNo = 0;
 303   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
 304        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
 305     if (I->isBitField())
 306       continue;
 307
 308     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 309     if (!CanPlaceFieldSubobjectAtOffset(*I, FieldOffset))
 310       return false;
 311   }
 312
 313   return true;
 314 }
 315
 316 void EmptySubobjectMap::UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
 317                                                   CharUnits Offset,
 318                                                   bool PlacingEmptyBase) {
 319   if (!PlacingEmptyBase && Offset >= SizeOfLargestEmptySubobject) {
 320     // We know that the only empty subobjects that can conflict with empty
 321     // subobject of non-empty bases, are empty bases that can be placed at
 322     // offset zero. Because of this, we only need to keep track of empty base
 323     // subobjects with offsets less than the size of the largest empty
 324     // subobject for our class.
 325     return;
 326   }
 327
 328   AddSubobjectAtOffset(Info->Class, Offset);
 329
 330   // Traverse all non-virtual bases.
 331   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
 332   for (const BaseSubobjectInfo *Base : Info->Bases) {
 333     if (Base->IsVirtual)
 334       continue;
 335
 336     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
 337     UpdateEmptyBaseSubobjects(Base, BaseOffset, PlacingEmptyBase);
 338   }
 339
 340   if (Info->PrimaryVirtualBaseInfo) {
 341     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
 342
 343     if (Info == PrimaryVirtualBaseInfo->Derived)
 344       UpdateEmptyBaseSubobjects(PrimaryVirtualBaseInfo, Offset,
 345                                 PlacingEmptyBase);
 346   }
 347
 348   // Traverse all member variables.
 349   unsigned FieldNo = 0;
 350   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
 351        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
 352     if (I->isBitField())
 353       continue;
 354
 355     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 356     UpdateEmptyFieldSubobjects(*I, FieldOffset);
 357   }
 358 }
 359
 360 bool EmptySubobjectMap::CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
 361                                              CharUnits Offset) {
 362   // If we know this class doesn't have any empty subobjects we don't need to
 363   // bother checking.
 364   if (SizeOfLargestEmptySubobject.isZero())
 365     return true;
 366
 367   if (!CanPlaceBaseSubobjectAtOffset(Info, Offset))
 368     return false;
 369
 370   // We are able to place the base at this offset. Make sure to update the
 371   // empty base subobject map.
 372   UpdateEmptyBaseSubobjects(Info, Offset, Info->Class->isEmpty());
 373   return true;
 374 }
 375
 376 bool
 377 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
 378                                                   const CXXRecordDecl *Class,
 379                                                   CharUnits Offset) const {
 380   // We don't have to keep looking past the maximum offset that's known to
 381   // contain an empty class.
 382   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 383     return true;
 384
 385   if (!CanPlaceSubobjectAtOffset(RD, Offset))
 386     return false;
 387
 388   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 389
 390   // Traverse all non-virtual bases.
 391   for (const CXXBaseSpecifier &Base : RD->bases()) {
 392     if (Base.isVirtual())
 393       continue;
 394
 395     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 396
 397     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
 398     if (!CanPlaceFieldSubobjectAtOffset(BaseDecl, Class, BaseOffset))
 399       return false;
 400   }
 401
 402   if (RD == Class) {
 403     // This is the most derived class, traverse virtual bases as well.
 404     for (const CXXBaseSpecifier &Base : RD->vbases()) {
 405       const CXXRecordDecl *VBaseDecl = Base.getType()->getAsCXXRecordDecl();
 406
 407       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
 408       if (!CanPlaceFieldSubobjectAtOffset(VBaseDecl, Class, VBaseOffset))
 409         return false;
 410     }
 411   }
 412
 413   // Traverse all member variables.
 414   unsigned FieldNo = 0;
 415   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 416        I != E; ++I, ++FieldNo) {
 417     if (I->isBitField())
 418       continue;
 419
 420     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 421
 422     if (!CanPlaceFieldSubobjectAtOffset(*I, FieldOffset))
 423       return false;
 424   }
 425
 426   return true;
 427 }
 428
 429 bool
 430 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
 431                                                   CharUnits Offset) const {
 432   // We don't have to keep looking past the maximum offset that's known to
 433   // contain an empty class.
 434   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 435     return true;
 436
 437   QualType T = FD->getType();
 438   if (const CXXRecordDecl *RD = T->getAsCXXRecordDecl())
 439     return CanPlaceFieldSubobjectAtOffset(RD, RD, Offset);
 440
 441   // If we have an array type we need to look at every element.
 442   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
 443     QualType ElemTy = Context.getBaseElementType(AT);
 444     const RecordType *RT = ElemTy->getAs<RecordType>();
 445     if (!RT)
 446       return true;
 447
 448     const CXXRecordDecl *RD = RT->getAsCXXRecordDecl();
 449     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 450
 451     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
 452     CharUnits ElementOffset = Offset;
 453     for (uint64_t I = 0; I != NumElements; ++I) {
 454       // We don't have to keep looking past the maximum offset that's known to
 455       // contain an empty class.
 456       if (!AnyEmptySubobjectsBeyondOffset(ElementOffset))
 457         return true;
 458
 459       if (!CanPlaceFieldSubobjectAtOffset(RD, RD, ElementOffset))
 460         return false;
 461
 462       ElementOffset += Layout.getSize();
 463     }
 464   }
 465
 466   return true;
 467 }
 468
 469 bool
 470 EmptySubobjectMap::CanPlaceFieldAtOffset(const FieldDecl *FD,
 471                                          CharUnits Offset) {
 472   if (!CanPlaceFieldSubobjectAtOffset(FD, Offset))
 473     return false;
 474
 475   // We are able to place the member variable at this offset.
 476   // Make sure to update the empty base subobject map.
 477   UpdateEmptyFieldSubobjects(FD, Offset);
 478   return true;
 479 }
 480
 481 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD,
 482                                                    const CXXRecordDecl *Class,
 483                                                    CharUnits Offset) {
 484   // We know that the only empty subobjects that can conflict with empty
 485   // field subobjects are subobjects of empty bases that can be placed at offset
 486   // zero. Because of this, we only need to keep track of empty field
 487   // subobjects with offsets less than the size of the largest empty
 488   // subobject for our class.
 489   if (Offset >= SizeOfLargestEmptySubobject)
 490     return;
 491
 492   AddSubobjectAtOffset(RD, Offset);
 493
 494   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 495
 496   // Traverse all non-virtual bases.
 497   for (const CXXBaseSpecifier &Base : RD->bases()) {
 498     if (Base.isVirtual())
 499       continue;
 500
 501     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
 502
 503     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
 504     UpdateEmptyFieldSubobjects(BaseDecl, Class, BaseOffset);
 505   }
 506
 507   if (RD == Class) {
 508     // This is the most derived class, traverse virtual bases as well.
 509     for (const CXXBaseSpecifier &Base : RD->vbases()) {
 510       const CXXRecordDecl *VBaseDecl = Base.getType()->getAsCXXRecordDecl();
 511
 512       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
 513       UpdateEmptyFieldSubobjects(VBaseDecl, Class, VBaseOffset);
 514     }
 515   }
 516
 517   // Traverse all member variables.
 518   unsigned FieldNo = 0;
 519   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 520        I != E; ++I, ++FieldNo) {
 521     if (I->isBitField())
 522       continue;
 523
 524     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 525
 526     UpdateEmptyFieldSubobjects(*I, FieldOffset);
 527   }
 528 }
 529
 530 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const FieldDecl *FD,
 531                                                    CharUnits Offset) {
 532   QualType T = FD->getType();
 533   if (const CXXRecordDecl *RD = T->getAsCXXRecordDecl()) {
 534     UpdateEmptyFieldSubobjects(RD, RD, Offset);
 535     return;
 536   }
 537
 538   // If we have an array type we need to update every element.
 539   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
 540     QualType ElemTy = Context.getBaseElementType(AT);
 541     const RecordType *RT = ElemTy->getAs<RecordType>();
 542     if (!RT)
 543       return;
 544
 545     const CXXRecordDecl *RD = RT->getAsCXXRecordDecl();
 546     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 547
 548     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
 549     CharUnits ElementOffset = Offset;
 550
 551     for (uint64_t I = 0; I != NumElements; ++I) {
 552       // We know that the only empty subobjects that can conflict with empty
 553       // field subobjects are subobjects of empty bases that can be placed at
 554       // offset zero. Because of this, we only need to keep track of empty field
 555       // subobjects with offsets less than the size of the largest empty
 556       // subobject for our class.
 557       if (ElementOffset >= SizeOfLargestEmptySubobject)
 558         return;
 559
 560       UpdateEmptyFieldSubobjects(RD, RD, ElementOffset);
 561       ElementOffset += Layout.getSize();
 562     }
 563   }
 564 }
 565
 566 typedef llvm::SmallPtrSet<const CXXRecordDecl*, 4> ClassSetTy;
 567
 568 class RecordLayoutBuilder {
 569 protected:
 570   // FIXME: Remove this and make the appropriate fields public.
 571   friend class clang::ASTContext;
 572
 573   const ASTContext &Context;
 574
 575   EmptySubobjectMap *EmptySubobjects;
 576
 577   /// Size - The current size of the record layout.
 578   uint64_t Size;
 579
 580   /// Alignment - The current alignment of the record layout.
 581   CharUnits Alignment;
 582
 583   /// \brief The alignment if attribute packed is not used.
 584   CharUnits UnpackedAlignment;
 585
 586   SmallVector<uint64_t, 16> FieldOffsets;
 587
 588   /// \brief Whether the external AST source has provided a layout for this
 589   /// record.
 590   unsigned UseExternalLayout : 1;
 591
 592   /// \brief Whether we need to infer alignment, even when we have an
 593   /// externally-provided layout.
 594   unsigned InferAlignment : 1;
 595
 596   /// Packed - Whether the record is packed or not.
 597   unsigned Packed : 1;
 598
 599   unsigned IsUnion : 1;
 600
 601   unsigned IsMac68kAlign : 1;
 602
 603   unsigned IsMsStruct : 1;
 604
 605   /// UnfilledBitsInLastUnit - If the last field laid out was a bitfield,
 606   /// this contains the number of bits in the last unit that can be used for
 607   /// an adjacent bitfield if necessary.  The unit in question is usually
 608   /// a byte, but larger units are used if IsMsStruct.
 609   unsigned char UnfilledBitsInLastUnit;
 610   /// LastBitfieldTypeSize - If IsMsStruct, represents the size of the type
 611   /// of the previous field if it was a bitfield.
 612   unsigned char LastBitfieldTypeSize;
 613
 614   /// MaxFieldAlignment - The maximum allowed field alignment. This is set by
 615   /// #pragma pack.
 616   CharUnits MaxFieldAlignment;
 617
 618   /// DataSize - The data size of the record being laid out.
 619   uint64_t DataSize;
 620
 621   CharUnits NonVirtualSize;
 622   CharUnits NonVirtualAlignment;
 623
 624   /// PrimaryBase - the primary base class (if one exists) of the class
 625   /// we're laying out.
 626   const CXXRecordDecl *PrimaryBase;
 627
 628   /// PrimaryBaseIsVirtual - Whether the primary base of the class we're laying
 629   /// out is virtual.
 630   bool PrimaryBaseIsVirtual;
 631
 632   /// HasOwnVFPtr - Whether the class provides its own vtable/vftbl
 633   /// pointer, as opposed to inheriting one from a primary base class.
 634   bool HasOwnVFPtr;
 635
 636   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsetsMapTy;
 637
 638   /// Bases - base classes and their offsets in the record.
 639   BaseOffsetsMapTy Bases;
 640
 641   // VBases - virtual base classes and their offsets in the record.
 642   ASTRecordLayout::VBaseOffsetsMapTy VBases;
 643
 644   /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
 645   /// primary base classes for some other direct or indirect base class.
 646   CXXIndirectPrimaryBaseSet IndirectPrimaryBases;
 647
 648   /// FirstNearlyEmptyVBase - The first nearly empty virtual base class in
 649   /// inheritance graph order. Used for determining the primary base class.
 650   const CXXRecordDecl *FirstNearlyEmptyVBase;
 651
 652   /// VisitedVirtualBases - A set of all the visited virtual bases, used to
 653   /// avoid visiting virtual bases more than once.
 654   llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
 655
 656   /// Valid if UseExternalLayout is true.
 657   ExternalLayout External;
 658
 659   RecordLayoutBuilder(const ASTContext &Context,
 660                       EmptySubobjectMap *EmptySubobjects)
 661     : Context(Context), EmptySubobjects(EmptySubobjects), Size(0),
 662       Alignment(CharUnits::One()), UnpackedAlignment(CharUnits::One()),
 663       UseExternalLayout(false), InferAlignment(false),
 664       Packed(false), IsUnion(false), IsMac68kAlign(false), IsMsStruct(false),
 665       UnfilledBitsInLastUnit(0), LastBitfieldTypeSize(0),
 666       MaxFieldAlignment(CharUnits::Zero()),
 667       DataSize(0), NonVirtualSize(CharUnits::Zero()),
 668       NonVirtualAlignment(CharUnits::One()),
 669       PrimaryBase(nullptr), PrimaryBaseIsVirtual(false),
 670       HasOwnVFPtr(false),
 671       FirstNearlyEmptyVBase(nullptr) {}
 672
 673   void Layout(const RecordDecl *D);
 674   void Layout(const CXXRecordDecl *D);
 675   void Layout(const ObjCInterfaceDecl *D);
 676
 677   void LayoutFields(const RecordDecl *D);
 678   void LayoutField(const FieldDecl *D, bool InsertExtraPadding);
 679   void LayoutWideBitField(uint64_t FieldSize, uint64_t TypeSize,
 680                           bool FieldPacked, const FieldDecl *D);
 681   void LayoutBitField(const FieldDecl *D);
 682
 683   TargetCXXABI getCXXABI() const {
 684     return Context.getTargetInfo().getCXXABI();
 685   }
 686
 687   /// BaseSubobjectInfoAllocator - Allocator for BaseSubobjectInfo objects.
 688   llvm::SpecificBumpPtrAllocator<BaseSubobjectInfo> BaseSubobjectInfoAllocator;
 689
 690   typedef llvm::DenseMap<const CXXRecordDecl *, BaseSubobjectInfo *>
 691     BaseSubobjectInfoMapTy;
 692
 693   /// VirtualBaseInfo - Map from all the (direct or indirect) virtual bases
 694   /// of the class we're laying out to their base subobject info.
 695   BaseSubobjectInfoMapTy VirtualBaseInfo;
 696
 697   /// NonVirtualBaseInfo - Map from all the direct non-virtual bases of the
 698   /// class we're laying out to their base subobject info.
 699   BaseSubobjectInfoMapTy NonVirtualBaseInfo;
 700
 701   /// ComputeBaseSubobjectInfo - Compute the base subobject information for the
 702   /// bases of the given class.
 703   void ComputeBaseSubobjectInfo(const CXXRecordDecl *RD);
 704
 705   /// ComputeBaseSubobjectInfo - Compute the base subobject information for a
 706   /// single class and all of its base classes.
 707   BaseSubobjectInfo *ComputeBaseSubobjectInfo(const CXXRecordDecl *RD,
 708                                               bool IsVirtual,
 709                                               BaseSubobjectInfo *Derived);
 710
 711   /// DeterminePrimaryBase - Determine the primary base of the given class.
 712   void DeterminePrimaryBase(const CXXRecordDecl *RD);
 713
 714   void SelectPrimaryVBase(const CXXRecordDecl *RD);
 715
 716   void EnsureVTablePointerAlignment(CharUnits UnpackedBaseAlign);
 717
 718   /// LayoutNonVirtualBases - Determines the primary base class (if any) and
 719   /// lays it out. Will then proceed to lay out all non-virtual base clasess.
 720   void LayoutNonVirtualBases(const CXXRecordDecl *RD);
 721
 722   /// LayoutNonVirtualBase - Lays out a single non-virtual base.
 723   void LayoutNonVirtualBase(const BaseSubobjectInfo *Base);
 724
 725   void AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info,
 726                                     CharUnits Offset);
 727
 728   /// LayoutVirtualBases - Lays out all the virtual bases.
 729   void LayoutVirtualBases(const CXXRecordDecl *RD,
 730                           const CXXRecordDecl *MostDerivedClass);
 731
 732   /// LayoutVirtualBase - Lays out a single virtual base.
 733   void LayoutVirtualBase(const BaseSubobjectInfo *Base);
 734
 735   /// LayoutBase - Will lay out a base and return the offset where it was
 736   /// placed, in chars.
 737   CharUnits LayoutBase(const BaseSubobjectInfo *Base);
 738
 739   /// InitializeLayout - Initialize record layout for the given record decl.
 740   void InitializeLayout(const Decl *D);
 741
 742   /// FinishLayout - Finalize record layout. Adjust record size based on the
 743   /// alignment.
 744   void FinishLayout(const NamedDecl *D);
 745
 746   void UpdateAlignment(CharUnits NewAlignment, CharUnits UnpackedNewAlignment);
 747   void UpdateAlignment(CharUnits NewAlignment) {
 748     UpdateAlignment(NewAlignment, NewAlignment);
 749   }
 750
 751   /// \brief Retrieve the externally-supplied field offset for the given
 752   /// field.
 753   ///
 754   /// \param Field The field whose offset is being queried.
 755   /// \param ComputedOffset The offset that we've computed for this field.
 756   uint64_t updateExternalFieldOffset(const FieldDecl *Field,
 757                                      uint64_t ComputedOffset);
 758
 759   void CheckFieldPadding(uint64_t Offset, uint64_t UnpaddedOffset,
 760                           uint64_t UnpackedOffset, unsigned UnpackedAlign,
 761                           bool isPacked, const FieldDecl *D);
 762
 763   DiagnosticBuilder Diag(SourceLocation Loc, unsigned DiagID);
 764
 765   CharUnits getSize() const {
 766     assert(Size % Context.getCharWidth() == 0);
 767     return Context.toCharUnitsFromBits(Size);
 768   }
 769   uint64_t getSizeInBits() const { return Size; }
 770
 771   void setSize(CharUnits NewSize) { Size = Context.toBits(NewSize); }
 772   void setSize(uint64_t NewSize) { Size = NewSize; }
 773
 774   CharUnits getAligment() const { return Alignment; }
 775
 776   CharUnits getDataSize() const {
 777     assert(DataSize % Context.getCharWidth() == 0);
 778     return Context.toCharUnitsFromBits(DataSize);
 779   }
 780   uint64_t getDataSizeInBits() const { return DataSize; }
 781
 782   void setDataSize(CharUnits NewSize) { DataSize = Context.toBits(NewSize); }
 783   void setDataSize(uint64_t NewSize) { DataSize = NewSize; }
 784
 785   RecordLayoutBuilder(const RecordLayoutBuilder &) = delete;
 786   void operator=(const RecordLayoutBuilder &) = delete;
 787 };
 788 } // end anonymous namespace
 789
 790 void
 791 RecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) {
 792   for (const auto &I : RD->bases()) {
 793     assert(!I.getType()->isDependentType() &&
 794            "Cannot layout class with dependent bases.");
 795
 796     const CXXRecordDecl *Base = I.getType()->getAsCXXRecordDecl();
 797
 798     // Check if this is a nearly empty virtual base.
 799     if (I.isVirtual() && Context.isNearlyEmpty(Base)) {
 800       // If it's not an indirect primary base, then we've found our primary
 801       // base.
 802       if (!IndirectPrimaryBases.count(Base)) {
 803         PrimaryBase = Base;
 804         PrimaryBaseIsVirtual = true;
 805         return;
 806       }
 807
 808       // Is this the first nearly empty virtual base?
 809       if (!FirstNearlyEmptyVBase)
 810         FirstNearlyEmptyVBase = Base;
 811     }
 812
 813     SelectPrimaryVBase(Base);
 814     if (PrimaryBase)
 815       return;
 816   }
 817 }
 818
 819 /// DeterminePrimaryBase - Determine the primary base of the given class.
 820 void RecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) {
 821   // If the class isn't dynamic, it won't have a primary base.
 822   if (!RD->isDynamicClass())
 823     return;
 824
 825   // Compute all the primary virtual bases for all of our direct and
 826   // indirect bases, and record all their primary virtual base classes.
 827   RD->getIndirectPrimaryBases(IndirectPrimaryBases);
 828
 829   // If the record has a dynamic base class, attempt to choose a primary base
 830   // class. It is the first (in direct base class order) non-virtual dynamic
 831   // base class, if one exists.
 832   for (const auto &I : RD->bases()) {
 833     // Ignore virtual bases.
 834     if (I.isVirtual())
 835       continue;
 836
 837     const CXXRecordDecl *Base = I.getType()->getAsCXXRecordDecl();
 838
 839     if (Base->isDynamicClass()) {
 840       // We found it.
 841       PrimaryBase = Base;
 842       PrimaryBaseIsVirtual = false;
 843       return;
 844     }
 845   }
 846
 847   // Under the Itanium ABI, if there is no non-virtual primary base class,
 848   // try to compute the primary virtual base.  The primary virtual base is
 849   // the first nearly empty virtual base that is not an indirect primary
 850   // virtual base class, if one exists.
 851   if (RD->getNumVBases() != 0) {
 852     SelectPrimaryVBase(RD);
 853     if (PrimaryBase)
 854       return;
 855   }
 856
 857   // Otherwise, it is the first indirect primary base class, if one exists.
 858   if (FirstNearlyEmptyVBase) {
 859     PrimaryBase = FirstNearlyEmptyVBase;
 860     PrimaryBaseIsVirtual = true;
 861     return;
 862   }
 863
 864   assert(!PrimaryBase && "Should not get here with a primary base!");
 865 }
 866
 867 BaseSubobjectInfo *
 868 RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD,
 869                                               bool IsVirtual,
 870                                               BaseSubobjectInfo *Derived) {
 871   BaseSubobjectInfo *Info;
 872
 873   if (IsVirtual) {
 874     // Check if we already have info about this virtual base.
 875     BaseSubobjectInfo *&InfoSlot = VirtualBaseInfo[RD];
 876     if (InfoSlot) {
 877       assert(InfoSlot->Class == RD && "Wrong class for virtual base info!");
 878       return InfoSlot;
 879     }
 880
 881     // We don't, create it.
 882     InfoSlot = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
 883     Info = InfoSlot;
 884   } else {
 885     Info = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
 886   }
 887
 888   Info->Class = RD;
 889   Info->IsVirtual = IsVirtual;
 890   Info->Derived = nullptr;
 891   Info->PrimaryVirtualBaseInfo = nullptr;
 892
 893   const CXXRecordDecl *PrimaryVirtualBase = nullptr;
 894   BaseSubobjectInfo *PrimaryVirtualBaseInfo = nullptr;
 895
 896   // Check if this base has a primary virtual base.
 897   if (RD->getNumVBases()) {
 898     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 899     if (Layout.isPrimaryBaseVirtual()) {
 900       // This base does have a primary virtual base.
 901       PrimaryVirtualBase = Layout.getPrimaryBase();
 902       assert(PrimaryVirtualBase && "Didn't have a primary virtual base!");
 903
 904       // Now check if we have base subobject info about this primary base.
 905       PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
 906
 907       if (PrimaryVirtualBaseInfo) {
 908         if (PrimaryVirtualBaseInfo->Derived) {
 909           // We did have info about this primary base, and it turns out that it
 910           // has already been claimed as a primary virtual base for another
 911           // base.
 912           PrimaryVirtualBase = nullptr;
 913         } else {
 914           // We can claim this base as our primary base.
 915           Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
 916           PrimaryVirtualBaseInfo->Derived = Info;
 917         }
 918       }
 919     }
 920   }
 921
 922   // Now go through all direct bases.
 923   for (const auto &I : RD->bases()) {
 924     bool IsVirtual = I.isVirtual();
 925
 926     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
 927
 928     Info->Bases.push_back(ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, Info));
 929   }
 930
 931   if (PrimaryVirtualBase && !PrimaryVirtualBaseInfo) {
 932     // Traversing the bases must have created the base info for our primary
 933     // virtual base.
 934     PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
 935     assert(PrimaryVirtualBaseInfo &&
 936            "Did not create a primary virtual base!");
 937
 938     // Claim the primary virtual base as our primary virtual base.
 939     Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
 940     PrimaryVirtualBaseInfo->Derived = Info;
 941   }
 942
 943   return Info;
 944 }
 945
 946 void RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD) {
 947   for (const auto &I : RD->bases()) {
 948     bool IsVirtual = I.isVirtual();
 949
 950     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
 951
 952     // Compute the base subobject info for this base.
 953     BaseSubobjectInfo *Info = ComputeBaseSubobjectInfo(BaseDecl, IsVirtual,
 954                                                        nullptr);
 955
 956     if (IsVirtual) {
 957       // ComputeBaseInfo has already added this base for us.
 958       assert(VirtualBaseInfo.count(BaseDecl) &&
 959              "Did not add virtual base!");
 960     } else {
 961       // Add the base info to the map of non-virtual bases.
 962       assert(!NonVirtualBaseInfo.count(BaseDecl) &&
 963              "Non-virtual base already exists!");
 964       NonVirtualBaseInfo.insert(std::make_pair(BaseDecl, Info));
 965     }
 966   }
 967 }
 968
 969 void
 970 RecordLayoutBuilder::EnsureVTablePointerAlignment(CharUnits UnpackedBaseAlign) {
 971   CharUnits BaseAlign = (Packed) ? CharUnits::One() : UnpackedBaseAlign;
 972
 973   // The maximum field alignment overrides base align.
 974   if (!MaxFieldAlignment.isZero()) {
 975     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
 976     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
 977   }
 978
 979   // Round up the current record size to pointer alignment.
 980   setSize(getSize().RoundUpToAlignment(BaseAlign));
 981   setDataSize(getSize());
 982
 983   // Update the alignment.
 984   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
 985 }
 986
 987 void
 988 RecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
 989   // Then, determine the primary base class.
 990   DeterminePrimaryBase(RD);
 991
 992   // Compute base subobject info.
 993   ComputeBaseSubobjectInfo(RD);
 994
 995   // If we have a primary base class, lay it out.
 996   if (PrimaryBase) {
 997     if (PrimaryBaseIsVirtual) {
 998       // If the primary virtual base was a primary virtual base of some other
 999       // base class we'll have to steal it.
1000       BaseSubobjectInfo *PrimaryBaseInfo = VirtualBaseInfo.lookup(PrimaryBase);
1001       PrimaryBaseInfo->Derived = nullptr;
1002
1003       // We have a virtual primary base, insert it as an indirect primary base.
1004       IndirectPrimaryBases.insert(PrimaryBase);
1005
1006       assert(!VisitedVirtualBases.count(PrimaryBase) &&
1007              "vbase already visited!");
1008       VisitedVirtualBases.insert(PrimaryBase);
1009
1010       LayoutVirtualBase(PrimaryBaseInfo);
1011     } else {
1012       BaseSubobjectInfo *PrimaryBaseInfo =
1013         NonVirtualBaseInfo.lookup(PrimaryBase);
1014       assert(PrimaryBaseInfo &&
1015              "Did not find base info for non-virtual primary base!");
1016
1017       LayoutNonVirtualBase(PrimaryBaseInfo);
1018     }
1019
1020   // If this class needs a vtable/vf-table and didn't get one from a
1021   // primary base, add it in now.
1022   } else if (RD->isDynamicClass()) {
1023     assert(DataSize == 0 && "Vtable pointer must be at offset zero!");
1024     CharUnits PtrWidth =
1025       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
1026     CharUnits PtrAlign =
1027       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(0));
1028     EnsureVTablePointerAlignment(PtrAlign);
1029     HasOwnVFPtr = true;
1030     setSize(getSize() + PtrWidth);
1031     setDataSize(getSize());
1032   }
1033
1034   // Now lay out the non-virtual bases.
1035   for (const auto &I : RD->bases()) {
1036
1037     // Ignore virtual bases.
1038     if (I.isVirtual())
1039       continue;
1040
1041     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
1042
1043     // Skip the primary base, because we've already laid it out.  The
1044     // !PrimaryBaseIsVirtual check is required because we might have a
1045     // non-virtual base of the same type as a primary virtual base.
1046     if (BaseDecl == PrimaryBase && !PrimaryBaseIsVirtual)
1047       continue;
1048
1049     // Lay out the base.
1050     BaseSubobjectInfo *BaseInfo = NonVirtualBaseInfo.lookup(BaseDecl);
1051     assert(BaseInfo && "Did not find base info for non-virtual base!");
1052
1053     LayoutNonVirtualBase(BaseInfo);
1054   }
1055 }
1056
1057 void RecordLayoutBuilder::LayoutNonVirtualBase(const BaseSubobjectInfo *Base) {
1058   // Layout the base.
1059   CharUnits Offset = LayoutBase(Base);
1060
1061   // Add its base class offset.
1062   assert(!Bases.count(Base->Class) && "base offset already exists!");
1063   Bases.insert(std::make_pair(Base->Class, Offset));
1064
1065   AddPrimaryVirtualBaseOffsets(Base, Offset);
1066 }
1067
1068 void
1069 RecordLayoutBuilder::AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info,
1070                                                   CharUnits Offset) {
1071   // This base isn't interesting, it has no virtual bases.
1072   if (!Info->Class->getNumVBases())
1073     return;
1074
1075   // First, check if we have a virtual primary base to add offsets for.
1076   if (Info->PrimaryVirtualBaseInfo) {
1077     assert(Info->PrimaryVirtualBaseInfo->IsVirtual &&
1078            "Primary virtual base is not virtual!");
1079     if (Info->PrimaryVirtualBaseInfo->Derived == Info) {
1080       // Add the offset.
1081       assert(!VBases.count(Info->PrimaryVirtualBaseInfo->Class) &&
1082              "primary vbase offset already exists!");
1083       VBases.insert(std::make_pair(Info->PrimaryVirtualBaseInfo->Class,
1084                                    ASTRecordLayout::VBaseInfo(Offset, false)));
1085
1086       // Traverse the primary virtual base.
1087       AddPrimaryVirtualBaseOffsets(Info->PrimaryVirtualBaseInfo, Offset);
1088     }
1089   }
1090
1091   // Now go through all direct non-virtual bases.
1092   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
1093   for (const BaseSubobjectInfo *Base : Info->Bases) {
1094     if (Base->IsVirtual)
1095       continue;
1096
1097     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
1098     AddPrimaryVirtualBaseOffsets(Base, BaseOffset);
1099   }
1100 }
1101
1102 void
1103 RecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
1104                                         const CXXRecordDecl *MostDerivedClass) {
1105   const CXXRecordDecl *PrimaryBase;
1106   bool PrimaryBaseIsVirtual;
1107
1108   if (MostDerivedClass == RD) {
1109     PrimaryBase = this->PrimaryBase;
1110     PrimaryBaseIsVirtual = this->PrimaryBaseIsVirtual;
1111   } else {
1112     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1113     PrimaryBase = Layout.getPrimaryBase();
1114     PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
1115   }
1116
1117   for (const CXXBaseSpecifier &Base : RD->bases()) {
1118     assert(!Base.getType()->isDependentType() &&
1119            "Cannot layout class with dependent bases.");
1120
1121     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1122
1123     if (Base.isVirtual()) {
1124       if (PrimaryBase != BaseDecl || !PrimaryBaseIsVirtual) {
1125         bool IndirectPrimaryBase = IndirectPrimaryBases.count(BaseDecl);
1126
1127         // Only lay out the virtual base if it's not an indirect primary base.
1128         if (!IndirectPrimaryBase) {
1129           // Only visit virtual bases once.
1130           if (!VisitedVirtualBases.insert(BaseDecl).second)
1131             continue;
1132
1133           const BaseSubobjectInfo *BaseInfo = VirtualBaseInfo.lookup(BaseDecl);
1134           assert(BaseInfo && "Did not find virtual base info!");
1135           LayoutVirtualBase(BaseInfo);
1136         }
1137       }
1138     }
1139
1140     if (!BaseDecl->getNumVBases()) {
1141       // This base isn't interesting since it doesn't have any virtual bases.
1142       continue;
1143     }
1144
1145     LayoutVirtualBases(BaseDecl, MostDerivedClass);
1146   }
1147 }
1148
1149 void RecordLayoutBuilder::LayoutVirtualBase(const BaseSubobjectInfo *Base) {
1150   assert(!Base->Derived && "Trying to lay out a primary virtual base!");
1151
1152   // Layout the base.
1153   CharUnits Offset = LayoutBase(Base);
1154
1155   // Add its base class offset.
1156   assert(!VBases.count(Base->Class) && "vbase offset already exists!");
1157   VBases.insert(std::make_pair(Base->Class,
1158                        ASTRecordLayout::VBaseInfo(Offset, false)));
1159
1160   AddPrimaryVirtualBaseOffsets(Base, Offset);
1161 }
1162
1163 CharUnits RecordLayoutBuilder::LayoutBase(const BaseSubobjectInfo *Base) {
1164   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base->Class);
1165
1166
1167   CharUnits Offset;
1168
1169   // Query the external layout to see if it provides an offset.
1170   bool HasExternalLayout = false;
1171   if (UseExternalLayout) {
1172     llvm::DenseMap<const CXXRecordDecl *, CharUnits>::iterator Known;
1173     if (Base->IsVirtual)
1174       HasExternalLayout = External.getExternalNVBaseOffset(Base->Class, Offset);
1175     else
1176       HasExternalLayout = External.getExternalVBaseOffset(Base->Class, Offset);
1177   }
1178
1179   CharUnits UnpackedBaseAlign = Layout.getNonVirtualAlignment();
1180   CharUnits BaseAlign = (Packed) ? CharUnits::One() : UnpackedBaseAlign;
1181
1182   // If we have an empty base class, try to place it at offset 0.
1183   if (Base->Class->isEmpty() &&
1184       (!HasExternalLayout || Offset == CharUnits::Zero()) &&
1185       EmptySubobjects->CanPlaceBaseAtOffset(Base, CharUnits::Zero())) {
1186     setSize(std::max(getSize(), Layout.getSize()));
1187     UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1188
1189     return CharUnits::Zero();
1190   }
1191
1192   // The maximum field alignment overrides base align.
1193   if (!MaxFieldAlignment.isZero()) {
1194     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
1195     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
1196   }
1197
1198   if (!HasExternalLayout) {
1199     // Round up the current record size to the base's alignment boundary.
1200     Offset = getDataSize().RoundUpToAlignment(BaseAlign);
1201
1202     // Try to place the base.
1203     while (!EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset))
1204       Offset += BaseAlign;
1205   } else {
1206     bool Allowed = EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset);
1207     (void)Allowed;
1208     assert(Allowed && "Base subobject externally placed at overlapping offset");
1209
1210     if (InferAlignment && Offset < getDataSize().RoundUpToAlignment(BaseAlign)){
1211       // The externally-supplied base offset is before the base offset we
1212       // computed. Assume that the structure is packed.
1213       Alignment = CharUnits::One();
1214       InferAlignment = false;
1215     }
1216   }
1217
1218   if (!Base->Class->isEmpty()) {
1219     // Update the data size.
1220     setDataSize(Offset + Layout.getNonVirtualSize());
1221
1222     setSize(std::max(getSize(), getDataSize()));
1223   } else
1224     setSize(std::max(getSize(), Offset + Layout.getSize()));
1225
1226   // Remember max struct/class alignment.
1227   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1228
1229   return Offset;
1230 }
1231
1232 void RecordLayoutBuilder::InitializeLayout(const Decl *D) {
1233   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) {
1234     IsUnion = RD->isUnion();
1235     IsMsStruct = RD->isMsStruct(Context);
1236   }
1237
1238   Packed = D->hasAttr<PackedAttr>();
1239
1240   // Honor the default struct packing maximum alignment flag.
1241   if (unsigned DefaultMaxFieldAlignment = Context.getLangOpts().PackStruct) {
1242     MaxFieldAlignment = CharUnits::fromQuantity(DefaultMaxFieldAlignment);
1243   }
1244
1245   // mac68k alignment supersedes maximum field alignment and attribute aligned,
1246   // and forces all structures to have 2-byte alignment. The IBM docs on it
1247   // allude to additional (more complicated) semantics, especially with regard
1248   // to bit-fields, but gcc appears not to follow that.
1249   if (D->hasAttr<AlignMac68kAttr>()) {
1250     IsMac68kAlign = true;
1251     MaxFieldAlignment = CharUnits::fromQuantity(2);
1252     Alignment = CharUnits::fromQuantity(2);
1253   } else {
1254     if (const MaxFieldAlignmentAttr *MFAA = D->getAttr<MaxFieldAlignmentAttr>())
1255       MaxFieldAlignment = Context.toCharUnitsFromBits(MFAA->getAlignment());
1256
1257     if (unsigned MaxAlign = D->getMaxAlignment())
1258       UpdateAlignment(Context.toCharUnitsFromBits(MaxAlign));
1259   }
1260
1261   // If there is an external AST source, ask it for the various offsets.
1262   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D))
1263     if (ExternalASTSource *Source = Context.getExternalSource()) {
1264       UseExternalLayout = Source->layoutRecordType(
1265           RD, External.Size, External.Align, External.FieldOffsets,
1266           External.BaseOffsets, External.VirtualBaseOffsets);
1267
1268       // Update based on external alignment.
1269       if (UseExternalLayout) {
1270         if (External.Align > 0) {
1271           Alignment = Context.toCharUnitsFromBits(External.Align);
1272         } else {
1273           // The external source didn't have alignment information; infer it.
1274           InferAlignment = true;
1275         }
1276       }
1277     }
1278 }
1279
1280 void RecordLayoutBuilder::Layout(const RecordDecl *D) {
1281   InitializeLayout(D);
1282   LayoutFields(D);
1283
1284   // Finally, round the size of the total struct up to the alignment of the
1285   // struct itself.
1286   FinishLayout(D);
1287 }
1288
1289 void RecordLayoutBuilder::Layout(const CXXRecordDecl *RD) {
1290   InitializeLayout(RD);
1291
1292   // Lay out the vtable and the non-virtual bases.
1293   LayoutNonVirtualBases(RD);
1294
1295   LayoutFields(RD);
1296
1297   NonVirtualSize = Context.toCharUnitsFromBits(
1298         llvm::RoundUpToAlignment(getSizeInBits(),
1299                                  Context.getTargetInfo().getCharAlign()));
1300   NonVirtualAlignment = Alignment;
1301
1302   // Lay out the virtual bases and add the primary virtual base offsets.
1303   LayoutVirtualBases(RD, RD);
1304
1305   // Finally, round the size of the total struct up to the alignment
1306   // of the struct itself.
1307   FinishLayout(RD);
1308
1309 #ifndef NDEBUG
1310   // Check that we have base offsets for all bases.
1311   for (const CXXBaseSpecifier &Base : RD->bases()) {
1312     if (Base.isVirtual())
1313       continue;
1314
1315     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1316
1317     assert(Bases.count(BaseDecl) && "Did not find base offset!");
1318   }
1319
1320   // And all virtual bases.
1321   for (const CXXBaseSpecifier &Base : RD->vbases()) {
1322     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1323
1324     assert(VBases.count(BaseDecl) && "Did not find base offset!");
1325   }
1326 #endif
1327 }
1328
1329 void RecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D) {
1330   if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
1331     const ASTRecordLayout &SL = Context.getASTObjCInterfaceLayout(SD);
1332
1333     UpdateAlignment(SL.getAlignment());
1334
1335     // We start laying out ivars not at the end of the superclass
1336     // structure, but at the next byte following the last field.
1337     setSize(SL.getDataSize());
1338     setDataSize(getSize());
1339   }
1340
1341   InitializeLayout(D);
1342   // Layout each ivar sequentially.
1343   for (const ObjCIvarDecl *IVD = D->all_declared_ivar_begin(); IVD;
1344        IVD = IVD->getNextIvar())
1345     LayoutField(IVD, false);
1346
1347   // Finally, round the size of the total struct up to the alignment of the
1348   // struct itself.
1349   FinishLayout(D);
1350 }
1351
1352 void RecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
1353   // Layout each field, for now, just sequentially, respecting alignment.  In
1354   // the future, this will need to be tweakable by targets.
1355   bool InsertExtraPadding = D->mayInsertExtraPadding(/*EmitRemark=*/true);
1356   bool HasFlexibleArrayMember = D->hasFlexibleArrayMember();
1357   for (auto I = D->field_begin(), End = D->field_end(); I != End; ++I) {
1358     auto Next(I);
1359     ++Next;
1360     LayoutField(*I,
1361                 InsertExtraPadding && (Next != End || !HasFlexibleArrayMember));
1362   }
1363 }
1364
1365 // Rounds the specified size to have it a multiple of the char size.
1366 static uint64_t
1367 roundUpSizeToCharAlignment(uint64_t Size,
1368                            const ASTContext &Context) {
1369   uint64_t CharAlignment = Context.getTargetInfo().getCharAlign();
1370   return llvm::RoundUpToAlignment(Size, CharAlignment);
1371 }
1372
1373 void RecordLayoutBuilder::LayoutWideBitField(uint64_t FieldSize,
1374                                              uint64_t TypeSize,
1375                                              bool FieldPacked,
1376                                              const FieldDecl *D) {
1377   assert(Context.getLangOpts().CPlusPlus &&
1378          "Can only have wide bit-fields in C++!");
1379
1380   // Itanium C++ ABI 2.4:
1381   //   If sizeof(T)*8 < n, let T' be the largest integral POD type with
1382   //   sizeof(T')*8 <= n.
1383
1384   QualType IntegralPODTypes[] = {
1385     Context.UnsignedCharTy, Context.UnsignedShortTy, Context.UnsignedIntTy,
1386     Context.UnsignedLongTy, Context.UnsignedLongLongTy
1387   };
1388
1389   QualType Type;
1390   for (const QualType &QT : IntegralPODTypes) {
1391     uint64_t Size = Context.getTypeSize(QT);
1392
1393     if (Size > FieldSize)
1394       break;
1395
1396     Type = QT;
1397   }
1398   assert(!Type.isNull() && "Did not find a type!");
1399
1400   CharUnits TypeAlign = Context.getTypeAlignInChars(Type);
1401
1402   // We're not going to use any of the unfilled bits in the last byte.
1403   UnfilledBitsInLastUnit = 0;
1404   LastBitfieldTypeSize = 0;
1405
1406   uint64_t FieldOffset;
1407   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastUnit;
1408
1409   if (IsUnion) {
1410     uint64_t RoundedFieldSize = roundUpSizeToCharAlignment(FieldSize,
1411                                                            Context);
1412     setDataSize(std::max(getDataSizeInBits(), RoundedFieldSize));
1413     FieldOffset = 0;
1414   } else {
1415     // The bitfield is allocated starting at the next offset aligned
1416     // appropriately for T', with length n bits.
1417     FieldOffset = llvm::RoundUpToAlignment(getDataSizeInBits(),
1418                                            Context.toBits(TypeAlign));
1419
1420     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1421
1422     setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1423                                          Context.getTargetInfo().getCharAlign()));
1424     UnfilledBitsInLastUnit = getDataSizeInBits() - NewSizeInBits;
1425   }
1426
1427   // Place this field at the current location.
1428   FieldOffsets.push_back(FieldOffset);
1429
1430   CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, FieldOffset,
1431                     Context.toBits(TypeAlign), FieldPacked, D);
1432
1433   // Update the size.
1434   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1435
1436   // Remember max struct/class alignment.
1437   UpdateAlignment(TypeAlign);
1438 }
1439
1440 void RecordLayoutBuilder::LayoutBitField(const FieldDecl *D) {
1441   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1442   uint64_t FieldSize = D->getBitWidthValue(Context);
1443   TypeInfo FieldInfo = Context.getTypeInfo(D->getType());
1444   uint64_t TypeSize = FieldInfo.Width;
1445   unsigned FieldAlign = FieldInfo.Align;
1446
1447   // UnfilledBitsInLastUnit is the difference between the end of the
1448   // last allocated bitfield (i.e. the first bit offset available for
1449   // bitfields) and the end of the current data size in bits (i.e. the
1450   // first bit offset available for non-bitfields).  The current data
1451   // size in bits is always a multiple of the char size; additionally,
1452   // for ms_struct records it's also a multiple of the
1453   // LastBitfieldTypeSize (if set).
1454
1455   // The struct-layout algorithm is dictated by the platform ABI,
1456   // which in principle could use almost any rules it likes.  In
1457   // practice, UNIXy targets tend to inherit the algorithm described
1458   // in the System V generic ABI.  The basic bitfield layout rule in
1459   // System V is to place bitfields at the next available bit offset
1460   // where the entire bitfield would fit in an aligned storage unit of
1461   // the declared type; it's okay if an earlier or later non-bitfield
1462   // is allocated in the same storage unit.  However, some targets
1463   // (those that !useBitFieldTypeAlignment(), e.g. ARM APCS) don't
1464   // require this storage unit to be aligned, and therefore always put
1465   // the bitfield at the next available bit offset.
1466
1467   // ms_struct basically requests a complete replacement of the
1468   // platform ABI's struct-layout algorithm, with the high-level goal
1469   // of duplicating MSVC's layout.  For non-bitfields, this follows
1470   // the standard algorithm.  The basic bitfield layout rule is to
1471   // allocate an entire unit of the bitfield's declared type
1472   // (e.g. 'unsigned long'), then parcel it up among successive
1473   // bitfields whose declared types have the same size, making a new
1474   // unit as soon as the last can no longer store the whole value.
1475   // Since it completely replaces the platform ABI's algorithm,
1476   // settings like !useBitFieldTypeAlignment() do not apply.
1477
1478   // A zero-width bitfield forces the use of a new storage unit for
1479   // later bitfields.  In general, this occurs by rounding up the
1480   // current size of the struct as if the algorithm were about to
1481   // place a non-bitfield of the field's formal type.  Usually this
1482   // does not change the alignment of the struct itself, but it does
1483   // on some targets (those that useZeroLengthBitfieldAlignment(),
1484   // e.g. ARM).  In ms_struct layout, zero-width bitfields are
1485   // ignored unless they follow a non-zero-width bitfield.
1486
1487   // A field alignment restriction (e.g. from #pragma pack) or
1488   // specification (e.g. from __attribute__((aligned))) changes the
1489   // formal alignment of the field.  For System V, this alters the
1490   // required alignment of the notional storage unit that must contain
1491   // the bitfield.  For ms_struct, this only affects the placement of
1492   // new storage units.  In both cases, the effect of #pragma pack is
1493   // ignored on zero-width bitfields.
1494
1495   // On System V, a packed field (e.g. from #pragma pack or
1496   // __attribute__((packed))) always uses the next available bit
1497   // offset.
1498
1499   // In an ms_struct struct, the alignment of a fundamental type is
1500   // always equal to its size.  This is necessary in order to mimic
1501   // the i386 alignment rules on targets which might not fully align
1502   // all types (e.g. Darwin PPC32, where alignof(long long) == 4).
1503
1504   // First, some simple bookkeeping to perform for ms_struct structs.
1505   if (IsMsStruct) {
1506     // The field alignment for integer types is always the size.
1507     FieldAlign = TypeSize;
1508
1509     // If the previous field was not a bitfield, or was a bitfield
1510     // with a different storage unit size, we're done with that
1511     // storage unit.
1512     if (LastBitfieldTypeSize != TypeSize) {
1513       // Also, ignore zero-length bitfields after non-bitfields.
1514       if (!LastBitfieldTypeSize && !FieldSize)
1515         FieldAlign = 1;
1516
1517       UnfilledBitsInLastUnit = 0;
1518       LastBitfieldTypeSize = 0;
1519     }
1520   }
1521
1522   // If the field is wider than its declared type, it follows
1523   // different rules in all cases.
1524   if (FieldSize > TypeSize) {
1525     LayoutWideBitField(FieldSize, TypeSize, FieldPacked, D);
1526     return;
1527   }
1528
1529   // Compute the next available bit offset.
1530   uint64_t FieldOffset =
1531     IsUnion ? 0 : (getDataSizeInBits() - UnfilledBitsInLastUnit);
1532
1533   // Handle targets that don't honor bitfield type alignment.
1534   if (!IsMsStruct && !Context.getTargetInfo().useBitFieldTypeAlignment()) {
1535     // Some such targets do honor it on zero-width bitfields.
1536     if (FieldSize == 0 &&
1537         Context.getTargetInfo().useZeroLengthBitfieldAlignment()) {
1538       // The alignment to round up to is the max of the field's natural
1539       // alignment and a target-specific fixed value (sometimes zero).
1540       unsigned ZeroLengthBitfieldBoundary =
1541         Context.getTargetInfo().getZeroLengthBitfieldBoundary();
1542       FieldAlign = std::max(FieldAlign, ZeroLengthBitfieldBoundary);
1543
1544     // If that doesn't apply, just ignore the field alignment.
1545     } else {
1546       FieldAlign = 1;
1547     }
1548   }
1549
1550   // Remember the alignment we would have used if the field were not packed.
1551   unsigned UnpackedFieldAlign = FieldAlign;
1552
1553   // Ignore the field alignment if the field is packed unless it has zero-size.
1554   if (!IsMsStruct && FieldPacked && FieldSize != 0)
1555     FieldAlign = 1;
1556
1557   // But, if there's an 'aligned' attribute on the field, honor that.
1558   if (unsigned ExplicitFieldAlign = D->getMaxAlignment()) {
1559     FieldAlign = std::max(FieldAlign, ExplicitFieldAlign);
1560     UnpackedFieldAlign = std::max(UnpackedFieldAlign, ExplicitFieldAlign);
1561   }
1562
1563   // But, if there's a #pragma pack in play, that takes precedent over
1564   // even the 'aligned' attribute, for non-zero-width bitfields.
1565   if (!MaxFieldAlignment.isZero() && FieldSize) {
1566     unsigned MaxFieldAlignmentInBits = Context.toBits(MaxFieldAlignment);
1567     FieldAlign = std::min(FieldAlign, MaxFieldAlignmentInBits);
1568     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignmentInBits);
1569   }
1570
1571   // For purposes of diagnostics, we're going to simultaneously
1572   // compute the field offsets that we would have used if we weren't
1573   // adding any alignment padding or if the field weren't packed.
1574   uint64_t UnpaddedFieldOffset = FieldOffset;
1575   uint64_t UnpackedFieldOffset = FieldOffset;
1576
1577   // Check if we need to add padding to fit the bitfield within an
1578   // allocation unit with the right size and alignment.  The rules are
1579   // somewhat different here for ms_struct structs.
1580   if (IsMsStruct) {
1581     // If it's not a zero-width bitfield, and we can fit the bitfield
1582     // into the active storage unit (and we haven't already decided to
1583     // start a new storage unit), just do so, regardless of any other
1584     // other consideration.  Otherwise, round up to the right alignment.
1585     if (FieldSize == 0 || FieldSize > UnfilledBitsInLastUnit) {
1586       FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
1587       UnpackedFieldOffset = llvm::RoundUpToAlignment(UnpackedFieldOffset,
1588                                                      UnpackedFieldAlign);
1589       UnfilledBitsInLastUnit = 0;
1590     }
1591
1592   } else {
1593     // #pragma pack, with any value, suppresses the insertion of padding.
1594     bool AllowPadding = MaxFieldAlignment.isZero();
1595
1596     // Compute the real offset.
1597     if (FieldSize == 0 ||
1598         (AllowPadding &&
1599          (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)) {
1600       FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
1601     }
1602
1603     // Repeat the computation for diagnostic purposes.
1604     if (FieldSize == 0 ||
1605         (AllowPadding &&
1606          (UnpackedFieldOffset & (UnpackedFieldAlign-1)) + FieldSize > TypeSize))
1607       UnpackedFieldOffset = llvm::RoundUpToAlignment(UnpackedFieldOffset,
1608                                                      UnpackedFieldAlign);
1609   }
1610
1611   // If we're using external layout, give the external layout a chance
1612   // to override this information.
1613   if (UseExternalLayout)
1614     FieldOffset = updateExternalFieldOffset(D, FieldOffset);
1615
1616   // Okay, place the bitfield at the calculated offset.
1617   FieldOffsets.push_back(FieldOffset);
1618
1619   // Bookkeeping:
1620
1621   // Anonymous members don't affect the overall record alignment,
1622   // except on targets where they do.
1623   if (!IsMsStruct &&
1624       !Context.getTargetInfo().useZeroLengthBitfieldAlignment() &&
1625       !D->getIdentifier())
1626     FieldAlign = UnpackedFieldAlign = 1;
1627
1628   // Diagnose differences in layout due to padding or packing.
1629   if (!UseExternalLayout)
1630     CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, UnpackedFieldOffset,
1631                       UnpackedFieldAlign, FieldPacked, D);
1632
1633   // Update DataSize to include the last byte containing (part of) the bitfield.
1634
1635   // For unions, this is just a max operation, as usual.
1636   if (IsUnion) {
1637     uint64_t RoundedFieldSize = roundUpSizeToCharAlignment(FieldSize,
1638                                                            Context);
1639     setDataSize(std::max(getDataSizeInBits(), RoundedFieldSize));
1640   // For non-zero-width bitfields in ms_struct structs, allocate a new
1641   // storage unit if necessary.
1642   } else if (IsMsStruct && FieldSize) {
1643     // We should have cleared UnfilledBitsInLastUnit in every case
1644     // where we changed storage units.
1645     if (!UnfilledBitsInLastUnit) {
1646       setDataSize(FieldOffset + TypeSize);
1647       UnfilledBitsInLastUnit = TypeSize;
1648     }
1649     UnfilledBitsInLastUnit -= FieldSize;
1650     LastBitfieldTypeSize = TypeSize;
1651
1652   // Otherwise, bump the data size up to include the bitfield,
1653   // including padding up to char alignment, and then remember how
1654   // bits we didn't use.
1655   } else {
1656     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1657     uint64_t CharAlignment = Context.getTargetInfo().getCharAlign();
1658     setDataSize(llvm::RoundUpToAlignment(NewSizeInBits, CharAlignment));
1659     UnfilledBitsInLastUnit = getDataSizeInBits() - NewSizeInBits;
1660
1661     // The only time we can get here for an ms_struct is if this is a
1662     // zero-width bitfield, which doesn't count as anything for the
1663     // purposes of unfilled bits.
1664     LastBitfieldTypeSize = 0;
1665   }
1666
1667   // Update the size.
1668   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1669
1670   // Remember max struct/class alignment.
1671   UpdateAlignment(Context.toCharUnitsFromBits(FieldAlign),
1672                   Context.toCharUnitsFromBits(UnpackedFieldAlign));
1673 }
1674
1675 void RecordLayoutBuilder::LayoutField(const FieldDecl *D,
1676                                       bool InsertExtraPadding) {
1677   if (D->isBitField()) {
1678     LayoutBitField(D);
1679     return;
1680   }
1681
1682   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastUnit;
1683
1684   // Reset the unfilled bits.
1685   UnfilledBitsInLastUnit = 0;
1686   LastBitfieldTypeSize = 0;
1687
1688   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1689   CharUnits FieldOffset =
1690     IsUnion ? CharUnits::Zero() : getDataSize();
1691   CharUnits FieldSize;
1692   CharUnits FieldAlign;
1693
1694   if (D->getType()->isIncompleteArrayType()) {
1695     // This is a flexible array member; we can't directly
1696     // query getTypeInfo about these, so we figure it out here.
1697     // Flexible array members don't have any size, but they
1698     // have to be aligned appropriately for their element type.
1699     FieldSize = CharUnits::Zero();
1700     const ArrayType* ATy = Context.getAsArrayType(D->getType());
1701     FieldAlign = Context.getTypeAlignInChars(ATy->getElementType());
1702   } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
1703     unsigned AS = RT->getPointeeType().getAddressSpace();
1704     FieldSize =
1705       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(AS));
1706     FieldAlign =
1707       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(AS));
1708   } else {
1709     std::pair<CharUnits, CharUnits> FieldInfo =
1710       Context.getTypeInfoInChars(D->getType());
1711     FieldSize = FieldInfo.first;
1712     FieldAlign = FieldInfo.second;
1713
1714     if (IsMsStruct) {
1715       // If MS bitfield layout is required, figure out what type is being
1716       // laid out and align the field to the width of that type.
1717
1718       // Resolve all typedefs down to their base type and round up the field
1719       // alignment if necessary.
1720       QualType T = Context.getBaseElementType(D->getType());
1721       if (const BuiltinType *BTy = T->getAs<BuiltinType>()) {
1722         CharUnits TypeSize = Context.getTypeSizeInChars(BTy);
1723         if (TypeSize > FieldAlign)
1724           FieldAlign = TypeSize;
1725       }
1726     }
1727   }
1728
1729   // The align if the field is not packed. This is to check if the attribute
1730   // was unnecessary (-Wpacked).
1731   CharUnits UnpackedFieldAlign = FieldAlign;
1732   CharUnits UnpackedFieldOffset = FieldOffset;
1733
1734   if (FieldPacked)
1735     FieldAlign = CharUnits::One();
1736   CharUnits MaxAlignmentInChars =
1737     Context.toCharUnitsFromBits(D->getMaxAlignment());
1738   FieldAlign = std::max(FieldAlign, MaxAlignmentInChars);
1739   UnpackedFieldAlign = std::max(UnpackedFieldAlign, MaxAlignmentInChars);
1740
1741   // The maximum field alignment overrides the aligned attribute.
1742   if (!MaxFieldAlignment.isZero()) {
1743     FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
1744     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignment);
1745   }
1746
1747   // Round up the current record size to the field's alignment boundary.
1748   FieldOffset = FieldOffset.RoundUpToAlignment(FieldAlign);
1749   UnpackedFieldOffset =
1750     UnpackedFieldOffset.RoundUpToAlignment(UnpackedFieldAlign);
1751
1752   if (UseExternalLayout) {
1753     FieldOffset = Context.toCharUnitsFromBits(
1754                     updateExternalFieldOffset(D, Context.toBits(FieldOffset)));
1755
1756     if (!IsUnion && EmptySubobjects) {
1757       // Record the fact that we're placing a field at this offset.
1758       bool Allowed = EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset);
1759       (void)Allowed;
1760       assert(Allowed && "Externally-placed field cannot be placed here");
1761     }
1762   } else {
1763     if (!IsUnion && EmptySubobjects) {
1764       // Check if we can place the field at this offset.
1765       while (!EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset)) {
1766         // We couldn't place the field at the offset. Try again at a new offset.
1767         FieldOffset += FieldAlign;
1768       }
1769     }
1770   }
1771
1772   // Place this field at the current location.
1773   FieldOffsets.push_back(Context.toBits(FieldOffset));
1774
1775   if (!UseExternalLayout)
1776     CheckFieldPadding(Context.toBits(FieldOffset), UnpaddedFieldOffset,
1777                       Context.toBits(UnpackedFieldOffset),
1778                       Context.toBits(UnpackedFieldAlign), FieldPacked, D);
1779
1780   if (InsertExtraPadding) {
1781     CharUnits ASanAlignment = CharUnits::fromQuantity(8);
1782     CharUnits ExtraSizeForAsan = ASanAlignment;
1783     if (FieldSize % ASanAlignment)
1784       ExtraSizeForAsan +=
1785           ASanAlignment - CharUnits::fromQuantity(FieldSize % ASanAlignment);
1786     FieldSize += ExtraSizeForAsan;
1787   }
1788
1789   // Reserve space for this field.
1790   uint64_t FieldSizeInBits = Context.toBits(FieldSize);
1791   if (IsUnion)
1792     setDataSize(std::max(getDataSizeInBits(), FieldSizeInBits));
1793   else
1794     setDataSize(FieldOffset + FieldSize);
1795
1796   // Update the size.
1797   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1798
1799   // Remember max struct/class alignment.
1800   UpdateAlignment(FieldAlign, UnpackedFieldAlign);
1801 }
1802
1803 void RecordLayoutBuilder::FinishLayout(const NamedDecl *D) {
1804   // In C++, records cannot be of size 0.
1805   if (Context.getLangOpts().CPlusPlus && getSizeInBits() == 0) {
1806     if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
1807       // Compatibility with gcc requires a class (pod or non-pod)
1808       // which is not empty but of size 0; such as having fields of
1809       // array of zero-length, remains of Size 0
1810       if (RD->isEmpty())
1811         setSize(CharUnits::One());
1812     }
1813     else
1814       setSize(CharUnits::One());
1815   }
1816
1817   // Finally, round the size of the record up to the alignment of the
1818   // record itself.
1819   uint64_t UnpaddedSize = getSizeInBits() - UnfilledBitsInLastUnit;
1820   uint64_t UnpackedSizeInBits =
1821   llvm::RoundUpToAlignment(getSizeInBits(),
1822                            Context.toBits(UnpackedAlignment));
1823   CharUnits UnpackedSize = Context.toCharUnitsFromBits(UnpackedSizeInBits);
1824   uint64_t RoundedSize
1825     = llvm::RoundUpToAlignment(getSizeInBits(), Context.toBits(Alignment));
1826
1827   if (UseExternalLayout) {
1828     // If we're inferring alignment, and the external size is smaller than
1829     // our size after we've rounded up to alignment, conservatively set the
1830     // alignment to 1.
1831     if (InferAlignment && External.Size < RoundedSize) {
1832       Alignment = CharUnits::One();
1833       InferAlignment = false;
1834     }
1835     setSize(External.Size);
1836     return;
1837   }
1838
1839   // Set the size to the final size.
1840   setSize(RoundedSize);
1841
1842   unsigned CharBitNum = Context.getTargetInfo().getCharWidth();
1843   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) {
1844     // Warn if padding was introduced to the struct/class/union.
1845     if (getSizeInBits() > UnpaddedSize) {
1846       unsigned PadSize = getSizeInBits() - UnpaddedSize;
1847       bool InBits = true;
1848       if (PadSize % CharBitNum == 0) {
1849         PadSize = PadSize / CharBitNum;
1850         InBits = false;
1851       }
1852       Diag(RD->getLocation(), diag::warn_padded_struct_size)
1853           << Context.getTypeDeclType(RD)
1854           << PadSize
1855           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1); // plural or not
1856     }
1857
1858     // Warn if we packed it unnecessarily. If the alignment is 1 byte don't
1859     // bother since there won't be alignment issues.
1860     if (Packed && UnpackedAlignment > CharUnits::One() &&
1861         getSize() == UnpackedSize)
1862       Diag(D->getLocation(), diag::warn_unnecessary_packed)
1863           << Context.getTypeDeclType(RD);
1864   }
1865 }
1866
1867 void RecordLayoutBuilder::UpdateAlignment(CharUnits NewAlignment,
1868                                           CharUnits UnpackedNewAlignment) {
1869   // The alignment is not modified when using 'mac68k' alignment or when
1870   // we have an externally-supplied layout that also provides overall alignment.
1871   if (IsMac68kAlign || (UseExternalLayout && !InferAlignment))
1872     return;
1873
1874   if (NewAlignment > Alignment) {
1875     assert(llvm::isPowerOf2_64(NewAlignment.getQuantity()) &&
1876            "Alignment not a power of 2");
1877     Alignment = NewAlignment;
1878   }
1879
1880   if (UnpackedNewAlignment > UnpackedAlignment) {
1881     assert(llvm::isPowerOf2_64(UnpackedNewAlignment.getQuantity()) &&
1882            "Alignment not a power of 2");
1883     UnpackedAlignment = UnpackedNewAlignment;
1884   }
1885 }
1886
1887 uint64_t
1888 RecordLayoutBuilder::updateExternalFieldOffset(const FieldDecl *Field,
1889                                                uint64_t ComputedOffset) {
1890   uint64_t ExternalFieldOffset = External.getExternalFieldOffset(Field);
1891
1892   if (InferAlignment && ExternalFieldOffset < ComputedOffset) {
1893     // The externally-supplied field offset is before the field offset we
1894     // computed. Assume that the structure is packed.
1895     Alignment = CharUnits::One();
1896     InferAlignment = false;
1897   }
1898
1899   // Use the externally-supplied field offset.
1900   return ExternalFieldOffset;
1901 }
1902
1903 /// \brief Get diagnostic %select index for tag kind for
1904 /// field padding diagnostic message.
1905 /// WARNING: Indexes apply to particular diagnostics only!
1906 ///
1907 /// \returns diagnostic %select index.
1908 static unsigned getPaddingDiagFromTagKind(TagTypeKind Tag) {
1909   switch (Tag) {
1910   case TTK_Struct: return 0;
1911   case TTK_Interface: return 1;
1912   case TTK_Class: return 2;
1913   default: llvm_unreachable("Invalid tag kind for field padding diagnostic!");
1914   }
1915 }
1916
1917 void RecordLayoutBuilder::CheckFieldPadding(uint64_t Offset,
1918                                             uint64_t UnpaddedOffset,
1919                                             uint64_t UnpackedOffset,
1920                                             unsigned UnpackedAlign,
1921                                             bool isPacked,
1922                                             const FieldDecl *D) {
1923   // We let objc ivars without warning, objc interfaces generally are not used
1924   // for padding tricks.
1925   if (isa<ObjCIvarDecl>(D))
1926     return;
1927
1928   // Don't warn about structs created without a SourceLocation.  This can
1929   // be done by clients of the AST, such as codegen.
1930   if (D->getLocation().isInvalid())
1931     return;
1932
1933   unsigned CharBitNum = Context.getTargetInfo().getCharWidth();
1934
1935   // Warn if padding was introduced to the struct/class.
1936   if (!IsUnion && Offset > UnpaddedOffset) {
1937     unsigned PadSize = Offset - UnpaddedOffset;
1938     bool InBits = true;
1939     if (PadSize % CharBitNum == 0) {
1940       PadSize = PadSize / CharBitNum;
1941       InBits = false;
1942     }
1943     if (D->getIdentifier())
1944       Diag(D->getLocation(), diag::warn_padded_struct_field)
1945           << getPaddingDiagFromTagKind(D->getParent()->getTagKind())
1946           << Context.getTypeDeclType(D->getParent())
1947           << PadSize
1948           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1) // plural or not
1949           << D->getIdentifier();
1950     else
1951       Diag(D->getLocation(), diag::warn_padded_struct_anon_field)
1952           << getPaddingDiagFromTagKind(D->getParent()->getTagKind())
1953           << Context.getTypeDeclType(D->getParent())
1954           << PadSize
1955           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1); // plural or not
1956   }
1957
1958   // Warn if we packed it unnecessarily. If the alignment is 1 byte don't
1959   // bother since there won't be alignment issues.
1960   if (isPacked && UnpackedAlign > CharBitNum && Offset == UnpackedOffset)
1961     Diag(D->getLocation(), diag::warn_unnecessary_packed)
1962         << D->getIdentifier();
1963 }
1964
1965 static const CXXMethodDecl *computeKeyFunction(ASTContext &Context,
1966                                                const CXXRecordDecl *RD) {
1967   // If a class isn't polymorphic it doesn't have a key function.
1968   if (!RD->isPolymorphic())
1969     return nullptr;
1970
1971   // A class that is not externally visible doesn't have a key function. (Or
1972   // at least, there's no point to assigning a key function to such a class;
1973   // this doesn't affect the ABI.)
1974   if (!RD->isExternallyVisible())
1975     return nullptr;
1976
1977   // Template instantiations don't have key functions per Itanium C++ ABI 5.2.6.
1978   // Same behavior as GCC.
1979   TemplateSpecializationKind TSK = RD->getTemplateSpecializationKind();
1980   if (TSK == TSK_ImplicitInstantiation ||
1981       TSK == TSK_ExplicitInstantiationDeclaration ||
1982       TSK == TSK_ExplicitInstantiationDefinition)
1983     return nullptr;
1984
1985   bool allowInlineFunctions =
1986     Context.getTargetInfo().getCXXABI().canKeyFunctionBeInline();
1987
1988   for (const CXXMethodDecl *MD : RD->methods()) {
1989     if (!MD->isVirtual())
1990       continue;
1991
1992     if (MD->isPure())
1993       continue;
1994
1995     // Ignore implicit member functions, they are always marked as inline, but
1996     // they don't have a body until they're defined.
1997     if (MD->isImplicit())
1998       continue;
1999
2000     if (MD->isInlineSpecified())
2001       continue;
2002
2003     if (MD->hasInlineBody())
2004       continue;
2005
2006     // Ignore inline deleted or defaulted functions.
2007     if (!MD->isUserProvided())
2008       continue;
2009
2010     // In certain ABIs, ignore functions with out-of-line inline definitions.
2011     if (!allowInlineFunctions) {
2012       const FunctionDecl *Def;
2013       if (MD->hasBody(Def) && Def->isInlineSpecified())
2014         continue;
2015     }
2016
2017     // If the key function is dllimport but the class isn't, then the class has
2018     // no key function. The DLL that exports the key function won't export the
2019     // vtable in this case.
2020     if (MD->hasAttr<DLLImportAttr>() && !RD->hasAttr<DLLImportAttr>())
2021       return nullptr;
2022
2023     // We found it.
2024     return MD;
2025   }
2026
2027   return nullptr;
2028 }
2029
2030 DiagnosticBuilder
2031 RecordLayoutBuilder::Diag(SourceLocation Loc, unsigned DiagID) {
2032   return Context.getDiagnostics().Report(Loc, DiagID);
2033 }
2034
2035 /// Does the target C++ ABI require us to skip over the tail-padding
2036 /// of the given class (considering it as a base class) when allocating
2037 /// objects?
2038 static bool mustSkipTailPadding(TargetCXXABI ABI, const CXXRecordDecl *RD) {
2039   switch (ABI.getTailPaddingUseRules()) {
2040   case TargetCXXABI::AlwaysUseTailPadding:
2041     return false;
2042
2043   case TargetCXXABI::UseTailPaddingUnlessPOD03:
2044     // FIXME: To the extent that this is meant to cover the Itanium ABI
2045     // rules, we should implement the restrictions about over-sized
2046     // bitfields:
2047     //
2048     // http://mentorembedded.github.com/cxx-abi/abi.html#POD :
2049     //   In general, a type is considered a POD for the purposes of
2050     //   layout if it is a POD type (in the sense of ISO C++
2051     //   [basic.types]). However, a POD-struct or POD-union (in the
2052     //   sense of ISO C++ [class]) with a bitfield member whose
2053     //   declared width is wider than the declared type of the
2054     //   bitfield is not a POD for the purpose of layout.  Similarly,
2055     //   an array type is not a POD for the purpose of layout if the
2056     //   element type of the array is not a POD for the purpose of
2057     //   layout.
2058     //
2059     //   Where references to the ISO C++ are made in this paragraph,
2060     //   the Technical Corrigendum 1 version of the standard is
2061     //   intended.
2062     return RD->isPOD();
2063
2064   case TargetCXXABI::UseTailPaddingUnlessPOD11:
2065     // This is equivalent to RD->getTypeForDecl().isCXX11PODType(),
2066     // but with a lot of abstraction penalty stripped off.  This does
2067     // assume that these properties are set correctly even in C++98
2068     // mode; fortunately, that is true because we want to assign
2069     // consistently semantics to the type-traits intrinsics (or at
2070     // least as many of them as possible).
2071     return RD->isTrivial() && RD->isStandardLayout();
2072   }
2073
2074   llvm_unreachable("bad tail-padding use kind");
2075 }
2076
2077 static bool isMsLayout(const RecordDecl* D) {
2078   return D->getASTContext().getTargetInfo().getCXXABI().isMicrosoft();
2079 }
2080
2081 // This section contains an implementation of struct layout that is, up to the
2082 // included tests, compatible with cl.exe (2013).  The layout produced is
2083 // significantly different than those produced by the Itanium ABI.  Here we note
2084 // the most important differences.
2085 //
2086 // * The alignment of bitfields in unions is ignored when computing the
2087 //   alignment of the union.
2088 // * The existence of zero-width bitfield that occurs after anything other than
2089 //   a non-zero length bitfield is ignored.
2090 // * There is no explicit primary base for the purposes of layout.  All bases
2091 //   with vfptrs are laid out first, followed by all bases without vfptrs.
2092 // * The Itanium equivalent vtable pointers are split into a vfptr (virtual
2093 //   function pointer) and a vbptr (virtual base pointer).  They can each be
2094 //   shared with a, non-virtual bases. These bases need not be the same.  vfptrs
2095 //   always occur at offset 0.  vbptrs can occur at an arbitrary offset and are
2096 //   placed after the lexiographically last non-virtual base.  This placement
2097 //   is always before fields but can be in the middle of the non-virtual bases
2098 //   due to the two-pass layout scheme for non-virtual-bases.
2099 // * Virtual bases sometimes require a 'vtordisp' field that is laid out before
2100 //   the virtual base and is used in conjunction with virtual overrides during
2101 //   construction and destruction.  This is always a 4 byte value and is used as
2102 //   an alternative to constructor vtables.
2103 // * vtordisps are allocated in a block of memory with size and alignment equal
2104 //   to the alignment of the completed structure (before applying __declspec(
2105 //   align())).  The vtordisp always occur at the end of the allocation block,
2106 //   immediately prior to the virtual base.
2107 // * vfptrs are injected after all bases and fields have been laid out.  In
2108 //   order to guarantee proper alignment of all fields, the vfptr injection
2109 //   pushes all bases and fields back by the alignment imposed by those bases
2110 //   and fields.  This can potentially add a significant amount of padding.
2111 //   vfptrs are always injected at offset 0.
2112 // * vbptrs are injected after all bases and fields have been laid out.  In
2113 //   order to guarantee proper alignment of all fields, the vfptr injection
2114 //   pushes all bases and fields back by the alignment imposed by those bases
2115 //   and fields.  This can potentially add a significant amount of padding.
2116 //   vbptrs are injected immediately after the last non-virtual base as
2117 //   lexiographically ordered in the code.  If this site isn't pointer aligned
2118 //   the vbptr is placed at the next properly aligned location.  Enough padding
2119 //   is added to guarantee a fit.
2120 // * The last zero sized non-virtual base can be placed at the end of the
2121 //   struct (potentially aliasing another object), or may alias with the first
2122 //   field, even if they are of the same type.
2123 // * The last zero size virtual base may be placed at the end of the struct
2124 //   potentially aliasing another object.
2125 // * The ABI attempts to avoid aliasing of zero sized bases by adding padding
2126 //   between bases or vbases with specific properties.  The criteria for
2127 //   additional padding between two bases is that the first base is zero sized
2128 //   or ends with a zero sized subobject and the second base is zero sized or
2129 //   trails with a zero sized base or field (sharing of vfptrs can reorder the
2130 //   layout of the so the leading base is not always the first one declared).
2131 //   This rule does take into account fields that are not records, so padding
2132 //   will occur even if the last field is, e.g. an int. The padding added for
2133 //   bases is 1 byte.  The padding added between vbases depends on the alignment
2134 //   of the object but is at least 4 bytes (in both 32 and 64 bit modes).
2135 // * There is no concept of non-virtual alignment, non-virtual alignment and
2136 //   alignment are always identical.
2137 // * There is a distinction between alignment and required alignment.
2138 //   __declspec(align) changes the required alignment of a struct.  This
2139 //   alignment is _always_ obeyed, even in the presence of #pragma pack. A
2140 //   record inherits required alignment from all of its fields and bases.
2141 // * __declspec(align) on bitfields has the effect of changing the bitfield's
2142 //   alignment instead of its required alignment.  This is the only known way
2143 //   to make the alignment of a struct bigger than 8.  Interestingly enough
2144 //   this alignment is also immune to the effects of #pragma pack and can be
2145 //   used to create structures with large alignment under #pragma pack.
2146 //   However, because it does not impact required alignment, such a structure,
2147 //   when used as a field or base, will not be aligned if #pragma pack is
2148 //   still active at the time of use.
2149 //
2150 // Known incompatibilities:
2151 // * all: #pragma pack between fields in a record
2152 // * 2010 and back: If the last field in a record is a bitfield, every object
2153 //   laid out after the record will have extra padding inserted before it.  The
2154 //   extra padding will have size equal to the size of the storage class of the
2155 //   bitfield.  0 sized bitfields don't exhibit this behavior and the extra
2156 //   padding can be avoided by adding a 0 sized bitfield after the non-zero-
2157 //   sized bitfield.
2158 // * 2012 and back: In 64-bit mode, if the alignment of a record is 16 or
2159 //   greater due to __declspec(align()) then a second layout phase occurs after
2160 //   The locations of the vf and vb pointers are known.  This layout phase
2161 //   suffers from the "last field is a bitfield" bug in 2010 and results in
2162 //   _every_ field getting padding put in front of it, potentially including the
2163 //   vfptr, leaving the vfprt at a non-zero location which results in a fault if
2164 //   anything tries to read the vftbl.  The second layout phase also treats
2165 //   bitfields as separate entities and gives them each storage rather than
2166 //   packing them.  Additionally, because this phase appears to perform a
2167 //   (an unstable) sort on the members before laying them out and because merged
2168 //   bitfields have the same address, the bitfields end up in whatever order
2169 //   the sort left them in, a behavior we could never hope to replicate.
2170
2171 namespace {
2172 struct MicrosoftRecordLayoutBuilder {
2173   struct ElementInfo {
2174     CharUnits Size;
2175     CharUnits Alignment;
2176   };
2177   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsetsMapTy;
2178   MicrosoftRecordLayoutBuilder(const ASTContext &Context) : Context(Context) {}
2179 private:
2180   MicrosoftRecordLayoutBuilder(const MicrosoftRecordLayoutBuilder &) = delete;
2181   void operator=(const MicrosoftRecordLayoutBuilder &) = delete;
2182 public:
2183   void layout(const RecordDecl *RD);
2184   void cxxLayout(const CXXRecordDecl *RD);
2185   /// \brief Initializes size and alignment and honors some flags.
2186   void initializeLayout(const RecordDecl *RD);
2187   /// \brief Initialized C++ layout, compute alignment and virtual alignment and
2188   /// existence of vfptrs and vbptrs.  Alignment is needed before the vfptr is
2189   /// laid out.
2190   void initializeCXXLayout(const CXXRecordDecl *RD);
2191   void layoutNonVirtualBases(const CXXRecordDecl *RD);
2192   void layoutNonVirtualBase(const CXXRecordDecl *BaseDecl,
2193                             const ASTRecordLayout &BaseLayout,
2194                             const ASTRecordLayout *&PreviousBaseLayout);
2195   void injectVFPtr(const CXXRecordDecl *RD);
2196   void injectVBPtr(const CXXRecordDecl *RD);
2197   /// \brief Lays out the fields of the record.  Also rounds size up to
2198   /// alignment.
2199   void layoutFields(const RecordDecl *RD);
2200   void layoutField(const FieldDecl *FD);
2201   void layoutBitField(const FieldDecl *FD);
2202   /// \brief Lays out a single zero-width bit-field in the record and handles
2203   /// special cases associated with zero-width bit-fields.
2204   void layoutZeroWidthBitField(const FieldDecl *FD);
2205   void layoutVirtualBases(const CXXRecordDecl *RD);
2206   void finalizeLayout(const RecordDecl *RD);
2207   /// \brief Gets the size and alignment of a base taking pragma pack and
2208   /// __declspec(align) into account.
2209   ElementInfo getAdjustedElementInfo(const ASTRecordLayout &Layout);
2210   /// \brief Gets the size and alignment of a field taking pragma  pack and
2211   /// __declspec(align) into account.  It also updates RequiredAlignment as a
2212   /// side effect because it is most convenient to do so here.
2213   ElementInfo getAdjustedElementInfo(const FieldDecl *FD);
2214   /// \brief Places a field at an offset in CharUnits.
2215   void placeFieldAtOffset(CharUnits FieldOffset) {
2216     FieldOffsets.push_back(Context.toBits(FieldOffset));
2217   }
2218   /// \brief Places a bitfield at a bit offset.
2219   void placeFieldAtBitOffset(uint64_t FieldOffset) {
2220     FieldOffsets.push_back(FieldOffset);
2221   }
2222   /// \brief Compute the set of virtual bases for which vtordisps are required.
2223   void computeVtorDispSet(
2224       llvm::SmallPtrSetImpl<const CXXRecordDecl *> &HasVtorDispSet,
2225       const CXXRecordDecl *RD) const;
2226   const ASTContext &Context;
2227   /// \brief The size of the record being laid out.
2228   CharUnits Size;
2229   /// \brief The non-virtual size of the record layout.
2230   CharUnits NonVirtualSize;
2231   /// \brief The data size of the record layout.
2232   CharUnits DataSize;
2233   /// \brief The current alignment of the record layout.
2234   CharUnits Alignment;
2235   /// \brief The maximum allowed field alignment. This is set by #pragma pack.
2236   CharUnits MaxFieldAlignment;
2237   /// \brief The alignment that this record must obey.  This is imposed by
2238   /// __declspec(align()) on the record itself or one of its fields or bases.
2239   CharUnits RequiredAlignment;
2240   /// \brief The size of the allocation of the currently active bitfield.
2241   /// This value isn't meaningful unless LastFieldIsNonZeroWidthBitfield
2242   /// is true.
2243   CharUnits CurrentBitfieldSize;
2244   /// \brief Offset to the virtual base table pointer (if one exists).
2245   CharUnits VBPtrOffset;
2246   /// \brief Minimum record size possible.
2247   CharUnits MinEmptyStructSize;
2248   /// \brief The size and alignment info of a pointer.
2249   ElementInfo PointerInfo;
2250   /// \brief The primary base class (if one exists).
2251   const CXXRecordDecl *PrimaryBase;
2252   /// \brief The class we share our vb-pointer with.
2253   const CXXRecordDecl *SharedVBPtrBase;
2254   /// \brief The collection of field offsets.
2255   SmallVector<uint64_t, 16> FieldOffsets;
2256   /// \brief Base classes and their offsets in the record.
2257   BaseOffsetsMapTy Bases;
2258   /// \brief virtual base classes and their offsets in the record.
2259   ASTRecordLayout::VBaseOffsetsMapTy VBases;
2260   /// \brief The number of remaining bits in our last bitfield allocation.
2261   /// This value isn't meaningful unless LastFieldIsNonZeroWidthBitfield is
2262   /// true.
2263   unsigned RemainingBitsInField;
2264   bool IsUnion : 1;
2265   /// \brief True if the last field laid out was a bitfield and was not 0
2266   /// width.
2267   bool LastFieldIsNonZeroWidthBitfield : 1;
2268   /// \brief True if the class has its own vftable pointer.
2269   bool HasOwnVFPtr : 1;
2270   /// \brief True if the class has a vbtable pointer.
2271   bool HasVBPtr : 1;
2272   /// \brief True if the last sub-object within the type is zero sized or the
2273   /// object itself is zero sized.  This *does not* count members that are not
2274   /// records.  Only used for MS-ABI.
2275   bool EndsWithZeroSizedObject : 1;
2276   /// \brief True if this class is zero sized or first base is zero sized or
2277   /// has this property.  Only used for MS-ABI.
2278   bool LeadsWithZeroSizedBase : 1;
2279
2280   /// \brief True if the external AST source provided a layout for this record.
2281   bool UseExternalLayout : 1;
2282
2283   /// \brief The layout provided by the external AST source. Only active if
2284   /// UseExternalLayout is true.
2285   ExternalLayout External;
2286 };
2287 } // namespace
2288
2289 MicrosoftRecordLayoutBuilder::ElementInfo
2290 MicrosoftRecordLayoutBuilder::getAdjustedElementInfo(
2291     const ASTRecordLayout &Layout) {
2292   ElementInfo Info;
2293   Info.Alignment = Layout.getAlignment();
2294   // Respect pragma pack.
2295   if (!MaxFieldAlignment.isZero())
2296     Info.Alignment = std::min(Info.Alignment, MaxFieldAlignment);
2297   // Track zero-sized subobjects here where it's already available.
2298   EndsWithZeroSizedObject = Layout.hasZeroSizedSubObject();
2299   // Respect required alignment, this is necessary because we may have adjusted
2300   // the alignment in the case of pragam pack.  Note that the required alignment
2301   // doesn't actually apply to the struct alignment at this point.
2302   Alignment = std::max(Alignment, Info.Alignment);
2303   RequiredAlignment = std::max(RequiredAlignment, Layout.getRequiredAlignment());
2304   Info.Alignment = std::max(Info.Alignment, Layout.getRequiredAlignment());
2305   Info.Size = Layout.getNonVirtualSize();
2306   return Info;
2307 }
2308
2309 MicrosoftRecordLayoutBuilder::ElementInfo
2310 MicrosoftRecordLayoutBuilder::getAdjustedElementInfo(
2311     const FieldDecl *FD) {
2312   // Get the alignment of the field type's natural alignment, ignore any
2313   // alignment attributes.
2314   ElementInfo Info;
2315   std::tie(Info.Size, Info.Alignment) =
2316       Context.getTypeInfoInChars(FD->getType()->getUnqualifiedDesugaredType());
2317   // Respect align attributes on the field.
2318   CharUnits FieldRequiredAlignment =
2319       Context.toCharUnitsFromBits(FD->getMaxAlignment());
2320   // Respect align attributes on the type.
2321   if (Context.isAlignmentRequired(FD->getType()))
2322     FieldRequiredAlignment = std::max(
2323         Context.getTypeAlignInChars(FD->getType()), FieldRequiredAlignment);
2324   // Respect attributes applied to subobjects of the field.
2325   if (FD->isBitField())
2326     // For some reason __declspec align impacts alignment rather than required
2327     // alignment when it is applied to bitfields.
2328     Info.Alignment = std::max(Info.Alignment, FieldRequiredAlignment);
2329   else {
2330     if (auto RT =
2331             FD->getType()->getBaseElementTypeUnsafe()->getAs<RecordType>()) {
2332       auto const &Layout = Context.getASTRecordLayout(RT->getDecl());
2333       EndsWithZeroSizedObject = Layout.hasZeroSizedSubObject();
2334       FieldRequiredAlignment = std::max(FieldRequiredAlignment,
2335                                         Layout.getRequiredAlignment());
2336     }
2337     // Capture required alignment as a side-effect.
2338     RequiredAlignment = std::max(RequiredAlignment, FieldRequiredAlignment);
2339   }
2340   // Respect pragma pack, attribute pack and declspec align
2341   if (!MaxFieldAlignment.isZero())
2342     Info.Alignment = std::min(Info.Alignment, MaxFieldAlignment);
2343   if (FD->hasAttr<PackedAttr>())
2344     Info.Alignment = CharUnits::One();
2345   Info.Alignment = std::max(Info.Alignment, FieldRequiredAlignment);
2346   return Info;
2347 }
2348
2349 void MicrosoftRecordLayoutBuilder::layout(const RecordDecl *RD) {
2350   // For C record layout, zero-sized records always have size 4.
2351   MinEmptyStructSize = CharUnits::fromQuantity(4);
2352   initializeLayout(RD);
2353   layoutFields(RD);
2354   DataSize = Size = Size.RoundUpToAlignment(Alignment);
2355   RequiredAlignment = std::max(
2356       RequiredAlignment, Context.toCharUnitsFromBits(RD->getMaxAlignment()));
2357   finalizeLayout(RD);
2358 }
2359
2360 void MicrosoftRecordLayoutBuilder::cxxLayout(const CXXRecordDecl *RD) {
2361   // The C++ standard says that empty structs have size 1.
2362   MinEmptyStructSize = CharUnits::One();
2363   initializeLayout(RD);
2364   initializeCXXLayout(RD);
2365   layoutNonVirtualBases(RD);
2366   layoutFields(RD);
2367   injectVBPtr(RD);
2368   injectVFPtr(RD);
2369   if (HasOwnVFPtr || (HasVBPtr && !SharedVBPtrBase))
2370     Alignment = std::max(Alignment, PointerInfo.Alignment);
2371   auto RoundingAlignment = Alignment;
2372   if (!MaxFieldAlignment.isZero())
2373     RoundingAlignment = std::min(RoundingAlignment, MaxFieldAlignment);
2374   NonVirtualSize = Size = Size.RoundUpToAlignment(RoundingAlignment);
2375   RequiredAlignment = std::max(
2376       RequiredAlignment, Context.toCharUnitsFromBits(RD->getMaxAlignment()));
2377   layoutVirtualBases(RD);
2378   finalizeLayout(RD);
2379 }
2380
2381 void MicrosoftRecordLayoutBuilder::initializeLayout(const RecordDecl *RD) {
2382   IsUnion = RD->isUnion();
2383   Size = CharUnits::Zero();
2384   Alignment = CharUnits::One();
2385   // In 64-bit mode we always perform an alignment step after laying out vbases.
2386   // In 32-bit mode we do not.  The check to see if we need to perform alignment
2387   // checks the RequiredAlignment field and performs alignment if it isn't 0.
2388   RequiredAlignment = Context.getTargetInfo().getTriple().isArch64Bit()
2389                           ? CharUnits::One()
2390                           : CharUnits::Zero();
2391   // Compute the maximum field alignment.
2392   MaxFieldAlignment = CharUnits::Zero();
2393   // Honor the default struct packing maximum alignment flag.
2394   if (unsigned DefaultMaxFieldAlignment = Context.getLangOpts().PackStruct)
2395       MaxFieldAlignment = CharUnits::fromQuantity(DefaultMaxFieldAlignment);
2396   // Honor the packing attribute.  The MS-ABI ignores pragma pack if its larger
2397   // than the pointer size.
2398   if (const MaxFieldAlignmentAttr *MFAA = RD->getAttr<MaxFieldAlignmentAttr>()){
2399     unsigned PackedAlignment = MFAA->getAlignment();
2400     if (PackedAlignment <= Context.getTargetInfo().getPointerWidth(0))
2401       MaxFieldAlignment = Context.toCharUnitsFromBits(PackedAlignment);
2402   }
2403   // Packed attribute forces max field alignment to be 1.
2404   if (RD->hasAttr<PackedAttr>())
2405     MaxFieldAlignment = CharUnits::One();
2406
2407   // Try to respect the external layout if present.
2408   UseExternalLayout = false;
2409   if (ExternalASTSource *Source = Context.getExternalSource())
2410     UseExternalLayout = Source->layoutRecordType(
2411         RD, External.Size, External.Align, External.FieldOffsets,
2412         External.BaseOffsets, External.VirtualBaseOffsets);
2413 }
2414
2415 void
2416 MicrosoftRecordLayoutBuilder::initializeCXXLayout(const CXXRecordDecl *RD) {
2417   EndsWithZeroSizedObject = false;
2418   LeadsWithZeroSizedBase = false;
2419   HasOwnVFPtr = false;
2420   HasVBPtr = false;
2421   PrimaryBase = nullptr;
2422   SharedVBPtrBase = nullptr;
2423   // Calculate pointer size and alignment.  These are used for vfptr and vbprt
2424   // injection.
2425   PointerInfo.Size =
2426       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
2427   PointerInfo.Alignment =
2428       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(0));
2429   // Respect pragma pack.
2430   if (!MaxFieldAlignment.isZero())
2431     PointerInfo.Alignment = std::min(PointerInfo.Alignment, MaxFieldAlignment);
2432 }
2433
2434 void
2435 MicrosoftRecordLayoutBuilder::layoutNonVirtualBases(const CXXRecordDecl *RD) {
2436   // The MS-ABI lays out all bases that contain leading vfptrs before it lays
2437   // out any bases that do not contain vfptrs.  We implement this as two passes
2438   // over the bases.  This approach guarantees that the primary base is laid out
2439   // first.  We use these passes to calculate some additional aggregated
2440   // information about the bases, such as reqruied alignment and the presence of
2441   // zero sized members.
2442   const ASTRecordLayout *PreviousBaseLayout = nullptr;
2443   // Iterate through the bases and lay out the non-virtual ones.
2444   for (const CXXBaseSpecifier &Base : RD->bases()) {
2445     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2446     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2447     // Mark and skip virtual bases.
2448     if (Base.isVirtual()) {
2449       HasVBPtr = true;
2450       continue;
2451     }
2452     // Check fo a base to share a VBPtr with.
2453     if (!SharedVBPtrBase && BaseLayout.hasVBPtr()) {
2454       SharedVBPtrBase = BaseDecl;
2455       HasVBPtr = true;
2456     }
2457     // Only lay out bases with extendable VFPtrs on the first pass.
2458     if (!BaseLayout.hasExtendableVFPtr())
2459       continue;
2460     // If we don't have a primary base, this one qualifies.
2461     if (!PrimaryBase) {
2462       PrimaryBase = BaseDecl;
2463       LeadsWithZeroSizedBase = BaseLayout.leadsWithZeroSizedBase();
2464     }
2465     // Lay out the base.
2466     layoutNonVirtualBase(BaseDecl, BaseLayout, PreviousBaseLayout);
2467   }
2468   // Figure out if we need a fresh VFPtr for this class.
2469   if (!PrimaryBase && RD->isDynamicClass())
2470     for (CXXRecordDecl::method_iterator i = RD->method_begin(),
2471                                         e = RD->method_end();
2472          !HasOwnVFPtr && i != e; ++i)
2473       HasOwnVFPtr = i->isVirtual() && i->size_overridden_methods() == 0;
2474   // If we don't have a primary base then we have a leading object that could
2475   // itself lead with a zero-sized object, something we track.
2476   bool CheckLeadingLayout = !PrimaryBase;
2477   // Iterate through the bases and lay out the non-virtual ones.
2478   for (const CXXBaseSpecifier &Base : RD->bases()) {
2479     if (Base.isVirtual())
2480       continue;
2481     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2482     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2483     // Only lay out bases without extendable VFPtrs on the second pass.
2484     if (BaseLayout.hasExtendableVFPtr()) {
2485       VBPtrOffset = Bases[BaseDecl] + BaseLayout.getNonVirtualSize();
2486       continue;
2487     }
2488     // If this is the first layout, check to see if it leads with a zero sized
2489     // object.  If it does, so do we.
2490     if (CheckLeadingLayout) {
2491       CheckLeadingLayout = false;
2492       LeadsWithZeroSizedBase = BaseLayout.leadsWithZeroSizedBase();
2493     }
2494     // Lay out the base.
2495     layoutNonVirtualBase(BaseDecl, BaseLayout, PreviousBaseLayout);
2496     VBPtrOffset = Bases[BaseDecl] + BaseLayout.getNonVirtualSize();
2497   }
2498   // Set our VBPtroffset if we know it at this point.
2499   if (!HasVBPtr)
2500     VBPtrOffset = CharUnits::fromQuantity(-1);
2501   else if (SharedVBPtrBase) {
2502     const ASTRecordLayout &Layout = Context.getASTRecordLayout(SharedVBPtrBase);
2503     VBPtrOffset = Bases[SharedVBPtrBase] + Layout.getVBPtrOffset();
2504   }
2505 }
2506
2507 void MicrosoftRecordLayoutBuilder::layoutNonVirtualBase(
2508     const CXXRecordDecl *BaseDecl,
2509     const ASTRecordLayout &BaseLayout,
2510     const ASTRecordLayout *&PreviousBaseLayout) {
2511   // Insert padding between two bases if the left first one is zero sized or
2512   // contains a zero sized subobject and the right is zero sized or one leads
2513   // with a zero sized base.
2514   if (PreviousBaseLayout && PreviousBaseLayout->hasZeroSizedSubObject() &&
2515       BaseLayout.leadsWithZeroSizedBase())
2516     Size++;
2517   ElementInfo Info = getAdjustedElementInfo(BaseLayout);
2518   CharUnits BaseOffset;
2519
2520   // Respect the external AST source base offset, if present.
2521   bool FoundBase = false;
2522   if (UseExternalLayout) {
2523     FoundBase = External.getExternalNVBaseOffset(BaseDecl, BaseOffset);
2524     if (FoundBase)
2525       assert(BaseOffset >= Size && "base offset already allocated");
2526   }
2527
2528   if (!FoundBase)
2529     BaseOffset = Size.RoundUpToAlignment(Info.Alignment);
2530   Bases.insert(std::make_pair(BaseDecl, BaseOffset));
2531   Size = BaseOffset + BaseLayout.getNonVirtualSize();
2532   PreviousBaseLayout = &BaseLayout;
2533 }
2534
2535 void MicrosoftRecordLayoutBuilder::layoutFields(const RecordDecl *RD) {
2536   LastFieldIsNonZeroWidthBitfield = false;
2537   for (const FieldDecl *Field : RD->fields())
2538     layoutField(Field);
2539 }
2540
2541 void MicrosoftRecordLayoutBuilder::layoutField(const FieldDecl *FD) {
2542   if (FD->isBitField()) {
2543     layoutBitField(FD);
2544     return;
2545   }
2546   LastFieldIsNonZeroWidthBitfield = false;
2547   ElementInfo Info = getAdjustedElementInfo(FD);
2548   Alignment = std::max(Alignment, Info.Alignment);
2549   if (IsUnion) {
2550     placeFieldAtOffset(CharUnits::Zero());
2551     Size = std::max(Size, Info.Size);
2552   } else {
2553     CharUnits FieldOffset;
2554     if (UseExternalLayout) {
2555       FieldOffset =
2556           Context.toCharUnitsFromBits(External.getExternalFieldOffset(FD));
2557       assert(FieldOffset >= Size && "field offset already allocated");
2558     } else {
2559       FieldOffset = Size.RoundUpToAlignment(Info.Alignment);
2560     }
2561     placeFieldAtOffset(FieldOffset);
2562     Size = FieldOffset + Info.Size;
2563   }
2564 }
2565
2566 void MicrosoftRecordLayoutBuilder::layoutBitField(const FieldDecl *FD) {
2567   unsigned Width = FD->getBitWidthValue(Context);
2568   if (Width == 0) {
2569     layoutZeroWidthBitField(FD);
2570     return;
2571   }
2572   ElementInfo Info = getAdjustedElementInfo(FD);
2573   // Clamp the bitfield to a containable size for the sake of being able
2574   // to lay them out.  Sema will throw an error.
2575   if (Width > Context.toBits(Info.Size))
2576     Width = Context.toBits(Info.Size);
2577   // Check to see if this bitfield fits into an existing allocation.  Note:
2578   // MSVC refuses to pack bitfields of formal types with different sizes
2579   // into the same allocation.
2580   if (!IsUnion && LastFieldIsNonZeroWidthBitfield &&
2581       CurrentBitfieldSize == Info.Size && Width <= RemainingBitsInField) {
2582     placeFieldAtBitOffset(Context.toBits(Size) - RemainingBitsInField);
2583     RemainingBitsInField -= Width;
2584     return;
2585   }
2586   LastFieldIsNonZeroWidthBitfield = true;
2587   CurrentBitfieldSize = Info.Size;
2588   if (IsUnion) {
2589     placeFieldAtOffset(CharUnits::Zero());
2590     Size = std::max(Size, Info.Size);
2591     // TODO: Add a Sema warning that MS ignores bitfield alignment in unions.
2592   } else {
2593     // Allocate a new block of memory and place the bitfield in it.
2594     CharUnits FieldOffset = Size.RoundUpToAlignment(Info.Alignment);
2595     placeFieldAtOffset(FieldOffset);
2596     Size = FieldOffset + Info.Size;
2597     Alignment = std::max(Alignment, Info.Alignment);
2598     RemainingBitsInField = Context.toBits(Info.Size) - Width;
2599   }
2600 }
2601
2602 void
2603 MicrosoftRecordLayoutBuilder::layoutZeroWidthBitField(const FieldDecl *FD) {
2604   // Zero-width bitfields are ignored unless they follow a non-zero-width
2605   // bitfield.
2606   if (!LastFieldIsNonZeroWidthBitfield) {
2607     placeFieldAtOffset(IsUnion ? CharUnits::Zero() : Size);
2608     // TODO: Add a Sema warning that MS ignores alignment for zero
2609     // sized bitfields that occur after zero-size bitfields or non-bitfields.
2610     return;
2611   }
2612   LastFieldIsNonZeroWidthBitfield = false;
2613   ElementInfo Info = getAdjustedElementInfo(FD);
2614   if (IsUnion) {
2615     placeFieldAtOffset(CharUnits::Zero());
2616     Size = std::max(Size, Info.Size);
2617     // TODO: Add a Sema warning that MS ignores bitfield alignment in unions.
2618   } else {
2619     // Round up the current record size to the field's alignment boundary.
2620     CharUnits FieldOffset = Size.RoundUpToAlignment(Info.Alignment);
2621     placeFieldAtOffset(FieldOffset);
2622     Size = FieldOffset;
2623     Alignment = std::max(Alignment, Info.Alignment);
2624   }
2625 }
2626
2627 void MicrosoftRecordLayoutBuilder::injectVBPtr(const CXXRecordDecl *RD) {
2628   if (!HasVBPtr || SharedVBPtrBase)
2629     return;
2630   // Inject the VBPointer at the injection site.
2631   CharUnits InjectionSite = VBPtrOffset;
2632   // But before we do, make sure it's properly aligned.
2633   VBPtrOffset = VBPtrOffset.RoundUpToAlignment(PointerInfo.Alignment);
2634   // Shift everything after the vbptr down, unless we're using an external
2635   // layout.
2636   if (UseExternalLayout)
2637     return;
2638   // Determine where the first field should be laid out after the vbptr.
2639   CharUnits FieldStart = VBPtrOffset + PointerInfo.Size;
2640   // Make sure that the amount we push the fields back by is a multiple of the
2641   // alignment.
2642   CharUnits Offset = (FieldStart - InjectionSite).RoundUpToAlignment(
2643       std::max(RequiredAlignment, Alignment));
2644   Size += Offset;
2645   for (uint64_t &FieldOffset : FieldOffsets)
2646     FieldOffset += Context.toBits(Offset);
2647   for (BaseOffsetsMapTy::value_type &Base : Bases)
2648     if (Base.second >= InjectionSite)
2649       Base.second += Offset;
2650 }
2651
2652 void MicrosoftRecordLayoutBuilder::injectVFPtr(const CXXRecordDecl *RD) {
2653   if (!HasOwnVFPtr)
2654     return;
2655   // Make sure that the amount we push the struct back by is a multiple of the
2656   // alignment.
2657   CharUnits Offset = PointerInfo.Size.RoundUpToAlignment(
2658       std::max(RequiredAlignment, Alignment));
2659   // Increase the size of the object and push back all fields, the vbptr and all
2660   // bases by the offset amount.
2661   Size += Offset;
2662   for (uint64_t &FieldOffset : FieldOffsets)
2663     FieldOffset += Context.toBits(Offset);
2664   if (HasVBPtr)
2665     VBPtrOffset += Offset;
2666   for (BaseOffsetsMapTy::value_type &Base : Bases)
2667     Base.second += Offset;
2668 }
2669
2670 void MicrosoftRecordLayoutBuilder::layoutVirtualBases(const CXXRecordDecl *RD) {
2671   if (!HasVBPtr)
2672     return;
2673   // Vtordisps are always 4 bytes (even in 64-bit mode)
2674   CharUnits VtorDispSize = CharUnits::fromQuantity(4);
2675   CharUnits VtorDispAlignment = VtorDispSize;
2676   // vtordisps respect pragma pack.
2677   if (!MaxFieldAlignment.isZero())
2678     VtorDispAlignment = std::min(VtorDispAlignment, MaxFieldAlignment);
2679   // The alignment of the vtordisp is at least the required alignment of the
2680   // entire record.  This requirement may be present to support vtordisp
2681   // injection.
2682   for (const CXXBaseSpecifier &VBase : RD->vbases()) {
2683     const CXXRecordDecl *BaseDecl = VBase.getType()->getAsCXXRecordDecl();
2684     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2685     RequiredAlignment =
2686         std::max(RequiredAlignment, BaseLayout.getRequiredAlignment());
2687   }
2688   VtorDispAlignment = std::max(VtorDispAlignment, RequiredAlignment);
2689   // Compute the vtordisp set.
2690   llvm::SmallPtrSet<const CXXRecordDecl *, 2> HasVtorDispSet;
2691   computeVtorDispSet(HasVtorDispSet, RD);
2692   // Iterate through the virtual bases and lay them out.
2693   const ASTRecordLayout *PreviousBaseLayout = nullptr;
2694   for (const CXXBaseSpecifier &VBase : RD->vbases()) {
2695     const CXXRecordDecl *BaseDecl = VBase.getType()->getAsCXXRecordDecl();
2696     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2697     bool HasVtordisp = HasVtorDispSet.count(BaseDecl) > 0;
2698     // Insert padding between two bases if the left first one is zero sized or
2699     // contains a zero sized subobject and the right is zero sized or one leads
2700     // with a zero sized base.  The padding between virtual bases is 4
2701     // bytes (in both 32 and 64 bits modes) and always involves rounding up to
2702     // the required alignment, we don't know why.
2703     if ((PreviousBaseLayout && PreviousBaseLayout->hasZeroSizedSubObject() &&
2704         BaseLayout.leadsWithZeroSizedBase()) || HasVtordisp) {
2705       Size = Size.RoundUpToAlignment(VtorDispAlignment) + VtorDispSize;
2706       Alignment = std::max(VtorDispAlignment, Alignment);
2707     }
2708     // Insert the virtual base.
2709     ElementInfo Info = getAdjustedElementInfo(BaseLayout);
2710     CharUnits BaseOffset;
2711
2712     // Respect the external AST source base offset, if present.
2713     bool FoundBase = false;
2714     if (UseExternalLayout) {
2715       FoundBase = External.getExternalVBaseOffset(BaseDecl, BaseOffset);
2716       if (FoundBase)
2717         assert(BaseOffset >= Size && "base offset already allocated");
2718     }
2719     if (!FoundBase)
2720       BaseOffset = Size.RoundUpToAlignment(Info.Alignment);
2721
2722     VBases.insert(std::make_pair(BaseDecl,
2723         ASTRecordLayout::VBaseInfo(BaseOffset, HasVtordisp)));
2724     Size = BaseOffset + BaseLayout.getNonVirtualSize();
2725     PreviousBaseLayout = &BaseLayout;
2726   }
2727 }
2728
2729 void MicrosoftRecordLayoutBuilder::finalizeLayout(const RecordDecl *RD) {
2730   // Respect required alignment.  Note that in 32-bit mode Required alignment
2731   // may be 0 and cause size not to be updated.
2732   DataSize = Size;
2733   if (!RequiredAlignment.isZero()) {
2734     Alignment = std::max(Alignment, RequiredAlignment);
2735     auto RoundingAlignment = Alignment;
2736     if (!MaxFieldAlignment.isZero())
2737       RoundingAlignment = std::min(RoundingAlignment, MaxFieldAlignment);
2738     RoundingAlignment = std::max(RoundingAlignment, RequiredAlignment);
2739     Size = Size.RoundUpToAlignment(RoundingAlignment);
2740   }
2741   if (Size.isZero()) {
2742     EndsWithZeroSizedObject = true;
2743     LeadsWithZeroSizedBase = true;
2744     // Zero-sized structures have size equal to their alignment if a
2745     // __declspec(align) came into play.
2746     if (RequiredAlignment >= MinEmptyStructSize)
2747       Size = Alignment;
2748     else
2749       Size = MinEmptyStructSize;
2750   }
2751
2752   if (UseExternalLayout) {
2753     Size = Context.toCharUnitsFromBits(External.Size);
2754     if (External.Align)
2755       Alignment = Context.toCharUnitsFromBits(External.Align);
2756   }
2757 }
2758
2759 // Recursively walks the non-virtual bases of a class and determines if any of
2760 // them are in the bases with overridden methods set.
2761 static bool
2762 RequiresVtordisp(const llvm::SmallPtrSetImpl<const CXXRecordDecl *> &
2763                      BasesWithOverriddenMethods,
2764                  const CXXRecordDecl *RD) {
2765   if (BasesWithOverriddenMethods.count(RD))
2766     return true;
2767   // If any of a virtual bases non-virtual bases (recursively) requires a
2768   // vtordisp than so does this virtual base.
2769   for (const CXXBaseSpecifier &Base : RD->bases())
2770     if (!Base.isVirtual() &&
2771         RequiresVtordisp(BasesWithOverriddenMethods,
2772                          Base.getType()->getAsCXXRecordDecl()))
2773       return true;
2774   return false;
2775 }
2776
2777 void MicrosoftRecordLayoutBuilder::computeVtorDispSet(
2778     llvm::SmallPtrSetImpl<const CXXRecordDecl *> &HasVtordispSet,
2779     const CXXRecordDecl *RD) const {
2780   // /vd2 or #pragma vtordisp(2): Always use vtordisps for virtual bases with
2781   // vftables.
2782   if (RD->getMSVtorDispMode() == MSVtorDispAttr::ForVFTable) {
2783     for (const CXXBaseSpecifier &Base : RD->vbases()) {
2784       const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2785       const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
2786       if (Layout.hasExtendableVFPtr())
2787         HasVtordispSet.insert(BaseDecl);
2788     }
2789     return;
2790   }
2791
2792   // If any of our bases need a vtordisp for this type, so do we.  Check our
2793   // direct bases for vtordisp requirements.
2794   for (const CXXBaseSpecifier &Base : RD->bases()) {
2795     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2796     const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
2797     for (const auto &bi : Layout.getVBaseOffsetsMap())
2798       if (bi.second.hasVtorDisp())
2799         HasVtordispSet.insert(bi.first);
2800   }
2801   // We don't introduce any additional vtordisps if either:
2802   // * A user declared constructor or destructor aren't declared.
2803   // * #pragma vtordisp(0) or the /vd0 flag are in use.
2804   if ((!RD->hasUserDeclaredConstructor() && !RD->hasUserDeclaredDestructor()) ||
2805       RD->getMSVtorDispMode() == MSVtorDispAttr::Never)
2806     return;
2807   // /vd1 or #pragma vtordisp(1): Try to guess based on whether we think it's
2808   // possible for a partially constructed object with virtual base overrides to
2809   // escape a non-trivial constructor.
2810   assert(RD->getMSVtorDispMode() == MSVtorDispAttr::ForVBaseOverride);
2811   // Compute a set of base classes which define methods we override.  A virtual
2812   // base in this set will require a vtordisp.  A virtual base that transitively
2813   // contains one of these bases as a non-virtual base will also require a
2814   // vtordisp.
2815   llvm::SmallPtrSet<const CXXMethodDecl *, 8> Work;
2816   llvm::SmallPtrSet<const CXXRecordDecl *, 2> BasesWithOverriddenMethods;
2817   // Seed the working set with our non-destructor, non-pure virtual methods.
2818   for (const CXXMethodDecl *MD : RD->methods())
2819     if (MD->isVirtual() && !isa<CXXDestructorDecl>(MD) && !MD->isPure())
2820       Work.insert(MD);
2821   while (!Work.empty()) {
2822     const CXXMethodDecl *MD = *Work.begin();
2823     CXXMethodDecl::method_iterator i = MD->begin_overridden_methods(),
2824                                    e = MD->end_overridden_methods();
2825     // If a virtual method has no-overrides it lives in its parent's vtable.
2826     if (i == e)
2827       BasesWithOverriddenMethods.insert(MD->getParent());
2828     else
2829       Work.insert(i, e);
2830     // We've finished processing this element, remove it from the working set.
2831     Work.erase(MD);
2832   }
2833   // For each of our virtual bases, check if it is in the set of overridden
2834   // bases or if it transitively contains a non-virtual base that is.
2835   for (const CXXBaseSpecifier &Base : RD->vbases()) {
2836     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2837     if (!HasVtordispSet.count(BaseDecl) &&
2838         RequiresVtordisp(BasesWithOverriddenMethods, BaseDecl))
2839       HasVtordispSet.insert(BaseDecl);
2840   }
2841 }
2842
2843 /// \brief Get or compute information about the layout of the specified record
2844 /// (struct/union/class), which indicates its size and field position
2845 /// information.
2846 const ASTRecordLayout *
2847 ASTContext::BuildMicrosoftASTRecordLayout(const RecordDecl *D) const {
2848   MicrosoftRecordLayoutBuilder Builder(*this);
2849   if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
2850     Builder.cxxLayout(RD);
2851     return new (*this) ASTRecordLayout(
2852         *this, Builder.Size, Builder.Alignment, Builder.RequiredAlignment,
2853         Builder.HasOwnVFPtr,
2854         Builder.HasOwnVFPtr || Builder.PrimaryBase,
2855         Builder.VBPtrOffset, Builder.NonVirtualSize, Builder.FieldOffsets.data(),
2856         Builder.FieldOffsets.size(), Builder.NonVirtualSize,
2857         Builder.Alignment, CharUnits::Zero(), Builder.PrimaryBase,
2858         false, Builder.SharedVBPtrBase,
2859         Builder.EndsWithZeroSizedObject, Builder.LeadsWithZeroSizedBase,
2860         Builder.Bases, Builder.VBases);
2861   } else {
2862     Builder.layout(D);
2863     return new (*this) ASTRecordLayout(
2864         *this, Builder.Size, Builder.Alignment, Builder.RequiredAlignment,
2865         Builder.Size, Builder.FieldOffsets.data(), Builder.FieldOffsets.size());
2866   }
2867 }
2868
2869 /// getASTRecordLayout - Get or compute information about the layout of the
2870 /// specified record (struct/union/class), which indicates its size and field
2871 /// position information.
2872 const ASTRecordLayout &
2873 ASTContext::getASTRecordLayout(const RecordDecl *D) const {
2874   // These asserts test different things.  A record has a definition
2875   // as soon as we begin to parse the definition.  That definition is
2876   // not a complete definition (which is what isDefinition() tests)
2877   // until we *finish* parsing the definition.
2878
2879   if (D->hasExternalLexicalStorage() && !D->getDefinition())
2880     getExternalSource()->CompleteType(const_cast<RecordDecl*>(D));
2881
2882   D = D->getDefinition();
2883   assert(D && "Cannot get layout of forward declarations!");
2884   assert(!D->isInvalidDecl() && "Cannot get layout of invalid decl!");
2885   assert(D->isCompleteDefinition() && "Cannot layout type before complete!");
2886
2887   // Look up this layout, if already laid out, return what we have.
2888   // Note that we can't save a reference to the entry because this function
2889   // is recursive.
2890   const ASTRecordLayout *Entry = ASTRecordLayouts[D];
2891   if (Entry) return *Entry;
2892
2893   const ASTRecordLayout *NewEntry = nullptr;
2894
2895   if (isMsLayout(D)) {
2896     NewEntry = BuildMicrosoftASTRecordLayout(D);
2897   } else if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
2898     EmptySubobjectMap EmptySubobjects(*this, RD);
2899     RecordLayoutBuilder Builder(*this, &EmptySubobjects);
2900     Builder.Layout(RD);
2901
2902     // In certain situations, we are allowed to lay out objects in the
2903     // tail-padding of base classes.  This is ABI-dependent.
2904     // FIXME: this should be stored in the record layout.
2905     bool skipTailPadding =
2906       mustSkipTailPadding(getTargetInfo().getCXXABI(), cast<CXXRecordDecl>(D));
2907
2908     // FIXME: This should be done in FinalizeLayout.
2909     CharUnits DataSize =
2910       skipTailPadding ? Builder.getSize() : Builder.getDataSize();
2911     CharUnits NonVirtualSize =
2912       skipTailPadding ? DataSize : Builder.NonVirtualSize;
2913     NewEntry =
2914       new (*this) ASTRecordLayout(*this, Builder.getSize(),
2915                                   Builder.Alignment,
2916                                   /*RequiredAlignment : used by MS-ABI)*/
2917                                   Builder.Alignment,
2918                                   Builder.HasOwnVFPtr,
2919                                   RD->isDynamicClass(),
2920                                   CharUnits::fromQuantity(-1),
2921                                   DataSize,
2922                                   Builder.FieldOffsets.data(),
2923                                   Builder.FieldOffsets.size(),
2924                                   NonVirtualSize,
2925                                   Builder.NonVirtualAlignment,
2926                                   EmptySubobjects.SizeOfLargestEmptySubobject,
2927                                   Builder.PrimaryBase,
2928                                   Builder.PrimaryBaseIsVirtual,
2929                                   nullptr, false, false,
2930                                   Builder.Bases, Builder.VBases);
2931   } else {
2932     RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/nullptr);
2933     Builder.Layout(D);
2934
2935     NewEntry =
2936       new (*this) ASTRecordLayout(*this, Builder.getSize(),
2937                                   Builder.Alignment,
2938                                   /*RequiredAlignment : used by MS-ABI)*/
2939                                   Builder.Alignment,
2940                                   Builder.getSize(),
2941                                   Builder.FieldOffsets.data(),
2942                                   Builder.FieldOffsets.size());
2943   }
2944
2945   ASTRecordLayouts[D] = NewEntry;
2946
2947   if (getLangOpts().DumpRecordLayouts) {
2948     llvm::outs() << "\n*** Dumping AST Record Layout\n";
2949     DumpRecordLayout(D, llvm::outs(), getLangOpts().DumpRecordLayoutsSimple);
2950   }
2951
2952   return *NewEntry;
2953 }
2954
2955 const CXXMethodDecl *ASTContext::getCurrentKeyFunction(const CXXRecordDecl *RD) {
2956   if (!getTargetInfo().getCXXABI().hasKeyFunctions())
2957     return nullptr;
2958
2959   assert(RD->getDefinition() && "Cannot get key function for forward decl!");
2960   RD = cast<CXXRecordDecl>(RD->getDefinition());
2961
2962   // Beware:
2963   //  1) computing the key function might trigger deserialization, which might
2964   //     invalidate iterators into KeyFunctions
2965   //  2) 'get' on the LazyDeclPtr might also trigger deserialization and
2966   //     invalidate the LazyDeclPtr within the map itself
2967   LazyDeclPtr Entry = KeyFunctions[RD];
2968   const Decl *Result =
2969       Entry ? Entry.get(getExternalSource()) : computeKeyFunction(*this, RD);
2970
2971   // Store it back if it changed.
2972   if (Entry.isOffset() || Entry.isValid() != bool(Result))
2973     KeyFunctions[RD] = const_cast<Decl*>(Result);
2974
2975   return cast_or_null<CXXMethodDecl>(Result);
2976 }
2977
2978 void ASTContext::setNonKeyFunction(const CXXMethodDecl *Method) {
2979   assert(Method == Method->getFirstDecl() &&
2980          "not working with method declaration from class definition");
2981
2982   // Look up the cache entry.  Since we're working with the first
2983   // declaration, its parent must be the class definition, which is
2984   // the correct key for the KeyFunctions hash.
2985   const auto &Map = KeyFunctions;
2986   auto I = Map.find(Method->getParent());
2987
2988   // If it's not cached, there's nothing to do.
2989   if (I == Map.end()) return;
2990
2991   // If it is cached, check whether it's the target method, and if so,
2992   // remove it from the cache. Note, the call to 'get' might invalidate
2993   // the iterator and the LazyDeclPtr object within the map.
2994   LazyDeclPtr Ptr = I->second;
2995   if (Ptr.get(getExternalSource()) == Method) {
2996     // FIXME: remember that we did this for module / chained PCH state?
2997     KeyFunctions.erase(Method->getParent());
2998   }
2999 }
3000
3001 static uint64_t getFieldOffset(const ASTContext &C, const FieldDecl *FD) {
3002   const ASTRecordLayout &Layout = C.getASTRecordLayout(FD->getParent());
3003   return Layout.getFieldOffset(FD->getFieldIndex());
3004 }
3005
3006 uint64_t ASTContext::getFieldOffset(const ValueDecl *VD) const {
3007   uint64_t OffsetInBits;
3008   if (const FieldDecl *FD = dyn_cast<FieldDecl>(VD)) {
3009     OffsetInBits = ::getFieldOffset(*this, FD);
3010   } else {
3011     const IndirectFieldDecl *IFD = cast<IndirectFieldDecl>(VD);
3012
3013     OffsetInBits = 0;
3014     for (const NamedDecl *ND : IFD->chain())
3015       OffsetInBits += ::getFieldOffset(*this, cast<FieldDecl>(ND));
3016   }
3017
3018   return OffsetInBits;
3019 }
3020
3021 /// getObjCLayout - Get or compute information about the layout of the
3022 /// given interface.
3023 ///
3024 /// \param Impl - If given, also include the layout of the interface's
3025 /// implementation. This may differ by including synthesized ivars.
3026 const ASTRecordLayout &
3027 ASTContext::getObjCLayout(const ObjCInterfaceDecl *D,
3028                           const ObjCImplementationDecl *Impl) const {
3029   // Retrieve the definition
3030   if (D->hasExternalLexicalStorage() && !D->getDefinition())
3031     getExternalSource()->CompleteType(const_cast<ObjCInterfaceDecl*>(D));
3032   D = D->getDefinition();
3033   assert(D && D->isThisDeclarationADefinition() && "Invalid interface decl!");
3034
3035   // Look up this layout, if already laid out, return what we have.
3036   const ObjCContainerDecl *Key =
3037     Impl ? (const ObjCContainerDecl*) Impl : (const ObjCContainerDecl*) D;
3038   if (const ASTRecordLayout *Entry = ObjCLayouts[Key])
3039     return *Entry;
3040
3041   // Add in synthesized ivar count if laying out an implementation.
3042   if (Impl) {
3043     unsigned SynthCount = CountNonClassIvars(D);
3044     // If there aren't any sythesized ivars then reuse the interface
3045     // entry. Note we can't cache this because we simply free all
3046     // entries later; however we shouldn't look up implementations
3047     // frequently.
3048     if (SynthCount == 0)
3049       return getObjCLayout(D, nullptr);
3050   }
3051
3052   RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/nullptr);
3053   Builder.Layout(D);
3054
3055   const ASTRecordLayout *NewEntry =
3056     new (*this) ASTRecordLayout(*this, Builder.getSize(),
3057                                 Builder.Alignment,
3058                                 /*RequiredAlignment : used by MS-ABI)*/
3059                                 Builder.Alignment,
3060                                 Builder.getDataSize(),
3061                                 Builder.FieldOffsets.data(),
3062                                 Builder.FieldOffsets.size());
3063
3064   ObjCLayouts[Key] = NewEntry;
3065
3066   return *NewEntry;
3067 }
3068
3069 static void PrintOffset(raw_ostream &OS,
3070                         CharUnits Offset, unsigned IndentLevel) {
3071   OS << llvm::format("%4" PRId64 " | ", (int64_t)Offset.getQuantity());
3072   OS.indent(IndentLevel * 2);
3073 }
3074
3075 static void PrintIndentNoOffset(raw_ostream &OS, unsigned IndentLevel) {
3076   OS << "     | ";
3077   OS.indent(IndentLevel * 2);
3078 }
3079
3080 static void DumpCXXRecordLayout(raw_ostream &OS,
3081                                 const CXXRecordDecl *RD, const ASTContext &C,
3082                                 CharUnits Offset,
3083                                 unsigned IndentLevel,
3084                                 const char* Description,
3085                                 bool IncludeVirtualBases) {
3086   const ASTRecordLayout &Layout = C.getASTRecordLayout(RD);
3087
3088   PrintOffset(OS, Offset, IndentLevel);
3089   OS << C.getTypeDeclType(const_cast<CXXRecordDecl *>(RD)).getAsString();
3090   if (Description)
3091     OS << ' ' << Description;
3092   if (RD->isEmpty())
3093     OS << " (empty)";
3094   OS << '\n';
3095
3096   IndentLevel++;
3097
3098   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
3099   bool HasOwnVFPtr = Layout.hasOwnVFPtr();
3100   bool HasOwnVBPtr = Layout.hasOwnVBPtr();
3101
3102   // Vtable pointer.
3103   if (RD->isDynamicClass() && !PrimaryBase && !isMsLayout(RD)) {
3104     PrintOffset(OS, Offset, IndentLevel);
3105     OS << '(' << *RD << " vtable pointer)\n";
3106   } else if (HasOwnVFPtr) {
3107     PrintOffset(OS, Offset, IndentLevel);
3108     // vfptr (for Microsoft C++ ABI)
3109     OS << '(' << *RD << " vftable pointer)\n";
3110   }
3111
3112   // Collect nvbases.
3113   SmallVector<const CXXRecordDecl *, 4> Bases;
3114   for (const CXXBaseSpecifier &Base : RD->bases()) {
3115     assert(!Base.getType()->isDependentType() &&
3116            "Cannot layout class with dependent bases.");
3117     if (!Base.isVirtual())
3118       Bases.push_back(Base.getType()->getAsCXXRecordDecl());
3119   }
3120
3121   // Sort nvbases by offset.
3122   std::stable_sort(Bases.begin(), Bases.end(),
3123                    [&](const CXXRecordDecl *L, const CXXRecordDecl *R) {
3124     return Layout.getBaseClassOffset(L) < Layout.getBaseClassOffset(R);
3125   });
3126
3127   // Dump (non-virtual) bases
3128   for (const CXXRecordDecl *Base : Bases) {
3129     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base);
3130     DumpCXXRecordLayout(OS, Base, C, BaseOffset, IndentLevel,
3131                         Base == PrimaryBase ? "(primary base)" : "(base)",
3132                         /*IncludeVirtualBases=*/false);
3133   }
3134
3135   // vbptr (for Microsoft C++ ABI)
3136   if (HasOwnVBPtr) {
3137     PrintOffset(OS, Offset + Layout.getVBPtrOffset(), IndentLevel);
3138     OS << '(' << *RD << " vbtable pointer)\n";
3139   }
3140
3141   // Dump fields.
3142   uint64_t FieldNo = 0;
3143   for (CXXRecordDecl::field_iterator I = RD->field_begin(),
3144          E = RD->field_end(); I != E; ++I, ++FieldNo) {
3145     const FieldDecl &Field = **I;
3146     CharUnits FieldOffset = Offset +
3147       C.toCharUnitsFromBits(Layout.getFieldOffset(FieldNo));
3148
3149     if (const CXXRecordDecl *D = Field.getType()->getAsCXXRecordDecl()) {
3150       DumpCXXRecordLayout(OS, D, C, FieldOffset, IndentLevel,
3151                           Field.getName().data(),
3152                           /*IncludeVirtualBases=*/true);
3153       continue;
3154     }
3155
3156     PrintOffset(OS, FieldOffset, IndentLevel);
3157     OS << Field.getType().getAsString() << ' ' << Field << '\n';
3158   }
3159
3160   if (!IncludeVirtualBases)
3161     return;
3162
3163   // Dump virtual bases.
3164   const ASTRecordLayout::VBaseOffsetsMapTy &vtordisps =
3165     Layout.getVBaseOffsetsMap();
3166   for (const CXXBaseSpecifier &Base : RD->vbases()) {
3167     assert(Base.isVirtual() && "Found non-virtual class!");
3168     const CXXRecordDecl *VBase = Base.getType()->getAsCXXRecordDecl();
3169
3170     CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBase);
3171
3172     if (vtordisps.find(VBase)->second.hasVtorDisp()) {
3173       PrintOffset(OS, VBaseOffset - CharUnits::fromQuantity(4), IndentLevel);
3174       OS << "(vtordisp for vbase " << *VBase << ")\n";
3175     }
3176
3177     DumpCXXRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel,
3178                         VBase == PrimaryBase ?
3179                         "(primary virtual base)" : "(virtual base)",
3180                         /*IncludeVirtualBases=*/false);
3181   }
3182
3183   PrintIndentNoOffset(OS, IndentLevel - 1);
3184   OS << "[sizeof=" << Layout.getSize().getQuantity();
3185   if (!isMsLayout(RD))
3186     OS << ", dsize=" << Layout.getDataSize().getQuantity();
3187   OS << ", align=" << Layout.getAlignment().getQuantity() << '\n';
3188
3189   PrintIndentNoOffset(OS, IndentLevel - 1);
3190   OS << " nvsize=" << Layout.getNonVirtualSize().getQuantity();
3191   OS << ", nvalign=" << Layout.getNonVirtualAlignment().getQuantity() << "]\n";
3192 }
3193
3194 void ASTContext::DumpRecordLayout(const RecordDecl *RD,
3195                                   raw_ostream &OS,
3196                                   bool Simple) const {
3197   const ASTRecordLayout &Info = getASTRecordLayout(RD);
3198
3199   if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD))
3200     if (!Simple)
3201       return DumpCXXRecordLayout(OS, CXXRD, *this, CharUnits(), 0, nullptr,
3202                                  /*IncludeVirtualBases=*/true);
3203
3204   OS << "Type: " << getTypeDeclType(RD).getAsString() << "\n";
3205   if (!Simple) {
3206     OS << "Record: ";
3207     RD->dump();
3208   }
3209   OS << "\nLayout: ";
3210   OS << "<ASTRecordLayout\n";
3211   OS << "  Size:" << toBits(Info.getSize()) << "\n";
3212   if (!isMsLayout(RD))
3213     OS << "  DataSize:" << toBits(Info.getDataSize()) << "\n";
3214   OS << "  Alignment:" << toBits(Info.getAlignment()) << "\n";
3215   OS << "  FieldOffsets: [";
3216   for (unsigned i = 0, e = Info.getFieldCount(); i != e; ++i) {
3217     if (i) OS << ", ";
3218     OS << Info.getFieldOffset(i);
3219   }
3220   OS << "]>\n";
3221 }