RecordLayoutBuilder.cpp revision 11391b7e25fe03a8f380a233137d14465e1074ec 
1//=== ASTRecordLayoutBuilder.cpp - Helper class for building record layouts ==//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#include "RecordLayoutBuilder.h"
11
12#include "clang/AST/Attr.h"
13#include "clang/AST/Decl.h"
14#include "clang/AST/DeclCXX.h"
15#include "clang/AST/DeclObjC.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/RecordLayout.h"
18#include "clang/Basic/TargetInfo.h"
19#include <llvm/ADT/SmallSet.h>
20#include <llvm/Support/MathExtras.h>
21
22using namespace clang;
23
24ASTRecordLayoutBuilder::ASTRecordLayoutBuilder(ASTContext &Ctx)
25  : Ctx(Ctx), Size(0), Alignment(8), Packed(false), MaxFieldAlignment(0),
26  NextOffset(0), IsUnion(false), NonVirtualSize(0), NonVirtualAlignment(8) {}
27
28/// LayoutVtable - Lay out the vtable and set PrimaryBase.
29void ASTRecordLayoutBuilder::LayoutVtable(const CXXRecordDecl *RD) {
30  // FIXME: audit indirect virtual bases
31  if (!RD->isPolymorphic() && !RD->getNumVBases()) {
32    // There is no primary base in this case.
33    setPrimaryBase(0, false);
34    return;
35  }
36
37  SelectPrimaryBase(RD);
38  if (PrimaryBase == 0) {
39    int AS = 0;
40    UpdateAlignment(Ctx.Target.getPointerAlign(AS));
41    Size += Ctx.Target.getPointerWidth(AS);
42    NextOffset = Size;
43  }
44}
45
46void
47ASTRecordLayoutBuilder::LayoutNonVirtualBases(const CXXRecordDecl *RD) {
48  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
49       e = RD->bases_end(); i != e; ++i) {
50    if (!i->isVirtual()) {
51      const CXXRecordDecl *Base =
52        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
53      // Skip the PrimaryBase here, as it is laid down first.
54      if (Base != PrimaryBase)
55        LayoutBaseNonVirtually(Base);
56    }
57  }
58}
59
60// Helper routines related to the abi definition from:
61//   http://www.codesourcery.com/public/cxx-abi/abi.html
62//
63/// IsNearlyEmpty - Indicates when a class has a vtable pointer, but
64/// no other data.
65bool ASTRecordLayoutBuilder::IsNearlyEmpty(const CXXRecordDecl *RD) {
66  // FIXME: Audit the corners
67  if (!RD->isDynamicClass())
68    return false;
69  const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
70  if (BaseInfo.getNonVirtualSize() == Ctx.Target.getPointerWidth(0))
71    return true;
72  return false;
73}
74
75void ASTRecordLayoutBuilder::SelectPrimaryForBase(const CXXRecordDecl *RD,
76                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
77  const ASTRecordLayout &Layout = Ctx.getASTRecordLayout(RD);
78  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
79  const bool PrimaryBaseWasVirtual = Layout.getPrimaryBaseWasVirtual();
80  if (PrimaryBaseWasVirtual) {
81    IndirectPrimary.insert(PrimaryBase);
82  }
83  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
84       e = RD->bases_end(); i != e; ++i) {
85    const CXXRecordDecl *Base =
86      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
87    // Only bases with virtual bases participate in computing the
88    // indirect primary virtual base classes.
89    // FIXME: audit indirect virtual bases
90    if (Base->getNumVBases() == 0)
91      continue;
92    SelectPrimaryForBase(Base, IndirectPrimary);
93  }
94}
95
96void ASTRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD,
97                                             const CXXRecordDecl *&FirstPrimary,
98                    llvm::SmallSet<const CXXRecordDecl*, 32> &IndirectPrimary) {
99  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
100         e = RD->bases_end(); i != e; ++i) {
101    const CXXRecordDecl *Base =
102      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
103    if (!i->isVirtual()) {
104      SelectPrimaryVBase(Base, FirstPrimary, IndirectPrimary);
105      if (PrimaryBase)
106        return;
107      continue;
108    }
109    if (IsNearlyEmpty(Base)) {
110      if (FirstPrimary==0)
111        FirstPrimary = Base;
112      if (!IndirectPrimary.count(Base)) {
113        setPrimaryBase(Base, true);
114        return;
115      }
116    }
117  }
118}
119
120/// SelectPrimaryBase - Selects the primary base for the given class and
121/// record that with setPrimaryBase.
122void ASTRecordLayoutBuilder::SelectPrimaryBase(const CXXRecordDecl *RD) {
123  // The primary base is the first non-virtual indirect or direct base class,
124  // if one exists.
125  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
126       e = RD->bases_end(); i != e; ++i) {
127    if (!i->isVirtual()) {
128      const CXXRecordDecl *Base =
129        cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
130      if (Base->isDynamicClass()) {
131        setPrimaryBase(Base, false);
132        return;
133      }
134    }
135  }
136
137  setPrimaryBase(0, false);
138
139  // Otherwise, it is the first nearly empty virtual base that is not an
140  // indirect primary virtual base class, if one exists.
141
142  // If we have no virtual bases at this point, bail out as the searching below
143  // is expensive.
144  // FIXME: audit indirect virtual bases
145  if (RD->getNumVBases() == 0) {
146    return;
147  }
148
149  // First, we compute all the primary virtual bases for all of our direct and
150  // indirect bases, and record all their primary virtual base classes.
151  const CXXRecordDecl *FirstPrimary = 0;
152  llvm::SmallSet<const CXXRecordDecl*, 32> IndirectPrimary;
153  for (CXXRecordDecl::base_class_const_iterator i = RD->bases_begin(),
154       e = RD->bases_end(); i != e; ++i) {
155    const CXXRecordDecl *Base =
156      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
157    SelectPrimaryForBase(Base, IndirectPrimary);
158  }
159
160  // Then we can search for the first nearly empty virtual base itself.
161  SelectPrimaryVBase(RD, FirstPrimary, IndirectPrimary);
162
163  // Otherwise if is the first nearly empty virtual base, if one exists,
164  // otherwise there is no primary base class.
165  setPrimaryBase(FirstPrimary, true);
166  return;
167}
168
169void ASTRecordLayoutBuilder::LayoutVirtualBase(const CXXRecordDecl *RD) {
170  LayoutBaseNonVirtually(RD);
171}
172
173void ASTRecordLayoutBuilder::LayoutVirtualBases(const CXXRecordDecl *RD) {
174  // FIXME: audit indirect virtual bases
175  for (CXXRecordDecl::base_class_const_iterator i = RD->vbases_begin(),
176         e = RD->vbases_end(); i != e; ++i) {
177    const CXXRecordDecl *Base =
178      cast<CXXRecordDecl>(i->getType()->getAs<RecordType>()->getDecl());
179    if (Base != PrimaryBase)
180      LayoutVirtualBase(Base);
181  }
182}
183
184void ASTRecordLayoutBuilder::LayoutBaseNonVirtually(const CXXRecordDecl *RD) {
185  const ASTRecordLayout &BaseInfo = Ctx.getASTRecordLayout(RD);
186    assert(BaseInfo.getDataSize() > 0 &&
187           "FIXME: Handle empty classes.");
188
189  unsigned BaseAlign = BaseInfo.getNonVirtualAlign();
190  uint64_t BaseSize = BaseInfo.getNonVirtualSize();
191
192  // Round up the current record size to the base's alignment boundary.
193  Size = (Size + (BaseAlign-1)) & ~(BaseAlign-1);
194
195  // Add base class offsets.
196  Bases.push_back(RD);
197  BaseOffsets.push_back(Size);
198
199  // Reserve space for this base.
200  Size += BaseSize;
201
202  // Remember the next available offset.
203  NextOffset = Size;
204
205  // Remember max struct/class alignment.
206  UpdateAlignment(BaseAlign);
207}
208
209void ASTRecordLayoutBuilder::Layout(const RecordDecl *D) {
210  IsUnion = D->isUnion();
211
212  Packed = D->hasAttr<PackedAttr>();
213
214  // The #pragma pack attribute specifies the maximum field alignment.
215  if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
216    MaxFieldAlignment = PPA->getAlignment();
217
218  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
219    UpdateAlignment(AA->getAlignment());
220
221  // If this is a C++ class, lay out the nonvirtual bases.
222  const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D);
223  if (RD) {
224    LayoutVtable(RD);
225    // PrimaryBase goes first.
226    if (PrimaryBase)
227      LayoutBaseNonVirtually(PrimaryBase);
228    LayoutNonVirtualBases(RD);
229  }
230
231  LayoutFields(D);
232
233  NonVirtualSize = Size;
234  NonVirtualAlignment = Alignment;
235
236  if (RD)
237    LayoutVirtualBases(RD);
238
239  // Finally, round the size of the total struct up to the alignment of the
240  // struct itself.
241  FinishLayout();
242}
243
244void ASTRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D,
245                                    const ObjCImplementationDecl *Impl) {
246  if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
247    const ASTRecordLayout &SL = Ctx.getASTObjCInterfaceLayout(SD);
248
249    UpdateAlignment(SL.getAlignment());
250
251    // We start laying out ivars not at the end of the superclass
252    // structure, but at the next byte following the last field.
253    Size = llvm::RoundUpToAlignment(SL.getDataSize(), 8);
254    NextOffset = Size;
255  }
256
257  Packed = D->hasAttr<PackedAttr>();
258
259  // The #pragma pack attribute specifies the maximum field alignment.
260  if (const PragmaPackAttr *PPA = D->getAttr<PragmaPackAttr>())
261    MaxFieldAlignment = PPA->getAlignment();
262
263  if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
264    UpdateAlignment(AA->getAlignment());
265
266  // Layout each ivar sequentially.
267  llvm::SmallVector<ObjCIvarDecl*, 16> Ivars;
268  Ctx.ShallowCollectObjCIvars(D, Ivars, Impl);
269  for (unsigned i = 0, e = Ivars.size(); i != e; ++i)
270    LayoutField(Ivars[i]);
271
272  // Finally, round the size of the total struct up to the alignment of the
273  // struct itself.
274  FinishLayout();
275}
276
277void ASTRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
278  // Layout each field, for now, just sequentially, respecting alignment.  In
279  // the future, this will need to be tweakable by targets.
280  for (RecordDecl::field_iterator Field = D->field_begin(),
281       FieldEnd = D->field_end(); Field != FieldEnd; ++Field)
282    LayoutField(*Field);
283}
284
285void ASTRecordLayoutBuilder::LayoutField(const FieldDecl *D) {
286  bool FieldPacked = Packed;
287  uint64_t FieldOffset = IsUnion ? 0 : Size;
288  uint64_t FieldSize;
289  unsigned FieldAlign;
290
291  FieldPacked |= D->hasAttr<PackedAttr>();
292
293  if (const Expr *BitWidthExpr = D->getBitWidth()) {
294    // TODO: Need to check this algorithm on other targets!
295    //       (tested on Linux-X86)
296    FieldSize = BitWidthExpr->EvaluateAsInt(Ctx).getZExtValue();
297
298    std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
299    uint64_t TypeSize = FieldInfo.first;
300
301    FieldAlign = FieldInfo.second;
302
303    if (FieldPacked)
304      FieldAlign = 1;
305    if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
306      FieldAlign = std::max(FieldAlign, AA->getAlignment());
307    // The maximum field alignment overrides the aligned attribute.
308    if (MaxFieldAlignment)
309      FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
310
311    // Check if we need to add padding to give the field the correct
312    // alignment.
313    if (FieldSize == 0 || (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)
314      FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1);
315
316    // Padding members don't affect overall alignment
317    if (!D->getIdentifier())
318      FieldAlign = 1;
319  } else {
320    if (D->getType()->isIncompleteArrayType()) {
321      // This is a flexible array member; we can't directly
322      // query getTypeInfo about these, so we figure it out here.
323      // Flexible array members don't have any size, but they
324      // have to be aligned appropriately for their element type.
325      FieldSize = 0;
326      const ArrayType* ATy = Ctx.getAsArrayType(D->getType());
327      FieldAlign = Ctx.getTypeAlign(ATy->getElementType());
328    } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
329      unsigned AS = RT->getPointeeType().getAddressSpace();
330      FieldSize = Ctx.Target.getPointerWidth(AS);
331      FieldAlign = Ctx.Target.getPointerAlign(AS);
332    } else {
333      std::pair<uint64_t, unsigned> FieldInfo = Ctx.getTypeInfo(D->getType());
334      FieldSize = FieldInfo.first;
335      FieldAlign = FieldInfo.second;
336    }
337
338    if (FieldPacked)
339      FieldAlign = 8;
340    if (const AlignedAttr *AA = D->getAttr<AlignedAttr>())
341      FieldAlign = std::max(FieldAlign, AA->getAlignment());
342    // The maximum field alignment overrides the aligned attribute.
343    if (MaxFieldAlignment)
344      FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
345
346    // Round up the current record size to the field's alignment boundary.
347    FieldOffset = (FieldOffset + (FieldAlign-1)) & ~(FieldAlign-1);
348  }
349
350  // Place this field at the current location.
351  FieldOffsets.push_back(FieldOffset);
352
353  // Reserve space for this field.
354  if (IsUnion)
355    Size = std::max(Size, FieldSize);
356  else
357    Size = FieldOffset + FieldSize;
358
359  // Remember the next available offset.
360  NextOffset = Size;
361
362  // Remember max struct/class alignment.
363  UpdateAlignment(FieldAlign);
364}
365
366void ASTRecordLayoutBuilder::FinishLayout() {
367  // In C++, records cannot be of size 0.
368  if (Ctx.getLangOptions().CPlusPlus && Size == 0)
369    Size = 8;
370  // Finally, round the size of the record up to the alignment of the
371  // record itself.
372  Size = (Size + (Alignment-1)) & ~(Alignment-1);
373}
374
375void ASTRecordLayoutBuilder::UpdateAlignment(unsigned NewAlignment) {
376  if (NewAlignment <= Alignment)
377    return;
378
379  assert(llvm::isPowerOf2_32(NewAlignment && "Alignment not a power of 2"));
380
381  Alignment = NewAlignment;
382}
383
384const ASTRecordLayout *
385ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
386                                      const RecordDecl *D) {
387  ASTRecordLayoutBuilder Builder(Ctx);
388
389  Builder.Layout(D);
390
391  if (!isa<CXXRecordDecl>(D))
392    return new ASTRecordLayout(Builder.Size, Builder.Alignment, Builder.Size,
393                               Builder.FieldOffsets.data(),
394                               Builder.FieldOffsets.size());
395
396  // FIXME: This is not always correct. See the part about bitfields at
397  // http://www.codesourcery.com/public/cxx-abi/abi.html#POD for more info.
398  // FIXME: IsPODForThePurposeOfLayout should be stored in the record layout.
399  bool IsPODForThePurposeOfLayout = cast<CXXRecordDecl>(D)->isPOD();
400
401  assert(Builder.Bases.size() == Builder.BaseOffsets.size() &&
402         "Base offsets vector must be same size as bases vector!");
403
404  // FIXME: This should be done in FinalizeLayout.
405  uint64_t DataSize =
406    IsPODForThePurposeOfLayout ? Builder.Size : Builder.NextOffset;
407  uint64_t NonVirtualSize =
408    IsPODForThePurposeOfLayout ? DataSize : Builder.NonVirtualSize;
409
410  return new ASTRecordLayout(Builder.Size, Builder.Alignment, DataSize,
411                             Builder.FieldOffsets.data(),
412                             Builder.FieldOffsets.size(),
413                             NonVirtualSize,
414                             Builder.NonVirtualAlignment,
415                             Builder.PrimaryBase,
416                             Builder.PrimaryBaseWasVirtual,
417                             Builder.Bases.data(),
418                             Builder.BaseOffsets.data(),
419                             Builder.Bases.size());
420}
421
422const ASTRecordLayout *
423ASTRecordLayoutBuilder::ComputeLayout(ASTContext &Ctx,
424                                      const ObjCInterfaceDecl *D,
425                                      const ObjCImplementationDecl *Impl) {
426  ASTRecordLayoutBuilder Builder(Ctx);
427
428  Builder.Layout(D, Impl);
429
430  return new ASTRecordLayout(Builder.Size, Builder.Alignment,
431                             Builder.NextOffset,
432                             Builder.FieldOffsets.data(),
433                             Builder.FieldOffsets.size());
434}
435