Home | History | Annotate | Download | only in AST
      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 
     50   BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
     51                  NonVirtualOffset(CharUnits::Zero()) { }
     52   BaseOffset(const CXXRecordDecl *DerivedClass,
     53              const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
     54     : DerivedClass(DerivedClass), VirtualBase(VirtualBase),
     55     NonVirtualOffset(NonVirtualOffset) { }
     56 
     57   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 
     76     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.
    141   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.
    150   void dump() {
    151     VisitedVirtualBasesSetTy VisitedVirtualBases;
    152     dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()),
    153          VisitedVirtualBases);
    154   }
    155 
    156 };
    157 
    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 
    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 
    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
    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
    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 
    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.
    467   bool empty() const { return Offsets.empty(); }
    468 };
    469 
    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 
    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 
    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 
    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:
    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;
    601   const_iterator components_begin() const { return Components.rbegin(); }
    602   const_iterator components_end() const { return Components.rend(); }
    603 
    604   const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
    605   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
    606     return VBaseOffsetOffsets;
    607   }
    608 };
    609 
    610 void
    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 
    659 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 
    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
    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 
    841     MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,
    842                uint64_t VTableIndex)
    843       : BaseOffset(BaseOffset),
    844       BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
    845       VTableIndex(VTableIndex) { }
    846 
    847     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.
    980   bool isBuildingConstructorVTable() const {
    981     return MostDerivedClass != LayoutClass;
    982   }
    983 
    984 public:
    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 
   1003   uint64_t getNumThunks() const {
   1004     return Thunks.size();
   1005   }
   1006 
   1007   ThunksMapTy::const_iterator thunks_begin() const {
   1008     return Thunks.begin();
   1009   }
   1010 
   1011   ThunksMapTy::const_iterator thunks_end() const {
   1012     return Thunks.end();
   1013   }
   1014 
   1015   const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
   1016     return VBaseOffsetOffsets;
   1017   }
   1018 
   1019   const AddressPointsMapTy &getAddressPoints() const {
   1020     return AddressPoints;
   1021   }
   1022 
   1023   MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
   1024     return MethodVTableIndices.begin();
   1025   }
   1026 
   1027   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.
   1033   uint64_t getNumVTableComponents() const {
   1034     return Components.size();
   1035   }
   1036 
   1037   const VTableComponent *vtable_component_begin() const {
   1038     return Components.begin();
   1039   }
   1040 
   1041   const VTableComponent *vtable_component_end() const {
   1042     return Components.end();
   1043   }
   1044 
   1045   AddressPointsMapTy::const_iterator address_points_begin() const {
   1046     return AddressPoints.begin();
   1047   }
   1048 
   1049   AddressPointsMapTy::const_iterator address_points_end() const {
   1050     return AddressPoints.end();
   1051   }
   1052 
   1053   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
   1054     return VTableThunks.begin();
   1055   }
   1056 
   1057   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 
   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
   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
   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 
   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
   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 
   1211 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 
   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 
   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.
   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 
   1354 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 *
   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 
   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 
   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 
   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
   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 
   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 
   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.
   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 
   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 
   2232 VTableLayout::~VTableLayout() { }
   2233 
   2234 ItaniumVTableContext::ItaniumVTableContext(ASTContext &Context)
   2235     : VTableContextBase(/*MS=*/false) {}
   2236 
   2237 ItaniumVTableContext::~ItaniumVTableContext() {
   2238   llvm::DeleteContainerSeconds(VTableLayouts);
   2239 }
   2240 
   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
   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 
   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
   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 
   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 
   2440     MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex,
   2441                bool UsesExtraSlot = false)
   2442         : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),
   2443           Shadowed(false), UsesExtraSlot(UsesExtraSlot) {}
   2444 
   2445     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.
   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.
   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 
   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:
   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 
   2561   uint64_t getNumThunks() const { return Thunks.size(); }
   2562 
   2563   ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
   2564 
   2565   ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
   2566 
   2567   method_locations_range vtable_locations() const {
   2568     return method_locations_range(MethodVFTableLocations.begin(),
   2569                                   MethodVFTableLocations.end());
   2570   }
   2571 
   2572   uint64_t getNumVTableComponents() const { return Components.size(); }
   2573 
   2574   const VTableComponent *vtable_component_begin() const {
   2575     return Components.begin();
   2576   }
   2577 
   2578   const VTableComponent *vtable_component_end() const {
   2579     return Components.end();
   2580   }
   2581 
   2582   VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
   2583     return VTableThunks.begin();
   2584   }
   2585 
   2586   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
   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.
   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 
   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 
   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 
   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 
   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 
   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 
   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 
   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.
   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 
   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 
   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 
   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.
   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.
   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 
   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.
   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 
   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 
   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 
   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 
   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 
   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 &
   3718 MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
   3719   return computeVBTableRelatedInformation(RD)->VBPtrPaths;
   3720 }
   3721 
   3722 const VPtrInfoVector &
   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 &
   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 &
   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