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