• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- CGRecordLayoutBuilder.cpp - CGRecordLayout builder  ----*- C++ -*-===//
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 // Builder implementation for CGRecordLayout objects.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "CGRecordLayout.h"
15 #include "CGCXXABI.h"
16 #include "CodeGenTypes.h"
17 #include "clang/AST/ASTContext.h"
18 #include "clang/AST/Attr.h"
19 #include "clang/AST/CXXInheritance.h"
20 #include "clang/AST/DeclCXX.h"
21 #include "clang/AST/Expr.h"
22 #include "clang/AST/RecordLayout.h"
23 #include "clang/Frontend/CodeGenOptions.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/Type.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/MathExtras.h"
29 #include "llvm/Support/raw_ostream.h"
30 using namespace clang;
31 using namespace CodeGen;
32 
33 namespace {
34 /// The CGRecordLowering is responsible for lowering an ASTRecordLayout to an
35 /// llvm::Type.  Some of the lowering is straightforward, some is not.  Here we
36 /// detail some of the complexities and weirdnesses here.
37 /// * LLVM does not have unions - Unions can, in theory be represented by any
38 ///   llvm::Type with correct size.  We choose a field via a specific heuristic
39 ///   and add padding if necessary.
40 /// * LLVM does not have bitfields - Bitfields are collected into contiguous
41 ///   runs and allocated as a single storage type for the run.  ASTRecordLayout
42 ///   contains enough information to determine where the runs break.  Microsoft
43 ///   and Itanium follow different rules and use different codepaths.
44 /// * It is desired that, when possible, bitfields use the appropriate iN type
45 ///   when lowered to llvm types.  For example unsigned x : 24 gets lowered to
46 ///   i24.  This isn't always possible because i24 has storage size of 32 bit
47 ///   and if it is possible to use that extra byte of padding we must use
48 ///   [i8 x 3] instead of i24.  The function clipTailPadding does this.
49 ///   C++ examples that require clipping:
50 ///   struct { int a : 24; char b; }; // a must be clipped, b goes at offset 3
51 ///   struct A { int a : 24; }; // a must be clipped because a struct like B
52 //    could exist: struct B : A { char b; }; // b goes at offset 3
53 /// * Clang ignores 0 sized bitfields and 0 sized bases but *not* zero sized
54 ///   fields.  The existing asserts suggest that LLVM assumes that *every* field
55 ///   has an underlying storage type.  Therefore empty structures containing
56 ///   zero sized subobjects such as empty records or zero sized arrays still get
57 ///   a zero sized (empty struct) storage type.
58 /// * Clang reads the complete type rather than the base type when generating
59 ///   code to access fields.  Bitfields in tail position with tail padding may
60 ///   be clipped in the base class but not the complete class (we may discover
61 ///   that the tail padding is not used in the complete class.) However,
62 ///   because LLVM reads from the complete type it can generate incorrect code
63 ///   if we do not clip the tail padding off of the bitfield in the complete
64 ///   layout.  This introduces a somewhat awkward extra unnecessary clip stage.
65 ///   The location of the clip is stored internally as a sentinal of type
66 ///   SCISSOR.  If LLVM were updated to read base types (which it probably
67 ///   should because locations of things such as VBases are bogus in the llvm
68 ///   type anyway) then we could eliminate the SCISSOR.
69 /// * Itanium allows nearly empty primary virtual bases.  These bases don't get
70 ///   get their own storage because they're laid out as part of another base
71 ///   or at the beginning of the structure.  Determining if a VBase actually
72 ///   gets storage awkwardly involves a walk of all bases.
73 /// * VFPtrs and VBPtrs do *not* make a record NotZeroInitializable.
74 struct CGRecordLowering {
75   // MemberInfo is a helper structure that contains information about a record
76   // member.  In additional to the standard member types, there exists a
77   // sentinal member type that ensures correct rounding.
78   struct MemberInfo {
79     CharUnits Offset;
80     enum InfoKind { VFPtr, VBPtr, Field, Base, VBase, Scissor } Kind;
81     llvm::Type *Data;
82     union {
83       const FieldDecl *FD;
84       const CXXRecordDecl *RD;
85     };
MemberInfo__anon5083c5770111::CGRecordLowering::MemberInfo86     MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data,
87                const FieldDecl *FD = nullptr)
88       : Offset(Offset), Kind(Kind), Data(Data), FD(FD) {}
MemberInfo__anon5083c5770111::CGRecordLowering::MemberInfo89     MemberInfo(CharUnits Offset, InfoKind Kind, llvm::Type *Data,
90                const CXXRecordDecl *RD)
91       : Offset(Offset), Kind(Kind), Data(Data), RD(RD) {}
92     // MemberInfos are sorted so we define a < operator.
operator <__anon5083c5770111::CGRecordLowering::MemberInfo93     bool operator <(const MemberInfo& a) const { return Offset < a.Offset; }
94   };
95   // The constructor.
96   CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D, bool Packed);
97   // Short helper routines.
98   /// \brief Constructs a MemberInfo instance from an offset and llvm::Type *.
StorageInfo__anon5083c5770111::CGRecordLowering99   MemberInfo StorageInfo(CharUnits Offset, llvm::Type *Data) {
100     return MemberInfo(Offset, MemberInfo::Field, Data);
101   }
102 
103   /// The Microsoft bitfield layout rule allocates discrete storage
104   /// units of the field's formal type and only combines adjacent
105   /// fields of the same formal type.  We want to emit a layout with
106   /// these discrete storage units instead of combining them into a
107   /// continuous run.
isDiscreteBitFieldABI__anon5083c5770111::CGRecordLowering108   bool isDiscreteBitFieldABI() {
109     return Context.getTargetInfo().getCXXABI().isMicrosoft() ||
110            D->isMsStruct(Context);
111   }
112 
113   /// The Itanium base layout rule allows virtual bases to overlap
114   /// other bases, which complicates layout in specific ways.
115   ///
116   /// Note specifically that the ms_struct attribute doesn't change this.
isOverlappingVBaseABI__anon5083c5770111::CGRecordLowering117   bool isOverlappingVBaseABI() {
118     return !Context.getTargetInfo().getCXXABI().isMicrosoft();
119   }
120 
121   /// \brief Wraps llvm::Type::getIntNTy with some implicit arguments.
getIntNType__anon5083c5770111::CGRecordLowering122   llvm::Type *getIntNType(uint64_t NumBits) {
123     return llvm::Type::getIntNTy(Types.getLLVMContext(),
124                                  (unsigned)llvm::alignTo(NumBits, 8));
125   }
126   /// \brief Gets an llvm type of size NumBytes and alignment 1.
getByteArrayType__anon5083c5770111::CGRecordLowering127   llvm::Type *getByteArrayType(CharUnits NumBytes) {
128     assert(!NumBytes.isZero() && "Empty byte arrays aren't allowed.");
129     llvm::Type *Type = llvm::Type::getInt8Ty(Types.getLLVMContext());
130     return NumBytes == CharUnits::One() ? Type :
131         (llvm::Type *)llvm::ArrayType::get(Type, NumBytes.getQuantity());
132   }
133   /// \brief Gets the storage type for a field decl and handles storage
134   /// for itanium bitfields that are smaller than their declared type.
getStorageType__anon5083c5770111::CGRecordLowering135   llvm::Type *getStorageType(const FieldDecl *FD) {
136     llvm::Type *Type = Types.ConvertTypeForMem(FD->getType());
137     if (!FD->isBitField()) return Type;
138     if (isDiscreteBitFieldABI()) return Type;
139     return getIntNType(std::min(FD->getBitWidthValue(Context),
140                              (unsigned)Context.toBits(getSize(Type))));
141   }
142   /// \brief Gets the llvm Basesubobject type from a CXXRecordDecl.
getStorageType__anon5083c5770111::CGRecordLowering143   llvm::Type *getStorageType(const CXXRecordDecl *RD) {
144     return Types.getCGRecordLayout(RD).getBaseSubobjectLLVMType();
145   }
bitsToCharUnits__anon5083c5770111::CGRecordLowering146   CharUnits bitsToCharUnits(uint64_t BitOffset) {
147     return Context.toCharUnitsFromBits(BitOffset);
148   }
getSize__anon5083c5770111::CGRecordLowering149   CharUnits getSize(llvm::Type *Type) {
150     return CharUnits::fromQuantity(DataLayout.getTypeAllocSize(Type));
151   }
getAlignment__anon5083c5770111::CGRecordLowering152   CharUnits getAlignment(llvm::Type *Type) {
153     return CharUnits::fromQuantity(DataLayout.getABITypeAlignment(Type));
154   }
isZeroInitializable__anon5083c5770111::CGRecordLowering155   bool isZeroInitializable(const FieldDecl *FD) {
156     return Types.isZeroInitializable(FD->getType());
157   }
isZeroInitializable__anon5083c5770111::CGRecordLowering158   bool isZeroInitializable(const RecordDecl *RD) {
159     return Types.isZeroInitializable(RD);
160   }
appendPaddingBytes__anon5083c5770111::CGRecordLowering161   void appendPaddingBytes(CharUnits Size) {
162     if (!Size.isZero())
163       FieldTypes.push_back(getByteArrayType(Size));
164   }
getFieldBitOffset__anon5083c5770111::CGRecordLowering165   uint64_t getFieldBitOffset(const FieldDecl *FD) {
166     return Layout.getFieldOffset(FD->getFieldIndex());
167   }
168   // Layout routines.
169   void setBitFieldInfo(const FieldDecl *FD, CharUnits StartOffset,
170                        llvm::Type *StorageType);
171   /// \brief Lowers an ASTRecordLayout to a llvm type.
172   void lower(bool NonVirtualBaseType);
173   void lowerUnion();
174   void accumulateFields();
175   void accumulateBitFields(RecordDecl::field_iterator Field,
176                         RecordDecl::field_iterator FieldEnd);
177   void accumulateBases();
178   void accumulateVPtrs();
179   void accumulateVBases();
180   /// \brief Recursively searches all of the bases to find out if a vbase is
181   /// not the primary vbase of some base class.
182   bool hasOwnStorage(const CXXRecordDecl *Decl, const CXXRecordDecl *Query);
183   void calculateZeroInit();
184   /// \brief Lowers bitfield storage types to I8 arrays for bitfields with tail
185   /// padding that is or can potentially be used.
186   void clipTailPadding();
187   /// \brief Determines if we need a packed llvm struct.
188   void determinePacked(bool NVBaseType);
189   /// \brief Inserts padding everwhere it's needed.
190   void insertPadding();
191   /// \brief Fills out the structures that are ultimately consumed.
192   void fillOutputFields();
193   // Input memoization fields.
194   CodeGenTypes &Types;
195   const ASTContext &Context;
196   const RecordDecl *D;
197   const CXXRecordDecl *RD;
198   const ASTRecordLayout &Layout;
199   const llvm::DataLayout &DataLayout;
200   // Helpful intermediate data-structures.
201   std::vector<MemberInfo> Members;
202   // Output fields, consumed by CodeGenTypes::ComputeRecordLayout.
203   SmallVector<llvm::Type *, 16> FieldTypes;
204   llvm::DenseMap<const FieldDecl *, unsigned> Fields;
205   llvm::DenseMap<const FieldDecl *, CGBitFieldInfo> BitFields;
206   llvm::DenseMap<const CXXRecordDecl *, unsigned> NonVirtualBases;
207   llvm::DenseMap<const CXXRecordDecl *, unsigned> VirtualBases;
208   bool IsZeroInitializable : 1;
209   bool IsZeroInitializableAsBase : 1;
210   bool Packed : 1;
211 private:
212   CGRecordLowering(const CGRecordLowering &) = delete;
213   void operator =(const CGRecordLowering &) = delete;
214 };
215 } // namespace {
216 
CGRecordLowering(CodeGenTypes & Types,const RecordDecl * D,bool Packed)217 CGRecordLowering::CGRecordLowering(CodeGenTypes &Types, const RecordDecl *D,                                 bool Packed)
218   : Types(Types), Context(Types.getContext()), D(D),
219     RD(dyn_cast<CXXRecordDecl>(D)),
220     Layout(Types.getContext().getASTRecordLayout(D)),
221     DataLayout(Types.getDataLayout()), IsZeroInitializable(true),
222     IsZeroInitializableAsBase(true), Packed(Packed) {}
223 
setBitFieldInfo(const FieldDecl * FD,CharUnits StartOffset,llvm::Type * StorageType)224 void CGRecordLowering::setBitFieldInfo(
225     const FieldDecl *FD, CharUnits StartOffset, llvm::Type *StorageType) {
226   CGBitFieldInfo &Info = BitFields[FD->getCanonicalDecl()];
227   Info.IsSigned = FD->getType()->isSignedIntegerOrEnumerationType();
228   Info.Offset = (unsigned)(getFieldBitOffset(FD) - Context.toBits(StartOffset));
229   Info.Size = FD->getBitWidthValue(Context);
230   Info.StorageSize = (unsigned)DataLayout.getTypeAllocSizeInBits(StorageType);
231   Info.StorageOffset = StartOffset;
232   if (Info.Size > Info.StorageSize)
233     Info.Size = Info.StorageSize;
234   // Reverse the bit offsets for big endian machines. Because we represent
235   // a bitfield as a single large integer load, we can imagine the bits
236   // counting from the most-significant-bit instead of the
237   // least-significant-bit.
238   if (DataLayout.isBigEndian())
239     Info.Offset = Info.StorageSize - (Info.Offset + Info.Size);
240 }
241 
lower(bool NVBaseType)242 void CGRecordLowering::lower(bool NVBaseType) {
243   // The lowering process implemented in this function takes a variety of
244   // carefully ordered phases.
245   // 1) Store all members (fields and bases) in a list and sort them by offset.
246   // 2) Add a 1-byte capstone member at the Size of the structure.
247   // 3) Clip bitfield storages members if their tail padding is or might be
248   //    used by another field or base.  The clipping process uses the capstone
249   //    by treating it as another object that occurs after the record.
250   // 4) Determine if the llvm-struct requires packing.  It's important that this
251   //    phase occur after clipping, because clipping changes the llvm type.
252   //    This phase reads the offset of the capstone when determining packedness
253   //    and updates the alignment of the capstone to be equal of the alignment
254   //    of the record after doing so.
255   // 5) Insert padding everywhere it is needed.  This phase requires 'Packed' to
256   //    have been computed and needs to know the alignment of the record in
257   //    order to understand if explicit tail padding is needed.
258   // 6) Remove the capstone, we don't need it anymore.
259   // 7) Determine if this record can be zero-initialized.  This phase could have
260   //    been placed anywhere after phase 1.
261   // 8) Format the complete list of members in a way that can be consumed by
262   //    CodeGenTypes::ComputeRecordLayout.
263   CharUnits Size = NVBaseType ? Layout.getNonVirtualSize() : Layout.getSize();
264   if (D->isUnion())
265     return lowerUnion();
266   accumulateFields();
267   // RD implies C++.
268   if (RD) {
269     accumulateVPtrs();
270     accumulateBases();
271     if (Members.empty())
272       return appendPaddingBytes(Size);
273     if (!NVBaseType)
274       accumulateVBases();
275   }
276   std::stable_sort(Members.begin(), Members.end());
277   Members.push_back(StorageInfo(Size, getIntNType(8)));
278   clipTailPadding();
279   determinePacked(NVBaseType);
280   insertPadding();
281   Members.pop_back();
282   calculateZeroInit();
283   fillOutputFields();
284 }
285 
lowerUnion()286 void CGRecordLowering::lowerUnion() {
287   CharUnits LayoutSize = Layout.getSize();
288   llvm::Type *StorageType = nullptr;
289   bool SeenNamedMember = false;
290   // Iterate through the fields setting bitFieldInfo and the Fields array. Also
291   // locate the "most appropriate" storage type.  The heuristic for finding the
292   // storage type isn't necessary, the first (non-0-length-bitfield) field's
293   // type would work fine and be simpler but would be different than what we've
294   // been doing and cause lit tests to change.
295   for (const auto *Field : D->fields()) {
296     if (Field->isBitField()) {
297       // Skip 0 sized bitfields.
298       if (Field->getBitWidthValue(Context) == 0)
299         continue;
300       llvm::Type *FieldType = getStorageType(Field);
301       if (LayoutSize < getSize(FieldType))
302         FieldType = getByteArrayType(LayoutSize);
303       setBitFieldInfo(Field, CharUnits::Zero(), FieldType);
304     }
305     Fields[Field->getCanonicalDecl()] = 0;
306     llvm::Type *FieldType = getStorageType(Field);
307     // Compute zero-initializable status.
308     // This union might not be zero initialized: it may contain a pointer to
309     // data member which might have some exotic initialization sequence.
310     // If this is the case, then we aught not to try and come up with a "better"
311     // type, it might not be very easy to come up with a Constant which
312     // correctly initializes it.
313     if (!SeenNamedMember) {
314       SeenNamedMember = Field->getIdentifier();
315       if (!SeenNamedMember)
316         if (const auto *FieldRD =
317                 dyn_cast_or_null<RecordDecl>(Field->getType()->getAsTagDecl()))
318         SeenNamedMember = FieldRD->findFirstNamedDataMember();
319       if (SeenNamedMember && !isZeroInitializable(Field)) {
320         IsZeroInitializable = IsZeroInitializableAsBase = false;
321         StorageType = FieldType;
322       }
323     }
324     // Because our union isn't zero initializable, we won't be getting a better
325     // storage type.
326     if (!IsZeroInitializable)
327       continue;
328     // Conditionally update our storage type if we've got a new "better" one.
329     if (!StorageType ||
330         getAlignment(FieldType) >  getAlignment(StorageType) ||
331         (getAlignment(FieldType) == getAlignment(StorageType) &&
332         getSize(FieldType) > getSize(StorageType)))
333       StorageType = FieldType;
334   }
335   // If we have no storage type just pad to the appropriate size and return.
336   if (!StorageType)
337     return appendPaddingBytes(LayoutSize);
338   // If our storage size was bigger than our required size (can happen in the
339   // case of packed bitfields on Itanium) then just use an I8 array.
340   if (LayoutSize < getSize(StorageType))
341     StorageType = getByteArrayType(LayoutSize);
342   FieldTypes.push_back(StorageType);
343   appendPaddingBytes(LayoutSize - getSize(StorageType));
344   // Set packed if we need it.
345   if (LayoutSize % getAlignment(StorageType))
346     Packed = true;
347 }
348 
accumulateFields()349 void CGRecordLowering::accumulateFields() {
350   for (RecordDecl::field_iterator Field = D->field_begin(),
351                                   FieldEnd = D->field_end();
352     Field != FieldEnd;)
353     if (Field->isBitField()) {
354       RecordDecl::field_iterator Start = Field;
355       // Iterate to gather the list of bitfields.
356       for (++Field; Field != FieldEnd && Field->isBitField(); ++Field);
357       accumulateBitFields(Start, Field);
358     } else {
359       Members.push_back(MemberInfo(
360           bitsToCharUnits(getFieldBitOffset(*Field)), MemberInfo::Field,
361           getStorageType(*Field), *Field));
362       ++Field;
363     }
364 }
365 
366 void
accumulateBitFields(RecordDecl::field_iterator Field,RecordDecl::field_iterator FieldEnd)367 CGRecordLowering::accumulateBitFields(RecordDecl::field_iterator Field,
368                                       RecordDecl::field_iterator FieldEnd) {
369   // Run stores the first element of the current run of bitfields.  FieldEnd is
370   // used as a special value to note that we don't have a current run.  A
371   // bitfield run is a contiguous collection of bitfields that can be stored in
372   // the same storage block.  Zero-sized bitfields and bitfields that would
373   // cross an alignment boundary break a run and start a new one.
374   RecordDecl::field_iterator Run = FieldEnd;
375   // Tail is the offset of the first bit off the end of the current run.  It's
376   // used to determine if the ASTRecordLayout is treating these two bitfields as
377   // contiguous.  StartBitOffset is offset of the beginning of the Run.
378   uint64_t StartBitOffset, Tail = 0;
379   if (isDiscreteBitFieldABI()) {
380     for (; Field != FieldEnd; ++Field) {
381       uint64_t BitOffset = getFieldBitOffset(*Field);
382       // Zero-width bitfields end runs.
383       if (Field->getBitWidthValue(Context) == 0) {
384         Run = FieldEnd;
385         continue;
386       }
387       llvm::Type *Type = Types.ConvertTypeForMem(Field->getType());
388       // If we don't have a run yet, or don't live within the previous run's
389       // allocated storage then we allocate some storage and start a new run.
390       if (Run == FieldEnd || BitOffset >= Tail) {
391         Run = Field;
392         StartBitOffset = BitOffset;
393         Tail = StartBitOffset + DataLayout.getTypeAllocSizeInBits(Type);
394         // Add the storage member to the record.  This must be added to the
395         // record before the bitfield members so that it gets laid out before
396         // the bitfields it contains get laid out.
397         Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type));
398       }
399       // Bitfields get the offset of their storage but come afterward and remain
400       // there after a stable sort.
401       Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset),
402                                    MemberInfo::Field, nullptr, *Field));
403     }
404     return;
405   }
406   for (;;) {
407     // Check to see if we need to start a new run.
408     if (Run == FieldEnd) {
409       // If we're out of fields, return.
410       if (Field == FieldEnd)
411         break;
412       // Any non-zero-length bitfield can start a new run.
413       if (Field->getBitWidthValue(Context) != 0) {
414         Run = Field;
415         StartBitOffset = getFieldBitOffset(*Field);
416         Tail = StartBitOffset + Field->getBitWidthValue(Context);
417       }
418       ++Field;
419       continue;
420     }
421     // Add bitfields to the run as long as they qualify.
422     if (Field != FieldEnd && Field->getBitWidthValue(Context) != 0 &&
423         Tail == getFieldBitOffset(*Field)) {
424       Tail += Field->getBitWidthValue(Context);
425       ++Field;
426       continue;
427     }
428     // We've hit a break-point in the run and need to emit a storage field.
429     llvm::Type *Type = getIntNType(Tail - StartBitOffset);
430     // Add the storage member to the record and set the bitfield info for all of
431     // the bitfields in the run.  Bitfields get the offset of their storage but
432     // come afterward and remain there after a stable sort.
433     Members.push_back(StorageInfo(bitsToCharUnits(StartBitOffset), Type));
434     for (; Run != Field; ++Run)
435       Members.push_back(MemberInfo(bitsToCharUnits(StartBitOffset),
436                                    MemberInfo::Field, nullptr, *Run));
437     Run = FieldEnd;
438   }
439 }
440 
accumulateBases()441 void CGRecordLowering::accumulateBases() {
442   // If we've got a primary virtual base, we need to add it with the bases.
443   if (Layout.isPrimaryBaseVirtual()) {
444     const CXXRecordDecl *BaseDecl = Layout.getPrimaryBase();
445     Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::Base,
446                                  getStorageType(BaseDecl), BaseDecl));
447   }
448   // Accumulate the non-virtual bases.
449   for (const auto &Base : RD->bases()) {
450     if (Base.isVirtual())
451       continue;
452 
453     // Bases can be zero-sized even if not technically empty if they
454     // contain only a trailing array member.
455     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
456     if (!BaseDecl->isEmpty() &&
457         !Context.getASTRecordLayout(BaseDecl).getNonVirtualSize().isZero())
458       Members.push_back(MemberInfo(Layout.getBaseClassOffset(BaseDecl),
459           MemberInfo::Base, getStorageType(BaseDecl), BaseDecl));
460   }
461 }
462 
accumulateVPtrs()463 void CGRecordLowering::accumulateVPtrs() {
464   if (Layout.hasOwnVFPtr())
465     Members.push_back(MemberInfo(CharUnits::Zero(), MemberInfo::VFPtr,
466         llvm::FunctionType::get(getIntNType(32), /*isVarArg=*/true)->
467             getPointerTo()->getPointerTo()));
468   if (Layout.hasOwnVBPtr())
469     Members.push_back(MemberInfo(Layout.getVBPtrOffset(), MemberInfo::VBPtr,
470         llvm::Type::getInt32PtrTy(Types.getLLVMContext())));
471 }
472 
accumulateVBases()473 void CGRecordLowering::accumulateVBases() {
474   CharUnits ScissorOffset = Layout.getNonVirtualSize();
475   // In the itanium ABI, it's possible to place a vbase at a dsize that is
476   // smaller than the nvsize.  Here we check to see if such a base is placed
477   // before the nvsize and set the scissor offset to that, instead of the
478   // nvsize.
479   if (isOverlappingVBaseABI())
480     for (const auto &Base : RD->vbases()) {
481       const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
482       if (BaseDecl->isEmpty())
483         continue;
484       // If the vbase is a primary virtual base of some base, then it doesn't
485       // get its own storage location but instead lives inside of that base.
486       if (Context.isNearlyEmpty(BaseDecl) && !hasOwnStorage(RD, BaseDecl))
487         continue;
488       ScissorOffset = std::min(ScissorOffset,
489                                Layout.getVBaseClassOffset(BaseDecl));
490     }
491   Members.push_back(MemberInfo(ScissorOffset, MemberInfo::Scissor, nullptr,
492                                RD));
493   for (const auto &Base : RD->vbases()) {
494     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
495     if (BaseDecl->isEmpty())
496       continue;
497     CharUnits Offset = Layout.getVBaseClassOffset(BaseDecl);
498     // If the vbase is a primary virtual base of some base, then it doesn't
499     // get its own storage location but instead lives inside of that base.
500     if (isOverlappingVBaseABI() &&
501         Context.isNearlyEmpty(BaseDecl) &&
502         !hasOwnStorage(RD, BaseDecl)) {
503       Members.push_back(MemberInfo(Offset, MemberInfo::VBase, nullptr,
504                                    BaseDecl));
505       continue;
506     }
507     // If we've got a vtordisp, add it as a storage type.
508     if (Layout.getVBaseOffsetsMap().find(BaseDecl)->second.hasVtorDisp())
509       Members.push_back(StorageInfo(Offset - CharUnits::fromQuantity(4),
510                                     getIntNType(32)));
511     Members.push_back(MemberInfo(Offset, MemberInfo::VBase,
512                                  getStorageType(BaseDecl), BaseDecl));
513   }
514 }
515 
hasOwnStorage(const CXXRecordDecl * Decl,const CXXRecordDecl * Query)516 bool CGRecordLowering::hasOwnStorage(const CXXRecordDecl *Decl,
517                                      const CXXRecordDecl *Query) {
518   const ASTRecordLayout &DeclLayout = Context.getASTRecordLayout(Decl);
519   if (DeclLayout.isPrimaryBaseVirtual() && DeclLayout.getPrimaryBase() == Query)
520     return false;
521   for (const auto &Base : Decl->bases())
522     if (!hasOwnStorage(Base.getType()->getAsCXXRecordDecl(), Query))
523       return false;
524   return true;
525 }
526 
calculateZeroInit()527 void CGRecordLowering::calculateZeroInit() {
528   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
529                                                MemberEnd = Members.end();
530        IsZeroInitializableAsBase && Member != MemberEnd; ++Member) {
531     if (Member->Kind == MemberInfo::Field) {
532       if (!Member->FD || isZeroInitializable(Member->FD))
533         continue;
534       IsZeroInitializable = IsZeroInitializableAsBase = false;
535     } else if (Member->Kind == MemberInfo::Base ||
536                Member->Kind == MemberInfo::VBase) {
537       if (isZeroInitializable(Member->RD))
538         continue;
539       IsZeroInitializable = false;
540       if (Member->Kind == MemberInfo::Base)
541         IsZeroInitializableAsBase = false;
542     }
543   }
544 }
545 
clipTailPadding()546 void CGRecordLowering::clipTailPadding() {
547   std::vector<MemberInfo>::iterator Prior = Members.begin();
548   CharUnits Tail = getSize(Prior->Data);
549   for (std::vector<MemberInfo>::iterator Member = Prior + 1,
550                                          MemberEnd = Members.end();
551        Member != MemberEnd; ++Member) {
552     // Only members with data and the scissor can cut into tail padding.
553     if (!Member->Data && Member->Kind != MemberInfo::Scissor)
554       continue;
555     if (Member->Offset < Tail) {
556       assert(Prior->Kind == MemberInfo::Field && !Prior->FD &&
557              "Only storage fields have tail padding!");
558       Prior->Data = getByteArrayType(bitsToCharUnits(llvm::alignTo(
559           cast<llvm::IntegerType>(Prior->Data)->getIntegerBitWidth(), 8)));
560     }
561     if (Member->Data)
562       Prior = Member;
563     Tail = Prior->Offset + getSize(Prior->Data);
564   }
565 }
566 
determinePacked(bool NVBaseType)567 void CGRecordLowering::determinePacked(bool NVBaseType) {
568   if (Packed)
569     return;
570   CharUnits Alignment = CharUnits::One();
571   CharUnits NVAlignment = CharUnits::One();
572   CharUnits NVSize =
573       !NVBaseType && RD ? Layout.getNonVirtualSize() : CharUnits::Zero();
574   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
575                                                MemberEnd = Members.end();
576        Member != MemberEnd; ++Member) {
577     if (!Member->Data)
578       continue;
579     // If any member falls at an offset that it not a multiple of its alignment,
580     // then the entire record must be packed.
581     if (Member->Offset % getAlignment(Member->Data))
582       Packed = true;
583     if (Member->Offset < NVSize)
584       NVAlignment = std::max(NVAlignment, getAlignment(Member->Data));
585     Alignment = std::max(Alignment, getAlignment(Member->Data));
586   }
587   // If the size of the record (the capstone's offset) is not a multiple of the
588   // record's alignment, it must be packed.
589   if (Members.back().Offset % Alignment)
590     Packed = true;
591   // If the non-virtual sub-object is not a multiple of the non-virtual
592   // sub-object's alignment, it must be packed.  We cannot have a packed
593   // non-virtual sub-object and an unpacked complete object or vise versa.
594   if (NVSize % NVAlignment)
595     Packed = true;
596   // Update the alignment of the sentinal.
597   if (!Packed)
598     Members.back().Data = getIntNType(Context.toBits(Alignment));
599 }
600 
insertPadding()601 void CGRecordLowering::insertPadding() {
602   std::vector<std::pair<CharUnits, CharUnits> > Padding;
603   CharUnits Size = CharUnits::Zero();
604   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
605                                                MemberEnd = Members.end();
606        Member != MemberEnd; ++Member) {
607     if (!Member->Data)
608       continue;
609     CharUnits Offset = Member->Offset;
610     assert(Offset >= Size);
611     // Insert padding if we need to.
612     if (Offset !=
613         Size.alignTo(Packed ? CharUnits::One() : getAlignment(Member->Data)))
614       Padding.push_back(std::make_pair(Size, Offset - Size));
615     Size = Offset + getSize(Member->Data);
616   }
617   if (Padding.empty())
618     return;
619   // Add the padding to the Members list and sort it.
620   for (std::vector<std::pair<CharUnits, CharUnits> >::const_iterator
621         Pad = Padding.begin(), PadEnd = Padding.end();
622         Pad != PadEnd; ++Pad)
623     Members.push_back(StorageInfo(Pad->first, getByteArrayType(Pad->second)));
624   std::stable_sort(Members.begin(), Members.end());
625 }
626 
fillOutputFields()627 void CGRecordLowering::fillOutputFields() {
628   for (std::vector<MemberInfo>::const_iterator Member = Members.begin(),
629                                                MemberEnd = Members.end();
630        Member != MemberEnd; ++Member) {
631     if (Member->Data)
632       FieldTypes.push_back(Member->Data);
633     if (Member->Kind == MemberInfo::Field) {
634       if (Member->FD)
635         Fields[Member->FD->getCanonicalDecl()] = FieldTypes.size() - 1;
636       // A field without storage must be a bitfield.
637       if (!Member->Data)
638         setBitFieldInfo(Member->FD, Member->Offset, FieldTypes.back());
639     } else if (Member->Kind == MemberInfo::Base)
640       NonVirtualBases[Member->RD] = FieldTypes.size() - 1;
641     else if (Member->Kind == MemberInfo::VBase)
642       VirtualBases[Member->RD] = FieldTypes.size() - 1;
643   }
644 }
645 
MakeInfo(CodeGenTypes & Types,const FieldDecl * FD,uint64_t Offset,uint64_t Size,uint64_t StorageSize,CharUnits StorageOffset)646 CGBitFieldInfo CGBitFieldInfo::MakeInfo(CodeGenTypes &Types,
647                                         const FieldDecl *FD,
648                                         uint64_t Offset, uint64_t Size,
649                                         uint64_t StorageSize,
650                                         CharUnits StorageOffset) {
651   // This function is vestigial from CGRecordLayoutBuilder days but is still
652   // used in GCObjCRuntime.cpp.  That usage has a "fixme" attached to it that
653   // when addressed will allow for the removal of this function.
654   llvm::Type *Ty = Types.ConvertTypeForMem(FD->getType());
655   CharUnits TypeSizeInBytes =
656     CharUnits::fromQuantity(Types.getDataLayout().getTypeAllocSize(Ty));
657   uint64_t TypeSizeInBits = Types.getContext().toBits(TypeSizeInBytes);
658 
659   bool IsSigned = FD->getType()->isSignedIntegerOrEnumerationType();
660 
661   if (Size > TypeSizeInBits) {
662     // We have a wide bit-field. The extra bits are only used for padding, so
663     // if we have a bitfield of type T, with size N:
664     //
665     // T t : N;
666     //
667     // We can just assume that it's:
668     //
669     // T t : sizeof(T);
670     //
671     Size = TypeSizeInBits;
672   }
673 
674   // Reverse the bit offsets for big endian machines. Because we represent
675   // a bitfield as a single large integer load, we can imagine the bits
676   // counting from the most-significant-bit instead of the
677   // least-significant-bit.
678   if (Types.getDataLayout().isBigEndian()) {
679     Offset = StorageSize - (Offset + Size);
680   }
681 
682   return CGBitFieldInfo(Offset, Size, IsSigned, StorageSize, StorageOffset);
683 }
684 
ComputeRecordLayout(const RecordDecl * D,llvm::StructType * Ty)685 CGRecordLayout *CodeGenTypes::ComputeRecordLayout(const RecordDecl *D,
686                                                   llvm::StructType *Ty) {
687   CGRecordLowering Builder(*this, D, /*Packed=*/false);
688 
689   Builder.lower(/*NonVirtualBaseType=*/false);
690 
691   // If we're in C++, compute the base subobject type.
692   llvm::StructType *BaseTy = nullptr;
693   if (isa<CXXRecordDecl>(D) && !D->isUnion() && !D->hasAttr<FinalAttr>()) {
694     BaseTy = Ty;
695     if (Builder.Layout.getNonVirtualSize() != Builder.Layout.getSize()) {
696       CGRecordLowering BaseBuilder(*this, D, /*Packed=*/Builder.Packed);
697       BaseBuilder.lower(/*NonVirtualBaseType=*/true);
698       BaseTy = llvm::StructType::create(
699           getLLVMContext(), BaseBuilder.FieldTypes, "", BaseBuilder.Packed);
700       addRecordTypeName(D, BaseTy, ".base");
701       // BaseTy and Ty must agree on their packedness for getLLVMFieldNo to work
702       // on both of them with the same index.
703       assert(Builder.Packed == BaseBuilder.Packed &&
704              "Non-virtual and complete types must agree on packedness");
705     }
706   }
707 
708   // Fill in the struct *after* computing the base type.  Filling in the body
709   // signifies that the type is no longer opaque and record layout is complete,
710   // but we may need to recursively layout D while laying D out as a base type.
711   Ty->setBody(Builder.FieldTypes, Builder.Packed);
712 
713   CGRecordLayout *RL =
714     new CGRecordLayout(Ty, BaseTy, Builder.IsZeroInitializable,
715                         Builder.IsZeroInitializableAsBase);
716 
717   RL->NonVirtualBases.swap(Builder.NonVirtualBases);
718   RL->CompleteObjectVirtualBases.swap(Builder.VirtualBases);
719 
720   // Add all the field numbers.
721   RL->FieldInfo.swap(Builder.Fields);
722 
723   // Add bitfield info.
724   RL->BitFields.swap(Builder.BitFields);
725 
726   // Dump the layout, if requested.
727   if (getContext().getLangOpts().DumpRecordLayouts) {
728     llvm::outs() << "\n*** Dumping IRgen Record Layout\n";
729     llvm::outs() << "Record: ";
730     D->dump(llvm::outs());
731     llvm::outs() << "\nLayout: ";
732     RL->print(llvm::outs());
733   }
734 
735 #ifndef NDEBUG
736   // Verify that the computed LLVM struct size matches the AST layout size.
737   const ASTRecordLayout &Layout = getContext().getASTRecordLayout(D);
738 
739   uint64_t TypeSizeInBits = getContext().toBits(Layout.getSize());
740   assert(TypeSizeInBits == getDataLayout().getTypeAllocSizeInBits(Ty) &&
741          "Type size mismatch!");
742 
743   if (BaseTy) {
744     CharUnits NonVirtualSize  = Layout.getNonVirtualSize();
745 
746     uint64_t AlignedNonVirtualTypeSizeInBits =
747       getContext().toBits(NonVirtualSize);
748 
749     assert(AlignedNonVirtualTypeSizeInBits ==
750            getDataLayout().getTypeAllocSizeInBits(BaseTy) &&
751            "Type size mismatch!");
752   }
753 
754   // Verify that the LLVM and AST field offsets agree.
755   llvm::StructType *ST =
756     dyn_cast<llvm::StructType>(RL->getLLVMType());
757   const llvm::StructLayout *SL = getDataLayout().getStructLayout(ST);
758 
759   const ASTRecordLayout &AST_RL = getContext().getASTRecordLayout(D);
760   RecordDecl::field_iterator it = D->field_begin();
761   for (unsigned i = 0, e = AST_RL.getFieldCount(); i != e; ++i, ++it) {
762     const FieldDecl *FD = *it;
763 
764     // For non-bit-fields, just check that the LLVM struct offset matches the
765     // AST offset.
766     if (!FD->isBitField()) {
767       unsigned FieldNo = RL->getLLVMFieldNo(FD);
768       assert(AST_RL.getFieldOffset(i) == SL->getElementOffsetInBits(FieldNo) &&
769              "Invalid field offset!");
770       continue;
771     }
772 
773     // Ignore unnamed bit-fields.
774     if (!FD->getDeclName())
775       continue;
776 
777     // Don't inspect zero-length bitfields.
778     if (FD->getBitWidthValue(getContext()) == 0)
779       continue;
780 
781     const CGBitFieldInfo &Info = RL->getBitFieldInfo(FD);
782     llvm::Type *ElementTy = ST->getTypeAtIndex(RL->getLLVMFieldNo(FD));
783 
784     // Unions have overlapping elements dictating their layout, but for
785     // non-unions we can verify that this section of the layout is the exact
786     // expected size.
787     if (D->isUnion()) {
788       // For unions we verify that the start is zero and the size
789       // is in-bounds. However, on BE systems, the offset may be non-zero, but
790       // the size + offset should match the storage size in that case as it
791       // "starts" at the back.
792       if (getDataLayout().isBigEndian())
793         assert(static_cast<unsigned>(Info.Offset + Info.Size) ==
794                Info.StorageSize &&
795                "Big endian union bitfield does not end at the back");
796       else
797         assert(Info.Offset == 0 &&
798                "Little endian union bitfield with a non-zero offset");
799       assert(Info.StorageSize <= SL->getSizeInBits() &&
800              "Union not large enough for bitfield storage");
801     } else {
802       assert(Info.StorageSize ==
803              getDataLayout().getTypeAllocSizeInBits(ElementTy) &&
804              "Storage size does not match the element type size");
805     }
806     assert(Info.Size > 0 && "Empty bitfield!");
807     assert(static_cast<unsigned>(Info.Offset) + Info.Size <= Info.StorageSize &&
808            "Bitfield outside of its allocated storage");
809   }
810 #endif
811 
812   return RL;
813 }
814 
print(raw_ostream & OS) const815 void CGRecordLayout::print(raw_ostream &OS) const {
816   OS << "<CGRecordLayout\n";
817   OS << "  LLVMType:" << *CompleteObjectType << "\n";
818   if (BaseSubobjectType)
819     OS << "  NonVirtualBaseLLVMType:" << *BaseSubobjectType << "\n";
820   OS << "  IsZeroInitializable:" << IsZeroInitializable << "\n";
821   OS << "  BitFields:[\n";
822 
823   // Print bit-field infos in declaration order.
824   std::vector<std::pair<unsigned, const CGBitFieldInfo*> > BFIs;
825   for (llvm::DenseMap<const FieldDecl*, CGBitFieldInfo>::const_iterator
826          it = BitFields.begin(), ie = BitFields.end();
827        it != ie; ++it) {
828     const RecordDecl *RD = it->first->getParent();
829     unsigned Index = 0;
830     for (RecordDecl::field_iterator
831            it2 = RD->field_begin(); *it2 != it->first; ++it2)
832       ++Index;
833     BFIs.push_back(std::make_pair(Index, &it->second));
834   }
835   llvm::array_pod_sort(BFIs.begin(), BFIs.end());
836   for (unsigned i = 0, e = BFIs.size(); i != e; ++i) {
837     OS.indent(4);
838     BFIs[i].second->print(OS);
839     OS << "\n";
840   }
841 
842   OS << "]>\n";
843 }
844 
dump() const845 LLVM_DUMP_METHOD void CGRecordLayout::dump() const {
846   print(llvm::errs());
847 }
848 
print(raw_ostream & OS) const849 void CGBitFieldInfo::print(raw_ostream &OS) const {
850   OS << "<CGBitFieldInfo"
851      << " Offset:" << Offset
852      << " Size:" << Size
853      << " IsSigned:" << IsSigned
854      << " StorageSize:" << StorageSize
855      << " StorageOffset:" << StorageOffset.getQuantity() << ">";
856 }
857 
dump() const858 LLVM_DUMP_METHOD void CGBitFieldInfo::dump() const {
859   print(llvm::errs());
860 }
861