Move vtordisp mode from Attr class to LangOptions.h, NFC
[lldb.git] / clang / lib / AST / RecordLayoutBuilder.cpp
1 //=== RecordLayoutBuilder.cpp - Helper class for building record layouts ---==//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "clang/AST/RecordLayout.h"
10 #include "clang/AST/ASTContext.h"
11 #include "clang/AST/ASTDiagnostic.h"
12 #include "clang/AST/Attr.h"
13 #include "clang/AST/CXXInheritance.h"
14 #include "clang/AST/Decl.h"
15 #include "clang/AST/DeclCXX.h"
16 #include "clang/AST/DeclObjC.h"
17 #include "clang/AST/Expr.h"
18 #include "clang/Basic/TargetInfo.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/Support/Format.h"
21 #include "llvm/Support/MathExtras.h"
22
23 using namespace clang;
24
25 namespace {
26
27 /// BaseSubobjectInfo - Represents a single base subobject in a complete class.
28 /// For a class hierarchy like
29 ///
30 /// class A { };
31 /// class B : A { };
32 /// class C : A, B { };
33 ///
34 /// The BaseSubobjectInfo graph for C will have three BaseSubobjectInfo
35 /// instances, one for B and two for A.
36 ///
37 /// If a base is virtual, it will only have one BaseSubobjectInfo allocated.
38 struct BaseSubobjectInfo {
39   /// Class - The class for this base info.
40   const CXXRecordDecl *Class;
41
42   /// IsVirtual - Whether the BaseInfo represents a virtual base or not.
43   bool IsVirtual;
44
45   /// Bases - Information about the base subobjects.
46   SmallVector<BaseSubobjectInfo*, 4> Bases;
47
48   /// PrimaryVirtualBaseInfo - Holds the base info for the primary virtual base
49   /// of this base info (if one exists).
50   BaseSubobjectInfo *PrimaryVirtualBaseInfo;
51
52   // FIXME: Document.
53   const BaseSubobjectInfo *Derived;
54 };
55
56 /// Externally provided layout. Typically used when the AST source, such
57 /// as DWARF, lacks all the information that was available at compile time, such
58 /// as alignment attributes on fields and pragmas in effect.
59 struct ExternalLayout {
60   ExternalLayout() : Size(0), Align(0) {}
61
62   /// Overall record size in bits.
63   uint64_t Size;
64
65   /// Overall record alignment in bits.
66   uint64_t Align;
67
68   /// Record field offsets in bits.
69   llvm::DenseMap<const FieldDecl *, uint64_t> FieldOffsets;
70
71   /// Direct, non-virtual base offsets.
72   llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsets;
73
74   /// Virtual base offsets.
75   llvm::DenseMap<const CXXRecordDecl *, CharUnits> VirtualBaseOffsets;
76
77   /// Get the offset of the given field. The external source must provide
78   /// entries for all fields in the record.
79   uint64_t getExternalFieldOffset(const FieldDecl *FD) {
80     assert(FieldOffsets.count(FD) &&
81            "Field does not have an external offset");
82     return FieldOffsets[FD];
83   }
84
85   bool getExternalNVBaseOffset(const CXXRecordDecl *RD, CharUnits &BaseOffset) {
86     auto Known = BaseOffsets.find(RD);
87     if (Known == BaseOffsets.end())
88       return false;
89     BaseOffset = Known->second;
90     return true;
91   }
92
93   bool getExternalVBaseOffset(const CXXRecordDecl *RD, CharUnits &BaseOffset) {
94     auto Known = VirtualBaseOffsets.find(RD);
95     if (Known == VirtualBaseOffsets.end())
96       return false;
97     BaseOffset = Known->second;
98     return true;
99   }
100 };
101
102 /// EmptySubobjectMap - Keeps track of which empty subobjects exist at different
103 /// offsets while laying out a C++ class.
104 class EmptySubobjectMap {
105   const ASTContext &Context;
106   uint64_t CharWidth;
107
108   /// Class - The class whose empty entries we're keeping track of.
109   const CXXRecordDecl *Class;
110
111   /// EmptyClassOffsets - A map from offsets to empty record decls.
112   typedef llvm::TinyPtrVector<const CXXRecordDecl *> ClassVectorTy;
113   typedef llvm::DenseMap<CharUnits, ClassVectorTy> EmptyClassOffsetsMapTy;
114   EmptyClassOffsetsMapTy EmptyClassOffsets;
115
116   /// MaxEmptyClassOffset - The highest offset known to contain an empty
117   /// base subobject.
118   CharUnits MaxEmptyClassOffset;
119
120   /// ComputeEmptySubobjectSizes - Compute the size of the largest base or
121   /// member subobject that is empty.
122   void ComputeEmptySubobjectSizes();
123
124   void AddSubobjectAtOffset(const CXXRecordDecl *RD, CharUnits Offset);
125
126   void UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
127                                  CharUnits Offset, bool PlacingEmptyBase);
128
129   void UpdateEmptyFieldSubobjects(const CXXRecordDecl *RD,
130                                   const CXXRecordDecl *Class, CharUnits Offset,
131                                   bool PlacingOverlappingField);
132   void UpdateEmptyFieldSubobjects(const FieldDecl *FD, CharUnits Offset,
133                                   bool PlacingOverlappingField);
134
135   /// AnyEmptySubobjectsBeyondOffset - Returns whether there are any empty
136   /// subobjects beyond the given offset.
137   bool AnyEmptySubobjectsBeyondOffset(CharUnits Offset) const {
138     return Offset <= MaxEmptyClassOffset;
139   }
140
141   CharUnits
142   getFieldOffset(const ASTRecordLayout &Layout, unsigned FieldNo) const {
143     uint64_t FieldOffset = Layout.getFieldOffset(FieldNo);
144     assert(FieldOffset % CharWidth == 0 &&
145            "Field offset not at char boundary!");
146
147     return Context.toCharUnitsFromBits(FieldOffset);
148   }
149
150 protected:
151   bool CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
152                                  CharUnits Offset) const;
153
154   bool CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
155                                      CharUnits Offset);
156
157   bool CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
158                                       const CXXRecordDecl *Class,
159                                       CharUnits Offset) const;
160   bool CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
161                                       CharUnits Offset) const;
162
163 public:
164   /// This holds the size of the largest empty subobject (either a base
165   /// or a member). Will be zero if the record being built doesn't contain
166   /// any empty classes.
167   CharUnits SizeOfLargestEmptySubobject;
168
169   EmptySubobjectMap(const ASTContext &Context, const CXXRecordDecl *Class)
170   : Context(Context), CharWidth(Context.getCharWidth()), Class(Class) {
171       ComputeEmptySubobjectSizes();
172   }
173
174   /// CanPlaceBaseAtOffset - Return whether the given base class can be placed
175   /// at the given offset.
176   /// Returns false if placing the record will result in two components
177   /// (direct or indirect) of the same type having the same offset.
178   bool CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
179                             CharUnits Offset);
180
181   /// CanPlaceFieldAtOffset - Return whether a field can be placed at the given
182   /// offset.
183   bool CanPlaceFieldAtOffset(const FieldDecl *FD, CharUnits Offset);
184 };
185
186 void EmptySubobjectMap::ComputeEmptySubobjectSizes() {
187   // Check the bases.
188   for (const CXXBaseSpecifier &Base : Class->bases()) {
189     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
190
191     CharUnits EmptySize;
192     const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
193     if (BaseDecl->isEmpty()) {
194       // If the class decl is empty, get its size.
195       EmptySize = Layout.getSize();
196     } else {
197       // Otherwise, we get the largest empty subobject for the decl.
198       EmptySize = Layout.getSizeOfLargestEmptySubobject();
199     }
200
201     if (EmptySize > SizeOfLargestEmptySubobject)
202       SizeOfLargestEmptySubobject = EmptySize;
203   }
204
205   // Check the fields.
206   for (const FieldDecl *FD : Class->fields()) {
207     const RecordType *RT =
208         Context.getBaseElementType(FD->getType())->getAs<RecordType>();
209
210     // We only care about record types.
211     if (!RT)
212       continue;
213
214     CharUnits EmptySize;
215     const CXXRecordDecl *MemberDecl = RT->getAsCXXRecordDecl();
216     const ASTRecordLayout &Layout = Context.getASTRecordLayout(MemberDecl);
217     if (MemberDecl->isEmpty()) {
218       // If the class decl is empty, get its size.
219       EmptySize = Layout.getSize();
220     } else {
221       // Otherwise, we get the largest empty subobject for the decl.
222       EmptySize = Layout.getSizeOfLargestEmptySubobject();
223     }
224
225     if (EmptySize > SizeOfLargestEmptySubobject)
226       SizeOfLargestEmptySubobject = EmptySize;
227   }
228 }
229
230 bool
231 EmptySubobjectMap::CanPlaceSubobjectAtOffset(const CXXRecordDecl *RD,
232                                              CharUnits Offset) const {
233   // We only need to check empty bases.
234   if (!RD->isEmpty())
235     return true;
236
237   EmptyClassOffsetsMapTy::const_iterator I = EmptyClassOffsets.find(Offset);
238   if (I == EmptyClassOffsets.end())
239     return true;
240
241   const ClassVectorTy &Classes = I->second;
242   if (llvm::find(Classes, RD) == Classes.end())
243     return true;
244
245   // There is already an empty class of the same type at this offset.
246   return false;
247 }
248
249 void EmptySubobjectMap::AddSubobjectAtOffset(const CXXRecordDecl *RD,
250                                              CharUnits Offset) {
251   // We only care about empty bases.
252   if (!RD->isEmpty())
253     return;
254
255   // If we have empty structures inside a union, we can assign both
256   // the same offset. Just avoid pushing them twice in the list.
257   ClassVectorTy &Classes = EmptyClassOffsets[Offset];
258   if (llvm::is_contained(Classes, RD))
259     return;
260
261   Classes.push_back(RD);
262
263   // Update the empty class offset.
264   if (Offset > MaxEmptyClassOffset)
265     MaxEmptyClassOffset = Offset;
266 }
267
268 bool
269 EmptySubobjectMap::CanPlaceBaseSubobjectAtOffset(const BaseSubobjectInfo *Info,
270                                                  CharUnits Offset) {
271   // We don't have to keep looking past the maximum offset that's known to
272   // contain an empty class.
273   if (!AnyEmptySubobjectsBeyondOffset(Offset))
274     return true;
275
276   if (!CanPlaceSubobjectAtOffset(Info->Class, Offset))
277     return false;
278
279   // Traverse all non-virtual bases.
280   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
281   for (const BaseSubobjectInfo *Base : Info->Bases) {
282     if (Base->IsVirtual)
283       continue;
284
285     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
286
287     if (!CanPlaceBaseSubobjectAtOffset(Base, BaseOffset))
288       return false;
289   }
290
291   if (Info->PrimaryVirtualBaseInfo) {
292     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
293
294     if (Info == PrimaryVirtualBaseInfo->Derived) {
295       if (!CanPlaceBaseSubobjectAtOffset(PrimaryVirtualBaseInfo, Offset))
296         return false;
297     }
298   }
299
300   // Traverse all member variables.
301   unsigned FieldNo = 0;
302   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
303        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
304     if (I->isBitField())
305       continue;
306
307     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
308     if (!CanPlaceFieldSubobjectAtOffset(*I, FieldOffset))
309       return false;
310   }
311
312   return true;
313 }
314
315 void EmptySubobjectMap::UpdateEmptyBaseSubobjects(const BaseSubobjectInfo *Info,
316                                                   CharUnits Offset,
317                                                   bool PlacingEmptyBase) {
318   if (!PlacingEmptyBase && Offset >= SizeOfLargestEmptySubobject) {
319     // We know that the only empty subobjects that can conflict with empty
320     // subobject of non-empty bases, are empty bases that can be placed at
321     // offset zero. Because of this, we only need to keep track of empty base
322     // subobjects with offsets less than the size of the largest empty
323     // subobject for our class.
324     return;
325   }
326
327   AddSubobjectAtOffset(Info->Class, Offset);
328
329   // Traverse all non-virtual bases.
330   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
331   for (const BaseSubobjectInfo *Base : Info->Bases) {
332     if (Base->IsVirtual)
333       continue;
334
335     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
336     UpdateEmptyBaseSubobjects(Base, BaseOffset, PlacingEmptyBase);
337   }
338
339   if (Info->PrimaryVirtualBaseInfo) {
340     BaseSubobjectInfo *PrimaryVirtualBaseInfo = Info->PrimaryVirtualBaseInfo;
341
342     if (Info == PrimaryVirtualBaseInfo->Derived)
343       UpdateEmptyBaseSubobjects(PrimaryVirtualBaseInfo, Offset,
344                                 PlacingEmptyBase);
345   }
346
347   // Traverse all member variables.
348   unsigned FieldNo = 0;
349   for (CXXRecordDecl::field_iterator I = Info->Class->field_begin(),
350        E = Info->Class->field_end(); I != E; ++I, ++FieldNo) {
351     if (I->isBitField())
352       continue;
353
354     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
355     UpdateEmptyFieldSubobjects(*I, FieldOffset, PlacingEmptyBase);
356   }
357 }
358
359 bool EmptySubobjectMap::CanPlaceBaseAtOffset(const BaseSubobjectInfo *Info,
360                                              CharUnits Offset) {
361   // If we know this class doesn't have any empty subobjects we don't need to
362   // bother checking.
363   if (SizeOfLargestEmptySubobject.isZero())
364     return true;
365
366   if (!CanPlaceBaseSubobjectAtOffset(Info, Offset))
367     return false;
368
369   // We are able to place the base at this offset. Make sure to update the
370   // empty base subobject map.
371   UpdateEmptyBaseSubobjects(Info, Offset, Info->Class->isEmpty());
372   return true;
373 }
374
375 bool
376 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const CXXRecordDecl *RD,
377                                                   const CXXRecordDecl *Class,
378                                                   CharUnits Offset) const {
379   // We don't have to keep looking past the maximum offset that's known to
380   // contain an empty class.
381   if (!AnyEmptySubobjectsBeyondOffset(Offset))
382     return true;
383
384   if (!CanPlaceSubobjectAtOffset(RD, Offset))
385     return false;
386
387   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
388
389   // Traverse all non-virtual bases.
390   for (const CXXBaseSpecifier &Base : RD->bases()) {
391     if (Base.isVirtual())
392       continue;
393
394     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
395
396     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
397     if (!CanPlaceFieldSubobjectAtOffset(BaseDecl, Class, BaseOffset))
398       return false;
399   }
400
401   if (RD == Class) {
402     // This is the most derived class, traverse virtual bases as well.
403     for (const CXXBaseSpecifier &Base : RD->vbases()) {
404       const CXXRecordDecl *VBaseDecl = Base.getType()->getAsCXXRecordDecl();
405
406       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
407       if (!CanPlaceFieldSubobjectAtOffset(VBaseDecl, Class, VBaseOffset))
408         return false;
409     }
410   }
411
412   // Traverse all member variables.
413   unsigned FieldNo = 0;
414   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
415        I != E; ++I, ++FieldNo) {
416     if (I->isBitField())
417       continue;
418
419     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
420
421     if (!CanPlaceFieldSubobjectAtOffset(*I, FieldOffset))
422       return false;
423   }
424
425   return true;
426 }
427
428 bool
429 EmptySubobjectMap::CanPlaceFieldSubobjectAtOffset(const FieldDecl *FD,
430                                                   CharUnits Offset) const {
431   // We don't have to keep looking past the maximum offset that's known to
432   // contain an empty class.
433   if (!AnyEmptySubobjectsBeyondOffset(Offset))
434     return true;
435
436   QualType T = FD->getType();
437   if (const CXXRecordDecl *RD = T->getAsCXXRecordDecl())
438     return CanPlaceFieldSubobjectAtOffset(RD, RD, Offset);
439
440   // If we have an array type we need to look at every element.
441   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
442     QualType ElemTy = Context.getBaseElementType(AT);
443     const RecordType *RT = ElemTy->getAs<RecordType>();
444     if (!RT)
445       return true;
446
447     const CXXRecordDecl *RD = RT->getAsCXXRecordDecl();
448     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
449
450     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
451     CharUnits ElementOffset = Offset;
452     for (uint64_t I = 0; I != NumElements; ++I) {
453       // We don't have to keep looking past the maximum offset that's known to
454       // contain an empty class.
455       if (!AnyEmptySubobjectsBeyondOffset(ElementOffset))
456         return true;
457
458       if (!CanPlaceFieldSubobjectAtOffset(RD, RD, ElementOffset))
459         return false;
460
461       ElementOffset += Layout.getSize();
462     }
463   }
464
465   return true;
466 }
467
468 bool
469 EmptySubobjectMap::CanPlaceFieldAtOffset(const FieldDecl *FD,
470                                          CharUnits Offset) {
471   if (!CanPlaceFieldSubobjectAtOffset(FD, Offset))
472     return false;
473
474   // We are able to place the member variable at this offset.
475   // Make sure to update the empty field subobject map.
476   UpdateEmptyFieldSubobjects(FD, Offset, FD->hasAttr<NoUniqueAddressAttr>());
477   return true;
478 }
479
480 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(
481     const CXXRecordDecl *RD, const CXXRecordDecl *Class, CharUnits Offset,
482     bool PlacingOverlappingField) {
483   // We know that the only empty subobjects that can conflict with empty
484   // field subobjects are subobjects of empty bases and potentially-overlapping
485   // fields that can be placed at offset zero. Because of this, we only need to
486   // keep track of empty field subobjects with offsets less than the size of
487   // the largest empty subobject for our class.
488   //
489   // (Proof: we will only consider placing a subobject at offset zero or at
490   // >= the current dsize. The only cases where the earlier subobject can be
491   // placed beyond the end of dsize is if it's an empty base or a
492   // potentially-overlapping field.)
493   if (!PlacingOverlappingField && Offset >= SizeOfLargestEmptySubobject)
494     return;
495
496   AddSubobjectAtOffset(RD, Offset);
497
498   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
499
500   // Traverse all non-virtual bases.
501   for (const CXXBaseSpecifier &Base : RD->bases()) {
502     if (Base.isVirtual())
503       continue;
504
505     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
506
507     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(BaseDecl);
508     UpdateEmptyFieldSubobjects(BaseDecl, Class, BaseOffset,
509                                PlacingOverlappingField);
510   }
511
512   if (RD == Class) {
513     // This is the most derived class, traverse virtual bases as well.
514     for (const CXXBaseSpecifier &Base : RD->vbases()) {
515       const CXXRecordDecl *VBaseDecl = Base.getType()->getAsCXXRecordDecl();
516
517       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBaseDecl);
518       UpdateEmptyFieldSubobjects(VBaseDecl, Class, VBaseOffset,
519                                  PlacingOverlappingField);
520     }
521   }
522
523   // Traverse all member variables.
524   unsigned FieldNo = 0;
525   for (CXXRecordDecl::field_iterator I = RD->field_begin(), E = RD->field_end();
526        I != E; ++I, ++FieldNo) {
527     if (I->isBitField())
528       continue;
529
530     CharUnits FieldOffset = Offset + getFieldOffset(Layout, FieldNo);
531
532     UpdateEmptyFieldSubobjects(*I, FieldOffset, PlacingOverlappingField);
533   }
534 }
535
536 void EmptySubobjectMap::UpdateEmptyFieldSubobjects(
537     const FieldDecl *FD, CharUnits Offset, bool PlacingOverlappingField) {
538   QualType T = FD->getType();
539   if (const CXXRecordDecl *RD = T->getAsCXXRecordDecl()) {
540     UpdateEmptyFieldSubobjects(RD, RD, Offset, PlacingOverlappingField);
541     return;
542   }
543
544   // If we have an array type we need to update every element.
545   if (const ConstantArrayType *AT = Context.getAsConstantArrayType(T)) {
546     QualType ElemTy = Context.getBaseElementType(AT);
547     const RecordType *RT = ElemTy->getAs<RecordType>();
548     if (!RT)
549       return;
550
551     const CXXRecordDecl *RD = RT->getAsCXXRecordDecl();
552     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
553
554     uint64_t NumElements = Context.getConstantArrayElementCount(AT);
555     CharUnits ElementOffset = Offset;
556
557     for (uint64_t I = 0; I != NumElements; ++I) {
558       // We know that the only empty subobjects that can conflict with empty
559       // field subobjects are subobjects of empty bases that can be placed at
560       // offset zero. Because of this, we only need to keep track of empty field
561       // subobjects with offsets less than the size of the largest empty
562       // subobject for our class.
563       if (!PlacingOverlappingField &&
564           ElementOffset >= SizeOfLargestEmptySubobject)
565         return;
566
567       UpdateEmptyFieldSubobjects(RD, RD, ElementOffset,
568                                  PlacingOverlappingField);
569       ElementOffset += Layout.getSize();
570     }
571   }
572 }
573
574 typedef llvm::SmallPtrSet<const CXXRecordDecl*, 4> ClassSetTy;
575
576 class ItaniumRecordLayoutBuilder {
577 protected:
578   // FIXME: Remove this and make the appropriate fields public.
579   friend class clang::ASTContext;
580
581   const ASTContext &Context;
582
583   EmptySubobjectMap *EmptySubobjects;
584
585   /// Size - The current size of the record layout.
586   uint64_t Size;
587
588   /// Alignment - The current alignment of the record layout.
589   CharUnits Alignment;
590
591   /// The alignment if attribute packed is not used.
592   CharUnits UnpackedAlignment;
593
594   /// \brief The maximum of the alignments of top-level members.
595   CharUnits UnadjustedAlignment;
596
597   SmallVector<uint64_t, 16> FieldOffsets;
598
599   /// Whether the external AST source has provided a layout for this
600   /// record.
601   unsigned UseExternalLayout : 1;
602
603   /// Whether we need to infer alignment, even when we have an
604   /// externally-provided layout.
605   unsigned InferAlignment : 1;
606
607   /// Packed - Whether the record is packed or not.
608   unsigned Packed : 1;
609
610   unsigned IsUnion : 1;
611
612   unsigned IsMac68kAlign : 1;
613
614   unsigned IsMsStruct : 1;
615
616   /// UnfilledBitsInLastUnit - If the last field laid out was a bitfield,
617   /// this contains the number of bits in the last unit that can be used for
618   /// an adjacent bitfield if necessary.  The unit in question is usually
619   /// a byte, but larger units are used if IsMsStruct.
620   unsigned char UnfilledBitsInLastUnit;
621   /// LastBitfieldTypeSize - If IsMsStruct, represents the size of the type
622   /// of the previous field if it was a bitfield.
623   unsigned char LastBitfieldTypeSize;
624
625   /// MaxFieldAlignment - The maximum allowed field alignment. This is set by
626   /// #pragma pack.
627   CharUnits MaxFieldAlignment;
628
629   /// DataSize - The data size of the record being laid out.
630   uint64_t DataSize;
631
632   CharUnits NonVirtualSize;
633   CharUnits NonVirtualAlignment;
634
635   /// If we've laid out a field but not included its tail padding in Size yet,
636   /// this is the size up to the end of that field.
637   CharUnits PaddedFieldSize;
638
639   /// PrimaryBase - the primary base class (if one exists) of the class
640   /// we're laying out.
641   const CXXRecordDecl *PrimaryBase;
642
643   /// PrimaryBaseIsVirtual - Whether the primary base of the class we're laying
644   /// out is virtual.
645   bool PrimaryBaseIsVirtual;
646
647   /// HasOwnVFPtr - Whether the class provides its own vtable/vftbl
648   /// pointer, as opposed to inheriting one from a primary base class.
649   bool HasOwnVFPtr;
650
651   /// the flag of field offset changing due to packed attribute.
652   bool HasPackedField;
653
654   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsetsMapTy;
655
656   /// Bases - base classes and their offsets in the record.
657   BaseOffsetsMapTy Bases;
658
659   // VBases - virtual base classes and their offsets in the record.
660   ASTRecordLayout::VBaseOffsetsMapTy VBases;
661
662   /// IndirectPrimaryBases - Virtual base classes, direct or indirect, that are
663   /// primary base classes for some other direct or indirect base class.
664   CXXIndirectPrimaryBaseSet IndirectPrimaryBases;
665
666   /// FirstNearlyEmptyVBase - The first nearly empty virtual base class in
667   /// inheritance graph order. Used for determining the primary base class.
668   const CXXRecordDecl *FirstNearlyEmptyVBase;
669
670   /// VisitedVirtualBases - A set of all the visited virtual bases, used to
671   /// avoid visiting virtual bases more than once.
672   llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
673
674   /// Valid if UseExternalLayout is true.
675   ExternalLayout External;
676
677   ItaniumRecordLayoutBuilder(const ASTContext &Context,
678                              EmptySubobjectMap *EmptySubobjects)
679       : Context(Context), EmptySubobjects(EmptySubobjects), Size(0),
680         Alignment(CharUnits::One()), UnpackedAlignment(CharUnits::One()),
681         UnadjustedAlignment(CharUnits::One()),
682         UseExternalLayout(false), InferAlignment(false), Packed(false),
683         IsUnion(false), IsMac68kAlign(false), IsMsStruct(false),
684         UnfilledBitsInLastUnit(0), LastBitfieldTypeSize(0),
685         MaxFieldAlignment(CharUnits::Zero()), DataSize(0),
686         NonVirtualSize(CharUnits::Zero()),
687         NonVirtualAlignment(CharUnits::One()),
688         PaddedFieldSize(CharUnits::Zero()), PrimaryBase(nullptr),
689         PrimaryBaseIsVirtual(false), HasOwnVFPtr(false),
690         HasPackedField(false), FirstNearlyEmptyVBase(nullptr) {}
691
692   void Layout(const RecordDecl *D);
693   void Layout(const CXXRecordDecl *D);
694   void Layout(const ObjCInterfaceDecl *D);
695
696   void LayoutFields(const RecordDecl *D);
697   void LayoutField(const FieldDecl *D, bool InsertExtraPadding);
698   void LayoutWideBitField(uint64_t FieldSize, uint64_t TypeSize,
699                           bool FieldPacked, const FieldDecl *D);
700   void LayoutBitField(const FieldDecl *D);
701
702   TargetCXXABI getCXXABI() const {
703     return Context.getTargetInfo().getCXXABI();
704   }
705
706   /// BaseSubobjectInfoAllocator - Allocator for BaseSubobjectInfo objects.
707   llvm::SpecificBumpPtrAllocator<BaseSubobjectInfo> BaseSubobjectInfoAllocator;
708
709   typedef llvm::DenseMap<const CXXRecordDecl *, BaseSubobjectInfo *>
710     BaseSubobjectInfoMapTy;
711
712   /// VirtualBaseInfo - Map from all the (direct or indirect) virtual bases
713   /// of the class we're laying out to their base subobject info.
714   BaseSubobjectInfoMapTy VirtualBaseInfo;
715
716   /// NonVirtualBaseInfo - Map from all the direct non-virtual bases of the
717   /// class we're laying out to their base subobject info.
718   BaseSubobjectInfoMapTy NonVirtualBaseInfo;
719
720   /// ComputeBaseSubobjectInfo - Compute the base subobject information for the
721   /// bases of the given class.
722   void ComputeBaseSubobjectInfo(const CXXRecordDecl *RD);
723
724   /// ComputeBaseSubobjectInfo - Compute the base subobject information for a
725   /// single class and all of its base classes.
726   BaseSubobjectInfo *ComputeBaseSubobjectInfo(const CXXRecordDecl *RD,
727                                               bool IsVirtual,
728                                               BaseSubobjectInfo *Derived);
729
730   /// DeterminePrimaryBase - Determine the primary base of the given class.
731   void DeterminePrimaryBase(const CXXRecordDecl *RD);
732
733   void SelectPrimaryVBase(const CXXRecordDecl *RD);
734
735   void EnsureVTablePointerAlignment(CharUnits UnpackedBaseAlign);
736
737   /// LayoutNonVirtualBases - Determines the primary base class (if any) and
738   /// lays it out. Will then proceed to lay out all non-virtual base clasess.
739   void LayoutNonVirtualBases(const CXXRecordDecl *RD);
740
741   /// LayoutNonVirtualBase - Lays out a single non-virtual base.
742   void LayoutNonVirtualBase(const BaseSubobjectInfo *Base);
743
744   void AddPrimaryVirtualBaseOffsets(const BaseSubobjectInfo *Info,
745                                     CharUnits Offset);
746
747   /// LayoutVirtualBases - Lays out all the virtual bases.
748   void LayoutVirtualBases(const CXXRecordDecl *RD,
749                           const CXXRecordDecl *MostDerivedClass);
750
751   /// LayoutVirtualBase - Lays out a single virtual base.
752   void LayoutVirtualBase(const BaseSubobjectInfo *Base);
753
754   /// LayoutBase - Will lay out a base and return the offset where it was
755   /// placed, in chars.
756   CharUnits LayoutBase(const BaseSubobjectInfo *Base);
757
758   /// InitializeLayout - Initialize record layout for the given record decl.
759   void InitializeLayout(const Decl *D);
760
761   /// FinishLayout - Finalize record layout. Adjust record size based on the
762   /// alignment.
763   void FinishLayout(const NamedDecl *D);
764
765   void UpdateAlignment(CharUnits NewAlignment, CharUnits UnpackedNewAlignment);
766   void UpdateAlignment(CharUnits NewAlignment) {
767     UpdateAlignment(NewAlignment, NewAlignment);
768   }
769
770   /// Retrieve the externally-supplied field offset for the given
771   /// field.
772   ///
773   /// \param Field The field whose offset is being queried.
774   /// \param ComputedOffset The offset that we've computed for this field.
775   uint64_t updateExternalFieldOffset(const FieldDecl *Field,
776                                      uint64_t ComputedOffset);
777
778   void CheckFieldPadding(uint64_t Offset, uint64_t UnpaddedOffset,
779                           uint64_t UnpackedOffset, unsigned UnpackedAlign,
780                           bool isPacked, const FieldDecl *D);
781
782   DiagnosticBuilder Diag(SourceLocation Loc, unsigned DiagID);
783
784   CharUnits getSize() const {
785     assert(Size % Context.getCharWidth() == 0);
786     return Context.toCharUnitsFromBits(Size);
787   }
788   uint64_t getSizeInBits() const { return Size; }
789
790   void setSize(CharUnits NewSize) { Size = Context.toBits(NewSize); }
791   void setSize(uint64_t NewSize) { Size = NewSize; }
792
793   CharUnits getAligment() const { return Alignment; }
794
795   CharUnits getDataSize() const {
796     assert(DataSize % Context.getCharWidth() == 0);
797     return Context.toCharUnitsFromBits(DataSize);
798   }
799   uint64_t getDataSizeInBits() const { return DataSize; }
800
801   void setDataSize(CharUnits NewSize) { DataSize = Context.toBits(NewSize); }
802   void setDataSize(uint64_t NewSize) { DataSize = NewSize; }
803
804   ItaniumRecordLayoutBuilder(const ItaniumRecordLayoutBuilder &) = delete;
805   void operator=(const ItaniumRecordLayoutBuilder &) = delete;
806 };
807 } // end anonymous namespace
808
809 void ItaniumRecordLayoutBuilder::SelectPrimaryVBase(const CXXRecordDecl *RD) {
810   for (const auto &I : RD->bases()) {
811     assert(!I.getType()->isDependentType() &&
812            "Cannot layout class with dependent bases.");
813
814     const CXXRecordDecl *Base = I.getType()->getAsCXXRecordDecl();
815
816     // Check if this is a nearly empty virtual base.
817     if (I.isVirtual() && Context.isNearlyEmpty(Base)) {
818       // If it's not an indirect primary base, then we've found our primary
819       // base.
820       if (!IndirectPrimaryBases.count(Base)) {
821         PrimaryBase = Base;
822         PrimaryBaseIsVirtual = true;
823         return;
824       }
825
826       // Is this the first nearly empty virtual base?
827       if (!FirstNearlyEmptyVBase)
828         FirstNearlyEmptyVBase = Base;
829     }
830
831     SelectPrimaryVBase(Base);
832     if (PrimaryBase)
833       return;
834   }
835 }
836
837 /// DeterminePrimaryBase - Determine the primary base of the given class.
838 void ItaniumRecordLayoutBuilder::DeterminePrimaryBase(const CXXRecordDecl *RD) {
839   // If the class isn't dynamic, it won't have a primary base.
840   if (!RD->isDynamicClass())
841     return;
842
843   // Compute all the primary virtual bases for all of our direct and
844   // indirect bases, and record all their primary virtual base classes.
845   RD->getIndirectPrimaryBases(IndirectPrimaryBases);
846
847   // If the record has a dynamic base class, attempt to choose a primary base
848   // class. It is the first (in direct base class order) non-virtual dynamic
849   // base class, if one exists.
850   for (const auto &I : RD->bases()) {
851     // Ignore virtual bases.
852     if (I.isVirtual())
853       continue;
854
855     const CXXRecordDecl *Base = I.getType()->getAsCXXRecordDecl();
856
857     if (Base->isDynamicClass()) {
858       // We found it.
859       PrimaryBase = Base;
860       PrimaryBaseIsVirtual = false;
861       return;
862     }
863   }
864
865   // Under the Itanium ABI, if there is no non-virtual primary base class,
866   // try to compute the primary virtual base.  The primary virtual base is
867   // the first nearly empty virtual base that is not an indirect primary
868   // virtual base class, if one exists.
869   if (RD->getNumVBases() != 0) {
870     SelectPrimaryVBase(RD);
871     if (PrimaryBase)
872       return;
873   }
874
875   // Otherwise, it is the first indirect primary base class, if one exists.
876   if (FirstNearlyEmptyVBase) {
877     PrimaryBase = FirstNearlyEmptyVBase;
878     PrimaryBaseIsVirtual = true;
879     return;
880   }
881
882   assert(!PrimaryBase && "Should not get here with a primary base!");
883 }
884
885 BaseSubobjectInfo *ItaniumRecordLayoutBuilder::ComputeBaseSubobjectInfo(
886     const CXXRecordDecl *RD, bool IsVirtual, BaseSubobjectInfo *Derived) {
887   BaseSubobjectInfo *Info;
888
889   if (IsVirtual) {
890     // Check if we already have info about this virtual base.
891     BaseSubobjectInfo *&InfoSlot = VirtualBaseInfo[RD];
892     if (InfoSlot) {
893       assert(InfoSlot->Class == RD && "Wrong class for virtual base info!");
894       return InfoSlot;
895     }
896
897     // We don't, create it.
898     InfoSlot = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
899     Info = InfoSlot;
900   } else {
901     Info = new (BaseSubobjectInfoAllocator.Allocate()) BaseSubobjectInfo;
902   }
903
904   Info->Class = RD;
905   Info->IsVirtual = IsVirtual;
906   Info->Derived = nullptr;
907   Info->PrimaryVirtualBaseInfo = nullptr;
908
909   const CXXRecordDecl *PrimaryVirtualBase = nullptr;
910   BaseSubobjectInfo *PrimaryVirtualBaseInfo = nullptr;
911
912   // Check if this base has a primary virtual base.
913   if (RD->getNumVBases()) {
914     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
915     if (Layout.isPrimaryBaseVirtual()) {
916       // This base does have a primary virtual base.
917       PrimaryVirtualBase = Layout.getPrimaryBase();
918       assert(PrimaryVirtualBase && "Didn't have a primary virtual base!");
919
920       // Now check if we have base subobject info about this primary base.
921       PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
922
923       if (PrimaryVirtualBaseInfo) {
924         if (PrimaryVirtualBaseInfo->Derived) {
925           // We did have info about this primary base, and it turns out that it
926           // has already been claimed as a primary virtual base for another
927           // base.
928           PrimaryVirtualBase = nullptr;
929         } else {
930           // We can claim this base as our primary base.
931           Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
932           PrimaryVirtualBaseInfo->Derived = Info;
933         }
934       }
935     }
936   }
937
938   // Now go through all direct bases.
939   for (const auto &I : RD->bases()) {
940     bool IsVirtual = I.isVirtual();
941
942     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
943
944     Info->Bases.push_back(ComputeBaseSubobjectInfo(BaseDecl, IsVirtual, Info));
945   }
946
947   if (PrimaryVirtualBase && !PrimaryVirtualBaseInfo) {
948     // Traversing the bases must have created the base info for our primary
949     // virtual base.
950     PrimaryVirtualBaseInfo = VirtualBaseInfo.lookup(PrimaryVirtualBase);
951     assert(PrimaryVirtualBaseInfo &&
952            "Did not create a primary virtual base!");
953
954     // Claim the primary virtual base as our primary virtual base.
955     Info->PrimaryVirtualBaseInfo = PrimaryVirtualBaseInfo;
956     PrimaryVirtualBaseInfo->Derived = Info;
957   }
958
959   return Info;
960 }
961
962 void ItaniumRecordLayoutBuilder::ComputeBaseSubobjectInfo(
963     const CXXRecordDecl *RD) {
964   for (const auto &I : RD->bases()) {
965     bool IsVirtual = I.isVirtual();
966
967     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
968
969     // Compute the base subobject info for this base.
970     BaseSubobjectInfo *Info = ComputeBaseSubobjectInfo(BaseDecl, IsVirtual,
971                                                        nullptr);
972
973     if (IsVirtual) {
974       // ComputeBaseInfo has already added this base for us.
975       assert(VirtualBaseInfo.count(BaseDecl) &&
976              "Did not add virtual base!");
977     } else {
978       // Add the base info to the map of non-virtual bases.
979       assert(!NonVirtualBaseInfo.count(BaseDecl) &&
980              "Non-virtual base already exists!");
981       NonVirtualBaseInfo.insert(std::make_pair(BaseDecl, Info));
982     }
983   }
984 }
985
986 void ItaniumRecordLayoutBuilder::EnsureVTablePointerAlignment(
987     CharUnits UnpackedBaseAlign) {
988   CharUnits BaseAlign = Packed ? CharUnits::One() : UnpackedBaseAlign;
989
990   // The maximum field alignment overrides base align.
991   if (!MaxFieldAlignment.isZero()) {
992     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
993     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
994   }
995
996   // Round up the current record size to pointer alignment.
997   setSize(getSize().alignTo(BaseAlign));
998
999   // Update the alignment.
1000   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1001 }
1002
1003 void ItaniumRecordLayoutBuilder::LayoutNonVirtualBases(
1004     const CXXRecordDecl *RD) {
1005   // Then, determine the primary base class.
1006   DeterminePrimaryBase(RD);
1007
1008   // Compute base subobject info.
1009   ComputeBaseSubobjectInfo(RD);
1010
1011   // If we have a primary base class, lay it out.
1012   if (PrimaryBase) {
1013     if (PrimaryBaseIsVirtual) {
1014       // If the primary virtual base was a primary virtual base of some other
1015       // base class we'll have to steal it.
1016       BaseSubobjectInfo *PrimaryBaseInfo = VirtualBaseInfo.lookup(PrimaryBase);
1017       PrimaryBaseInfo->Derived = nullptr;
1018
1019       // We have a virtual primary base, insert it as an indirect primary base.
1020       IndirectPrimaryBases.insert(PrimaryBase);
1021
1022       assert(!VisitedVirtualBases.count(PrimaryBase) &&
1023              "vbase already visited!");
1024       VisitedVirtualBases.insert(PrimaryBase);
1025
1026       LayoutVirtualBase(PrimaryBaseInfo);
1027     } else {
1028       BaseSubobjectInfo *PrimaryBaseInfo =
1029         NonVirtualBaseInfo.lookup(PrimaryBase);
1030       assert(PrimaryBaseInfo &&
1031              "Did not find base info for non-virtual primary base!");
1032
1033       LayoutNonVirtualBase(PrimaryBaseInfo);
1034     }
1035
1036   // If this class needs a vtable/vf-table and didn't get one from a
1037   // primary base, add it in now.
1038   } else if (RD->isDynamicClass()) {
1039     assert(DataSize == 0 && "Vtable pointer must be at offset zero!");
1040     CharUnits PtrWidth =
1041       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
1042     CharUnits PtrAlign =
1043       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(0));
1044     EnsureVTablePointerAlignment(PtrAlign);
1045     HasOwnVFPtr = true;
1046     setSize(getSize() + PtrWidth);
1047     setDataSize(getSize());
1048   }
1049
1050   // Now lay out the non-virtual bases.
1051   for (const auto &I : RD->bases()) {
1052
1053     // Ignore virtual bases.
1054     if (I.isVirtual())
1055       continue;
1056
1057     const CXXRecordDecl *BaseDecl = I.getType()->getAsCXXRecordDecl();
1058
1059     // Skip the primary base, because we've already laid it out.  The
1060     // !PrimaryBaseIsVirtual check is required because we might have a
1061     // non-virtual base of the same type as a primary virtual base.
1062     if (BaseDecl == PrimaryBase && !PrimaryBaseIsVirtual)
1063       continue;
1064
1065     // Lay out the base.
1066     BaseSubobjectInfo *BaseInfo = NonVirtualBaseInfo.lookup(BaseDecl);
1067     assert(BaseInfo && "Did not find base info for non-virtual base!");
1068
1069     LayoutNonVirtualBase(BaseInfo);
1070   }
1071 }
1072
1073 void ItaniumRecordLayoutBuilder::LayoutNonVirtualBase(
1074     const BaseSubobjectInfo *Base) {
1075   // Layout the base.
1076   CharUnits Offset = LayoutBase(Base);
1077
1078   // Add its base class offset.
1079   assert(!Bases.count(Base->Class) && "base offset already exists!");
1080   Bases.insert(std::make_pair(Base->Class, Offset));
1081
1082   AddPrimaryVirtualBaseOffsets(Base, Offset);
1083 }
1084
1085 void ItaniumRecordLayoutBuilder::AddPrimaryVirtualBaseOffsets(
1086     const BaseSubobjectInfo *Info, CharUnits Offset) {
1087   // This base isn't interesting, it has no virtual bases.
1088   if (!Info->Class->getNumVBases())
1089     return;
1090
1091   // First, check if we have a virtual primary base to add offsets for.
1092   if (Info->PrimaryVirtualBaseInfo) {
1093     assert(Info->PrimaryVirtualBaseInfo->IsVirtual &&
1094            "Primary virtual base is not virtual!");
1095     if (Info->PrimaryVirtualBaseInfo->Derived == Info) {
1096       // Add the offset.
1097       assert(!VBases.count(Info->PrimaryVirtualBaseInfo->Class) &&
1098              "primary vbase offset already exists!");
1099       VBases.insert(std::make_pair(Info->PrimaryVirtualBaseInfo->Class,
1100                                    ASTRecordLayout::VBaseInfo(Offset, false)));
1101
1102       // Traverse the primary virtual base.
1103       AddPrimaryVirtualBaseOffsets(Info->PrimaryVirtualBaseInfo, Offset);
1104     }
1105   }
1106
1107   // Now go through all direct non-virtual bases.
1108   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Info->Class);
1109   for (const BaseSubobjectInfo *Base : Info->Bases) {
1110     if (Base->IsVirtual)
1111       continue;
1112
1113     CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base->Class);
1114     AddPrimaryVirtualBaseOffsets(Base, BaseOffset);
1115   }
1116 }
1117
1118 void ItaniumRecordLayoutBuilder::LayoutVirtualBases(
1119     const CXXRecordDecl *RD, const CXXRecordDecl *MostDerivedClass) {
1120   const CXXRecordDecl *PrimaryBase;
1121   bool PrimaryBaseIsVirtual;
1122
1123   if (MostDerivedClass == RD) {
1124     PrimaryBase = this->PrimaryBase;
1125     PrimaryBaseIsVirtual = this->PrimaryBaseIsVirtual;
1126   } else {
1127     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1128     PrimaryBase = Layout.getPrimaryBase();
1129     PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
1130   }
1131
1132   for (const CXXBaseSpecifier &Base : RD->bases()) {
1133     assert(!Base.getType()->isDependentType() &&
1134            "Cannot layout class with dependent bases.");
1135
1136     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1137
1138     if (Base.isVirtual()) {
1139       if (PrimaryBase != BaseDecl || !PrimaryBaseIsVirtual) {
1140         bool IndirectPrimaryBase = IndirectPrimaryBases.count(BaseDecl);
1141
1142         // Only lay out the virtual base if it's not an indirect primary base.
1143         if (!IndirectPrimaryBase) {
1144           // Only visit virtual bases once.
1145           if (!VisitedVirtualBases.insert(BaseDecl).second)
1146             continue;
1147
1148           const BaseSubobjectInfo *BaseInfo = VirtualBaseInfo.lookup(BaseDecl);
1149           assert(BaseInfo && "Did not find virtual base info!");
1150           LayoutVirtualBase(BaseInfo);
1151         }
1152       }
1153     }
1154
1155     if (!BaseDecl->getNumVBases()) {
1156       // This base isn't interesting since it doesn't have any virtual bases.
1157       continue;
1158     }
1159
1160     LayoutVirtualBases(BaseDecl, MostDerivedClass);
1161   }
1162 }
1163
1164 void ItaniumRecordLayoutBuilder::LayoutVirtualBase(
1165     const BaseSubobjectInfo *Base) {
1166   assert(!Base->Derived && "Trying to lay out a primary virtual base!");
1167
1168   // Layout the base.
1169   CharUnits Offset = LayoutBase(Base);
1170
1171   // Add its base class offset.
1172   assert(!VBases.count(Base->Class) && "vbase offset already exists!");
1173   VBases.insert(std::make_pair(Base->Class,
1174                        ASTRecordLayout::VBaseInfo(Offset, false)));
1175
1176   AddPrimaryVirtualBaseOffsets(Base, Offset);
1177 }
1178
1179 CharUnits
1180 ItaniumRecordLayoutBuilder::LayoutBase(const BaseSubobjectInfo *Base) {
1181   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base->Class);
1182
1183
1184   CharUnits Offset;
1185
1186   // Query the external layout to see if it provides an offset.
1187   bool HasExternalLayout = false;
1188   if (UseExternalLayout) {
1189     // FIXME: This appears to be reversed.
1190     if (Base->IsVirtual)
1191       HasExternalLayout = External.getExternalNVBaseOffset(Base->Class, Offset);
1192     else
1193       HasExternalLayout = External.getExternalVBaseOffset(Base->Class, Offset);
1194   }
1195
1196   // Clang <= 6 incorrectly applied the 'packed' attribute to base classes.
1197   // Per GCC's documentation, it only applies to non-static data members.
1198   CharUnits UnpackedBaseAlign = Layout.getNonVirtualAlignment();
1199   CharUnits BaseAlign =
1200       (Packed && ((Context.getLangOpts().getClangABICompat() <=
1201                    LangOptions::ClangABI::Ver6) ||
1202                   Context.getTargetInfo().getTriple().isPS4()))
1203           ? CharUnits::One()
1204           : UnpackedBaseAlign;
1205
1206   // If we have an empty base class, try to place it at offset 0.
1207   if (Base->Class->isEmpty() &&
1208       (!HasExternalLayout || Offset == CharUnits::Zero()) &&
1209       EmptySubobjects->CanPlaceBaseAtOffset(Base, CharUnits::Zero())) {
1210     setSize(std::max(getSize(), Layout.getSize()));
1211     UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1212
1213     return CharUnits::Zero();
1214   }
1215
1216   // The maximum field alignment overrides base align.
1217   if (!MaxFieldAlignment.isZero()) {
1218     BaseAlign = std::min(BaseAlign, MaxFieldAlignment);
1219     UnpackedBaseAlign = std::min(UnpackedBaseAlign, MaxFieldAlignment);
1220   }
1221
1222   if (!HasExternalLayout) {
1223     // Round up the current record size to the base's alignment boundary.
1224     Offset = getDataSize().alignTo(BaseAlign);
1225
1226     // Try to place the base.
1227     while (!EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset))
1228       Offset += BaseAlign;
1229   } else {
1230     bool Allowed = EmptySubobjects->CanPlaceBaseAtOffset(Base, Offset);
1231     (void)Allowed;
1232     assert(Allowed && "Base subobject externally placed at overlapping offset");
1233
1234     if (InferAlignment && Offset < getDataSize().alignTo(BaseAlign)) {
1235       // The externally-supplied base offset is before the base offset we
1236       // computed. Assume that the structure is packed.
1237       Alignment = CharUnits::One();
1238       InferAlignment = false;
1239     }
1240   }
1241
1242   if (!Base->Class->isEmpty()) {
1243     // Update the data size.
1244     setDataSize(Offset + Layout.getNonVirtualSize());
1245
1246     setSize(std::max(getSize(), getDataSize()));
1247   } else
1248     setSize(std::max(getSize(), Offset + Layout.getSize()));
1249
1250   // Remember max struct/class alignment.
1251   UpdateAlignment(BaseAlign, UnpackedBaseAlign);
1252
1253   return Offset;
1254 }
1255
1256 void ItaniumRecordLayoutBuilder::InitializeLayout(const Decl *D) {
1257   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) {
1258     IsUnion = RD->isUnion();
1259     IsMsStruct = RD->isMsStruct(Context);
1260   }
1261
1262   Packed = D->hasAttr<PackedAttr>();
1263
1264   // Honor the default struct packing maximum alignment flag.
1265   if (unsigned DefaultMaxFieldAlignment = Context.getLangOpts().PackStruct) {
1266     MaxFieldAlignment = CharUnits::fromQuantity(DefaultMaxFieldAlignment);
1267   }
1268
1269   // mac68k alignment supersedes maximum field alignment and attribute aligned,
1270   // and forces all structures to have 2-byte alignment. The IBM docs on it
1271   // allude to additional (more complicated) semantics, especially with regard
1272   // to bit-fields, but gcc appears not to follow that.
1273   if (D->hasAttr<AlignMac68kAttr>()) {
1274     IsMac68kAlign = true;
1275     MaxFieldAlignment = CharUnits::fromQuantity(2);
1276     Alignment = CharUnits::fromQuantity(2);
1277   } else {
1278     if (const MaxFieldAlignmentAttr *MFAA = D->getAttr<MaxFieldAlignmentAttr>())
1279       MaxFieldAlignment = Context.toCharUnitsFromBits(MFAA->getAlignment());
1280
1281     if (unsigned MaxAlign = D->getMaxAlignment())
1282       UpdateAlignment(Context.toCharUnitsFromBits(MaxAlign));
1283   }
1284
1285   // If there is an external AST source, ask it for the various offsets.
1286   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D))
1287     if (ExternalASTSource *Source = Context.getExternalSource()) {
1288       UseExternalLayout = Source->layoutRecordType(
1289           RD, External.Size, External.Align, External.FieldOffsets,
1290           External.BaseOffsets, External.VirtualBaseOffsets);
1291
1292       // Update based on external alignment.
1293       if (UseExternalLayout) {
1294         if (External.Align > 0) {
1295           Alignment = Context.toCharUnitsFromBits(External.Align);
1296         } else {
1297           // The external source didn't have alignment information; infer it.
1298           InferAlignment = true;
1299         }
1300       }
1301     }
1302 }
1303
1304 void ItaniumRecordLayoutBuilder::Layout(const RecordDecl *D) {
1305   InitializeLayout(D);
1306   LayoutFields(D);
1307
1308   // Finally, round the size of the total struct up to the alignment of the
1309   // struct itself.
1310   FinishLayout(D);
1311 }
1312
1313 void ItaniumRecordLayoutBuilder::Layout(const CXXRecordDecl *RD) {
1314   InitializeLayout(RD);
1315
1316   // Lay out the vtable and the non-virtual bases.
1317   LayoutNonVirtualBases(RD);
1318
1319   LayoutFields(RD);
1320
1321   NonVirtualSize = Context.toCharUnitsFromBits(
1322       llvm::alignTo(getSizeInBits(), Context.getTargetInfo().getCharAlign()));
1323   NonVirtualAlignment = Alignment;
1324
1325   // Lay out the virtual bases and add the primary virtual base offsets.
1326   LayoutVirtualBases(RD, RD);
1327
1328   // Finally, round the size of the total struct up to the alignment
1329   // of the struct itself.
1330   FinishLayout(RD);
1331
1332 #ifndef NDEBUG
1333   // Check that we have base offsets for all bases.
1334   for (const CXXBaseSpecifier &Base : RD->bases()) {
1335     if (Base.isVirtual())
1336       continue;
1337
1338     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1339
1340     assert(Bases.count(BaseDecl) && "Did not find base offset!");
1341   }
1342
1343   // And all virtual bases.
1344   for (const CXXBaseSpecifier &Base : RD->vbases()) {
1345     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
1346
1347     assert(VBases.count(BaseDecl) && "Did not find base offset!");
1348   }
1349 #endif
1350 }
1351
1352 void ItaniumRecordLayoutBuilder::Layout(const ObjCInterfaceDecl *D) {
1353   if (ObjCInterfaceDecl *SD = D->getSuperClass()) {
1354     const ASTRecordLayout &SL = Context.getASTObjCInterfaceLayout(SD);
1355
1356     UpdateAlignment(SL.getAlignment());
1357
1358     // We start laying out ivars not at the end of the superclass
1359     // structure, but at the next byte following the last field.
1360     setDataSize(SL.getDataSize());
1361     setSize(getDataSize());
1362   }
1363
1364   InitializeLayout(D);
1365   // Layout each ivar sequentially.
1366   for (const ObjCIvarDecl *IVD = D->all_declared_ivar_begin(); IVD;
1367        IVD = IVD->getNextIvar())
1368     LayoutField(IVD, false);
1369
1370   // Finally, round the size of the total struct up to the alignment of the
1371   // struct itself.
1372   FinishLayout(D);
1373 }
1374
1375 void ItaniumRecordLayoutBuilder::LayoutFields(const RecordDecl *D) {
1376   // Layout each field, for now, just sequentially, respecting alignment.  In
1377   // the future, this will need to be tweakable by targets.
1378   bool InsertExtraPadding = D->mayInsertExtraPadding(/*EmitRemark=*/true);
1379   bool HasFlexibleArrayMember = D->hasFlexibleArrayMember();
1380   for (auto I = D->field_begin(), End = D->field_end(); I != End; ++I) {
1381     auto Next(I);
1382     ++Next;
1383     LayoutField(*I,
1384                 InsertExtraPadding && (Next != End || !HasFlexibleArrayMember));
1385   }
1386 }
1387
1388 // Rounds the specified size to have it a multiple of the char size.
1389 static uint64_t
1390 roundUpSizeToCharAlignment(uint64_t Size,
1391                            const ASTContext &Context) {
1392   uint64_t CharAlignment = Context.getTargetInfo().getCharAlign();
1393   return llvm::alignTo(Size, CharAlignment);
1394 }
1395
1396 void ItaniumRecordLayoutBuilder::LayoutWideBitField(uint64_t FieldSize,
1397                                                     uint64_t TypeSize,
1398                                                     bool FieldPacked,
1399                                                     const FieldDecl *D) {
1400   assert(Context.getLangOpts().CPlusPlus &&
1401          "Can only have wide bit-fields in C++!");
1402
1403   // Itanium C++ ABI 2.4:
1404   //   If sizeof(T)*8 < n, let T' be the largest integral POD type with
1405   //   sizeof(T')*8 <= n.
1406
1407   QualType IntegralPODTypes[] = {
1408     Context.UnsignedCharTy, Context.UnsignedShortTy, Context.UnsignedIntTy,
1409     Context.UnsignedLongTy, Context.UnsignedLongLongTy
1410   };
1411
1412   QualType Type;
1413   for (const QualType &QT : IntegralPODTypes) {
1414     uint64_t Size = Context.getTypeSize(QT);
1415
1416     if (Size > FieldSize)
1417       break;
1418
1419     Type = QT;
1420   }
1421   assert(!Type.isNull() && "Did not find a type!");
1422
1423   CharUnits TypeAlign = Context.getTypeAlignInChars(Type);
1424
1425   // We're not going to use any of the unfilled bits in the last byte.
1426   UnfilledBitsInLastUnit = 0;
1427   LastBitfieldTypeSize = 0;
1428
1429   uint64_t FieldOffset;
1430   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastUnit;
1431
1432   if (IsUnion) {
1433     uint64_t RoundedFieldSize = roundUpSizeToCharAlignment(FieldSize,
1434                                                            Context);
1435     setDataSize(std::max(getDataSizeInBits(), RoundedFieldSize));
1436     FieldOffset = 0;
1437   } else {
1438     // The bitfield is allocated starting at the next offset aligned
1439     // appropriately for T', with length n bits.
1440     FieldOffset = llvm::alignTo(getDataSizeInBits(), Context.toBits(TypeAlign));
1441
1442     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1443
1444     setDataSize(
1445         llvm::alignTo(NewSizeInBits, Context.getTargetInfo().getCharAlign()));
1446     UnfilledBitsInLastUnit = getDataSizeInBits() - NewSizeInBits;
1447   }
1448
1449   // Place this field at the current location.
1450   FieldOffsets.push_back(FieldOffset);
1451
1452   CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, FieldOffset,
1453                     Context.toBits(TypeAlign), FieldPacked, D);
1454
1455   // Update the size.
1456   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1457
1458   // Remember max struct/class alignment.
1459   UpdateAlignment(TypeAlign);
1460 }
1461
1462 void ItaniumRecordLayoutBuilder::LayoutBitField(const FieldDecl *D) {
1463   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1464   uint64_t FieldSize = D->getBitWidthValue(Context);
1465   TypeInfo FieldInfo = Context.getTypeInfo(D->getType());
1466   uint64_t TypeSize = FieldInfo.Width;
1467   unsigned FieldAlign = FieldInfo.Align;
1468
1469   // UnfilledBitsInLastUnit is the difference between the end of the
1470   // last allocated bitfield (i.e. the first bit offset available for
1471   // bitfields) and the end of the current data size in bits (i.e. the
1472   // first bit offset available for non-bitfields).  The current data
1473   // size in bits is always a multiple of the char size; additionally,
1474   // for ms_struct records it's also a multiple of the
1475   // LastBitfieldTypeSize (if set).
1476
1477   // The struct-layout algorithm is dictated by the platform ABI,
1478   // which in principle could use almost any rules it likes.  In
1479   // practice, UNIXy targets tend to inherit the algorithm described
1480   // in the System V generic ABI.  The basic bitfield layout rule in
1481   // System V is to place bitfields at the next available bit offset
1482   // where the entire bitfield would fit in an aligned storage unit of
1483   // the declared type; it's okay if an earlier or later non-bitfield
1484   // is allocated in the same storage unit.  However, some targets
1485   // (those that !useBitFieldTypeAlignment(), e.g. ARM APCS) don't
1486   // require this storage unit to be aligned, and therefore always put
1487   // the bitfield at the next available bit offset.
1488
1489   // ms_struct basically requests a complete replacement of the
1490   // platform ABI's struct-layout algorithm, with the high-level goal
1491   // of duplicating MSVC's layout.  For non-bitfields, this follows
1492   // the standard algorithm.  The basic bitfield layout rule is to
1493   // allocate an entire unit of the bitfield's declared type
1494   // (e.g. 'unsigned long'), then parcel it up among successive
1495   // bitfields whose declared types have the same size, making a new
1496   // unit as soon as the last can no longer store the whole value.
1497   // Since it completely replaces the platform ABI's algorithm,
1498   // settings like !useBitFieldTypeAlignment() do not apply.
1499
1500   // A zero-width bitfield forces the use of a new storage unit for
1501   // later bitfields.  In general, this occurs by rounding up the
1502   // current size of the struct as if the algorithm were about to
1503   // place a non-bitfield of the field's formal type.  Usually this
1504   // does not change the alignment of the struct itself, but it does
1505   // on some targets (those that useZeroLengthBitfieldAlignment(),
1506   // e.g. ARM).  In ms_struct layout, zero-width bitfields are
1507   // ignored unless they follow a non-zero-width bitfield.
1508
1509   // A field alignment restriction (e.g. from #pragma pack) or
1510   // specification (e.g. from __attribute__((aligned))) changes the
1511   // formal alignment of the field.  For System V, this alters the
1512   // required alignment of the notional storage unit that must contain
1513   // the bitfield.  For ms_struct, this only affects the placement of
1514   // new storage units.  In both cases, the effect of #pragma pack is
1515   // ignored on zero-width bitfields.
1516
1517   // On System V, a packed field (e.g. from #pragma pack or
1518   // __attribute__((packed))) always uses the next available bit
1519   // offset.
1520
1521   // In an ms_struct struct, the alignment of a fundamental type is
1522   // always equal to its size.  This is necessary in order to mimic
1523   // the i386 alignment rules on targets which might not fully align
1524   // all types (e.g. Darwin PPC32, where alignof(long long) == 4).
1525
1526   // First, some simple bookkeeping to perform for ms_struct structs.
1527   if (IsMsStruct) {
1528     // The field alignment for integer types is always the size.
1529     FieldAlign = TypeSize;
1530
1531     // If the previous field was not a bitfield, or was a bitfield
1532     // with a different storage unit size, or if this field doesn't fit into
1533     // the current storage unit, we're done with that storage unit.
1534     if (LastBitfieldTypeSize != TypeSize ||
1535         UnfilledBitsInLastUnit < FieldSize) {
1536       // Also, ignore zero-length bitfields after non-bitfields.
1537       if (!LastBitfieldTypeSize && !FieldSize)
1538         FieldAlign = 1;
1539
1540       UnfilledBitsInLastUnit = 0;
1541       LastBitfieldTypeSize = 0;
1542     }
1543   }
1544
1545   // If the field is wider than its declared type, it follows
1546   // different rules in all cases.
1547   if (FieldSize > TypeSize) {
1548     LayoutWideBitField(FieldSize, TypeSize, FieldPacked, D);
1549     return;
1550   }
1551
1552   // Compute the next available bit offset.
1553   uint64_t FieldOffset =
1554     IsUnion ? 0 : (getDataSizeInBits() - UnfilledBitsInLastUnit);
1555
1556   // Handle targets that don't honor bitfield type alignment.
1557   if (!IsMsStruct && !Context.getTargetInfo().useBitFieldTypeAlignment()) {
1558     // Some such targets do honor it on zero-width bitfields.
1559     if (FieldSize == 0 &&
1560         Context.getTargetInfo().useZeroLengthBitfieldAlignment()) {
1561       // The alignment to round up to is the max of the field's natural
1562       // alignment and a target-specific fixed value (sometimes zero).
1563       unsigned ZeroLengthBitfieldBoundary =
1564         Context.getTargetInfo().getZeroLengthBitfieldBoundary();
1565       FieldAlign = std::max(FieldAlign, ZeroLengthBitfieldBoundary);
1566
1567     // If that doesn't apply, just ignore the field alignment.
1568     } else {
1569       FieldAlign = 1;
1570     }
1571   }
1572
1573   // Remember the alignment we would have used if the field were not packed.
1574   unsigned UnpackedFieldAlign = FieldAlign;
1575
1576   // Ignore the field alignment if the field is packed unless it has zero-size.
1577   if (!IsMsStruct && FieldPacked && FieldSize != 0)
1578     FieldAlign = 1;
1579
1580   // But, if there's an 'aligned' attribute on the field, honor that.
1581   unsigned ExplicitFieldAlign = D->getMaxAlignment();
1582   if (ExplicitFieldAlign) {
1583     FieldAlign = std::max(FieldAlign, ExplicitFieldAlign);
1584     UnpackedFieldAlign = std::max(UnpackedFieldAlign, ExplicitFieldAlign);
1585   }
1586
1587   // But, if there's a #pragma pack in play, that takes precedent over
1588   // even the 'aligned' attribute, for non-zero-width bitfields.
1589   unsigned MaxFieldAlignmentInBits = Context.toBits(MaxFieldAlignment);
1590   if (!MaxFieldAlignment.isZero() && FieldSize) {
1591     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignmentInBits);
1592     if (FieldPacked)
1593       FieldAlign = UnpackedFieldAlign;
1594     else
1595       FieldAlign = std::min(FieldAlign, MaxFieldAlignmentInBits);
1596   }
1597
1598   // But, ms_struct just ignores all of that in unions, even explicit
1599   // alignment attributes.
1600   if (IsMsStruct && IsUnion) {
1601     FieldAlign = UnpackedFieldAlign = 1;
1602   }
1603
1604   // For purposes of diagnostics, we're going to simultaneously
1605   // compute the field offsets that we would have used if we weren't
1606   // adding any alignment padding or if the field weren't packed.
1607   uint64_t UnpaddedFieldOffset = FieldOffset;
1608   uint64_t UnpackedFieldOffset = FieldOffset;
1609
1610   // Check if we need to add padding to fit the bitfield within an
1611   // allocation unit with the right size and alignment.  The rules are
1612   // somewhat different here for ms_struct structs.
1613   if (IsMsStruct) {
1614     // If it's not a zero-width bitfield, and we can fit the bitfield
1615     // into the active storage unit (and we haven't already decided to
1616     // start a new storage unit), just do so, regardless of any other
1617     // other consideration.  Otherwise, round up to the right alignment.
1618     if (FieldSize == 0 || FieldSize > UnfilledBitsInLastUnit) {
1619       FieldOffset = llvm::alignTo(FieldOffset, FieldAlign);
1620       UnpackedFieldOffset =
1621           llvm::alignTo(UnpackedFieldOffset, UnpackedFieldAlign);
1622       UnfilledBitsInLastUnit = 0;
1623     }
1624
1625   } else {
1626     // #pragma pack, with any value, suppresses the insertion of padding.
1627     bool AllowPadding = MaxFieldAlignment.isZero();
1628
1629     // Compute the real offset.
1630     if (FieldSize == 0 ||
1631         (AllowPadding &&
1632          (FieldOffset & (FieldAlign-1)) + FieldSize > TypeSize)) {
1633       FieldOffset = llvm::alignTo(FieldOffset, FieldAlign);
1634     } else if (ExplicitFieldAlign &&
1635                (MaxFieldAlignmentInBits == 0 ||
1636                 ExplicitFieldAlign <= MaxFieldAlignmentInBits) &&
1637                Context.getTargetInfo().useExplicitBitFieldAlignment()) {
1638       // TODO: figure it out what needs to be done on targets that don't honor
1639       // bit-field type alignment like ARM APCS ABI.
1640       FieldOffset = llvm::alignTo(FieldOffset, ExplicitFieldAlign);
1641     }
1642
1643     // Repeat the computation for diagnostic purposes.
1644     if (FieldSize == 0 ||
1645         (AllowPadding &&
1646          (UnpackedFieldOffset & (UnpackedFieldAlign-1)) + FieldSize > TypeSize))
1647       UnpackedFieldOffset =
1648           llvm::alignTo(UnpackedFieldOffset, UnpackedFieldAlign);
1649     else if (ExplicitFieldAlign &&
1650              (MaxFieldAlignmentInBits == 0 ||
1651               ExplicitFieldAlign <= MaxFieldAlignmentInBits) &&
1652              Context.getTargetInfo().useExplicitBitFieldAlignment())
1653       UnpackedFieldOffset =
1654           llvm::alignTo(UnpackedFieldOffset, ExplicitFieldAlign);
1655   }
1656
1657   // If we're using external layout, give the external layout a chance
1658   // to override this information.
1659   if (UseExternalLayout)
1660     FieldOffset = updateExternalFieldOffset(D, FieldOffset);
1661
1662   // Okay, place the bitfield at the calculated offset.
1663   FieldOffsets.push_back(FieldOffset);
1664
1665   // Bookkeeping:
1666
1667   // Anonymous members don't affect the overall record alignment,
1668   // except on targets where they do.
1669   if (!IsMsStruct &&
1670       !Context.getTargetInfo().useZeroLengthBitfieldAlignment() &&
1671       !D->getIdentifier())
1672     FieldAlign = UnpackedFieldAlign = 1;
1673
1674   // Diagnose differences in layout due to padding or packing.
1675   if (!UseExternalLayout)
1676     CheckFieldPadding(FieldOffset, UnpaddedFieldOffset, UnpackedFieldOffset,
1677                       UnpackedFieldAlign, FieldPacked, D);
1678
1679   // Update DataSize to include the last byte containing (part of) the bitfield.
1680
1681   // For unions, this is just a max operation, as usual.
1682   if (IsUnion) {
1683     // For ms_struct, allocate the entire storage unit --- unless this
1684     // is a zero-width bitfield, in which case just use a size of 1.
1685     uint64_t RoundedFieldSize;
1686     if (IsMsStruct) {
1687       RoundedFieldSize =
1688         (FieldSize ? TypeSize : Context.getTargetInfo().getCharWidth());
1689
1690     // Otherwise, allocate just the number of bytes required to store
1691     // the bitfield.
1692     } else {
1693       RoundedFieldSize = roundUpSizeToCharAlignment(FieldSize, Context);
1694     }
1695     setDataSize(std::max(getDataSizeInBits(), RoundedFieldSize));
1696
1697   // For non-zero-width bitfields in ms_struct structs, allocate a new
1698   // storage unit if necessary.
1699   } else if (IsMsStruct && FieldSize) {
1700     // We should have cleared UnfilledBitsInLastUnit in every case
1701     // where we changed storage units.
1702     if (!UnfilledBitsInLastUnit) {
1703       setDataSize(FieldOffset + TypeSize);
1704       UnfilledBitsInLastUnit = TypeSize;
1705     }
1706     UnfilledBitsInLastUnit -= FieldSize;
1707     LastBitfieldTypeSize = TypeSize;
1708
1709   // Otherwise, bump the data size up to include the bitfield,
1710   // including padding up to char alignment, and then remember how
1711   // bits we didn't use.
1712   } else {
1713     uint64_t NewSizeInBits = FieldOffset + FieldSize;
1714     uint64_t CharAlignment = Context.getTargetInfo().getCharAlign();
1715     setDataSize(llvm::alignTo(NewSizeInBits, CharAlignment));
1716     UnfilledBitsInLastUnit = getDataSizeInBits() - NewSizeInBits;
1717
1718     // The only time we can get here for an ms_struct is if this is a
1719     // zero-width bitfield, which doesn't count as anything for the
1720     // purposes of unfilled bits.
1721     LastBitfieldTypeSize = 0;
1722   }
1723
1724   // Update the size.
1725   setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1726
1727   // Remember max struct/class alignment.
1728   UnadjustedAlignment =
1729       std::max(UnadjustedAlignment, Context.toCharUnitsFromBits(FieldAlign));
1730   UpdateAlignment(Context.toCharUnitsFromBits(FieldAlign),
1731                   Context.toCharUnitsFromBits(UnpackedFieldAlign));
1732 }
1733
1734 void ItaniumRecordLayoutBuilder::LayoutField(const FieldDecl *D,
1735                                              bool InsertExtraPadding) {
1736   if (D->isBitField()) {
1737     LayoutBitField(D);
1738     return;
1739   }
1740
1741   uint64_t UnpaddedFieldOffset = getDataSizeInBits() - UnfilledBitsInLastUnit;
1742
1743   // Reset the unfilled bits.
1744   UnfilledBitsInLastUnit = 0;
1745   LastBitfieldTypeSize = 0;
1746
1747   auto *FieldClass = D->getType()->getAsCXXRecordDecl();
1748   bool PotentiallyOverlapping = D->hasAttr<NoUniqueAddressAttr>() && FieldClass;
1749   bool IsOverlappingEmptyField = PotentiallyOverlapping && FieldClass->isEmpty();
1750   bool FieldPacked = Packed || D->hasAttr<PackedAttr>();
1751
1752   CharUnits FieldOffset = (IsUnion || IsOverlappingEmptyField)
1753                               ? CharUnits::Zero()
1754                               : getDataSize();
1755   CharUnits FieldSize;
1756   CharUnits FieldAlign;
1757   // The amount of this class's dsize occupied by the field.
1758   // This is equal to FieldSize unless we're permitted to pack
1759   // into the field's tail padding.
1760   CharUnits EffectiveFieldSize;
1761
1762   if (D->getType()->isIncompleteArrayType()) {
1763     // This is a flexible array member; we can't directly
1764     // query getTypeInfo about these, so we figure it out here.
1765     // Flexible array members don't have any size, but they
1766     // have to be aligned appropriately for their element type.
1767     EffectiveFieldSize = FieldSize = CharUnits::Zero();
1768     const ArrayType* ATy = Context.getAsArrayType(D->getType());
1769     FieldAlign = Context.getTypeAlignInChars(ATy->getElementType());
1770   } else if (const ReferenceType *RT = D->getType()->getAs<ReferenceType>()) {
1771     unsigned AS = Context.getTargetAddressSpace(RT->getPointeeType());
1772     EffectiveFieldSize = FieldSize =
1773       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(AS));
1774     FieldAlign =
1775       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(AS));
1776   } else {
1777     std::pair<CharUnits, CharUnits> FieldInfo =
1778       Context.getTypeInfoInChars(D->getType());
1779     EffectiveFieldSize = FieldSize = FieldInfo.first;
1780     FieldAlign = FieldInfo.second;
1781
1782     // A potentially-overlapping field occupies its dsize or nvsize, whichever
1783     // is larger.
1784     if (PotentiallyOverlapping) {
1785       const ASTRecordLayout &Layout = Context.getASTRecordLayout(FieldClass);
1786       EffectiveFieldSize =
1787           std::max(Layout.getNonVirtualSize(), Layout.getDataSize());
1788     }
1789
1790     if (IsMsStruct) {
1791       // If MS bitfield layout is required, figure out what type is being
1792       // laid out and align the field to the width of that type.
1793
1794       // Resolve all typedefs down to their base type and round up the field
1795       // alignment if necessary.
1796       QualType T = Context.getBaseElementType(D->getType());
1797       if (const BuiltinType *BTy = T->getAs<BuiltinType>()) {
1798         CharUnits TypeSize = Context.getTypeSizeInChars(BTy);
1799
1800         if (!llvm::isPowerOf2_64(TypeSize.getQuantity())) {
1801           assert(
1802               !Context.getTargetInfo().getTriple().isWindowsMSVCEnvironment() &&
1803               "Non PowerOf2 size in MSVC mode");
1804           // Base types with sizes that aren't a power of two don't work
1805           // with the layout rules for MS structs. This isn't an issue in
1806           // MSVC itself since there are no such base data types there.
1807           // On e.g. x86_32 mingw and linux, long double is 12 bytes though.
1808           // Any structs involving that data type obviously can't be ABI
1809           // compatible with MSVC regardless of how it is laid out.
1810
1811           // Since ms_struct can be mass enabled (via a pragma or via the
1812           // -mms-bitfields command line parameter), this can trigger for
1813           // structs that don't actually need MSVC compatibility, so we
1814           // need to be able to sidestep the ms_struct layout for these types.
1815
1816           // Since the combination of -mms-bitfields together with structs
1817           // like max_align_t (which contains a long double) for mingw is
1818           // quite comon (and GCC handles it silently), just handle it
1819           // silently there. For other targets that have ms_struct enabled
1820           // (most probably via a pragma or attribute), trigger a diagnostic
1821           // that defaults to an error.
1822           if (!Context.getTargetInfo().getTriple().isWindowsGNUEnvironment())
1823             Diag(D->getLocation(), diag::warn_npot_ms_struct);
1824         }
1825         if (TypeSize > FieldAlign &&
1826             llvm::isPowerOf2_64(TypeSize.getQuantity()))
1827           FieldAlign = TypeSize;
1828       }
1829     }
1830   }
1831
1832   // The align if the field is not packed. This is to check if the attribute
1833   // was unnecessary (-Wpacked).
1834   CharUnits UnpackedFieldAlign = FieldAlign;
1835   CharUnits UnpackedFieldOffset = FieldOffset;
1836
1837   if (FieldPacked)
1838     FieldAlign = CharUnits::One();
1839   CharUnits MaxAlignmentInChars =
1840     Context.toCharUnitsFromBits(D->getMaxAlignment());
1841   FieldAlign = std::max(FieldAlign, MaxAlignmentInChars);
1842   UnpackedFieldAlign = std::max(UnpackedFieldAlign, MaxAlignmentInChars);
1843
1844   // The maximum field alignment overrides the aligned attribute.
1845   if (!MaxFieldAlignment.isZero()) {
1846     FieldAlign = std::min(FieldAlign, MaxFieldAlignment);
1847     UnpackedFieldAlign = std::min(UnpackedFieldAlign, MaxFieldAlignment);
1848   }
1849
1850   // Round up the current record size to the field's alignment boundary.
1851   FieldOffset = FieldOffset.alignTo(FieldAlign);
1852   UnpackedFieldOffset = UnpackedFieldOffset.alignTo(UnpackedFieldAlign);
1853
1854   if (UseExternalLayout) {
1855     FieldOffset = Context.toCharUnitsFromBits(
1856                     updateExternalFieldOffset(D, Context.toBits(FieldOffset)));
1857
1858     if (!IsUnion && EmptySubobjects) {
1859       // Record the fact that we're placing a field at this offset.
1860       bool Allowed = EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset);
1861       (void)Allowed;
1862       assert(Allowed && "Externally-placed field cannot be placed here");
1863     }
1864   } else {
1865     if (!IsUnion && EmptySubobjects) {
1866       // Check if we can place the field at this offset.
1867       while (!EmptySubobjects->CanPlaceFieldAtOffset(D, FieldOffset)) {
1868         // We couldn't place the field at the offset. Try again at a new offset.
1869         // We try offset 0 (for an empty field) and then dsize(C) onwards.
1870         if (FieldOffset == CharUnits::Zero() &&
1871             getDataSize() != CharUnits::Zero())
1872           FieldOffset = getDataSize().alignTo(FieldAlign);
1873         else
1874           FieldOffset += FieldAlign;
1875       }
1876     }
1877   }
1878
1879   // Place this field at the current location.
1880   FieldOffsets.push_back(Context.toBits(FieldOffset));
1881
1882   if (!UseExternalLayout)
1883     CheckFieldPadding(Context.toBits(FieldOffset), UnpaddedFieldOffset,
1884                       Context.toBits(UnpackedFieldOffset),
1885                       Context.toBits(UnpackedFieldAlign), FieldPacked, D);
1886
1887   if (InsertExtraPadding) {
1888     CharUnits ASanAlignment = CharUnits::fromQuantity(8);
1889     CharUnits ExtraSizeForAsan = ASanAlignment;
1890     if (FieldSize % ASanAlignment)
1891       ExtraSizeForAsan +=
1892           ASanAlignment - CharUnits::fromQuantity(FieldSize % ASanAlignment);
1893     EffectiveFieldSize = FieldSize = FieldSize + ExtraSizeForAsan;
1894   }
1895
1896   // Reserve space for this field.
1897   if (!IsOverlappingEmptyField) {
1898     uint64_t EffectiveFieldSizeInBits = Context.toBits(EffectiveFieldSize);
1899     if (IsUnion)
1900       setDataSize(std::max(getDataSizeInBits(), EffectiveFieldSizeInBits));
1901     else
1902       setDataSize(FieldOffset + EffectiveFieldSize);
1903
1904     PaddedFieldSize = std::max(PaddedFieldSize, FieldOffset + FieldSize);
1905     setSize(std::max(getSizeInBits(), getDataSizeInBits()));
1906   } else {
1907     setSize(std::max(getSizeInBits(),
1908                      (uint64_t)Context.toBits(FieldOffset + FieldSize)));
1909   }
1910
1911   // Remember max struct/class alignment.
1912   UnadjustedAlignment = std::max(UnadjustedAlignment, FieldAlign);
1913   UpdateAlignment(FieldAlign, UnpackedFieldAlign);
1914 }
1915
1916 void ItaniumRecordLayoutBuilder::FinishLayout(const NamedDecl *D) {
1917   // In C++, records cannot be of size 0.
1918   if (Context.getLangOpts().CPlusPlus && getSizeInBits() == 0) {
1919     if (const CXXRecordDecl *RD = dyn_cast<CXXRecordDecl>(D)) {
1920       // Compatibility with gcc requires a class (pod or non-pod)
1921       // which is not empty but of size 0; such as having fields of
1922       // array of zero-length, remains of Size 0
1923       if (RD->isEmpty())
1924         setSize(CharUnits::One());
1925     }
1926     else
1927       setSize(CharUnits::One());
1928   }
1929
1930   // If we have any remaining field tail padding, include that in the overall
1931   // size.
1932   setSize(std::max(getSizeInBits(), (uint64_t)Context.toBits(PaddedFieldSize)));
1933
1934   // Finally, round the size of the record up to the alignment of the
1935   // record itself.
1936   uint64_t UnpaddedSize = getSizeInBits() - UnfilledBitsInLastUnit;
1937   uint64_t UnpackedSizeInBits =
1938       llvm::alignTo(getSizeInBits(), Context.toBits(UnpackedAlignment));
1939   uint64_t RoundedSize =
1940       llvm::alignTo(getSizeInBits(), Context.toBits(Alignment));
1941
1942   if (UseExternalLayout) {
1943     // If we're inferring alignment, and the external size is smaller than
1944     // our size after we've rounded up to alignment, conservatively set the
1945     // alignment to 1.
1946     if (InferAlignment && External.Size < RoundedSize) {
1947       Alignment = CharUnits::One();
1948       InferAlignment = false;
1949     }
1950     setSize(External.Size);
1951     return;
1952   }
1953
1954   // Set the size to the final size.
1955   setSize(RoundedSize);
1956
1957   unsigned CharBitNum = Context.getTargetInfo().getCharWidth();
1958   if (const RecordDecl *RD = dyn_cast<RecordDecl>(D)) {
1959     // Warn if padding was introduced to the struct/class/union.
1960     if (getSizeInBits() > UnpaddedSize) {
1961       unsigned PadSize = getSizeInBits() - UnpaddedSize;
1962       bool InBits = true;
1963       if (PadSize % CharBitNum == 0) {
1964         PadSize = PadSize / CharBitNum;
1965         InBits = false;
1966       }
1967       Diag(RD->getLocation(), diag::warn_padded_struct_size)
1968           << Context.getTypeDeclType(RD)
1969           << PadSize
1970           << (InBits ? 1 : 0); // (byte|bit)
1971     }
1972
1973     // Warn if we packed it unnecessarily, when the unpacked alignment is not
1974     // greater than the one after packing, the size in bits doesn't change and
1975     // the offset of each field is identical.
1976     if (Packed && UnpackedAlignment <= Alignment &&
1977         UnpackedSizeInBits == getSizeInBits() && !HasPackedField)
1978       Diag(D->getLocation(), diag::warn_unnecessary_packed)
1979           << Context.getTypeDeclType(RD);
1980   }
1981 }
1982
1983 void ItaniumRecordLayoutBuilder::UpdateAlignment(
1984     CharUnits NewAlignment, CharUnits UnpackedNewAlignment) {
1985   // The alignment is not modified when using 'mac68k' alignment or when
1986   // we have an externally-supplied layout that also provides overall alignment.
1987   if (IsMac68kAlign || (UseExternalLayout && !InferAlignment))
1988     return;
1989
1990   if (NewAlignment > Alignment) {
1991     assert(llvm::isPowerOf2_64(NewAlignment.getQuantity()) &&
1992            "Alignment not a power of 2");
1993     Alignment = NewAlignment;
1994   }
1995
1996   if (UnpackedNewAlignment > UnpackedAlignment) {
1997     assert(llvm::isPowerOf2_64(UnpackedNewAlignment.getQuantity()) &&
1998            "Alignment not a power of 2");
1999     UnpackedAlignment = UnpackedNewAlignment;
2000   }
2001 }
2002
2003 uint64_t
2004 ItaniumRecordLayoutBuilder::updateExternalFieldOffset(const FieldDecl *Field,
2005                                                       uint64_t ComputedOffset) {
2006   uint64_t ExternalFieldOffset = External.getExternalFieldOffset(Field);
2007
2008   if (InferAlignment && ExternalFieldOffset < ComputedOffset) {
2009     // The externally-supplied field offset is before the field offset we
2010     // computed. Assume that the structure is packed.
2011     Alignment = CharUnits::One();
2012     InferAlignment = false;
2013   }
2014
2015   // Use the externally-supplied field offset.
2016   return ExternalFieldOffset;
2017 }
2018
2019 /// Get diagnostic %select index for tag kind for
2020 /// field padding diagnostic message.
2021 /// WARNING: Indexes apply to particular diagnostics only!
2022 ///
2023 /// \returns diagnostic %select index.
2024 static unsigned getPaddingDiagFromTagKind(TagTypeKind Tag) {
2025   switch (Tag) {
2026   case TTK_Struct: return 0;
2027   case TTK_Interface: return 1;
2028   case TTK_Class: return 2;
2029   default: llvm_unreachable("Invalid tag kind for field padding diagnostic!");
2030   }
2031 }
2032
2033 void ItaniumRecordLayoutBuilder::CheckFieldPadding(
2034     uint64_t Offset, uint64_t UnpaddedOffset, uint64_t UnpackedOffset,
2035     unsigned UnpackedAlign, bool isPacked, const FieldDecl *D) {
2036   // We let objc ivars without warning, objc interfaces generally are not used
2037   // for padding tricks.
2038   if (isa<ObjCIvarDecl>(D))
2039     return;
2040
2041   // Don't warn about structs created without a SourceLocation.  This can
2042   // be done by clients of the AST, such as codegen.
2043   if (D->getLocation().isInvalid())
2044     return;
2045
2046   unsigned CharBitNum = Context.getTargetInfo().getCharWidth();
2047
2048   // Warn if padding was introduced to the struct/class.
2049   if (!IsUnion && Offset > UnpaddedOffset) {
2050     unsigned PadSize = Offset - UnpaddedOffset;
2051     bool InBits = true;
2052     if (PadSize % CharBitNum == 0) {
2053       PadSize = PadSize / CharBitNum;
2054       InBits = false;
2055     }
2056     if (D->getIdentifier())
2057       Diag(D->getLocation(), diag::warn_padded_struct_field)
2058           << getPaddingDiagFromTagKind(D->getParent()->getTagKind())
2059           << Context.getTypeDeclType(D->getParent())
2060           << PadSize
2061           << (InBits ? 1 : 0) // (byte|bit)
2062           << D->getIdentifier();
2063     else
2064       Diag(D->getLocation(), diag::warn_padded_struct_anon_field)
2065           << getPaddingDiagFromTagKind(D->getParent()->getTagKind())
2066           << Context.getTypeDeclType(D->getParent())
2067           << PadSize
2068           << (InBits ? 1 : 0); // (byte|bit)
2069  }
2070  if (isPacked && Offset != UnpackedOffset) {
2071    HasPackedField = true;
2072  }
2073 }
2074
2075 static const CXXMethodDecl *computeKeyFunction(ASTContext &Context,
2076                                                const CXXRecordDecl *RD) {
2077   // If a class isn't polymorphic it doesn't have a key function.
2078   if (!RD->isPolymorphic())
2079     return nullptr;
2080
2081   // A class that is not externally visible doesn't have a key function. (Or
2082   // at least, there's no point to assigning a key function to such a class;
2083   // this doesn't affect the ABI.)
2084   if (!RD->isExternallyVisible())
2085     return nullptr;
2086
2087   // Template instantiations don't have key functions per Itanium C++ ABI 5.2.6.
2088   // Same behavior as GCC.
2089   TemplateSpecializationKind TSK = RD->getTemplateSpecializationKind();
2090   if (TSK == TSK_ImplicitInstantiation ||
2091       TSK == TSK_ExplicitInstantiationDeclaration ||
2092       TSK == TSK_ExplicitInstantiationDefinition)
2093     return nullptr;
2094
2095   bool allowInlineFunctions =
2096     Context.getTargetInfo().getCXXABI().canKeyFunctionBeInline();
2097
2098   for (const CXXMethodDecl *MD : RD->methods()) {
2099     if (!MD->isVirtual())
2100       continue;
2101
2102     if (MD->isPure())
2103       continue;
2104
2105     // Ignore implicit member functions, they are always marked as inline, but
2106     // they don't have a body until they're defined.
2107     if (MD->isImplicit())
2108       continue;
2109
2110     if (MD->isInlineSpecified())
2111       continue;
2112
2113     if (MD->hasInlineBody())
2114       continue;
2115
2116     // Ignore inline deleted or defaulted functions.
2117     if (!MD->isUserProvided())
2118       continue;
2119
2120     // In certain ABIs, ignore functions with out-of-line inline definitions.
2121     if (!allowInlineFunctions) {
2122       const FunctionDecl *Def;
2123       if (MD->hasBody(Def) && Def->isInlineSpecified())
2124         continue;
2125     }
2126
2127     if (Context.getLangOpts().CUDA) {
2128       // While compiler may see key method in this TU, during CUDA
2129       // compilation we should ignore methods that are not accessible
2130       // on this side of compilation.
2131       if (Context.getLangOpts().CUDAIsDevice) {
2132         // In device mode ignore methods without __device__ attribute.
2133         if (!MD->hasAttr<CUDADeviceAttr>())
2134           continue;
2135       } else {
2136         // In host mode ignore __device__-only methods.
2137         if (!MD->hasAttr<CUDAHostAttr>() && MD->hasAttr<CUDADeviceAttr>())
2138           continue;
2139       }
2140     }
2141
2142     // If the key function is dllimport but the class isn't, then the class has
2143     // no key function. The DLL that exports the key function won't export the
2144     // vtable in this case.
2145     if (MD->hasAttr<DLLImportAttr>() && !RD->hasAttr<DLLImportAttr>())
2146       return nullptr;
2147
2148     // We found it.
2149     return MD;
2150   }
2151
2152   return nullptr;
2153 }
2154
2155 DiagnosticBuilder ItaniumRecordLayoutBuilder::Diag(SourceLocation Loc,
2156                                                    unsigned DiagID) {
2157   return Context.getDiagnostics().Report(Loc, DiagID);
2158 }
2159
2160 /// Does the target C++ ABI require us to skip over the tail-padding
2161 /// of the given class (considering it as a base class) when allocating
2162 /// objects?
2163 static bool mustSkipTailPadding(TargetCXXABI ABI, const CXXRecordDecl *RD) {
2164   switch (ABI.getTailPaddingUseRules()) {
2165   case TargetCXXABI::AlwaysUseTailPadding:
2166     return false;
2167
2168   case TargetCXXABI::UseTailPaddingUnlessPOD03:
2169     // FIXME: To the extent that this is meant to cover the Itanium ABI
2170     // rules, we should implement the restrictions about over-sized
2171     // bitfields:
2172     //
2173     // http://itanium-cxx-abi.github.io/cxx-abi/abi.html#POD :
2174     //   In general, a type is considered a POD for the purposes of
2175     //   layout if it is a POD type (in the sense of ISO C++
2176     //   [basic.types]). However, a POD-struct or POD-union (in the
2177     //   sense of ISO C++ [class]) with a bitfield member whose
2178     //   declared width is wider than the declared type of the
2179     //   bitfield is not a POD for the purpose of layout.  Similarly,
2180     //   an array type is not a POD for the purpose of layout if the
2181     //   element type of the array is not a POD for the purpose of
2182     //   layout.
2183     //
2184     //   Where references to the ISO C++ are made in this paragraph,
2185     //   the Technical Corrigendum 1 version of the standard is
2186     //   intended.
2187     return RD->isPOD();
2188
2189   case TargetCXXABI::UseTailPaddingUnlessPOD11:
2190     // This is equivalent to RD->getTypeForDecl().isCXX11PODType(),
2191     // but with a lot of abstraction penalty stripped off.  This does
2192     // assume that these properties are set correctly even in C++98
2193     // mode; fortunately, that is true because we want to assign
2194     // consistently semantics to the type-traits intrinsics (or at
2195     // least as many of them as possible).
2196     return RD->isTrivial() && RD->isCXX11StandardLayout();
2197   }
2198
2199   llvm_unreachable("bad tail-padding use kind");
2200 }
2201
2202 static bool isMsLayout(const ASTContext &Context) {
2203   return Context.getTargetInfo().getCXXABI().isMicrosoft();
2204 }
2205
2206 // This section contains an implementation of struct layout that is, up to the
2207 // included tests, compatible with cl.exe (2013).  The layout produced is
2208 // significantly different than those produced by the Itanium ABI.  Here we note
2209 // the most important differences.
2210 //
2211 // * The alignment of bitfields in unions is ignored when computing the
2212 //   alignment of the union.
2213 // * The existence of zero-width bitfield that occurs after anything other than
2214 //   a non-zero length bitfield is ignored.
2215 // * There is no explicit primary base for the purposes of layout.  All bases
2216 //   with vfptrs are laid out first, followed by all bases without vfptrs.
2217 // * The Itanium equivalent vtable pointers are split into a vfptr (virtual
2218 //   function pointer) and a vbptr (virtual base pointer).  They can each be
2219 //   shared with a, non-virtual bases. These bases need not be the same.  vfptrs
2220 //   always occur at offset 0.  vbptrs can occur at an arbitrary offset and are
2221 //   placed after the lexicographically last non-virtual base.  This placement
2222 //   is always before fields but can be in the middle of the non-virtual bases
2223 //   due to the two-pass layout scheme for non-virtual-bases.
2224 // * Virtual bases sometimes require a 'vtordisp' field that is laid out before
2225 //   the virtual base and is used in conjunction with virtual overrides during
2226 //   construction and destruction.  This is always a 4 byte value and is used as
2227 //   an alternative to constructor vtables.
2228 // * vtordisps are allocated in a block of memory with size and alignment equal
2229 //   to the alignment of the completed structure (before applying __declspec(
2230 //   align())).  The vtordisp always occur at the end of the allocation block,
2231 //   immediately prior to the virtual base.
2232 // * vfptrs are injected after all bases and fields have been laid out.  In
2233 //   order to guarantee proper alignment of all fields, the vfptr injection
2234 //   pushes all bases and fields back by the alignment imposed by those bases
2235 //   and fields.  This can potentially add a significant amount of padding.
2236 //   vfptrs are always injected at offset 0.
2237 // * vbptrs are injected after all bases and fields have been laid out.  In
2238 //   order to guarantee proper alignment of all fields, the vfptr injection
2239 //   pushes all bases and fields back by the alignment imposed by those bases
2240 //   and fields.  This can potentially add a significant amount of padding.
2241 //   vbptrs are injected immediately after the last non-virtual base as
2242 //   lexicographically ordered in the code.  If this site isn't pointer aligned
2243 //   the vbptr is placed at the next properly aligned location.  Enough padding
2244 //   is added to guarantee a fit.
2245 // * The last zero sized non-virtual base can be placed at the end of the
2246 //   struct (potentially aliasing another object), or may alias with the first
2247 //   field, even if they are of the same type.
2248 // * The last zero size virtual base may be placed at the end of the struct
2249 //   potentially aliasing another object.
2250 // * The ABI attempts to avoid aliasing of zero sized bases by adding padding
2251 //   between bases or vbases with specific properties.  The criteria for
2252 //   additional padding between two bases is that the first base is zero sized
2253 //   or ends with a zero sized subobject and the second base is zero sized or
2254 //   trails with a zero sized base or field (sharing of vfptrs can reorder the
2255 //   layout of the so the leading base is not always the first one declared).
2256 //   This rule does take into account fields that are not records, so padding
2257 //   will occur even if the last field is, e.g. an int. The padding added for
2258 //   bases is 1 byte.  The padding added between vbases depends on the alignment
2259 //   of the object but is at least 4 bytes (in both 32 and 64 bit modes).
2260 // * There is no concept of non-virtual alignment, non-virtual alignment and
2261 //   alignment are always identical.
2262 // * There is a distinction between alignment and required alignment.
2263 //   __declspec(align) changes the required alignment of a struct.  This
2264 //   alignment is _always_ obeyed, even in the presence of #pragma pack. A
2265 //   record inherits required alignment from all of its fields and bases.
2266 // * __declspec(align) on bitfields has the effect of changing the bitfield's
2267 //   alignment instead of its required alignment.  This is the only known way
2268 //   to make the alignment of a struct bigger than 8.  Interestingly enough
2269 //   this alignment is also immune to the effects of #pragma pack and can be
2270 //   used to create structures with large alignment under #pragma pack.
2271 //   However, because it does not impact required alignment, such a structure,
2272 //   when used as a field or base, will not be aligned if #pragma pack is
2273 //   still active at the time of use.
2274 //
2275 // Known incompatibilities:
2276 // * all: #pragma pack between fields in a record
2277 // * 2010 and back: If the last field in a record is a bitfield, every object
2278 //   laid out after the record will have extra padding inserted before it.  The
2279 //   extra padding will have size equal to the size of the storage class of the
2280 //   bitfield.  0 sized bitfields don't exhibit this behavior and the extra
2281 //   padding can be avoided by adding a 0 sized bitfield after the non-zero-
2282 //   sized bitfield.
2283 // * 2012 and back: In 64-bit mode, if the alignment of a record is 16 or
2284 //   greater due to __declspec(align()) then a second layout phase occurs after
2285 //   The locations of the vf and vb pointers are known.  This layout phase
2286 //   suffers from the "last field is a bitfield" bug in 2010 and results in
2287 //   _every_ field getting padding put in front of it, potentially including the
2288 //   vfptr, leaving the vfprt at a non-zero location which results in a fault if
2289 //   anything tries to read the vftbl.  The second layout phase also treats
2290 //   bitfields as separate entities and gives them each storage rather than
2291 //   packing them.  Additionally, because this phase appears to perform a
2292 //   (an unstable) sort on the members before laying them out and because merged
2293 //   bitfields have the same address, the bitfields end up in whatever order
2294 //   the sort left them in, a behavior we could never hope to replicate.
2295
2296 namespace {
2297 struct MicrosoftRecordLayoutBuilder {
2298   struct ElementInfo {
2299     CharUnits Size;
2300     CharUnits Alignment;
2301   };
2302   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> BaseOffsetsMapTy;
2303   MicrosoftRecordLayoutBuilder(const ASTContext &Context) : Context(Context) {}
2304 private:
2305   MicrosoftRecordLayoutBuilder(const MicrosoftRecordLayoutBuilder &) = delete;
2306   void operator=(const MicrosoftRecordLayoutBuilder &) = delete;
2307 public:
2308   void layout(const RecordDecl *RD);
2309   void cxxLayout(const CXXRecordDecl *RD);
2310   /// Initializes size and alignment and honors some flags.
2311   void initializeLayout(const RecordDecl *RD);
2312   /// Initialized C++ layout, compute alignment and virtual alignment and
2313   /// existence of vfptrs and vbptrs.  Alignment is needed before the vfptr is
2314   /// laid out.
2315   void initializeCXXLayout(const CXXRecordDecl *RD);
2316   void layoutNonVirtualBases(const CXXRecordDecl *RD);
2317   void layoutNonVirtualBase(const CXXRecordDecl *RD,
2318                             const CXXRecordDecl *BaseDecl,
2319                             const ASTRecordLayout &BaseLayout,
2320                             const ASTRecordLayout *&PreviousBaseLayout);
2321   void injectVFPtr(const CXXRecordDecl *RD);
2322   void injectVBPtr(const CXXRecordDecl *RD);
2323   /// Lays out the fields of the record.  Also rounds size up to
2324   /// alignment.
2325   void layoutFields(const RecordDecl *RD);
2326   void layoutField(const FieldDecl *FD);
2327   void layoutBitField(const FieldDecl *FD);
2328   /// Lays out a single zero-width bit-field in the record and handles
2329   /// special cases associated with zero-width bit-fields.
2330   void layoutZeroWidthBitField(const FieldDecl *FD);
2331   void layoutVirtualBases(const CXXRecordDecl *RD);
2332   void finalizeLayout(const RecordDecl *RD);
2333   /// Gets the size and alignment of a base taking pragma pack and
2334   /// __declspec(align) into account.
2335   ElementInfo getAdjustedElementInfo(const ASTRecordLayout &Layout);
2336   /// Gets the size and alignment of a field taking pragma  pack and
2337   /// __declspec(align) into account.  It also updates RequiredAlignment as a
2338   /// side effect because it is most convenient to do so here.
2339   ElementInfo getAdjustedElementInfo(const FieldDecl *FD);
2340   /// Places a field at an offset in CharUnits.
2341   void placeFieldAtOffset(CharUnits FieldOffset) {
2342     FieldOffsets.push_back(Context.toBits(FieldOffset));
2343   }
2344   /// Places a bitfield at a bit offset.
2345   void placeFieldAtBitOffset(uint64_t FieldOffset) {
2346     FieldOffsets.push_back(FieldOffset);
2347   }
2348   /// Compute the set of virtual bases for which vtordisps are required.
2349   void computeVtorDispSet(
2350       llvm::SmallPtrSetImpl<const CXXRecordDecl *> &HasVtorDispSet,
2351       const CXXRecordDecl *RD) const;
2352   const ASTContext &Context;
2353   /// The size of the record being laid out.
2354   CharUnits Size;
2355   /// The non-virtual size of the record layout.
2356   CharUnits NonVirtualSize;
2357   /// The data size of the record layout.
2358   CharUnits DataSize;
2359   /// The current alignment of the record layout.
2360   CharUnits Alignment;
2361   /// The maximum allowed field alignment. This is set by #pragma pack.
2362   CharUnits MaxFieldAlignment;
2363   /// The alignment that this record must obey.  This is imposed by
2364   /// __declspec(align()) on the record itself or one of its fields or bases.
2365   CharUnits RequiredAlignment;
2366   /// The size of the allocation of the currently active bitfield.
2367   /// This value isn't meaningful unless LastFieldIsNonZeroWidthBitfield
2368   /// is true.
2369   CharUnits CurrentBitfieldSize;
2370   /// Offset to the virtual base table pointer (if one exists).
2371   CharUnits VBPtrOffset;
2372   /// Minimum record size possible.
2373   CharUnits MinEmptyStructSize;
2374   /// The size and alignment info of a pointer.
2375   ElementInfo PointerInfo;
2376   /// The primary base class (if one exists).
2377   const CXXRecordDecl *PrimaryBase;
2378   /// The class we share our vb-pointer with.
2379   const CXXRecordDecl *SharedVBPtrBase;
2380   /// The collection of field offsets.
2381   SmallVector<uint64_t, 16> FieldOffsets;
2382   /// Base classes and their offsets in the record.
2383   BaseOffsetsMapTy Bases;
2384   /// virtual base classes and their offsets in the record.
2385   ASTRecordLayout::VBaseOffsetsMapTy VBases;
2386   /// The number of remaining bits in our last bitfield allocation.
2387   /// This value isn't meaningful unless LastFieldIsNonZeroWidthBitfield is
2388   /// true.
2389   unsigned RemainingBitsInField;
2390   bool IsUnion : 1;
2391   /// True if the last field laid out was a bitfield and was not 0
2392   /// width.
2393   bool LastFieldIsNonZeroWidthBitfield : 1;
2394   /// True if the class has its own vftable pointer.
2395   bool HasOwnVFPtr : 1;
2396   /// True if the class has a vbtable pointer.
2397   bool HasVBPtr : 1;
2398   /// True if the last sub-object within the type is zero sized or the
2399   /// object itself is zero sized.  This *does not* count members that are not
2400   /// records.  Only used for MS-ABI.
2401   bool EndsWithZeroSizedObject : 1;
2402   /// True if this class is zero sized or first base is zero sized or
2403   /// has this property.  Only used for MS-ABI.
2404   bool LeadsWithZeroSizedBase : 1;
2405
2406   /// True if the external AST source provided a layout for this record.
2407   bool UseExternalLayout : 1;
2408
2409   /// The layout provided by the external AST source. Only active if
2410   /// UseExternalLayout is true.
2411   ExternalLayout External;
2412 };
2413 } // namespace
2414
2415 MicrosoftRecordLayoutBuilder::ElementInfo
2416 MicrosoftRecordLayoutBuilder::getAdjustedElementInfo(
2417     const ASTRecordLayout &Layout) {
2418   ElementInfo Info;
2419   Info.Alignment = Layout.getAlignment();
2420   // Respect pragma pack.
2421   if (!MaxFieldAlignment.isZero())
2422     Info.Alignment = std::min(Info.Alignment, MaxFieldAlignment);
2423   // Track zero-sized subobjects here where it's already available.
2424   EndsWithZeroSizedObject = Layout.endsWithZeroSizedObject();
2425   // Respect required alignment, this is necessary because we may have adjusted
2426   // the alignment in the case of pragam pack.  Note that the required alignment
2427   // doesn't actually apply to the struct alignment at this point.
2428   Alignment = std::max(Alignment, Info.Alignment);
2429   RequiredAlignment = std::max(RequiredAlignment, Layout.getRequiredAlignment());
2430   Info.Alignment = std::max(Info.Alignment, Layout.getRequiredAlignment());
2431   Info.Size = Layout.getNonVirtualSize();
2432   return Info;
2433 }
2434
2435 MicrosoftRecordLayoutBuilder::ElementInfo
2436 MicrosoftRecordLayoutBuilder::getAdjustedElementInfo(
2437     const FieldDecl *FD) {
2438   // Get the alignment of the field type's natural alignment, ignore any
2439   // alignment attributes.
2440   ElementInfo Info;
2441   std::tie(Info.Size, Info.Alignment) =
2442       Context.getTypeInfoInChars(FD->getType()->getUnqualifiedDesugaredType());
2443   // Respect align attributes on the field.
2444   CharUnits FieldRequiredAlignment =
2445       Context.toCharUnitsFromBits(FD->getMaxAlignment());
2446   // Respect align attributes on the type.
2447   if (Context.isAlignmentRequired(FD->getType()))
2448     FieldRequiredAlignment = std::max(
2449         Context.getTypeAlignInChars(FD->getType()), FieldRequiredAlignment);
2450   // Respect attributes applied to subobjects of the field.
2451   if (FD->isBitField())
2452     // For some reason __declspec align impacts alignment rather than required
2453     // alignment when it is applied to bitfields.
2454     Info.Alignment = std::max(Info.Alignment, FieldRequiredAlignment);
2455   else {
2456     if (auto RT =
2457             FD->getType()->getBaseElementTypeUnsafe()->getAs<RecordType>()) {
2458       auto const &Layout = Context.getASTRecordLayout(RT->getDecl());
2459       EndsWithZeroSizedObject = Layout.endsWithZeroSizedObject();
2460       FieldRequiredAlignment = std::max(FieldRequiredAlignment,
2461                                         Layout.getRequiredAlignment());
2462     }
2463     // Capture required alignment as a side-effect.
2464     RequiredAlignment = std::max(RequiredAlignment, FieldRequiredAlignment);
2465   }
2466   // Respect pragma pack, attribute pack and declspec align
2467   if (!MaxFieldAlignment.isZero())
2468     Info.Alignment = std::min(Info.Alignment, MaxFieldAlignment);
2469   if (FD->hasAttr<PackedAttr>())
2470     Info.Alignment = CharUnits::One();
2471   Info.Alignment = std::max(Info.Alignment, FieldRequiredAlignment);
2472   return Info;
2473 }
2474
2475 void MicrosoftRecordLayoutBuilder::layout(const RecordDecl *RD) {
2476   // For C record layout, zero-sized records always have size 4.
2477   MinEmptyStructSize = CharUnits::fromQuantity(4);
2478   initializeLayout(RD);
2479   layoutFields(RD);
2480   DataSize = Size = Size.alignTo(Alignment);
2481   RequiredAlignment = std::max(
2482       RequiredAlignment, Context.toCharUnitsFromBits(RD->getMaxAlignment()));
2483   finalizeLayout(RD);
2484 }
2485
2486 void MicrosoftRecordLayoutBuilder::cxxLayout(const CXXRecordDecl *RD) {
2487   // The C++ standard says that empty structs have size 1.
2488   MinEmptyStructSize = CharUnits::One();
2489   initializeLayout(RD);
2490   initializeCXXLayout(RD);
2491   layoutNonVirtualBases(RD);
2492   layoutFields(RD);
2493   injectVBPtr(RD);
2494   injectVFPtr(RD);
2495   if (HasOwnVFPtr || (HasVBPtr && !SharedVBPtrBase))
2496     Alignment = std::max(Alignment, PointerInfo.Alignment);
2497   auto RoundingAlignment = Alignment;
2498   if (!MaxFieldAlignment.isZero())
2499     RoundingAlignment = std::min(RoundingAlignment, MaxFieldAlignment);
2500   if (!UseExternalLayout)
2501     Size = Size.alignTo(RoundingAlignment);
2502   NonVirtualSize = Size;
2503   RequiredAlignment = std::max(
2504       RequiredAlignment, Context.toCharUnitsFromBits(RD->getMaxAlignment()));
2505   layoutVirtualBases(RD);
2506   finalizeLayout(RD);
2507 }
2508
2509 void MicrosoftRecordLayoutBuilder::initializeLayout(const RecordDecl *RD) {
2510   IsUnion = RD->isUnion();
2511   Size = CharUnits::Zero();
2512   Alignment = CharUnits::One();
2513   // In 64-bit mode we always perform an alignment step after laying out vbases.
2514   // In 32-bit mode we do not.  The check to see if we need to perform alignment
2515   // checks the RequiredAlignment field and performs alignment if it isn't 0.
2516   RequiredAlignment = Context.getTargetInfo().getTriple().isArch64Bit()
2517                           ? CharUnits::One()
2518                           : CharUnits::Zero();
2519   // Compute the maximum field alignment.
2520   MaxFieldAlignment = CharUnits::Zero();
2521   // Honor the default struct packing maximum alignment flag.
2522   if (unsigned DefaultMaxFieldAlignment = Context.getLangOpts().PackStruct)
2523       MaxFieldAlignment = CharUnits::fromQuantity(DefaultMaxFieldAlignment);
2524   // Honor the packing attribute.  The MS-ABI ignores pragma pack if its larger
2525   // than the pointer size.
2526   if (const MaxFieldAlignmentAttr *MFAA = RD->getAttr<MaxFieldAlignmentAttr>()){
2527     unsigned PackedAlignment = MFAA->getAlignment();
2528     if (PackedAlignment <= Context.getTargetInfo().getPointerWidth(0))
2529       MaxFieldAlignment = Context.toCharUnitsFromBits(PackedAlignment);
2530   }
2531   // Packed attribute forces max field alignment to be 1.
2532   if (RD->hasAttr<PackedAttr>())
2533     MaxFieldAlignment = CharUnits::One();
2534
2535   // Try to respect the external layout if present.
2536   UseExternalLayout = false;
2537   if (ExternalASTSource *Source = Context.getExternalSource())
2538     UseExternalLayout = Source->layoutRecordType(
2539         RD, External.Size, External.Align, External.FieldOffsets,
2540         External.BaseOffsets, External.VirtualBaseOffsets);
2541 }
2542
2543 void
2544 MicrosoftRecordLayoutBuilder::initializeCXXLayout(const CXXRecordDecl *RD) {
2545   EndsWithZeroSizedObject = false;
2546   LeadsWithZeroSizedBase = false;
2547   HasOwnVFPtr = false;
2548   HasVBPtr = false;
2549   PrimaryBase = nullptr;
2550   SharedVBPtrBase = nullptr;
2551   // Calculate pointer size and alignment.  These are used for vfptr and vbprt
2552   // injection.
2553   PointerInfo.Size =
2554       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
2555   PointerInfo.Alignment =
2556       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerAlign(0));
2557   // Respect pragma pack.
2558   if (!MaxFieldAlignment.isZero())
2559     PointerInfo.Alignment = std::min(PointerInfo.Alignment, MaxFieldAlignment);
2560 }
2561
2562 void
2563 MicrosoftRecordLayoutBuilder::layoutNonVirtualBases(const CXXRecordDecl *RD) {
2564   // The MS-ABI lays out all bases that contain leading vfptrs before it lays
2565   // out any bases that do not contain vfptrs.  We implement this as two passes
2566   // over the bases.  This approach guarantees that the primary base is laid out
2567   // first.  We use these passes to calculate some additional aggregated
2568   // information about the bases, such as required alignment and the presence of
2569   // zero sized members.
2570   const ASTRecordLayout *PreviousBaseLayout = nullptr;
2571   // Iterate through the bases and lay out the non-virtual ones.
2572   for (const CXXBaseSpecifier &Base : RD->bases()) {
2573     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2574     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2575     // Mark and skip virtual bases.
2576     if (Base.isVirtual()) {
2577       HasVBPtr = true;
2578       continue;
2579     }
2580     // Check for a base to share a VBPtr with.
2581     if (!SharedVBPtrBase && BaseLayout.hasVBPtr()) {
2582       SharedVBPtrBase = BaseDecl;
2583       HasVBPtr = true;
2584     }
2585     // Only lay out bases with extendable VFPtrs on the first pass.
2586     if (!BaseLayout.hasExtendableVFPtr())
2587       continue;
2588     // If we don't have a primary base, this one qualifies.
2589     if (!PrimaryBase) {
2590       PrimaryBase = BaseDecl;
2591       LeadsWithZeroSizedBase = BaseLayout.leadsWithZeroSizedBase();
2592     }
2593     // Lay out the base.
2594     layoutNonVirtualBase(RD, BaseDecl, BaseLayout, PreviousBaseLayout);
2595   }
2596   // Figure out if we need a fresh VFPtr for this class.
2597   if (!PrimaryBase && RD->isDynamicClass())
2598     for (CXXRecordDecl::method_iterator i = RD->method_begin(),
2599                                         e = RD->method_end();
2600          !HasOwnVFPtr && i != e; ++i)
2601       HasOwnVFPtr = i->isVirtual() && i->size_overridden_methods() == 0;
2602   // If we don't have a primary base then we have a leading object that could
2603   // itself lead with a zero-sized object, something we track.
2604   bool CheckLeadingLayout = !PrimaryBase;
2605   // Iterate through the bases and lay out the non-virtual ones.
2606   for (const CXXBaseSpecifier &Base : RD->bases()) {
2607     if (Base.isVirtual())
2608       continue;
2609     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2610     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2611     // Only lay out bases without extendable VFPtrs on the second pass.
2612     if (BaseLayout.hasExtendableVFPtr()) {
2613       VBPtrOffset = Bases[BaseDecl] + BaseLayout.getNonVirtualSize();
2614       continue;
2615     }
2616     // If this is the first layout, check to see if it leads with a zero sized
2617     // object.  If it does, so do we.
2618     if (CheckLeadingLayout) {
2619       CheckLeadingLayout = false;
2620       LeadsWithZeroSizedBase = BaseLayout.leadsWithZeroSizedBase();
2621     }
2622     // Lay out the base.
2623     layoutNonVirtualBase(RD, BaseDecl, BaseLayout, PreviousBaseLayout);
2624     VBPtrOffset = Bases[BaseDecl] + BaseLayout.getNonVirtualSize();
2625   }
2626   // Set our VBPtroffset if we know it at this point.
2627   if (!HasVBPtr)
2628     VBPtrOffset = CharUnits::fromQuantity(-1);
2629   else if (SharedVBPtrBase) {
2630     const ASTRecordLayout &Layout = Context.getASTRecordLayout(SharedVBPtrBase);
2631     VBPtrOffset = Bases[SharedVBPtrBase] + Layout.getVBPtrOffset();
2632   }
2633 }
2634
2635 static bool recordUsesEBO(const RecordDecl *RD) {
2636   if (!isa<CXXRecordDecl>(RD))
2637     return false;
2638   if (RD->hasAttr<EmptyBasesAttr>())
2639     return true;
2640   if (auto *LVA = RD->getAttr<LayoutVersionAttr>())
2641     // TODO: Double check with the next version of MSVC.
2642     if (LVA->getVersion() <= LangOptions::MSVC2015)
2643       return false;
2644   // TODO: Some later version of MSVC will change the default behavior of the
2645   // compiler to enable EBO by default.  When this happens, we will need an
2646   // additional isCompatibleWithMSVC check.
2647   return false;
2648 }
2649
2650 void MicrosoftRecordLayoutBuilder::layoutNonVirtualBase(
2651     const CXXRecordDecl *RD,
2652     const CXXRecordDecl *BaseDecl,
2653     const ASTRecordLayout &BaseLayout,
2654     const ASTRecordLayout *&PreviousBaseLayout) {
2655   // Insert padding between two bases if the left first one is zero sized or
2656   // contains a zero sized subobject and the right is zero sized or one leads
2657   // with a zero sized base.
2658   bool MDCUsesEBO = recordUsesEBO(RD);
2659   if (PreviousBaseLayout && PreviousBaseLayout->endsWithZeroSizedObject() &&
2660       BaseLayout.leadsWithZeroSizedBase() && !MDCUsesEBO)
2661     Size++;
2662   ElementInfo Info = getAdjustedElementInfo(BaseLayout);
2663   CharUnits BaseOffset;
2664
2665   // Respect the external AST source base offset, if present.
2666   bool FoundBase = false;
2667   if (UseExternalLayout) {
2668     FoundBase = External.getExternalNVBaseOffset(BaseDecl, BaseOffset);
2669     if (FoundBase) {
2670       assert(BaseOffset >= Size && "base offset already allocated");
2671       Size = BaseOffset;
2672     }
2673   }
2674
2675   if (!FoundBase) {
2676     if (MDCUsesEBO && BaseDecl->isEmpty()) {
2677       assert(BaseLayout.getNonVirtualSize() == CharUnits::Zero());
2678       BaseOffset = CharUnits::Zero();
2679     } else {
2680       // Otherwise, lay the base out at the end of the MDC.
2681       BaseOffset = Size = Size.alignTo(Info.Alignment);
2682     }
2683   }
2684   Bases.insert(std::make_pair(BaseDecl, BaseOffset));
2685   Size += BaseLayout.getNonVirtualSize();
2686   PreviousBaseLayout = &BaseLayout;
2687 }
2688
2689 void MicrosoftRecordLayoutBuilder::layoutFields(const RecordDecl *RD) {
2690   LastFieldIsNonZeroWidthBitfield = false;
2691   for (const FieldDecl *Field : RD->fields())
2692     layoutField(Field);
2693 }
2694
2695 void MicrosoftRecordLayoutBuilder::layoutField(const FieldDecl *FD) {
2696   if (FD->isBitField()) {
2697     layoutBitField(FD);
2698     return;
2699   }
2700   LastFieldIsNonZeroWidthBitfield = false;
2701   ElementInfo Info = getAdjustedElementInfo(FD);
2702   Alignment = std::max(Alignment, Info.Alignment);
2703   CharUnits FieldOffset;
2704   if (UseExternalLayout)
2705     FieldOffset =
2706         Context.toCharUnitsFromBits(External.getExternalFieldOffset(FD));
2707   else if (IsUnion)
2708     FieldOffset = CharUnits::Zero();
2709   else
2710     FieldOffset = Size.alignTo(Info.Alignment);
2711   placeFieldAtOffset(FieldOffset);
2712   Size = std::max(Size, FieldOffset + Info.Size);
2713 }
2714
2715 void MicrosoftRecordLayoutBuilder::layoutBitField(const FieldDecl *FD) {
2716   unsigned Width = FD->getBitWidthValue(Context);
2717   if (Width == 0) {
2718     layoutZeroWidthBitField(FD);
2719     return;
2720   }
2721   ElementInfo Info = getAdjustedElementInfo(FD);
2722   // Clamp the bitfield to a containable size for the sake of being able
2723   // to lay them out.  Sema will throw an error.
2724   if (Width > Context.toBits(Info.Size))
2725     Width = Context.toBits(Info.Size);
2726   // Check to see if this bitfield fits into an existing allocation.  Note:
2727   // MSVC refuses to pack bitfields of formal types with different sizes
2728   // into the same allocation.
2729   if (!UseExternalLayout && !IsUnion && LastFieldIsNonZeroWidthBitfield &&
2730       CurrentBitfieldSize == Info.Size && Width <= RemainingBitsInField) {
2731     placeFieldAtBitOffset(Context.toBits(Size) - RemainingBitsInField);
2732     RemainingBitsInField -= Width;
2733     return;
2734   }
2735   LastFieldIsNonZeroWidthBitfield = true;
2736   CurrentBitfieldSize = Info.Size;
2737   if (UseExternalLayout) {
2738     auto FieldBitOffset = External.getExternalFieldOffset(FD);
2739     placeFieldAtBitOffset(FieldBitOffset);
2740     auto NewSize = Context.toCharUnitsFromBits(
2741         llvm::alignDown(FieldBitOffset, Context.toBits(Info.Alignment)) +
2742         Context.toBits(Info.Size));
2743     Size = std::max(Size, NewSize);
2744     Alignment = std::max(Alignment, Info.Alignment);
2745   } else if (IsUnion) {
2746     placeFieldAtOffset(CharUnits::Zero());
2747     Size = std::max(Size, Info.Size);
2748     // TODO: Add a Sema warning that MS ignores bitfield alignment in unions.
2749   } else {
2750     // Allocate a new block of memory and place the bitfield in it.
2751     CharUnits FieldOffset = Size.alignTo(Info.Alignment);
2752     placeFieldAtOffset(FieldOffset);
2753     Size = FieldOffset + Info.Size;
2754     Alignment = std::max(Alignment, Info.Alignment);
2755     RemainingBitsInField = Context.toBits(Info.Size) - Width;
2756   }
2757 }
2758
2759 void
2760 MicrosoftRecordLayoutBuilder::layoutZeroWidthBitField(const FieldDecl *FD) {
2761   // Zero-width bitfields are ignored unless they follow a non-zero-width
2762   // bitfield.
2763   if (!LastFieldIsNonZeroWidthBitfield) {
2764     placeFieldAtOffset(IsUnion ? CharUnits::Zero() : Size);
2765     // TODO: Add a Sema warning that MS ignores alignment for zero
2766     // sized bitfields that occur after zero-size bitfields or non-bitfields.
2767     return;
2768   }
2769   LastFieldIsNonZeroWidthBitfield = false;
2770   ElementInfo Info = getAdjustedElementInfo(FD);
2771   if (IsUnion) {
2772     placeFieldAtOffset(CharUnits::Zero());
2773     Size = std::max(Size, Info.Size);
2774     // TODO: Add a Sema warning that MS ignores bitfield alignment in unions.
2775   } else {
2776     // Round up the current record size to the field's alignment boundary.
2777     CharUnits FieldOffset = Size.alignTo(Info.Alignment);
2778     placeFieldAtOffset(FieldOffset);
2779     Size = FieldOffset;
2780     Alignment = std::max(Alignment, Info.Alignment);
2781   }
2782 }
2783
2784 void MicrosoftRecordLayoutBuilder::injectVBPtr(const CXXRecordDecl *RD) {
2785   if (!HasVBPtr || SharedVBPtrBase)
2786     return;
2787   // Inject the VBPointer at the injection site.
2788   CharUnits InjectionSite = VBPtrOffset;
2789   // But before we do, make sure it's properly aligned.
2790   VBPtrOffset = VBPtrOffset.alignTo(PointerInfo.Alignment);
2791   // Determine where the first field should be laid out after the vbptr.
2792   CharUnits FieldStart = VBPtrOffset + PointerInfo.Size;
2793   // Shift everything after the vbptr down, unless we're using an external
2794   // layout.
2795   if (UseExternalLayout) {
2796     // It is possible that there were no fields or bases located after vbptr,
2797     // so the size was not adjusted before.
2798     if (Size < FieldStart)
2799       Size = FieldStart;
2800     return;
2801   }
2802   // Make sure that the amount we push the fields back by is a multiple of the
2803   // alignment.
2804   CharUnits Offset = (FieldStart - InjectionSite)
2805                          .alignTo(std::max(RequiredAlignment, Alignment));
2806   Size += Offset;
2807   for (uint64_t &FieldOffset : FieldOffsets)
2808     FieldOffset += Context.toBits(Offset);
2809   for (BaseOffsetsMapTy::value_type &Base : Bases)
2810     if (Base.second >= InjectionSite)
2811       Base.second += Offset;
2812 }
2813
2814 void MicrosoftRecordLayoutBuilder::injectVFPtr(const CXXRecordDecl *RD) {
2815   if (!HasOwnVFPtr)
2816     return;
2817   // Make sure that the amount we push the struct back by is a multiple of the
2818   // alignment.
2819   CharUnits Offset =
2820       PointerInfo.Size.alignTo(std::max(RequiredAlignment, Alignment));
2821   // Push back the vbptr, but increase the size of the object and push back
2822   // regular fields by the offset only if not using external record layout.
2823   if (HasVBPtr)
2824     VBPtrOffset += Offset;
2825
2826   if (UseExternalLayout) {
2827     // The class may have no bases or fields, but still have a vfptr
2828     // (e.g. it's an interface class). The size was not correctly set before
2829     // in this case.
2830     if (FieldOffsets.empty() && Bases.empty())
2831       Size += Offset;
2832     return;
2833   }
2834
2835   Size += Offset;
2836
2837   // If we're using an external layout, the fields offsets have already
2838   // accounted for this adjustment.
2839   for (uint64_t &FieldOffset : FieldOffsets)
2840     FieldOffset += Context.toBits(Offset);
2841   for (BaseOffsetsMapTy::value_type &Base : Bases)
2842     Base.second += Offset;
2843 }
2844
2845 void MicrosoftRecordLayoutBuilder::layoutVirtualBases(const CXXRecordDecl *RD) {
2846   if (!HasVBPtr)
2847     return;
2848   // Vtordisps are always 4 bytes (even in 64-bit mode)
2849   CharUnits VtorDispSize = CharUnits::fromQuantity(4);
2850   CharUnits VtorDispAlignment = VtorDispSize;
2851   // vtordisps respect pragma pack.
2852   if (!MaxFieldAlignment.isZero())
2853     VtorDispAlignment = std::min(VtorDispAlignment, MaxFieldAlignment);
2854   // The alignment of the vtordisp is at least the required alignment of the
2855   // entire record.  This requirement may be present to support vtordisp
2856   // injection.
2857   for (const CXXBaseSpecifier &VBase : RD->vbases()) {
2858     const CXXRecordDecl *BaseDecl = VBase.getType()->getAsCXXRecordDecl();
2859     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2860     RequiredAlignment =
2861         std::max(RequiredAlignment, BaseLayout.getRequiredAlignment());
2862   }
2863   VtorDispAlignment = std::max(VtorDispAlignment, RequiredAlignment);
2864   // Compute the vtordisp set.
2865   llvm::SmallPtrSet<const CXXRecordDecl *, 2> HasVtorDispSet;
2866   computeVtorDispSet(HasVtorDispSet, RD);
2867   // Iterate through the virtual bases and lay them out.
2868   const ASTRecordLayout *PreviousBaseLayout = nullptr;
2869   for (const CXXBaseSpecifier &VBase : RD->vbases()) {
2870     const CXXRecordDecl *BaseDecl = VBase.getType()->getAsCXXRecordDecl();
2871     const ASTRecordLayout &BaseLayout = Context.getASTRecordLayout(BaseDecl);
2872     bool HasVtordisp = HasVtorDispSet.count(BaseDecl) > 0;
2873     // Insert padding between two bases if the left first one is zero sized or
2874     // contains a zero sized subobject and the right is zero sized or one leads
2875     // with a zero sized base.  The padding between virtual bases is 4
2876     // bytes (in both 32 and 64 bits modes) and always involves rounding up to
2877     // the required alignment, we don't know why.
2878     if ((PreviousBaseLayout && PreviousBaseLayout->endsWithZeroSizedObject() &&
2879          BaseLayout.leadsWithZeroSizedBase() && !recordUsesEBO(RD)) ||
2880         HasVtordisp) {
2881       Size = Size.alignTo(VtorDispAlignment) + VtorDispSize;
2882       Alignment = std::max(VtorDispAlignment, Alignment);
2883     }
2884     // Insert the virtual base.
2885     ElementInfo Info = getAdjustedElementInfo(BaseLayout);
2886     CharUnits BaseOffset;
2887
2888     // Respect the external AST source base offset, if present.
2889     if (UseExternalLayout) {
2890       if (!External.getExternalVBaseOffset(BaseDecl, BaseOffset))
2891         BaseOffset = Size;
2892     } else
2893       BaseOffset = Size.alignTo(Info.Alignment);
2894
2895     assert(BaseOffset >= Size && "base offset already allocated");
2896
2897     VBases.insert(std::make_pair(BaseDecl,
2898         ASTRecordLayout::VBaseInfo(BaseOffset, HasVtordisp)));
2899     Size = BaseOffset + BaseLayout.getNonVirtualSize();
2900     PreviousBaseLayout = &BaseLayout;
2901   }
2902 }
2903
2904 void MicrosoftRecordLayoutBuilder::finalizeLayout(const RecordDecl *RD) {
2905   // Respect required alignment.  Note that in 32-bit mode Required alignment
2906   // may be 0 and cause size not to be updated.
2907   DataSize = Size;
2908   if (!RequiredAlignment.isZero()) {
2909     Alignment = std::max(Alignment, RequiredAlignment);
2910     auto RoundingAlignment = Alignment;
2911     if (!MaxFieldAlignment.isZero())
2912       RoundingAlignment = std::min(RoundingAlignment, MaxFieldAlignment);
2913     RoundingAlignment = std::max(RoundingAlignment, RequiredAlignment);
2914     Size = Size.alignTo(RoundingAlignment);
2915   }
2916   if (Size.isZero()) {
2917     if (!recordUsesEBO(RD) || !cast<CXXRecordDecl>(RD)->isEmpty()) {
2918       EndsWithZeroSizedObject = true;
2919       LeadsWithZeroSizedBase = true;
2920     }
2921     // Zero-sized structures have size equal to their alignment if a
2922     // __declspec(align) came into play.
2923     if (RequiredAlignment >= MinEmptyStructSize)
2924       Size = Alignment;
2925     else
2926       Size = MinEmptyStructSize;
2927   }
2928
2929   if (UseExternalLayout) {
2930     Size = Context.toCharUnitsFromBits(External.Size);
2931     if (External.Align)
2932       Alignment = Context.toCharUnitsFromBits(External.Align);
2933   }
2934 }
2935
2936 // Recursively walks the non-virtual bases of a class and determines if any of
2937 // them are in the bases with overridden methods set.
2938 static bool
2939 RequiresVtordisp(const llvm::SmallPtrSetImpl<const CXXRecordDecl *> &
2940                      BasesWithOverriddenMethods,
2941                  const CXXRecordDecl *RD) {
2942   if (BasesWithOverriddenMethods.count(RD))
2943     return true;
2944   // If any of a virtual bases non-virtual bases (recursively) requires a
2945   // vtordisp than so does this virtual base.
2946   for (const CXXBaseSpecifier &Base : RD->bases())
2947     if (!Base.isVirtual() &&
2948         RequiresVtordisp(BasesWithOverriddenMethods,
2949                          Base.getType()->getAsCXXRecordDecl()))
2950       return true;
2951   return false;
2952 }
2953
2954 void MicrosoftRecordLayoutBuilder::computeVtorDispSet(
2955     llvm::SmallPtrSetImpl<const CXXRecordDecl *> &HasVtordispSet,
2956     const CXXRecordDecl *RD) const {
2957   // /vd2 or #pragma vtordisp(2): Always use vtordisps for virtual bases with
2958   // vftables.
2959   if (RD->getMSVtorDispMode() == MSVtorDispMode::ForVFTable) {
2960     for (const CXXBaseSpecifier &Base : RD->vbases()) {
2961       const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2962       const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
2963       if (Layout.hasExtendableVFPtr())
2964         HasVtordispSet.insert(BaseDecl);
2965     }
2966     return;
2967   }
2968
2969   // If any of our bases need a vtordisp for this type, so do we.  Check our
2970   // direct bases for vtordisp requirements.
2971   for (const CXXBaseSpecifier &Base : RD->bases()) {
2972     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
2973     const ASTRecordLayout &Layout = Context.getASTRecordLayout(BaseDecl);
2974     for (const auto &bi : Layout.getVBaseOffsetsMap())
2975       if (bi.second.hasVtorDisp())
2976         HasVtordispSet.insert(bi.first);
2977   }
2978   // We don't introduce any additional vtordisps if either:
2979   // * A user declared constructor or destructor aren't declared.
2980   // * #pragma vtordisp(0) or the /vd0 flag are in use.
2981   if ((!RD->hasUserDeclaredConstructor() && !RD->hasUserDeclaredDestructor()) ||
2982       RD->getMSVtorDispMode() == MSVtorDispMode::Never)
2983     return;
2984   // /vd1 or #pragma vtordisp(1): Try to guess based on whether we think it's
2985   // possible for a partially constructed object with virtual base overrides to
2986   // escape a non-trivial constructor.
2987   assert(RD->getMSVtorDispMode() == MSVtorDispMode::ForVBaseOverride);
2988   // Compute a set of base classes which define methods we override.  A virtual
2989   // base in this set will require a vtordisp.  A virtual base that transitively
2990   // contains one of these bases as a non-virtual base will also require a
2991   // vtordisp.
2992   llvm::SmallPtrSet<const CXXMethodDecl *, 8> Work;
2993   llvm::SmallPtrSet<const CXXRecordDecl *, 2> BasesWithOverriddenMethods;
2994   // Seed the working set with our non-destructor, non-pure virtual methods.
2995   for (const CXXMethodDecl *MD : RD->methods())
2996     if (MD->isVirtual() && !isa<CXXDestructorDecl>(MD) && !MD->isPure())
2997       Work.insert(MD);
2998   while (!Work.empty()) {
2999     const CXXMethodDecl *MD = *Work.begin();
3000     auto MethodRange = MD->overridden_methods();
3001     // If a virtual method has no-overrides it lives in its parent's vtable.
3002     if (MethodRange.begin() == MethodRange.end())
3003       BasesWithOverriddenMethods.insert(MD->getParent());
3004     else
3005       Work.insert(MethodRange.begin(), MethodRange.end());
3006     // We've finished processing this element, remove it from the working set.
3007     Work.erase(MD);
3008   }
3009   // For each of our virtual bases, check if it is in the set of overridden
3010   // bases or if it transitively contains a non-virtual base that is.
3011   for (const CXXBaseSpecifier &Base : RD->vbases()) {
3012     const CXXRecordDecl *BaseDecl = Base.getType()->getAsCXXRecordDecl();
3013     if (!HasVtordispSet.count(BaseDecl) &&
3014         RequiresVtordisp(BasesWithOverriddenMethods, BaseDecl))
3015       HasVtordispSet.insert(BaseDecl);
3016   }
3017 }
3018
3019 /// getASTRecordLayout - Get or compute information about the layout of the
3020 /// specified record (struct/union/class), which indicates its size and field
3021 /// position information.
3022 const ASTRecordLayout &
3023 ASTContext::getASTRecordLayout(const RecordDecl *D) const {
3024   // These asserts test different things.  A record has a definition
3025   // as soon as we begin to parse the definition.  That definition is
3026   // not a complete definition (which is what isDefinition() tests)
3027   // until we *finish* parsing the definition.
3028
3029   if (D->hasExternalLexicalStorage() && !D->getDefinition())
3030     getExternalSource()->CompleteType(const_cast<RecordDecl*>(D));
3031
3032   D = D->getDefinition();
3033   assert(D && "Cannot get layout of forward declarations!");
3034   assert(!D->isInvalidDecl() && "Cannot get layout of invalid decl!");
3035   assert(D->isCompleteDefinition() && "Cannot layout type before complete!");
3036
3037   // Look up this layout, if already laid out, return what we have.
3038   // Note that we can't save a reference to the entry because this function
3039   // is recursive.
3040   const ASTRecordLayout *Entry = ASTRecordLayouts[D];
3041   if (Entry) return *Entry;
3042
3043   const ASTRecordLayout *NewEntry = nullptr;
3044
3045   if (isMsLayout(*this)) {
3046     MicrosoftRecordLayoutBuilder Builder(*this);
3047     if (const auto *RD = dyn_cast<CXXRecordDecl>(D)) {
3048       Builder.cxxLayout(RD);
3049       NewEntry = new (*this) ASTRecordLayout(
3050           *this, Builder.Size, Builder.Alignment, Builder.Alignment,
3051           Builder.RequiredAlignment,
3052           Builder.HasOwnVFPtr, Builder.HasOwnVFPtr || Builder.PrimaryBase,
3053           Builder.VBPtrOffset, Builder.DataSize, Builder.FieldOffsets,
3054           Builder.NonVirtualSize, Builder.Alignment, CharUnits::Zero(),
3055           Builder.PrimaryBase, false, Builder.SharedVBPtrBase,
3056           Builder.EndsWithZeroSizedObject, Builder.LeadsWithZeroSizedBase,
3057           Builder.Bases, Builder.VBases);
3058     } else {
3059       Builder.layout(D);
3060       NewEntry = new (*this) ASTRecordLayout(
3061           *this, Builder.Size, Builder.Alignment, Builder.Alignment,
3062           Builder.RequiredAlignment,
3063           Builder.Size, Builder.FieldOffsets);
3064     }
3065   } else {
3066     if (const auto *RD = dyn_cast<CXXRecordDecl>(D)) {
3067       EmptySubobjectMap EmptySubobjects(*this, RD);
3068       ItaniumRecordLayoutBuilder Builder(*this, &EmptySubobjects);
3069       Builder.Layout(RD);
3070
3071       // In certain situations, we are allowed to lay out objects in the
3072       // tail-padding of base classes.  This is ABI-dependent.
3073       // FIXME: this should be stored in the record layout.
3074       bool skipTailPadding =
3075           mustSkipTailPadding(getTargetInfo().getCXXABI(), RD);
3076
3077       // FIXME: This should be done in FinalizeLayout.
3078       CharUnits DataSize =
3079           skipTailPadding ? Builder.getSize() : Builder.getDataSize();
3080       CharUnits NonVirtualSize =
3081           skipTailPadding ? DataSize : Builder.NonVirtualSize;
3082       NewEntry = new (*this) ASTRecordLayout(
3083           *this, Builder.getSize(), Builder.Alignment, Builder.UnadjustedAlignment,
3084           /*RequiredAlignment : used by MS-ABI)*/
3085           Builder.Alignment, Builder.HasOwnVFPtr, RD->isDynamicClass(),
3086           CharUnits::fromQuantity(-1), DataSize, Builder.FieldOffsets,
3087           NonVirtualSize, Builder.NonVirtualAlignment,
3088           EmptySubobjects.SizeOfLargestEmptySubobject, Builder.PrimaryBase,
3089           Builder.PrimaryBaseIsVirtual, nullptr, false, false, Builder.Bases,
3090           Builder.VBases);
3091     } else {
3092       ItaniumRecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/nullptr);
3093       Builder.Layout(D);
3094
3095       NewEntry = new (*this) ASTRecordLayout(
3096           *this, Builder.getSize(), Builder.Alignment, Builder.UnadjustedAlignment,
3097           /*RequiredAlignment : used by MS-ABI)*/
3098           Builder.Alignment, Builder.getSize(), Builder.FieldOffsets);
3099     }
3100   }
3101
3102   ASTRecordLayouts[D] = NewEntry;
3103
3104   if (getLangOpts().DumpRecordLayouts) {
3105     llvm::outs() << "\n*** Dumping AST Record Layout\n";
3106     DumpRecordLayout(D, llvm::outs(), getLangOpts().DumpRecordLayoutsSimple);
3107   }
3108
3109   return *NewEntry;
3110 }
3111
3112 const CXXMethodDecl *ASTContext::getCurrentKeyFunction(const CXXRecordDecl *RD) {
3113   if (!getTargetInfo().getCXXABI().hasKeyFunctions())
3114     return nullptr;
3115
3116   assert(RD->getDefinition() && "Cannot get key function for forward decl!");
3117   RD = RD->getDefinition();
3118
3119   // Beware:
3120   //  1) computing the key function might trigger deserialization, which might
3121   //     invalidate iterators into KeyFunctions
3122   //  2) 'get' on the LazyDeclPtr might also trigger deserialization and
3123   //     invalidate the LazyDeclPtr within the map itself
3124   LazyDeclPtr Entry = KeyFunctions[RD];
3125   const Decl *Result =
3126       Entry ? Entry.get(getExternalSource()) : computeKeyFunction(*this, RD);
3127
3128   // Store it back if it changed.
3129   if (Entry.isOffset() || Entry.isValid() != bool(Result))
3130     KeyFunctions[RD] = const_cast<Decl*>(Result);
3131
3132   return cast_or_null<CXXMethodDecl>(Result);
3133 }
3134
3135 void ASTContext::setNonKeyFunction(const CXXMethodDecl *Method) {
3136   assert(Method == Method->getFirstDecl() &&
3137          "not working with method declaration from class definition");
3138
3139   // Look up the cache entry.  Since we're working with the first
3140   // declaration, its parent must be the class definition, which is
3141   // the correct key for the KeyFunctions hash.
3142   const auto &Map = KeyFunctions;
3143   auto I = Map.find(Method->getParent());
3144
3145   // If it's not cached, there's nothing to do.
3146   if (I == Map.end()) return;
3147
3148   // If it is cached, check whether it's the target method, and if so,
3149   // remove it from the cache. Note, the call to 'get' might invalidate
3150   // the iterator and the LazyDeclPtr object within the map.
3151   LazyDeclPtr Ptr = I->second;
3152   if (Ptr.get(getExternalSource()) == Method) {
3153     // FIXME: remember that we did this for module / chained PCH state?
3154     KeyFunctions.erase(Method->getParent());
3155   }
3156 }
3157
3158 static uint64_t getFieldOffset(const ASTContext &C, const FieldDecl *FD) {
3159   const ASTRecordLayout &Layout = C.getASTRecordLayout(FD->getParent());
3160   return Layout.getFieldOffset(FD->getFieldIndex());
3161 }
3162
3163 uint64_t ASTContext::getFieldOffset(const ValueDecl *VD) const {
3164   uint64_t OffsetInBits;
3165   if (const FieldDecl *FD = dyn_cast<FieldDecl>(VD)) {
3166     OffsetInBits = ::getFieldOffset(*this, FD);
3167   } else {
3168     const IndirectFieldDecl *IFD = cast<IndirectFieldDecl>(VD);
3169
3170     OffsetInBits = 0;
3171     for (const NamedDecl *ND : IFD->chain())
3172       OffsetInBits += ::getFieldOffset(*this, cast<FieldDecl>(ND));
3173   }
3174
3175   return OffsetInBits;
3176 }
3177
3178 uint64_t ASTContext::lookupFieldBitOffset(const ObjCInterfaceDecl *OID,
3179                                           const ObjCImplementationDecl *ID,
3180                                           const ObjCIvarDecl *Ivar) const {
3181   const ObjCInterfaceDecl *Container = Ivar->getContainingInterface();
3182
3183   // FIXME: We should eliminate the need to have ObjCImplementationDecl passed
3184   // in here; it should never be necessary because that should be the lexical
3185   // decl context for the ivar.
3186
3187   // If we know have an implementation (and the ivar is in it) then
3188   // look up in the implementation layout.
3189   const ASTRecordLayout *RL;
3190   if (ID && declaresSameEntity(ID->getClassInterface(), Container))
3191     RL = &getASTObjCImplementationLayout(ID);
3192   else
3193     RL = &getASTObjCInterfaceLayout(Container);
3194
3195   // Compute field index.
3196   //
3197   // FIXME: The index here is closely tied to how ASTContext::getObjCLayout is
3198   // implemented. This should be fixed to get the information from the layout
3199   // directly.
3200   unsigned Index = 0;
3201
3202   for (const ObjCIvarDecl *IVD = Container->all_declared_ivar_begin();
3203        IVD; IVD = IVD->getNextIvar()) {
3204     if (Ivar == IVD)
3205       break;
3206     ++Index;
3207   }
3208   assert(Index < RL->getFieldCount() && "Ivar is not inside record layout!");
3209
3210   return RL->getFieldOffset(Index);
3211 }
3212
3213 /// getObjCLayout - Get or compute information about the layout of the
3214 /// given interface.
3215 ///
3216 /// \param Impl - If given, also include the layout of the interface's
3217 /// implementation. This may differ by including synthesized ivars.
3218 const ASTRecordLayout &
3219 ASTContext::getObjCLayout(const ObjCInterfaceDecl *D,
3220                           const ObjCImplementationDecl *Impl) const {
3221   // Retrieve the definition
3222   if (D->hasExternalLexicalStorage() && !D->getDefinition())
3223     getExternalSource()->CompleteType(const_cast<ObjCInterfaceDecl*>(D));
3224   D = D->getDefinition();
3225   assert(D && D->isThisDeclarationADefinition() && "Invalid interface decl!");
3226
3227   // Look up this layout, if already laid out, return what we have.
3228   const ObjCContainerDecl *Key =
3229     Impl ? (const ObjCContainerDecl*) Impl : (const ObjCContainerDecl*) D;
3230   if (const ASTRecordLayout *Entry = ObjCLayouts[Key])
3231     return *Entry;
3232
3233   // Add in synthesized ivar count if laying out an implementation.
3234   if (Impl) {
3235     unsigned SynthCount = CountNonClassIvars(D);
3236     // If there aren't any synthesized ivars then reuse the interface
3237     // entry. Note we can't cache this because we simply free all
3238     // entries later; however we shouldn't look up implementations
3239     // frequently.
3240     if (SynthCount == 0)
3241       return getObjCLayout(D, nullptr);
3242   }
3243
3244   ItaniumRecordLayoutBuilder Builder(*this, /*EmptySubobjects=*/nullptr);
3245   Builder.Layout(D);
3246
3247   const ASTRecordLayout *NewEntry =
3248     new (*this) ASTRecordLayout(*this, Builder.getSize(),
3249                                 Builder.Alignment,
3250                                 Builder.UnadjustedAlignment,
3251                                 /*RequiredAlignment : used by MS-ABI)*/
3252                                 Builder.Alignment,
3253                                 Builder.getDataSize(),
3254                                 Builder.FieldOffsets);
3255
3256   ObjCLayouts[Key] = NewEntry;
3257
3258   return *NewEntry;
3259 }
3260
3261 static void PrintOffset(raw_ostream &OS,
3262                         CharUnits Offset, unsigned IndentLevel) {
3263   OS << llvm::format("%10" PRId64 " | ", (int64_t)Offset.getQuantity());
3264   OS.indent(IndentLevel * 2);
3265 }
3266
3267 static void PrintBitFieldOffset(raw_ostream &OS, CharUnits Offset,
3268                                 unsigned Begin, unsigned Width,
3269                                 unsigned IndentLevel) {
3270   llvm::SmallString<10> Buffer;
3271   {
3272     llvm::raw_svector_ostream BufferOS(Buffer);
3273     BufferOS << Offset.getQuantity() << ':';
3274     if (Width == 0) {
3275       BufferOS << '-';
3276     } else {
3277       BufferOS << Begin << '-' << (Begin + Width - 1);
3278     }
3279   }
3280
3281   OS << llvm::right_justify(Buffer, 10) << " | ";
3282   OS.indent(IndentLevel * 2);
3283 }
3284
3285 static void PrintIndentNoOffset(raw_ostream &OS, unsigned IndentLevel) {
3286   OS << "           | ";
3287   OS.indent(IndentLevel * 2);
3288 }
3289
3290 static void DumpRecordLayout(raw_ostream &OS, const RecordDecl *RD,
3291                              const ASTContext &C,
3292                              CharUnits Offset,
3293                              unsigned IndentLevel,
3294                              const char* Description,
3295                              bool PrintSizeInfo,
3296                              bool IncludeVirtualBases) {
3297   const ASTRecordLayout &Layout = C.getASTRecordLayout(RD);
3298   auto CXXRD = dyn_cast<CXXRecordDecl>(RD);
3299
3300   PrintOffset(OS, Offset, IndentLevel);
3301   OS << C.getTypeDeclType(const_cast<RecordDecl*>(RD)).getAsString();
3302   if (Description)
3303     OS << ' ' << Description;
3304   if (CXXRD && CXXRD->isEmpty())
3305     OS << " (empty)";
3306   OS << '\n';
3307
3308   IndentLevel++;
3309
3310   // Dump bases.
3311   if (CXXRD) {
3312     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
3313     bool HasOwnVFPtr = Layout.hasOwnVFPtr();
3314     bool HasOwnVBPtr = Layout.hasOwnVBPtr();
3315
3316     // Vtable pointer.
3317     if (CXXRD->isDynamicClass() && !PrimaryBase && !isMsLayout(C)) {
3318       PrintOffset(OS, Offset, IndentLevel);
3319       OS << '(' << *RD << " vtable pointer)\n";
3320     } else if (HasOwnVFPtr) {
3321       PrintOffset(OS, Offset, IndentLevel);
3322       // vfptr (for Microsoft C++ ABI)
3323       OS << '(' << *RD << " vftable pointer)\n";
3324     }
3325
3326     // Collect nvbases.
3327     SmallVector<const CXXRecordDecl *, 4> Bases;
3328     for (const CXXBaseSpecifier &Base : CXXRD->bases()) {
3329       assert(!Base.getType()->isDependentType() &&
3330              "Cannot layout class with dependent bases.");
3331       if (!Base.isVirtual())
3332         Bases.push_back(Base.getType()->getAsCXXRecordDecl());
3333     }
3334
3335     // Sort nvbases by offset.
3336     llvm::stable_sort(
3337         Bases, [&](const CXXRecordDecl *L, const CXXRecordDecl *R) {
3338           return Layout.getBaseClassOffset(L) < Layout.getBaseClassOffset(R);
3339         });
3340
3341     // Dump (non-virtual) bases
3342     for (const CXXRecordDecl *Base : Bases) {
3343       CharUnits BaseOffset = Offset + Layout.getBaseClassOffset(Base);
3344       DumpRecordLayout(OS, Base, C, BaseOffset, IndentLevel,
3345                        Base == PrimaryBase ? "(primary base)" : "(base)",
3346                        /*PrintSizeInfo=*/false,
3347                        /*IncludeVirtualBases=*/false);
3348     }
3349
3350     // vbptr (for Microsoft C++ ABI)
3351     if (HasOwnVBPtr) {
3352       PrintOffset(OS, Offset + Layout.getVBPtrOffset(), IndentLevel);
3353       OS << '(' << *RD << " vbtable pointer)\n";
3354     }
3355   }
3356
3357   // Dump fields.
3358   uint64_t FieldNo = 0;
3359   for (RecordDecl::field_iterator I = RD->field_begin(),
3360          E = RD->field_end(); I != E; ++I, ++FieldNo) {
3361     const FieldDecl &Field = **I;
3362     uint64_t LocalFieldOffsetInBits = Layout.getFieldOffset(FieldNo);
3363     CharUnits FieldOffset =
3364       Offset + C.toCharUnitsFromBits(LocalFieldOffsetInBits);
3365
3366     // Recursively dump fields of record type.
3367     if (auto RT = Field.getType()->getAs<RecordType>()) {
3368       DumpRecordLayout(OS, RT->getDecl(), C, FieldOffset, IndentLevel,
3369                        Field.getName().data(),
3370                        /*PrintSizeInfo=*/false,
3371                        /*IncludeVirtualBases=*/true);
3372       continue;
3373     }
3374
3375     if (Field.isBitField()) {
3376       uint64_t LocalFieldByteOffsetInBits = C.toBits(FieldOffset - Offset);
3377       unsigned Begin = LocalFieldOffsetInBits - LocalFieldByteOffsetInBits;
3378       unsigned Width = Field.getBitWidthValue(C);
3379       PrintBitFieldOffset(OS, FieldOffset, Begin, Width, IndentLevel);
3380     } else {
3381       PrintOffset(OS, FieldOffset, IndentLevel);
3382     }
3383     OS << Field.getType().getAsString() << ' ' << Field << '\n';
3384   }
3385
3386   // Dump virtual bases.
3387   if (CXXRD && IncludeVirtualBases) {
3388     const ASTRecordLayout::VBaseOffsetsMapTy &VtorDisps =
3389       Layout.getVBaseOffsetsMap();
3390
3391     for (const CXXBaseSpecifier &Base : CXXRD->vbases()) {
3392       assert(Base.isVirtual() && "Found non-virtual class!");
3393       const CXXRecordDecl *VBase = Base.getType()->getAsCXXRecordDecl();
3394
3395       CharUnits VBaseOffset = Offset + Layout.getVBaseClassOffset(VBase);
3396
3397       if (VtorDisps.find(VBase)->second.hasVtorDisp()) {
3398         PrintOffset(OS, VBaseOffset - CharUnits::fromQuantity(4), IndentLevel);
3399         OS << "(vtordisp for vbase " << *VBase << ")\n";
3400       }
3401
3402       DumpRecordLayout(OS, VBase, C, VBaseOffset, IndentLevel,
3403                        VBase == Layout.getPrimaryBase() ?
3404                          "(primary virtual base)" : "(virtual base)",
3405                        /*PrintSizeInfo=*/false,
3406                        /*IncludeVirtualBases=*/false);
3407     }
3408   }
3409
3410   if (!PrintSizeInfo) return;
3411
3412   PrintIndentNoOffset(OS, IndentLevel - 1);
3413   OS << "[sizeof=" << Layout.getSize().getQuantity();
3414   if (CXXRD && !isMsLayout(C))
3415     OS << ", dsize=" << Layout.getDataSize().getQuantity();
3416   OS << ", align=" << Layout.getAlignment().getQuantity();
3417
3418   if (CXXRD) {
3419     OS << ",\n";
3420     PrintIndentNoOffset(OS, IndentLevel - 1);
3421     OS << " nvsize=" << Layout.getNonVirtualSize().getQuantity();
3422     OS << ", nvalign=" << Layout.getNonVirtualAlignment().getQuantity();
3423   }
3424   OS << "]\n";
3425 }
3426
3427 void ASTContext::DumpRecordLayout(const RecordDecl *RD,
3428                                   raw_ostream &OS,
3429                                   bool Simple) const {
3430   if (!Simple) {
3431     ::DumpRecordLayout(OS, RD, *this, CharUnits(), 0, nullptr,
3432                        /*PrintSizeInfo*/true,
3433                        /*IncludeVirtualBases=*/true);
3434     return;
3435   }
3436
3437   // The "simple" format is designed to be parsed by the
3438   // layout-override testing code.  There shouldn't be any external
3439   // uses of this format --- when LLDB overrides a layout, it sets up
3440   // the data structures directly --- so feel free to adjust this as
3441   // you like as long as you also update the rudimentary parser for it
3442   // in libFrontend.
3443
3444   const ASTRecordLayout &Info = getASTRecordLayout(RD);
3445   OS << "Type: " << getTypeDeclType(RD).getAsString() << "\n";
3446   OS << "\nLayout: ";
3447   OS << "<ASTRecordLayout\n";
3448   OS << "  Size:" << toBits(Info.getSize()) << "\n";
3449   if (!isMsLayout(*this))
3450     OS << "  DataSize:" << toBits(Info.getDataSize()) << "\n";
3451   OS << "  Alignment:" << toBits(Info.getAlignment()) << "\n";
3452   OS << "  FieldOffsets: [";
3453   for (unsigned i = 0, e = Info.getFieldCount(); i != e; ++i) {
3454     if (i) OS << ", ";
3455     OS << Info.getFieldOffset(i);
3456   }
3457   OS << "]>\n";
3458 }