blob: 78f9194d73593e5328f337adc58183e1b5a7eb37 [file] [log] [blame]
Anders Carlsson35a36eb2010-05-26 05:41:04 +00001//=== RecordLayoutBuilder.cpp - Helper class for building record layouts ---==//
Anders Carlsson79474332009-07-18 20:20:21 +00002//
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
Anders Carlsson79474332009-07-18 20:20:21 +000010#include "clang/AST/Attr.h"
11#include "clang/AST/Decl.h"
Anders Carlsson6d9f6f32009-07-19 00:18:47 +000012#include "clang/AST/DeclCXX.h"
Anders Carlsson4f516282009-07-18 20:50:59 +000013#include "clang/AST/DeclObjC.h"
Anders Carlsson79474332009-07-18 20:20:21 +000014#include "clang/AST/Expr.h"
Anders Carlsson35a36eb2010-05-26 05:41:04 +000015#include "clang/AST/RecordLayout.h"
Anders Carlsson79474332009-07-18 20:20:21 +000016#include "clang/Basic/TargetInfo.h"
Daniel Dunbaraa423af2010-04-08 02:59:49 +000017#include "llvm/Support/Format.h"
18#include "llvm/ADT/SmallSet.h"
19#include "llvm/Support/MathExtras.h"
Anders Carlsson35a36eb2010-05-26 05:41:04 +000020#include <map>
Anders Carlsson79474332009-07-18 20:20:21 +000021
22using namespace clang;
23
Benjamin Kramerc7656cd2010-05-26 09:58:31 +000024namespace {
Anders Carlssonf58de112010-05-26 15:32:58 +000025
26/// EmptySubobjectMap - Keeps track of which empty subobjects exist at different
27/// offsets while laying out a C++ class.
28class EmptySubobjectMap {
29 ASTContext &Context;
30
31 /// Class - The class whose empty entries we're keeping track of.
32 const CXXRecordDecl *Class;
33
Anders Carlssonc5ca1f72010-05-26 15:54:25 +000034 /// ComputeEmptySubobjectSizes - Compute the size of the largest base or
35 /// member subobject that is empty.
36 void ComputeEmptySubobjectSizes();
37
Anders Carlssonf58de112010-05-26 15:32:58 +000038public:
Anders Carlssonc5ca1f72010-05-26 15:54:25 +000039 /// This holds the size of the largest empty subobject (either a base
40 /// or a member). Will be zero if the record being built doesn't contain
41 /// any empty classes.
42 uint64_t SizeOfLargestEmptySubobject;
43
Anders Carlssonf58de112010-05-26 15:32:58 +000044 EmptySubobjectMap(ASTContext &Context, const CXXRecordDecl *Class)
Anders Carlssonc121b4e2010-05-27 00:07:01 +000045 : Context(Context), Class(Class), SizeOfLargestEmptySubobject(0) {
46 ComputeEmptySubobjectSizes();
47 }
48
49 /// CanPlaceBaseAtOffset - Return whether the given base class can be placed
50 /// at the given offset.
51 /// Returns false if placing the record will result in two components
52 /// (direct or indirect) of the same type having the same offset.
53 bool CanPlaceBaseAtOffset(const CXXRecordDecl *RD, bool BaseIsVirtual,
54 uint64_t Offset);
Anders Carlssonf58de112010-05-26 15:32:58 +000055};
Anders Carlssonc5ca1f72010-05-26 15:54:25 +000056
57void EmptySubobjectMap::ComputeEmptySubobjectSizes() {
58 // Check the bases.
59 for (CXXRecordDecl::base_class_const_iterator I = Class->bases_begin(),
60 E = Class->bases_end(); I != E; ++I) {
61 const CXXRecordDecl *BaseDecl =
62 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
63
64 uint64_t EmptySize = 0;
65 const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
66 if (BaseDecl->isEmpty()) {
67 // If the class decl is empty, get its size.
68 EmptySize = Layout.getSize();
69 } else {
70 // Otherwise, we get the largest empty subobject for the decl.
71 EmptySize = Layout.getSizeOfLargestEmptySubobject();
72 }
73
74 SizeOfLargestEmptySubobject = std::max(SizeOfLargestEmptySubobject,
75 EmptySize);
76 }
Anders Carlssonf58de112010-05-26 15:32:58 +000077
Anders Carlssonc5ca1f72010-05-26 15:54:25 +000078 // Check the fields.
79 for (CXXRecordDecl::field_iterator I = Class->field_begin(),
80 E = Class->field_end(); I != E; ++I) {
81 const FieldDecl *FD = *I;
82
83 const RecordType *RT =
84 Context.getBaseElementType(FD->getType())->getAs<RecordType>();
85
86 // We only care about record types.
87 if (!RT)
88 continue;
89
90 uint64_t EmptySize = 0;
91 const CXXRecordDecl *MemberDecl = cast<CXXRecordDecl>(RT->getDecl());
92 const ASTRecordLayout &Layout = Context.getASTRecordLayout(MemberDecl);
93 if (MemberDecl->isEmpty()) {
94 // If the class decl is empty, get its size.
95 EmptySize = Layout.getSize();
96 } else {
97 // Otherwise, we get the largest empty subobject for the decl.
98 EmptySize = Layout.getSizeOfLargestEmptySubobject();
99 }
100
101 SizeOfLargestEmptySubobject = std::max(SizeOfLargestEmptySubobject,
102 EmptySize);
103 }
104}
105
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000106bool
107EmptySubobjectMap::CanPlaceBaseAtOffset(const CXXRecordDecl *RD,
108 bool BaseIsVirtual,
109 uint64_t Offset) {
110 // If we know this class doesn't have any empty subobjects we don't need to
111 // bother checking.
112 if (!SizeOfLargestEmptySubobject)
113 return true;
114
115 return true;
116}
117
Anders Carlssonc2226202010-05-26 05:58:59 +0000118class RecordLayoutBuilder {
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000119 // FIXME: Remove this and make the appropriate fields public.
120 friend class clang::ASTContext;
121
122 ASTContext &Context;
123
Anders Carlssonf58de112010-05-26 15:32:58 +0000124 EmptySubobjectMap *EmptySubobjects;
125
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000126 /// Size - The current size of the record layout.
127 uint64_t Size;
128
129 /// Alignment - The current alignment of the record layout.
130 unsigned Alignment;
131
132 llvm::SmallVector<uint64_t, 16> FieldOffsets;
133
134 /// Packed - Whether the record is packed or not.
135 bool Packed;
136
137 /// UnfilledBitsInLastByte - If the last field laid out was a bitfield,
138 /// this contains the number of bits in the last byte that can be used for
139 /// an adjacent bitfield if necessary.
140 unsigned char UnfilledBitsInLastByte;
141
142 /// MaxFieldAlignment - The maximum allowed field alignment. This is set by
143 /// #pragma pack.
144 unsigned MaxFieldAlignment;
145
146 /// DataSize - The data size of the record being laid out.
147 uint64_t DataSize;
148
149 bool IsUnion;
150
151 uint64_t NonVirtualSize;
152 unsigned NonVirtualAlignment;
153
154 /// PrimaryBase - the primary base class (if one exists) of the class
155 /// we're laying out.
156 const CXXRecordDecl *PrimaryBase;
157
158 /// PrimaryBaseIsVirtual - Whether the primary base of the class we're laying
159 /// out is virtual.
160 bool PrimaryBaseIsVirtual;
161
162 typedef llvm::DenseMap<const CXXRecordDecl *, uint64_t> BaseOffsetsMapTy;
163
164 /// Bases - base classes and their offsets in the record.
165 BaseOffsetsMapTy Bases;
166
167 // VBases - virtual base classes and their offsets in the record.
168 BaseOffsetsMapTy VBases;
169
170 /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
171 /// primary base classes for some other direct or indirect base class.
172 llvm::SmallSet<const CXXRecordDecl*, 32> IndirectPrimaryBases;
173
174 /// FirstNearlyEmptyVBase - The first nearly empty virtual base class in
175 /// inheritance graph order. Used for determining the primary base class.
176 const CXXRecordDecl *FirstNearlyEmptyVBase;
177
178 /// VisitedVirtualBases - A set of all the visited virtual bases, used to
179 /// avoid visiting virtual bases more than once.
180 llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000181
182 /// EmptyClassOffsets - A map from offsets to empty record decls.
183 typedef std::multimap<uint64_t, const CXXRecordDecl *> EmptyClassOffsetsTy;
184 EmptyClassOffsetsTy EmptyClassOffsets;
185
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000186 RecordLayoutBuilder(ASTContext &Context, EmptySubobjectMap *EmptySubobjects)
187 : Context(Context), EmptySubobjects(EmptySubobjects), Size(0), Alignment(8),
Anders Carlssonf58de112010-05-26 15:32:58 +0000188 Packed(false), UnfilledBitsInLastByte(0), MaxFieldAlignment(0), DataSize(0),
Anders Carlssonce7f7772010-05-26 15:20:08 +0000189 IsUnion(false), NonVirtualSize(0), NonVirtualAlignment(8), PrimaryBase(0),
Anders Carlssonc5ca1f72010-05-26 15:54:25 +0000190 PrimaryBaseIsVirtual(false), FirstNearlyEmptyVBase(0) { }
Anders Carlssonce7f7772010-05-26 15:20:08 +0000191
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000192 void Layout(const RecordDecl *D);
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000193 void Layout(const CXXRecordDecl *D);
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000194 void Layout(const ObjCInterfaceDecl *D);
195
196 void LayoutFields(const RecordDecl *D);
197 void LayoutField(const FieldDecl *D);
198 void LayoutWideBitField(uint64_t FieldSize, uint64_t TypeSize);
199 void LayoutBitField(const FieldDecl *D);
200
201 /// ComputeEmptySubobjectSizes - Compute the size of the largest base or
202 /// member subobject that is empty.
203 void ComputeEmptySubobjectSizes(const CXXRecordDecl *RD);
204
205 /// DeterminePrimaryBase - Determine the primary base of the given class.
206 void DeterminePrimaryBase(const CXXRecordDecl *RD);
207
208 void SelectPrimaryVBase(const CXXRecordDecl *RD);
209
210 /// IdentifyPrimaryBases - Identify all virtual base classes, direct or
211 /// indirect, that are primary base classes for some other direct or indirect
212 /// base class.
213 void IdentifyPrimaryBases(const CXXRecordDecl *RD);
214
215 bool IsNearlyEmpty(const CXXRecordDecl *RD) const;
216
217 /// LayoutNonVirtualBases - Determines the primary base class (if any) and
218 /// lays it out. Will then proceed to lay out all non-virtual base clasess.
219 void LayoutNonVirtualBases(const CXXRecordDecl *RD);
220
221 /// LayoutNonVirtualBase - Lays out a single non-virtual base.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000222 void LayoutNonVirtualBase(const CXXRecordDecl *Base);
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000223
224 void AddPrimaryVirtualBaseOffsets(const CXXRecordDecl *RD, uint64_t Offset,
225 const CXXRecordDecl *MostDerivedClass);
226
227 /// LayoutVirtualBases - Lays out all the virtual bases.
228 void LayoutVirtualBases(const CXXRecordDecl *RD,
229 const CXXRecordDecl *MostDerivedClass);
230
231 /// LayoutVirtualBase - Lays out a single virtual base.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000232 void LayoutVirtualBase(const CXXRecordDecl *Base);
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000233
234 /// LayoutBase - Will lay out a base and return the offset where it was
235 /// placed, in bits.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000236 uint64_t LayoutBase(const CXXRecordDecl *Base, bool BaseIsVirtual);
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000237
238 /// canPlaceRecordAtOffset - Return whether a record (either a base class
239 /// or a field) can be placed at the given offset.
240 /// Returns false if placing the record will result in two components
241 /// (direct or indirect) of the same type having the same offset.
242 bool canPlaceRecordAtOffset(const CXXRecordDecl *RD, uint64_t Offset,
243 bool CheckVBases) const;
244
245 /// canPlaceFieldAtOffset - Return whether a field can be placed at the given
246 /// offset.
247 bool canPlaceFieldAtOffset(const FieldDecl *FD, uint64_t Offset) const;
248
249 /// UpdateEmptyClassOffsets - Called after a record (either a base class
250 /// or a field) has been placed at the given offset. Will update the
251 /// EmptyClassOffsets map if the class is empty or has any empty bases or
252 /// fields.
253 void UpdateEmptyClassOffsets(const CXXRecordDecl *RD, uint64_t Offset,
254 bool UpdateVBases);
255
256 /// UpdateEmptyClassOffsets - Called after a field has been placed at the
257 /// given offset.
258 void UpdateEmptyClassOffsets(const FieldDecl *FD, uint64_t Offset);
259
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000260 /// InitializeLayout - Initialize record layout for the given record decl.
261 void InitializeLayout(const RecordDecl *D);
262
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000263 /// FinishLayout - Finalize record layout. Adjust record size based on the
264 /// alignment.
265 void FinishLayout();
266
267 void UpdateAlignment(unsigned NewAlignment);
268
Anders Carlssonc2226202010-05-26 05:58:59 +0000269 RecordLayoutBuilder(const RecordLayoutBuilder&); // DO NOT IMPLEMENT
270 void operator=(const RecordLayoutBuilder&); // DO NOT IMPLEMENT
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000271public:
272 static const CXXMethodDecl *ComputeKeyFunction(const CXXRecordDecl *RD);
273};
Benjamin Kramerc7656cd2010-05-26 09:58:31 +0000274} // end anonymous namespace
Anders Carlsson35a36eb2010-05-26 05:41:04 +0000275
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000276/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but
277/// no other data.
Anders Carlssonc2226202010-05-26 05:58:59 +0000278bool RecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) const {
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000279 // FIXME: Audit the corners
280 if (!RD->isDynamicClass())
281 return false;
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000282 const ASTRecordLayout &BaseInfo = Context.getASTRecordLayout(RD);
283 if (BaseInfo.getNonVirtualSize() == Context.Target.getPointerWidth(0))
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000284 return true;
285 return false;
286}
287
Anders Carlssonc2226202010-05-26 05:58:59 +0000288void RecordLayoutBuilder::IdentifyPrimaryBases(const CXXRecordDecl *RD) {
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000289 const ASTRecordLayout::PrimaryBaseInfo &BaseInfo =
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000290 Context.getASTRecordLayout(RD).getPrimaryBaseInfo();
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000291
Anders Carlsson81430692009-09-22 03:02:06 +0000292 // If the record has a primary base class that is virtual, add it to the set
293 // of primary bases.
Anders Carlssona30c0d32009-11-27 22:14:40 +0000294 if (BaseInfo.isVirtual())
295 IndirectPrimaryBases.insert(BaseInfo.getBase());
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000296
Anders Carlsson81430692009-09-22 03:02:06 +0000297 // Now traverse all bases and find primary bases for them.
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000298 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000299 e = RD->bases_end(); i != e; ++i) {
Sebastian Redl1054fae2009-10-25 17:03:50 +0000300 assert(!i->getType()->isDependentType() &&
301 "Cannot layout class with dependent bases.");
Mike Stump11289f42009-09-09 15:08:12 +0000302 const CXXRecordDecl *Base =
Mike Stump78696a72009-08-11 04:03:59 +0000303 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000304
Mike Stump78696a72009-08-11 04:03:59 +0000305 // Only bases with virtual bases participate in computing the
306 // indirect primary virtual base classes.
Mike Stumpc2f591b2009-08-13 22:53:07 +0000307 if (Base->getNumVBases())
Anders Carlsson81430692009-09-22 03:02:06 +0000308 IdentifyPrimaryBases(Base);
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000309 }
310}
311
Anders Carlsson81430692009-09-22 03:02:06 +0000312void
Anders Carlssonc2226202010-05-26 05:58:59 +0000313RecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) {
Anders Carlssonf2fa75b2010-03-11 03:39:12 +0000314 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000315 E = RD->bases_end(); I != E; ++I) {
Anders Carlssonf2fa75b2010-03-11 03:39:12 +0000316 assert(!I->getType()->isDependentType() &&
Sebastian Redl1054fae2009-10-25 17:03:50 +0000317 "Cannot layout class with dependent bases.");
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000318
Mike Stump11289f42009-09-09 15:08:12 +0000319 const CXXRecordDecl *Base =
Anders Carlssonf2fa75b2010-03-11 03:39:12 +0000320 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000321
Anders Carlssonf2fa75b2010-03-11 03:39:12 +0000322 // Check if this is a nearly empty virtual base.
323 if (I->isVirtual() && IsNearlyEmpty(Base)) {
324 // If it's not an indirect primary base, then we've found our primary
325 // base.
Anders Carlsson81430692009-09-22 03:02:06 +0000326 if (!IndirectPrimaryBases.count(Base)) {
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000327 PrimaryBase = Base;
328 PrimaryBaseIsVirtual = true;
Mike Stump6f3793b2009-08-12 21:50:08 +0000329 return;
330 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000331
Anders Carlssonf2fa75b2010-03-11 03:39:12 +0000332 // Is this the first nearly empty virtual base?
333 if (!FirstNearlyEmptyVBase)
334 FirstNearlyEmptyVBase = Base;
Mike Stump6f3793b2009-08-12 21:50:08 +0000335 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000336
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000337 SelectPrimaryVBase(Base);
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000338 if (PrimaryBase)
Zhongxing Xuec345b72010-02-15 04:28:35 +0000339 return;
Mike Stump6f3793b2009-08-12 21:50:08 +0000340 }
341}
342
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000343/// DeterminePrimaryBase - Determine the primary base of the given class.
Anders Carlssonc2226202010-05-26 05:58:59 +0000344void RecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) {
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000345 // If the class isn't dynamic, it won't have a primary base.
346 if (!RD->isDynamicClass())
347 return;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000348
Anders Carlsson81430692009-09-22 03:02:06 +0000349 // Compute all the primary virtual bases for all of our direct and
Mike Stump590a7c72009-08-13 23:26:06 +0000350 // indirect bases, and record all their primary virtual base classes.
Mike Stump590a7c72009-08-13 23:26:06 +0000351 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000352 e = RD->bases_end(); i != e; ++i) {
Sebastian Redl1054fae2009-10-25 17:03:50 +0000353 assert(!i->getType()->isDependentType() &&
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000354 "Cannot lay out class with dependent bases.");
Mike Stump11289f42009-09-09 15:08:12 +0000355 const CXXRecordDecl *Base =
Mike Stump590a7c72009-08-13 23:26:06 +0000356 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
Anders Carlsson81430692009-09-22 03:02:06 +0000357 IdentifyPrimaryBases(Base);
Mike Stump590a7c72009-08-13 23:26:06 +0000358 }
359
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000360 // If the record has a dynamic base class, attempt to choose a primary base
361 // class. It is the first (in direct base class order) non-virtual dynamic
Anders Carlsson81430692009-09-22 03:02:06 +0000362 // base class, if one exists.
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000363 for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000364 e = RD->bases_end(); i != e; ++i) {
Anders Carlsson03ff3792009-11-27 22:05:05 +0000365 // Ignore virtual bases.
366 if (i->isVirtual())
367 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000368
Anders Carlsson03ff3792009-11-27 22:05:05 +0000369 const CXXRecordDecl *Base =
370 cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
371
372 if (Base->isDynamicClass()) {
373 // We found it.
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000374 PrimaryBase = Base;
375 PrimaryBaseIsVirtual = false;
Anders Carlsson03ff3792009-11-27 22:05:05 +0000376 return;
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000377 }
378 }
379
380 // Otherwise, it is the first nearly empty virtual base that is not an
Mike Stump78696a72009-08-11 04:03:59 +0000381 // indirect primary virtual base class, if one exists.
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000382 if (RD->getNumVBases() != 0) {
383 SelectPrimaryVBase(RD);
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000384 if (PrimaryBase)
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000385 return;
386 }
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000387
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000388 // Otherwise, it is the first nearly empty virtual base that is not an
389 // indirect primary virtual base class, if one exists.
390 if (FirstNearlyEmptyVBase) {
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000391 PrimaryBase = FirstNearlyEmptyVBase;
392 PrimaryBaseIsVirtual = true;
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000393 return;
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000394 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000395
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000396 // Otherwise there is no primary base class.
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000397 assert(!PrimaryBase && "Should not get here with a primary base!");
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000398
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000399 // Allocate the virtual table pointer at offset zero.
400 assert(DataSize == 0 && "Vtable pointer must be at offset zero!");
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000401
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000402 // Update the size.
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000403 Size += Context.Target.getPointerWidth(0);
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000404 DataSize = Size;
405
406 // Update the alignment.
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000407 UpdateAlignment(Context.Target.getPointerAlign(0));
Mike Stumpd8fe7b22009-08-05 22:37:18 +0000408}
409
Anders Carlsson09ffa322010-03-10 22:21:28 +0000410void
Anders Carlssonc2226202010-05-26 05:58:59 +0000411RecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000412 // First, determine the primary base class.
413 DeterminePrimaryBase(RD);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000414
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000415 // If we have a primary base class, lay it out.
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000416 if (PrimaryBase) {
417 if (PrimaryBaseIsVirtual) {
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000418 // We have a virtual primary base, insert it as an indirect primary base.
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000419 IndirectPrimaryBases.insert(PrimaryBase);
Anders Carlssonfe900962010-03-11 05:42:17 +0000420
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000421 assert(!VisitedVirtualBases.count(PrimaryBase) &&
422 "vbase already visited!");
423 VisitedVirtualBases.insert(PrimaryBase);
Anders Carlsson291279e2010-04-10 18:42:27 +0000424
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000425 LayoutVirtualBase(PrimaryBase);
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000426 } else
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000427 LayoutNonVirtualBase(PrimaryBase);
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000428 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000429
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000430 // Now lay out the non-virtual bases.
431 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000432 E = RD->bases_end(); I != E; ++I) {
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000433
434 // Ignore virtual bases.
435 if (I->isVirtual())
436 continue;
437
438 const CXXRecordDecl *Base =
439 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
440
441 // Skip the primary base.
Anders Carlssonb48414f2010-05-26 05:31:23 +0000442 if (Base == PrimaryBase && !PrimaryBaseIsVirtual)
Anders Carlsson8630b5b2010-03-11 00:15:35 +0000443 continue;
444
445 // Lay out the base.
446 LayoutNonVirtualBase(Base);
Anders Carlsson09ffa322010-03-10 22:21:28 +0000447 }
448}
449
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000450void RecordLayoutBuilder::LayoutNonVirtualBase(const CXXRecordDecl *Base) {
Anders Carlsson0d0b5882010-03-10 22:26:24 +0000451 // Layout the base.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000452 uint64_t Offset = LayoutBase(Base, /*BaseIsVirtual=*/false);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000453
Anders Carlsson0d0b5882010-03-10 22:26:24 +0000454 // Add its base class offset.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000455 if (!Bases.insert(std::make_pair(Base, Offset)).second)
Anders Carlsson6a848892010-03-11 04:10:39 +0000456 assert(false && "Added same base offset more than once!");
Anders Carlsson09ffa322010-03-10 22:21:28 +0000457}
Mike Stump2b84dd32009-11-05 04:02:15 +0000458
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000459void
Anders Carlssonc2226202010-05-26 05:58:59 +0000460RecordLayoutBuilder::AddPrimaryVirtualBaseOffsets(const CXXRecordDecl *RD,
Anders Carlssonea7b1822010-04-15 16:12:58 +0000461 uint64_t Offset,
462 const CXXRecordDecl *MostDerivedClass) {
463 // We already have the offset for the primary base of the most derived class.
464 if (RD != MostDerivedClass) {
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000465 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonea7b1822010-04-15 16:12:58 +0000466 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
467
468 // If this is a primary virtual base and we haven't seen it before, add it.
469 if (PrimaryBase && Layout.getPrimaryBaseWasVirtual() &&
470 !VBases.count(PrimaryBase))
471 VBases.insert(std::make_pair(PrimaryBase, Offset));
472 }
473
474 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
475 E = RD->bases_end(); I != E; ++I) {
476 assert(!I->getType()->isDependentType() &&
477 "Cannot layout class with dependent bases.");
478
479 const CXXRecordDecl *BaseDecl =
480 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
481
482 if (!BaseDecl->getNumVBases()) {
483 // This base isn't interesting since it doesn't have any virtual bases.
484 continue;
485 }
486
487 // Compute the offset of this base.
488 uint64_t BaseOffset;
489
490 if (I->isVirtual()) {
491 // If we don't know this vbase yet, don't visit it. It will be visited
492 // later.
493 if (!VBases.count(BaseDecl)) {
494 continue;
495 }
496
497 // Check if we've already visited this base.
498 if (!VisitedVirtualBases.insert(BaseDecl))
499 continue;
500
501 // We want the vbase offset from the class we're currently laying out.
502 BaseOffset = VBases[BaseDecl];
503 } else if (RD == MostDerivedClass) {
504 // We want the base offset from the class we're currently laying out.
505 assert(Bases.count(BaseDecl) && "Did not find base!");
506 BaseOffset = Bases[BaseDecl];
507 } else {
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000508 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonea7b1822010-04-15 16:12:58 +0000509 BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
510 }
511
512 AddPrimaryVirtualBaseOffsets(BaseDecl, BaseOffset, MostDerivedClass);
513 }
514}
515
516void
Anders Carlssonc2226202010-05-26 05:58:59 +0000517RecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD,
Anders Carlssonea7b1822010-04-15 16:12:58 +0000518 const CXXRecordDecl *MostDerivedClass) {
Anders Carlssonde710c92010-03-11 04:33:54 +0000519 const CXXRecordDecl *PrimaryBase;
Anders Carlsson291279e2010-04-10 18:42:27 +0000520 bool PrimaryBaseIsVirtual;
Anders Carlssonfe900962010-03-11 05:42:17 +0000521
Anders Carlsson291279e2010-04-10 18:42:27 +0000522 if (MostDerivedClass == RD) {
Anders Carlssond20e7cd2010-05-26 05:20:58 +0000523 PrimaryBase = this->PrimaryBase;
524 PrimaryBaseIsVirtual = this->PrimaryBaseIsVirtual;
Anders Carlsson291279e2010-04-10 18:42:27 +0000525 } else {
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000526 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonde710c92010-03-11 04:33:54 +0000527 PrimaryBase = Layout.getPrimaryBase();
Anders Carlsson291279e2010-04-10 18:42:27 +0000528 PrimaryBaseIsVirtual = Layout.getPrimaryBaseWasVirtual();
529 }
530
Anders Carlssonf7b7a1e2010-03-11 04:24:02 +0000531 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
532 E = RD->bases_end(); I != E; ++I) {
533 assert(!I->getType()->isDependentType() &&
Sebastian Redl1054fae2009-10-25 17:03:50 +0000534 "Cannot layout class with dependent bases.");
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000535
Mike Stump11289f42009-09-09 15:08:12 +0000536 const CXXRecordDecl *Base =
Anders Carlssonf7b7a1e2010-03-11 04:24:02 +0000537 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
538
539 if (I->isVirtual()) {
Anders Carlsson291279e2010-04-10 18:42:27 +0000540 if (PrimaryBase != Base || !PrimaryBaseIsVirtual) {
541 bool IndirectPrimaryBase = IndirectPrimaryBases.count(Base);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000542
Anders Carlsson291279e2010-04-10 18:42:27 +0000543 // Only lay out the virtual base if it's not an indirect primary base.
544 if (!IndirectPrimaryBase) {
545 // Only visit virtual bases once.
546 if (!VisitedVirtualBases.insert(Base))
547 continue;
548
Anders Carlssonfe900962010-03-11 05:42:17 +0000549 LayoutVirtualBase(Base);
Anders Carlsson6a848892010-03-11 04:10:39 +0000550 }
Mike Stump2b84dd32009-11-05 04:02:15 +0000551 }
Mike Stumpc2f591b2009-08-13 22:53:07 +0000552 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000553
Anders Carlssonf7b7a1e2010-03-11 04:24:02 +0000554 if (!Base->getNumVBases()) {
555 // This base isn't interesting since it doesn't have any virtual bases.
556 continue;
Mike Stump996576f32009-08-16 19:04:13 +0000557 }
Anders Carlssonf7b7a1e2010-03-11 04:24:02 +0000558
Anders Carlssonea7b1822010-04-15 16:12:58 +0000559 LayoutVirtualBases(Base, MostDerivedClass);
Mike Stump6b2556f2009-08-06 13:41:24 +0000560 }
561}
562
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000563void RecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *Base) {
Anders Carlsson0d0b5882010-03-10 22:26:24 +0000564 // Layout the base.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000565 uint64_t Offset = LayoutBase(Base, /*BaseIsVirtual=*/true);
Anders Carlsson0d0b5882010-03-10 22:26:24 +0000566
567 // Add its base class offset.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000568 if (!VBases.insert(std::make_pair(Base, Offset)).second)
Anders Carlsson6a848892010-03-11 04:10:39 +0000569 assert(false && "Added same vbase offset more than once!");
Anders Carlsson09ffa322010-03-10 22:21:28 +0000570}
571
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000572uint64_t RecordLayoutBuilder::LayoutBase(const CXXRecordDecl *Base,
573 bool BaseIsVirtual) {
574 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base);
Anders Carlsson09ffa322010-03-10 22:21:28 +0000575
576 // If we have an empty base class, try to place it at offset 0.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000577 if (Base->isEmpty() &&
578 EmptySubobjects->CanPlaceBaseAtOffset(Base, BaseIsVirtual, 0) &&
579 canPlaceRecordAtOffset(Base, 0, /*CheckVBases=*/false)) {
Anders Carlsson09ffa322010-03-10 22:21:28 +0000580 // We were able to place the class at offset 0.
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000581 UpdateEmptyClassOffsets(Base, 0, /*UpdateVBases=*/false);
Anders Carlsson09ffa322010-03-10 22:21:28 +0000582
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000583 Size = std::max(Size, Layout.getSize());
Anders Carlsson09ffa322010-03-10 22:21:28 +0000584
585 return 0;
586 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000587
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000588 unsigned BaseAlign = Layout.getNonVirtualAlign();
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000589
Anders Carlsson09ffa322010-03-10 22:21:28 +0000590 // Round up the current record size to the base's alignment boundary.
591 uint64_t Offset = llvm::RoundUpToAlignment(DataSize, BaseAlign);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000592
Anders Carlsson09ffa322010-03-10 22:21:28 +0000593 // Try to place the base.
594 while (true) {
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000595 if (EmptySubobjects->CanPlaceBaseAtOffset(Base, BaseIsVirtual, Offset) &&
596 canPlaceRecordAtOffset(Base, Offset, /*CheckVBases=*/false))
Anders Carlsson09ffa322010-03-10 22:21:28 +0000597 break;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000598
Anders Carlsson09ffa322010-03-10 22:21:28 +0000599 Offset += BaseAlign;
600 }
601
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000602 if (!Base->isEmpty()) {
Anders Carlsson09ffa322010-03-10 22:21:28 +0000603 // Update the data size.
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000604 DataSize = Offset + Layout.getNonVirtualSize();
Anders Carlsson09ffa322010-03-10 22:21:28 +0000605
606 Size = std::max(Size, DataSize);
607 } else
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000608 Size = std::max(Size, Offset + Layout.getSize());
Anders Carlsson09ffa322010-03-10 22:21:28 +0000609
610 // Remember max struct/class alignment.
611 UpdateAlignment(BaseAlign);
612
Anders Carlssonc121b4e2010-05-27 00:07:01 +0000613 UpdateEmptyClassOffsets(Base, Offset, /*UpdateVBases=*/false);
Anders Carlsson09ffa322010-03-10 22:21:28 +0000614 return Offset;
615}
616
Anders Carlssond626cb72010-05-10 15:26:14 +0000617bool
Anders Carlssonc2226202010-05-26 05:58:59 +0000618RecordLayoutBuilder::canPlaceRecordAtOffset(const CXXRecordDecl *RD,
Anders Carlssond626cb72010-05-10 15:26:14 +0000619 uint64_t Offset,
620 bool CheckVBases) const {
Anders Carlssonf24b18f2009-09-24 03:22:10 +0000621 // Look for an empty class with the same type at the same offset.
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000622 for (EmptyClassOffsetsTy::const_iterator I =
623 EmptyClassOffsets.lower_bound(Offset),
624 E = EmptyClassOffsets.upper_bound(Offset); I != E; ++I) {
625
Anders Carlssonf24b18f2009-09-24 03:22:10 +0000626 if (I->second == RD)
627 return false;
628 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000629
Anders Carlsson82828a32010-05-09 05:03:38 +0000630 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000631
632 // Check bases.
633 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000634 E = RD->bases_end(); I != E; ++I) {
Sebastian Redl1054fae2009-10-25 17:03:50 +0000635 assert(!I->getType()->isDependentType() &&
636 "Cannot layout class with dependent bases.");
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000637 if (I->isVirtual())
638 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000639
Anders Carlsson82828a32010-05-09 05:03:38 +0000640 const CXXRecordDecl *BaseDecl =
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000641 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
642
Anders Carlsson82828a32010-05-09 05:03:38 +0000643 uint64_t BaseOffset = Layout.getBaseClassOffset(BaseDecl);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000644
Anders Carlssond626cb72010-05-10 15:26:14 +0000645 if (!canPlaceRecordAtOffset(BaseDecl, Offset + BaseOffset,
646 /*CheckVBases=*/false))
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000647 return false;
648 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000649
Anders Carlssond7d358a2009-09-25 15:39:00 +0000650 // Check fields.
651 unsigned FieldNo = 0;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000652 for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
Anders Carlssond7d358a2009-09-25 15:39:00 +0000653 I != E; ++I, ++FieldNo) {
654 const FieldDecl *FD = *I;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000655
Anders Carlsson82828a32010-05-09 05:03:38 +0000656 uint64_t FieldOffset = Layout.getFieldOffset(FieldNo);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000657
Anders Carlssond7d358a2009-09-25 15:39:00 +0000658 if (!canPlaceFieldAtOffset(FD, Offset + FieldOffset))
659 return false;
660 }
661
Anders Carlssond626cb72010-05-10 15:26:14 +0000662 if (CheckVBases) {
663 // FIXME: virtual bases.
664 }
665
Anders Carlsson6522b052009-09-24 03:13:30 +0000666 return true;
667}
668
Anders Carlssonc2226202010-05-26 05:58:59 +0000669bool RecordLayoutBuilder::canPlaceFieldAtOffset(const FieldDecl *FD,
Anders Carlsson6f95c702009-09-25 00:02:51 +0000670 uint64_t Offset) const {
Anders Carlsson4bf82142009-09-25 01:23:32 +0000671 QualType T = FD->getType();
672 if (const RecordType *RT = T->getAs<RecordType>()) {
Anders Carlsson6f95c702009-09-25 00:02:51 +0000673 if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl()))
Anders Carlssond626cb72010-05-10 15:26:14 +0000674 return canPlaceRecordAtOffset(RD, Offset, /*CheckVBases=*/true);
Anders Carlsson6f95c702009-09-25 00:02:51 +0000675 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000676
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000677 if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
678 QualType ElemTy = Context.getBaseElementType(AT);
Anders Carlsson4bf82142009-09-25 01:23:32 +0000679 const RecordType *RT = ElemTy->getAs<RecordType>();
680 if (!RT)
681 return true;
682 const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl());
683 if (!RD)
684 return true;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000685
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000686 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlsson4bf82142009-09-25 01:23:32 +0000687
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000688 uint64_t NumElements = Context.getConstantArrayElementCount(AT);
Mike Stump2b84dd32009-11-05 04:02:15 +0000689 uint64_t ElementOffset = Offset;
Anders Carlsson4bf82142009-09-25 01:23:32 +0000690 for (uint64_t I = 0; I != NumElements; ++I) {
Anders Carlssond626cb72010-05-10 15:26:14 +0000691 if (!canPlaceRecordAtOffset(RD, ElementOffset, /*CheckVBases=*/true))
Anders Carlsson4bf82142009-09-25 01:23:32 +0000692 return false;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000693
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000694 ElementOffset += Layout.getSize();
Anders Carlsson4bf82142009-09-25 01:23:32 +0000695 }
696 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000697
Anders Carlsson6f95c702009-09-25 00:02:51 +0000698 return true;
699}
700
Anders Carlssonc2226202010-05-26 05:58:59 +0000701void RecordLayoutBuilder::UpdateEmptyClassOffsets(const CXXRecordDecl *RD,
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000702 uint64_t Offset,
703 bool UpdateVBases) {
Anders Carlssonf24b18f2009-09-24 03:22:10 +0000704 if (RD->isEmpty())
705 EmptyClassOffsets.insert(std::make_pair(Offset, RD));
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000706
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000707 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000708
709 // Update bases.
710 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000711 E = RD->bases_end(); I != E; ++I) {
Sebastian Redl1054fae2009-10-25 17:03:50 +0000712 assert(!I->getType()->isDependentType() &&
713 "Cannot layout class with dependent bases.");
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000714 if (I->isVirtual())
715 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000716
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000717 const CXXRecordDecl *Base =
718 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000719
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000720 uint64_t BaseClassOffset = Layout.getBaseClassOffset(Base);
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000721 UpdateEmptyClassOffsets(Base, Offset + BaseClassOffset,
722 /*UpdateVBases=*/false);
Anders Carlssonbb66bc82009-09-24 05:21:31 +0000723 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000724
Anders Carlssond7d358a2009-09-25 15:39:00 +0000725 // Update fields.
726 unsigned FieldNo = 0;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000727 for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
Anders Carlssond7d358a2009-09-25 15:39:00 +0000728 I != E; ++I, ++FieldNo) {
729 const FieldDecl *FD = *I;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000730
Anders Carlsson2357bfd2010-05-08 22:35:05 +0000731 uint64_t FieldOffset = Layout.getFieldOffset(FieldNo);
Anders Carlssond7d358a2009-09-25 15:39:00 +0000732 UpdateEmptyClassOffsets(FD, Offset + FieldOffset);
733 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000734
Anders Carlsson57732052010-05-23 18:14:24 +0000735 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
736
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000737 if (UpdateVBases) {
738 // FIXME: Update virtual bases.
Anders Carlsson57732052010-05-23 18:14:24 +0000739 } else if (PrimaryBase && Layout.getPrimaryBaseWasVirtual()) {
740 // We always want to update the offsets of a primary virtual base.
741 assert(Layout.getVBaseClassOffset(PrimaryBase) == 0 &&
742 "primary base class offset must always be 0!");
743 UpdateEmptyClassOffsets(PrimaryBase, Offset, /*UpdateVBases=*/false);
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000744 }
Anders Carlsson6522b052009-09-24 03:13:30 +0000745}
746
Anders Carlssone1883102009-09-25 01:54:38 +0000747void
Anders Carlssonc2226202010-05-26 05:58:59 +0000748RecordLayoutBuilder::UpdateEmptyClassOffsets(const FieldDecl *FD,
Anders Carlssone1883102009-09-25 01:54:38 +0000749 uint64_t Offset) {
750 QualType T = FD->getType();
751
752 if (const RecordType *RT = T->getAs<RecordType>()) {
753 if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000754 UpdateEmptyClassOffsets(RD, Offset, /*UpdateVBases=*/true);
Anders Carlssone1883102009-09-25 01:54:38 +0000755 return;
756 }
757 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000758
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000759 if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
760 QualType ElemTy = Context.getBaseElementType(AT);
Anders Carlssone1883102009-09-25 01:54:38 +0000761 const RecordType *RT = ElemTy->getAs<RecordType>();
762 if (!RT)
763 return;
764 const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(RT->getDecl());
765 if (!RD)
766 return;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000767
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000768 const ASTRecordLayout &Info = Context.getASTRecordLayout(RD);
Anders Carlssone1883102009-09-25 01:54:38 +0000769
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000770 uint64_t NumElements = Context.getConstantArrayElementCount(AT);
Mike Stump2b84dd32009-11-05 04:02:15 +0000771 uint64_t ElementOffset = Offset;
Anders Carlssone1883102009-09-25 01:54:38 +0000772
773 for (uint64_t I = 0; I != NumElements; ++I) {
Anders Carlsson5f1a1702010-05-10 15:28:59 +0000774 UpdateEmptyClassOffsets(RD, ElementOffset, /*UpdateVBases=*/true);
Anders Carlssone1883102009-09-25 01:54:38 +0000775 ElementOffset += Info.getSize();
776 }
777 }
778}
779
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000780void RecordLayoutBuilder::InitializeLayout(const RecordDecl *D) {
Anders Carlsson79474332009-07-18 20:20:21 +0000781 IsUnion = D->isUnion();
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000782
Anders Carlsson28a5fa22009-08-08 19:38:24 +0000783 Packed = D->hasAttr<PackedAttr>();
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000784
Anders Carlsson28a5fa22009-08-08 19:38:24 +0000785 // The #pragma pack attribute specifies the maximum field alignment.
Anders Carlsson68e0b682009-08-08 18:23:56 +0000786 if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
Anders Carlsson28a5fa22009-08-08 19:38:24 +0000787 MaxFieldAlignment = PPA->getAlignment();
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000788
Anders Carlsson79474332009-07-18 20:20:21 +0000789 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
Alexis Hunt96d5c762009-11-21 08:43:09 +0000790 UpdateAlignment(AA->getMaxAlignment());
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000791}
Anders Carlsson6d9f6f32009-07-19 00:18:47 +0000792
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000793void RecordLayoutBuilder::Layout(const RecordDecl *D) {
794 InitializeLayout(D);
Anders Carlsson118ce162009-07-18 21:48:39 +0000795 LayoutFields(D);
Mike Stump11289f42009-09-09 15:08:12 +0000796
Anders Carlsson79474332009-07-18 20:20:21 +0000797 // Finally, round the size of the total struct up to the alignment of the
798 // struct itself.
799 FinishLayout();
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000800}
801
802void RecordLayoutBuilder::Layout(const CXXRecordDecl *RD) {
Anders Carlssonf58de112010-05-26 15:32:58 +0000803 // Create our empty subobject offset map.
804 EmptySubobjectMap EmptySubobjectMap(Context, RD);
805 EmptySubobjects = &EmptySubobjectMap;
806
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000807 InitializeLayout(RD);
808
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000809 // Lay out the vtable and the non-virtual bases.
810 LayoutNonVirtualBases(RD);
811
812 LayoutFields(RD);
813
814 NonVirtualSize = Size;
815 NonVirtualAlignment = Alignment;
816
817 // Lay out the virtual bases and add the primary virtual base offsets.
818 LayoutVirtualBases(RD, RD);
819
820 VisitedVirtualBases.clear();
821 AddPrimaryVirtualBaseOffsets(RD, 0, RD);
822
823 // Finally, round the size of the total struct up to the alignment of the
824 // struct itself.
825 FinishLayout();
826
Anders Carlsson5b441d72010-04-10 21:24:48 +0000827#ifndef NDEBUG
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000828 // Check that we have base offsets for all bases.
829 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
830 E = RD->bases_end(); I != E; ++I) {
831 if (I->isVirtual())
832 continue;
Anders Carlsson5b441d72010-04-10 21:24:48 +0000833
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000834 const CXXRecordDecl *BaseDecl =
835 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
836
837 assert(Bases.count(BaseDecl) && "Did not find base offset!");
838 }
839
840 // And all virtual bases.
841 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
842 E = RD->vbases_end(); I != E; ++I) {
843 const CXXRecordDecl *BaseDecl =
844 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
Anders Carlsson5b441d72010-04-10 21:24:48 +0000845
Anders Carlssonc28a6c92010-05-26 15:10:00 +0000846 assert(VBases.count(BaseDecl) && "Did not find base offset!");
Anders Carlsson5b441d72010-04-10 21:24:48 +0000847 }
848#endif
Anders Carlsson79474332009-07-18 20:20:21 +0000849}
850
Anders Carlssonc2226202010-05-26 05:58:59 +0000851void RecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D) {
Anders Carlsson4f516282009-07-18 20:50:59 +0000852 if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000853 const ASTRecordLayout &SL = Context.getASTObjCInterfaceLayout(SD);
Anders Carlsson4f516282009-07-18 20:50:59 +0000854
855 UpdateAlignment(SL.getAlignment());
Mike Stump11289f42009-09-09 15:08:12 +0000856
Anders Carlsson4f516282009-07-18 20:50:59 +0000857 // We start laying out ivars not at the end of the superclass
858 // structure, but at the next byte following the last field.
Anders Carlsson27b50132009-07-18 21:26:44 +0000859 Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8);
Anders Carlsson47680d82009-09-26 01:34:51 +0000860 DataSize = Size;
Anders Carlsson4f516282009-07-18 20:50:59 +0000861 }
Mike Stump11289f42009-09-09 15:08:12 +0000862
Anders Carlsson28a5fa22009-08-08 19:38:24 +0000863 Packed = D->hasAttr<PackedAttr>();
Mike Stump11289f42009-09-09 15:08:12 +0000864
Anders Carlsson28a5fa22009-08-08 19:38:24 +0000865 // The #pragma pack attribute specifies the maximum field alignment.
866 if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
867 MaxFieldAlignment = PPA->getAlignment();
Mike Stump11289f42009-09-09 15:08:12 +0000868
Anders Carlsson4f516282009-07-18 20:50:59 +0000869 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
Alexis Hunt96d5c762009-11-21 08:43:09 +0000870 UpdateAlignment(AA->getMaxAlignment());
Anders Carlsson4f516282009-07-18 20:50:59 +0000871 // Layout each ivar sequentially.
872 llvm::SmallVector<ObjCIvarDecl*, 16> Ivars;
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000873 Context.ShallowCollectObjCIvars(D, Ivars);
Anders Carlsson4f516282009-07-18 20:50:59 +0000874 for (unsigned i = 0, e = Ivars.size(); i != e; ++i)
875 LayoutField(Ivars[i]);
Mike Stump11289f42009-09-09 15:08:12 +0000876
Anders Carlsson4f516282009-07-18 20:50:59 +0000877 // Finally, round the size of the total struct up to the alignment of the
878 // struct itself.
879 FinishLayout();
880}
881
Anders Carlssonc2226202010-05-26 05:58:59 +0000882void RecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
Anders Carlsson118ce162009-07-18 21:48:39 +0000883 // Layout each field, for now, just sequentially, respecting alignment. In
884 // the future, this will need to be tweakable by targets.
Mike Stump11289f42009-09-09 15:08:12 +0000885 for (RecordDecl::field_iterator Field = D->field_begin(),
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000886 FieldEnd = D->field_end(); Field != FieldEnd; ++Field)
Anders Carlsson118ce162009-07-18 21:48:39 +0000887 LayoutField(*Field);
888}
889
Anders Carlssonc2226202010-05-26 05:58:59 +0000890void RecordLayoutBuilder::LayoutWideBitField(uint64_t FieldSize,
Anders Carlsson57235162010-04-16 15:57:11 +0000891 uint64_t TypeSize) {
892 assert(Context.getLangOptions().CPlusPlus &&
893 "Can only have wide bit-fields in C++!");
894
895 // Itanium C++ ABI 2.4:
896 // If sizeof(T)*8 < n, let T' be the largest integral POD type with
897 // sizeof(T')*8 <= n.
898
899 QualType IntegralPODTypes[] = {
900 Context.UnsignedCharTy, Context.UnsignedShortTy, Context.UnsignedIntTy,
901 Context.UnsignedLongTy, Context.UnsignedLongLongTy
902 };
903
Anders Carlsson57235162010-04-16 15:57:11 +0000904 QualType Type;
905 for (unsigned I = 0, E = llvm::array_lengthof(IntegralPODTypes);
906 I != E; ++I) {
907 uint64_t Size = Context.getTypeSize(IntegralPODTypes[I]);
Anders Carlsson57235162010-04-16 15:57:11 +0000908
909 if (Size > FieldSize)
910 break;
911
912 Type = IntegralPODTypes[I];
913 }
914 assert(!Type.isNull() && "Did not find a type!");
Anders Carlsson57235162010-04-16 15:57:11 +0000915
916 unsigned TypeAlign = Context.getTypeAlign(Type);
917
918 // We're not going to use any of the unfilled bits in the last byte.
919 UnfilledBitsInLastByte = 0;
920
Anders Carlssonaad5fa82010-04-17 20:21:41 +0000921 uint64_t FieldOffset;
922
Anders Carlsson57235162010-04-16 15:57:11 +0000923 if (IsUnion) {
924 DataSize = std::max(DataSize, FieldSize);
Anders Carlssonaad5fa82010-04-17 20:21:41 +0000925 FieldOffset = 0;
Anders Carlsson57235162010-04-16 15:57:11 +0000926 } else {
Anders Carlssonaad5fa82010-04-17 20:21:41 +0000927 // The bitfield is allocated starting at the next offset aligned appropriately
928 // for T', with length n bits.
929 FieldOffset = llvm::RoundUpToAlignment(DataSize, TypeAlign);
930
Anders Carlsson57235162010-04-16 15:57:11 +0000931 uint64_t NewSizeInBits = FieldOffset + FieldSize;
932
933 DataSize = llvm::RoundUpToAlignment(NewSizeInBits, 8);
934 UnfilledBitsInLastByte = DataSize - NewSizeInBits;
935 }
936
937 // Place this field at the current location.
938 FieldOffsets.push_back(FieldOffset);
939
940 // Update the size.
941 Size = std::max(Size, DataSize);
942
943 // Remember max struct/class alignment.
944 UpdateAlignment(TypeAlign);
945}
946
Anders Carlssonc2226202010-05-26 05:58:59 +0000947void RecordLayoutBuilder::LayoutBitField(const FieldDecl *D) {
Anders Carlsson07209442009-11-22 17:37:31 +0000948 bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
Anders Carlssonba958402009-11-22 19:13:51 +0000949 uint64_t FieldOffset = IsUnion ? 0 : (DataSize - UnfilledBitsInLastByte);
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000950 uint64_t FieldSize = D->getBitWidth()->EvaluateAsInt(Context).getZExtValue();
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000951
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000952 std::pair<uint64_t, unsigned> FieldInfo = Context.getTypeInfo(D->getType());
Anders Carlsson07209442009-11-22 17:37:31 +0000953 uint64_t TypeSize = FieldInfo.first;
954 unsigned FieldAlign = FieldInfo.second;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000955
Anders Carlsson57235162010-04-16 15:57:11 +0000956 if (FieldSize > TypeSize) {
957 LayoutWideBitField(FieldSize, TypeSize);
958 return;
959 }
960
Anders Carlsson5efc56e2010-04-16 15:07:51 +0000961 if (FieldPacked || !Context.Target.useBitFieldTypeAlignment())
Anders Carlsson07209442009-11-22 17:37:31 +0000962 FieldAlign = 1;
963 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
964 FieldAlign = std::max(FieldAlign, AA->getMaxAlignment());
965
966 // The maximum field alignment overrides the aligned attribute.
967 if (MaxFieldAlignment)
968 FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000969
Daniel Dunbar3d9289c2010-04-15 06:18:39 +0000970 // Check if we need to add padding to give the field the correct alignment.
Anders Carlsson07209442009-11-22 17:37:31 +0000971 if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)
972 FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000973
Daniel Dunbar3d9289c2010-04-15 06:18:39 +0000974 // Padding members don't affect overall alignment.
Anders Carlsson07209442009-11-22 17:37:31 +0000975 if (!D->getIdentifier())
976 FieldAlign = 1;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000977
Anders Carlsson07209442009-11-22 17:37:31 +0000978 // Place this field at the current location.
979 FieldOffsets.push_back(FieldOffset);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000980
Anders Carlssonba958402009-11-22 19:13:51 +0000981 // Update DataSize to include the last byte containing (part of) the bitfield.
982 if (IsUnion) {
983 // FIXME: I think FieldSize should be TypeSize here.
984 DataSize = std::max(DataSize, FieldSize);
985 } else {
986 uint64_t NewSizeInBits = FieldOffset + FieldSize;
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000987
Anders Carlssonba958402009-11-22 19:13:51 +0000988 DataSize = llvm::RoundUpToAlignment(NewSizeInBits, 8);
989 UnfilledBitsInLastByte = DataSize - NewSizeInBits;
990 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000991
Anders Carlssonba958402009-11-22 19:13:51 +0000992 // Update the size.
993 Size = std::max(Size, DataSize);
Daniel Dunbaraa423af2010-04-08 02:59:49 +0000994
Anders Carlsson07209442009-11-22 17:37:31 +0000995 // Remember max struct/class alignment.
996 UpdateAlignment(FieldAlign);
997}
998
Anders Carlssonc2226202010-05-26 05:58:59 +0000999void RecordLayoutBuilder::LayoutField(const FieldDecl *D) {
Anders Carlsson07209442009-11-22 17:37:31 +00001000 if (D->isBitField()) {
1001 LayoutBitField(D);
1002 return;
1003 }
1004
Anders Carlssonba958402009-11-22 19:13:51 +00001005 // Reset the unfilled bits.
1006 UnfilledBitsInLastByte = 0;
1007
Anders Carlsson07209442009-11-22 17:37:31 +00001008 bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
Anders Carlsson47680d82009-09-26 01:34:51 +00001009 uint64_t FieldOffset = IsUnion ? 0 : DataSize;
Anders Carlsson79474332009-07-18 20:20:21 +00001010 uint64_t FieldSize;
1011 unsigned FieldAlign;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001012
Anders Carlsson07209442009-11-22 17:37:31 +00001013 if (D->getType()->isIncompleteArrayType()) {
1014 // This is a flexible array member; we can't directly
1015 // query getTypeInfo about these, so we figure it out here.
1016 // Flexible array members don't have any size, but they
1017 // have to be aligned appropriately for their element type.
1018 FieldSize = 0;
Anders Carlsson5efc56e2010-04-16 15:07:51 +00001019 const ArrayType* ATy = Context.getAsArrayType(D->getType());
1020 FieldAlign = Context.getTypeAlign(ATy->getElementType());
Anders Carlsson07209442009-11-22 17:37:31 +00001021 } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
1022 unsigned AS = RT->getPointeeType().getAddressSpace();
Anders Carlsson5efc56e2010-04-16 15:07:51 +00001023 FieldSize = Context.Target.getPointerWidth(AS);
1024 FieldAlign = Context.Target.getPointerAlign(AS);
Anders Carlsson79474332009-07-18 20:20:21 +00001025 } else {
Anders Carlsson5efc56e2010-04-16 15:07:51 +00001026 std::pair<uint64_t, unsigned> FieldInfo = Context.getTypeInfo(D->getType());
Anders Carlsson07209442009-11-22 17:37:31 +00001027 FieldSize = FieldInfo.first;
1028 FieldAlign = FieldInfo.second;
Anders Carlsson79474332009-07-18 20:20:21 +00001029 }
Mike Stump11289f42009-09-09 15:08:12 +00001030
Anders Carlsson07209442009-11-22 17:37:31 +00001031 if (FieldPacked)
1032 FieldAlign = 8;
1033 if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
1034 FieldAlign = std::max(FieldAlign, AA->getMaxAlignment());
1035
1036 // The maximum field alignment overrides the aligned attribute.
1037 if (MaxFieldAlignment)
1038 FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
1039
1040 // Round up the current record size to the field's alignment boundary.
1041 FieldOffset = llvm::RoundUpToAlignment(FieldOffset, FieldAlign);
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001042
Anders Carlsson07209442009-11-22 17:37:31 +00001043 if (!IsUnion) {
1044 while (true) {
1045 // Check if we can place the field at this offset.
1046 if (canPlaceFieldAtOffset(D, FieldOffset))
1047 break;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001048
Anders Carlsson07209442009-11-22 17:37:31 +00001049 // We couldn't place the field at the offset. Try again at a new offset.
1050 FieldOffset += FieldAlign;
1051 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001052
Anders Carlsson07209442009-11-22 17:37:31 +00001053 UpdateEmptyClassOffsets(D, FieldOffset);
1054 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001055
Anders Carlsson79474332009-07-18 20:20:21 +00001056 // Place this field at the current location.
1057 FieldOffsets.push_back(FieldOffset);
Mike Stump11289f42009-09-09 15:08:12 +00001058
Anders Carlsson79474332009-07-18 20:20:21 +00001059 // Reserve space for this field.
1060 if (IsUnion)
1061 Size = std::max(Size, FieldSize);
1062 else
1063 Size = FieldOffset + FieldSize;
Mike Stump11289f42009-09-09 15:08:12 +00001064
Anders Carlsson47680d82009-09-26 01:34:51 +00001065 // Update the data size.
1066 DataSize = Size;
Mike Stump11289f42009-09-09 15:08:12 +00001067
Anders Carlsson79474332009-07-18 20:20:21 +00001068 // Remember max struct/class alignment.
1069 UpdateAlignment(FieldAlign);
1070}
1071
Anders Carlssonc2226202010-05-26 05:58:59 +00001072void RecordLayoutBuilder::FinishLayout() {
Anders Carlsson79474332009-07-18 20:20:21 +00001073 // In C++, records cannot be of size 0.
Anders Carlsson5efc56e2010-04-16 15:07:51 +00001074 if (Context.getLangOptions().CPlusPlus && Size == 0)
Anders Carlsson79474332009-07-18 20:20:21 +00001075 Size = 8;
1076 // Finally, round the size of the record up to the alignment of the
1077 // record itself.
Anders Carlsson07209442009-11-22 17:37:31 +00001078 Size = llvm::RoundUpToAlignment(Size, Alignment);
Anders Carlsson79474332009-07-18 20:20:21 +00001079}
1080
Anders Carlssonc2226202010-05-26 05:58:59 +00001081void RecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) {
Anders Carlsson79474332009-07-18 20:20:21 +00001082 if (NewAlignment <= Alignment)
1083 return;
Mike Stump11289f42009-09-09 15:08:12 +00001084
Anders Carlsson79474332009-07-18 20:20:21 +00001085 assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2"));
Mike Stump11289f42009-09-09 15:08:12 +00001086
Anders Carlsson79474332009-07-18 20:20:21 +00001087 Alignment = NewAlignment;
1088}
Mike Stump11289f42009-09-09 15:08:12 +00001089
Anders Carlsson5ebf8b42009-12-07 04:35:11 +00001090const CXXMethodDecl *
Anders Carlssonc2226202010-05-26 05:58:59 +00001091RecordLayoutBuilder::ComputeKeyFunction(const CXXRecordDecl *RD) {
Anders Carlsson5ebf8b42009-12-07 04:35:11 +00001092 assert(RD->isDynamicClass() && "Class does not have any virtual methods!");
1093
Daniel Dunbarccabe482010-04-19 20:44:53 +00001094 // If a class isn't polymorphic it doesn't have a key function.
Anders Carlsson5ebf8b42009-12-07 04:35:11 +00001095 if (!RD->isPolymorphic())
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001096 return 0;
Eli Friedmanf2c79b62009-12-08 03:56:49 +00001097
1098 // A class inside an anonymous namespace doesn't have a key function. (Or
1099 // at least, there's no point to assigning a key function to such a class;
1100 // this doesn't affect the ABI.)
1101 if (RD->isInAnonymousNamespace())
1102 return 0;
1103
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001104 for (CXXRecordDecl::method_iterator I = RD->method_begin(),
1105 E = RD->method_end(); I != E; ++I) {
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001106 const CXXMethodDecl *MD = *I;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001107
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001108 if (!MD->isVirtual())
1109 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001110
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001111 if (MD->isPure())
1112 continue;
Eli Friedmanf2c79b62009-12-08 03:56:49 +00001113
Anders Carlssonf98849e2009-12-02 17:15:43 +00001114 // Ignore implicit member functions, they are always marked as inline, but
1115 // they don't have a body until they're defined.
1116 if (MD->isImplicit())
1117 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001118
Douglas Gregora318efd2010-01-05 19:06:31 +00001119 if (MD->isInlineSpecified())
1120 continue;
Eli Friedman71a26d82009-12-06 20:50:05 +00001121
1122 if (MD->hasInlineBody())
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001123 continue;
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001124
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001125 // We found it.
1126 return MD;
1127 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001128
Anders Carlssonb1d3f7c2009-11-30 23:41:22 +00001129 return 0;
1130}
1131
Anders Carlssondf291d82010-05-26 04:56:53 +00001132/// getASTRecordLayout - Get or compute information about the layout of the
1133/// specified record (struct/union/class), which indicates its size and field
1134/// position information.
1135const ASTRecordLayout &ASTContext::getASTRecordLayout(const RecordDecl *D) {
1136 D = D->getDefinition();
1137 assert(D && "Cannot get layout of forward declarations!");
1138
1139 // Look up this layout, if already laid out, return what we have.
1140 // Note that we can't save a reference to the entry because this function
1141 // is recursive.
1142 const ASTRecordLayout *Entry = ASTRecordLayouts[D];
1143 if (Entry) return *Entry;
1144
Anders Carlssond2954862010-05-26 05:10:47 +00001145 const ASTRecordLayout *NewEntry;
1146
1147 if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
Anders Carlssonc121b4e2010-05-27 00:07:01 +00001148 EmptySubobjectMap EmptySubobjects(*this, RD);
1149 RecordLayoutBuilder Builder(*this, &EmptySubobjects);
Anders Carlssond2954862010-05-26 05:10:47 +00001150 Builder.Layout(RD);
1151
1152 // FIXME: This is not always correct. See the part about bitfields at
1153 // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info.
1154 // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout.
1155 bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD();
1156
1157 // FIXME: This should be done in FinalizeLayout.
1158 uint64_t DataSize =
1159 IsPODForThePurposeOfLayout ? Builder.Size : Builder.DataSize;
1160 uint64_t NonVirtualSize =
1161 IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize;
1162
1163 NewEntry =
1164 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment,
1165 DataSize, Builder.FieldOffsets.data(),
1166 Builder.FieldOffsets.size(),
1167 NonVirtualSize,
1168 Builder.NonVirtualAlignment,
Anders Carlssonc121b4e2010-05-27 00:07:01 +00001169 EmptySubobjects.SizeOfLargestEmptySubobject,
Anders Carlssond2954862010-05-26 05:10:47 +00001170 Builder.PrimaryBase,
Anders Carlsson1d1e4cf2010-05-26 05:25:15 +00001171 Builder.PrimaryBaseIsVirtual,
Anders Carlssond2954862010-05-26 05:10:47 +00001172 Builder.Bases, Builder.VBases);
1173 } else {
Anders Carlssonc121b4e2010-05-27 00:07:01 +00001174 RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0);
Anders Carlssond2954862010-05-26 05:10:47 +00001175 Builder.Layout(D);
1176
1177 NewEntry =
1178 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment,
1179 Builder.Size,
1180 Builder.FieldOffsets.data(),
1181 Builder.FieldOffsets.size());
1182 }
1183
Anders Carlssondf291d82010-05-26 04:56:53 +00001184 ASTRecordLayouts[D] = NewEntry;
1185
1186 if (getLangOptions().DumpRecordLayouts) {
1187 llvm::errs() << "\n*** Dumping AST Record Layout\n";
1188 DumpRecordLayout(D, llvm::errs());
1189 }
1190
1191 return *NewEntry;
1192}
1193
1194const CXXMethodDecl *ASTContext::getKeyFunction(const CXXRecordDecl *RD) {
1195 RD = cast<CXXRecordDecl>(RD->getDefinition());
1196 assert(RD && "Cannot get key function for forward declarations!");
1197
1198 const CXXMethodDecl *&Entry = KeyFunctions[RD];
1199 if (!Entry)
Anders Carlssonc2226202010-05-26 05:58:59 +00001200 Entry = RecordLayoutBuilder::ComputeKeyFunction(RD);
Anders Carlssondf291d82010-05-26 04:56:53 +00001201 else
Anders Carlssonc2226202010-05-26 05:58:59 +00001202 assert(Entry == RecordLayoutBuilder::ComputeKeyFunction(RD) &&
Anders Carlssondf291d82010-05-26 04:56:53 +00001203 "Key function changed!");
1204
1205 return Entry;
1206}
1207
1208/// getInterfaceLayoutImpl - Get or compute information about the
1209/// layout of the given interface.
1210///
1211/// \param Impl - If given, also include the layout of the interface's
1212/// implementation. This may differ by including synthesized ivars.
1213const ASTRecordLayout &
1214ASTContext::getObjCLayout(const ObjCInterfaceDecl *D,
1215 const ObjCImplementationDecl *Impl) {
1216 assert(!D->isForwardDecl() && "Invalid interface decl!");
1217
1218 // Look up this layout, if already laid out, return what we have.
1219 ObjCContainerDecl *Key =
1220 Impl ? (ObjCContainerDecl*) Impl : (ObjCContainerDecl*) D;
1221 if (const ASTRecordLayout *Entry = ObjCLayouts[Key])
1222 return *Entry;
1223
1224 // Add in synthesized ivar count if laying out an implementation.
1225 if (Impl) {
1226 unsigned SynthCount = CountNonClassIvars(D);
1227 // If there aren't any sythesized ivars then reuse the interface
1228 // entry. Note we can't cache this because we simply free all
1229 // entries later; however we shouldn't look up implementations
1230 // frequently.
1231 if (SynthCount == 0)
1232 return getObjCLayout(D, 0);
1233 }
1234
Anders Carlssonc121b4e2010-05-27 00:07:01 +00001235 RecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/0);
Anders Carlsson6ed3a9a2010-05-26 05:04:25 +00001236 Builder.Layout(D);
1237
Anders Carlssondf291d82010-05-26 04:56:53 +00001238 const ASTRecordLayout *NewEntry =
Anders Carlsson6ed3a9a2010-05-26 05:04:25 +00001239 new (*this) ASTRecordLayout(*this, Builder.Size, Builder.Alignment,
1240 Builder.DataSize,
1241 Builder.FieldOffsets.data(),
1242 Builder.FieldOffsets.size());
1243
Anders Carlssondf291d82010-05-26 04:56:53 +00001244 ObjCLayouts[Key] = NewEntry;
1245
1246 return *NewEntry;
1247}
1248
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001249static void PrintOffset(llvm::raw_ostream &OS,
1250 uint64_t Offset, unsigned IndentLevel) {
1251 OS << llvm::format("%4d | ", Offset);
1252 OS.indent(IndentLevel * 2);
1253}
1254
1255static void DumpCXXRecordLayout(llvm::raw_ostream &OS,
1256 const CXXRecordDecl *RD, ASTContext &C,
1257 uint64_t Offset,
1258 unsigned IndentLevel,
1259 const char* Description,
1260 bool IncludeVirtualBases) {
1261 const ASTRecordLayout &Info = C.getASTRecordLayout(RD);
1262
1263 PrintOffset(OS, Offset, IndentLevel);
Dan Gohman145f3f12010-04-19 16:39:44 +00001264 OS << C.getTypeDeclType(const_cast<CXXRecordDecl *>(RD)).getAsString();
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001265 if (Description)
1266 OS << ' ' << Description;
1267 if (RD->isEmpty())
1268 OS << " (empty)";
1269 OS << '\n';
1270
1271 IndentLevel++;
1272
1273 const CXXRecordDecl *PrimaryBase = Info.getPrimaryBase();
1274
1275 // Vtable pointer.
1276 if (RD->isDynamicClass() && !PrimaryBase) {
1277 PrintOffset(OS, Offset, IndentLevel);
Benjamin Kramerb11416d2010-04-17 09:33:03 +00001278 OS << '(' << RD << " vtable pointer)\n";
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001279 }
1280 // Dump (non-virtual) bases
1281 for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
1282 E = RD->bases_end(); I != E; ++I) {
1283 assert(!I->getType()->isDependentType() &&
1284 "Cannot layout class with dependent bases.");
1285 if (I->isVirtual())
1286 continue;
1287
1288 const CXXRecordDecl *Base =
1289 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1290
1291 uint64_t BaseOffset = Offset + Info.getBaseClassOffset(Base) / 8;
1292
1293 DumpCXXRecordLayout(OS, Base, C, BaseOffset, IndentLevel,
1294 Base == PrimaryBase ? "(primary base)" : "(base)",
1295 /*IncludeVirtualBases=*/false);
1296 }
1297
1298 // Dump fields.
1299 uint64_t FieldNo = 0;
1300 for (CXXRecordDecl::field_iterator I = RD->field_begin(),
1301 E = RD->field_end(); I != E; ++I, ++FieldNo) {
1302 const FieldDecl *Field = *I;
1303 uint64_t FieldOffset = Offset + Info.getFieldOffset(FieldNo) / 8;
1304
1305 if (const RecordType *RT = Field->getType()->getAs<RecordType>()) {
1306 if (const CXXRecordDecl *D = dyn_cast<CXXRecordDecl>(RT->getDecl())) {
1307 DumpCXXRecordLayout(OS, D, C, FieldOffset, IndentLevel,
1308 Field->getNameAsCString(),
1309 /*IncludeVirtualBases=*/true);
1310 continue;
1311 }
1312 }
1313
1314 PrintOffset(OS, FieldOffset, IndentLevel);
Benjamin Kramerb11416d2010-04-17 09:33:03 +00001315 OS << Field->getType().getAsString() << ' ' << Field << '\n';
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001316 }
1317
1318 if (!IncludeVirtualBases)
1319 return;
1320
1321 // Dump virtual bases.
1322 for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(),
1323 E = RD->vbases_end(); I != E; ++I) {
1324 assert(I->isVirtual() && "Found non-virtual class!");
1325 const CXXRecordDecl *VBase =
1326 cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
1327
1328 uint64_t VBaseOffset = Offset + Info.getVBaseClassOffset(VBase) / 8;
1329 DumpCXXRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel,
1330 VBase == PrimaryBase ?
1331 "(primary virtual base)" : "(virtual base)",
1332 /*IncludeVirtualBases=*/false);
1333 }
Daniel Dunbaraa423af2010-04-08 02:59:49 +00001334
1335 OS << " sizeof=" << Info.getSize() / 8;
1336 OS << ", dsize=" << Info.getDataSize() / 8;
1337 OS << ", align=" << Info.getAlignment() / 8 << '\n';
1338 OS << " nvsize=" << Info.getNonVirtualSize() / 8;
1339 OS << ", nvalign=" << Info.getNonVirtualAlign() / 8 << '\n';
1340 OS << '\n';
1341}
Daniel Dunbarccabe482010-04-19 20:44:53 +00001342
1343void ASTContext::DumpRecordLayout(const RecordDecl *RD,
1344 llvm::raw_ostream &OS) {
1345 const ASTRecordLayout &Info = getASTRecordLayout(RD);
1346
1347 if (const CXXRecordDecl *CXXRD = dyn_cast<CXXRecordDecl>(RD))
1348 return DumpCXXRecordLayout(OS, CXXRD, *this, 0, 0, 0,
1349 /*IncludeVirtualBases=*/true);
1350
1351 OS << "Type: " << getTypeDeclType(RD).getAsString() << "\n";
1352 OS << "Record: ";
1353 RD->dump();
1354 OS << "\nLayout: ";
1355 OS << "<ASTRecordLayout\n";
1356 OS << " Size:" << Info.getSize() << "\n";
1357 OS << " DataSize:" << Info.getDataSize() << "\n";
1358 OS << " Alignment:" << Info.getAlignment() << "\n";
1359 OS << " FieldOffsets: [";
1360 for (unsigned i = 0, e = Info.getFieldCount(); i != e; ++i) {
1361 if (i) OS << ", ";
1362 OS << Info.getFieldOffset(i);
1363 }
1364 OS << "]>\n";
1365}