• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
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 // This contains code dealing with generation of the layout of virtual tables.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/AST/VTableBuilder.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/ASTDiagnostic.h"
17 #include "clang/AST/CXXInheritance.h"
18 #include "clang/AST/RecordLayout.h"
19 #include "clang/Basic/TargetInfo.h"
20 #include "llvm/ADT/SetOperations.h"
21 #include "llvm/ADT/SmallPtrSet.h"
22 #include "llvm/Support/Format.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <algorithm>
25 #include <cstdio>
26 
27 using namespace clang;
28 
29 #define DUMP_OVERRIDERS 0
30 
31 namespace {
32 
33 /// BaseOffset - Represents an offset from a derived class to a direct or
34 /// indirect base class.
35 struct BaseOffset {
36   /// DerivedClass - The derived class.
37   const CXXRecordDecl *DerivedClass;
38 
39   /// VirtualBase - If the path from the derived class to the base class
40   /// involves virtual base classes, this holds the declaration of the last
41   /// virtual base in this path (i.e. closest to the base class).
42   const CXXRecordDecl *VirtualBase;
43 
44   /// NonVirtualOffset - The offset from the derived class to the base class.
45   /// (Or the offset from the virtual base class to the base class, if the
46   /// path from the derived class to the base class involves a virtual base
47   /// class.
48   CharUnits NonVirtualOffset;
49 
BaseOffset__anon5d32d09d0111::BaseOffset50   BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
51                  NonVirtualOffset(CharUnits::Zero()) { }
BaseOffset__anon5d32d09d0111::BaseOffset52   BaseOffset(const CXXRecordDecl *DerivedClass,
53              const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
54     : DerivedClass(DerivedClass), VirtualBase(VirtualBase),
55     NonVirtualOffset(NonVirtualOffset) { }
56 
isEmpty__anon5d32d09d0111::BaseOffset57   bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; }
58 };
59 
60 /// FinalOverriders - Contains the final overrider member functions for all
61 /// member functions in the base subobjects of a class.
62 class FinalOverriders {
63 public:
64   /// OverriderInfo - Information about a final overrider.
65   struct OverriderInfo {
66     /// Method - The method decl of the overrider.
67     const CXXMethodDecl *Method;
68 
69     /// VirtualBase - The virtual base class subobject of this overrider.
70     /// Note that this records the closest derived virtual base class subobject.
71     const CXXRecordDecl *VirtualBase;
72 
73     /// Offset - the base offset of the overrider's parent in the layout class.
74     CharUnits Offset;
75 
OverriderInfo__anon5d32d09d0111::FinalOverriders::OverriderInfo76     OverriderInfo() : Method(nullptr), VirtualBase(nullptr),
77                       Offset(CharUnits::Zero()) { }
78   };
79 
80 private:
81   /// MostDerivedClass - The most derived class for which the final overriders
82   /// are stored.
83   const CXXRecordDecl *MostDerivedClass;
84 
85   /// MostDerivedClassOffset - If we're building final overriders for a
86   /// construction vtable, this holds the offset from the layout class to the
87   /// most derived class.
88   const CharUnits MostDerivedClassOffset;
89 
90   /// LayoutClass - The class we're using for layout information. Will be
91   /// different than the most derived class if the final overriders are for a
92   /// construction vtable.
93   const CXXRecordDecl *LayoutClass;
94 
95   ASTContext &Context;
96 
97   /// MostDerivedClassLayout - the AST record layout of the most derived class.
98   const ASTRecordLayout &MostDerivedClassLayout;
99 
100   /// MethodBaseOffsetPairTy - Uniquely identifies a member function
101   /// in a base subobject.
102   typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
103 
104   typedef llvm::DenseMap<MethodBaseOffsetPairTy,
105                          OverriderInfo> OverridersMapTy;
106 
107   /// OverridersMap - The final overriders for all virtual member functions of
108   /// all the base subobjects of the most derived class.
109   OverridersMapTy OverridersMap;
110 
111   /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
112   /// as a record decl and a subobject number) and its offsets in the most
113   /// derived class as well as the layout class.
114   typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>,
115                          CharUnits> SubobjectOffsetMapTy;
116 
117   typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
118 
119   /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
120   /// given base.
121   void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
122                           CharUnits OffsetInLayoutClass,
123                           SubobjectOffsetMapTy &SubobjectOffsets,
124                           SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
125                           SubobjectCountMapTy &SubobjectCounts);
126 
127   typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
128 
129   /// dump - dump the final overriders for a base subobject, and all its direct
130   /// and indirect base subobjects.
131   void dump(raw_ostream &Out, BaseSubobject Base,
132             VisitedVirtualBasesSetTy& VisitedVirtualBases);
133 
134 public:
135   FinalOverriders(const CXXRecordDecl *MostDerivedClass,
136                   CharUnits MostDerivedClassOffset,
137                   const CXXRecordDecl *LayoutClass);
138 
139   /// getOverrider - Get the final overrider for the given method declaration in
140   /// the subobject with the given base offset.
getOverrider(const CXXMethodDecl * MD,CharUnits BaseOffset) const141   OverriderInfo getOverrider(const CXXMethodDecl *MD,
142                              CharUnits BaseOffset) const {
143     assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) &&
144            "Did not find overrider!");
145 
146     return OverridersMap.lookup(std::make_pair(MD, BaseOffset));
147   }
148 
149   /// dump - dump the final overriders.
dump()150   void dump() {
151     VisitedVirtualBasesSetTy VisitedVirtualBases;
152     dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()),
153          VisitedVirtualBases);
154   }
155 
156 };
157 
FinalOverriders(const CXXRecordDecl * MostDerivedClass,CharUnits MostDerivedClassOffset,const CXXRecordDecl * LayoutClass)158 FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
159                                  CharUnits MostDerivedClassOffset,
160                                  const CXXRecordDecl *LayoutClass)
161   : MostDerivedClass(MostDerivedClass),
162   MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
163   Context(MostDerivedClass->getASTContext()),
164   MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
165 
166   // Compute base offsets.
167   SubobjectOffsetMapTy SubobjectOffsets;
168   SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
169   SubobjectCountMapTy SubobjectCounts;
170   ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()),
171                      /*IsVirtual=*/false,
172                      MostDerivedClassOffset,
173                      SubobjectOffsets, SubobjectLayoutClassOffsets,
174                      SubobjectCounts);
175 
176   // Get the final overriders.
177   CXXFinalOverriderMap FinalOverriders;
178   MostDerivedClass->getFinalOverriders(FinalOverriders);
179 
180   for (const auto &Overrider : FinalOverriders) {
181     const CXXMethodDecl *MD = Overrider.first;
182     const OverridingMethods &Methods = Overrider.second;
183 
184     for (const auto &M : Methods) {
185       unsigned SubobjectNumber = M.first;
186       assert(SubobjectOffsets.count(std::make_pair(MD->getParent(),
187                                                    SubobjectNumber)) &&
188              "Did not find subobject offset!");
189 
190       CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(),
191                                                             SubobjectNumber)];
192 
193       assert(M.second.size() == 1 && "Final overrider is not unique!");
194       const UniqueVirtualMethod &Method = M.second.front();
195 
196       const CXXRecordDecl *OverriderRD = Method.Method->getParent();
197       assert(SubobjectLayoutClassOffsets.count(
198              std::make_pair(OverriderRD, Method.Subobject))
199              && "Did not find subobject offset!");
200       CharUnits OverriderOffset =
201         SubobjectLayoutClassOffsets[std::make_pair(OverriderRD,
202                                                    Method.Subobject)];
203 
204       OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)];
205       assert(!Overrider.Method && "Overrider should not exist yet!");
206 
207       Overrider.Offset = OverriderOffset;
208       Overrider.Method = Method.Method;
209       Overrider.VirtualBase = Method.InVirtualSubobject;
210     }
211   }
212 
213 #if DUMP_OVERRIDERS
214   // And dump them (for now).
215   dump();
216 #endif
217 }
218 
ComputeBaseOffset(const ASTContext & Context,const CXXRecordDecl * DerivedRD,const CXXBasePath & Path)219 static BaseOffset ComputeBaseOffset(const ASTContext &Context,
220                                     const CXXRecordDecl *DerivedRD,
221                                     const CXXBasePath &Path) {
222   CharUnits NonVirtualOffset = CharUnits::Zero();
223 
224   unsigned NonVirtualStart = 0;
225   const CXXRecordDecl *VirtualBase = nullptr;
226 
227   // First, look for the virtual base class.
228   for (int I = Path.size(), E = 0; I != E; --I) {
229     const CXXBasePathElement &Element = Path[I - 1];
230 
231     if (Element.Base->isVirtual()) {
232       NonVirtualStart = I;
233       QualType VBaseType = Element.Base->getType();
234       VirtualBase = VBaseType->getAsCXXRecordDecl();
235       break;
236     }
237   }
238 
239   // Now compute the non-virtual offset.
240   for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) {
241     const CXXBasePathElement &Element = Path[I];
242 
243     // Check the base class offset.
244     const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
245 
246     const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl();
247 
248     NonVirtualOffset += Layout.getBaseClassOffset(Base);
249   }
250 
251   // FIXME: This should probably use CharUnits or something. Maybe we should
252   // even change the base offsets in ASTRecordLayout to be specified in
253   // CharUnits.
254   return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
255 
256 }
257 
ComputeBaseOffset(const ASTContext & Context,const CXXRecordDecl * BaseRD,const CXXRecordDecl * DerivedRD)258 static BaseOffset ComputeBaseOffset(const ASTContext &Context,
259                                     const CXXRecordDecl *BaseRD,
260                                     const CXXRecordDecl *DerivedRD) {
261   CXXBasePaths Paths(/*FindAmbiguities=*/false,
262                      /*RecordPaths=*/true, /*DetectVirtual=*/false);
263 
264   if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
265     llvm_unreachable("Class must be derived from the passed in base class!");
266 
267   return ComputeBaseOffset(Context, DerivedRD, Paths.front());
268 }
269 
270 static BaseOffset
ComputeReturnAdjustmentBaseOffset(ASTContext & Context,const CXXMethodDecl * DerivedMD,const CXXMethodDecl * BaseMD)271 ComputeReturnAdjustmentBaseOffset(ASTContext &Context,
272                                   const CXXMethodDecl *DerivedMD,
273                                   const CXXMethodDecl *BaseMD) {
274   const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>();
275   const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>();
276 
277   // Canonicalize the return types.
278   CanQualType CanDerivedReturnType =
279       Context.getCanonicalType(DerivedFT->getReturnType());
280   CanQualType CanBaseReturnType =
281       Context.getCanonicalType(BaseFT->getReturnType());
282 
283   assert(CanDerivedReturnType->getTypeClass() ==
284          CanBaseReturnType->getTypeClass() &&
285          "Types must have same type class!");
286 
287   if (CanDerivedReturnType == CanBaseReturnType) {
288     // No adjustment needed.
289     return BaseOffset();
290   }
291 
292   if (isa<ReferenceType>(CanDerivedReturnType)) {
293     CanDerivedReturnType =
294       CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
295     CanBaseReturnType =
296       CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
297   } else if (isa<PointerType>(CanDerivedReturnType)) {
298     CanDerivedReturnType =
299       CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
300     CanBaseReturnType =
301       CanBaseReturnType->getAs<PointerType>()->getPointeeType();
302   } else {
303     llvm_unreachable("Unexpected return type!");
304   }
305 
306   // We need to compare unqualified types here; consider
307   //   const T *Base::foo();
308   //   T *Derived::foo();
309   if (CanDerivedReturnType.getUnqualifiedType() ==
310       CanBaseReturnType.getUnqualifiedType()) {
311     // No adjustment needed.
312     return BaseOffset();
313   }
314 
315   const CXXRecordDecl *DerivedRD =
316     cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl());
317 
318   const CXXRecordDecl *BaseRD =
319     cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());
320 
321   return ComputeBaseOffset(Context, BaseRD, DerivedRD);
322 }
323 
324 void
ComputeBaseOffsets(BaseSubobject Base,bool IsVirtual,CharUnits OffsetInLayoutClass,SubobjectOffsetMapTy & SubobjectOffsets,SubobjectOffsetMapTy & SubobjectLayoutClassOffsets,SubobjectCountMapTy & SubobjectCounts)325 FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
326                               CharUnits OffsetInLayoutClass,
327                               SubobjectOffsetMapTy &SubobjectOffsets,
328                               SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
329                               SubobjectCountMapTy &SubobjectCounts) {
330   const CXXRecordDecl *RD = Base.getBase();
331 
332   unsigned SubobjectNumber = 0;
333   if (!IsVirtual)
334     SubobjectNumber = ++SubobjectCounts[RD];
335 
336   // Set up the subobject to offset mapping.
337   assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))
338          && "Subobject offset already exists!");
339   assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber))
340          && "Subobject offset already exists!");
341 
342   SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();
343   SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =
344     OffsetInLayoutClass;
345 
346   // Traverse our bases.
347   for (const auto &B : RD->bases()) {
348     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
349 
350     CharUnits BaseOffset;
351     CharUnits BaseOffsetInLayoutClass;
352     if (B.isVirtual()) {
353       // Check if we've visited this virtual base before.
354       if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))
355         continue;
356 
357       const ASTRecordLayout &LayoutClassLayout =
358         Context.getASTRecordLayout(LayoutClass);
359 
360       BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
361       BaseOffsetInLayoutClass =
362         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
363     } else {
364       const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
365       CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);
366 
367       BaseOffset = Base.getBaseOffset() + Offset;
368       BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
369     }
370 
371     ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset),
372                        B.isVirtual(), BaseOffsetInLayoutClass,
373                        SubobjectOffsets, SubobjectLayoutClassOffsets,
374                        SubobjectCounts);
375   }
376 }
377 
dump(raw_ostream & Out,BaseSubobject Base,VisitedVirtualBasesSetTy & VisitedVirtualBases)378 void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
379                            VisitedVirtualBasesSetTy &VisitedVirtualBases) {
380   const CXXRecordDecl *RD = Base.getBase();
381   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
382 
383   for (const auto &B : RD->bases()) {
384     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
385 
386     // Ignore bases that don't have any virtual member functions.
387     if (!BaseDecl->isPolymorphic())
388       continue;
389 
390     CharUnits BaseOffset;
391     if (B.isVirtual()) {
392       if (!VisitedVirtualBases.insert(BaseDecl).second) {
393         // We've visited this base before.
394         continue;
395       }
396 
397       BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
398     } else {
399       BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();
400     }
401 
402     dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
403   }
404 
405   Out << "Final overriders for (";
406   RD->printQualifiedName(Out);
407   Out << ", ";
408   Out << Base.getBaseOffset().getQuantity() << ")\n";
409 
410   // Now dump the overriders for this base subobject.
411   for (const auto *MD : RD->methods()) {
412     if (!MD->isVirtual())
413       continue;
414     MD = MD->getCanonicalDecl();
415 
416     OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());
417 
418     Out << "  ";
419     MD->printQualifiedName(Out);
420     Out << " - (";
421     Overrider.Method->printQualifiedName(Out);
422     Out << ", " << Overrider.Offset.getQuantity() << ')';
423 
424     BaseOffset Offset;
425     if (!Overrider.Method->isPure())
426       Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
427 
428     if (!Offset.isEmpty()) {
429       Out << " [ret-adj: ";
430       if (Offset.VirtualBase) {
431         Offset.VirtualBase->printQualifiedName(Out);
432         Out << " vbase, ";
433       }
434 
435       Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
436     }
437 
438     Out << "\n";
439   }
440 }
441 
442 /// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
443 struct VCallOffsetMap {
444 
445   typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
446 
447   /// Offsets - Keeps track of methods and their offsets.
448   // FIXME: This should be a real map and not a vector.
449   SmallVector<MethodAndOffsetPairTy, 16> Offsets;
450 
451   /// MethodsCanShareVCallOffset - Returns whether two virtual member functions
452   /// can share the same vcall offset.
453   static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
454                                          const CXXMethodDecl *RHS);
455 
456 public:
457   /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
458   /// add was successful, or false if there was already a member function with
459   /// the same signature in the map.
460   bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
461 
462   /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
463   /// vtable address point) for the given virtual member function.
464   CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
465 
466   // empty - Return whether the offset map is empty or not.
empty__anon5d32d09d0111::VCallOffsetMap467   bool empty() const { return Offsets.empty(); }
468 };
469 
HasSameVirtualSignature(const CXXMethodDecl * LHS,const CXXMethodDecl * RHS)470 static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
471                                     const CXXMethodDecl *RHS) {
472   const FunctionProtoType *LT =
473     cast<FunctionProtoType>(LHS->getType().getCanonicalType());
474   const FunctionProtoType *RT =
475     cast<FunctionProtoType>(RHS->getType().getCanonicalType());
476 
477   // Fast-path matches in the canonical types.
478   if (LT == RT) return true;
479 
480   // Force the signatures to match.  We can't rely on the overrides
481   // list here because there isn't necessarily an inheritance
482   // relationship between the two methods.
483   if (LT->getTypeQuals() != RT->getTypeQuals())
484     return false;
485   return LT->getParamTypes() == RT->getParamTypes();
486 }
487 
MethodsCanShareVCallOffset(const CXXMethodDecl * LHS,const CXXMethodDecl * RHS)488 bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
489                                                 const CXXMethodDecl *RHS) {
490   assert(LHS->isVirtual() && "LHS must be virtual!");
491   assert(RHS->isVirtual() && "LHS must be virtual!");
492 
493   // A destructor can share a vcall offset with another destructor.
494   if (isa<CXXDestructorDecl>(LHS))
495     return isa<CXXDestructorDecl>(RHS);
496 
497   // FIXME: We need to check more things here.
498 
499   // The methods must have the same name.
500   DeclarationName LHSName = LHS->getDeclName();
501   DeclarationName RHSName = RHS->getDeclName();
502   if (LHSName != RHSName)
503     return false;
504 
505   // And the same signatures.
506   return HasSameVirtualSignature(LHS, RHS);
507 }
508 
AddVCallOffset(const CXXMethodDecl * MD,CharUnits OffsetOffset)509 bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,
510                                     CharUnits OffsetOffset) {
511   // Check if we can reuse an offset.
512   for (const auto &OffsetPair : Offsets) {
513     if (MethodsCanShareVCallOffset(OffsetPair.first, MD))
514       return false;
515   }
516 
517   // Add the offset.
518   Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));
519   return true;
520 }
521 
getVCallOffsetOffset(const CXXMethodDecl * MD)522 CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
523   // Look for an offset.
524   for (const auto &OffsetPair : Offsets) {
525     if (MethodsCanShareVCallOffset(OffsetPair.first, MD))
526       return OffsetPair.second;
527   }
528 
529   llvm_unreachable("Should always find a vcall offset offset!");
530 }
531 
532 /// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
533 class VCallAndVBaseOffsetBuilder {
534 public:
535   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
536     VBaseOffsetOffsetsMapTy;
537 
538 private:
539   /// MostDerivedClass - The most derived class for which we're building vcall
540   /// and vbase offsets.
541   const CXXRecordDecl *MostDerivedClass;
542 
543   /// LayoutClass - The class we're using for layout information. Will be
544   /// different than the most derived class if we're building a construction
545   /// vtable.
546   const CXXRecordDecl *LayoutClass;
547 
548   /// Context - The ASTContext which we will use for layout information.
549   ASTContext &Context;
550 
551   /// Components - vcall and vbase offset components
552   typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
553   VTableComponentVectorTy Components;
554 
555   /// VisitedVirtualBases - Visited virtual bases.
556   llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
557 
558   /// VCallOffsets - Keeps track of vcall offsets.
559   VCallOffsetMap VCallOffsets;
560 
561 
562   /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
563   /// relative to the address point.
564   VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
565 
566   /// FinalOverriders - The final overriders of the most derived class.
567   /// (Can be null when we're not building a vtable of the most derived class).
568   const FinalOverriders *Overriders;
569 
570   /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
571   /// given base subobject.
572   void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
573                                CharUnits RealBaseOffset);
574 
575   /// AddVCallOffsets - Add vcall offsets for the given base subobject.
576   void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
577 
578   /// AddVBaseOffsets - Add vbase offsets for the given class.
579   void AddVBaseOffsets(const CXXRecordDecl *Base,
580                        CharUnits OffsetInLayoutClass);
581 
582   /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
583   /// chars, relative to the vtable address point.
584   CharUnits getCurrentOffsetOffset() const;
585 
586 public:
VCallAndVBaseOffsetBuilder(const CXXRecordDecl * MostDerivedClass,const CXXRecordDecl * LayoutClass,const FinalOverriders * Overriders,BaseSubobject Base,bool BaseIsVirtual,CharUnits OffsetInLayoutClass)587   VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass,
588                              const CXXRecordDecl *LayoutClass,
589                              const FinalOverriders *Overriders,
590                              BaseSubobject Base, bool BaseIsVirtual,
591                              CharUnits OffsetInLayoutClass)
592     : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass),
593     Context(MostDerivedClass->getASTContext()), Overriders(Overriders) {
594 
595     // Add vcall and vbase offsets.
596     AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);
597   }
598 
599   /// Methods for iterating over the components.
600   typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
components_begin() const601   const_iterator components_begin() const { return Components.rbegin(); }
components_end() const602   const_iterator components_end() const { return Components.rend(); }
603 
getVCallOffsets() const604   const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
getVBaseOffsetOffsets() const605   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
606     return VBaseOffsetOffsets;
607   }
608 };
609 
610 void
AddVCallAndVBaseOffsets(BaseSubobject Base,bool BaseIsVirtual,CharUnits RealBaseOffset)611 VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
612                                                     bool BaseIsVirtual,
613                                                     CharUnits RealBaseOffset) {
614   const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
615 
616   // Itanium C++ ABI 2.5.2:
617   //   ..in classes sharing a virtual table with a primary base class, the vcall
618   //   and vbase offsets added by the derived class all come before the vcall
619   //   and vbase offsets required by the base class, so that the latter may be
620   //   laid out as required by the base class without regard to additions from
621   //   the derived class(es).
622 
623   // (Since we're emitting the vcall and vbase offsets in reverse order, we'll
624   // emit them for the primary base first).
625   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
626     bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
627 
628     CharUnits PrimaryBaseOffset;
629 
630     // Get the base offset of the primary base.
631     if (PrimaryBaseIsVirtual) {
632       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
633              "Primary vbase should have a zero offset!");
634 
635       const ASTRecordLayout &MostDerivedClassLayout =
636         Context.getASTRecordLayout(MostDerivedClass);
637 
638       PrimaryBaseOffset =
639         MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
640     } else {
641       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
642              "Primary base should have a zero offset!");
643 
644       PrimaryBaseOffset = Base.getBaseOffset();
645     }
646 
647     AddVCallAndVBaseOffsets(
648       BaseSubobject(PrimaryBase,PrimaryBaseOffset),
649       PrimaryBaseIsVirtual, RealBaseOffset);
650   }
651 
652   AddVBaseOffsets(Base.getBase(), RealBaseOffset);
653 
654   // We only want to add vcall offsets for virtual bases.
655   if (BaseIsVirtual)
656     AddVCallOffsets(Base, RealBaseOffset);
657 }
658 
getCurrentOffsetOffset() const659 CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
660   // OffsetIndex is the index of this vcall or vbase offset, relative to the
661   // vtable address point. (We subtract 3 to account for the information just
662   // above the address point, the RTTI info, the offset to top, and the
663   // vcall offset itself).
664   int64_t OffsetIndex = -(int64_t)(3 + Components.size());
665 
666   CharUnits PointerWidth =
667     Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
668   CharUnits OffsetOffset = PointerWidth * OffsetIndex;
669   return OffsetOffset;
670 }
671 
AddVCallOffsets(BaseSubobject Base,CharUnits VBaseOffset)672 void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,
673                                                  CharUnits VBaseOffset) {
674   const CXXRecordDecl *RD = Base.getBase();
675   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
676 
677   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
678 
679   // Handle the primary base first.
680   // We only want to add vcall offsets if the base is non-virtual; a virtual
681   // primary base will have its vcall and vbase offsets emitted already.
682   if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {
683     // Get the base offset of the primary base.
684     assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
685            "Primary base should have a zero offset!");
686 
687     AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),
688                     VBaseOffset);
689   }
690 
691   // Add the vcall offsets.
692   for (const auto *MD : RD->methods()) {
693     if (!MD->isVirtual())
694       continue;
695     MD = MD->getCanonicalDecl();
696 
697     CharUnits OffsetOffset = getCurrentOffsetOffset();
698 
699     // Don't add a vcall offset if we already have one for this member function
700     // signature.
701     if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
702       continue;
703 
704     CharUnits Offset = CharUnits::Zero();
705 
706     if (Overriders) {
707       // Get the final overrider.
708       FinalOverriders::OverriderInfo Overrider =
709         Overriders->getOverrider(MD, Base.getBaseOffset());
710 
711       /// The vcall offset is the offset from the virtual base to the object
712       /// where the function was overridden.
713       Offset = Overrider.Offset - VBaseOffset;
714     }
715 
716     Components.push_back(
717       VTableComponent::MakeVCallOffset(Offset));
718   }
719 
720   // And iterate over all non-virtual bases (ignoring the primary base).
721   for (const auto &B : RD->bases()) {
722     if (B.isVirtual())
723       continue;
724 
725     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
726     if (BaseDecl == PrimaryBase)
727       continue;
728 
729     // Get the base offset of this base.
730     CharUnits BaseOffset = Base.getBaseOffset() +
731       Layout.getBaseClassOffset(BaseDecl);
732 
733     AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset),
734                     VBaseOffset);
735   }
736 }
737 
738 void
AddVBaseOffsets(const CXXRecordDecl * RD,CharUnits OffsetInLayoutClass)739 VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
740                                             CharUnits OffsetInLayoutClass) {
741   const ASTRecordLayout &LayoutClassLayout =
742     Context.getASTRecordLayout(LayoutClass);
743 
744   // Add vbase offsets.
745   for (const auto &B : RD->bases()) {
746     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
747 
748     // Check if this is a virtual base that we haven't visited before.
749     if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl).second) {
750       CharUnits Offset =
751         LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;
752 
753       // Add the vbase offset offset.
754       assert(!VBaseOffsetOffsets.count(BaseDecl) &&
755              "vbase offset offset already exists!");
756 
757       CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
758       VBaseOffsetOffsets.insert(
759           std::make_pair(BaseDecl, VBaseOffsetOffset));
760 
761       Components.push_back(
762           VTableComponent::MakeVBaseOffset(Offset));
763     }
764 
765     // Check the base class looking for more vbase offsets.
766     AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);
767   }
768 }
769 
770 /// ItaniumVTableBuilder - Class for building vtable layout information.
771 class ItaniumVTableBuilder {
772 public:
773   /// PrimaryBasesSetVectorTy - A set vector of direct and indirect
774   /// primary bases.
775   typedef llvm::SmallSetVector<const CXXRecordDecl *, 8>
776     PrimaryBasesSetVectorTy;
777 
778   typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
779     VBaseOffsetOffsetsMapTy;
780 
781   typedef llvm::DenseMap<BaseSubobject, uint64_t>
782     AddressPointsMapTy;
783 
784   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
785 
786 private:
787   /// VTables - Global vtable information.
788   ItaniumVTableContext &VTables;
789 
790   /// MostDerivedClass - The most derived class for which we're building this
791   /// vtable.
792   const CXXRecordDecl *MostDerivedClass;
793 
794   /// MostDerivedClassOffset - If we're building a construction vtable, this
795   /// holds the offset from the layout class to the most derived class.
796   const CharUnits MostDerivedClassOffset;
797 
798   /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual
799   /// base. (This only makes sense when building a construction vtable).
800   bool MostDerivedClassIsVirtual;
801 
802   /// LayoutClass - The class we're using for layout information. Will be
803   /// different than the most derived class if we're building a construction
804   /// vtable.
805   const CXXRecordDecl *LayoutClass;
806 
807   /// Context - The ASTContext which we will use for layout information.
808   ASTContext &Context;
809 
810   /// FinalOverriders - The final overriders of the most derived class.
811   const FinalOverriders Overriders;
812 
813   /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
814   /// bases in this vtable.
815   llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
816 
817   /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
818   /// the most derived class.
819   VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
820 
821   /// Components - The components of the vtable being built.
822   SmallVector<VTableComponent, 64> Components;
823 
824   /// AddressPoints - Address points for the vtable being built.
825   AddressPointsMapTy AddressPoints;
826 
827   /// MethodInfo - Contains information about a method in a vtable.
828   /// (Used for computing 'this' pointer adjustment thunks.
829   struct MethodInfo {
830     /// BaseOffset - The base offset of this method.
831     const CharUnits BaseOffset;
832 
833     /// BaseOffsetInLayoutClass - The base offset in the layout class of this
834     /// method.
835     const CharUnits BaseOffsetInLayoutClass;
836 
837     /// VTableIndex - The index in the vtable that this method has.
838     /// (For destructors, this is the index of the complete destructor).
839     const uint64_t VTableIndex;
840 
MethodInfo__anon5d32d09d0111::ItaniumVTableBuilder::MethodInfo841     MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,
842                uint64_t VTableIndex)
843       : BaseOffset(BaseOffset),
844       BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
845       VTableIndex(VTableIndex) { }
846 
MethodInfo__anon5d32d09d0111::ItaniumVTableBuilder::MethodInfo847     MethodInfo()
848       : BaseOffset(CharUnits::Zero()),
849       BaseOffsetInLayoutClass(CharUnits::Zero()),
850       VTableIndex(0) { }
851   };
852 
853   typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
854 
855   /// MethodInfoMap - The information for all methods in the vtable we're
856   /// currently building.
857   MethodInfoMapTy MethodInfoMap;
858 
859   /// MethodVTableIndices - Contains the index (relative to the vtable address
860   /// point) where the function pointer for a virtual function is stored.
861   MethodVTableIndicesTy MethodVTableIndices;
862 
863   typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
864 
865   /// VTableThunks - The thunks by vtable index in the vtable currently being
866   /// built.
867   VTableThunksMapTy VTableThunks;
868 
869   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
870   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
871 
872   /// Thunks - A map that contains all the thunks needed for all methods in the
873   /// most derived class for which the vtable is currently being built.
874   ThunksMapTy Thunks;
875 
876   /// AddThunk - Add a thunk for the given method.
877   void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
878 
879   /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
880   /// part of the vtable we're currently building.
881   void ComputeThisAdjustments();
882 
883   typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
884 
885   /// PrimaryVirtualBases - All known virtual bases who are a primary base of
886   /// some other base.
887   VisitedVirtualBasesSetTy PrimaryVirtualBases;
888 
889   /// ComputeReturnAdjustment - Compute the return adjustment given a return
890   /// adjustment base offset.
891   ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
892 
893   /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
894   /// the 'this' pointer from the base subobject to the derived subobject.
895   BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
896                                              BaseSubobject Derived) const;
897 
898   /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
899   /// given virtual member function, its offset in the layout class and its
900   /// final overrider.
901   ThisAdjustment
902   ComputeThisAdjustment(const CXXMethodDecl *MD,
903                         CharUnits BaseOffsetInLayoutClass,
904                         FinalOverriders::OverriderInfo Overrider);
905 
906   /// AddMethod - Add a single virtual member function to the vtable
907   /// components vector.
908   void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
909 
910   /// IsOverriderUsed - Returns whether the overrider will ever be used in this
911   /// part of the vtable.
912   ///
913   /// Itanium C++ ABI 2.5.2:
914   ///
915   ///   struct A { virtual void f(); };
916   ///   struct B : virtual public A { int i; };
917   ///   struct C : virtual public A { int j; };
918   ///   struct D : public B, public C {};
919   ///
920   ///   When B and C are declared, A is a primary base in each case, so although
921   ///   vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
922   ///   adjustment is required and no thunk is generated. However, inside D
923   ///   objects, A is no longer a primary base of C, so if we allowed calls to
924   ///   C::f() to use the copy of A's vtable in the C subobject, we would need
925   ///   to adjust this from C* to B::A*, which would require a third-party
926   ///   thunk. Since we require that a call to C::f() first convert to A*,
927   ///   C-in-D's copy of A's vtable is never referenced, so this is not
928   ///   necessary.
929   bool IsOverriderUsed(const CXXMethodDecl *Overrider,
930                        CharUnits BaseOffsetInLayoutClass,
931                        const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
932                        CharUnits FirstBaseOffsetInLayoutClass) const;
933 
934 
935   /// AddMethods - Add the methods of this base subobject and all its
936   /// primary bases to the vtable components vector.
937   void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
938                   const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
939                   CharUnits FirstBaseOffsetInLayoutClass,
940                   PrimaryBasesSetVectorTy &PrimaryBases);
941 
942   // LayoutVTable - Layout the vtable for the given base class, including its
943   // secondary vtables and any vtables for virtual bases.
944   void LayoutVTable();
945 
946   /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the
947   /// given base subobject, as well as all its secondary vtables.
948   ///
949   /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
950   /// or a direct or indirect base of a virtual base.
951   ///
952   /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual
953   /// in the layout class.
954   void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,
955                                         bool BaseIsMorallyVirtual,
956                                         bool BaseIsVirtualInLayoutClass,
957                                         CharUnits OffsetInLayoutClass);
958 
959   /// LayoutSecondaryVTables - Layout the secondary vtables for the given base
960   /// subobject.
961   ///
962   /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
963   /// or a direct or indirect base of a virtual base.
964   void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,
965                               CharUnits OffsetInLayoutClass);
966 
967   /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this
968   /// class hierarchy.
969   void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD,
970                                     CharUnits OffsetInLayoutClass,
971                                     VisitedVirtualBasesSetTy &VBases);
972 
973   /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the
974   /// given base (excluding any primary bases).
975   void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD,
976                                     VisitedVirtualBasesSetTy &VBases);
977 
978   /// isBuildingConstructionVTable - Return whether this vtable builder is
979   /// building a construction vtable.
isBuildingConstructorVTable() const980   bool isBuildingConstructorVTable() const {
981     return MostDerivedClass != LayoutClass;
982   }
983 
984 public:
ItaniumVTableBuilder(ItaniumVTableContext & VTables,const CXXRecordDecl * MostDerivedClass,CharUnits MostDerivedClassOffset,bool MostDerivedClassIsVirtual,const CXXRecordDecl * LayoutClass)985   ItaniumVTableBuilder(ItaniumVTableContext &VTables,
986                        const CXXRecordDecl *MostDerivedClass,
987                        CharUnits MostDerivedClassOffset,
988                        bool MostDerivedClassIsVirtual,
989                        const CXXRecordDecl *LayoutClass)
990       : VTables(VTables), MostDerivedClass(MostDerivedClass),
991         MostDerivedClassOffset(MostDerivedClassOffset),
992         MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
993         LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
994         Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {
995     assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());
996 
997     LayoutVTable();
998 
999     if (Context.getLangOpts().DumpVTableLayouts)
1000       dumpLayout(llvm::outs());
1001   }
1002 
getNumThunks() const1003   uint64_t getNumThunks() const {
1004     return Thunks.size();
1005   }
1006 
thunks_begin() const1007   ThunksMapTy::const_iterator thunks_begin() const {
1008     return Thunks.begin();
1009   }
1010 
thunks_end() const1011   ThunksMapTy::const_iterator thunks_end() const {
1012     return Thunks.end();
1013   }
1014 
getVBaseOffsetOffsets() const1015   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
1016     return VBaseOffsetOffsets;
1017   }
1018 
getAddressPoints() const1019   const AddressPointsMapTy &getAddressPoints() const {
1020     return AddressPoints;
1021   }
1022 
vtable_indices_begin() const1023   MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
1024     return MethodVTableIndices.begin();
1025   }
1026 
vtable_indices_end() const1027   MethodVTableIndicesTy::const_iterator vtable_indices_end() const {
1028     return MethodVTableIndices.end();
1029   }
1030 
1031   /// getNumVTableComponents - Return the number of components in the vtable
1032   /// currently built.
getNumVTableComponents() const1033   uint64_t getNumVTableComponents() const {
1034     return Components.size();
1035   }
1036 
vtable_component_begin() const1037   const VTableComponent *vtable_component_begin() const {
1038     return Components.begin();
1039   }
1040 
vtable_component_end() const1041   const VTableComponent *vtable_component_end() const {
1042     return Components.end();
1043   }
1044 
address_points_begin() const1045   AddressPointsMapTy::const_iterator address_points_begin() const {
1046     return AddressPoints.begin();
1047   }
1048 
address_points_end() const1049   AddressPointsMapTy::const_iterator address_points_end() const {
1050     return AddressPoints.end();
1051   }
1052 
vtable_thunks_begin() const1053   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
1054     return VTableThunks.begin();
1055   }
1056 
vtable_thunks_end() const1057   VTableThunksMapTy::const_iterator vtable_thunks_end() const {
1058     return VTableThunks.end();
1059   }
1060 
1061   /// dumpLayout - Dump the vtable layout.
1062   void dumpLayout(raw_ostream&);
1063 };
1064 
AddThunk(const CXXMethodDecl * MD,const ThunkInfo & Thunk)1065 void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
1066                                     const ThunkInfo &Thunk) {
1067   assert(!isBuildingConstructorVTable() &&
1068          "Can't add thunks for construction vtable");
1069 
1070   SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];
1071 
1072   // Check if we have this thunk already.
1073   if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) !=
1074       ThunksVector.end())
1075     return;
1076 
1077   ThunksVector.push_back(Thunk);
1078 }
1079 
1080 typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;
1081 
1082 /// Visit all the methods overridden by the given method recursively,
1083 /// in a depth-first pre-order. The Visitor's visitor method returns a bool
1084 /// indicating whether to continue the recursion for the given overridden
1085 /// method (i.e. returning false stops the iteration).
1086 template <class VisitorTy>
1087 static void
visitAllOverriddenMethods(const CXXMethodDecl * MD,VisitorTy & Visitor)1088 visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1089   assert(MD->isVirtual() && "Method is not virtual!");
1090 
1091   for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
1092        E = MD->end_overridden_methods(); I != E; ++I) {
1093     const CXXMethodDecl *OverriddenMD = *I;
1094     if (!Visitor(OverriddenMD))
1095       continue;
1096     visitAllOverriddenMethods(OverriddenMD, Visitor);
1097   }
1098 }
1099 
1100 /// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
1101 /// the overridden methods that the function decl overrides.
1102 static void
ComputeAllOverriddenMethods(const CXXMethodDecl * MD,OverriddenMethodsSetTy & OverriddenMethods)1103 ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
1104                             OverriddenMethodsSetTy& OverriddenMethods) {
1105   auto OverriddenMethodsCollector = [&](const CXXMethodDecl *MD) {
1106     // Don't recurse on this method if we've already collected it.
1107     return OverriddenMethods.insert(MD).second;
1108   };
1109   visitAllOverriddenMethods(MD, OverriddenMethodsCollector);
1110 }
1111 
ComputeThisAdjustments()1112 void ItaniumVTableBuilder::ComputeThisAdjustments() {
1113   // Now go through the method info map and see if any of the methods need
1114   // 'this' pointer adjustments.
1115   for (const auto &MI : MethodInfoMap) {
1116     const CXXMethodDecl *MD = MI.first;
1117     const MethodInfo &MethodInfo = MI.second;
1118 
1119     // Ignore adjustments for unused function pointers.
1120     uint64_t VTableIndex = MethodInfo.VTableIndex;
1121     if (Components[VTableIndex].getKind() ==
1122         VTableComponent::CK_UnusedFunctionPointer)
1123       continue;
1124 
1125     // Get the final overrider for this method.
1126     FinalOverriders::OverriderInfo Overrider =
1127       Overriders.getOverrider(MD, MethodInfo.BaseOffset);
1128 
1129     // Check if we need an adjustment at all.
1130     if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {
1131       // When a return thunk is needed by a derived class that overrides a
1132       // virtual base, gcc uses a virtual 'this' adjustment as well.
1133       // While the thunk itself might be needed by vtables in subclasses or
1134       // in construction vtables, there doesn't seem to be a reason for using
1135       // the thunk in this vtable. Still, we do so to match gcc.
1136       if (VTableThunks.lookup(VTableIndex).Return.isEmpty())
1137         continue;
1138     }
1139 
1140     ThisAdjustment ThisAdjustment =
1141       ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider);
1142 
1143     if (ThisAdjustment.isEmpty())
1144       continue;
1145 
1146     // Add it.
1147     VTableThunks[VTableIndex].This = ThisAdjustment;
1148 
1149     if (isa<CXXDestructorDecl>(MD)) {
1150       // Add an adjustment for the deleting destructor as well.
1151       VTableThunks[VTableIndex + 1].This = ThisAdjustment;
1152     }
1153   }
1154 
1155   /// Clear the method info map.
1156   MethodInfoMap.clear();
1157 
1158   if (isBuildingConstructorVTable()) {
1159     // We don't need to store thunk information for construction vtables.
1160     return;
1161   }
1162 
1163   for (const auto &TI : VTableThunks) {
1164     const VTableComponent &Component = Components[TI.first];
1165     const ThunkInfo &Thunk = TI.second;
1166     const CXXMethodDecl *MD;
1167 
1168     switch (Component.getKind()) {
1169     default:
1170       llvm_unreachable("Unexpected vtable component kind!");
1171     case VTableComponent::CK_FunctionPointer:
1172       MD = Component.getFunctionDecl();
1173       break;
1174     case VTableComponent::CK_CompleteDtorPointer:
1175       MD = Component.getDestructorDecl();
1176       break;
1177     case VTableComponent::CK_DeletingDtorPointer:
1178       // We've already added the thunk when we saw the complete dtor pointer.
1179       continue;
1180     }
1181 
1182     if (MD->getParent() == MostDerivedClass)
1183       AddThunk(MD, Thunk);
1184   }
1185 }
1186 
1187 ReturnAdjustment
ComputeReturnAdjustment(BaseOffset Offset)1188 ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {
1189   ReturnAdjustment Adjustment;
1190 
1191   if (!Offset.isEmpty()) {
1192     if (Offset.VirtualBase) {
1193       // Get the virtual base offset offset.
1194       if (Offset.DerivedClass == MostDerivedClass) {
1195         // We can get the offset offset directly from our map.
1196         Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1197           VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity();
1198       } else {
1199         Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1200           VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass,
1201                                              Offset.VirtualBase).getQuantity();
1202       }
1203     }
1204 
1205     Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1206   }
1207 
1208   return Adjustment;
1209 }
1210 
ComputeThisAdjustmentBaseOffset(BaseSubobject Base,BaseSubobject Derived) const1211 BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
1212     BaseSubobject Base, BaseSubobject Derived) const {
1213   const CXXRecordDecl *BaseRD = Base.getBase();
1214   const CXXRecordDecl *DerivedRD = Derived.getBase();
1215 
1216   CXXBasePaths Paths(/*FindAmbiguities=*/true,
1217                      /*RecordPaths=*/true, /*DetectVirtual=*/true);
1218 
1219   if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
1220     llvm_unreachable("Class must be derived from the passed in base class!");
1221 
1222   // We have to go through all the paths, and see which one leads us to the
1223   // right base subobject.
1224   for (const CXXBasePath &Path : Paths) {
1225     BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, Path);
1226 
1227     CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;
1228 
1229     if (Offset.VirtualBase) {
1230       // If we have a virtual base class, the non-virtual offset is relative
1231       // to the virtual base class offset.
1232       const ASTRecordLayout &LayoutClassLayout =
1233         Context.getASTRecordLayout(LayoutClass);
1234 
1235       /// Get the virtual base offset, relative to the most derived class
1236       /// layout.
1237       OffsetToBaseSubobject +=
1238         LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase);
1239     } else {
1240       // Otherwise, the non-virtual offset is relative to the derived class
1241       // offset.
1242       OffsetToBaseSubobject += Derived.getBaseOffset();
1243     }
1244 
1245     // Check if this path gives us the right base subobject.
1246     if (OffsetToBaseSubobject == Base.getBaseOffset()) {
1247       // Since we're going from the base class _to_ the derived class, we'll
1248       // invert the non-virtual offset here.
1249       Offset.NonVirtualOffset = -Offset.NonVirtualOffset;
1250       return Offset;
1251     }
1252   }
1253 
1254   return BaseOffset();
1255 }
1256 
ComputeThisAdjustment(const CXXMethodDecl * MD,CharUnits BaseOffsetInLayoutClass,FinalOverriders::OverriderInfo Overrider)1257 ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
1258     const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
1259     FinalOverriders::OverriderInfo Overrider) {
1260   // Ignore adjustments for pure virtual member functions.
1261   if (Overrider.Method->isPure())
1262     return ThisAdjustment();
1263 
1264   BaseSubobject OverriddenBaseSubobject(MD->getParent(),
1265                                         BaseOffsetInLayoutClass);
1266 
1267   BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),
1268                                        Overrider.Offset);
1269 
1270   // Compute the adjustment offset.
1271   BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject,
1272                                                       OverriderBaseSubobject);
1273   if (Offset.isEmpty())
1274     return ThisAdjustment();
1275 
1276   ThisAdjustment Adjustment;
1277 
1278   if (Offset.VirtualBase) {
1279     // Get the vcall offset map for this virtual base.
1280     VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];
1281 
1282     if (VCallOffsets.empty()) {
1283       // We don't have vcall offsets for this virtual base, go ahead and
1284       // build them.
1285       VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, MostDerivedClass,
1286                                          /*FinalOverriders=*/nullptr,
1287                                          BaseSubobject(Offset.VirtualBase,
1288                                                        CharUnits::Zero()),
1289                                          /*BaseIsVirtual=*/true,
1290                                          /*OffsetInLayoutClass=*/
1291                                              CharUnits::Zero());
1292 
1293       VCallOffsets = Builder.getVCallOffsets();
1294     }
1295 
1296     Adjustment.Virtual.Itanium.VCallOffsetOffset =
1297       VCallOffsets.getVCallOffsetOffset(MD).getQuantity();
1298   }
1299 
1300   // Set the non-virtual part of the adjustment.
1301   Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1302 
1303   return Adjustment;
1304 }
1305 
AddMethod(const CXXMethodDecl * MD,ReturnAdjustment ReturnAdjustment)1306 void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
1307                                      ReturnAdjustment ReturnAdjustment) {
1308   if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1309     assert(ReturnAdjustment.isEmpty() &&
1310            "Destructor can't have return adjustment!");
1311 
1312     // Add both the complete destructor and the deleting destructor.
1313     Components.push_back(VTableComponent::MakeCompleteDtor(DD));
1314     Components.push_back(VTableComponent::MakeDeletingDtor(DD));
1315   } else {
1316     // Add the return adjustment if necessary.
1317     if (!ReturnAdjustment.isEmpty())
1318       VTableThunks[Components.size()].Return = ReturnAdjustment;
1319 
1320     // Add the function.
1321     Components.push_back(VTableComponent::MakeFunction(MD));
1322   }
1323 }
1324 
1325 /// OverridesIndirectMethodInBase - Return whether the given member function
1326 /// overrides any methods in the set of given bases.
1327 /// Unlike OverridesMethodInBase, this checks "overriders of overriders".
1328 /// For example, if we have:
1329 ///
1330 /// struct A { virtual void f(); }
1331 /// struct B : A { virtual void f(); }
1332 /// struct C : B { virtual void f(); }
1333 ///
1334 /// OverridesIndirectMethodInBase will return true if given C::f as the method
1335 /// and { A } as the set of bases.
OverridesIndirectMethodInBases(const CXXMethodDecl * MD,ItaniumVTableBuilder::PrimaryBasesSetVectorTy & Bases)1336 static bool OverridesIndirectMethodInBases(
1337     const CXXMethodDecl *MD,
1338     ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {
1339   if (Bases.count(MD->getParent()))
1340     return true;
1341 
1342   for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
1343        E = MD->end_overridden_methods(); I != E; ++I) {
1344     const CXXMethodDecl *OverriddenMD = *I;
1345 
1346     // Check "indirect overriders".
1347     if (OverridesIndirectMethodInBases(OverriddenMD, Bases))
1348       return true;
1349   }
1350 
1351   return false;
1352 }
1353 
IsOverriderUsed(const CXXMethodDecl * Overrider,CharUnits BaseOffsetInLayoutClass,const CXXRecordDecl * FirstBaseInPrimaryBaseChain,CharUnits FirstBaseOffsetInLayoutClass) const1354 bool ItaniumVTableBuilder::IsOverriderUsed(
1355     const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
1356     const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1357     CharUnits FirstBaseOffsetInLayoutClass) const {
1358   // If the base and the first base in the primary base chain have the same
1359   // offsets, then this overrider will be used.
1360   if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)
1361    return true;
1362 
1363   // We know now that Base (or a direct or indirect base of it) is a primary
1364   // base in part of the class hierarchy, but not a primary base in the most
1365   // derived class.
1366 
1367   // If the overrider is the first base in the primary base chain, we know
1368   // that the overrider will be used.
1369   if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)
1370     return true;
1371 
1372   ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;
1373 
1374   const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;
1375   PrimaryBases.insert(RD);
1376 
1377   // Now traverse the base chain, starting with the first base, until we find
1378   // the base that is no longer a primary base.
1379   while (true) {
1380     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1381     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1382 
1383     if (!PrimaryBase)
1384       break;
1385 
1386     if (Layout.isPrimaryBaseVirtual()) {
1387       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1388              "Primary base should always be at offset 0!");
1389 
1390       const ASTRecordLayout &LayoutClassLayout =
1391         Context.getASTRecordLayout(LayoutClass);
1392 
1393       // Now check if this is the primary base that is not a primary base in the
1394       // most derived class.
1395       if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1396           FirstBaseOffsetInLayoutClass) {
1397         // We found it, stop walking the chain.
1398         break;
1399       }
1400     } else {
1401       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1402              "Primary base should always be at offset 0!");
1403     }
1404 
1405     if (!PrimaryBases.insert(PrimaryBase))
1406       llvm_unreachable("Found a duplicate primary base!");
1407 
1408     RD = PrimaryBase;
1409   }
1410 
1411   // If the final overrider is an override of one of the primary bases,
1412   // then we know that it will be used.
1413   return OverridesIndirectMethodInBases(Overrider, PrimaryBases);
1414 }
1415 
1416 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
1417 
1418 /// FindNearestOverriddenMethod - Given a method, returns the overridden method
1419 /// from the nearest base. Returns null if no method was found.
1420 /// The Bases are expected to be sorted in a base-to-derived order.
1421 static const CXXMethodDecl *
FindNearestOverriddenMethod(const CXXMethodDecl * MD,BasesSetVectorTy & Bases)1422 FindNearestOverriddenMethod(const CXXMethodDecl *MD,
1423                             BasesSetVectorTy &Bases) {
1424   OverriddenMethodsSetTy OverriddenMethods;
1425   ComputeAllOverriddenMethods(MD, OverriddenMethods);
1426 
1427   for (const CXXRecordDecl *PrimaryBase :
1428        llvm::make_range(Bases.rbegin(), Bases.rend())) {
1429     // Now check the overridden methods.
1430     for (const CXXMethodDecl *OverriddenMD : OverriddenMethods) {
1431       // We found our overridden method.
1432       if (OverriddenMD->getParent() == PrimaryBase)
1433         return OverriddenMD;
1434     }
1435   }
1436 
1437   return nullptr;
1438 }
1439 
AddMethods(BaseSubobject Base,CharUnits BaseOffsetInLayoutClass,const CXXRecordDecl * FirstBaseInPrimaryBaseChain,CharUnits FirstBaseOffsetInLayoutClass,PrimaryBasesSetVectorTy & PrimaryBases)1440 void ItaniumVTableBuilder::AddMethods(
1441     BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
1442     const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1443     CharUnits FirstBaseOffsetInLayoutClass,
1444     PrimaryBasesSetVectorTy &PrimaryBases) {
1445   // Itanium C++ ABI 2.5.2:
1446   //   The order of the virtual function pointers in a virtual table is the
1447   //   order of declaration of the corresponding member functions in the class.
1448   //
1449   //   There is an entry for any virtual function declared in a class,
1450   //   whether it is a new function or overrides a base class function,
1451   //   unless it overrides a function from the primary base, and conversion
1452   //   between their return types does not require an adjustment.
1453 
1454   const CXXRecordDecl *RD = Base.getBase();
1455   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1456 
1457   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1458     CharUnits PrimaryBaseOffset;
1459     CharUnits PrimaryBaseOffsetInLayoutClass;
1460     if (Layout.isPrimaryBaseVirtual()) {
1461       assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1462              "Primary vbase should have a zero offset!");
1463 
1464       const ASTRecordLayout &MostDerivedClassLayout =
1465         Context.getASTRecordLayout(MostDerivedClass);
1466 
1467       PrimaryBaseOffset =
1468         MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
1469 
1470       const ASTRecordLayout &LayoutClassLayout =
1471         Context.getASTRecordLayout(LayoutClass);
1472 
1473       PrimaryBaseOffsetInLayoutClass =
1474         LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
1475     } else {
1476       assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1477              "Primary base should have a zero offset!");
1478 
1479       PrimaryBaseOffset = Base.getBaseOffset();
1480       PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;
1481     }
1482 
1483     AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset),
1484                PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain,
1485                FirstBaseOffsetInLayoutClass, PrimaryBases);
1486 
1487     if (!PrimaryBases.insert(PrimaryBase))
1488       llvm_unreachable("Found a duplicate primary base!");
1489   }
1490 
1491   const CXXDestructorDecl *ImplicitVirtualDtor = nullptr;
1492 
1493   typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;
1494   NewVirtualFunctionsTy NewVirtualFunctions;
1495 
1496   // Now go through all virtual member functions and add them.
1497   for (const auto *MD : RD->methods()) {
1498     if (!MD->isVirtual())
1499       continue;
1500     MD = MD->getCanonicalDecl();
1501 
1502     // Get the final overrider.
1503     FinalOverriders::OverriderInfo Overrider =
1504       Overriders.getOverrider(MD, Base.getBaseOffset());
1505 
1506     // Check if this virtual member function overrides a method in a primary
1507     // base. If this is the case, and the return type doesn't require adjustment
1508     // then we can just use the member function from the primary base.
1509     if (const CXXMethodDecl *OverriddenMD =
1510           FindNearestOverriddenMethod(MD, PrimaryBases)) {
1511       if (ComputeReturnAdjustmentBaseOffset(Context, MD,
1512                                             OverriddenMD).isEmpty()) {
1513         // Replace the method info of the overridden method with our own
1514         // method.
1515         assert(MethodInfoMap.count(OverriddenMD) &&
1516                "Did not find the overridden method!");
1517         MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];
1518 
1519         MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1520                               OverriddenMethodInfo.VTableIndex);
1521 
1522         assert(!MethodInfoMap.count(MD) &&
1523                "Should not have method info for this method yet!");
1524 
1525         MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1526         MethodInfoMap.erase(OverriddenMD);
1527 
1528         // If the overridden method exists in a virtual base class or a direct
1529         // or indirect base class of a virtual base class, we need to emit a
1530         // thunk if we ever have a class hierarchy where the base class is not
1531         // a primary base in the complete object.
1532         if (!isBuildingConstructorVTable() && OverriddenMD != MD) {
1533           // Compute the this adjustment.
1534           ThisAdjustment ThisAdjustment =
1535             ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass,
1536                                   Overrider);
1537 
1538           if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&
1539               Overrider.Method->getParent() == MostDerivedClass) {
1540 
1541             // There's no return adjustment from OverriddenMD and MD,
1542             // but that doesn't mean there isn't one between MD and
1543             // the final overrider.
1544             BaseOffset ReturnAdjustmentOffset =
1545               ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
1546             ReturnAdjustment ReturnAdjustment =
1547               ComputeReturnAdjustment(ReturnAdjustmentOffset);
1548 
1549             // This is a virtual thunk for the most derived class, add it.
1550             AddThunk(Overrider.Method,
1551                      ThunkInfo(ThisAdjustment, ReturnAdjustment));
1552           }
1553         }
1554 
1555         continue;
1556       }
1557     }
1558 
1559     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1560       if (MD->isImplicit()) {
1561         // Itanium C++ ABI 2.5.2:
1562         //   If a class has an implicitly-defined virtual destructor,
1563         //   its entries come after the declared virtual function pointers.
1564 
1565         assert(!ImplicitVirtualDtor &&
1566                "Did already see an implicit virtual dtor!");
1567         ImplicitVirtualDtor = DD;
1568         continue;
1569       }
1570     }
1571 
1572     NewVirtualFunctions.push_back(MD);
1573   }
1574 
1575   if (ImplicitVirtualDtor)
1576     NewVirtualFunctions.push_back(ImplicitVirtualDtor);
1577 
1578   for (const CXXMethodDecl *MD : NewVirtualFunctions) {
1579     // Get the final overrider.
1580     FinalOverriders::OverriderInfo Overrider =
1581       Overriders.getOverrider(MD, Base.getBaseOffset());
1582 
1583     // Insert the method info for this method.
1584     MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1585                           Components.size());
1586 
1587     assert(!MethodInfoMap.count(MD) &&
1588            "Should not have method info for this method yet!");
1589     MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1590 
1591     // Check if this overrider is going to be used.
1592     const CXXMethodDecl *OverriderMD = Overrider.Method;
1593     if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass,
1594                          FirstBaseInPrimaryBaseChain,
1595                          FirstBaseOffsetInLayoutClass)) {
1596       Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD));
1597       continue;
1598     }
1599 
1600     // Check if this overrider needs a return adjustment.
1601     // We don't want to do this for pure virtual member functions.
1602     BaseOffset ReturnAdjustmentOffset;
1603     if (!OverriderMD->isPure()) {
1604       ReturnAdjustmentOffset =
1605         ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);
1606     }
1607 
1608     ReturnAdjustment ReturnAdjustment =
1609       ComputeReturnAdjustment(ReturnAdjustmentOffset);
1610 
1611     AddMethod(Overrider.Method, ReturnAdjustment);
1612   }
1613 }
1614 
LayoutVTable()1615 void ItaniumVTableBuilder::LayoutVTable() {
1616   LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass,
1617                                                  CharUnits::Zero()),
1618                                    /*BaseIsMorallyVirtual=*/false,
1619                                    MostDerivedClassIsVirtual,
1620                                    MostDerivedClassOffset);
1621 
1622   VisitedVirtualBasesSetTy VBases;
1623 
1624   // Determine the primary virtual bases.
1625   DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset,
1626                                VBases);
1627   VBases.clear();
1628 
1629   LayoutVTablesForVirtualBases(MostDerivedClass, VBases);
1630 
1631   // -fapple-kext adds an extra entry at end of vtbl.
1632   bool IsAppleKext = Context.getLangOpts().AppleKext;
1633   if (IsAppleKext)
1634     Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));
1635 }
1636 
LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,bool BaseIsMorallyVirtual,bool BaseIsVirtualInLayoutClass,CharUnits OffsetInLayoutClass)1637 void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
1638     BaseSubobject Base, bool BaseIsMorallyVirtual,
1639     bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
1640   assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
1641 
1642   // Add vcall and vbase offsets for this vtable.
1643   VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders,
1644                                      Base, BaseIsVirtualInLayoutClass,
1645                                      OffsetInLayoutClass);
1646   Components.append(Builder.components_begin(), Builder.components_end());
1647 
1648   // Check if we need to add these vcall offsets.
1649   if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {
1650     VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];
1651 
1652     if (VCallOffsets.empty())
1653       VCallOffsets = Builder.getVCallOffsets();
1654   }
1655 
1656   // If we're laying out the most derived class we want to keep track of the
1657   // virtual base class offset offsets.
1658   if (Base.getBase() == MostDerivedClass)
1659     VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();
1660 
1661   // Add the offset to top.
1662   CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;
1663   Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop));
1664 
1665   // Next, add the RTTI.
1666   Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
1667 
1668   uint64_t AddressPoint = Components.size();
1669 
1670   // Now go through all virtual member functions and add them.
1671   PrimaryBasesSetVectorTy PrimaryBases;
1672   AddMethods(Base, OffsetInLayoutClass,
1673              Base.getBase(), OffsetInLayoutClass,
1674              PrimaryBases);
1675 
1676   const CXXRecordDecl *RD = Base.getBase();
1677   if (RD == MostDerivedClass) {
1678     assert(MethodVTableIndices.empty());
1679     for (const auto &I : MethodInfoMap) {
1680       const CXXMethodDecl *MD = I.first;
1681       const MethodInfo &MI = I.second;
1682       if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1683         MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]
1684             = MI.VTableIndex - AddressPoint;
1685         MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]
1686             = MI.VTableIndex + 1 - AddressPoint;
1687       } else {
1688         MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;
1689       }
1690     }
1691   }
1692 
1693   // Compute 'this' pointer adjustments.
1694   ComputeThisAdjustments();
1695 
1696   // Add all address points.
1697   while (true) {
1698     AddressPoints.insert(std::make_pair(
1699       BaseSubobject(RD, OffsetInLayoutClass),
1700       AddressPoint));
1701 
1702     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1703     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1704 
1705     if (!PrimaryBase)
1706       break;
1707 
1708     if (Layout.isPrimaryBaseVirtual()) {
1709       // Check if this virtual primary base is a primary base in the layout
1710       // class. If it's not, we don't want to add it.
1711       const ASTRecordLayout &LayoutClassLayout =
1712         Context.getASTRecordLayout(LayoutClass);
1713 
1714       if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1715           OffsetInLayoutClass) {
1716         // We don't want to add this class (or any of its primary bases).
1717         break;
1718       }
1719     }
1720 
1721     RD = PrimaryBase;
1722   }
1723 
1724   // Layout secondary vtables.
1725   LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);
1726 }
1727 
1728 void
LayoutSecondaryVTables(BaseSubobject Base,bool BaseIsMorallyVirtual,CharUnits OffsetInLayoutClass)1729 ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
1730                                              bool BaseIsMorallyVirtual,
1731                                              CharUnits OffsetInLayoutClass) {
1732   // Itanium C++ ABI 2.5.2:
1733   //   Following the primary virtual table of a derived class are secondary
1734   //   virtual tables for each of its proper base classes, except any primary
1735   //   base(s) with which it shares its primary virtual table.
1736 
1737   const CXXRecordDecl *RD = Base.getBase();
1738   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1739   const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1740 
1741   for (const auto &B : RD->bases()) {
1742     // Ignore virtual bases, we'll emit them later.
1743     if (B.isVirtual())
1744       continue;
1745 
1746     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1747 
1748     // Ignore bases that don't have a vtable.
1749     if (!BaseDecl->isDynamicClass())
1750       continue;
1751 
1752     if (isBuildingConstructorVTable()) {
1753       // Itanium C++ ABI 2.6.4:
1754       //   Some of the base class subobjects may not need construction virtual
1755       //   tables, which will therefore not be present in the construction
1756       //   virtual table group, even though the subobject virtual tables are
1757       //   present in the main virtual table group for the complete object.
1758       if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases())
1759         continue;
1760     }
1761 
1762     // Get the base offset of this base.
1763     CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl);
1764     CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset;
1765 
1766     CharUnits BaseOffsetInLayoutClass =
1767       OffsetInLayoutClass + RelativeBaseOffset;
1768 
1769     // Don't emit a secondary vtable for a primary base. We might however want
1770     // to emit secondary vtables for other bases of this base.
1771     if (BaseDecl == PrimaryBase) {
1772       LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset),
1773                              BaseIsMorallyVirtual, BaseOffsetInLayoutClass);
1774       continue;
1775     }
1776 
1777     // Layout the primary vtable (and any secondary vtables) for this base.
1778     LayoutPrimaryAndSecondaryVTables(
1779       BaseSubobject(BaseDecl, BaseOffset),
1780       BaseIsMorallyVirtual,
1781       /*BaseIsVirtualInLayoutClass=*/false,
1782       BaseOffsetInLayoutClass);
1783   }
1784 }
1785 
DeterminePrimaryVirtualBases(const CXXRecordDecl * RD,CharUnits OffsetInLayoutClass,VisitedVirtualBasesSetTy & VBases)1786 void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
1787     const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
1788     VisitedVirtualBasesSetTy &VBases) {
1789   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1790 
1791   // Check if this base has a primary base.
1792   if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1793 
1794     // Check if it's virtual.
1795     if (Layout.isPrimaryBaseVirtual()) {
1796       bool IsPrimaryVirtualBase = true;
1797 
1798       if (isBuildingConstructorVTable()) {
1799         // Check if the base is actually a primary base in the class we use for
1800         // layout.
1801         const ASTRecordLayout &LayoutClassLayout =
1802           Context.getASTRecordLayout(LayoutClass);
1803 
1804         CharUnits PrimaryBaseOffsetInLayoutClass =
1805           LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
1806 
1807         // We know that the base is not a primary base in the layout class if
1808         // the base offsets are different.
1809         if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)
1810           IsPrimaryVirtualBase = false;
1811       }
1812 
1813       if (IsPrimaryVirtualBase)
1814         PrimaryVirtualBases.insert(PrimaryBase);
1815     }
1816   }
1817 
1818   // Traverse bases, looking for more primary virtual bases.
1819   for (const auto &B : RD->bases()) {
1820     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1821 
1822     CharUnits BaseOffsetInLayoutClass;
1823 
1824     if (B.isVirtual()) {
1825       if (!VBases.insert(BaseDecl).second)
1826         continue;
1827 
1828       const ASTRecordLayout &LayoutClassLayout =
1829         Context.getASTRecordLayout(LayoutClass);
1830 
1831       BaseOffsetInLayoutClass =
1832         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1833     } else {
1834       BaseOffsetInLayoutClass =
1835         OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl);
1836     }
1837 
1838     DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases);
1839   }
1840 }
1841 
LayoutVTablesForVirtualBases(const CXXRecordDecl * RD,VisitedVirtualBasesSetTy & VBases)1842 void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
1843     const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) {
1844   // Itanium C++ ABI 2.5.2:
1845   //   Then come the virtual base virtual tables, also in inheritance graph
1846   //   order, and again excluding primary bases (which share virtual tables with
1847   //   the classes for which they are primary).
1848   for (const auto &B : RD->bases()) {
1849     const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1850 
1851     // Check if this base needs a vtable. (If it's virtual, not a primary base
1852     // of some other class, and we haven't visited it before).
1853     if (B.isVirtual() && BaseDecl->isDynamicClass() &&
1854         !PrimaryVirtualBases.count(BaseDecl) &&
1855         VBases.insert(BaseDecl).second) {
1856       const ASTRecordLayout &MostDerivedClassLayout =
1857         Context.getASTRecordLayout(MostDerivedClass);
1858       CharUnits BaseOffset =
1859         MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
1860 
1861       const ASTRecordLayout &LayoutClassLayout =
1862         Context.getASTRecordLayout(LayoutClass);
1863       CharUnits BaseOffsetInLayoutClass =
1864         LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1865 
1866       LayoutPrimaryAndSecondaryVTables(
1867         BaseSubobject(BaseDecl, BaseOffset),
1868         /*BaseIsMorallyVirtual=*/true,
1869         /*BaseIsVirtualInLayoutClass=*/true,
1870         BaseOffsetInLayoutClass);
1871     }
1872 
1873     // We only need to check the base for virtual base vtables if it actually
1874     // has virtual bases.
1875     if (BaseDecl->getNumVBases())
1876       LayoutVTablesForVirtualBases(BaseDecl, VBases);
1877   }
1878 }
1879 
1880 /// dumpLayout - Dump the vtable layout.
dumpLayout(raw_ostream & Out)1881 void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {
1882   // FIXME: write more tests that actually use the dumpLayout output to prevent
1883   // ItaniumVTableBuilder regressions.
1884 
1885   if (isBuildingConstructorVTable()) {
1886     Out << "Construction vtable for ('";
1887     MostDerivedClass->printQualifiedName(Out);
1888     Out << "', ";
1889     Out << MostDerivedClassOffset.getQuantity() << ") in '";
1890     LayoutClass->printQualifiedName(Out);
1891   } else {
1892     Out << "Vtable for '";
1893     MostDerivedClass->printQualifiedName(Out);
1894   }
1895   Out << "' (" << Components.size() << " entries).\n";
1896 
1897   // Iterate through the address points and insert them into a new map where
1898   // they are keyed by the index and not the base object.
1899   // Since an address point can be shared by multiple subobjects, we use an
1900   // STL multimap.
1901   std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;
1902   for (const auto &AP : AddressPoints) {
1903     const BaseSubobject &Base = AP.first;
1904     uint64_t Index = AP.second;
1905 
1906     AddressPointsByIndex.insert(std::make_pair(Index, Base));
1907   }
1908 
1909   for (unsigned I = 0, E = Components.size(); I != E; ++I) {
1910     uint64_t Index = I;
1911 
1912     Out << llvm::format("%4d | ", I);
1913 
1914     const VTableComponent &Component = Components[I];
1915 
1916     // Dump the component.
1917     switch (Component.getKind()) {
1918 
1919     case VTableComponent::CK_VCallOffset:
1920       Out << "vcall_offset ("
1921           << Component.getVCallOffset().getQuantity()
1922           << ")";
1923       break;
1924 
1925     case VTableComponent::CK_VBaseOffset:
1926       Out << "vbase_offset ("
1927           << Component.getVBaseOffset().getQuantity()
1928           << ")";
1929       break;
1930 
1931     case VTableComponent::CK_OffsetToTop:
1932       Out << "offset_to_top ("
1933           << Component.getOffsetToTop().getQuantity()
1934           << ")";
1935       break;
1936 
1937     case VTableComponent::CK_RTTI:
1938       Component.getRTTIDecl()->printQualifiedName(Out);
1939       Out << " RTTI";
1940       break;
1941 
1942     case VTableComponent::CK_FunctionPointer: {
1943       const CXXMethodDecl *MD = Component.getFunctionDecl();
1944 
1945       std::string Str =
1946         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
1947                                     MD);
1948       Out << Str;
1949       if (MD->isPure())
1950         Out << " [pure]";
1951 
1952       if (MD->isDeleted())
1953         Out << " [deleted]";
1954 
1955       ThunkInfo Thunk = VTableThunks.lookup(I);
1956       if (!Thunk.isEmpty()) {
1957         // If this function pointer has a return adjustment, dump it.
1958         if (!Thunk.Return.isEmpty()) {
1959           Out << "\n       [return adjustment: ";
1960           Out << Thunk.Return.NonVirtual << " non-virtual";
1961 
1962           if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
1963             Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
1964             Out << " vbase offset offset";
1965           }
1966 
1967           Out << ']';
1968         }
1969 
1970         // If this function pointer has a 'this' pointer adjustment, dump it.
1971         if (!Thunk.This.isEmpty()) {
1972           Out << "\n       [this adjustment: ";
1973           Out << Thunk.This.NonVirtual << " non-virtual";
1974 
1975           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
1976             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
1977             Out << " vcall offset offset";
1978           }
1979 
1980           Out << ']';
1981         }
1982       }
1983 
1984       break;
1985     }
1986 
1987     case VTableComponent::CK_CompleteDtorPointer:
1988     case VTableComponent::CK_DeletingDtorPointer: {
1989       bool IsComplete =
1990         Component.getKind() == VTableComponent::CK_CompleteDtorPointer;
1991 
1992       const CXXDestructorDecl *DD = Component.getDestructorDecl();
1993 
1994       DD->printQualifiedName(Out);
1995       if (IsComplete)
1996         Out << "() [complete]";
1997       else
1998         Out << "() [deleting]";
1999 
2000       if (DD->isPure())
2001         Out << " [pure]";
2002 
2003       ThunkInfo Thunk = VTableThunks.lookup(I);
2004       if (!Thunk.isEmpty()) {
2005         // If this destructor has a 'this' pointer adjustment, dump it.
2006         if (!Thunk.This.isEmpty()) {
2007           Out << "\n       [this adjustment: ";
2008           Out << Thunk.This.NonVirtual << " non-virtual";
2009 
2010           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2011             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2012             Out << " vcall offset offset";
2013           }
2014 
2015           Out << ']';
2016         }
2017       }
2018 
2019       break;
2020     }
2021 
2022     case VTableComponent::CK_UnusedFunctionPointer: {
2023       const CXXMethodDecl *MD = Component.getUnusedFunctionDecl();
2024 
2025       std::string Str =
2026         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2027                                     MD);
2028       Out << "[unused] " << Str;
2029       if (MD->isPure())
2030         Out << " [pure]";
2031     }
2032 
2033     }
2034 
2035     Out << '\n';
2036 
2037     // Dump the next address point.
2038     uint64_t NextIndex = Index + 1;
2039     if (AddressPointsByIndex.count(NextIndex)) {
2040       if (AddressPointsByIndex.count(NextIndex) == 1) {
2041         const BaseSubobject &Base =
2042           AddressPointsByIndex.find(NextIndex)->second;
2043 
2044         Out << "       -- (";
2045         Base.getBase()->printQualifiedName(Out);
2046         Out << ", " << Base.getBaseOffset().getQuantity();
2047         Out << ") vtable address --\n";
2048       } else {
2049         CharUnits BaseOffset =
2050           AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset();
2051 
2052         // We store the class names in a set to get a stable order.
2053         std::set<std::string> ClassNames;
2054         for (const auto &I :
2055              llvm::make_range(AddressPointsByIndex.equal_range(NextIndex))) {
2056           assert(I.second.getBaseOffset() == BaseOffset &&
2057                  "Invalid base offset!");
2058           const CXXRecordDecl *RD = I.second.getBase();
2059           ClassNames.insert(RD->getQualifiedNameAsString());
2060         }
2061 
2062         for (const std::string &Name : ClassNames) {
2063           Out << "       -- (" << Name;
2064           Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n";
2065         }
2066       }
2067     }
2068   }
2069 
2070   Out << '\n';
2071 
2072   if (isBuildingConstructorVTable())
2073     return;
2074 
2075   if (MostDerivedClass->getNumVBases()) {
2076     // We store the virtual base class names and their offsets in a map to get
2077     // a stable order.
2078 
2079     std::map<std::string, CharUnits> ClassNamesAndOffsets;
2080     for (const auto &I : VBaseOffsetOffsets) {
2081       std::string ClassName = I.first->getQualifiedNameAsString();
2082       CharUnits OffsetOffset = I.second;
2083       ClassNamesAndOffsets.insert(std::make_pair(ClassName, OffsetOffset));
2084     }
2085 
2086     Out << "Virtual base offset offsets for '";
2087     MostDerivedClass->printQualifiedName(Out);
2088     Out << "' (";
2089     Out << ClassNamesAndOffsets.size();
2090     Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n";
2091 
2092     for (const auto &I : ClassNamesAndOffsets)
2093       Out << "   " << I.first << " | " << I.second.getQuantity() << '\n';
2094 
2095     Out << "\n";
2096   }
2097 
2098   if (!Thunks.empty()) {
2099     // We store the method names in a map to get a stable order.
2100     std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
2101 
2102     for (const auto &I : Thunks) {
2103       const CXXMethodDecl *MD = I.first;
2104       std::string MethodName =
2105         PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2106                                     MD);
2107 
2108       MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
2109     }
2110 
2111     for (const auto &I : MethodNamesAndDecls) {
2112       const std::string &MethodName = I.first;
2113       const CXXMethodDecl *MD = I.second;
2114 
2115       ThunkInfoVectorTy ThunksVector = Thunks[MD];
2116       std::sort(ThunksVector.begin(), ThunksVector.end(),
2117                 [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
2118         assert(LHS.Method == nullptr && RHS.Method == nullptr);
2119         return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
2120       });
2121 
2122       Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
2123       Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
2124 
2125       for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
2126         const ThunkInfo &Thunk = ThunksVector[I];
2127 
2128         Out << llvm::format("%4d | ", I);
2129 
2130         // If this function pointer has a return pointer adjustment, dump it.
2131         if (!Thunk.Return.isEmpty()) {
2132           Out << "return adjustment: " << Thunk.Return.NonVirtual;
2133           Out << " non-virtual";
2134           if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
2135             Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
2136             Out << " vbase offset offset";
2137           }
2138 
2139           if (!Thunk.This.isEmpty())
2140             Out << "\n       ";
2141         }
2142 
2143         // If this function pointer has a 'this' pointer adjustment, dump it.
2144         if (!Thunk.This.isEmpty()) {
2145           Out << "this adjustment: ";
2146           Out << Thunk.This.NonVirtual << " non-virtual";
2147 
2148           if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2149             Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2150             Out << " vcall offset offset";
2151           }
2152         }
2153 
2154         Out << '\n';
2155       }
2156 
2157       Out << '\n';
2158     }
2159   }
2160 
2161   // Compute the vtable indices for all the member functions.
2162   // Store them in a map keyed by the index so we'll get a sorted table.
2163   std::map<uint64_t, std::string> IndicesMap;
2164 
2165   for (const auto *MD : MostDerivedClass->methods()) {
2166     // We only want virtual member functions.
2167     if (!MD->isVirtual())
2168       continue;
2169     MD = MD->getCanonicalDecl();
2170 
2171     std::string MethodName =
2172       PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2173                                   MD);
2174 
2175     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2176       GlobalDecl GD(DD, Dtor_Complete);
2177       assert(MethodVTableIndices.count(GD));
2178       uint64_t VTableIndex = MethodVTableIndices[GD];
2179       IndicesMap[VTableIndex] = MethodName + " [complete]";
2180       IndicesMap[VTableIndex + 1] = MethodName + " [deleting]";
2181     } else {
2182       assert(MethodVTableIndices.count(MD));
2183       IndicesMap[MethodVTableIndices[MD]] = MethodName;
2184     }
2185   }
2186 
2187   // Print the vtable indices for all the member functions.
2188   if (!IndicesMap.empty()) {
2189     Out << "VTable indices for '";
2190     MostDerivedClass->printQualifiedName(Out);
2191     Out << "' (" << IndicesMap.size() << " entries).\n";
2192 
2193     for (const auto &I : IndicesMap) {
2194       uint64_t VTableIndex = I.first;
2195       const std::string &MethodName = I.second;
2196 
2197       Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName
2198           << '\n';
2199     }
2200   }
2201 
2202   Out << '\n';
2203 }
2204 }
2205 
VTableLayout(uint64_t NumVTableComponents,const VTableComponent * VTableComponents,uint64_t NumVTableThunks,const VTableThunkTy * VTableThunks,const AddressPointsMapTy & AddressPoints,bool IsMicrosoftABI)2206 VTableLayout::VTableLayout(uint64_t NumVTableComponents,
2207                            const VTableComponent *VTableComponents,
2208                            uint64_t NumVTableThunks,
2209                            const VTableThunkTy *VTableThunks,
2210                            const AddressPointsMapTy &AddressPoints,
2211                            bool IsMicrosoftABI)
2212   : NumVTableComponents(NumVTableComponents),
2213     VTableComponents(new VTableComponent[NumVTableComponents]),
2214     NumVTableThunks(NumVTableThunks),
2215     VTableThunks(new VTableThunkTy[NumVTableThunks]),
2216     AddressPoints(AddressPoints),
2217     IsMicrosoftABI(IsMicrosoftABI) {
2218   std::copy(VTableComponents, VTableComponents+NumVTableComponents,
2219             this->VTableComponents.get());
2220   std::copy(VTableThunks, VTableThunks+NumVTableThunks,
2221             this->VTableThunks.get());
2222   std::sort(this->VTableThunks.get(),
2223             this->VTableThunks.get() + NumVTableThunks,
2224             [](const VTableLayout::VTableThunkTy &LHS,
2225                const VTableLayout::VTableThunkTy &RHS) {
2226     assert((LHS.first != RHS.first || LHS.second == RHS.second) &&
2227            "Different thunks should have unique indices!");
2228     return LHS.first < RHS.first;
2229   });
2230 }
2231 
~VTableLayout()2232 VTableLayout::~VTableLayout() { }
2233 
ItaniumVTableContext(ASTContext & Context)2234 ItaniumVTableContext::ItaniumVTableContext(ASTContext &Context)
2235     : VTableContextBase(/*MS=*/false) {}
2236 
~ItaniumVTableContext()2237 ItaniumVTableContext::~ItaniumVTableContext() {
2238   llvm::DeleteContainerSeconds(VTableLayouts);
2239 }
2240 
getMethodVTableIndex(GlobalDecl GD)2241 uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {
2242   MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD);
2243   if (I != MethodVTableIndices.end())
2244     return I->second;
2245 
2246   const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
2247 
2248   computeVTableRelatedInformation(RD);
2249 
2250   I = MethodVTableIndices.find(GD);
2251   assert(I != MethodVTableIndices.end() && "Did not find index!");
2252   return I->second;
2253 }
2254 
2255 CharUnits
getVirtualBaseOffsetOffset(const CXXRecordDecl * RD,const CXXRecordDecl * VBase)2256 ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
2257                                                  const CXXRecordDecl *VBase) {
2258   ClassPairTy ClassPair(RD, VBase);
2259 
2260   VirtualBaseClassOffsetOffsetsMapTy::iterator I =
2261     VirtualBaseClassOffsetOffsets.find(ClassPair);
2262   if (I != VirtualBaseClassOffsetOffsets.end())
2263     return I->second;
2264 
2265   VCallAndVBaseOffsetBuilder Builder(RD, RD, /*FinalOverriders=*/nullptr,
2266                                      BaseSubobject(RD, CharUnits::Zero()),
2267                                      /*BaseIsVirtual=*/false,
2268                                      /*OffsetInLayoutClass=*/CharUnits::Zero());
2269 
2270   for (const auto &I : Builder.getVBaseOffsetOffsets()) {
2271     // Insert all types.
2272     ClassPairTy ClassPair(RD, I.first);
2273 
2274     VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));
2275   }
2276 
2277   I = VirtualBaseClassOffsetOffsets.find(ClassPair);
2278   assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");
2279 
2280   return I->second;
2281 }
2282 
CreateVTableLayout(const ItaniumVTableBuilder & Builder)2283 static VTableLayout *CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
2284   SmallVector<VTableLayout::VTableThunkTy, 1>
2285     VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
2286 
2287   return new VTableLayout(Builder.getNumVTableComponents(),
2288                           Builder.vtable_component_begin(),
2289                           VTableThunks.size(),
2290                           VTableThunks.data(),
2291                           Builder.getAddressPoints(),
2292                           /*IsMicrosoftABI=*/false);
2293 }
2294 
2295 void
computeVTableRelatedInformation(const CXXRecordDecl * RD)2296 ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
2297   const VTableLayout *&Entry = VTableLayouts[RD];
2298 
2299   // Check if we've computed this information before.
2300   if (Entry)
2301     return;
2302 
2303   ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),
2304                                /*MostDerivedClassIsVirtual=*/0, RD);
2305   Entry = CreateVTableLayout(Builder);
2306 
2307   MethodVTableIndices.insert(Builder.vtable_indices_begin(),
2308                              Builder.vtable_indices_end());
2309 
2310   // Add the known thunks.
2311   Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
2312 
2313   // If we don't have the vbase information for this class, insert it.
2314   // getVirtualBaseOffsetOffset will compute it separately without computing
2315   // the rest of the vtable related information.
2316   if (!RD->getNumVBases())
2317     return;
2318 
2319   const CXXRecordDecl *VBase =
2320     RD->vbases_begin()->getType()->getAsCXXRecordDecl();
2321 
2322   if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase)))
2323     return;
2324 
2325   for (const auto &I : Builder.getVBaseOffsetOffsets()) {
2326     // Insert all types.
2327     ClassPairTy ClassPair(RD, I.first);
2328 
2329     VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));
2330   }
2331 }
2332 
createConstructionVTableLayout(const CXXRecordDecl * MostDerivedClass,CharUnits MostDerivedClassOffset,bool MostDerivedClassIsVirtual,const CXXRecordDecl * LayoutClass)2333 VTableLayout *ItaniumVTableContext::createConstructionVTableLayout(
2334     const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
2335     bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {
2336   ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,
2337                                MostDerivedClassIsVirtual, LayoutClass);
2338   return CreateVTableLayout(Builder);
2339 }
2340 
2341 namespace {
2342 
2343 // Vtables in the Microsoft ABI are different from the Itanium ABI.
2344 //
2345 // The main differences are:
2346 //  1. Separate vftable and vbtable.
2347 //
2348 //  2. Each subobject with a vfptr gets its own vftable rather than an address
2349 //     point in a single vtable shared between all the subobjects.
2350 //     Each vftable is represented by a separate section and virtual calls
2351 //     must be done using the vftable which has a slot for the function to be
2352 //     called.
2353 //
2354 //  3. Virtual method definitions expect their 'this' parameter to point to the
2355 //     first vfptr whose table provides a compatible overridden method.  In many
2356 //     cases, this permits the original vf-table entry to directly call
2357 //     the method instead of passing through a thunk.
2358 //     See example before VFTableBuilder::ComputeThisOffset below.
2359 //
2360 //     A compatible overridden method is one which does not have a non-trivial
2361 //     covariant-return adjustment.
2362 //
2363 //     The first vfptr is the one with the lowest offset in the complete-object
2364 //     layout of the defining class, and the method definition will subtract
2365 //     that constant offset from the parameter value to get the real 'this'
2366 //     value.  Therefore, if the offset isn't really constant (e.g. if a virtual
2367 //     function defined in a virtual base is overridden in a more derived
2368 //     virtual base and these bases have a reverse order in the complete
2369 //     object), the vf-table may require a this-adjustment thunk.
2370 //
2371 //  4. vftables do not contain new entries for overrides that merely require
2372 //     this-adjustment.  Together with #3, this keeps vf-tables smaller and
2373 //     eliminates the need for this-adjustment thunks in many cases, at the cost
2374 //     of often requiring redundant work to adjust the "this" pointer.
2375 //
2376 //  5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.
2377 //     Vtordisps are emitted into the class layout if a class has
2378 //      a) a user-defined ctor/dtor
2379 //     and
2380 //      b) a method overriding a method in a virtual base.
2381 //
2382 //  To get a better understanding of this code,
2383 //  you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp
2384 
2385 class VFTableBuilder {
2386 public:
2387   typedef MicrosoftVTableContext::MethodVFTableLocation MethodVFTableLocation;
2388 
2389   typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
2390     MethodVFTableLocationsTy;
2391 
2392   typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator>
2393     method_locations_range;
2394 
2395 private:
2396   /// VTables - Global vtable information.
2397   MicrosoftVTableContext &VTables;
2398 
2399   /// Context - The ASTContext which we will use for layout information.
2400   ASTContext &Context;
2401 
2402   /// MostDerivedClass - The most derived class for which we're building this
2403   /// vtable.
2404   const CXXRecordDecl *MostDerivedClass;
2405 
2406   const ASTRecordLayout &MostDerivedClassLayout;
2407 
2408   const VPtrInfo &WhichVFPtr;
2409 
2410   /// FinalOverriders - The final overriders of the most derived class.
2411   const FinalOverriders Overriders;
2412 
2413   /// Components - The components of the vftable being built.
2414   SmallVector<VTableComponent, 64> Components;
2415 
2416   MethodVFTableLocationsTy MethodVFTableLocations;
2417 
2418   /// \brief Does this class have an RTTI component?
2419   bool HasRTTIComponent;
2420 
2421   /// MethodInfo - Contains information about a method in a vtable.
2422   /// (Used for computing 'this' pointer adjustment thunks.
2423   struct MethodInfo {
2424     /// VBTableIndex - The nonzero index in the vbtable that
2425     /// this method's base has, or zero.
2426     const uint64_t VBTableIndex;
2427 
2428     /// VFTableIndex - The index in the vftable that this method has.
2429     const uint64_t VFTableIndex;
2430 
2431     /// Shadowed - Indicates if this vftable slot is shadowed by
2432     /// a slot for a covariant-return override. If so, it shouldn't be printed
2433     /// or used for vcalls in the most derived class.
2434     bool Shadowed;
2435 
2436     /// UsesExtraSlot - Indicates if this vftable slot was created because
2437     /// any of the overridden slots required a return adjusting thunk.
2438     bool UsesExtraSlot;
2439 
MethodInfo__anon5d32d09d0511::VFTableBuilder::MethodInfo2440     MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex,
2441                bool UsesExtraSlot = false)
2442         : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),
2443           Shadowed(false), UsesExtraSlot(UsesExtraSlot) {}
2444 
MethodInfo__anon5d32d09d0511::VFTableBuilder::MethodInfo2445     MethodInfo()
2446         : VBTableIndex(0), VFTableIndex(0), Shadowed(false),
2447           UsesExtraSlot(false) {}
2448   };
2449 
2450   typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
2451 
2452   /// MethodInfoMap - The information for all methods in the vftable we're
2453   /// currently building.
2454   MethodInfoMapTy MethodInfoMap;
2455 
2456   typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
2457 
2458   /// VTableThunks - The thunks by vftable index in the vftable currently being
2459   /// built.
2460   VTableThunksMapTy VTableThunks;
2461 
2462   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
2463   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
2464 
2465   /// Thunks - A map that contains all the thunks needed for all methods in the
2466   /// most derived class for which the vftable is currently being built.
2467   ThunksMapTy Thunks;
2468 
2469   /// AddThunk - Add a thunk for the given method.
AddThunk(const CXXMethodDecl * MD,const ThunkInfo & Thunk)2470   void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) {
2471     SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD];
2472 
2473     // Check if we have this thunk already.
2474     if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) !=
2475         ThunksVector.end())
2476       return;
2477 
2478     ThunksVector.push_back(Thunk);
2479   }
2480 
2481   /// ComputeThisOffset - Returns the 'this' argument offset for the given
2482   /// method, relative to the beginning of the MostDerivedClass.
2483   CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider);
2484 
2485   void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,
2486                                    CharUnits ThisOffset, ThisAdjustment &TA);
2487 
2488   /// AddMethod - Add a single virtual member function to the vftable
2489   /// components vector.
AddMethod(const CXXMethodDecl * MD,ThunkInfo TI)2490   void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {
2491     if (!TI.isEmpty()) {
2492       VTableThunks[Components.size()] = TI;
2493       AddThunk(MD, TI);
2494     }
2495     if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2496       assert(TI.Return.isEmpty() &&
2497              "Destructor can't have return adjustment!");
2498       Components.push_back(VTableComponent::MakeDeletingDtor(DD));
2499     } else {
2500       Components.push_back(VTableComponent::MakeFunction(MD));
2501     }
2502   }
2503 
2504   /// AddMethods - Add the methods of this base subobject and the relevant
2505   /// subbases to the vftable we're currently laying out.
2506   void AddMethods(BaseSubobject Base, unsigned BaseDepth,
2507                   const CXXRecordDecl *LastVBase,
2508                   BasesSetVectorTy &VisitedBases);
2509 
LayoutVFTable()2510   void LayoutVFTable() {
2511     // RTTI data goes before all other entries.
2512     if (HasRTTIComponent)
2513       Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
2514 
2515     BasesSetVectorTy VisitedBases;
2516     AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr,
2517                VisitedBases);
2518     assert((HasRTTIComponent ? Components.size() - 1 : Components.size()) &&
2519            "vftable can't be empty");
2520 
2521     assert(MethodVFTableLocations.empty());
2522     for (const auto &I : MethodInfoMap) {
2523       const CXXMethodDecl *MD = I.first;
2524       const MethodInfo &MI = I.second;
2525       // Skip the methods that the MostDerivedClass didn't override
2526       // and the entries shadowed by return adjusting thunks.
2527       if (MD->getParent() != MostDerivedClass || MI.Shadowed)
2528         continue;
2529       MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),
2530                                 WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);
2531       if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2532         MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;
2533       } else {
2534         MethodVFTableLocations[MD] = Loc;
2535       }
2536     }
2537   }
2538 
2539 public:
VFTableBuilder(MicrosoftVTableContext & VTables,const CXXRecordDecl * MostDerivedClass,const VPtrInfo * Which)2540   VFTableBuilder(MicrosoftVTableContext &VTables,
2541                  const CXXRecordDecl *MostDerivedClass, const VPtrInfo *Which)
2542       : VTables(VTables),
2543         Context(MostDerivedClass->getASTContext()),
2544         MostDerivedClass(MostDerivedClass),
2545         MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)),
2546         WhichVFPtr(*Which),
2547         Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) {
2548     // Only include the RTTI component if we know that we will provide a
2549     // definition of the vftable.
2550     HasRTTIComponent = Context.getLangOpts().RTTIData &&
2551                        !MostDerivedClass->hasAttr<DLLImportAttr>() &&
2552                        MostDerivedClass->getTemplateSpecializationKind() !=
2553                            TSK_ExplicitInstantiationDeclaration;
2554 
2555     LayoutVFTable();
2556 
2557     if (Context.getLangOpts().DumpVTableLayouts)
2558       dumpLayout(llvm::outs());
2559   }
2560 
getNumThunks() const2561   uint64_t getNumThunks() const { return Thunks.size(); }
2562 
thunks_begin() const2563   ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
2564 
thunks_end() const2565   ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
2566 
vtable_locations() const2567   method_locations_range vtable_locations() const {
2568     return method_locations_range(MethodVFTableLocations.begin(),
2569                                   MethodVFTableLocations.end());
2570   }
2571 
getNumVTableComponents() const2572   uint64_t getNumVTableComponents() const { return Components.size(); }
2573 
vtable_component_begin() const2574   const VTableComponent *vtable_component_begin() const {
2575     return Components.begin();
2576   }
2577 
vtable_component_end() const2578   const VTableComponent *vtable_component_end() const {
2579     return Components.end();
2580   }
2581 
vtable_thunks_begin() const2582   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
2583     return VTableThunks.begin();
2584   }
2585 
vtable_thunks_end() const2586   VTableThunksMapTy::const_iterator vtable_thunks_end() const {
2587     return VTableThunks.end();
2588   }
2589 
2590   void dumpLayout(raw_ostream &);
2591 };
2592 
2593 } // end namespace
2594 
2595 // Let's study one class hierarchy as an example:
2596 //   struct A {
2597 //     virtual void f();
2598 //     int x;
2599 //   };
2600 //
2601 //   struct B : virtual A {
2602 //     virtual void f();
2603 //   };
2604 //
2605 // Record layouts:
2606 //   struct A:
2607 //   0 |   (A vftable pointer)
2608 //   4 |   int x
2609 //
2610 //   struct B:
2611 //   0 |   (B vbtable pointer)
2612 //   4 |   struct A (virtual base)
2613 //   4 |     (A vftable pointer)
2614 //   8 |     int x
2615 //
2616 // Let's assume we have a pointer to the A part of an object of dynamic type B:
2617 //   B b;
2618 //   A *a = (A*)&b;
2619 //   a->f();
2620 //
2621 // In this hierarchy, f() belongs to the vftable of A, so B::f() expects
2622 // "this" parameter to point at the A subobject, which is B+4.
2623 // In the B::f() prologue, it adjusts "this" back to B by subtracting 4,
2624 // performed as a *static* adjustment.
2625 //
2626 // Interesting thing happens when we alter the relative placement of A and B
2627 // subobjects in a class:
2628 //   struct C : virtual B { };
2629 //
2630 //   C c;
2631 //   A *a = (A*)&c;
2632 //   a->f();
2633 //
2634 // Respective record layout is:
2635 //   0 |   (C vbtable pointer)
2636 //   4 |   struct A (virtual base)
2637 //   4 |     (A vftable pointer)
2638 //   8 |     int x
2639 //  12 |   struct B (virtual base)
2640 //  12 |     (B vbtable pointer)
2641 //
2642 // The final overrider of f() in class C is still B::f(), so B+4 should be
2643 // passed as "this" to that code.  However, "a" points at B-8, so the respective
2644 // vftable entry should hold a thunk that adds 12 to the "this" argument before
2645 // performing a tail call to B::f().
2646 //
2647 // With this example in mind, we can now calculate the 'this' argument offset
2648 // for the given method, relative to the beginning of the MostDerivedClass.
2649 CharUnits
ComputeThisOffset(FinalOverriders::OverriderInfo Overrider)2650 VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {
2651   BasesSetVectorTy Bases;
2652 
2653   {
2654     // Find the set of least derived bases that define the given method.
2655     OverriddenMethodsSetTy VisitedOverriddenMethods;
2656     auto InitialOverriddenDefinitionCollector = [&](
2657         const CXXMethodDecl *OverriddenMD) {
2658       if (OverriddenMD->size_overridden_methods() == 0)
2659         Bases.insert(OverriddenMD->getParent());
2660       // Don't recurse on this method if we've already collected it.
2661       return VisitedOverriddenMethods.insert(OverriddenMD).second;
2662     };
2663     visitAllOverriddenMethods(Overrider.Method,
2664                               InitialOverriddenDefinitionCollector);
2665   }
2666 
2667   // If there are no overrides then 'this' is located
2668   // in the base that defines the method.
2669   if (Bases.size() == 0)
2670     return Overrider.Offset;
2671 
2672   CXXBasePaths Paths;
2673   Overrider.Method->getParent()->lookupInBases(
2674       [&Bases](const CXXBaseSpecifier *Specifier, CXXBasePath &) {
2675         return Bases.count(Specifier->getType()->getAsCXXRecordDecl());
2676       },
2677       Paths);
2678 
2679   // This will hold the smallest this offset among overridees of MD.
2680   // This implies that an offset of a non-virtual base will dominate an offset
2681   // of a virtual base to potentially reduce the number of thunks required
2682   // in the derived classes that inherit this method.
2683   CharUnits Ret;
2684   bool First = true;
2685 
2686   const ASTRecordLayout &OverriderRDLayout =
2687       Context.getASTRecordLayout(Overrider.Method->getParent());
2688   for (const CXXBasePath &Path : Paths) {
2689     CharUnits ThisOffset = Overrider.Offset;
2690     CharUnits LastVBaseOffset;
2691 
2692     // For each path from the overrider to the parents of the overridden
2693     // methods, traverse the path, calculating the this offset in the most
2694     // derived class.
2695     for (const CXXBasePathElement &Element : Path) {
2696       QualType CurTy = Element.Base->getType();
2697       const CXXRecordDecl *PrevRD = Element.Class,
2698                           *CurRD = CurTy->getAsCXXRecordDecl();
2699       const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);
2700 
2701       if (Element.Base->isVirtual()) {
2702         // The interesting things begin when you have virtual inheritance.
2703         // The final overrider will use a static adjustment equal to the offset
2704         // of the vbase in the final overrider class.
2705         // For example, if the final overrider is in a vbase B of the most
2706         // derived class and it overrides a method of the B's own vbase A,
2707         // it uses A* as "this".  In its prologue, it can cast A* to B* with
2708         // a static offset.  This offset is used regardless of the actual
2709         // offset of A from B in the most derived class, requiring an
2710         // this-adjusting thunk in the vftable if A and B are laid out
2711         // differently in the most derived class.
2712         LastVBaseOffset = ThisOffset =
2713             Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD);
2714       } else {
2715         ThisOffset += Layout.getBaseClassOffset(CurRD);
2716       }
2717     }
2718 
2719     if (isa<CXXDestructorDecl>(Overrider.Method)) {
2720       if (LastVBaseOffset.isZero()) {
2721         // If a "Base" class has at least one non-virtual base with a virtual
2722         // destructor, the "Base" virtual destructor will take the address
2723         // of the "Base" subobject as the "this" argument.
2724         ThisOffset = Overrider.Offset;
2725       } else {
2726         // A virtual destructor of a virtual base takes the address of the
2727         // virtual base subobject as the "this" argument.
2728         ThisOffset = LastVBaseOffset;
2729       }
2730     }
2731 
2732     if (Ret > ThisOffset || First) {
2733       First = false;
2734       Ret = ThisOffset;
2735     }
2736   }
2737 
2738   assert(!First && "Method not found in the given subobject?");
2739   return Ret;
2740 }
2741 
2742 // Things are getting even more complex when the "this" adjustment has to
2743 // use a dynamic offset instead of a static one, or even two dynamic offsets.
2744 // This is sometimes required when a virtual call happens in the middle of
2745 // a non-most-derived class construction or destruction.
2746 //
2747 // Let's take a look at the following example:
2748 //   struct A {
2749 //     virtual void f();
2750 //   };
2751 //
2752 //   void foo(A *a) { a->f(); }  // Knows nothing about siblings of A.
2753 //
2754 //   struct B : virtual A {
2755 //     virtual void f();
2756 //     B() {
2757 //       foo(this);
2758 //     }
2759 //   };
2760 //
2761 //   struct C : virtual B {
2762 //     virtual void f();
2763 //   };
2764 //
2765 // Record layouts for these classes are:
2766 //   struct A
2767 //   0 |   (A vftable pointer)
2768 //
2769 //   struct B
2770 //   0 |   (B vbtable pointer)
2771 //   4 |   (vtordisp for vbase A)
2772 //   8 |   struct A (virtual base)
2773 //   8 |     (A vftable pointer)
2774 //
2775 //   struct C
2776 //   0 |   (C vbtable pointer)
2777 //   4 |   (vtordisp for vbase A)
2778 //   8 |   struct A (virtual base)  // A precedes B!
2779 //   8 |     (A vftable pointer)
2780 //  12 |   struct B (virtual base)
2781 //  12 |     (B vbtable pointer)
2782 //
2783 // When one creates an object of type C, the C constructor:
2784 // - initializes all the vbptrs, then
2785 // - calls the A subobject constructor
2786 //   (initializes A's vfptr with an address of A vftable), then
2787 // - calls the B subobject constructor
2788 //   (initializes A's vfptr with an address of B vftable and vtordisp for A),
2789 //   that in turn calls foo(), then
2790 // - initializes A's vfptr with an address of C vftable and zeroes out the
2791 //   vtordisp
2792 //   FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable
2793 //   without vtordisp thunks?
2794 //   FIXME: how are vtordisp handled in the presence of nooverride/final?
2795 //
2796 // When foo() is called, an object with a layout of class C has a vftable
2797 // referencing B::f() that assumes a B layout, so the "this" adjustments are
2798 // incorrect, unless an extra adjustment is done.  This adjustment is called
2799 // "vtordisp adjustment".  Vtordisp basically holds the difference between the
2800 // actual location of a vbase in the layout class and the location assumed by
2801 // the vftable of the class being constructed/destructed.  Vtordisp is only
2802 // needed if "this" escapes a
2803 // structor (or we can't prove otherwise).
2804 // [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an
2805 // estimation of a dynamic adjustment]
2806 //
2807 // foo() gets a pointer to the A vbase and doesn't know anything about B or C,
2808 // so it just passes that pointer as "this" in a virtual call.
2809 // If there was no vtordisp, that would just dispatch to B::f().
2810 // However, B::f() assumes B+8 is passed as "this",
2811 // yet the pointer foo() passes along is B-4 (i.e. C+8).
2812 // An extra adjustment is needed, so we emit a thunk into the B vftable.
2813 // This vtordisp thunk subtracts the value of vtordisp
2814 // from the "this" argument (-12) before making a tailcall to B::f().
2815 //
2816 // Let's consider an even more complex example:
2817 //   struct D : virtual B, virtual C {
2818 //     D() {
2819 //       foo(this);
2820 //     }
2821 //   };
2822 //
2823 //   struct D
2824 //   0 |   (D vbtable pointer)
2825 //   4 |   (vtordisp for vbase A)
2826 //   8 |   struct A (virtual base)  // A precedes both B and C!
2827 //   8 |     (A vftable pointer)
2828 //  12 |   struct B (virtual base)  // B precedes C!
2829 //  12 |     (B vbtable pointer)
2830 //  16 |   struct C (virtual base)
2831 //  16 |     (C vbtable pointer)
2832 //
2833 // When D::D() calls foo(), we find ourselves in a thunk that should tailcall
2834 // to C::f(), which assumes C+8 as its "this" parameter.  This time, foo()
2835 // passes along A, which is C-8.  The A vtordisp holds
2836 //   "D.vbptr[index_of_A] - offset_of_A_in_D"
2837 // and we statically know offset_of_A_in_D, so can get a pointer to D.
2838 // When we know it, we can make an extra vbtable lookup to locate the C vbase
2839 // and one extra static adjustment to calculate the expected value of C+8.
CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,CharUnits ThisOffset,ThisAdjustment & TA)2840 void VFTableBuilder::CalculateVtordispAdjustment(
2841     FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,
2842     ThisAdjustment &TA) {
2843   const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap =
2844       MostDerivedClassLayout.getVBaseOffsetsMap();
2845   const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry =
2846       VBaseMap.find(WhichVFPtr.getVBaseWithVPtr());
2847   assert(VBaseMapEntry != VBaseMap.end());
2848 
2849   // If there's no vtordisp or the final overrider is defined in the same vbase
2850   // as the initial declaration, we don't need any vtordisp adjustment.
2851   if (!VBaseMapEntry->second.hasVtorDisp() ||
2852       Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())
2853     return;
2854 
2855   // OK, now we know we need to use a vtordisp thunk.
2856   // The implicit vtordisp field is located right before the vbase.
2857   CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset;
2858   TA.Virtual.Microsoft.VtordispOffset =
2859       (OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4;
2860 
2861   // A simple vtordisp thunk will suffice if the final overrider is defined
2862   // in either the most derived class or its non-virtual base.
2863   if (Overrider.Method->getParent() == MostDerivedClass ||
2864       !Overrider.VirtualBase)
2865     return;
2866 
2867   // Otherwise, we need to do use the dynamic offset of the final overrider
2868   // in order to get "this" adjustment right.
2869   TA.Virtual.Microsoft.VBPtrOffset =
2870       (OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset -
2871        MostDerivedClassLayout.getVBPtrOffset()).getQuantity();
2872   TA.Virtual.Microsoft.VBOffsetOffset =
2873       Context.getTypeSizeInChars(Context.IntTy).getQuantity() *
2874       VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase);
2875 
2876   TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity();
2877 }
2878 
GroupNewVirtualOverloads(const CXXRecordDecl * RD,SmallVector<const CXXMethodDecl *,10> & VirtualMethods)2879 static void GroupNewVirtualOverloads(
2880     const CXXRecordDecl *RD,
2881     SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) {
2882   // Put the virtual methods into VirtualMethods in the proper order:
2883   // 1) Group overloads by declaration name. New groups are added to the
2884   //    vftable in the order of their first declarations in this class
2885   //    (including overrides, non-virtual methods and any other named decl that
2886   //    might be nested within the class).
2887   // 2) In each group, new overloads appear in the reverse order of declaration.
2888   typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;
2889   SmallVector<MethodGroup, 10> Groups;
2890   typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;
2891   VisitedGroupIndicesTy VisitedGroupIndices;
2892   for (const auto *D : RD->decls()) {
2893     const auto *ND = dyn_cast<NamedDecl>(D);
2894     if (!ND)
2895       continue;
2896     VisitedGroupIndicesTy::iterator J;
2897     bool Inserted;
2898     std::tie(J, Inserted) = VisitedGroupIndices.insert(
2899         std::make_pair(ND->getDeclName(), Groups.size()));
2900     if (Inserted)
2901       Groups.push_back(MethodGroup());
2902     if (const auto *MD = dyn_cast<CXXMethodDecl>(ND))
2903       if (MD->isVirtual())
2904         Groups[J->second].push_back(MD->getCanonicalDecl());
2905   }
2906 
2907   for (const MethodGroup &Group : Groups)
2908     VirtualMethods.append(Group.rbegin(), Group.rend());
2909 }
2910 
isDirectVBase(const CXXRecordDecl * Base,const CXXRecordDecl * RD)2911 static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {
2912   for (const auto &B : RD->bases()) {
2913     if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base)
2914       return true;
2915   }
2916   return false;
2917 }
2918 
AddMethods(BaseSubobject Base,unsigned BaseDepth,const CXXRecordDecl * LastVBase,BasesSetVectorTy & VisitedBases)2919 void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
2920                                 const CXXRecordDecl *LastVBase,
2921                                 BasesSetVectorTy &VisitedBases) {
2922   const CXXRecordDecl *RD = Base.getBase();
2923   if (!RD->isPolymorphic())
2924     return;
2925 
2926   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
2927 
2928   // See if this class expands a vftable of the base we look at, which is either
2929   // the one defined by the vfptr base path or the primary base of the current
2930   // class.
2931   const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;
2932   CharUnits NextBaseOffset;
2933   if (BaseDepth < WhichVFPtr.PathToBaseWithVPtr.size()) {
2934     NextBase = WhichVFPtr.PathToBaseWithVPtr[BaseDepth];
2935     if (isDirectVBase(NextBase, RD)) {
2936       NextLastVBase = NextBase;
2937       NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase);
2938     } else {
2939       NextBaseOffset =
2940           Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase);
2941     }
2942   } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
2943     assert(!Layout.isPrimaryBaseVirtual() &&
2944            "No primary virtual bases in this ABI");
2945     NextBase = PrimaryBase;
2946     NextBaseOffset = Base.getBaseOffset();
2947   }
2948 
2949   if (NextBase) {
2950     AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1,
2951                NextLastVBase, VisitedBases);
2952     if (!VisitedBases.insert(NextBase))
2953       llvm_unreachable("Found a duplicate primary base!");
2954   }
2955 
2956   SmallVector<const CXXMethodDecl*, 10> VirtualMethods;
2957   // Put virtual methods in the proper order.
2958   GroupNewVirtualOverloads(RD, VirtualMethods);
2959 
2960   // Now go through all virtual member functions and add them to the current
2961   // vftable. This is done by
2962   //  - replacing overridden methods in their existing slots, as long as they
2963   //    don't require return adjustment; calculating This adjustment if needed.
2964   //  - adding new slots for methods of the current base not present in any
2965   //    sub-bases;
2966   //  - adding new slots for methods that require Return adjustment.
2967   // We keep track of the methods visited in the sub-bases in MethodInfoMap.
2968   for (const CXXMethodDecl *MD : VirtualMethods) {
2969     FinalOverriders::OverriderInfo FinalOverrider =
2970         Overriders.getOverrider(MD, Base.getBaseOffset());
2971     const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method;
2972     const CXXMethodDecl *OverriddenMD =
2973         FindNearestOverriddenMethod(MD, VisitedBases);
2974 
2975     ThisAdjustment ThisAdjustmentOffset;
2976     bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false;
2977     CharUnits ThisOffset = ComputeThisOffset(FinalOverrider);
2978     ThisAdjustmentOffset.NonVirtual =
2979         (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();
2980     if ((OverriddenMD || FinalOverriderMD != MD) &&
2981         WhichVFPtr.getVBaseWithVPtr())
2982       CalculateVtordispAdjustment(FinalOverrider, ThisOffset,
2983                                   ThisAdjustmentOffset);
2984 
2985     if (OverriddenMD) {
2986       // If MD overrides anything in this vftable, we need to update the
2987       // entries.
2988       MethodInfoMapTy::iterator OverriddenMDIterator =
2989           MethodInfoMap.find(OverriddenMD);
2990 
2991       // If the overridden method went to a different vftable, skip it.
2992       if (OverriddenMDIterator == MethodInfoMap.end())
2993         continue;
2994 
2995       MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;
2996 
2997       // Let's check if the overrider requires any return adjustments.
2998       // We must create a new slot if the MD's return type is not trivially
2999       // convertible to the OverriddenMD's one.
3000       // Once a chain of method overrides adds a return adjusting vftable slot,
3001       // all subsequent overrides will also use an extra method slot.
3002       ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset(
3003                                   Context, MD, OverriddenMD).isEmpty() ||
3004                              OverriddenMethodInfo.UsesExtraSlot;
3005 
3006       if (!ReturnAdjustingThunk) {
3007         // No return adjustment needed - just replace the overridden method info
3008         // with the current info.
3009         MethodInfo MI(OverriddenMethodInfo.VBTableIndex,
3010                       OverriddenMethodInfo.VFTableIndex);
3011         MethodInfoMap.erase(OverriddenMDIterator);
3012 
3013         assert(!MethodInfoMap.count(MD) &&
3014                "Should not have method info for this method yet!");
3015         MethodInfoMap.insert(std::make_pair(MD, MI));
3016         continue;
3017       }
3018 
3019       // In case we need a return adjustment, we'll add a new slot for
3020       // the overrider. Mark the overriden method as shadowed by the new slot.
3021       OverriddenMethodInfo.Shadowed = true;
3022 
3023       // Force a special name mangling for a return-adjusting thunk
3024       // unless the method is the final overrider without this adjustment.
3025       ForceReturnAdjustmentMangling =
3026           !(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty());
3027     } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||
3028                MD->size_overridden_methods()) {
3029       // Skip methods that don't belong to the vftable of the current class,
3030       // e.g. each method that wasn't seen in any of the visited sub-bases
3031       // but overrides multiple methods of other sub-bases.
3032       continue;
3033     }
3034 
3035     // If we got here, MD is a method not seen in any of the sub-bases or
3036     // it requires return adjustment. Insert the method info for this method.
3037     unsigned VBIndex =
3038         LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0;
3039     MethodInfo MI(VBIndex,
3040                   HasRTTIComponent ? Components.size() - 1 : Components.size(),
3041                   ReturnAdjustingThunk);
3042 
3043     assert(!MethodInfoMap.count(MD) &&
3044            "Should not have method info for this method yet!");
3045     MethodInfoMap.insert(std::make_pair(MD, MI));
3046 
3047     // Check if this overrider needs a return adjustment.
3048     // We don't want to do this for pure virtual member functions.
3049     BaseOffset ReturnAdjustmentOffset;
3050     ReturnAdjustment ReturnAdjustment;
3051     if (!FinalOverriderMD->isPure()) {
3052       ReturnAdjustmentOffset =
3053           ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD);
3054     }
3055     if (!ReturnAdjustmentOffset.isEmpty()) {
3056       ForceReturnAdjustmentMangling = true;
3057       ReturnAdjustment.NonVirtual =
3058           ReturnAdjustmentOffset.NonVirtualOffset.getQuantity();
3059       if (ReturnAdjustmentOffset.VirtualBase) {
3060         const ASTRecordLayout &DerivedLayout =
3061             Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass);
3062         ReturnAdjustment.Virtual.Microsoft.VBPtrOffset =
3063             DerivedLayout.getVBPtrOffset().getQuantity();
3064         ReturnAdjustment.Virtual.Microsoft.VBIndex =
3065             VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass,
3066                                     ReturnAdjustmentOffset.VirtualBase);
3067       }
3068     }
3069 
3070     AddMethod(FinalOverriderMD,
3071               ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment,
3072                         ForceReturnAdjustmentMangling ? MD : nullptr));
3073   }
3074 }
3075 
PrintBasePath(const VPtrInfo::BasePath & Path,raw_ostream & Out)3076 static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {
3077   for (const CXXRecordDecl *Elem :
3078        llvm::make_range(Path.rbegin(), Path.rend())) {
3079     Out << "'";
3080     Elem->printQualifiedName(Out);
3081     Out << "' in ";
3082   }
3083 }
3084 
dumpMicrosoftThunkAdjustment(const ThunkInfo & TI,raw_ostream & Out,bool ContinueFirstLine)3085 static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
3086                                          bool ContinueFirstLine) {
3087   const ReturnAdjustment &R = TI.Return;
3088   bool Multiline = false;
3089   const char *LinePrefix = "\n       ";
3090   if (!R.isEmpty() || TI.Method) {
3091     if (!ContinueFirstLine)
3092       Out << LinePrefix;
3093     Out << "[return adjustment (to type '"
3094         << TI.Method->getReturnType().getCanonicalType().getAsString()
3095         << "'): ";
3096     if (R.Virtual.Microsoft.VBPtrOffset)
3097       Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";
3098     if (R.Virtual.Microsoft.VBIndex)
3099       Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";
3100     Out << R.NonVirtual << " non-virtual]";
3101     Multiline = true;
3102   }
3103 
3104   const ThisAdjustment &T = TI.This;
3105   if (!T.isEmpty()) {
3106     if (Multiline || !ContinueFirstLine)
3107       Out << LinePrefix;
3108     Out << "[this adjustment: ";
3109     if (!TI.This.Virtual.isEmpty()) {
3110       assert(T.Virtual.Microsoft.VtordispOffset < 0);
3111       Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";
3112       if (T.Virtual.Microsoft.VBPtrOffset) {
3113         Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset
3114             << " to the left,";
3115         assert(T.Virtual.Microsoft.VBOffsetOffset > 0);
3116         Out << LinePrefix << " vboffset at "
3117             << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";
3118       }
3119     }
3120     Out << T.NonVirtual << " non-virtual]";
3121   }
3122 }
3123 
dumpLayout(raw_ostream & Out)3124 void VFTableBuilder::dumpLayout(raw_ostream &Out) {
3125   Out << "VFTable for ";
3126   PrintBasePath(WhichVFPtr.PathToBaseWithVPtr, Out);
3127   Out << "'";
3128   MostDerivedClass->printQualifiedName(Out);
3129   Out << "' (" << Components.size()
3130       << (Components.size() == 1 ? " entry" : " entries") << ").\n";
3131 
3132   for (unsigned I = 0, E = Components.size(); I != E; ++I) {
3133     Out << llvm::format("%4d | ", I);
3134 
3135     const VTableComponent &Component = Components[I];
3136 
3137     // Dump the component.
3138     switch (Component.getKind()) {
3139     case VTableComponent::CK_RTTI:
3140       Component.getRTTIDecl()->printQualifiedName(Out);
3141       Out << " RTTI";
3142       break;
3143 
3144     case VTableComponent::CK_FunctionPointer: {
3145       const CXXMethodDecl *MD = Component.getFunctionDecl();
3146 
3147       // FIXME: Figure out how to print the real thunk type, since they can
3148       // differ in the return type.
3149       std::string Str = PredefinedExpr::ComputeName(
3150           PredefinedExpr::PrettyFunctionNoVirtual, MD);
3151       Out << Str;
3152       if (MD->isPure())
3153         Out << " [pure]";
3154 
3155       if (MD->isDeleted())
3156         Out << " [deleted]";
3157 
3158       ThunkInfo Thunk = VTableThunks.lookup(I);
3159       if (!Thunk.isEmpty())
3160         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3161 
3162       break;
3163     }
3164 
3165     case VTableComponent::CK_DeletingDtorPointer: {
3166       const CXXDestructorDecl *DD = Component.getDestructorDecl();
3167 
3168       DD->printQualifiedName(Out);
3169       Out << "() [scalar deleting]";
3170 
3171       if (DD->isPure())
3172         Out << " [pure]";
3173 
3174       ThunkInfo Thunk = VTableThunks.lookup(I);
3175       if (!Thunk.isEmpty()) {
3176         assert(Thunk.Return.isEmpty() &&
3177                "No return adjustment needed for destructors!");
3178         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3179       }
3180 
3181       break;
3182     }
3183 
3184     default:
3185       DiagnosticsEngine &Diags = Context.getDiagnostics();
3186       unsigned DiagID = Diags.getCustomDiagID(
3187           DiagnosticsEngine::Error,
3188           "Unexpected vftable component type %0 for component number %1");
3189       Diags.Report(MostDerivedClass->getLocation(), DiagID)
3190           << I << Component.getKind();
3191     }
3192 
3193     Out << '\n';
3194   }
3195 
3196   Out << '\n';
3197 
3198   if (!Thunks.empty()) {
3199     // We store the method names in a map to get a stable order.
3200     std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
3201 
3202     for (const auto &I : Thunks) {
3203       const CXXMethodDecl *MD = I.first;
3204       std::string MethodName = PredefinedExpr::ComputeName(
3205           PredefinedExpr::PrettyFunctionNoVirtual, MD);
3206 
3207       MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
3208     }
3209 
3210     for (const auto &MethodNameAndDecl : MethodNamesAndDecls) {
3211       const std::string &MethodName = MethodNameAndDecl.first;
3212       const CXXMethodDecl *MD = MethodNameAndDecl.second;
3213 
3214       ThunkInfoVectorTy ThunksVector = Thunks[MD];
3215       std::stable_sort(ThunksVector.begin(), ThunksVector.end(),
3216                        [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
3217         // Keep different thunks with the same adjustments in the order they
3218         // were put into the vector.
3219         return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
3220       });
3221 
3222       Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
3223       Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
3224 
3225       for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
3226         const ThunkInfo &Thunk = ThunksVector[I];
3227 
3228         Out << llvm::format("%4d | ", I);
3229         dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true);
3230         Out << '\n';
3231       }
3232 
3233       Out << '\n';
3234     }
3235   }
3236 
3237   Out.flush();
3238 }
3239 
setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *,4> & A,ArrayRef<const CXXRecordDecl * > B)3240 static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
3241                           ArrayRef<const CXXRecordDecl *> B) {
3242   for (const CXXRecordDecl *Decl : B) {
3243     if (A.count(Decl))
3244       return true;
3245   }
3246   return false;
3247 }
3248 
3249 static bool rebucketPaths(VPtrInfoVector &Paths);
3250 
3251 /// Produces MSVC-compatible vbtable data.  The symbols produced by this
3252 /// algorithm match those produced by MSVC 2012 and newer, which is different
3253 /// from MSVC 2010.
3254 ///
3255 /// MSVC 2012 appears to minimize the vbtable names using the following
3256 /// algorithm.  First, walk the class hierarchy in the usual order, depth first,
3257 /// left to right, to find all of the subobjects which contain a vbptr field.
3258 /// Visiting each class node yields a list of inheritance paths to vbptrs.  Each
3259 /// record with a vbptr creates an initially empty path.
3260 ///
3261 /// To combine paths from child nodes, the paths are compared to check for
3262 /// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of
3263 /// components in the same order.  Each group of ambiguous paths is extended by
3264 /// appending the class of the base from which it came.  If the current class
3265 /// node produced an ambiguous path, its path is extended with the current class.
3266 /// After extending paths, MSVC again checks for ambiguity, and extends any
3267 /// ambiguous path which wasn't already extended.  Because each node yields an
3268 /// unambiguous set of paths, MSVC doesn't need to extend any path more than once
3269 /// to produce an unambiguous set of paths.
3270 ///
3271 /// TODO: Presumably vftables use the same algorithm.
computeVTablePaths(bool ForVBTables,const CXXRecordDecl * RD,VPtrInfoVector & Paths)3272 void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
3273                                                 const CXXRecordDecl *RD,
3274                                                 VPtrInfoVector &Paths) {
3275   assert(Paths.empty());
3276   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3277 
3278   // Base case: this subobject has its own vptr.
3279   if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr())
3280     Paths.push_back(new VPtrInfo(RD));
3281 
3282   // Recursive case: get all the vbtables from our bases and remove anything
3283   // that shares a virtual base.
3284   llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
3285   for (const auto &B : RD->bases()) {
3286     const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
3287     if (B.isVirtual() && VBasesSeen.count(Base))
3288       continue;
3289 
3290     if (!Base->isDynamicClass())
3291       continue;
3292 
3293     const VPtrInfoVector &BasePaths =
3294         ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base);
3295 
3296     for (VPtrInfo *BaseInfo : BasePaths) {
3297       // Don't include the path if it goes through a virtual base that we've
3298       // already included.
3299       if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases))
3300         continue;
3301 
3302       // Copy the path and adjust it as necessary.
3303       VPtrInfo *P = new VPtrInfo(*BaseInfo);
3304 
3305       // We mangle Base into the path if the path would've been ambiguous and it
3306       // wasn't already extended with Base.
3307       if (P->MangledPath.empty() || P->MangledPath.back() != Base)
3308         P->NextBaseToMangle = Base;
3309 
3310       // Keep track of which vtable the derived class is going to extend with
3311       // new methods or bases.  We append to either the vftable of our primary
3312       // base, or the first non-virtual base that has a vbtable.
3313       if (P->ReusingBase == Base &&
3314           Base == (ForVBTables ? Layout.getBaseSharingVBPtr()
3315                                : Layout.getPrimaryBase()))
3316         P->ReusingBase = RD;
3317 
3318       // Keep track of the full adjustment from the MDC to this vtable.  The
3319       // adjustment is captured by an optional vbase and a non-virtual offset.
3320       if (B.isVirtual())
3321         P->ContainingVBases.push_back(Base);
3322       else if (P->ContainingVBases.empty())
3323         P->NonVirtualOffset += Layout.getBaseClassOffset(Base);
3324 
3325       // Update the full offset in the MDC.
3326       P->FullOffsetInMDC = P->NonVirtualOffset;
3327       if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())
3328         P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB);
3329 
3330       Paths.push_back(P);
3331     }
3332 
3333     if (B.isVirtual())
3334       VBasesSeen.insert(Base);
3335 
3336     // After visiting any direct base, we've transitively visited all of its
3337     // morally virtual bases.
3338     for (const auto &VB : Base->vbases())
3339       VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl());
3340   }
3341 
3342   // Sort the paths into buckets, and if any of them are ambiguous, extend all
3343   // paths in ambiguous buckets.
3344   bool Changed = true;
3345   while (Changed)
3346     Changed = rebucketPaths(Paths);
3347 }
3348 
extendPath(VPtrInfo * P)3349 static bool extendPath(VPtrInfo *P) {
3350   if (P->NextBaseToMangle) {
3351     P->MangledPath.push_back(P->NextBaseToMangle);
3352     P->NextBaseToMangle = nullptr;// Prevent the path from being extended twice.
3353     return true;
3354   }
3355   return false;
3356 }
3357 
rebucketPaths(VPtrInfoVector & Paths)3358 static bool rebucketPaths(VPtrInfoVector &Paths) {
3359   // What we're essentially doing here is bucketing together ambiguous paths.
3360   // Any bucket with more than one path in it gets extended by NextBase, which
3361   // is usually the direct base of the inherited the vbptr.  This code uses a
3362   // sorted vector to implement a multiset to form the buckets.  Note that the
3363   // ordering is based on pointers, but it doesn't change our output order.  The
3364   // current algorithm is designed to match MSVC 2012's names.
3365   VPtrInfoVector PathsSorted(Paths);
3366   std::sort(PathsSorted.begin(), PathsSorted.end(),
3367             [](const VPtrInfo *LHS, const VPtrInfo *RHS) {
3368     return LHS->MangledPath < RHS->MangledPath;
3369   });
3370   bool Changed = false;
3371   for (size_t I = 0, E = PathsSorted.size(); I != E;) {
3372     // Scan forward to find the end of the bucket.
3373     size_t BucketStart = I;
3374     do {
3375       ++I;
3376     } while (I != E && PathsSorted[BucketStart]->MangledPath ==
3377                            PathsSorted[I]->MangledPath);
3378 
3379     // If this bucket has multiple paths, extend them all.
3380     if (I - BucketStart > 1) {
3381       for (size_t II = BucketStart; II != I; ++II)
3382         Changed |= extendPath(PathsSorted[II]);
3383       assert(Changed && "no paths were extended to fix ambiguity");
3384     }
3385   }
3386   return Changed;
3387 }
3388 
~MicrosoftVTableContext()3389 MicrosoftVTableContext::~MicrosoftVTableContext() {
3390   for (auto &P : VFPtrLocations)
3391     llvm::DeleteContainerPointers(*P.second);
3392   llvm::DeleteContainerSeconds(VFPtrLocations);
3393   llvm::DeleteContainerSeconds(VFTableLayouts);
3394   llvm::DeleteContainerSeconds(VBaseInfo);
3395 }
3396 
3397 namespace {
3398 typedef llvm::SetVector<BaseSubobject, std::vector<BaseSubobject>,
3399                         llvm::DenseSet<BaseSubobject>> FullPathTy;
3400 }
3401 
3402 // This recursive function finds all paths from a subobject centered at
3403 // (RD, Offset) to the subobject located at BaseWithVPtr.
findPathsToSubobject(ASTContext & Context,const ASTRecordLayout & MostDerivedLayout,const CXXRecordDecl * RD,CharUnits Offset,BaseSubobject BaseWithVPtr,FullPathTy & FullPath,std::list<FullPathTy> & Paths)3404 static void findPathsToSubobject(ASTContext &Context,
3405                                  const ASTRecordLayout &MostDerivedLayout,
3406                                  const CXXRecordDecl *RD, CharUnits Offset,
3407                                  BaseSubobject BaseWithVPtr,
3408                                  FullPathTy &FullPath,
3409                                  std::list<FullPathTy> &Paths) {
3410   if (BaseSubobject(RD, Offset) == BaseWithVPtr) {
3411     Paths.push_back(FullPath);
3412     return;
3413   }
3414 
3415   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3416 
3417   for (const CXXBaseSpecifier &BS : RD->bases()) {
3418     const CXXRecordDecl *Base = BS.getType()->getAsCXXRecordDecl();
3419     CharUnits NewOffset = BS.isVirtual()
3420                               ? MostDerivedLayout.getVBaseClassOffset(Base)
3421                               : Offset + Layout.getBaseClassOffset(Base);
3422     FullPath.insert(BaseSubobject(Base, NewOffset));
3423     findPathsToSubobject(Context, MostDerivedLayout, Base, NewOffset,
3424                          BaseWithVPtr, FullPath, Paths);
3425     FullPath.pop_back();
3426   }
3427 }
3428 
3429 // Return the paths which are not subsets of other paths.
removeRedundantPaths(std::list<FullPathTy> & FullPaths)3430 static void removeRedundantPaths(std::list<FullPathTy> &FullPaths) {
3431   FullPaths.remove_if([&](const FullPathTy &SpecificPath) {
3432     for (const FullPathTy &OtherPath : FullPaths) {
3433       if (&SpecificPath == &OtherPath)
3434         continue;
3435       if (std::all_of(SpecificPath.begin(), SpecificPath.end(),
3436                       [&](const BaseSubobject &BSO) {
3437                         return OtherPath.count(BSO) != 0;
3438                       })) {
3439         return true;
3440       }
3441     }
3442     return false;
3443   });
3444 }
3445 
getOffsetOfFullPath(ASTContext & Context,const CXXRecordDecl * RD,const FullPathTy & FullPath)3446 static CharUnits getOffsetOfFullPath(ASTContext &Context,
3447                                      const CXXRecordDecl *RD,
3448                                      const FullPathTy &FullPath) {
3449   const ASTRecordLayout &MostDerivedLayout =
3450       Context.getASTRecordLayout(RD);
3451   CharUnits Offset = CharUnits::fromQuantity(-1);
3452   for (const BaseSubobject &BSO : FullPath) {
3453     const CXXRecordDecl *Base = BSO.getBase();
3454     // The first entry in the path is always the most derived record, skip it.
3455     if (Base == RD) {
3456       assert(Offset.getQuantity() == -1);
3457       Offset = CharUnits::Zero();
3458       continue;
3459     }
3460     assert(Offset.getQuantity() != -1);
3461     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3462     // While we know which base has to be traversed, we don't know if that base
3463     // was a virtual base.
3464     const CXXBaseSpecifier *BaseBS = std::find_if(
3465         RD->bases_begin(), RD->bases_end(), [&](const CXXBaseSpecifier &BS) {
3466           return BS.getType()->getAsCXXRecordDecl() == Base;
3467         });
3468     Offset = BaseBS->isVirtual() ? MostDerivedLayout.getVBaseClassOffset(Base)
3469                                  : Offset + Layout.getBaseClassOffset(Base);
3470     RD = Base;
3471   }
3472   return Offset;
3473 }
3474 
3475 // We want to select the path which introduces the most covariant overrides.  If
3476 // two paths introduce overrides which the other path doesn't contain, issue a
3477 // diagnostic.
selectBestPath(ASTContext & Context,const CXXRecordDecl * RD,VPtrInfo * Info,std::list<FullPathTy> & FullPaths)3478 static const FullPathTy *selectBestPath(ASTContext &Context,
3479                                         const CXXRecordDecl *RD, VPtrInfo *Info,
3480                                         std::list<FullPathTy> &FullPaths) {
3481   // Handle some easy cases first.
3482   if (FullPaths.empty())
3483     return nullptr;
3484   if (FullPaths.size() == 1)
3485     return &FullPaths.front();
3486 
3487   const FullPathTy *BestPath = nullptr;
3488   typedef std::set<const CXXMethodDecl *> OverriderSetTy;
3489   OverriderSetTy LastOverrides;
3490   for (const FullPathTy &SpecificPath : FullPaths) {
3491     assert(!SpecificPath.empty());
3492     OverriderSetTy CurrentOverrides;
3493     const CXXRecordDecl *TopLevelRD = SpecificPath.begin()->getBase();
3494     // Find the distance from the start of the path to the subobject with the
3495     // VPtr.
3496     CharUnits BaseOffset =
3497         getOffsetOfFullPath(Context, TopLevelRD, SpecificPath);
3498     FinalOverriders Overriders(TopLevelRD, CharUnits::Zero(), TopLevelRD);
3499     for (const CXXMethodDecl *MD : Info->BaseWithVPtr->methods()) {
3500       if (!MD->isVirtual())
3501         continue;
3502       FinalOverriders::OverriderInfo OI =
3503           Overriders.getOverrider(MD->getCanonicalDecl(), BaseOffset);
3504       const CXXMethodDecl *OverridingMethod = OI.Method;
3505       // Only overriders which have a return adjustment introduce problematic
3506       // thunks.
3507       if (ComputeReturnAdjustmentBaseOffset(Context, OverridingMethod, MD)
3508               .isEmpty())
3509         continue;
3510       // It's possible that the overrider isn't in this path.  If so, skip it
3511       // because this path didn't introduce it.
3512       const CXXRecordDecl *OverridingParent = OverridingMethod->getParent();
3513       if (std::none_of(SpecificPath.begin(), SpecificPath.end(),
3514                        [&](const BaseSubobject &BSO) {
3515                          return BSO.getBase() == OverridingParent;
3516                        }))
3517         continue;
3518       CurrentOverrides.insert(OverridingMethod);
3519     }
3520     OverriderSetTy NewOverrides =
3521         llvm::set_difference(CurrentOverrides, LastOverrides);
3522     if (NewOverrides.empty())
3523       continue;
3524     OverriderSetTy MissingOverrides =
3525         llvm::set_difference(LastOverrides, CurrentOverrides);
3526     if (MissingOverrides.empty()) {
3527       // This path is a strict improvement over the last path, let's use it.
3528       BestPath = &SpecificPath;
3529       std::swap(CurrentOverrides, LastOverrides);
3530     } else {
3531       // This path introduces an overrider with a conflicting covariant thunk.
3532       DiagnosticsEngine &Diags = Context.getDiagnostics();
3533       const CXXMethodDecl *CovariantMD = *NewOverrides.begin();
3534       const CXXMethodDecl *ConflictMD = *MissingOverrides.begin();
3535       Diags.Report(RD->getLocation(), diag::err_vftable_ambiguous_component)
3536           << RD;
3537       Diags.Report(CovariantMD->getLocation(), diag::note_covariant_thunk)
3538           << CovariantMD;
3539       Diags.Report(ConflictMD->getLocation(), diag::note_covariant_thunk)
3540           << ConflictMD;
3541     }
3542   }
3543   // Go with the path that introduced the most covariant overrides.  If there is
3544   // no such path, pick the first path.
3545   return BestPath ? BestPath : &FullPaths.front();
3546 }
3547 
computeFullPathsForVFTables(ASTContext & Context,const CXXRecordDecl * RD,VPtrInfoVector & Paths)3548 static void computeFullPathsForVFTables(ASTContext &Context,
3549                                         const CXXRecordDecl *RD,
3550                                         VPtrInfoVector &Paths) {
3551   const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD);
3552   FullPathTy FullPath;
3553   std::list<FullPathTy> FullPaths;
3554   for (VPtrInfo *Info : Paths) {
3555     findPathsToSubobject(
3556         Context, MostDerivedLayout, RD, CharUnits::Zero(),
3557         BaseSubobject(Info->BaseWithVPtr, Info->FullOffsetInMDC), FullPath,
3558         FullPaths);
3559     FullPath.clear();
3560     removeRedundantPaths(FullPaths);
3561     Info->PathToBaseWithVPtr.clear();
3562     if (const FullPathTy *BestPath =
3563             selectBestPath(Context, RD, Info, FullPaths))
3564       for (const BaseSubobject &BSO : *BestPath)
3565         Info->PathToBaseWithVPtr.push_back(BSO.getBase());
3566     FullPaths.clear();
3567   }
3568 }
3569 
computeVTableRelatedInformation(const CXXRecordDecl * RD)3570 void MicrosoftVTableContext::computeVTableRelatedInformation(
3571     const CXXRecordDecl *RD) {
3572   assert(RD->isDynamicClass());
3573 
3574   // Check if we've computed this information before.
3575   if (VFPtrLocations.count(RD))
3576     return;
3577 
3578   const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;
3579 
3580   VPtrInfoVector *VFPtrs = new VPtrInfoVector();
3581   computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs);
3582   computeFullPathsForVFTables(Context, RD, *VFPtrs);
3583   VFPtrLocations[RD] = VFPtrs;
3584 
3585   MethodVFTableLocationsTy NewMethodLocations;
3586   for (const VPtrInfo *VFPtr : *VFPtrs) {
3587     VFTableBuilder Builder(*this, RD, VFPtr);
3588 
3589     VFTableIdTy id(RD, VFPtr->FullOffsetInMDC);
3590     assert(VFTableLayouts.count(id) == 0);
3591     SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
3592         Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
3593     VFTableLayouts[id] = new VTableLayout(
3594         Builder.getNumVTableComponents(), Builder.vtable_component_begin(),
3595         VTableThunks.size(), VTableThunks.data(), EmptyAddressPointsMap, true);
3596     Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
3597 
3598     for (const auto &Loc : Builder.vtable_locations()) {
3599       GlobalDecl GD = Loc.first;
3600       MethodVFTableLocation NewLoc = Loc.second;
3601       auto M = NewMethodLocations.find(GD);
3602       if (M == NewMethodLocations.end() || NewLoc < M->second)
3603         NewMethodLocations[GD] = NewLoc;
3604     }
3605   }
3606 
3607   MethodVFTableLocations.insert(NewMethodLocations.begin(),
3608                                 NewMethodLocations.end());
3609   if (Context.getLangOpts().DumpVTableLayouts)
3610     dumpMethodLocations(RD, NewMethodLocations, llvm::outs());
3611 }
3612 
dumpMethodLocations(const CXXRecordDecl * RD,const MethodVFTableLocationsTy & NewMethods,raw_ostream & Out)3613 void MicrosoftVTableContext::dumpMethodLocations(
3614     const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
3615     raw_ostream &Out) {
3616   // Compute the vtable indices for all the member functions.
3617   // Store them in a map keyed by the location so we'll get a sorted table.
3618   std::map<MethodVFTableLocation, std::string> IndicesMap;
3619   bool HasNonzeroOffset = false;
3620 
3621   for (const auto &I : NewMethods) {
3622     const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I.first.getDecl());
3623     assert(MD->isVirtual());
3624 
3625     std::string MethodName = PredefinedExpr::ComputeName(
3626         PredefinedExpr::PrettyFunctionNoVirtual, MD);
3627 
3628     if (isa<CXXDestructorDecl>(MD)) {
3629       IndicesMap[I.second] = MethodName + " [scalar deleting]";
3630     } else {
3631       IndicesMap[I.second] = MethodName;
3632     }
3633 
3634     if (!I.second.VFPtrOffset.isZero() || I.second.VBTableIndex != 0)
3635       HasNonzeroOffset = true;
3636   }
3637 
3638   // Print the vtable indices for all the member functions.
3639   if (!IndicesMap.empty()) {
3640     Out << "VFTable indices for ";
3641     Out << "'";
3642     RD->printQualifiedName(Out);
3643     Out << "' (" << IndicesMap.size()
3644         << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n";
3645 
3646     CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1);
3647     uint64_t LastVBIndex = 0;
3648     for (const auto &I : IndicesMap) {
3649       CharUnits VFPtrOffset = I.first.VFPtrOffset;
3650       uint64_t VBIndex = I.first.VBTableIndex;
3651       if (HasNonzeroOffset &&
3652           (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) {
3653         assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);
3654         Out << " -- accessible via ";
3655         if (VBIndex)
3656           Out << "vbtable index " << VBIndex << ", ";
3657         Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";
3658         LastVFPtrOffset = VFPtrOffset;
3659         LastVBIndex = VBIndex;
3660       }
3661 
3662       uint64_t VTableIndex = I.first.Index;
3663       const std::string &MethodName = I.second;
3664       Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n';
3665     }
3666     Out << '\n';
3667   }
3668 
3669   Out.flush();
3670 }
3671 
computeVBTableRelatedInformation(const CXXRecordDecl * RD)3672 const VirtualBaseInfo *MicrosoftVTableContext::computeVBTableRelatedInformation(
3673     const CXXRecordDecl *RD) {
3674   VirtualBaseInfo *VBI;
3675 
3676   {
3677     // Get or create a VBI for RD.  Don't hold a reference to the DenseMap cell,
3678     // as it may be modified and rehashed under us.
3679     VirtualBaseInfo *&Entry = VBaseInfo[RD];
3680     if (Entry)
3681       return Entry;
3682     Entry = VBI = new VirtualBaseInfo();
3683   }
3684 
3685   computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths);
3686 
3687   // First, see if the Derived class shared the vbptr with a non-virtual base.
3688   const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3689   if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {
3690     // If the Derived class shares the vbptr with a non-virtual base, the shared
3691     // virtual bases come first so that the layout is the same.
3692     const VirtualBaseInfo *BaseInfo =
3693         computeVBTableRelatedInformation(VBPtrBase);
3694     VBI->VBTableIndices.insert(BaseInfo->VBTableIndices.begin(),
3695                                BaseInfo->VBTableIndices.end());
3696   }
3697 
3698   // New vbases are added to the end of the vbtable.
3699   // Skip the self entry and vbases visited in the non-virtual base, if any.
3700   unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();
3701   for (const auto &VB : RD->vbases()) {
3702     const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();
3703     if (!VBI->VBTableIndices.count(CurVBase))
3704       VBI->VBTableIndices[CurVBase] = VBTableIndex++;
3705   }
3706 
3707   return VBI;
3708 }
3709 
getVBTableIndex(const CXXRecordDecl * Derived,const CXXRecordDecl * VBase)3710 unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
3711                                                  const CXXRecordDecl *VBase) {
3712   const VirtualBaseInfo *VBInfo = computeVBTableRelatedInformation(Derived);
3713   assert(VBInfo->VBTableIndices.count(VBase));
3714   return VBInfo->VBTableIndices.find(VBase)->second;
3715 }
3716 
3717 const VPtrInfoVector &
enumerateVBTables(const CXXRecordDecl * RD)3718 MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
3719   return computeVBTableRelatedInformation(RD)->VBPtrPaths;
3720 }
3721 
3722 const VPtrInfoVector &
getVFPtrOffsets(const CXXRecordDecl * RD)3723 MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {
3724   computeVTableRelatedInformation(RD);
3725 
3726   assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");
3727   return *VFPtrLocations[RD];
3728 }
3729 
3730 const VTableLayout &
getVFTableLayout(const CXXRecordDecl * RD,CharUnits VFPtrOffset)3731 MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
3732                                          CharUnits VFPtrOffset) {
3733   computeVTableRelatedInformation(RD);
3734 
3735   VFTableIdTy id(RD, VFPtrOffset);
3736   assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");
3737   return *VFTableLayouts[id];
3738 }
3739 
3740 const MicrosoftVTableContext::MethodVFTableLocation &
getMethodVFTableLocation(GlobalDecl GD)3741 MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {
3742   assert(cast<CXXMethodDecl>(GD.getDecl())->isVirtual() &&
3743          "Only use this method for virtual methods or dtors");
3744   if (isa<CXXDestructorDecl>(GD.getDecl()))
3745     assert(GD.getDtorType() == Dtor_Deleting);
3746 
3747   MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD);
3748   if (I != MethodVFTableLocations.end())
3749     return I->second;
3750 
3751   const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
3752 
3753   computeVTableRelatedInformation(RD);
3754 
3755   I = MethodVFTableLocations.find(GD);
3756   assert(I != MethodVFTableLocations.end() && "Did not find index!");
3757   return I->second;
3758 }
3759