lib/AST/RecordLayoutBuilder.cpp

   1 //=== ASTRecordLayoutBuilder.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 "RecordLayoutBuilder.h"
  11
  12 #include "clang/AST/Attr.h"
  13 #include "clang/AST/Decl.h"
  14 #include "clang/AST/DeclCXX.h"
  15 #include "clang/AST/DeclObjC.h"
  16 #include "clang/AST/Expr.h"
  17 #include "clang/AST/RecordLayout.h"
  18 #include "clang/Basic/TargetInfo.h"
  19 #include <llvm/ADT/SmallSet.h>
  20 #include <llvm/Support/MathExtras.h>
  21
  22 using namespace clang;
  23
  24 ASTRecordLayoutBuilder::ASTRecordLayoutBuilder(ASTContext &Ctx)
  25   : Ctx(Ctx), Size(0), Alignment(8), Packed(false), MaxFieldAlignment(0),
  26   DataSize(0), IsUnion(false), NonVirtualSize(0), NonVirtualAlignment(8),
  27   PrimaryBase(0), PrimaryBaseWasVirtual(false) {}
  28
  29 /// LayoutVtable - Lay out the vtable and set PrimaryBase.
  30 void ASTRecordLayoutBuilder::LayoutVtable(const CXXRecordDecl *RD) {
  31   if (!RD->isDynamicClass()) {
  32     // There is no primary base in this case.
  33     return;
  34   }
  35
  36   SelectPrimaryBase(RD);
  37   if (PrimaryBase == 0) {
  38     int AS = 0;
  39     UpdateAlignment(Ctx.Target.getPointerAlign(AS));
  40     Size += Ctx.Target.getPointerWidth(AS);
  41     DataSize = Size;
  42   }
  43 }
  44
  45 void
  46 ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
  47   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
  48        e = RD->bases_end(); i != e; ++i) {
  49     if (!i->isVirtual()) {
  50       assert(!i->getType()->isDependentType() &&
  51              "Cannot layout class with dependent bases.");
  52       const CXXRecordDecl *Base =
  53         cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
  54       // Skip the PrimaryBase here, as it is laid down first.
  55       if (Base != PrimaryBase || PrimaryBaseWasVirtual)
  56         LayoutBaseNonVirtually(Base, false);
  57     }
  58   }
  59 }
  60
  61 // Helper routines related to the abi definition from:
  62 //   http://www.codesourcery.com/public/cxx-abi/abi.html
  63 //
  64 /// IsNearlyEmpty - Indicates when a class has a vtable pointer, but
  65 /// no other data.
  66 bool ASTRecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) const {
  67   // FIXME: Audit the corners
  68   if (!RD->isDynamicClass())
  69     return false;
  70   const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
  71   if (BaseInfo.getNonVirtualSize() == Ctx.Target.getPointerWidth(0))
  72     return true;
  73   return false;
  74 }
  75
  76 void ASTRecordLayoutBuilder::IdentifyPrimaryBases(const CXXRecordDecl *RD) {
  77   const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
  78
  79   // If the record has a primary base class that is virtual, add it to the set
  80   // of primary bases.
  81   if (Layout.getPrimaryBaseWasVirtual())
  82     IndirectPrimaryBases.insert(Layout.getPrimaryBase());
  83
  84   // Now traverse all bases and find primary bases for them.
  85   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
  86        e = RD->bases_end(); i != e; ++i) {
  87     assert(!i->getType()->isDependentType() &&
  88            "Cannot layout class with dependent bases.");
  89     const CXXRecordDecl *Base =
  90       cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
  91
  92     // Only bases with virtual bases participate in computing the
  93     // indirect primary virtual base classes.
  94     if (Base->getNumVBases())
  95       IdentifyPrimaryBases(Base);
  96   }
  97 }
  98
  99 void
 100 ASTRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD,
 101                                            const CXXRecordDecl *&FirstPrimary) {
 102   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 103          e = RD->bases_end(); i != e; ++i) {
 104     assert(!i->getType()->isDependentType() &&
 105            "Cannot layout class with dependent bases.");
 106     const CXXRecordDecl *Base =
 107       cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 108     if (!i->isVirtual()) {
 109       SelectPrimaryVBase(Base, FirstPrimary);
 110       if (PrimaryBase)
 111         return;
 112       continue;
 113     }
 114     if (IsNearlyEmpty(Base)) {
 115       if (FirstPrimary==0)
 116         FirstPrimary = Base;
 117       if (!IndirectPrimaryBases.count(Base)) {
 118         setPrimaryBase(Base, true);
 119         return;
 120       }
 121     }
 122   }
 123 }
 124
 125 /// SelectPrimaryBase - Selects the primary base for the given class and
 126 /// record that with setPrimaryBase.  We also calculate the IndirectPrimaries.
 127 void ASTRecordLayoutBuilder::SelectPrimaryBase(const CXXRecordDecl *RD) {
 128   // Compute all the primary virtual bases for all of our direct and
 129   // indirect bases, and record all their primary virtual base classes.
 130   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 131        e = RD->bases_end(); i != e; ++i) {
 132     assert(!i->getType()->isDependentType() &&
 133            "Cannot layout class with dependent bases.");
 134     const CXXRecordDecl *Base =
 135       cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 136     IdentifyPrimaryBases(Base);
 137   }
 138
 139   // If the record has a dynamic base class, attempt to choose a primary base
 140   // class. It is the first (in direct base class order) non-virtual dynamic
 141   // base class, if one exists.
 142   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 143        e = RD->bases_end(); i != e; ++i) {
 144     if (!i->isVirtual()) {
 145       const CXXRecordDecl *Base =
 146         cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 147       if (Base->isDynamicClass()) {
 148         // We found it.
 149         setPrimaryBase(Base, false);
 150         return;
 151       }
 152     }
 153   }
 154
 155   // Otherwise, it is the first nearly empty virtual base that is not an
 156   // indirect primary virtual base class, if one exists.
 157
 158   // If we have no virtual bases at this point, bail out as the searching below
 159   // is expensive.
 160   if (RD->getNumVBases() == 0)
 161     return;
 162
 163   // Then we can search for the first nearly empty virtual base itself.
 164   const CXXRecordDecl *FirstPrimary = 0;
 165   SelectPrimaryVBase(RD, FirstPrimary);
 166
 167   // Otherwise if is the first nearly empty virtual base, if one exists,
 168   // otherwise there is no primary base class.
 169   if (!PrimaryBase)
 170     setPrimaryBase(FirstPrimary, true);
 171 }
 172
 173 void ASTRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *RD) {
 174   LayoutBaseNonVirtually(RD, true);
 175 }
 176
 177 void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
 178                                                 const CXXRecordDecl *PB,
 179                                                 int64_t Offset,
 180                                  llvm::SmallSet<const CXXRecordDecl*, 32> &mark,
 181                     llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
 182   for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
 183          e = RD->bases_end(); i != e; ++i) {
 184     assert(!i->getType()->isDependentType() &&
 185            "Cannot layout class with dependent bases.");
 186     const CXXRecordDecl *Base =
 187       cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
 188 #if 0
 189     const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base);
 190     const CXXRecordDecl *PB = L.getPrimaryBase();
 191     if (PB && L.getPrimaryBaseWasVirtual()
 192         && IndirectPrimary.count(PB)) {
 193       int64_t BaseOffset;
 194       // FIXME: calculate this.
 195       BaseOffset = (1<<63) | (1<<31);
 196       VBases.push_back(PB);
 197       VBaseOffsets.push_back(BaseOffset);
 198     }
 199 #endif
 200     int64_t BaseOffset = Offset;;
 201     // FIXME: Calculate BaseOffset.
 202     if (i->isVirtual()) {
 203       if (Base == PB) {
 204         // Only lay things out once.
 205         if (mark.count(Base))
 206           continue;
 207         // Mark it so we don't lay it out twice.
 208         mark.insert(Base);
 209         assert (IndirectPrimary.count(Base) && "IndirectPrimary was wrong");
 210         VBases.push_back(std::make_pair(Base, Offset));
 211       } else if (IndirectPrimary.count(Base)) {
 212         // Someone else will eventually lay this out.
 213         ;
 214       } else {
 215         // Only lay things out once.
 216         if (mark.count(Base))
 217           continue;
 218         // Mark it so we don't lay it out twice.
 219         mark.insert(Base);
 220         LayoutVirtualBase(Base);
 221         BaseOffset = VBases.back().second;
 222       }
 223     }
 224     if (Base->getNumVBases()) {
 225       const ASTRecordLayout &L = Ctx.getASTRecordLayout(Base);
 226       const CXXRecordDecl *PB = L.getPrimaryBase();
 227       LayoutVirtualBases(Base, PB, BaseOffset, mark, IndirectPrimary);
 228     }
 229   }
 230 }
 231
 232 bool ASTRecordLayoutBuilder::canPlaceRecordAtOffset(const CXXRecordDecl *RD,
 233                                                     uint64_t Offset) const {
 234   // Look for an empty class with the same type at the same offset.
 235   for (EmptyClassOffsetsTy::const_iterator I =
 236         EmptyClassOffsets.lower_bound(Offset),
 237        E = EmptyClassOffsets.upper_bound(Offset); I != E; ++I) {
 238
 239     if (I->second == RD)
 240       return false;
 241   }
 242
 243   const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);
 244
 245   // Check bases.
 246   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 247        E = RD->bases_end(); I != E; ++I) {
 248     assert(!I->getType()->isDependentType() &&
 249            "Cannot layout class with dependent bases.");
 250     if (I->isVirtual())
 251       continue;
 252
 253     const CXXRecordDecl *Base =
 254       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 255
 256     uint64_t BaseClassOffset = Info.getBaseClassOffset(Base);
 257
 258     if (!canPlaceRecordAtOffset(Base, Offset + BaseClassOffset))
 259       return false;
 260   }
 261
 262   // Check fields.
 263   unsigned FieldNo = 0;
 264   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 265        I != E; ++I, ++FieldNo) {
 266     const FieldDecl *FD = *I;
 267
 268     uint64_t FieldOffset = Info.getFieldOffset(FieldNo);
 269
 270     if (!canPlaceFieldAtOffset(FD, Offset + FieldOffset))
 271       return false;
 272   }
 273
 274   // FIXME: virtual bases.
 275   return true;
 276 }
 277
 278 bool ASTRecordLayoutBuilder::canPlaceFieldAtOffset(const FieldDecl *FD,
 279                                                    uint64_t Offset) const {
 280   QualType T = FD->getType();
 281   if (const RecordType *RT = T->getAs<RecordType>()) {
 282     if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl()))
 283       return canPlaceRecordAtOffset(RD, Offset);
 284   }
 285
 286   if (const ConstantArrayType *AT = Ctx.getAsConstantArrayType(T)) {
 287     QualType ElemTy = Ctx.getBaseElementType(AT);
 288     const RecordType *RT = ElemTy->getAs<RecordType>();
 289     if (!RT)
 290       return true;
 291     const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl());
 292     if (!RD)
 293       return true;
 294
 295     const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);
 296
 297     uint64_t NumElements = Ctx.getConstantArrayElementCount(AT);
 298     unsigned ElementOffset = Offset;
 299     for (uint64_t I = 0; I != NumElements; ++I) {
 300       if (!canPlaceRecordAtOffset(RD, ElementOffset))
 301         return false;
 302
 303       ElementOffset += Info.getSize();
 304     }
 305   }
 306
 307   return true;
 308 }
 309
 310 void ASTRecordLayoutBuilder::UpdateEmptyClassOffsets(const CXXRecordDecl *RD,
 311                                                      uint64_t Offset) {
 312   if (RD->isEmpty())
 313     EmptyClassOffsets.insert(std::make_pair(Offset, RD));
 314
 315   const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);
 316
 317   // Update bases.
 318   for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
 319        E = RD->bases_end(); I != E; ++I) {
 320     assert(!I->getType()->isDependentType() &&
 321            "Cannot layout class with dependent bases.");
 322     if (I->isVirtual())
 323       continue;
 324
 325     const CXXRecordDecl *Base =
 326       cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
 327
 328     uint64_t BaseClassOffset = Info.getBaseClassOffset(Base);
 329     UpdateEmptyClassOffsets(Base, Offset + BaseClassOffset);
 330   }
 331
 332   // Update fields.
 333   unsigned FieldNo = 0;
 334   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
 335        I != E; ++I, ++FieldNo) {
 336     const FieldDecl *FD = *I;
 337
 338     uint64_t FieldOffset = Info.getFieldOffset(FieldNo);
 339     UpdateEmptyClassOffsets(FD, Offset + FieldOffset);
 340   }
 341
 342   // FIXME: Update virtual bases.
 343 }
 344
 345 void
 346 ASTRecordLayoutBuilder::UpdateEmptyClassOffsets(const FieldDecl *FD,
 347                                                 uint64_t Offset) {
 348   QualType T = FD->getType();
 349
 350   if (const RecordType *RT = T->getAs<RecordType>()) {
 351     if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
 352       UpdateEmptyClassOffsets(RD, Offset);
 353       return;
 354     }
 355   }
 356
 357   if (const ConstantArrayType *AT = Ctx.getAsConstantArrayType(T)) {
 358     QualType ElemTy = Ctx.getBaseElementType(AT);
 359     const RecordType *RT = ElemTy->getAs<RecordType>();
 360     if (!RT)
 361       return;
 362     const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl());
 363     if (!RD)
 364       return;
 365
 366     const ASTRecordLayout &Info = Ctx.getASTRecordLayout(RD);
 367
 368     uint64_t NumElements = Ctx.getConstantArrayElementCount(AT);
 369     unsigned ElementOffset = Offset;
 370
 371     for (uint64_t I = 0; I != NumElements; ++I) {
 372       UpdateEmptyClassOffsets(RD, ElementOffset);
 373       ElementOffset += Info.getSize();
 374     }
 375   }
 376 }
 377
 378 uint64_t ASTRecordLayoutBuilder::LayoutBase(const CXXRecordDecl *RD) {
 379   const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
 380
 381   // If we have an empty base class, try to place it at offset 0.
 382   if (RD->isEmpty() && canPlaceRecordAtOffset(RD, 0)) {
 383     // We were able to place the class at offset 0.
 384     UpdateEmptyClassOffsets(RD, 0);
 385
 386     Size = std::max(Size, BaseInfo.getSize());
 387
 388     return 0;
 389   }
 390
 391   unsigned BaseAlign = BaseInfo.getNonVirtualAlign();
 392
 393   // Round up the current record size to the base's alignment boundary.
 394   uint64_t Offset = llvm::RoundUpToAlignment(DataSize, BaseAlign);
 395
 396   // Try to place the base.
 397   while (true) {
 398     if (canPlaceRecordAtOffset(RD, Offset))
 399       break;
 400
 401     Offset += BaseAlign;
 402   }
 403
 404   if (!RD->isEmpty()) {
 405     // Update the data size.
 406     DataSize = Offset + BaseInfo.getNonVirtualSize();
 407
 408     Size = std::max(Size, DataSize);
 409   } else
 410     Size = std::max(Size, Offset + BaseInfo.getSize());
 411
 412   // Remember max struct/class alignment.
 413   UpdateAlignment(BaseAlign);
 414
 415   UpdateEmptyClassOffsets(RD, Offset);
 416   return Offset;
 417 }
 418
 419 void ASTRecordLayoutBuilder::LayoutBaseNonVirtually(const CXXRecordDecl *RD,
 420   bool IsVirtualBase) {
 421   // Layout the base.
 422   unsigned Offset = LayoutBase(RD);
 423
 424   // Add base class offsets.
 425   if (IsVirtualBase)
 426     VBases.push_back(std::make_pair(RD, Offset));
 427   else
 428     Bases.push_back(std::make_pair(RD, Offset));
 429
 430 #if 0
 431   // And now add offsets for all our primary virtual bases as well, so
 432   // they all have offsets.
 433   const ASTRecordLayout *L = &BaseInfo;
 434   const CXXRecordDecl *PB = L->getPrimaryBase();
 435   while (PB) {
 436     if (L->getPrimaryBaseWasVirtual()) {
 437       VBases.push_back(PB);
 438       VBaseOffsets.push_back(Size);
 439     }
 440     PB = L->getPrimaryBase();
 441     if (PB)
 442       L = &Ctx.getASTRecordLayout(PB);
 443   }
 444 #endif
 445 }
 446
 447 void ASTRecordLayoutBuilder::Layout(const RecordDecl *D) {
 448   IsUnion = D->isUnion();
 449
 450   Packed = D->hasAttr<PackedAttr>();
 451
 452   // The #pragma pack attribute specifies the maximum field alignment.
 453   if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
 454     MaxFieldAlignment = PPA->getAlignment();
 455
 456   if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
 457     UpdateAlignment(AA->getAlignment());
 458
 459   // If this is a C++ class, lay out the vtable and the non-virtual bases.
 460   const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D);
 461   if (RD) {
 462     LayoutVtable(RD);
 463     // PrimaryBase goes first.
 464     if (PrimaryBase) {
 465       if (PrimaryBaseWasVirtual)
 466         IndirectPrimaryBases.insert(PrimaryBase);
 467       LayoutBaseNonVirtually(PrimaryBase, PrimaryBaseWasVirtual);
 468     }
 469     LayoutNonVirtualBases(RD);
 470   }
 471
 472   LayoutFields(D);
 473
 474   NonVirtualSize = Size;
 475   NonVirtualAlignment = Alignment;
 476
 477   if (RD) {
 478     llvm::SmallSet<const CXXRecordDecl*, 32> mark;
 479     LayoutVirtualBases(RD, PrimaryBase, 0, mark, IndirectPrimaryBases);
 480   }
 481
 482   // Finally, round the size of the total struct up to the alignment of the
 483   // struct itself.
 484   FinishLayout();
 485 }
 486
 487 void ASTRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D,
 488                                     const ObjCImplementationDecl *Impl) {
 489   if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
 490     const ASTRecordLayout &SL = Ctx.getASTObjCInterfaceLayout(SD);
 491
 492     UpdateAlignment(SL.getAlignment());
 493
 494     // We start laying out ivars not at the end of the superclass
 495     // structure, but at the next byte following the last field.
 496     Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8);
 497     DataSize = Size;
 498   }
 499
 500   Packed = D->hasAttr<PackedAttr>();
 501
 502   // The #pragma pack attribute specifies the maximum field alignment.
 503   if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
 504     MaxFieldAlignment = PPA->getAlignment();
 505
 506   if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
 507     UpdateAlignment(AA->getAlignment());
 508
 509   // Layout each ivar sequentially.
 510   llvm::SmallVector<ObjCIvarDecl*, 16> Ivars;
 511   Ctx.ShallowCollectObjCIvars(D, Ivars, Impl);
 512   for (unsigned i = 0, e = Ivars.size(); i != e; ++i)
 513     LayoutField(Ivars[i]);
 514
 515   // Finally, round the size of the total struct up to the alignment of the
 516   // struct itself.
 517   FinishLayout();
 518 }
 519
 520 void ASTRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
 521   // Layout each field, for now, just sequentially, respecting alignment.  In
 522   // the future, this will need to be tweakable by targets.
 523   for (RecordDecl::field_iterator Field = D->field_begin(),
 524        FieldEnd = D->field_end(); Field != FieldEnd; ++Field)
 525     LayoutField(*Field);
 526 }
 527
 528 void ASTRecordLayoutBuilder::LayoutField(const FieldDecl *D) {
 529   bool FieldPacked = Packed;
 530   uint64_t FieldOffset = IsUnion ? 0 : DataSize;
 531   uint64_t FieldSize;
 532   unsigned FieldAlign;
 533
 534   FieldPacked |= D->hasAttr<PackedAttr>();
 535
 536   if (const Expr *BitWidthExpr = D->getBitWidth()) {
 537     // TODO: Need to check this algorithm on other targets!
 538     //       (tested on Linux-X86)
 539     FieldSize = BitWidthExpr->EvaluateAsInt(Ctx).getZExtValue();
 540
 541     std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
 542     uint64_t TypeSize = FieldInfo.first;
 543
 544     FieldAlign = FieldInfo.second;
 545
 546     if (FieldPacked)
 547       FieldAlign = 1;
 548     if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
 549       FieldAlign = std::max(FieldAlign, AA->getAlignment());
 550     // The maximum field alignment overrides the aligned attribute.
 551     if (MaxFieldAlignment)
 552       FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
 553
 554     // Check if we need to add padding to give the field the correct
 555     // alignment.
 556     if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)
 557       FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1);
 558
 559     // Padding members don't affect overall alignment
 560     if (!D->getIdentifier())
 561       FieldAlign = 1;
 562   } else {
 563     if (D->getType()->isIncompleteArrayType()) {
 564       // This is a flexible array member; we can't directly
 565       // query getTypeInfo about these, so we figure it out here.
 566       // Flexible array members don't have any size, but they
 567       // have to be aligned appropriately for their element type.
 568       FieldSize = 0;
 569       const ArrayType* ATy = Ctx.getAsArrayType(D->getType());
 570       FieldAlign = Ctx.getTypeAlign(ATy->getElementType());
 571     } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
 572       unsigned AS = RT->getPointeeType().getAddressSpace();
 573       FieldSize = Ctx.Target.getPointerWidth(AS);
 574       FieldAlign = Ctx.Target.getPointerAlign(AS);
 575     } else {
 576       std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
 577       FieldSize = FieldInfo.first;
 578       FieldAlign = FieldInfo.second;
 579     }
 580
 581     if (FieldPacked)
 582       FieldAlign = 8;
 583     if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
 584       FieldAlign = std::max(FieldAlign, AA->getAlignment());
 585     // The maximum field alignment overrides the aligned attribute.
 586     if (MaxFieldAlignment)
 587       FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
 588
 589     // Round up the current record size to the field's alignment boundary.
 590     FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
 591
 592     if (!IsUnion) {
 593       while (true) {
 594         // Check if we can place the field at this offset.
 595         if (canPlaceFieldAtOffset(D, FieldOffset))
 596           break;
 597
 598         // We couldn't place the field at the offset. Try again at a new offset.
 599         FieldOffset += FieldAlign;
 600       }
 601
 602       UpdateEmptyClassOffsets(D, FieldOffset);
 603     }
 604   }
 605
 606   // Place this field at the current location.
 607   FieldOffsets.push_back(FieldOffset);
 608
 609   // Reserve space for this field.
 610   if (IsUnion)
 611     Size = std::max(Size, FieldSize);
 612   else
 613     Size = FieldOffset + FieldSize;
 614
 615   // Update the data size.
 616   DataSize = Size;
 617
 618   // Remember max struct/class alignment.
 619   UpdateAlignment(FieldAlign);
 620 }
 621
 622 void ASTRecordLayoutBuilder::FinishLayout() {
 623   // In C++, records cannot be of size 0.
 624   if (Ctx.getLangOptions().CPlusPlus && Size == 0)
 625     Size = 8;
 626   // Finally, round the size of the record up to the alignment of the
 627   // record itself.
 628   Size = (Size + (Alignment-1)) & ~(Alignment-1);
 629 }
 630
 631 void ASTRecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) {
 632   if (NewAlignment <= Alignment)
 633     return;
 634
 635   assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2"));
 636
 637   Alignment = NewAlignment;
 638 }
 639
 640 const ASTRecordLayout *
 641 ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
 642                                       const RecordDecl *D) {
 643   ASTRecordLayoutBuilder Builder(Ctx);
 644
 645   Builder.Layout(D);
 646
 647   if (!isa<CXXRecordDecl>(D))
 648     return new ASTRecordLayout(Builder.Size, Builder.Alignment, Builder.Size,
 649                                Builder.FieldOffsets.data(),
 650                                Builder.FieldOffsets.size());
 651
 652   // FIXME: This is not always correct. See the part about bitfields at
 653   // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info.
 654   // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout.
 655   bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD();
 656
 657   // FIXME: This should be done in FinalizeLayout.
 658   uint64_t DataSize =
 659     IsPODForThePurposeOfLayout ? Builder.Size : Builder.DataSize;
 660   uint64_t NonVirtualSize =
 661     IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize;
 662
 663   return new ASTRecordLayout(Builder.Size, Builder.Alignment, DataSize,
 664                              Builder.FieldOffsets.data(),
 665                              Builder.FieldOffsets.size(),
 666                              NonVirtualSize,
 667                              Builder.NonVirtualAlignment,
 668                              Builder.PrimaryBase,
 669                              Builder.PrimaryBaseWasVirtual,
 670                              Builder.Bases.data(),
 671                              Builder.Bases.size(),
 672                              Builder.VBases.data(),
 673                              Builder.VBases.size());
 674 }
 675
 676 const ASTRecordLayout *
 677 ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
 678                                       const ObjCInterfaceDecl *D,
 679                                       const ObjCImplementationDecl *Impl) {
 680   ASTRecordLayoutBuilder Builder(Ctx);
 681
 682   Builder.Layout(D, Impl);
 683
 684   return new ASTRecordLayout(Builder.Size, Builder.Alignment,
 685                              Builder.DataSize,
 686                              Builder.FieldOffsets.data(),
 687                              Builder.FieldOffsets.size());
 688 }