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