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/Attr.h"
  11 #include "clang/AST/CXXInheritance.h"
  12 #include "clang/AST/Decl.h"
  13 #include "clang/AST/DeclCXX.h"
  14 #include "clang/AST/DeclObjC.h"
  15 #include "clang/AST/Expr.h"
  16 #include "clang/AST/RecordLayout.h"
  17 #include "clang/Basic/TargetInfo.h"
  18 #include "clang/Sema/SemaDiagnostic.h"
  19 #include "llvm/Support/Format.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/Support/MathExtras.h"
  22 #include "llvm/Support/CrashRecoveryContext.h"
  23
  24 using namespace clang;
  25
  26 namespace {
  27
  28 /// BaseSubobjectInfo - Represents a single base subobject in a complete class.
  29 /// For a class hierarchy like
  30 ///
  31 /// class A { };
  32 /// class B : A { };
  33 /// class C : A, B { };
  34 ///
  35 /// The BaseSubobjectInfo graph for C will have three BaseSubobjectInfo
  36 /// instances, one for B and two for A.
  37 ///
  38 /// If a base is virtual, it will only have one BaseSubobjectInfo allocated.
  39 struct BaseSubobjectInfo {
  40   /// Class - The class for this base info.
  41   const CXXRecordDecl *Class;
  42
  43   /// IsVirtual - Whether the BaseInfo represents a virtual base or not.
  44   bool IsVirtual;
  45
  46   /// Bases - Information about the base subobjects.
  47   llvm::SmallVector<BaseSubobjectInfo*, 4> Bases;
  48
  49   /// PrimaryVirtualBaseInfo - Holds the base info for the primary virtual base
  50   /// of this base info (if one exists).
  51   BaseSubobjectInfo *PrimaryVirtualBaseInfo;
  52
  53   // FIXME: Document.
  54   const BaseSubobjectInfo *Derived;
  55 };
  56
  57 /// EmptySubobjectMap - Keeps track of which empty subobjects exist at different
  58 /// offsets while laying out a C++ class.
  59 class EmptySubobjectMap {
  60   const ASTContext &Context;
  61   uint64_t CharWidth;
  62
  63   /// Class - The class whose empty entries we're keeping track of.
  64   const CXXRecordDecl *Class;
  65
  66   /// EmptyClassOffsets - A map from offsets to empty record decls.
  67   typedef llvm::SmallVector<const CXXRecordDecl *, 1> ClassVectorTy;
  68   typedef llvm::DenseMap<CharUnits, ClassVectorTy> EmptyClassOffsetsMapTy;
  69   EmptyClassOffsetsMapTy EmptyClassOffsets;
  70
  71   /// MaxEmptyClassOffset - The highest offset known to contain an empty
  72   /// base subobject.
  73   CharUnits MaxEmptyClassOffset;
  74
  75   /// ComputeEmptySubobjectSizes - Compute the size of the largest base or
  76   /// member subobject that is empty.
  77   void ComputeEmptySubobjectSizes();
  78
  79   void AddSubobjectAtOffset(const CXXRecordDecl *RD, CharUnits Offset);
  80
  81   void UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
  82                                  CharUnits Offset, bool PlacingEmptyBase);
  83
  84   void UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD,
  85                                   const CXXRecordDecl *Class,
  86                                   CharUnits Offset);
  87   void UpdateEmptyFieldSubobjects(const FieldDecl *FD, CharUnits Offset);
  88
  89   /// AnyEmptySubobjectsBeyondOffset - Returns whether there are any empty
  90   /// subobjects beyond the given offset.
  91   bool AnyEmptySubobjectsBeyondOffset(CharUnits Offset) const {
  92     return Offset <= MaxEmptyClassOffset;
  93   }
  94
  95   CharUnits
  96   getFieldOffset(const ASTRecordLayout &Layout, unsigned FieldNo) const {
  97     uint64_t FieldOffset = Layout.getFieldOffset(FieldNo);
  98     assert(FieldOffset % CharWidth == 0 &&
  99            "Field offset not at char boundary!");
 100
 101     return Context.toCharUnitsFromBits(FieldOffset);
 102   }
 103
 104 protected:
 105   bool CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
 106                                  CharUnits Offset) const;
 107
 108   bool CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
 109                                      CharUnits Offset);
 110
 111   bool CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
 112                                       const CXXRecordDecl *Class,
 113                                       CharUnits Offset) const;
 114   bool CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
 115                                       CharUnits Offset) const;
 116
 117 public:
 118   /// This holds the size of the largest empty subobject (either a base
 119   /// or a member). Will be zero if the record being built doesn't contain
 120   /// any empty classes.
 121   CharUnits SizeOfLargestEmptySubobject;
 122
 123   EmptySubobjectMap(const ASTContext &Context, const CXXRecordDecl *Class)
 124   : Context(Context), CharWidth(Context.getCharWidth()), Class(Class) {
 125       ComputeEmptySubobjectSizes();
 126   }
 127
 128   /// CanPlaceBaseAtOffset - Return whether the given base class can be placed
 129   /// at the given offset.
 130   /// Returns false if placing the record will result in two components
 131   /// (direct or indirect) of the same type having the same offset.
 132   bool CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
 133                             CharUnits Offset);
 134
 135   /// CanPlaceFieldAtOffset - Return whether a field can be placed at the given
 136   /// offset.
 137   bool CanPlaceFieldAtOffset(const FieldDecl *FD, CharUnits Offset);
 138 };
 139
 140 void EmptySubobjectMap::ComputeEmptySubobjectSizes() {
 141   // Check the bases.
 142   for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
 143        E = Class->bases_end(); I != E; ++I) {
 144     const CXXRecordDecl *BaseDecl =
 145       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 146
 147     CharUnits EmptySize;
 148     const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
 149     if (BaseDecl->isEmpty()) {
 150       // If the class decl is empty, get its size.
 151       EmptySize = Layout.getSize();
 152     } else {
 153       // Otherwise, we get the largest empty subobject for the decl.
 154       EmptySize = Layout.getSizeOfLargestEmptySubobject();
 155     }
 156
 157     if (EmptySize > SizeOfLargestEmptySubobject)
 158       SizeOfLargestEmptySubobject = EmptySize;
 159   }
 160
 161   // Check the fields.
 162   for (CXXRecordDecl::field_iterator I = Class->field_begin(),
 163        E = Class->field_end(); I != E; ++I) {
 164     const FieldDecl *FD = *I;
 165
 166     const RecordType *RT =
 167       Context.getBaseElementType(FD->getType())->getAs<RecordType>();
 168
 169     // We only care about record types.
 170     if (!RT)
 171       continue;
 172
 173     CharUnits EmptySize;
 174     const CXXRecordDecl *MemberDecl = cast<CXXRecordDecl>(RT->getDecl());
 175     const ASTRecordLayout &Layout = Context.getASTRecordLayout(MemberDecl);
 176     if (MemberDecl->isEmpty()) {
 177       // If the class decl is empty, get its size.
 178       EmptySize = Layout.getSize();
 179     } else {
 180       // Otherwise, we get the largest empty subobject for the decl.
 181       EmptySize = Layout.getSizeOfLargestEmptySubobject();
 182     }
 183
 184     if (EmptySize > SizeOfLargestEmptySubobject)
 185       SizeOfLargestEmptySubobject = EmptySize;
 186   }
 187 }
 188
 189 bool
 190 EmptySubobjectMap::CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
 191                                              CharUnits Offset) const {
 192   // We only need to check empty bases.
 193   if (!RD->isEmpty())
 194     return true;
 195
 196   EmptyClassOffsetsMapTy::const_iterator I = EmptyClassOffsets.find(Offset);
 197   if (I == EmptyClassOffsets.end())
 198     return true;
 199
 200   const ClassVectorTy& Classes = I->second;
 201   if (std::find(Classes.begin(), Classes.end(), RD) == Classes.end())
 202     return true;
 203
 204   // There is already an empty class of the same type at this offset.
 205   return false;
 206 }
 207
 208 void EmptySubobjectMap::AddSubobjectAtOffset(const CXXRecordDecl *RD,
 209                                              CharUnits Offset) {
 210   // We only care about empty bases.
 211   if (!RD->isEmpty())
 212     return;
 213
 214   // If we have empty structures inside an union, we can assign both
 215   // the same offset. Just avoid pushing them twice in the list.
 216   ClassVectorTy& Classes = EmptyClassOffsets[Offset];
 217   if (std::find(Classes.begin(), Classes.end(), RD) != Classes.end())
 218     return;
 219
 220   Classes.push_back(RD);
 221
 222   // Update the empty class offset.
 223   if (Offset > MaxEmptyClassOffset)
 224     MaxEmptyClassOffset = Offset;
 225 }
 226
 227 bool
 228 EmptySubobjectMap::CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
 229                                                  CharUnits Offset) {
 230   // We don't have to keep looking past the maximum offset that's known to
 231   // contain an empty class.
 232   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 233     return true;
 234
 235   if (!CanPlaceSubobjectAtOffset(Info->Class, Offset))
 236     return false;
 237
 238   // Traverse all non-virtual bases.
 239   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
 240   for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) {
 241     BaseSubobjectInfo* Base = Info->Bases[I];
 242     if (Base->IsVirtual)
 243       continue;
 244
 245     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
 246
 247     if (!CanPlaceBaseSubobjectAtOffset(Base, BaseOffset))
 248       return false;
 249   }
 250
 251   if (Info->PrimaryVirtualBaseInfo) {
 252     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
 253
 254     if (Info == PrimaryVirtualBaseInfo->Derived) {
 255       if (!CanPlaceBaseSubobjectAtOffset(PrimaryVirtualBaseInfo, Offset))
 256         return false;
 257     }
 258   }
 259
 260   // Traverse all member variables.
 261   unsigned FieldNo = 0;
 262   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
 263        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
 264     const FieldDecl *FD = *I;
 265     if (FD->isBitField())
 266       continue;
 267
 268     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 269     if (!CanPlaceFieldSubobjectAtOffset(FD, FieldOffset))
 270       return false;
 271   }
 272
 273   return true;
 274 }
 275
 276 void EmptySubobjectMap::UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
 277                                                   CharUnits Offset,
 278                                                   bool PlacingEmptyBase) {
 279   if (!PlacingEmptyBase && Offset >= SizeOfLargestEmptySubobject) {
 280     // We know that the only empty subobjects that can conflict with empty
 281     // subobject of non-empty bases, are empty bases that can be placed at
 282     // offset zero. Because of this, we only need to keep track of empty base
 283     // subobjects with offsets less than the size of the largest empty
 284     // subobject for our class.
 285     return;
 286   }
 287
 288   AddSubobjectAtOffset(Info->Class, Offset);
 289
 290   // Traverse all non-virtual bases.
 291   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
 292   for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) {
 293     BaseSubobjectInfo* Base = Info->Bases[I];
 294     if (Base->IsVirtual)
 295       continue;
 296
 297     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
 298     UpdateEmptyBaseSubobjects(Base, BaseOffset, PlacingEmptyBase);
 299   }
 300
 301   if (Info->PrimaryVirtualBaseInfo) {
 302     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
 303
 304     if (Info == PrimaryVirtualBaseInfo->Derived)
 305       UpdateEmptyBaseSubobjects(PrimaryVirtualBaseInfo, Offset,
 306                                 PlacingEmptyBase);
 307   }
 308
 309   // Traverse all member variables.
 310   unsigned FieldNo = 0;
 311   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
 312        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
 313     const FieldDecl *FD = *I;
 314     if (FD->isBitField())
 315       continue;
 316
 317     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 318     UpdateEmptyFieldSubobjects(FD, FieldOffset);
 319   }
 320 }
 321
 322 bool EmptySubobjectMap::CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
 323                                              CharUnits Offset) {
 324   // If we know this class doesn't have any empty subobjects we don't need to
 325   // bother checking.
 326   if (SizeOfLargestEmptySubobject.isZero())
 327     return true;
 328
 329   if (!CanPlaceBaseSubobjectAtOffset(Info, Offset))
 330     return false;
 331
 332   // We are able to place the base at this offset. Make sure to update the
 333   // empty base subobject map.
 334   UpdateEmptyBaseSubobjects(Info, Offset, Info->Class->isEmpty());
 335   return true;
 336 }
 337
 338 bool
 339 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
 340                                                   const CXXRecordDecl *Class,
 341                                                   CharUnits Offset) const {
 342   // We don't have to keep looking past the maximum offset that's known to
 343   // contain an empty class.
 344   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 345     return true;
 346
 347   if (!CanPlaceSubobjectAtOffset(RD, Offset))
 348     return false;
 349
 350   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 351
 352   // Traverse all non-virtual bases.
 353   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 354        E = RD->bases_end(); I != E; ++I) {
 355     if (I->isVirtual())
 356       continue;
 357
 358     const CXXRecordDecl *BaseDecl =
 359       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 360
 361     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
 362     if (!CanPlaceFieldSubobjectAtOffset(BaseDecl, Class, BaseOffset))
 363       return false;
 364   }
 365
 366   if (RD == Class) {
 367     // This is the most derived class, traverse virtual bases as well.
 368     for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
 369          E = RD->vbases_end(); I != E; ++I) {
 370       const CXXRecordDecl *VBaseDecl =
 371         cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 372
 373       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
 374       if (!CanPlaceFieldSubobjectAtOffset(VBaseDecl, Class, VBaseOffset))
 375         return false;
 376     }
 377   }
 378
 379   // Traverse all member variables.
 380   unsigned FieldNo = 0;
 381   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 382        I != E; ++I, ++FieldNo) {
 383     const FieldDecl *FD = *I;
 384     if (FD->isBitField())
 385       continue;
 386
 387     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 388
 389     if (!CanPlaceFieldSubobjectAtOffset(FD, FieldOffset))
 390       return false;
 391   }
 392
 393   return true;
 394 }
 395
 396 bool
 397 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
 398                                                   CharUnits Offset) const {
 399   // We don't have to keep looking past the maximum offset that's known to
 400   // contain an empty class.
 401   if (!AnyEmptySubobjectsBeyondOffset(Offset))
 402     return true;
 403
 404   QualType T = FD->getType();
 405   if (const RecordType *RT = T->getAs<RecordType>()) {
 406     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 407     return CanPlaceFieldSubobjectAtOffset(RD, RD, Offset);
 408   }
 409
 410   // If we have an array type we need to look at every element.
 411   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
 412     QualType ElemTy = Context.getBaseElementType(AT);
 413     const RecordType *RT = ElemTy->getAs<RecordType>();
 414     if (!RT)
 415       return true;
 416
 417     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 418     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 419
 420     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
 421     CharUnits ElementOffset = Offset;
 422     for (uint64_t I = 0; I != NumElements; ++I) {
 423       // We don't have to keep looking past the maximum offset that's known to
 424       // contain an empty class.
 425       if (!AnyEmptySubobjectsBeyondOffset(ElementOffset))
 426         return true;
 427
 428       if (!CanPlaceFieldSubobjectAtOffset(RD, RD, ElementOffset))
 429         return false;
 430
 431       ElementOffset += Layout.getSize();
 432     }
 433   }
 434
 435   return true;
 436 }
 437
 438 bool
 439 EmptySubobjectMap::CanPlaceFieldAtOffset(const FieldDecl *FD,
 440                                          CharUnits Offset) {
 441   if (!CanPlaceFieldSubobjectAtOffset(FD, Offset))
 442     return false;
 443
 444   // We are able to place the member variable at this offset.
 445   // Make sure to update the empty base subobject map.
 446   UpdateEmptyFieldSubobjects(FD, Offset);
 447   return true;
 448 }
 449
 450 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD,
 451                                                    const CXXRecordDecl *Class,
 452                                                    CharUnits Offset) {
 453   // We know that the only empty subobjects that can conflict with empty
 454   // field subobjects are subobjects of empty bases that can be placed at offset
 455   // zero. Because of this, we only need to keep track of empty field
 456   // subobjects with offsets less than the size of the largest empty
 457   // subobject for our class.
 458   if (Offset >= SizeOfLargestEmptySubobject)
 459     return;
 460
 461   AddSubobjectAtOffset(RD, Offset);
 462
 463   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 464
 465   // Traverse all non-virtual bases.
 466   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 467        E = RD->bases_end(); I != E; ++I) {
 468     if (I->isVirtual())
 469       continue;
 470
 471     const CXXRecordDecl *BaseDecl =
 472       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 473
 474     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
 475     UpdateEmptyFieldSubobjects(BaseDecl, Class, BaseOffset);
 476   }
 477
 478   if (RD == Class) {
 479     // This is the most derived class, traverse virtual bases as well.
 480     for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
 481          E = RD->vbases_end(); I != E; ++I) {
 482       const CXXRecordDecl *VBaseDecl =
 483       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 484
 485       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
 486       UpdateEmptyFieldSubobjects(VBaseDecl, Class, VBaseOffset);
 487     }
 488   }
 489
 490   // Traverse all member variables.
 491   unsigned FieldNo = 0;
 492   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 493        I != E; ++I, ++FieldNo) {
 494     const FieldDecl *FD = *I;
 495     if (FD->isBitField())
 496       continue;
 497
 498     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
 499
 500     UpdateEmptyFieldSubobjects(FD, FieldOffset);
 501   }
 502 }
 503
 504 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(const FieldDecl *FD,
 505                                                    CharUnits Offset) {
 506   QualType T = FD->getType();
 507   if (const RecordType *RT = T->getAs<RecordType>()) {
 508     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 509     UpdateEmptyFieldSubobjects(RD, RD, Offset);
 510     return;
 511   }
 512
 513   // If we have an array type we need to update every element.
 514   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
 515     QualType ElemTy = Context.getBaseElementType(AT);
 516     const RecordType *RT = ElemTy->getAs<RecordType>();
 517     if (!RT)
 518       return;
 519
 520     const CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
 521     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 522
 523     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
 524     CharUnits ElementOffset = Offset;
 525
 526     for (uint64_t I = 0; I != NumElements; ++I) {
 527       // We know that the only empty subobjects that can conflict with empty
 528       // field subobjects are subobjects of empty bases that can be placed at
 529       // offset zero. Because of this, we only need to keep track of empty field
 530       // subobjects with offsets less than the size of the largest empty
 531       // subobject for our class.
 532       if (ElementOffset >= SizeOfLargestEmptySubobject)
 533         return;
 534
 535       UpdateEmptyFieldSubobjects(RD, RD, ElementOffset);
 536       ElementOffset += Layout.getSize();
 537     }
 538   }
 539 }
 540
 541 class RecordLayoutBuilder {
 542 protected:
 543   // FIXME: Remove this and make the appropriate fields public.
 544   friend class clang::ASTContext;
 545
 546   const ASTContext &Context;
 547
 548   EmptySubobjectMap *EmptySubobjects;
 549
 550   /// Size - The current size of the record layout.
 551   uint64_t Size;
 552
 553   /// Alignment - The current alignment of the record layout.
 554   CharUnits Alignment;
 555
 556   /// \brief The alignment if attribute packed is not used.
 557   CharUnits UnpackedAlignment;
 558
 559   llvm::SmallVector<uint64_t, 16> FieldOffsets;
 560
 561   /// Packed - Whether the record is packed or not.
 562   unsigned Packed : 1;
 563
 564   unsigned IsUnion : 1;
 565
 566   unsigned IsMac68kAlign : 1;
 567
 568   unsigned IsMsStruct : 1;
 569
 570   /// UnfilledBitsInLastByte - If the last field laid out was a bitfield,
 571   /// this contains the number of bits in the last byte that can be used for
 572   /// an adjacent bitfield if necessary.
 573   unsigned char UnfilledBitsInLastByte;
 574
 575   /// MaxFieldAlignment - The maximum allowed field alignment. This is set by
 576   /// #pragma pack.
 577   CharUnits MaxFieldAlignment;
 578
 579   /// DataSize - The data size of the record being laid out.
 580   uint64_t DataSize;
 581
 582   CharUnits NonVirtualSize;
 583   CharUnits NonVirtualAlignment;
 584
 585   FieldDecl *ZeroLengthBitfield;
 586
 587   /// PrimaryBase - the primary base class (if one exists) of the class
 588   /// we're laying out.
 589   const CXXRecordDecl *PrimaryBase;
 590
 591   /// PrimaryBaseIsVirtual - Whether the primary base of the class we're laying
 592   /// out is virtual.
 593   bool PrimaryBaseIsVirtual;
 594
 595   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsetsMapTy;
 596
 597   /// Bases - base classes and their offsets in the record.
 598   BaseOffsetsMapTy Bases;
 599
 600   // VBases - virtual base classes and their offsets in the record.
 601   BaseOffsetsMapTy VBases;
 602
 603   /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
 604   /// primary base classes for some other direct or indirect base class.
 605   CXXIndirectPrimaryBaseSet IndirectPrimaryBases;
 606
 607   /// FirstNearlyEmptyVBase - The first nearly empty virtual base class in
 608   /// inheritance graph order. Used for determining the primary base class.
 609   const CXXRecordDecl *FirstNearlyEmptyVBase;
 610
 611   /// VisitedVirtualBases - A set of all the visited virtual bases, used to
 612   /// avoid visiting virtual bases more than once.
 613   llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
 614
 615   RecordLayoutBuilder(const ASTContext &Context, EmptySubobjectMap
 616                       *EmptySubobjects)
 617     : Context(Context), EmptySubobjects(EmptySubobjects), Size(0),
 618       Alignment(CharUnits::One()), UnpackedAlignment(Alignment),
 619       Packed(false), IsUnion(false),
 620       IsMac68kAlign(false), IsMsStruct(false),
 621       UnfilledBitsInLastByte(0), MaxFieldAlignment(CharUnits::Zero()),
 622       DataSize(0), NonVirtualSize(CharUnits::Zero()),
 623       NonVirtualAlignment(CharUnits::One()),
 624       ZeroLengthBitfield(0), PrimaryBase(0),
 625       PrimaryBaseIsVirtual(false), FirstNearlyEmptyVBase(0) { }
 626
 627   void Layout(const RecordDecl *D);
 628   void Layout(const CXXRecordDecl *D);
 629   void Layout(const ObjCInterfaceDecl *D);
 630
 631   void LayoutFields(const RecordDecl *D);
 632   void LayoutField(const FieldDecl *D);
 633   void LayoutWideBitField(uint64_t FieldSize, uint64_t TypeSize,
 634                           bool FieldPacked, const FieldDecl *D);
 635   void LayoutBitField(const FieldDecl *D);
 636
 637   /// BaseSubobjectInfoAllocator - Allocator for BaseSubobjectInfo objects.
 638   llvm::SpecificBumpPtrAllocator<BaseSubobjectInfo> BaseSubobjectInfoAllocator;
 639
 640   typedef llvm::DenseMap<const CXXRecordDecl *, BaseSubobjectInfo *>
 641     BaseSubobjectInfoMapTy;
 642
 643   /// VirtualBaseInfo - Map from all the (direct or indirect) virtual bases
 644   /// of the class we're laying out to their base subobject info.
 645   BaseSubobjectInfoMapTy VirtualBaseInfo;
 646
 647   /// NonVirtualBaseInfo - Map from all the direct non-virtual bases of the
 648   /// class we're laying out to their base subobject info.
 649   BaseSubobjectInfoMapTy NonVirtualBaseInfo;
 650
 651   /// ComputeBaseSubobjectInfo - Compute the base subobject information for the
 652   /// bases of the given class.
 653   void ComputeBaseSubobjectInfo(const CXXRecordDecl *RD);
 654
 655   /// ComputeBaseSubobjectInfo - Compute the base subobject information for a
 656   /// single class and all of its base classes.
 657   BaseSubobjectInfo *ComputeBaseSubobjectInfo(const CXXRecordDecl *RD,
 658                                               bool IsVirtual,
 659                                               BaseSubobjectInfo *Derived);
 660
 661   /// DeterminePrimaryBase - Determine the primary base of the given class.
 662   void DeterminePrimaryBase(const CXXRecordDecl *RD);
 663
 664   void SelectPrimaryVBase(const CXXRecordDecl *RD);
 665
 666   virtual CharUnits GetVirtualPointersSize(const CXXRecordDecl *RD) const;
 667
 668   /// LayoutNonVirtualBases - Determines the primary base class (if any) and
 669   /// lays it out. Will then proceed to lay out all non-virtual base clasess.
 670   void LayoutNonVirtualBases(const CXXRecordDecl *RD);
 671
 672   /// LayoutNonVirtualBase - Lays out a single non-virtual base.
 673   void LayoutNonVirtualBase(const BaseSubobjectInfo *Base);
 674
 675   void AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info,
 676                                     CharUnits Offset);
 677
 678   /// LayoutVirtualBases - Lays out all the virtual bases.
 679   void LayoutVirtualBases(const CXXRecordDecl *RD,
 680                           const CXXRecordDecl *MostDerivedClass);
 681
 682   /// LayoutVirtualBase - Lays out a single virtual base.
 683   void LayoutVirtualBase(const BaseSubobjectInfo *Base);
 684
 685   /// LayoutBase - Will lay out a base and return the offset where it was
 686   /// placed, in chars.
 687   CharUnits LayoutBase(const BaseSubobjectInfo *Base);
 688
 689   /// InitializeLayout - Initialize record layout for the given record decl.
 690   void InitializeLayout(const Decl *D);
 691
 692   /// FinishLayout - Finalize record layout. Adjust record size based on the
 693   /// alignment.
 694   void FinishLayout(const NamedDecl *D);
 695
 696   void UpdateAlignment(CharUnits NewAlignment, CharUnits UnpackedNewAlignment);
 697   void UpdateAlignment(CharUnits NewAlignment) {
 698     UpdateAlignment(NewAlignment, NewAlignment);
 699   }
 700
 701   void CheckFieldPadding(uint64_t Offset, uint64_t UnpaddedOffset,
 702                           uint64_t UnpackedOffset, unsigned UnpackedAlign,
 703                           bool isPacked, const FieldDecl *D);
 704
 705   DiagnosticBuilder Diag(SourceLocation Loc, unsigned DiagID);
 706
 707   CharUnits getSize() const {
 708     assert(Size % Context.getCharWidth() == 0);
 709     return Context.toCharUnitsFromBits(Size);
 710   }
 711   uint64_t getSizeInBits() const { return Size; }
 712
 713   void setSize(CharUnits NewSize) { Size = Context.toBits(NewSize); }
 714   void setSize(uint64_t NewSize) { Size = NewSize; }
 715
 716   CharUnits getDataSize() const {
 717     assert(DataSize % Context.getCharWidth() == 0);
 718     return Context.toCharUnitsFromBits(DataSize);
 719   }
 720   uint64_t getDataSizeInBits() const { return DataSize; }
 721
 722   void setDataSize(CharUnits NewSize) { DataSize = Context.toBits(NewSize); }
 723   void setDataSize(uint64_t NewSize) { DataSize = NewSize; }
 724
 725
 726   RecordLayoutBuilder(const RecordLayoutBuilder&);   // DO NOT IMPLEMENT
 727   void operator=(const RecordLayoutBuilder&); // DO NOT IMPLEMENT
 728 public:
 729   static const CXXMethodDecl *ComputeKeyFunction(const CXXRecordDecl *RD);
 730
 731   virtual ~RecordLayoutBuilder() { }
 732 };
 733 } // end anonymous namespace
 734
 735 void
 736 RecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) {
 737   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 738          E = RD->bases_end(); I != E; ++I) {
 739     assert(!I->getType()->isDependentType() &&
 740            "Cannot layout class with dependent bases.");
 741
 742     const CXXRecordDecl *Base =
 743       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 744
 745     // Check if this is a nearly empty virtual base.
 746     if (I->isVirtual() && Context.isNearlyEmpty(Base)) {
 747       // If it's not an indirect primary base, then we've found our primary
 748       // base.
 749       if (!IndirectPrimaryBases.count(Base)) {
 750         PrimaryBase = Base;
 751         PrimaryBaseIsVirtual = true;
 752         return;
 753       }
 754
 755       // Is this the first nearly empty virtual base?
 756       if (!FirstNearlyEmptyVBase)
 757         FirstNearlyEmptyVBase = Base;
 758     }
 759
 760     SelectPrimaryVBase(Base);
 761     if (PrimaryBase)
 762       return;
 763   }
 764 }
 765
 766 CharUnits
 767 RecordLayoutBuilder::GetVirtualPointersSize(const CXXRecordDecl *RD) const {
 768   return Context.toCharUnitsFromBits(Context.Target.getPointerWidth(0));
 769 }
 770
 771 /// DeterminePrimaryBase - Determine the primary base of the given class.
 772 void RecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) {
 773   // If the class isn't dynamic, it won't have a primary base.
 774   if (!RD->isDynamicClass())
 775     return;
 776
 777   // Compute all the primary virtual bases for all of our direct and
 778   // indirect bases, and record all their primary virtual base classes.
 779   RD->getIndirectPrimaryBases(IndirectPrimaryBases);
 780
 781   // If the record has a dynamic base class, attempt to choose a primary base
 782   // class. It is the first (in direct base class order) non-virtual dynamic
 783   // base class, if one exists.
 784   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 785          e = RD->bases_end(); i != e; ++i) {
 786     // Ignore virtual bases.
 787     if (i->isVirtual())
 788       continue;
 789
 790     const CXXRecordDecl *Base =
 791       cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 792
 793     if (Base->isDynamicClass()) {
 794       // We found it.
 795       PrimaryBase = Base;
 796       PrimaryBaseIsVirtual = false;
 797       return;
 798     }
 799   }
 800
 801   // Otherwise, it is the first nearly empty virtual base that is not an
 802   // indirect primary virtual base class, if one exists.
 803   if (RD->getNumVBases() != 0) {
 804     SelectPrimaryVBase(RD);
 805     if (PrimaryBase)
 806       return;
 807   }
 808
 809   // Otherwise, it is the first nearly empty virtual base that is not an
 810   // indirect primary virtual base class, if one exists.
 811   if (FirstNearlyEmptyVBase) {
 812     PrimaryBase = FirstNearlyEmptyVBase;
 813     PrimaryBaseIsVirtual = true;
 814     return;
 815   }
 816
 817   // Otherwise there is no primary base class.
 818   assert(!PrimaryBase && "Should not get here with a primary base!");
 819
 820   // Allocate the virtual table pointer at offset zero.
 821   assert(DataSize == 0 && "Vtable pointer must be at offset zero!");
 822
 823   // Update the size.
 824   setSize(getSize() + GetVirtualPointersSize(RD));
 825   setDataSize(getSize());
 826
 827   CharUnits UnpackedBaseAlign =
 828     Context.toCharUnitsFromBits(Context.Target.getPointerAlign(0));
 829   CharUnits BaseAlign = (Packed) ? CharUnits::One() : UnpackedBaseAlign;
 830
 831   // The maximum field alignment overrides base align.
 832   if (!MaxFieldAlignment.isZero()) {
 833     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
 834     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
 835   }
 836
 837   // Update the alignment.
 838   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
 839 }
 840
 841 BaseSubobjectInfo *
 842 RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD,
 843                                               bool IsVirtual,
 844                                               BaseSubobjectInfo *Derived) {
 845   BaseSubobjectInfo *Info;
 846
 847   if (IsVirtual) {
 848     // Check if we already have info about this virtual base.
 849     BaseSubobjectInfo *&InfoSlot = VirtualBaseInfo[RD];
 850     if (InfoSlot) {
 851       assert(InfoSlot->Class == RD && "Wrong class for virtual base info!");
 852       return InfoSlot;
 853     }
 854
 855     // We don't, create it.
 856     InfoSlot = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
 857     Info = InfoSlot;
 858   } else {
 859     Info = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
 860   }
 861
 862   Info->Class = RD;
 863   Info->IsVirtual = IsVirtual;
 864   Info->Derived = 0;
 865   Info->PrimaryVirtualBaseInfo = 0;
 866
 867   const CXXRecordDecl *PrimaryVirtualBase = 0;
 868   BaseSubobjectInfo *PrimaryVirtualBaseInfo = 0;
 869
 870   // Check if this base has a primary virtual base.
 871   if (RD->getNumVBases()) {
 872     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
 873     if (Layout.isPrimaryBaseVirtual()) {
 874       // This base does have a primary virtual base.
 875       PrimaryVirtualBase = Layout.getPrimaryBase();
 876       assert(PrimaryVirtualBase && "Didn't have a primary virtual base!");
 877
 878       // Now check if we have base subobject info about this primary base.
 879       PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
 880
 881       if (PrimaryVirtualBaseInfo) {
 882         if (PrimaryVirtualBaseInfo->Derived) {
 883           // We did have info about this primary base, and it turns out that it
 884           // has already been claimed as a primary virtual base for another
 885           // base.
 886           PrimaryVirtualBase = 0;
 887         } else {
 888           // We can claim this base as our primary base.
 889           Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
 890           PrimaryVirtualBaseInfo->Derived = Info;
 891         }
 892       }
 893     }
 894   }
 895
 896   // Now go through all direct bases.
 897   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 898        E = RD->bases_end(); I != E; ++I) {
 899     bool IsVirtual = I->isVirtual();
 900
 901     const CXXRecordDecl *BaseDecl =
 902       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 903
 904     Info->Bases.push_back(ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, Info));
 905   }
 906
 907   if (PrimaryVirtualBase && !PrimaryVirtualBaseInfo) {
 908     // Traversing the bases must have created the base info for our primary
 909     // virtual base.
 910     PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
 911     assert(PrimaryVirtualBaseInfo &&
 912            "Did not create a primary virtual base!");
 913
 914     // Claim the primary virtual base as our primary virtual base.
 915     Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
 916     PrimaryVirtualBaseInfo->Derived = Info;
 917   }
 918
 919   return Info;
 920 }
 921
 922 void RecordLayoutBuilder::ComputeBaseSubobjectInfo(const CXXRecordDecl *RD) {
 923   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 924        E = RD->bases_end(); I != E; ++I) {
 925     bool IsVirtual = I->isVirtual();
 926
 927     const CXXRecordDecl *BaseDecl =
 928       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 929
 930     // Compute the base subobject info for this base.
 931     BaseSubobjectInfo *Info = ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, 0);
 932
 933     if (IsVirtual) {
 934       // ComputeBaseInfo has already added this base for us.
 935       assert(VirtualBaseInfo.count(BaseDecl) &&
 936              "Did not add virtual base!");
 937     } else {
 938       // Add the base info to the map of non-virtual bases.
 939       assert(!NonVirtualBaseInfo.count(BaseDecl) &&
 940              "Non-virtual base already exists!");
 941       NonVirtualBaseInfo.insert(std::make_pair(BaseDecl, Info));
 942     }
 943   }
 944 }
 945
 946 void
 947 RecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
 948   // Then, determine the primary base class.
 949   DeterminePrimaryBase(RD);
 950
 951   // Compute base subobject info.
 952   ComputeBaseSubobjectInfo(RD);
 953
 954   // If we have a primary base class, lay it out.
 955   if (PrimaryBase) {
 956     if (PrimaryBaseIsVirtual) {
 957       // If the primary virtual base was a primary virtual base of some other
 958       // base class we'll have to steal it.
 959       BaseSubobjectInfo *PrimaryBaseInfo = VirtualBaseInfo.lookup(PrimaryBase);
 960       PrimaryBaseInfo->Derived = 0;
 961
 962       // We have a virtual primary base, insert it as an indirect primary base.
 963       IndirectPrimaryBases.insert(PrimaryBase);
 964
 965       assert(!VisitedVirtualBases.count(PrimaryBase) &&
 966              "vbase already visited!");
 967       VisitedVirtualBases.insert(PrimaryBase);
 968
 969       LayoutVirtualBase(PrimaryBaseInfo);
 970     } else {
 971       BaseSubobjectInfo *PrimaryBaseInfo =
 972         NonVirtualBaseInfo.lookup(PrimaryBase);
 973       assert(PrimaryBaseInfo &&
 974              "Did not find base info for non-virtual primary base!");
 975
 976       LayoutNonVirtualBase(PrimaryBaseInfo);
 977     }
 978   }
 979
 980   // Now lay out the non-virtual bases.
 981   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 982          E = RD->bases_end(); I != E; ++I) {
 983
 984     // Ignore virtual bases.
 985     if (I->isVirtual())
 986       continue;
 987
 988     const CXXRecordDecl *BaseDecl =
 989       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 990
 991     // Skip the primary base.
 992     if (BaseDecl == PrimaryBase && !PrimaryBaseIsVirtual)
 993       continue;
 994
 995     // Lay out the base.
 996     BaseSubobjectInfo *BaseInfo = NonVirtualBaseInfo.lookup(BaseDecl);
 997     assert(BaseInfo && "Did not find base info for non-virtual base!");
 998
 999     LayoutNonVirtualBase(BaseInfo);
1000   }
1001 }
1002
1003 void RecordLayoutBuilder::LayoutNonVirtualBase(const BaseSubobjectInfo *Base) {
1004   // Layout the base.
1005   CharUnits Offset = LayoutBase(Base);
1006
1007   // Add its base class offset.
1008   assert(!Bases.count(Base->Class) && "base offset already exists!");
1009   Bases.insert(std::make_pair(Base->Class, Offset));
1010
1011   AddPrimaryVirtualBaseOffsets(Base, Offset);
1012 }
1013
1014 void
1015 RecordLayoutBuilder::AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info,
1016                                                   CharUnits Offset) {
1017   // This base isn't interesting, it has no virtual bases.
1018   if (!Info->Class->getNumVBases())
1019     return;
1020
1021   // First, check if we have a virtual primary base to add offsets for.
1022   if (Info->PrimaryVirtualBaseInfo) {
1023     assert(Info->PrimaryVirtualBaseInfo->IsVirtual &&
1024            "Primary virtual base is not virtual!");
1025     if (Info->PrimaryVirtualBaseInfo->Derived == Info) {
1026       // Add the offset.
1027       assert(!VBases.count(Info->PrimaryVirtualBaseInfo->Class) &&
1028              "primary vbase offset already exists!");
1029       VBases.insert(std::make_pair(Info->PrimaryVirtualBaseInfo->Class,
1030                                    Offset));
1031
1032       // Traverse the primary virtual base.
1033       AddPrimaryVirtualBaseOffsets(Info->PrimaryVirtualBaseInfo, Offset);
1034     }
1035   }
1036
1037   // Now go through all direct non-virtual bases.
1038   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
1039   for (unsigned I = 0, E = Info->Bases.size(); I != E; ++I) {
1040     const BaseSubobjectInfo *Base = Info->Bases[I];
1041     if (Base->IsVirtual)
1042       continue;
1043
1044     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
1045     AddPrimaryVirtualBaseOffsets(Base, BaseOffset);
1046   }
1047 }
1048
1049 void
1050 RecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
1051                                         const CXXRecordDecl *MostDerivedClass) {
1052   const CXXRecordDecl *PrimaryBase;
1053   bool PrimaryBaseIsVirtual;
1054
1055   if (MostDerivedClass == RD) {
1056     PrimaryBase = this->PrimaryBase;
1057     PrimaryBaseIsVirtual = this->PrimaryBaseIsVirtual;
1058   } else {
1059     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1060     PrimaryBase = Layout.getPrimaryBase();
1061     PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
1062   }
1063
1064   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
1065          E = RD->bases_end(); I != E; ++I) {
1066     assert(!I->getType()->isDependentType() &&
1067            "Cannot layout class with dependent bases.");
1068
1069     const CXXRecordDecl *BaseDecl =
1070       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1071
1072     if (I->isVirtual()) {
1073       if (PrimaryBase != BaseDecl || !PrimaryBaseIsVirtual) {
1074         bool IndirectPrimaryBase = IndirectPrimaryBases.count(BaseDecl);
1075
1076         // Only lay out the virtual base if it's not an indirect primary base.
1077         if (!IndirectPrimaryBase) {
1078           // Only visit virtual bases once.
1079           if (!VisitedVirtualBases.insert(BaseDecl))
1080             continue;
1081
1082           const BaseSubobjectInfo *BaseInfo = VirtualBaseInfo.lookup(BaseDecl);
1083           assert(BaseInfo && "Did not find virtual base info!");
1084           LayoutVirtualBase(BaseInfo);
1085         }
1086       }
1087     }
1088
1089     if (!BaseDecl->getNumVBases()) {
1090       // This base isn't interesting since it doesn't have any virtual bases.
1091       continue;
1092     }
1093
1094     LayoutVirtualBases(BaseDecl, MostDerivedClass);
1095   }
1096 }
1097
1098 void RecordLayoutBuilder::LayoutVirtualBase(const BaseSubobjectInfo *Base) {
1099   assert(!Base->Derived && "Trying to lay out a primary virtual base!");
1100
1101   // Layout the base.
1102   CharUnits Offset = LayoutBase(Base);
1103
1104   // Add its base class offset.
1105   assert(!VBases.count(Base->Class) && "vbase offset already exists!");
1106   VBases.insert(std::make_pair(Base->Class, Offset));
1107
1108   AddPrimaryVirtualBaseOffsets(Base, Offset);
1109 }
1110
1111 CharUnits RecordLayoutBuilder::LayoutBase(const BaseSubobjectInfo *Base) {
1112   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base->Class);
1113
1114   // If we have an empty base class, try to place it at offset 0.
1115   if (Base->Class->isEmpty() &&
1116       EmptySubobjects->CanPlaceBaseAtOffset(Base, CharUnits::Zero())) {
1117     setSize(std::max(getSize(), Layout.getSize()));
1118
1119     return CharUnits::Zero();
1120   }
1121
1122   CharUnits UnpackedBaseAlign = Layout.getNonVirtualAlign();
1123   CharUnits BaseAlign = (Packed) ? CharUnits::One() : UnpackedBaseAlign;
1124
1125   // The maximum field alignment overrides base align.
1126   if (!MaxFieldAlignment.isZero()) {
1127     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
1128     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
1129   }
1130
1131   // Round up the current record size to the base's alignment boundary.
1132   CharUnits Offset = getDataSize().RoundUpToAlignment(BaseAlign);
1133
1134   // Try to place the base.
1135   while (!EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset))
1136     Offset += BaseAlign;
1137
1138   if (!Base->Class->isEmpty()) {
1139     // Update the data size.
1140     setDataSize(Offset + Layout.getNonVirtualSize());
1141
1142     setSize(std::max(getSize(), getDataSize()));
1143   } else
1144     setSize(std::max(getSize(), Offset + Layout.getSize()));
1145
1146   // Remember max struct/class alignment.
1147   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1148
1149   return Offset;
1150 }
1151
1152 void RecordLayoutBuilder::InitializeLayout(const Decl *D) {
1153   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D))
1154     IsUnion = RD->isUnion();
1155
1156   Packed = D->hasAttr<PackedAttr>();
1157
1158   IsMsStruct = D->hasAttr<MsStructAttr>();
1159
1160   // mac68k alignment supersedes maximum field alignment and attribute aligned,
1161   // and forces all structures to have 2-byte alignment. The IBM docs on it
1162   // allude to additional (more complicated) semantics, especially with regard
1163   // to bit-fields, but gcc appears not to follow that.
1164   if (D->hasAttr<AlignMac68kAttr>()) {
1165     IsMac68kAlign = true;
1166     MaxFieldAlignment = CharUnits::fromQuantity(2);
1167     Alignment = CharUnits::fromQuantity(2);
1168   } else {
1169     if (const MaxFieldAlignmentAttr *MFAA = D->getAttr<MaxFieldAlignmentAttr>())
1170       MaxFieldAlignment = Context.toCharUnitsFromBits(MFAA->getAlignment());
1171
1172     if (unsigned MaxAlign = D->getMaxAlignment())
1173       UpdateAlignment(Context.toCharUnitsFromBits(MaxAlign));
1174   }
1175 }
1176
1177 void RecordLayoutBuilder::Layout(const RecordDecl *D) {
1178   InitializeLayout(D);
1179   LayoutFields(D);
1180
1181   // Finally, round the size of the total struct up to the alignment of the
1182   // struct itself.
1183   FinishLayout(D);
1184 }
1185
1186 void RecordLayoutBuilder::Layout(const CXXRecordDecl *RD) {
1187   InitializeLayout(RD);
1188
1189   // Lay out the vtable and the non-virtual bases.
1190   LayoutNonVirtualBases(RD);
1191
1192   LayoutFields(RD);
1193
1194   NonVirtualSize = Context.toCharUnitsFromBits(
1195         llvm::RoundUpToAlignment(getSizeInBits(),
1196                                  Context.Target.getCharAlign()));
1197   NonVirtualAlignment = Alignment;
1198
1199   // Lay out the virtual bases and add the primary virtual base offsets.
1200   LayoutVirtualBases(RD, RD);
1201
1202   VisitedVirtualBases.clear();
1203
1204   // Finally, round the size of the total struct up to the alignment of the
1205   // struct itself.
1206   FinishLayout(RD);
1207
1208 #ifndef NDEBUG
1209   // Check that we have base offsets for all bases.
1210   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
1211        E = RD->bases_end(); I != E; ++I) {
1212     if (I->isVirtual())
1213       continue;
1214
1215     const CXXRecordDecl *BaseDecl =
1216       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1217
1218     assert(Bases.count(BaseDecl) && "Did not find base offset!");
1219   }
1220
1221   // And all virtual bases.
1222   for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
1223        E = RD->vbases_end(); I != E; ++I) {
1224     const CXXRecordDecl *BaseDecl =
1225       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1226
1227     assert(VBases.count(BaseDecl) && "Did not find base offset!");
1228   }
1229 #endif
1230 }
1231
1232 void RecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D) {
1233   if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
1234     const ASTRecordLayout &SL = Context.getASTObjCInterfaceLayout(SD);
1235
1236     UpdateAlignment(SL.getAlignment());
1237
1238     // We start laying out ivars not at the end of the superclass
1239     // structure, but at the next byte following the last field.
1240     setSize(SL.getDataSize());
1241     setDataSize(getSize());
1242   }
1243
1244   InitializeLayout(D);
1245
1246   // Layout each ivar sequentially.
1247   llvm::SmallVector<ObjCIvarDecl*, 16> Ivars;
1248   Context.ShallowCollectObjCIvars(D, Ivars);
1249   for (unsigned i = 0, e = Ivars.size(); i != e; ++i)
1250     LayoutField(Ivars[i]);
1251
1252   // Finally, round the size of the total struct up to the alignment of the
1253   // struct itself.
1254   FinishLayout(D);
1255 }
1256
1257 void RecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
1258   // Layout each field, for now, just sequentially, respecting alignment.  In
1259   // the future, this will need to be tweakable by targets.
1260   const FieldDecl *LastFD = 0;
1261   ZeroLengthBitfield = 0;
1262   unsigned RemainingInAlignment = 0;
1263   for (RecordDecl::field_iterator Field = D->field_begin(),
1264        FieldEnd = D->field_end(); Field != FieldEnd; ++Field) {
1265     if (IsMsStruct) {
1266       FieldDecl *FD =  (*Field);
1267       if (Context.ZeroBitfieldFollowsBitfield(FD, LastFD))
1268         ZeroLengthBitfield = FD;
1269       // Zero-length bitfields following non-bitfield members are
1270       // ignored:
1271       else if (Context.ZeroBitfieldFollowsNonBitfield(FD, LastFD))
1272         continue;
1273       // FIXME. streamline these conditions into a simple one.
1274       else if (Context.BitfieldFollowsBitfield(FD, LastFD) ||
1275                Context.BitfieldFollowsNoneBitfield(FD, LastFD) ||
1276                Context.NoneBitfieldFollowsBitfield(FD, LastFD)) {
1277         // 1) Adjacent bit fields are packed into the same 1-, 2-, or
1278         // 4-byte allocation unit if the integral types are the same
1279         // size and if the next bit field fits into the current
1280         // allocation unit without crossing the boundary imposed by the
1281         // common alignment requirements of the bit fields.
1282         // 2) Establish a new alignment for a bitfield following
1283         // a non-bitfield if size of their types differ.
1284         // 3) Establish a new alignment for a non-bitfield following
1285         // a bitfield if size of their types differ.
1286         std::pair<uint64_t, unsigned> FieldInfo =
1287           Context.getTypeInfo(FD->getType());
1288         uint64_t TypeSize = FieldInfo.first;
1289         unsigned FieldAlign = FieldInfo.second;
1290         // This check is needed for 'long long' in -m32 mode.
1291         if (TypeSize > FieldAlign)
1292           FieldAlign = TypeSize;
1293         FieldInfo = Context.getTypeInfo(LastFD->getType());
1294         uint64_t TypeSizeLastFD = FieldInfo.first;
1295         unsigned FieldAlignLastFD = FieldInfo.second;
1296         // This check is needed for 'long long' in -m32 mode.
1297         if (TypeSizeLastFD > FieldAlignLastFD)
1298           FieldAlignLastFD = TypeSizeLastFD;
1299
1300         if (TypeSizeLastFD != TypeSize) {
1301           if (RemainingInAlignment &&
1302               LastFD && LastFD->isBitField() &&
1303               LastFD->getBitWidth()->EvaluateAsInt(Context).getZExtValue()) {
1304             // If previous field was a bitfield with some remaining unfilled
1305             // bits, pad the field so current field starts on its type boundary.
1306             uint64_t FieldOffset =
1307             getDataSizeInBits() - UnfilledBitsInLastByte;
1308             uint64_t NewSizeInBits = RemainingInAlignment + FieldOffset;
1309             setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1310                                                  Context.Target.getCharAlign()));
1311             setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1312             RemainingInAlignment = 0;
1313           }
1314
1315           uint64_t UnpaddedFieldOffset =
1316             getDataSizeInBits() - UnfilledBitsInLastByte;
1317           FieldAlign = std::max(FieldAlign, FieldAlignLastFD);
1318
1319           // The maximum field alignment overrides the aligned attribute.
1320           if (!MaxFieldAlignment.isZero()) {
1321             unsigned MaxFieldAlignmentInBits =
1322               Context.toBits(MaxFieldAlignment);
1323             FieldAlign = std::min(FieldAlign, MaxFieldAlignmentInBits);
1324           }
1325
1326           uint64_t NewSizeInBits =
1327             llvm::RoundUpToAlignment(UnpaddedFieldOffset, FieldAlign);
1328           setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1329                                                Context.Target.getCharAlign()));
1330           UnfilledBitsInLastByte = getDataSizeInBits() - NewSizeInBits;
1331           setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1332         }
1333         if (FD->isBitField()) {
1334           uint64_t FieldSize =
1335             FD->getBitWidth()->EvaluateAsInt(Context).getZExtValue();
1336           assert (FieldSize > 0 && "LayoutFields - ms_struct layout");
1337           if (RemainingInAlignment < FieldSize)
1338             RemainingInAlignment = TypeSize - FieldSize;
1339           else
1340             RemainingInAlignment -= FieldSize;
1341         }
1342       }
1343       else if (FD->isBitField()) {
1344         uint64_t FieldSize =
1345           FD->getBitWidth()->EvaluateAsInt(Context).getZExtValue();
1346         std::pair<uint64_t, unsigned> FieldInfo =
1347           Context.getTypeInfo(FD->getType());
1348         uint64_t TypeSize = FieldInfo.first;
1349         RemainingInAlignment = TypeSize - FieldSize;
1350       }
1351       LastFD = FD;
1352     }
1353     LayoutField(*Field);
1354   }
1355   if (IsMsStruct && RemainingInAlignment &&
1356       LastFD && LastFD->isBitField() &&
1357       LastFD->getBitWidth()->EvaluateAsInt(Context).getZExtValue()) {
1358     // If we ended a bitfield before the full length of the type then
1359     // pad the struct out to the full length of the last type.
1360     uint64_t FieldOffset =
1361       getDataSizeInBits() - UnfilledBitsInLastByte;
1362     uint64_t NewSizeInBits = RemainingInAlignment + FieldOffset;
1363     setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1364                                          Context.Target.getCharAlign()));
1365     setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1366   }
1367 }
1368
1369 void RecordLayoutBuilder::LayoutWideBitField(uint64_t FieldSize,
1370                                              uint64_t TypeSize,
1371                                              bool FieldPacked,
1372                                              const FieldDecl *D) {
1373   assert(Context.getLangOptions().CPlusPlus &&
1374          "Can only have wide bit-fields in C++!");
1375
1376   // Itanium C++ ABI 2.4:
1377   //   If sizeof(T)*8 < n, let T' be the largest integral POD type with
1378   //   sizeof(T')*8 <= n.
1379
1380   QualType IntegralPODTypes[] = {
1381     Context.UnsignedCharTy, Context.UnsignedShortTy, Context.UnsignedIntTy,
1382     Context.UnsignedLongTy, Context.UnsignedLongLongTy
1383   };
1384
1385   QualType Type;
1386   for (unsigned I = 0, E = llvm::array_lengthof(IntegralPODTypes);
1387        I != E; ++I) {
1388     uint64_t Size = Context.getTypeSize(IntegralPODTypes[I]);
1389
1390     if (Size > FieldSize)
1391       break;
1392
1393     Type = IntegralPODTypes[I];
1394   }
1395   assert(!Type.isNull() && "Did not find a type!");
1396
1397   CharUnits TypeAlign = Context.getTypeAlignInChars(Type);
1398
1399   // We're not going to use any of the unfilled bits in the last byte.
1400   UnfilledBitsInLastByte = 0;
1401
1402   uint64_t FieldOffset;
1403   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastByte;
1404
1405   if (IsUnion) {
1406     setDataSize(std::max(getDataSizeInBits(), FieldSize));
1407     FieldOffset = 0;
1408   } else {
1409     // The bitfield is allocated starting at the next offset aligned appropriately
1410     // for T', with length n bits.
1411     FieldOffset = llvm::RoundUpToAlignment(getDataSizeInBits(),
1412                                            Context.toBits(TypeAlign));
1413
1414     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1415
1416     setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1417                                          Context.Target.getCharAlign()));
1418     UnfilledBitsInLastByte = getDataSizeInBits() - NewSizeInBits;
1419   }
1420
1421   // Place this field at the current location.
1422   FieldOffsets.push_back(FieldOffset);
1423
1424   CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, FieldOffset,
1425                     Context.toBits(TypeAlign), FieldPacked, D);
1426
1427   // Update the size.
1428   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1429
1430   // Remember max struct/class alignment.
1431   UpdateAlignment(TypeAlign);
1432 }
1433
1434 void RecordLayoutBuilder::LayoutBitField(const FieldDecl *D) {
1435   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1436   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastByte;
1437   uint64_t FieldOffset = IsUnion ? 0 : UnpaddedFieldOffset;
1438   uint64_t FieldSize = D->getBitWidth()->EvaluateAsInt(Context).getZExtValue();
1439
1440   std::pair<uint64_t, unsigned> FieldInfo = Context.getTypeInfo(D->getType());
1441   uint64_t TypeSize = FieldInfo.first;
1442   unsigned FieldAlign = FieldInfo.second;
1443
1444   // This check is needed for 'long long' in -m32 mode.
1445   if (IsMsStruct && (TypeSize > FieldAlign))
1446     FieldAlign = TypeSize;
1447
1448   if (ZeroLengthBitfield) {
1449     // If a zero-length bitfield is inserted after a bitfield,
1450     // and the alignment of the zero-length bitfield is
1451     // greater than the member that follows it, `bar', `bar'
1452     // will be aligned as the type of the zero-length bitfield.
1453     if (ZeroLengthBitfield != D) {
1454       std::pair<uint64_t, unsigned> FieldInfo =
1455         Context.getTypeInfo(ZeroLengthBitfield->getType());
1456       unsigned ZeroLengthBitfieldAlignment = FieldInfo.second;
1457       // Ignore alignment of subsequent zero-length bitfields.
1458       if ((ZeroLengthBitfieldAlignment > FieldAlign) || (FieldSize == 0))
1459         FieldAlign = ZeroLengthBitfieldAlignment;
1460       if (FieldSize)
1461         ZeroLengthBitfield = 0;
1462     }
1463   }
1464
1465   if (FieldSize > TypeSize) {
1466     LayoutWideBitField(FieldSize, TypeSize, FieldPacked, D);
1467     return;
1468   }
1469
1470   // The align if the field is not packed. This is to check if the attribute
1471   // was unnecessary (-Wpacked).
1472   unsigned UnpackedFieldAlign = FieldAlign;
1473   uint64_t UnpackedFieldOffset = FieldOffset;
1474   if (!Context.Target.useBitFieldTypeAlignment())
1475     UnpackedFieldAlign = 1;
1476
1477   if (FieldPacked || !Context.Target.useBitFieldTypeAlignment())
1478     FieldAlign = 1;
1479   FieldAlign = std::max(FieldAlign, D->getMaxAlignment());
1480   UnpackedFieldAlign = std::max(UnpackedFieldAlign, D->getMaxAlignment());
1481
1482   // The maximum field alignment overrides the aligned attribute.
1483   if (!MaxFieldAlignment.isZero()) {
1484     unsigned MaxFieldAlignmentInBits = Context.toBits(MaxFieldAlignment);
1485     FieldAlign = std::min(FieldAlign, MaxFieldAlignmentInBits);
1486     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignmentInBits);
1487   }
1488
1489   // Check if we need to add padding to give the field the correct alignment.
1490   if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)
1491     FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
1492
1493   if (FieldSize == 0 ||
1494       (UnpackedFieldOffset & (UnpackedFieldAlign-1)) + FieldSize > TypeSize)
1495     UnpackedFieldOffset = llvm::RoundUpToAlignment(UnpackedFieldOffset,
1496                                                    UnpackedFieldAlign);
1497
1498   // Padding members don't affect overall alignment.
1499   if (!D->getIdentifier())
1500     FieldAlign = UnpackedFieldAlign = 1;
1501
1502   // Place this field at the current location.
1503   FieldOffsets.push_back(FieldOffset);
1504
1505   CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, UnpackedFieldOffset,
1506                     UnpackedFieldAlign, FieldPacked, D);
1507
1508   // Update DataSize to include the last byte containing (part of) the bitfield.
1509   if (IsUnion) {
1510     // FIXME: I think FieldSize should be TypeSize here.
1511     setDataSize(std::max(getDataSizeInBits(), FieldSize));
1512   } else {
1513     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1514
1515     setDataSize(llvm::RoundUpToAlignment(NewSizeInBits,
1516                                          Context.Target.getCharAlign()));
1517     UnfilledBitsInLastByte = getDataSizeInBits() - NewSizeInBits;
1518   }
1519
1520   // Update the size.
1521   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1522
1523   // Remember max struct/class alignment.
1524   UpdateAlignment(Context.toCharUnitsFromBits(FieldAlign),
1525                   Context.toCharUnitsFromBits(UnpackedFieldAlign));
1526 }
1527
1528 void RecordLayoutBuilder::LayoutField(const FieldDecl *D) {
1529   if (D->isBitField()) {
1530     LayoutBitField(D);
1531     return;
1532   }
1533
1534   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastByte;
1535
1536   // Reset the unfilled bits.
1537   UnfilledBitsInLastByte = 0;
1538
1539   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1540   CharUnits FieldOffset =
1541     IsUnion ? CharUnits::Zero() : getDataSize();
1542   CharUnits FieldSize;
1543   CharUnits FieldAlign;
1544
1545   if (D->getType()->isIncompleteArrayType()) {
1546     // This is a flexible array member; we can't directly
1547     // query getTypeInfo about these, so we figure it out here.
1548     // Flexible array members don't have any size, but they
1549     // have to be aligned appropriately for their element type.
1550     FieldSize = CharUnits::Zero();
1551     const ArrayType* ATy = Context.getAsArrayType(D->getType());
1552     FieldAlign = Context.getTypeAlignInChars(ATy->getElementType());
1553   } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
1554     unsigned AS = RT->getPointeeType().getAddressSpace();
1555     FieldSize =
1556       Context.toCharUnitsFromBits(Context.Target.getPointerWidth(AS));
1557     FieldAlign =
1558       Context.toCharUnitsFromBits(Context.Target.getPointerAlign(AS));
1559   } else {
1560     std::pair<CharUnits, CharUnits> FieldInfo =
1561       Context.getTypeInfoInChars(D->getType());
1562     FieldSize = FieldInfo.first;
1563     FieldAlign = FieldInfo.second;
1564
1565     if (ZeroLengthBitfield) {
1566       // If a zero-length bitfield is inserted after a bitfield,
1567       // and the alignment of the zero-length bitfield is
1568       // greater than the member that follows it, `bar', `bar'
1569       // will be aligned as the type of the zero-length bitfield.
1570       std::pair<CharUnits, CharUnits> FieldInfo =
1571         Context.getTypeInfoInChars(ZeroLengthBitfield->getType());
1572       CharUnits ZeroLengthBitfieldAlignment = FieldInfo.second;
1573       if (ZeroLengthBitfieldAlignment > FieldAlign)
1574         FieldAlign = ZeroLengthBitfieldAlignment;
1575       ZeroLengthBitfield = 0;
1576     }
1577
1578     if (Context.getLangOptions().MSBitfields || IsMsStruct) {
1579       // If MS bitfield layout is required, figure out what type is being
1580       // laid out and align the field to the width of that type.
1581
1582       // Resolve all typedefs down to their base type and round up the field
1583       // alignment if necessary.
1584       QualType T = Context.getBaseElementType(D->getType());
1585       if (const BuiltinType *BTy = T->getAs<BuiltinType>()) {
1586         CharUnits TypeSize = Context.getTypeSizeInChars(BTy);
1587         if (TypeSize > FieldAlign)
1588           FieldAlign = TypeSize;
1589       }
1590     }
1591   }
1592
1593   // The align if the field is not packed. This is to check if the attribute
1594   // was unnecessary (-Wpacked).
1595   CharUnits UnpackedFieldAlign = FieldAlign;
1596   CharUnits UnpackedFieldOffset = FieldOffset;
1597
1598   if (FieldPacked)
1599     FieldAlign = CharUnits::One();
1600   CharUnits MaxAlignmentInChars =
1601     Context.toCharUnitsFromBits(D->getMaxAlignment());
1602   FieldAlign = std::max(FieldAlign, MaxAlignmentInChars);
1603   UnpackedFieldAlign = std::max(UnpackedFieldAlign, MaxAlignmentInChars);
1604
1605   // The maximum field alignment overrides the aligned attribute.
1606   if (!MaxFieldAlignment.isZero()) {
1607     FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
1608     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignment);
1609   }
1610
1611   // Round up the current record size to the field's alignment boundary.
1612   FieldOffset = FieldOffset.RoundUpToAlignment(FieldAlign);
1613   UnpackedFieldOffset =
1614     UnpackedFieldOffset.RoundUpToAlignment(UnpackedFieldAlign);
1615
1616   if (!IsUnion && EmptySubobjects) {
1617     // Check if we can place the field at this offset.
1618     while (!EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset)) {
1619       // We couldn't place the field at the offset. Try again at a new offset.
1620       FieldOffset += FieldAlign;
1621     }
1622   }
1623
1624   // Place this field at the current location.
1625   FieldOffsets.push_back(Context.toBits(FieldOffset));
1626
1627   CheckFieldPadding(Context.toBits(FieldOffset), UnpaddedFieldOffset,
1628                     Context.toBits(UnpackedFieldOffset),
1629                     Context.toBits(UnpackedFieldAlign), FieldPacked, D);
1630
1631   // Reserve space for this field.
1632   uint64_t FieldSizeInBits = Context.toBits(FieldSize);
1633   if (IsUnion)
1634     setSize(std::max(getSizeInBits(), FieldSizeInBits));
1635   else
1636     setSize(FieldOffset + FieldSize);
1637
1638   // Update the data size.
1639   setDataSize(getSizeInBits());
1640
1641   // Remember max struct/class alignment.
1642   UpdateAlignment(FieldAlign, UnpackedFieldAlign);
1643 }
1644
1645 void RecordLayoutBuilder::FinishLayout(const NamedDecl *D) {
1646   // In C++, records cannot be of size 0.
1647   if (Context.getLangOptions().CPlusPlus && getSizeInBits() == 0) {
1648     if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
1649       // Compatibility with gcc requires a class (pod or non-pod)
1650       // which is not empty but of size 0; such as having fields of
1651       // array of zero-length, remains of Size 0
1652       if (RD->isEmpty())
1653         setSize(CharUnits::One());
1654     }
1655     else
1656       setSize(CharUnits::One());
1657   }
1658   // Finally, round the size of the record up to the alignment of the
1659   // record itself.
1660   uint64_t UnpaddedSize = getSizeInBits() - UnfilledBitsInLastByte;
1661   uint64_t UnpackedSizeInBits =
1662     llvm::RoundUpToAlignment(getSizeInBits(),
1663                              Context.toBits(UnpackedAlignment));
1664   CharUnits UnpackedSize = Context.toCharUnitsFromBits(UnpackedSizeInBits);
1665   setSize(llvm::RoundUpToAlignment(getSizeInBits(), Context.toBits(Alignment)));
1666
1667   unsigned CharBitNum = Context.Target.getCharWidth();
1668   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) {
1669     // Warn if padding was introduced to the struct/class/union.
1670     if (getSizeInBits() > UnpaddedSize) {
1671       unsigned PadSize = getSizeInBits() - UnpaddedSize;
1672       bool InBits = true;
1673       if (PadSize % CharBitNum == 0) {
1674         PadSize = PadSize / CharBitNum;
1675         InBits = false;
1676       }
1677       Diag(RD->getLocation(), diag::warn_padded_struct_size)
1678           << Context.getTypeDeclType(RD)
1679           << PadSize
1680           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1); // plural or not
1681     }
1682
1683     // Warn if we packed it unnecessarily. If the alignment is 1 byte don't
1684     // bother since there won't be alignment issues.
1685     if (Packed && UnpackedAlignment > CharUnits::One() &&
1686         getSize() == UnpackedSize)
1687       Diag(D->getLocation(), diag::warn_unnecessary_packed)
1688           << Context.getTypeDeclType(RD);
1689   }
1690 }
1691
1692 void RecordLayoutBuilder::UpdateAlignment(CharUnits NewAlignment,
1693                                           CharUnits UnpackedNewAlignment) {
1694   // The alignment is not modified when using 'mac68k' alignment.
1695   if (IsMac68kAlign)
1696     return;
1697
1698   if (NewAlignment > Alignment) {
1699     assert(llvm::isPowerOf2_32(NewAlignment.getQuantity() &&
1700            "Alignment not a power of 2"));
1701     Alignment = NewAlignment;
1702   }
1703
1704   if (UnpackedNewAlignment > UnpackedAlignment) {
1705     assert(llvm::isPowerOf2_32(UnpackedNewAlignment.getQuantity() &&
1706            "Alignment not a power of 2"));
1707     UnpackedAlignment = UnpackedNewAlignment;
1708   }
1709 }
1710
1711 void RecordLayoutBuilder::CheckFieldPadding(uint64_t Offset,
1712                                             uint64_t UnpaddedOffset,
1713                                             uint64_t UnpackedOffset,
1714                                             unsigned UnpackedAlign,
1715                                             bool isPacked,
1716                                             const FieldDecl *D) {
1717   // We let objc ivars without warning, objc interfaces generally are not used
1718   // for padding tricks.
1719   if (isa<ObjCIvarDecl>(D))
1720     return;
1721
1722   unsigned CharBitNum = Context.Target.getCharWidth();
1723
1724   // Warn if padding was introduced to the struct/class.
1725   if (!IsUnion && Offset > UnpaddedOffset) {
1726     unsigned PadSize = Offset - UnpaddedOffset;
1727     bool InBits = true;
1728     if (PadSize % CharBitNum == 0) {
1729       PadSize = PadSize / CharBitNum;
1730       InBits = false;
1731     }
1732     if (D->getIdentifier())
1733       Diag(D->getLocation(), diag::warn_padded_struct_field)
1734           << (D->getParent()->isStruct() ? 0 : 1) // struct|class
1735           << Context.getTypeDeclType(D->getParent())
1736           << PadSize
1737           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1) // plural or not
1738           << D->getIdentifier();
1739     else
1740       Diag(D->getLocation(), diag::warn_padded_struct_anon_field)
1741           << (D->getParent()->isStruct() ? 0 : 1) // struct|class
1742           << Context.getTypeDeclType(D->getParent())
1743           << PadSize
1744           << (InBits ? 1 : 0) /*(byte|bit)*/ << (PadSize > 1); // plural or not
1745   }
1746
1747   // Warn if we packed it unnecessarily. If the alignment is 1 byte don't
1748   // bother since there won't be alignment issues.
1749   if (isPacked && UnpackedAlign > CharBitNum && Offset == UnpackedOffset)
1750     Diag(D->getLocation(), diag::warn_unnecessary_packed)
1751         << D->getIdentifier();
1752 }
1753
1754 const CXXMethodDecl *
1755 RecordLayoutBuilder::ComputeKeyFunction(const CXXRecordDecl *RD) {
1756   // If a class isn't polymorphic it doesn't have a key function.
1757   if (!RD->isPolymorphic())
1758     return 0;
1759
1760   // A class that is not externally visible doesn't have a key function. (Or
1761   // at least, there's no point to assigning a key function to such a class;
1762   // this doesn't affect the ABI.)
1763   if (RD->getLinkage() != ExternalLinkage)
1764     return 0;
1765
1766   // Template instantiations don't have key functions,see Itanium C++ ABI 5.2.6.
1767   // Same behavior as GCC.
1768   TemplateSpecializationKind TSK = RD->getTemplateSpecializationKind();
1769   if (TSK == TSK_ImplicitInstantiation ||
1770       TSK == TSK_ExplicitInstantiationDefinition)
1771     return 0;
1772
1773   for (CXXRecordDecl::method_iterator I = RD->method_begin(),
1774          E = RD->method_end(); I != E; ++I) {
1775     const CXXMethodDecl *MD = *I;
1776
1777     if (!MD->isVirtual())
1778       continue;
1779
1780     if (MD->isPure())
1781       continue;
1782
1783     // Ignore implicit member functions, they are always marked as inline, but
1784     // they don't have a body until they're defined.
1785     if (MD->isImplicit())
1786       continue;
1787
1788     if (MD->isInlineSpecified())
1789       continue;
1790
1791     if (MD->hasInlineBody())
1792       continue;
1793
1794     // We found it.
1795     return MD;
1796   }
1797
1798   return 0;
1799 }
1800
1801 DiagnosticBuilder
1802 RecordLayoutBuilder::Diag(SourceLocation Loc, unsigned DiagID) {
1803   return Context.getDiagnostics().Report(Loc, DiagID);
1804 }
1805
1806 namespace {
1807   // This class implements layout specific to the Microsoft ABI.
1808   class MSRecordLayoutBuilder : public RecordLayoutBuilder {
1809   public:
1810     MSRecordLayoutBuilder(const ASTContext& Ctx,
1811                           EmptySubobjectMap *EmptySubobjects) :
1812       RecordLayoutBuilder(Ctx, EmptySubobjects) {}
1813
1814     virtual CharUnits GetVirtualPointersSize(const CXXRecordDecl *RD) const;
1815   };
1816 }
1817
1818 CharUnits
1819 MSRecordLayoutBuilder::GetVirtualPointersSize(const CXXRecordDecl *RD) const {
1820   // We should reserve space for two pointers if the class has both
1821   // virtual functions and virtual bases.
1822   CharUnits PointerWidth =
1823     Context.toCharUnitsFromBits(Context.Target.getPointerWidth(0));
1824   if (RD->isPolymorphic() && RD->getNumVBases() > 0)
1825     return 2 * PointerWidth;
1826   return PointerWidth;
1827 }
1828
1829 /// getASTRecordLayout - Get or compute information about the layout of the
1830 /// specified record (struct/union/class), which indicates its size and field
1831 /// position information.
1832 const ASTRecordLayout &
1833 ASTContext::getASTRecordLayout(const RecordDecl *D) const {
1834   D = D->getDefinition();
1835   assert(D && "Cannot get layout of forward declarations!");
1836
1837   // Look up this layout, if already laid out, return what we have.
1838   // Note that we can't save a reference to the entry because this function
1839   // is recursive.
1840   const ASTRecordLayout *Entry = ASTRecordLayouts[D];
1841   if (Entry) return *Entry;
1842
1843   const ASTRecordLayout *NewEntry;
1844
1845   if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
1846     EmptySubobjectMap EmptySubobjects(*this, RD);
1847
1848     // When compiling for Microsoft, use the special MS builder.
1849     llvm::OwningPtr<RecordLayoutBuilder> Builder;
1850     switch (Target.getCXXABI()) {
1851     default:
1852       Builder.reset(new RecordLayoutBuilder(*this, &EmptySubobjects));
1853       break;
1854     case CXXABI_Microsoft:
1855       Builder.reset(new MSRecordLayoutBuilder(*this, &EmptySubobjects));
1856     }
1857     // Recover resources if we crash before exiting this method.
1858     llvm::CrashRecoveryContextCleanupRegistrar<RecordLayoutBuilder>
1859       RecordBuilderCleanup(Builder.get());
1860
1861     Builder->Layout(RD);
1862
1863     // FIXME: This is not always correct. See the part about bitfields at
1864     // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info.
1865     // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout.
1866     bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD();
1867
1868     // FIXME: This should be done in FinalizeLayout.
1869     CharUnits DataSize =
1870       IsPODForThePurposeOfLayout ? Builder->getSize() : Builder->getDataSize();
1871     CharUnits NonVirtualSize =
1872       IsPODForThePurposeOfLayout ? DataSize : Builder->NonVirtualSize;
1873
1874     NewEntry =
1875       new (*this) ASTRecordLayout(*this, Builder->getSize(),
1876                                   Builder->Alignment,
1877                                   DataSize,
1878                                   Builder->FieldOffsets.data(),
1879                                   Builder->FieldOffsets.size(),
1880                                   NonVirtualSize,
1881                                   Builder->NonVirtualAlignment,
1882                                   EmptySubobjects.SizeOfLargestEmptySubobject,
1883                                   Builder->PrimaryBase,
1884                                   Builder->PrimaryBaseIsVirtual,
1885                                   Builder->Bases, Builder->VBases);
1886   } else {
1887     RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0);
1888     Builder.Layout(D);
1889
1890     NewEntry =
1891       new (*this) ASTRecordLayout(*this, Builder.getSize(),
1892                                   Builder.Alignment,
1893                                   Builder.getSize(),
1894                                   Builder.FieldOffsets.data(),
1895                                   Builder.FieldOffsets.size());
1896   }
1897
1898   ASTRecordLayouts[D] = NewEntry;
1899
1900   if (getLangOptions().DumpRecordLayouts) {
1901     llvm::errs() << "\n*** Dumping AST Record Layout\n";
1902     DumpRecordLayout(D, llvm::errs());
1903   }
1904
1905   return *NewEntry;
1906 }
1907
1908 const CXXMethodDecl *ASTContext::getKeyFunction(const CXXRecordDecl *RD) {
1909   RD = cast<CXXRecordDecl>(RD->getDefinition());
1910   assert(RD && "Cannot get key function for forward declarations!");
1911
1912   const CXXMethodDecl *&Entry = KeyFunctions[RD];
1913   if (!Entry)
1914     Entry = RecordLayoutBuilder::ComputeKeyFunction(RD);
1915
1916   return Entry;
1917 }
1918
1919 /// getInterfaceLayoutImpl - Get or compute information about the
1920 /// layout of the given interface.
1921 ///
1922 /// \param Impl - If given, also include the layout of the interface's
1923 /// implementation. This may differ by including synthesized ivars.
1924 const ASTRecordLayout &
1925 ASTContext::getObjCLayout(const ObjCInterfaceDecl *D,
1926                           const ObjCImplementationDecl *Impl) const {
1927   assert(!D->isForwardDecl() && "Invalid interface decl!");
1928
1929   // Look up this layout, if already laid out, return what we have.
1930   ObjCContainerDecl *Key =
1931     Impl ? (ObjCContainerDecl*) Impl : (ObjCContainerDecl*) D;
1932   if (const ASTRecordLayout *Entry = ObjCLayouts[Key])
1933     return *Entry;
1934
1935   // Add in synthesized ivar count if laying out an implementation.
1936   if (Impl) {
1937     unsigned SynthCount = CountNonClassIvars(D);
1938     // If there aren't any sythesized ivars then reuse the interface
1939     // entry. Note we can't cache this because we simply free all
1940     // entries later; however we shouldn't look up implementations
1941     // frequently.
1942     if (SynthCount == 0)
1943       return getObjCLayout(D, 0);
1944   }
1945
1946   RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0);
1947   Builder.Layout(D);
1948
1949   const ASTRecordLayout *NewEntry =
1950     new (*this) ASTRecordLayout(*this, Builder.getSize(),
1951                                 Builder.Alignment,
1952                                 Builder.getDataSize(),
1953                                 Builder.FieldOffsets.data(),
1954                                 Builder.FieldOffsets.size());
1955
1956   ObjCLayouts[Key] = NewEntry;
1957
1958   return *NewEntry;
1959 }
1960
1961 static void PrintOffset(llvm::raw_ostream &OS,
1962                         CharUnits Offset, unsigned IndentLevel) {
1963   OS << llvm::format("%4d | ", Offset.getQuantity());
1964   OS.indent(IndentLevel * 2);
1965 }
1966
1967 static void DumpCXXRecordLayout(llvm::raw_ostream &OS,
1968                                 const CXXRecordDecl *RD, const ASTContext &C,
1969                                 CharUnits Offset,
1970                                 unsigned IndentLevel,
1971                                 const char* Description,
1972                                 bool IncludeVirtualBases) {
1973   const ASTRecordLayout &Layout = C.getASTRecordLayout(RD);
1974
1975   PrintOffset(OS, Offset, IndentLevel);
1976   OS << C.getTypeDeclType(const_cast<CXXRecordDecl *>(RD)).getAsString();
1977   if (Description)
1978     OS << ' ' << Description;
1979   if (RD->isEmpty())
1980     OS << " (empty)";
1981   OS << '\n';
1982
1983   IndentLevel++;
1984
1985   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1986
1987   // Vtable pointer.
1988   if (RD->isDynamicClass() && !PrimaryBase) {
1989     PrintOffset(OS, Offset, IndentLevel);
1990     OS << '(' << RD << " vtable pointer)\n";
1991   }
1992   // Dump (non-virtual) bases
1993   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
1994          E = RD->bases_end(); I != E; ++I) {
1995     assert(!I->getType()->isDependentType() &&
1996            "Cannot layout class with dependent bases.");
1997     if (I->isVirtual())
1998       continue;
1999
2000     const CXXRecordDecl *Base =
2001       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
2002
2003     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base);
2004
2005     DumpCXXRecordLayout(OS, Base, C, BaseOffset, IndentLevel,
2006                         Base == PrimaryBase ? "(primary base)" : "(base)",
2007                         /*IncludeVirtualBases=*/false);
2008   }
2009
2010   // Dump fields.
2011   uint64_t FieldNo = 0;
2012   for (CXXRecordDecl::field_iterator I = RD->field_begin(),
2013          E = RD->field_end(); I != E; ++I, ++FieldNo) {
2014     const FieldDecl *Field = *I;
2015     CharUnits FieldOffset = Offset +
2016       C.toCharUnitsFromBits(Layout.getFieldOffset(FieldNo));
2017
2018     if (const RecordType *RT = Field->getType()->getAs<RecordType>()) {
2019       if (const CXXRecordDecl *D = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
2020         DumpCXXRecordLayout(OS, D, C, FieldOffset, IndentLevel,
2021                             Field->getName().data(),
2022                             /*IncludeVirtualBases=*/true);
2023         continue;
2024       }
2025     }
2026
2027     PrintOffset(OS, FieldOffset, IndentLevel);
2028     OS << Field->getType().getAsString() << ' ' << Field << '\n';
2029   }
2030
2031   if (!IncludeVirtualBases)
2032     return;
2033
2034   // Dump virtual bases.
2035   for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
2036          E = RD->vbases_end(); I != E; ++I) {
2037     assert(I->isVirtual() && "Found non-virtual class!");
2038     const CXXRecordDecl *VBase =
2039       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
2040
2041     CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBase);
2042     DumpCXXRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel,
2043                         VBase == PrimaryBase ?
2044                         "(primary virtual base)" : "(virtual base)",
2045                         /*IncludeVirtualBases=*/false);
2046   }
2047
2048   OS << "  sizeof=" << Layout.getSize().getQuantity();
2049   OS << ", dsize=" << Layout.getDataSize().getQuantity();
2050   OS << ", align=" << Layout.getAlignment().getQuantity() << '\n';
2051   OS << "  nvsize=" << Layout.getNonVirtualSize().getQuantity();
2052   OS << ", nvalign=" << Layout.getNonVirtualAlign().getQuantity() << '\n';
2053   OS << '\n';
2054 }
2055
2056 void ASTContext::DumpRecordLayout(const RecordDecl *RD,
2057                                   llvm::raw_ostream &OS) const {
2058   const ASTRecordLayout &Info = getASTRecordLayout(RD);
2059
2060   if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD))
2061     return DumpCXXRecordLayout(OS, CXXRD, *this, CharUnits(), 0, 0,
2062                                /*IncludeVirtualBases=*/true);
2063
2064   OS << "Type: " << getTypeDeclType(RD).getAsString() << "\n";
2065   OS << "Record: ";
2066   RD->dump();
2067   OS << "\nLayout: ";
2068   OS << "<ASTRecordLayout\n";
2069   OS << "  Size:" << toBits(Info.getSize()) << "\n";
2070   OS << "  DataSize:" << toBits(Info.getDataSize()) << "\n";
2071   OS << "  Alignment:" << toBits(Info.getAlignment()) << "\n";
2072   OS << "  FieldOffsets: [";
2073   for (unsigned i = 0, e = Info.getFieldCount(); i != e; ++i) {
2074     if (i) OS << ", ";
2075     OS << Info.getFieldOffset(i);
2076   }
2077   OS << "]>\n";
2078 }