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