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