RecordLayoutBuilder.cpp revision ffa6d1ca26643972b8b6bf394e0cc1cb757643ef 
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/Support/Format.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/Support/MathExtras.h"
21
22using namespace clang;
23
24ASTRecordLayoutBuilder::ASTRecordLayoutBuilder(ASTContext &Ctx)
25  : Ctx(Ctx), Size(0), Alignment(8), Packed(false), UnfilledBitsInLastByte(0),
26    MaxFieldAlignment(0), DataSize(0), IsUnion(false), NonVirtualSize(0),
27    NonVirtualAlignment(8), FirstNearlyEmptyVBase(0) { }
28
29/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but
30/// no other data.
31bool ASTRecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) const {
32  // FIXME: Audit the corners
33  if (!RD->isDynamicClass())
34    return false;
35  const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
36  if (BaseInfo.getNonVirtualSize() == Ctx.Target.getPointerWidth(0))
37    return true;
38  return false;
39}
40
41void ASTRecordLayoutBuilder::IdentifyPrimaryBases(const CXXRecordDecl *RD) {
42  const ASTRecordLayout::PrimaryBaseInfo &BaseInfo =
43    Ctx.getASTRecordLayout(RD).getPrimaryBaseInfo();
44
45  // If the record has a primary base class that is virtual, add it to the set
46  // of primary bases.
47  if (BaseInfo.isVirtual())
48    IndirectPrimaryBases.insert(BaseInfo.getBase());
49
50  // Now traverse all bases and find primary bases for them.
51  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
52         e = RD->bases_end(); i != e; ++i) {
53    assert(!i->getType()->isDependentType() &&
54           "Cannot layout class with dependent bases.");
55    const CXXRecordDecl *Base =
56      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
57
58    // Only bases with virtual bases participate in computing the
59    // indirect primary virtual base classes.
60    if (Base->getNumVBases())
61      IdentifyPrimaryBases(Base);
62  }
63}
64
65void
66ASTRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) {
67  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
68         E = RD->bases_end(); I != E; ++I) {
69    assert(!I->getType()->isDependentType() &&
70           "Cannot layout class with dependent bases.");
71
72    const CXXRecordDecl *Base =
73      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
74
75    // Check if this is a nearly empty virtual base.
76    if (I->isVirtual() && IsNearlyEmpty(Base)) {
77      // If it's not an indirect primary base, then we've found our primary
78      // base.
79      if (!IndirectPrimaryBases.count(Base)) {
80        PrimaryBase = ASTRecordLayout::PrimaryBaseInfo(Base,
81                                                       /*IsVirtual=*/true);
82        return;
83      }
84
85      // Is this the first nearly empty virtual base?
86      if (!FirstNearlyEmptyVBase)
87        FirstNearlyEmptyVBase = Base;
88    }
89
90    SelectPrimaryVBase(Base);
91    if (PrimaryBase.getBase())
92      return;
93  }
94}
95
96/// DeterminePrimaryBase - Determine the primary base of the given class.
97void ASTRecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) {
98  // If the class isn't dynamic, it won't have a primary base.
99  if (!RD->isDynamicClass())
100    return;
101
102  // Compute all the primary virtual bases for all of our direct and
103  // indirect bases, and record all their primary virtual base classes.
104  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
105         e = RD->bases_end(); i != e; ++i) {
106    assert(!i->getType()->isDependentType() &&
107           "Cannot lay out class with dependent bases.");
108    const CXXRecordDecl *Base =
109      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
110    IdentifyPrimaryBases(Base);
111  }
112
113  // If the record has a dynamic base class, attempt to choose a primary base
114  // class. It is the first (in direct base class order) non-virtual dynamic
115  // base class, if one exists.
116  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
117         e = RD->bases_end(); i != e; ++i) {
118    // Ignore virtual bases.
119    if (i->isVirtual())
120      continue;
121
122    const CXXRecordDecl *Base =
123      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
124
125    if (Base->isDynamicClass()) {
126      // We found it.
127      PrimaryBase = ASTRecordLayout::PrimaryBaseInfo(Base, /*IsVirtual=*/false);
128      return;
129    }
130  }
131
132  // Otherwise, it is the first nearly empty virtual base that is not an
133  // indirect primary virtual base class, if one exists.
134  if (RD->getNumVBases() != 0) {
135    SelectPrimaryVBase(RD);
136    if (PrimaryBase.getBase())
137      return;
138  }
139
140  // Otherwise, it is the first nearly empty virtual base that is not an
141  // indirect primary virtual base class, if one exists.
142  if (FirstNearlyEmptyVBase) {
143    PrimaryBase = ASTRecordLayout::PrimaryBaseInfo(FirstNearlyEmptyVBase,
144                                                   /*IsVirtual=*/true);
145    return;
146  }
147
148  // Otherwise there is no primary base class.
149  assert(!PrimaryBase.getBase() && "Should not get here with a primary base!");
150
151  // Allocate the virtual table pointer at offset zero.
152  assert(DataSize == 0 && "Vtable pointer must be at offset zero!");
153
154  // Update the size.
155  Size += Ctx.Target.getPointerWidth(0);
156  DataSize = Size;
157
158  // Update the alignment.
159  UpdateAlignment(Ctx.Target.getPointerAlign(0));
160}
161
162void
163ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
164  // First, determine the primary base class.
165  DeterminePrimaryBase(RD);
166
167  // If we have a primary base class, lay it out.
168  if (const CXXRecordDecl *Base = PrimaryBase.getBase()) {
169    if (PrimaryBase.isVirtual()) {
170      // We have a virtual primary base, insert it as an indirect primary base.
171      IndirectPrimaryBases.insert(Base);
172
173      assert(!VisitedVirtualBases.count(Base) && "vbase already visited!");
174      VisitedVirtualBases.insert(Base);
175
176      LayoutVirtualBase(Base);
177    } else
178      LayoutNonVirtualBase(Base);
179  }
180
181  // Now lay out the non-virtual bases.
182  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
183         E = RD->bases_end(); I != E; ++I) {
184
185    // Ignore virtual bases.
186    if (I->isVirtual())
187      continue;
188
189    const CXXRecordDecl *Base =
190      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
191
192    // Skip the primary base.
193    if (Base == PrimaryBase.getBase() && !PrimaryBase.isVirtual())
194      continue;
195
196    // Lay out the base.
197    LayoutNonVirtualBase(Base);
198  }
199}
200
201void ASTRecordLayoutBuilder::LayoutNonVirtualBase(const CXXRecordDecl *RD) {
202  // Layout the base.
203  uint64_t Offset = LayoutBase(RD);
204
205  // Add its base class offset.
206  if (!Bases.insert(std::make_pair(RD, Offset)).second)
207    assert(false && "Added same base offset more than once!");
208}
209
210void
211ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
212                                           uint64_t Offset,
213                                           const CXXRecordDecl *MostDerivedClass) {
214  const CXXRecordDecl *PrimaryBase;
215  bool PrimaryBaseIsVirtual;
216
217  if (MostDerivedClass == RD) {
218    PrimaryBase = this->PrimaryBase.getBase();
219    PrimaryBaseIsVirtual = this->PrimaryBase.isVirtual();
220  } else {
221    const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
222    PrimaryBase = Layout.getPrimaryBase();
223    PrimaryBaseIsVirtual = Layout.getPrimaryBaseWasVirtual();
224  }
225
226  // Check the primary base first.
227  if (PrimaryBase && PrimaryBaseIsVirtual &&
228      VisitedVirtualBases.insert(PrimaryBase)) {
229    assert(!VBases.count(PrimaryBase) && "vbase offset already exists!");
230
231    VBases.insert(std::make_pair(PrimaryBase, Offset));
232  }
233
234  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
235         E = RD->bases_end(); I != E; ++I) {
236    assert(!I->getType()->isDependentType() &&
237           "Cannot layout class with dependent bases.");
238
239    const CXXRecordDecl *Base =
240      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
241
242    if (I->isVirtual()) {
243      if (PrimaryBase != Base || !PrimaryBaseIsVirtual) {
244        bool IndirectPrimaryBase = IndirectPrimaryBases.count(Base);
245
246        // Only lay out the virtual base if it's not an indirect primary base.
247        if (!IndirectPrimaryBase) {
248          // Only visit virtual bases once.
249          if (!VisitedVirtualBases.insert(Base))
250            continue;
251
252          LayoutVirtualBase(Base);
253        }
254      }
255    }
256
257    if (!Base->getNumVBases()) {
258      // This base isn't interesting since it doesn't have any virtual bases.
259      continue;
260    }
261
262    // Compute the offset of this base.
263    uint64_t BaseOffset;
264
265    if (I->isVirtual()) {
266      // If we don't know this vbase yet, don't visit it. It will be visited
267      // later.
268      if (!VBases.count(Base))
269        continue;
270
271      // We want the vbase offset from the class we're currently laying out.
272      BaseOffset = VBases[Base];
273    } else if (RD == MostDerivedClass) {
274      // We want the base offset from the class we're currently laying out.
275      assert(Bases.count(Base) && "Did not find base!");
276      BaseOffset = Bases[Base];
277    } else {
278      const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
279      BaseOffset = Offset + Layout.getBaseClassOffset(Base);
280    }
281
282    LayoutVirtualBases(Base, BaseOffset, MostDerivedClass);
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 this is a C++ class, lay out its virtual bases.
505  if (RD)
506    LayoutVirtualBases(RD, 0, RD);
507
508  // Finally, round the size of the total struct up to the alignment of the
509  // struct itself.
510  FinishLayout();
511
512#ifndef NDEBUG
513  if (RD) {
514    // Check that we have base offsets for all bases.
515    for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
516         E = RD->bases_end(); I != E; ++I) {
517      if (I->isVirtual())
518        continue;
519
520      const CXXRecordDecl *BaseDecl =
521        cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
522
523      assert(Bases.count(BaseDecl) && "Did not find base offset!");
524    }
525
526    // And all virtual bases.
527    for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
528         E = RD->vbases_end(); I != E; ++I) {
529      const CXXRecordDecl *BaseDecl =
530        cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
531
532      assert(VBases.count(BaseDecl) && "Did not find base offset!");
533    }
534  }
535#endif
536}
537
538// FIXME. Impl is no longer needed.
539void ASTRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D,
540                                    const ObjCImplementationDecl *Impl) {
541  if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
542    const ASTRecordLayout &SL = Ctx.getASTObjCInterfaceLayout(SD);
543
544    UpdateAlignment(SL.getAlignment());
545
546    // We start laying out ivars not at the end of the superclass
547    // structure, but at the next byte following the last field.
548    Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8);
549    DataSize = Size;
550  }
551
552  Packed = D->hasAttr<PackedAttr>();
553
554  // The #pragma pack attribute specifies the maximum field alignment.
555  if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
556    MaxFieldAlignment = PPA->getAlignment();
557
558  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
559    UpdateAlignment(AA->getMaxAlignment());
560  // Layout each ivar sequentially.
561  llvm::SmallVector<ObjCIvarDecl*, 16> Ivars;
562  Ctx.ShallowCollectObjCIvars(D, Ivars);
563  for (unsigned i = 0, e = Ivars.size(); i != e; ++i)
564    LayoutField(Ivars[i]);
565
566  // Finally, round the size of the total struct up to the alignment of the
567  // struct itself.
568  FinishLayout();
569}
570
571void ASTRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
572  // Layout each field, for now, just sequentially, respecting alignment.  In
573  // the future, this will need to be tweakable by targets.
574  for (RecordDecl::field_iterator Field = D->field_begin(),
575         FieldEnd = D->field_end(); Field != FieldEnd; ++Field)
576    LayoutField(*Field);
577}
578
579void ASTRecordLayoutBuilder::LayoutBitField(const FieldDecl *D) {
580  bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
581  uint64_t FieldOffset = IsUnion ? 0 : (DataSize - UnfilledBitsInLastByte);
582  uint64_t FieldSize = D->getBitWidth()->EvaluateAsInt(Ctx).getZExtValue();
583
584  std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
585  uint64_t TypeSize = FieldInfo.first;
586  unsigned FieldAlign = FieldInfo.second;
587
588  if (FieldPacked || !Ctx.Target.useBitfieldTypeAlignment())
589    FieldAlign = 1;
590  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
591    FieldAlign = std::max(FieldAlign, AA->getMaxAlignment());
592
593  // The maximum field alignment overrides the aligned attribute.
594  if (MaxFieldAlignment)
595    FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
596
597  // Check if we need to add padding to give the field the correct alignment.
598  if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)
599    FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1);
600
601  // Padding members don't affect overall alignment.
602  if (!D->getIdentifier())
603    FieldAlign = 1;
604
605  // Place this field at the current location.
606  FieldOffsets.push_back(FieldOffset);
607
608  // Update DataSize to include the last byte containing (part of) the bitfield.
609  if (IsUnion) {
610    // FIXME: I think FieldSize should be TypeSize here.
611    DataSize = std::max(DataSize, FieldSize);
612  } else {
613    uint64_t NewSizeInBits = FieldOffset + FieldSize;
614
615    DataSize = llvm::RoundUpToAlignment(NewSizeInBits, 8);
616    UnfilledBitsInLastByte = DataSize - NewSizeInBits;
617  }
618
619  // Update the size.
620  Size = std::max(Size, DataSize);
621
622  // Remember max struct/class alignment.
623  UpdateAlignment(FieldAlign);
624}
625
626void ASTRecordLayoutBuilder::LayoutField(const FieldDecl *D) {
627  if (D->isBitField()) {
628    LayoutBitField(D);
629    return;
630  }
631
632  // Reset the unfilled bits.
633  UnfilledBitsInLastByte = 0;
634
635  bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
636  uint64_t FieldOffset = IsUnion ? 0 : DataSize;
637  uint64_t FieldSize;
638  unsigned FieldAlign;
639
640  if (D->getType()->isIncompleteArrayType()) {
641    // This is a flexible array member; we can't directly
642    // query getTypeInfo about these, so we figure it out here.
643    // Flexible array members don't have any size, but they
644    // have to be aligned appropriately for their element type.
645    FieldSize = 0;
646    const ArrayType* ATy = Ctx.getAsArrayType(D->getType());
647    FieldAlign = Ctx.getTypeAlign(ATy->getElementType());
648  } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
649    unsigned AS = RT->getPointeeType().getAddressSpace();
650    FieldSize = Ctx.Target.getPointerWidth(AS);
651    FieldAlign = Ctx.Target.getPointerAlign(AS);
652  } else {
653    std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
654    FieldSize = FieldInfo.first;
655    FieldAlign = FieldInfo.second;
656  }
657
658  if (FieldPacked)
659    FieldAlign = 8;
660  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
661    FieldAlign = std::max(FieldAlign, AA->getMaxAlignment());
662
663  // The maximum field alignment overrides the aligned attribute.
664  if (MaxFieldAlignment)
665    FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
666
667  // Round up the current record size to the field's alignment boundary.
668  FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
669
670  if (!IsUnion) {
671    while (true) {
672      // Check if we can place the field at this offset.
673      if (canPlaceFieldAtOffset(D, FieldOffset))
674        break;
675
676      // We couldn't place the field at the offset. Try again at a new offset.
677      FieldOffset += FieldAlign;
678    }
679
680    UpdateEmptyClassOffsets(D, FieldOffset);
681  }
682
683  // Place this field at the current location.
684  FieldOffsets.push_back(FieldOffset);
685
686  // Reserve space for this field.
687  if (IsUnion)
688    Size = std::max(Size, FieldSize);
689  else
690    Size = FieldOffset + FieldSize;
691
692  // Update the data size.
693  DataSize = Size;
694
695  // Remember max struct/class alignment.
696  UpdateAlignment(FieldAlign);
697}
698
699void ASTRecordLayoutBuilder::FinishLayout() {
700  // In C++, records cannot be of size 0.
701  if (Ctx.getLangOptions().CPlusPlus && Size == 0)
702    Size = 8;
703  // Finally, round the size of the record up to the alignment of the
704  // record itself.
705  Size = llvm::RoundUpToAlignment(Size, Alignment);
706}
707
708void ASTRecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) {
709  if (NewAlignment <= Alignment)
710    return;
711
712  assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2"));
713
714  Alignment = NewAlignment;
715}
716
717const ASTRecordLayout *
718ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
719                                      const RecordDecl *D) {
720  ASTRecordLayoutBuilder Builder(Ctx);
721
722  Builder.Layout(D);
723
724  if (!isa<CXXRecordDecl>(D))
725    return new (Ctx) ASTRecordLayout(Ctx, Builder.Size, Builder.Alignment,
726                                     Builder.Size,
727                                     Builder.FieldOffsets.data(),
728                                     Builder.FieldOffsets.size());
729
730  // FIXME: This is not always correct. See the part about bitfields at
731  // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info.
732  // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout.
733  bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD();
734
735  // FIXME: This should be done in FinalizeLayout.
736  uint64_t DataSize =
737    IsPODForThePurposeOfLayout ? Builder.Size : Builder.DataSize;
738  uint64_t NonVirtualSize =
739    IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize;
740
741  return new (Ctx) ASTRecordLayout(Ctx, Builder.Size, Builder.Alignment,
742                                   DataSize, Builder.FieldOffsets.data(),
743                                   Builder.FieldOffsets.size(),
744                                   NonVirtualSize,
745                                   Builder.NonVirtualAlignment,
746                                   Builder.PrimaryBase,
747                                   Builder.Bases, Builder.VBases);
748}
749
750const ASTRecordLayout *
751ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
752                                      const ObjCInterfaceDecl *D,
753                                      const ObjCImplementationDecl *Impl) {
754  ASTRecordLayoutBuilder Builder(Ctx);
755
756  Builder.Layout(D, Impl);
757
758  return new (Ctx) ASTRecordLayout(Ctx, Builder.Size, Builder.Alignment,
759                                   Builder.DataSize,
760                                   Builder.FieldOffsets.data(),
761                                   Builder.FieldOffsets.size());
762}
763
764const CXXMethodDecl *
765ASTRecordLayoutBuilder::ComputeKeyFunction(const CXXRecordDecl *RD) {
766  assert(RD->isDynamicClass() && "Class does not have any virtual methods!");
767
768  // If a class isnt' polymorphic it doesn't have a key function.
769  if (!RD->isPolymorphic())
770    return 0;
771
772  // A class inside an anonymous namespace doesn't have a key function.  (Or
773  // at least, there's no point to assigning a key function to such a class;
774  // this doesn't affect the ABI.)
775  if (RD->isInAnonymousNamespace())
776    return 0;
777
778  for (CXXRecordDecl::method_iterator I = RD->method_begin(),
779         E = RD->method_end(); I != E; ++I) {
780    const CXXMethodDecl *MD = *I;
781
782    if (!MD->isVirtual())
783      continue;
784
785    if (MD->isPure())
786      continue;
787
788    // Ignore implicit member functions, they are always marked as inline, but
789    // they don't have a body until they're defined.
790    if (MD->isImplicit())
791      continue;
792
793    if (MD->isInlineSpecified())
794      continue;
795
796    if (MD->hasInlineBody())
797      continue;
798
799    // We found it.
800    return MD;
801  }
802
803  return 0;
804}
805
806static void PrintOffset(llvm::raw_ostream &OS,
807                        uint64_t Offset, unsigned IndentLevel) {
808  OS << llvm::format("%4d | ", Offset);
809  OS.indent(IndentLevel * 2);
810}
811
812static void DumpCXXRecordLayout(llvm::raw_ostream &OS,
813                                const CXXRecordDecl *RD, ASTContext &C,
814                                uint64_t Offset,
815                                unsigned IndentLevel,
816                                const char* Description,
817                                bool IncludeVirtualBases) {
818  const ASTRecordLayout &Info = C.getASTRecordLayout(RD);
819
820  PrintOffset(OS, Offset, IndentLevel);
821  OS << C.getTypeDeclType((CXXRecordDecl *)RD).getAsString();
822  if (Description)
823    OS << ' ' << Description;
824  if (RD->isEmpty())
825    OS << " (empty)";
826  OS << '\n';
827
828  IndentLevel++;
829
830  const CXXRecordDecl *PrimaryBase = Info.getPrimaryBase();
831
832  // Vtable pointer.
833  if (RD->isDynamicClass() && !PrimaryBase) {
834    PrintOffset(OS, Offset, IndentLevel);
835    OS << '(' << RD->getNameAsString() << " vtable pointer)\n";
836  }
837  // Dump (non-virtual) bases
838  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
839         E = RD->bases_end(); I != E; ++I) {
840    assert(!I->getType()->isDependentType() &&
841           "Cannot layout class with dependent bases.");
842    if (I->isVirtual())
843      continue;
844
845    const CXXRecordDecl *Base =
846      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
847
848    uint64_t BaseOffset = Offset + Info.getBaseClassOffset(Base) / 8;
849
850    DumpCXXRecordLayout(OS, Base, C, BaseOffset, IndentLevel,
851                        Base == PrimaryBase ? "(primary base)" : "(base)",
852                        /*IncludeVirtualBases=*/false);
853  }
854
855  // Dump fields.
856  uint64_t FieldNo = 0;
857  for (CXXRecordDecl::field_iterator I = RD->field_begin(),
858         E = RD->field_end(); I != E; ++I, ++FieldNo) {
859    const FieldDecl *Field = *I;
860    uint64_t FieldOffset = Offset + Info.getFieldOffset(FieldNo) / 8;
861
862    if (const RecordType *RT = Field->getType()->getAs<RecordType>()) {
863      if (const CXXRecordDecl *D = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
864        DumpCXXRecordLayout(OS, D, C, FieldOffset, IndentLevel,
865                            Field->getNameAsCString(),
866                            /*IncludeVirtualBases=*/true);
867        continue;
868      }
869    }
870
871    PrintOffset(OS, FieldOffset, IndentLevel);
872    OS << Field->getType().getAsString() << ' ';
873    OS << Field->getNameAsString() << '\n';
874  }
875
876  if (!IncludeVirtualBases)
877    return;
878
879  // Dump virtual bases.
880  for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
881         E = RD->vbases_end(); I != E; ++I) {
882    assert(I->isVirtual() && "Found non-virtual class!");
883    const CXXRecordDecl *VBase =
884      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
885
886    uint64_t VBaseOffset = Offset + Info.getVBaseClassOffset(VBase) / 8;
887    DumpCXXRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel,
888                        VBase == PrimaryBase ?
889                        "(primary virtual base)" : "(virtual base)",
890                        /*IncludeVirtualBases=*/false);
891  }
892}
893
894void ASTContext::DumpRecordLayout(const RecordDecl *RD,
895                                  llvm::raw_ostream &OS) {
896  const ASTRecordLayout &Info = getASTRecordLayout(RD);
897
898  if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD))
899    DumpCXXRecordLayout(OS, CXXRD, *this, 0, 0, 0,
900                        /*IncludeVirtualBases=*/true);
901  else
902    OS << getTypeDeclType(RD).getAsString();
903
904  OS << "  sizeof=" << Info.getSize() / 8;
905  OS << ", dsize=" << Info.getDataSize() / 8;
906  OS << ", align=" << Info.getAlignment() / 8 << '\n';
907  OS << "  nvsize=" << Info.getNonVirtualSize() / 8;
908  OS << ", nvalign=" << Info.getNonVirtualAlign() / 8 << '\n';
909  OS << '\n';
910}
911