brintos / llvm-project-archived public Read only

1//===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This contains code dealing with generation of the layout of virtual tables.10//11//===----------------------------------------------------------------------===//12 13#include "clang/AST/VTableBuilder.h"14#include "clang/AST/ASTContext.h"15#include "clang/AST/ASTDiagnostic.h"16#include "clang/AST/CXXInheritance.h"17#include "clang/AST/RecordLayout.h"18#include "clang/Basic/TargetInfo.h"19#include "llvm/ADT/SetOperations.h"20#include "llvm/ADT/SetVector.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 27using namespace clang;28 29#define DUMP_OVERRIDERS 030 31namespace {32 33/// BaseOffset - Represents an offset from a derived class to a direct or34/// indirect base class.35struct BaseOffset {36  /// DerivedClass - The derived class.37  const CXXRecordDecl *DerivedClass;38 39  /// VirtualBase - If the path from the derived class to the base class40  /// involves virtual base classes, this holds the declaration of the last41  /// 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 the46  /// path from the derived class to the base class involves a virtual base47  /// 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 all61/// member functions in the base subobjects of a class.62class FinalOverriders {63public: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 80private:81  /// MostDerivedClass - The most derived class for which the final overriders82  /// are stored.83  const CXXRecordDecl *MostDerivedClass;84 85  /// MostDerivedClassOffset - If we're building final overriders for a86  /// construction vtable, this holds the offset from the layout class to the87  /// most derived class.88  const CharUnits MostDerivedClassOffset;89 90  /// LayoutClass - The class we're using for layout information. Will be91  /// different than the most derived class if the final overriders are for a92  /// 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 function101  /// 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 of108  /// all the base subobjects of the most derived class.109  OverridersMapTy OverridersMap;110 111  /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented112  /// as a record decl and a subobject number) and its offsets in the most113  /// 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 the120  /// 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 direct130  /// and indirect base subobjects.131  void dump(raw_ostream &Out, BaseSubobject Base,132            VisitedVirtualBasesSetTy& VisitedVirtualBases);133 134public:135  FinalOverriders(const CXXRecordDecl *MostDerivedClass,136                  CharUnits MostDerivedClassOffset,137                  const CXXRecordDecl *LayoutClass);138 139  /// getOverrider - Get the final overrider for the given method declaration in140  /// 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 158FinalOverriders::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_OVERRIDERS214  // And dump them (for now).215  dump();216#endif217}218 219static 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 should252  // even change the base offsets in ASTRecordLayout to be specified in253  // CharUnits.254  return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);255 256}257 258static 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 270static BaseOffset271ComputeReturnAdjustmentBaseOffset(ASTContext &Context,272                                  const CXXMethodDecl *DerivedMD,273                                  const CXXMethodDecl *BaseMD) {274  const auto *BaseFT = BaseMD->getType()->castAs<FunctionType>();275  const auto *DerivedFT = DerivedMD->getType()->castAs<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; consider307  //   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 auto *DerivedRD =316      cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl())317          ->getDefinitionOrSelf();318 319  const auto *BaseRD =320      cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());321 322  return ComputeBaseOffset(Context, BaseRD, DerivedRD);323}324 325void326FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,327                              CharUnits OffsetInLayoutClass,328                              SubobjectOffsetMapTy &SubobjectOffsets,329                              SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,330                              SubobjectCountMapTy &SubobjectCounts) {331  const CXXRecordDecl *RD = Base.getBase();332 333  unsigned SubobjectNumber = 0;334  if (!IsVirtual)335    SubobjectNumber = ++SubobjectCounts[RD];336 337  // Set up the subobject to offset mapping.338  assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))339         && "Subobject offset already exists!");340  assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber))341         && "Subobject offset already exists!");342 343  SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();344  SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =345    OffsetInLayoutClass;346 347  // Traverse our bases.348  for (const auto &B : RD->bases()) {349    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();350 351    CharUnits BaseOffset;352    CharUnits BaseOffsetInLayoutClass;353    if (B.isVirtual()) {354      // Check if we've visited this virtual base before.355      if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))356        continue;357 358      const ASTRecordLayout &LayoutClassLayout =359        Context.getASTRecordLayout(LayoutClass);360 361      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);362      BaseOffsetInLayoutClass =363        LayoutClassLayout.getVBaseClassOffset(BaseDecl);364    } else {365      const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);366      CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);367 368      BaseOffset = Base.getBaseOffset() + Offset;369      BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;370    }371 372    ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset),373                       B.isVirtual(), BaseOffsetInLayoutClass,374                       SubobjectOffsets, SubobjectLayoutClassOffsets,375                       SubobjectCounts);376  }377}378 379void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,380                           VisitedVirtualBasesSetTy &VisitedVirtualBases) {381  const CXXRecordDecl *RD = Base.getBase();382  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);383 384  for (const auto &B : RD->bases()) {385    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();386 387    // Ignore bases that don't have any virtual member functions.388    if (!BaseDecl->isPolymorphic())389      continue;390 391    CharUnits BaseOffset;392    if (B.isVirtual()) {393      if (!VisitedVirtualBases.insert(BaseDecl).second) {394        // We've visited this base before.395        continue;396      }397 398      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);399    } else {400      BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();401    }402 403    dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);404  }405 406  Out << "Final overriders for (";407  RD->printQualifiedName(Out);408  Out << ", ";409  Out << Base.getBaseOffset().getQuantity() << ")\n";410 411  // Now dump the overriders for this base subobject.412  for (const auto *MD : RD->methods()) {413    if (!VTableContextBase::hasVtableSlot(MD))414      continue;415    MD = MD->getCanonicalDecl();416 417    OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());418 419    Out << "  ";420    MD->printQualifiedName(Out);421    Out << " - (";422    Overrider.Method->printQualifiedName(Out);423    Out << ", " << Overrider.Offset.getQuantity() << ')';424 425    BaseOffset Offset;426    if (!Overrider.Method->isPureVirtual())427      Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);428 429    if (!Offset.isEmpty()) {430      Out << " [ret-adj: ";431      if (Offset.VirtualBase) {432        Offset.VirtualBase->printQualifiedName(Out);433        Out << " vbase, ";434      }435 436      Out << Offset.NonVirtualOffset.getQuantity() << " nv]";437    }438 439    Out << "\n";440  }441}442 443/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.444struct VCallOffsetMap {445 446  typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;447 448  /// Offsets - Keeps track of methods and their offsets.449  // FIXME: This should be a real map and not a vector.450  SmallVector<MethodAndOffsetPairTy, 16> Offsets;451 452  /// MethodsCanShareVCallOffset - Returns whether two virtual member functions453  /// can share the same vcall offset.454  static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,455                                         const CXXMethodDecl *RHS);456 457public:458  /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the459  /// add was successful, or false if there was already a member function with460  /// the same signature in the map.461  bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);462 463  /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the464  /// vtable address point) for the given virtual member function.465  CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);466 467  // empty - Return whether the offset map is empty or not.468  bool empty() const { return Offsets.empty(); }469};470 471static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,472                                    const CXXMethodDecl *RHS) {473  const FunctionProtoType *LT =474    cast<FunctionProtoType>(LHS->getType().getCanonicalType());475  const FunctionProtoType *RT =476    cast<FunctionProtoType>(RHS->getType().getCanonicalType());477 478  // Fast-path matches in the canonical types.479  if (LT == RT) return true;480 481  // Force the signatures to match.  We can't rely on the overrides482  // list here because there isn't necessarily an inheritance483  // relationship between the two methods.484  if (LT->getMethodQuals() != RT->getMethodQuals())485    return false;486  return LT->getParamTypes() == RT->getParamTypes();487}488 489bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,490                                                const CXXMethodDecl *RHS) {491  assert(VTableContextBase::hasVtableSlot(LHS) && "LHS must be virtual!");492  assert(VTableContextBase::hasVtableSlot(RHS) && "RHS must be virtual!");493 494  // A destructor can share a vcall offset with another destructor.495  if (isa<CXXDestructorDecl>(LHS))496    return isa<CXXDestructorDecl>(RHS);497 498  // FIXME: We need to check more things here.499 500  // The methods must have the same name.501  DeclarationName LHSName = LHS->getDeclName();502  DeclarationName RHSName = RHS->getDeclName();503  if (LHSName != RHSName)504    return false;505 506  // And the same signatures.507  return HasSameVirtualSignature(LHS, RHS);508}509 510bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,511                                    CharUnits OffsetOffset) {512  // Check if we can reuse an offset.513  for (const auto &OffsetPair : Offsets) {514    if (MethodsCanShareVCallOffset(OffsetPair.first, MD))515      return false;516  }517 518  // Add the offset.519  Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));520  return true;521}522 523CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {524  // Look for an offset.525  for (const auto &OffsetPair : Offsets) {526    if (MethodsCanShareVCallOffset(OffsetPair.first, MD))527      return OffsetPair.second;528  }529 530  llvm_unreachable("Should always find a vcall offset offset!");531}532 533/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.534class VCallAndVBaseOffsetBuilder {535public:536  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>537    VBaseOffsetOffsetsMapTy;538 539private:540  const ItaniumVTableContext &VTables;541 542  /// MostDerivedClass - The most derived class for which we're building vcall543  /// and vbase offsets.544  const CXXRecordDecl *MostDerivedClass;545 546  /// LayoutClass - The class we're using for layout information. Will be547  /// different than the most derived class if we're building a construction548  /// vtable.549  const CXXRecordDecl *LayoutClass;550 551  /// Context - The ASTContext which we will use for layout information.552  ASTContext &Context;553 554  /// Components - vcall and vbase offset components555  typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;556  VTableComponentVectorTy Components;557 558  /// VisitedVirtualBases - Visited virtual bases.559  llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;560 561  /// VCallOffsets - Keeps track of vcall offsets.562  VCallOffsetMap VCallOffsets;563 564 565  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,566  /// relative to the address point.567  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;568 569  /// FinalOverriders - The final overriders of the most derived class.570  /// (Can be null when we're not building a vtable of the most derived class).571  const FinalOverriders *Overriders;572 573  /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the574  /// given base subobject.575  void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,576                               CharUnits RealBaseOffset);577 578  /// AddVCallOffsets - Add vcall offsets for the given base subobject.579  void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);580 581  /// AddVBaseOffsets - Add vbase offsets for the given class.582  void AddVBaseOffsets(const CXXRecordDecl *Base,583                       CharUnits OffsetInLayoutClass);584 585  /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in586  /// chars, relative to the vtable address point.587  CharUnits getCurrentOffsetOffset() const;588 589public:590  VCallAndVBaseOffsetBuilder(const ItaniumVTableContext &VTables,591                             const CXXRecordDecl *MostDerivedClass,592                             const CXXRecordDecl *LayoutClass,593                             const FinalOverriders *Overriders,594                             BaseSubobject Base, bool BaseIsVirtual,595                             CharUnits OffsetInLayoutClass)596      : VTables(VTables), MostDerivedClass(MostDerivedClass),597        LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),598        Overriders(Overriders) {599 600    // Add vcall and vbase offsets.601    AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);602  }603 604  /// Methods for iterating over the components.605  typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;606  const_iterator components_begin() const { return Components.rbegin(); }607  const_iterator components_end() const { return Components.rend(); }608 609  const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }610  const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {611    return VBaseOffsetOffsets;612  }613};614 615void616VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,617                                                    bool BaseIsVirtual,618                                                    CharUnits RealBaseOffset) {619  const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());620 621  // Itanium C++ ABI 2.5.2:622  //   ..in classes sharing a virtual table with a primary base class, the vcall623  //   and vbase offsets added by the derived class all come before the vcall624  //   and vbase offsets required by the base class, so that the latter may be625  //   laid out as required by the base class without regard to additions from626  //   the derived class(es).627 628  // (Since we're emitting the vcall and vbase offsets in reverse order, we'll629  // emit them for the primary base first).630  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {631    bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();632 633    CharUnits PrimaryBaseOffset;634 635    // Get the base offset of the primary base.636    if (PrimaryBaseIsVirtual) {637      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&638             "Primary vbase should have a zero offset!");639 640      const ASTRecordLayout &MostDerivedClassLayout =641        Context.getASTRecordLayout(MostDerivedClass);642 643      PrimaryBaseOffset =644        MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);645    } else {646      assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&647             "Primary base should have a zero offset!");648 649      PrimaryBaseOffset = Base.getBaseOffset();650    }651 652    AddVCallAndVBaseOffsets(653      BaseSubobject(PrimaryBase,PrimaryBaseOffset),654      PrimaryBaseIsVirtual, RealBaseOffset);655  }656 657  AddVBaseOffsets(Base.getBase(), RealBaseOffset);658 659  // We only want to add vcall offsets for virtual bases.660  if (BaseIsVirtual)661    AddVCallOffsets(Base, RealBaseOffset);662}663 664CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {665  // OffsetIndex is the index of this vcall or vbase offset, relative to the666  // vtable address point. (We subtract 3 to account for the information just667  // above the address point, the RTTI info, the offset to top, and the668  // vcall offset itself).669  size_t NumComponentsAboveAddrPoint = 3;670  if (Context.getLangOpts().OmitVTableRTTI)671    NumComponentsAboveAddrPoint--;672  int64_t OffsetIndex =673      -(int64_t)(NumComponentsAboveAddrPoint + Components.size());674 675  // Under the relative ABI, the offset widths are 32-bit ints instead of676  // pointer widths.677  CharUnits OffsetWidth = Context.toCharUnitsFromBits(678      VTables.isRelativeLayout()679          ? 32680          : Context.getTargetInfo().getPointerWidth(LangAS::Default));681  CharUnits OffsetOffset = OffsetWidth * OffsetIndex;682 683  return OffsetOffset;684}685 686void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,687                                                 CharUnits VBaseOffset) {688  const CXXRecordDecl *RD = Base.getBase();689  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);690 691  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();692 693  // Handle the primary base first.694  // We only want to add vcall offsets if the base is non-virtual; a virtual695  // primary base will have its vcall and vbase offsets emitted already.696  if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {697    // Get the base offset of the primary base.698    assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&699           "Primary base should have a zero offset!");700 701    AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),702                    VBaseOffset);703  }704 705  // Add the vcall offsets.706  for (const auto *MD : RD->methods()) {707    if (!VTableContextBase::hasVtableSlot(MD))708      continue;709    MD = MD->getCanonicalDecl();710 711    CharUnits OffsetOffset = getCurrentOffsetOffset();712 713    // Don't add a vcall offset if we already have one for this member function714    // signature.715    if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))716      continue;717 718    CharUnits Offset = CharUnits::Zero();719 720    if (Overriders) {721      // Get the final overrider.722      FinalOverriders::OverriderInfo Overrider =723        Overriders->getOverrider(MD, Base.getBaseOffset());724 725      /// The vcall offset is the offset from the virtual base to the object726      /// where the function was overridden.727      Offset = Overrider.Offset - VBaseOffset;728    }729 730    Components.push_back(731      VTableComponent::MakeVCallOffset(Offset));732  }733 734  // And iterate over all non-virtual bases (ignoring the primary base).735  for (const auto &B : RD->bases()) {736    if (B.isVirtual())737      continue;738 739    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();740    if (BaseDecl == PrimaryBase)741      continue;742 743    // Get the base offset of this base.744    CharUnits BaseOffset = Base.getBaseOffset() +745      Layout.getBaseClassOffset(BaseDecl);746 747    AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset),748                    VBaseOffset);749  }750}751 752void753VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,754                                            CharUnits OffsetInLayoutClass) {755  const ASTRecordLayout &LayoutClassLayout =756    Context.getASTRecordLayout(LayoutClass);757 758  // Add vbase offsets.759  for (const auto &B : RD->bases()) {760    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();761 762    // Check if this is a virtual base that we haven't visited before.763    if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl).second) {764      CharUnits Offset =765        LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;766 767      // Add the vbase offset offset.768      assert(!VBaseOffsetOffsets.count(BaseDecl) &&769             "vbase offset offset already exists!");770 771      CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();772      VBaseOffsetOffsets.insert(773          std::make_pair(BaseDecl, VBaseOffsetOffset));774 775      Components.push_back(776          VTableComponent::MakeVBaseOffset(Offset));777    }778 779    // Check the base class looking for more vbase offsets.780    AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);781  }782}783 784/// ItaniumVTableBuilder - Class for building vtable layout information.785class ItaniumVTableBuilder {786public:787  /// PrimaryBasesSetVectorTy - A set vector of direct and indirect788  /// primary bases.789  typedef llvm::SmallSetVector<const CXXRecordDecl *, 8>790    PrimaryBasesSetVectorTy;791 792  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>793    VBaseOffsetOffsetsMapTy;794 795  typedef VTableLayout::AddressPointsMapTy AddressPointsMapTy;796 797  typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;798 799private:800  /// VTables - Global vtable information.801  ItaniumVTableContext &VTables;802 803  /// MostDerivedClass - The most derived class for which we're building this804  /// vtable.805  const CXXRecordDecl *MostDerivedClass;806 807  /// MostDerivedClassOffset - If we're building a construction vtable, this808  /// holds the offset from the layout class to the most derived class.809  const CharUnits MostDerivedClassOffset;810 811  /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual812  /// base. (This only makes sense when building a construction vtable).813  bool MostDerivedClassIsVirtual;814 815  /// LayoutClass - The class we're using for layout information. Will be816  /// different than the most derived class if we're building a construction817  /// vtable.818  const CXXRecordDecl *LayoutClass;819 820  /// Context - The ASTContext which we will use for layout information.821  ASTContext &Context;822 823  /// FinalOverriders - The final overriders of the most derived class.824  const FinalOverriders Overriders;825 826  /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual827  /// bases in this vtable.828  llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;829 830  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for831  /// the most derived class.832  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;833 834  /// Components - The components of the vtable being built.835  SmallVector<VTableComponent, 64> Components;836 837  /// AddressPoints - Address points for the vtable being built.838  AddressPointsMapTy AddressPoints;839 840  /// MethodInfo - Contains information about a method in a vtable.841  /// (Used for computing 'this' pointer adjustment thunks.842  struct MethodInfo {843    /// BaseOffset - The base offset of this method.844    const CharUnits BaseOffset;845 846    /// BaseOffsetInLayoutClass - The base offset in the layout class of this847    /// method.848    const CharUnits BaseOffsetInLayoutClass;849 850    /// VTableIndex - The index in the vtable that this method has.851    /// (For destructors, this is the index of the complete destructor).852    const uint64_t VTableIndex;853 854    MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,855               uint64_t VTableIndex)856      : BaseOffset(BaseOffset),857      BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),858      VTableIndex(VTableIndex) { }859 860    MethodInfo()861      : BaseOffset(CharUnits::Zero()),862      BaseOffsetInLayoutClass(CharUnits::Zero()),863      VTableIndex(0) { }864 865    MethodInfo(MethodInfo const&) = default;866  };867 868  typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;869 870  /// MethodInfoMap - The information for all methods in the vtable we're871  /// currently building.872  MethodInfoMapTy MethodInfoMap;873 874  /// MethodVTableIndices - Contains the index (relative to the vtable address875  /// point) where the function pointer for a virtual function is stored.876  MethodVTableIndicesTy MethodVTableIndices;877 878  typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;879 880  /// VTableThunks - The thunks by vtable index in the vtable currently being881  /// built.882  VTableThunksMapTy VTableThunks;883 884  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;885  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;886 887  /// Thunks - A map that contains all the thunks needed for all methods in the888  /// most derived class for which the vtable is currently being built.889  ThunksMapTy Thunks;890 891  /// AddThunk - Add a thunk for the given method.892  void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);893 894  /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the895  /// part of the vtable we're currently building.896  void ComputeThisAdjustments();897 898  typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;899 900  /// PrimaryVirtualBases - All known virtual bases who are a primary base of901  /// some other base.902  VisitedVirtualBasesSetTy PrimaryVirtualBases;903 904  /// ComputeReturnAdjustment - Compute the return adjustment given a return905  /// adjustment base offset.906  ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);907 908  /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting909  /// the 'this' pointer from the base subobject to the derived subobject.910  BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,911                                             BaseSubobject Derived) const;912 913  /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the914  /// given virtual member function, its offset in the layout class and its915  /// final overrider.916  ThisAdjustment917  ComputeThisAdjustment(const CXXMethodDecl *MD,918                        CharUnits BaseOffsetInLayoutClass,919                        FinalOverriders::OverriderInfo Overrider);920 921  /// AddMethod - Add a single virtual member function to the vtable922  /// components vector.923  void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);924 925  /// IsOverriderUsed - Returns whether the overrider will ever be used in this926  /// part of the vtable.927  ///928  /// Itanium C++ ABI 2.5.2:929  ///930  ///   struct A { virtual void f(); };931  ///   struct B : virtual public A { int i; };932  ///   struct C : virtual public A { int j; };933  ///   struct D : public B, public C {};934  ///935  ///   When B and C are declared, A is a primary base in each case, so although936  ///   vcall offsets are allocated in the A-in-B and A-in-C vtables, no this937  ///   adjustment is required and no thunk is generated. However, inside D938  ///   objects, A is no longer a primary base of C, so if we allowed calls to939  ///   C::f() to use the copy of A's vtable in the C subobject, we would need940  ///   to adjust this from C* to B::A*, which would require a third-party941  ///   thunk. Since we require that a call to C::f() first convert to A*,942  ///   C-in-D's copy of A's vtable is never referenced, so this is not943  ///   necessary.944  bool IsOverriderUsed(const CXXMethodDecl *Overrider,945                       CharUnits BaseOffsetInLayoutClass,946                       const CXXRecordDecl *FirstBaseInPrimaryBaseChain,947                       CharUnits FirstBaseOffsetInLayoutClass) const;948 949 950  /// AddMethods - Add the methods of this base subobject and all its951  /// primary bases to the vtable components vector.952  void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,953                  const CXXRecordDecl *FirstBaseInPrimaryBaseChain,954                  CharUnits FirstBaseOffsetInLayoutClass,955                  PrimaryBasesSetVectorTy &PrimaryBases);956 957  // LayoutVTable - Layout the vtable for the given base class, including its958  // secondary vtables and any vtables for virtual bases.959  void LayoutVTable();960 961  /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the962  /// given base subobject, as well as all its secondary vtables.963  ///964  /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base965  /// or a direct or indirect base of a virtual base.966  ///967  /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual968  /// in the layout class.969  void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,970                                        bool BaseIsMorallyVirtual,971                                        bool BaseIsVirtualInLayoutClass,972                                        CharUnits OffsetInLayoutClass);973 974  /// LayoutSecondaryVTables - Layout the secondary vtables for the given base975  /// subobject.976  ///977  /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base978  /// or a direct or indirect base of a virtual base.979  void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,980                              CharUnits OffsetInLayoutClass);981 982  /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this983  /// class hierarchy.984  void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD,985                                    CharUnits OffsetInLayoutClass,986                                    VisitedVirtualBasesSetTy &VBases);987 988  /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the989  /// given base (excluding any primary bases).990  void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD,991                                    VisitedVirtualBasesSetTy &VBases);992 993  /// isBuildingConstructionVTable - Return whether this vtable builder is994  /// building a construction vtable.995  bool isBuildingConstructorVTable() const {996    return MostDerivedClass != LayoutClass;997  }998 999public:1000  /// Component indices of the first component of each of the vtables in the1001  /// vtable group.1002  SmallVector<size_t, 4> VTableIndices;1003 1004  ItaniumVTableBuilder(ItaniumVTableContext &VTables,1005                       const CXXRecordDecl *MostDerivedClass,1006                       CharUnits MostDerivedClassOffset,1007                       bool MostDerivedClassIsVirtual,1008                       const CXXRecordDecl *LayoutClass)1009      : VTables(VTables), MostDerivedClass(MostDerivedClass),1010        MostDerivedClassOffset(MostDerivedClassOffset),1011        MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),1012        LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),1013        Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {1014    assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());1015 1016    LayoutVTable();1017 1018    if (Context.getLangOpts().DumpVTableLayouts)1019      dumpLayout(llvm::outs());1020  }1021 1022  uint64_t getNumThunks() const {1023    return Thunks.size();1024  }1025 1026  ThunksMapTy::const_iterator thunks_begin() const {1027    return Thunks.begin();1028  }1029 1030  ThunksMapTy::const_iterator thunks_end() const {1031    return Thunks.end();1032  }1033 1034  const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {1035    return VBaseOffsetOffsets;1036  }1037 1038  const AddressPointsMapTy &getAddressPoints() const {1039    return AddressPoints;1040  }1041 1042  MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {1043    return MethodVTableIndices.begin();1044  }1045 1046  MethodVTableIndicesTy::const_iterator vtable_indices_end() const {1047    return MethodVTableIndices.end();1048  }1049 1050  ArrayRef<VTableComponent> vtable_components() const { return Components; }1051 1052  AddressPointsMapTy::const_iterator address_points_begin() const {1053    return AddressPoints.begin();1054  }1055 1056  AddressPointsMapTy::const_iterator address_points_end() const {1057    return AddressPoints.end();1058  }1059 1060  VTableThunksMapTy::const_iterator vtable_thunks_begin() const {1061    return VTableThunks.begin();1062  }1063 1064  VTableThunksMapTy::const_iterator vtable_thunks_end() const {1065    return VTableThunks.end();1066  }1067 1068  /// dumpLayout - Dump the vtable layout.1069  void dumpLayout(raw_ostream&);1070};1071 1072void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,1073                                    const ThunkInfo &Thunk) {1074  assert(!isBuildingConstructorVTable() &&1075         "Can't add thunks for construction vtable");1076 1077  SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];1078 1079  // Check if we have this thunk already.1080  if (llvm::is_contained(ThunksVector, Thunk))1081    return;1082 1083  ThunksVector.push_back(Thunk);1084}1085 1086typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;1087 1088/// Visit all the methods overridden by the given method recursively,1089/// in a depth-first pre-order. The Visitor's visitor method returns a bool1090/// indicating whether to continue the recursion for the given overridden1091/// method (i.e. returning false stops the iteration).1092template <class VisitorTy>1093static void1094visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {1095  assert(VTableContextBase::hasVtableSlot(MD) && "Method is not virtual!");1096 1097  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {1098    if (!Visitor(OverriddenMD))1099      continue;1100    visitAllOverriddenMethods(OverriddenMD, Visitor);1101  }1102}1103 1104/// ComputeAllOverriddenMethods - Given a method decl, will return a set of all1105/// the overridden methods that the function decl overrides.1106static void1107ComputeAllOverriddenMethods(const CXXMethodDecl *MD,1108                            OverriddenMethodsSetTy& OverriddenMethods) {1109  auto OverriddenMethodsCollector = [&](const CXXMethodDecl *MD) {1110    // Don't recurse on this method if we've already collected it.1111    return OverriddenMethods.insert(MD).second;1112  };1113  visitAllOverriddenMethods(MD, OverriddenMethodsCollector);1114}1115 1116void ItaniumVTableBuilder::ComputeThisAdjustments() {1117  // Now go through the method info map and see if any of the methods need1118  // 'this' pointer adjustments.1119  for (const auto &MI : MethodInfoMap) {1120    const CXXMethodDecl *MD = MI.first;1121    const MethodInfo &MethodInfo = MI.second;1122 1123    // Ignore adjustments for unused function pointers.1124    uint64_t VTableIndex = MethodInfo.VTableIndex;1125    if (Components[VTableIndex].getKind() ==1126        VTableComponent::CK_UnusedFunctionPointer)1127      continue;1128 1129    // Get the final overrider for this method.1130    FinalOverriders::OverriderInfo Overrider =1131      Overriders.getOverrider(MD, MethodInfo.BaseOffset);1132 1133    // Check if we need an adjustment at all.1134    if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {1135      // When a return thunk is needed by a derived class that overrides a1136      // virtual base, gcc uses a virtual 'this' adjustment as well.1137      // While the thunk itself might be needed by vtables in subclasses or1138      // in construction vtables, there doesn't seem to be a reason for using1139      // the thunk in this vtable. Still, we do so to match gcc.1140      if (VTableThunks.lookup(VTableIndex).Return.isEmpty())1141        continue;1142    }1143 1144    ThisAdjustment ThisAdjustment =1145      ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider);1146 1147    if (ThisAdjustment.isEmpty())1148      continue;1149 1150    // Add it.1151    auto SetThisAdjustmentThunk = [&](uint64_t Idx) {1152      // If a this pointer adjustment is required, record the method that1153      // created the vtable entry. MD is not necessarily the method that1154      // created the entry since derived classes overwrite base class1155      // information in MethodInfoMap, hence findOriginalMethodInMap is called1156      // here.1157      //1158      // For example, in the following class hierarchy, if MD = D1::m and1159      // Overrider = D2:m, the original method that created the entry is B0:m,1160      // which is what findOriginalMethodInMap(MD) returns:1161      //1162      // struct B0 { int a; virtual void m(); };1163      // struct D0 : B0 { int a; void m() override; };1164      // struct D1 : B0 { int a; void m() override; };1165      // struct D2 : D0, D1 { int a; void m() override; };1166      //1167      // We need to record the method because we cannot1168      // call findOriginalMethod to find the method that created the entry if1169      // the method in the entry requires adjustment.1170      //1171      // Do not set ThunkInfo::Method if Idx is already in VTableThunks. This1172      // can happen when covariant return adjustment is required too.1173      auto [It, Inserted] = VTableThunks.try_emplace(Idx);1174      if (Inserted) {1175        const CXXMethodDecl *Method = VTables.findOriginalMethodInMap(MD);1176        It->second.Method = Method;1177        It->second.ThisType = Method->getThisType().getTypePtr();1178      }1179      It->second.This = ThisAdjustment;1180    };1181 1182    SetThisAdjustmentThunk(VTableIndex);1183 1184    if (isa<CXXDestructorDecl>(MD)) {1185      // Add an adjustment for the deleting destructor as well.1186      SetThisAdjustmentThunk(VTableIndex + 1);1187    }1188  }1189 1190  /// Clear the method info map.1191  MethodInfoMap.clear();1192 1193  if (isBuildingConstructorVTable()) {1194    // We don't need to store thunk information for construction vtables.1195    return;1196  }1197 1198  for (const auto &TI : VTableThunks) {1199    const VTableComponent &Component = Components[TI.first];1200    const ThunkInfo &Thunk = TI.second;1201    const CXXMethodDecl *MD;1202 1203    switch (Component.getKind()) {1204    default:1205      llvm_unreachable("Unexpected vtable component kind!");1206    case VTableComponent::CK_FunctionPointer:1207      MD = Component.getFunctionDecl();1208      break;1209    case VTableComponent::CK_CompleteDtorPointer:1210      MD = Component.getDestructorDecl();1211      break;1212    case VTableComponent::CK_DeletingDtorPointer:1213      // We've already added the thunk when we saw the complete dtor pointer.1214      continue;1215    }1216 1217    if (MD->getParent() == MostDerivedClass)1218      AddThunk(MD, Thunk);1219  }1220}1221 1222ReturnAdjustment1223ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {1224  ReturnAdjustment Adjustment;1225 1226  if (!Offset.isEmpty()) {1227    if (Offset.VirtualBase) {1228      // Get the virtual base offset offset.1229      if (Offset.DerivedClass == MostDerivedClass) {1230        // We can get the offset offset directly from our map.1231        Adjustment.Virtual.Itanium.VBaseOffsetOffset =1232          VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity();1233      } else {1234        Adjustment.Virtual.Itanium.VBaseOffsetOffset =1235          VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass,1236                                             Offset.VirtualBase).getQuantity();1237      }1238    }1239 1240    Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();1241  }1242 1243  return Adjustment;1244}1245 1246BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(1247    BaseSubobject Base, BaseSubobject Derived) const {1248  const CXXRecordDecl *BaseRD = Base.getBase();1249  const CXXRecordDecl *DerivedRD = Derived.getBase();1250 1251  CXXBasePaths Paths(/*FindAmbiguities=*/true,1252                     /*RecordPaths=*/true, /*DetectVirtual=*/true);1253 1254  if (!DerivedRD->isDerivedFrom(BaseRD, Paths))1255    llvm_unreachable("Class must be derived from the passed in base class!");1256 1257  // We have to go through all the paths, and see which one leads us to the1258  // right base subobject.1259  for (const CXXBasePath &Path : Paths) {1260    BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, Path);1261 1262    CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;1263 1264    if (Offset.VirtualBase) {1265      // If we have a virtual base class, the non-virtual offset is relative1266      // to the virtual base class offset.1267      const ASTRecordLayout &LayoutClassLayout =1268        Context.getASTRecordLayout(LayoutClass);1269 1270      /// Get the virtual base offset, relative to the most derived class1271      /// layout.1272      OffsetToBaseSubobject +=1273        LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase);1274    } else {1275      // Otherwise, the non-virtual offset is relative to the derived class1276      // offset.1277      OffsetToBaseSubobject += Derived.getBaseOffset();1278    }1279 1280    // Check if this path gives us the right base subobject.1281    if (OffsetToBaseSubobject == Base.getBaseOffset()) {1282      // Since we're going from the base class _to_ the derived class, we'll1283      // invert the non-virtual offset here.1284      Offset.NonVirtualOffset = -Offset.NonVirtualOffset;1285      return Offset;1286    }1287  }1288 1289  return BaseOffset();1290}1291 1292ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(1293    const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,1294    FinalOverriders::OverriderInfo Overrider) {1295  // Ignore adjustments for pure virtual member functions.1296  if (Overrider.Method->isPureVirtual())1297    return ThisAdjustment();1298 1299  BaseSubobject OverriddenBaseSubobject(MD->getParent(),1300                                        BaseOffsetInLayoutClass);1301 1302  BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),1303                                       Overrider.Offset);1304 1305  // Compute the adjustment offset.1306  BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject,1307                                                      OverriderBaseSubobject);1308  if (Offset.isEmpty())1309    return ThisAdjustment();1310 1311  ThisAdjustment Adjustment;1312 1313  if (Offset.VirtualBase) {1314    // Get the vcall offset map for this virtual base.1315    VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];1316 1317    if (VCallOffsets.empty()) {1318      // We don't have vcall offsets for this virtual base, go ahead and1319      // build them.1320      VCallAndVBaseOffsetBuilder Builder(1321          VTables, MostDerivedClass, MostDerivedClass,1322          /*Overriders=*/nullptr,1323          BaseSubobject(Offset.VirtualBase, CharUnits::Zero()),1324          /*BaseIsVirtual=*/true,1325          /*OffsetInLayoutClass=*/1326          CharUnits::Zero());1327 1328      VCallOffsets = Builder.getVCallOffsets();1329    }1330 1331    Adjustment.Virtual.Itanium.VCallOffsetOffset =1332      VCallOffsets.getVCallOffsetOffset(MD).getQuantity();1333  }1334 1335  // Set the non-virtual part of the adjustment.1336  Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();1337 1338  return Adjustment;1339}1340 1341void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,1342                                     ReturnAdjustment ReturnAdjustment) {1343  if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {1344    assert(ReturnAdjustment.isEmpty() &&1345           "Destructor can't have return adjustment!");1346 1347    // Add both the complete destructor and the deleting destructor.1348    Components.push_back(VTableComponent::MakeCompleteDtor(DD));1349    Components.push_back(VTableComponent::MakeDeletingDtor(DD));1350  } else {1351    // Add the return adjustment if necessary.1352    if (!ReturnAdjustment.isEmpty())1353      VTableThunks[Components.size()].Return = ReturnAdjustment;1354 1355    // Add the function.1356    Components.push_back(VTableComponent::MakeFunction(MD));1357  }1358}1359 1360/// OverridesIndirectMethodInBase - Return whether the given member function1361/// overrides any methods in the set of given bases.1362/// Unlike OverridesMethodInBase, this checks "overriders of overriders".1363/// For example, if we have:1364///1365/// struct A { virtual void f(); }1366/// struct B : A { virtual void f(); }1367/// struct C : B { virtual void f(); }1368///1369/// OverridesIndirectMethodInBase will return true if given C::f as the method1370/// and { A } as the set of bases.1371static bool OverridesIndirectMethodInBases(1372    const CXXMethodDecl *MD,1373    ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {1374  if (Bases.count(MD->getParent()))1375    return true;1376 1377  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {1378    // Check "indirect overriders".1379    if (OverridesIndirectMethodInBases(OverriddenMD, Bases))1380      return true;1381  }1382 1383  return false;1384}1385 1386bool ItaniumVTableBuilder::IsOverriderUsed(1387    const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,1388    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,1389    CharUnits FirstBaseOffsetInLayoutClass) const {1390  // If the base and the first base in the primary base chain have the same1391  // offsets, then this overrider will be used.1392  if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)1393   return true;1394 1395  // We know now that Base (or a direct or indirect base of it) is a primary1396  // base in part of the class hierarchy, but not a primary base in the most1397  // derived class.1398 1399  // If the overrider is the first base in the primary base chain, we know1400  // that the overrider will be used.1401  if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)1402    return true;1403 1404  ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;1405 1406  const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;1407  PrimaryBases.insert(RD);1408 1409  // Now traverse the base chain, starting with the first base, until we find1410  // the base that is no longer a primary base.1411  while (true) {1412    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);1413    const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();1414 1415    if (!PrimaryBase)1416      break;1417 1418    if (Layout.isPrimaryBaseVirtual()) {1419      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&1420             "Primary base should always be at offset 0!");1421 1422      const ASTRecordLayout &LayoutClassLayout =1423        Context.getASTRecordLayout(LayoutClass);1424 1425      // Now check if this is the primary base that is not a primary base in the1426      // most derived class.1427      if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=1428          FirstBaseOffsetInLayoutClass) {1429        // We found it, stop walking the chain.1430        break;1431      }1432    } else {1433      assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&1434             "Primary base should always be at offset 0!");1435    }1436 1437    if (!PrimaryBases.insert(PrimaryBase))1438      llvm_unreachable("Found a duplicate primary base!");1439 1440    RD = PrimaryBase;1441  }1442 1443  // If the final overrider is an override of one of the primary bases,1444  // then we know that it will be used.1445  return OverridesIndirectMethodInBases(Overrider, PrimaryBases);1446}1447 1448typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;1449 1450/// FindNearestOverriddenMethod - Given a method, returns the overridden method1451/// from the nearest base. Returns null if no method was found.1452/// The Bases are expected to be sorted in a base-to-derived order.1453static const CXXMethodDecl *1454FindNearestOverriddenMethod(const CXXMethodDecl *MD,1455                            BasesSetVectorTy &Bases) {1456  OverriddenMethodsSetTy OverriddenMethods;1457  ComputeAllOverriddenMethods(MD, OverriddenMethods);1458 1459  for (const CXXRecordDecl *PrimaryBase : llvm::reverse(Bases)) {1460    // Now check the overridden methods.1461    for (const CXXMethodDecl *OverriddenMD : OverriddenMethods) {1462      // We found our overridden method.1463      if (OverriddenMD->getParent() == PrimaryBase)1464        return OverriddenMD;1465    }1466  }1467 1468  return nullptr;1469}1470 1471void ItaniumVTableBuilder::AddMethods(1472    BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,1473    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,1474    CharUnits FirstBaseOffsetInLayoutClass,1475    PrimaryBasesSetVectorTy &PrimaryBases) {1476  // Itanium C++ ABI 2.5.2:1477  //   The order of the virtual function pointers in a virtual table is the1478  //   order of declaration of the corresponding member functions in the class.1479  //1480  //   There is an entry for any virtual function declared in a class,1481  //   whether it is a new function or overrides a base class function,1482  //   unless it overrides a function from the primary base, and conversion1483  //   between their return types does not require an adjustment.1484 1485  const CXXRecordDecl *RD = Base.getBase();1486  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);1487 1488  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {1489    CharUnits PrimaryBaseOffset;1490    CharUnits PrimaryBaseOffsetInLayoutClass;1491    if (Layout.isPrimaryBaseVirtual()) {1492      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&1493             "Primary vbase should have a zero offset!");1494 1495      const ASTRecordLayout &MostDerivedClassLayout =1496        Context.getASTRecordLayout(MostDerivedClass);1497 1498      PrimaryBaseOffset =1499        MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);1500 1501      const ASTRecordLayout &LayoutClassLayout =1502        Context.getASTRecordLayout(LayoutClass);1503 1504      PrimaryBaseOffsetInLayoutClass =1505        LayoutClassLayout.getVBaseClassOffset(PrimaryBase);1506    } else {1507      assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&1508             "Primary base should have a zero offset!");1509 1510      PrimaryBaseOffset = Base.getBaseOffset();1511      PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;1512    }1513 1514    AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset),1515               PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain,1516               FirstBaseOffsetInLayoutClass, PrimaryBases);1517 1518    if (!PrimaryBases.insert(PrimaryBase))1519      llvm_unreachable("Found a duplicate primary base!");1520  }1521 1522  typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;1523  NewVirtualFunctionsTy NewVirtualFunctions;1524 1525  llvm::SmallVector<const CXXMethodDecl*, 4> NewImplicitVirtualFunctions;1526 1527  // Now go through all virtual member functions and add them.1528  for (const auto *MD : RD->methods()) {1529    if (!ItaniumVTableContext::hasVtableSlot(MD))1530      continue;1531    MD = MD->getCanonicalDecl();1532 1533    // Get the final overrider.1534    FinalOverriders::OverriderInfo Overrider =1535      Overriders.getOverrider(MD, Base.getBaseOffset());1536 1537    // Check if this virtual member function overrides a method in a primary1538    // base. If this is the case, and the return type doesn't require adjustment1539    // then we can just use the member function from the primary base.1540    if (const CXXMethodDecl *OverriddenMD =1541          FindNearestOverriddenMethod(MD, PrimaryBases)) {1542      if (ComputeReturnAdjustmentBaseOffset(Context, MD,1543                                            OverriddenMD).isEmpty()) {1544        VTables.setOriginalMethod(MD, OverriddenMD);1545 1546        // Replace the method info of the overridden method with our own1547        // method.1548        assert(MethodInfoMap.count(OverriddenMD) &&1549               "Did not find the overridden method!");1550        MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];1551 1552        MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,1553                              OverriddenMethodInfo.VTableIndex);1554 1555        assert(!MethodInfoMap.count(MD) &&1556               "Should not have method info for this method yet!");1557 1558        MethodInfoMap.insert(std::make_pair(MD, MethodInfo));1559        MethodInfoMap.erase(OverriddenMD);1560 1561        // If the overridden method exists in a virtual base class or a direct1562        // or indirect base class of a virtual base class, we need to emit a1563        // thunk if we ever have a class hierarchy where the base class is not1564        // a primary base in the complete object.1565        if (!isBuildingConstructorVTable() && OverriddenMD != MD) {1566          // Compute the this adjustment.1567          ThisAdjustment ThisAdjustment =1568            ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass,1569                                  Overrider);1570 1571          if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&1572              Overrider.Method->getParent() == MostDerivedClass) {1573 1574            // There's no return adjustment from OverriddenMD and MD,1575            // but that doesn't mean there isn't one between MD and1576            // the final overrider.1577            BaseOffset ReturnAdjustmentOffset =1578              ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);1579            ReturnAdjustment ReturnAdjustment =1580              ComputeReturnAdjustment(ReturnAdjustmentOffset);1581 1582            // This is a virtual thunk for the most derived class, add it.1583            AddThunk(Overrider.Method,1584                     ThunkInfo(ThisAdjustment, ReturnAdjustment,1585                               OverriddenMD->getThisType().getTypePtr()));1586          }1587        }1588 1589        continue;1590      }1591    }1592 1593    if (MD->isImplicit())1594      NewImplicitVirtualFunctions.push_back(MD);1595    else1596      NewVirtualFunctions.push_back(MD);1597  }1598 1599  llvm::stable_sort(1600      NewImplicitVirtualFunctions,1601      [](const CXXMethodDecl *A, const CXXMethodDecl *B) {1602        if (A == B)1603          return false;1604        if (A->isCopyAssignmentOperator() != B->isCopyAssignmentOperator())1605          return A->isCopyAssignmentOperator();1606        if (A->isMoveAssignmentOperator() != B->isMoveAssignmentOperator())1607          return A->isMoveAssignmentOperator();1608        if (isa<CXXDestructorDecl>(A) != isa<CXXDestructorDecl>(B))1609          return isa<CXXDestructorDecl>(A);1610        assert(A->getOverloadedOperator() == OO_EqualEqual &&1611               B->getOverloadedOperator() == OO_EqualEqual &&1612               "unexpected or duplicate implicit virtual function");1613        // We rely on Sema to have declared the operator== members in the1614        // same order as the corresponding operator<=> members.1615        return false;1616      });1617  NewVirtualFunctions.append(NewImplicitVirtualFunctions.begin(),1618                             NewImplicitVirtualFunctions.end());1619 1620  for (const CXXMethodDecl *MD : NewVirtualFunctions) {1621    // Get the final overrider.1622    FinalOverriders::OverriderInfo Overrider =1623      Overriders.getOverrider(MD, Base.getBaseOffset());1624 1625    // Insert the method info for this method.1626    MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,1627                          Components.size());1628 1629    assert(!MethodInfoMap.count(MD) &&1630           "Should not have method info for this method yet!");1631    MethodInfoMap.insert(std::make_pair(MD, MethodInfo));1632 1633    // Check if this overrider is going to be used.1634    const CXXMethodDecl *OverriderMD = Overrider.Method;1635    if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass,1636                         FirstBaseInPrimaryBaseChain,1637                         FirstBaseOffsetInLayoutClass)) {1638      Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD));1639      continue;1640    }1641 1642    // Check if this overrider needs a return adjustment.1643    // We don't want to do this for pure virtual member functions.1644    BaseOffset ReturnAdjustmentOffset;1645    if (!OverriderMD->isPureVirtual()) {1646      ReturnAdjustmentOffset =1647        ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);1648    }1649 1650    ReturnAdjustment ReturnAdjustment =1651      ComputeReturnAdjustment(ReturnAdjustmentOffset);1652 1653    // If a return adjustment is required, record the method that created the1654    // vtable entry. We need to record the method because we cannot call1655    // findOriginalMethod to find the method that created the entry if the1656    // method in the entry requires adjustment.1657    if (!ReturnAdjustment.isEmpty()) {1658      auto &VTT = VTableThunks[Components.size()];1659      VTT.Method = MD;1660      VTT.ThisType = MD->getThisType().getTypePtr();1661    }1662 1663    AddMethod(Overrider.Method, ReturnAdjustment);1664  }1665}1666 1667void ItaniumVTableBuilder::LayoutVTable() {1668  LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass,1669                                                 CharUnits::Zero()),1670                                   /*BaseIsMorallyVirtual=*/false,1671                                   MostDerivedClassIsVirtual,1672                                   MostDerivedClassOffset);1673 1674  VisitedVirtualBasesSetTy VBases;1675 1676  // Determine the primary virtual bases.1677  DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset,1678                               VBases);1679  VBases.clear();1680 1681  LayoutVTablesForVirtualBases(MostDerivedClass, VBases);1682 1683  // -fapple-kext adds an extra entry at end of vtbl.1684  bool IsAppleKext = Context.getLangOpts().AppleKext;1685  if (IsAppleKext)1686    Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));1687}1688 1689void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(1690    BaseSubobject Base, bool BaseIsMorallyVirtual,1691    bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {1692  assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");1693 1694  unsigned VTableIndex = Components.size();1695  VTableIndices.push_back(VTableIndex);1696 1697  // Add vcall and vbase offsets for this vtable.1698  VCallAndVBaseOffsetBuilder Builder(1699      VTables, MostDerivedClass, LayoutClass, &Overriders, Base,1700      BaseIsVirtualInLayoutClass, OffsetInLayoutClass);1701  Components.append(Builder.components_begin(), Builder.components_end());1702 1703  // Check if we need to add these vcall offsets.1704  if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {1705    VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];1706 1707    if (VCallOffsets.empty())1708      VCallOffsets = Builder.getVCallOffsets();1709  }1710 1711  // If we're laying out the most derived class we want to keep track of the1712  // virtual base class offset offsets.1713  if (Base.getBase() == MostDerivedClass)1714    VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();1715 1716  // Add the offset to top.1717  CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;1718  Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop));1719 1720  // Next, add the RTTI.1721  if (!Context.getLangOpts().OmitVTableRTTI)1722    Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));1723 1724  uint64_t AddressPoint = Components.size();1725 1726  // Now go through all virtual member functions and add them.1727  PrimaryBasesSetVectorTy PrimaryBases;1728  AddMethods(Base, OffsetInLayoutClass,1729             Base.getBase(), OffsetInLayoutClass,1730             PrimaryBases);1731 1732  const CXXRecordDecl *RD = Base.getBase();1733  if (RD == MostDerivedClass) {1734    assert(MethodVTableIndices.empty());1735    for (const auto &I : MethodInfoMap) {1736      const CXXMethodDecl *MD = I.first;1737      const MethodInfo &MI = I.second;1738      if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {1739        MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]1740            = MI.VTableIndex - AddressPoint;1741        MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]1742            = MI.VTableIndex + 1 - AddressPoint;1743      } else {1744        MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;1745      }1746    }1747  }1748 1749  // Compute 'this' pointer adjustments.1750  ComputeThisAdjustments();1751 1752  // Add all address points.1753  while (true) {1754    AddressPoints.insert(1755        std::make_pair(BaseSubobject(RD, OffsetInLayoutClass),1756                       VTableLayout::AddressPointLocation{1757                           unsigned(VTableIndices.size() - 1),1758                           unsigned(AddressPoint - VTableIndex)}));1759 1760    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);1761    const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();1762 1763    if (!PrimaryBase)1764      break;1765 1766    if (Layout.isPrimaryBaseVirtual()) {1767      // Check if this virtual primary base is a primary base in the layout1768      // class. If it's not, we don't want to add it.1769      const ASTRecordLayout &LayoutClassLayout =1770        Context.getASTRecordLayout(LayoutClass);1771 1772      if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=1773          OffsetInLayoutClass) {1774        // We don't want to add this class (or any of its primary bases).1775        break;1776      }1777    }1778 1779    RD = PrimaryBase;1780  }1781 1782  // Layout secondary vtables.1783  LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);1784}1785 1786void1787ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,1788                                             bool BaseIsMorallyVirtual,1789                                             CharUnits OffsetInLayoutClass) {1790  // Itanium C++ ABI 2.5.2:1791  //   Following the primary virtual table of a derived class are secondary1792  //   virtual tables for each of its proper base classes, except any primary1793  //   base(s) with which it shares its primary virtual table.1794 1795  const CXXRecordDecl *RD = Base.getBase();1796  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);1797  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();1798 1799  for (const auto &B : RD->bases()) {1800    // Ignore virtual bases, we'll emit them later.1801    if (B.isVirtual())1802      continue;1803 1804    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();1805 1806    // Ignore bases that don't have a vtable.1807    if (!BaseDecl->isDynamicClass())1808      continue;1809 1810    if (isBuildingConstructorVTable()) {1811      // Itanium C++ ABI 2.6.4:1812      //   Some of the base class subobjects may not need construction virtual1813      //   tables, which will therefore not be present in the construction1814      //   virtual table group, even though the subobject virtual tables are1815      //   present in the main virtual table group for the complete object.1816      if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases())1817        continue;1818    }1819 1820    // Get the base offset of this base.1821    CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl);1822    CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset;1823 1824    CharUnits BaseOffsetInLayoutClass =1825      OffsetInLayoutClass + RelativeBaseOffset;1826 1827    // Don't emit a secondary vtable for a primary base. We might however want1828    // to emit secondary vtables for other bases of this base.1829    if (BaseDecl == PrimaryBase) {1830      LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset),1831                             BaseIsMorallyVirtual, BaseOffsetInLayoutClass);1832      continue;1833    }1834 1835    // Layout the primary vtable (and any secondary vtables) for this base.1836    LayoutPrimaryAndSecondaryVTables(1837      BaseSubobject(BaseDecl, BaseOffset),1838      BaseIsMorallyVirtual,1839      /*BaseIsVirtualInLayoutClass=*/false,1840      BaseOffsetInLayoutClass);1841  }1842}1843 1844void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(1845    const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,1846    VisitedVirtualBasesSetTy &VBases) {1847  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);1848 1849  // Check if this base has a primary base.1850  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {1851 1852    // Check if it's virtual.1853    if (Layout.isPrimaryBaseVirtual()) {1854      bool IsPrimaryVirtualBase = true;1855 1856      if (isBuildingConstructorVTable()) {1857        // Check if the base is actually a primary base in the class we use for1858        // layout.1859        const ASTRecordLayout &LayoutClassLayout =1860          Context.getASTRecordLayout(LayoutClass);1861 1862        CharUnits PrimaryBaseOffsetInLayoutClass =1863          LayoutClassLayout.getVBaseClassOffset(PrimaryBase);1864 1865        // We know that the base is not a primary base in the layout class if1866        // the base offsets are different.1867        if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)1868          IsPrimaryVirtualBase = false;1869      }1870 1871      if (IsPrimaryVirtualBase)1872        PrimaryVirtualBases.insert(PrimaryBase);1873    }1874  }1875 1876  // Traverse bases, looking for more primary virtual bases.1877  for (const auto &B : RD->bases()) {1878    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();1879 1880    CharUnits BaseOffsetInLayoutClass;1881 1882    if (B.isVirtual()) {1883      if (!VBases.insert(BaseDecl).second)1884        continue;1885 1886      const ASTRecordLayout &LayoutClassLayout =1887        Context.getASTRecordLayout(LayoutClass);1888 1889      BaseOffsetInLayoutClass =1890        LayoutClassLayout.getVBaseClassOffset(BaseDecl);1891    } else {1892      BaseOffsetInLayoutClass =1893        OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl);1894    }1895 1896    DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases);1897  }1898}1899 1900void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(1901    const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) {1902  // Itanium C++ ABI 2.5.2:1903  //   Then come the virtual base virtual tables, also in inheritance graph1904  //   order, and again excluding primary bases (which share virtual tables with1905  //   the classes for which they are primary).1906  for (const auto &B : RD->bases()) {1907    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();1908 1909    // Check if this base needs a vtable. (If it's virtual, not a primary base1910    // of some other class, and we haven't visited it before).1911    if (B.isVirtual() && BaseDecl->isDynamicClass() &&1912        !PrimaryVirtualBases.count(BaseDecl) &&1913        VBases.insert(BaseDecl).second) {1914      const ASTRecordLayout &MostDerivedClassLayout =1915        Context.getASTRecordLayout(MostDerivedClass);1916      CharUnits BaseOffset =1917        MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);1918 1919      const ASTRecordLayout &LayoutClassLayout =1920        Context.getASTRecordLayout(LayoutClass);1921      CharUnits BaseOffsetInLayoutClass =1922        LayoutClassLayout.getVBaseClassOffset(BaseDecl);1923 1924      LayoutPrimaryAndSecondaryVTables(1925        BaseSubobject(BaseDecl, BaseOffset),1926        /*BaseIsMorallyVirtual=*/true,1927        /*BaseIsVirtualInLayoutClass=*/true,1928        BaseOffsetInLayoutClass);1929    }1930 1931    // We only need to check the base for virtual base vtables if it actually1932    // has virtual bases.1933    if (BaseDecl->getNumVBases())1934      LayoutVTablesForVirtualBases(BaseDecl, VBases);1935  }1936}1937 1938static void printThunkMethod(const ThunkInfo &Info, raw_ostream &Out) {1939  if (!Info.Method)1940    return;1941  std::string Str = PredefinedExpr::ComputeName(1942      PredefinedIdentKind::PrettyFunctionNoVirtual, Info.Method);1943  Out << " method: " << Str;1944}1945 1946/// dumpLayout - Dump the vtable layout.1947void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {1948  // FIXME: write more tests that actually use the dumpLayout output to prevent1949  // ItaniumVTableBuilder regressions.1950 1951  Out << "Original map\n";1952 1953  for (const auto &P : VTables.getOriginalMethodMap()) {1954    std::string Str0 =1955        PredefinedExpr::ComputeName(PredefinedIdentKind::PrettyFunctionNoVirtual,1956                                    P.first);1957    std::string Str1 =1958        PredefinedExpr::ComputeName(PredefinedIdentKind::PrettyFunctionNoVirtual,1959                                    P.second);1960    Out << " " << Str0 << " -> " << Str1 << "\n";1961  }1962 1963  if (isBuildingConstructorVTable()) {1964    Out << "Construction vtable for ('";1965    MostDerivedClass->printQualifiedName(Out);1966    Out << "', ";1967    Out << MostDerivedClassOffset.getQuantity() << ") in '";1968    LayoutClass->printQualifiedName(Out);1969  } else {1970    Out << "Vtable for '";1971    MostDerivedClass->printQualifiedName(Out);1972  }1973  Out << "' (" << Components.size() << " entries).\n";1974 1975  // Iterate through the address points and insert them into a new map where1976  // they are keyed by the index and not the base object.1977  // Since an address point can be shared by multiple subobjects, we use an1978  // STL multimap.1979  std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;1980  for (const auto &AP : AddressPoints) {1981    const BaseSubobject &Base = AP.first;1982    uint64_t Index =1983        VTableIndices[AP.second.VTableIndex] + AP.second.AddressPointIndex;1984 1985    AddressPointsByIndex.insert(std::make_pair(Index, Base));1986  }1987 1988  for (unsigned I = 0, E = Components.size(); I != E; ++I) {1989    uint64_t Index = I;1990 1991    Out << llvm::format("%4d | ", I);1992 1993    const VTableComponent &Component = Components[I];1994 1995    // Dump the component.1996    switch (Component.getKind()) {1997 1998    case VTableComponent::CK_VCallOffset:1999      Out << "vcall_offset ("2000          << Component.getVCallOffset().getQuantity()2001          << ")";2002      break;2003 2004    case VTableComponent::CK_VBaseOffset:2005      Out << "vbase_offset ("2006          << Component.getVBaseOffset().getQuantity()2007          << ")";2008      break;2009 2010    case VTableComponent::CK_OffsetToTop:2011      Out << "offset_to_top ("2012          << Component.getOffsetToTop().getQuantity()2013          << ")";2014      break;2015 2016    case VTableComponent::CK_RTTI:2017      Component.getRTTIDecl()->printQualifiedName(Out);2018      Out << " RTTI";2019      break;2020 2021    case VTableComponent::CK_FunctionPointer: {2022      const CXXMethodDecl *MD = Component.getFunctionDecl();2023 2024      std::string Str = PredefinedExpr::ComputeName(2025          PredefinedIdentKind::PrettyFunctionNoVirtual, MD);2026      Out << Str;2027      if (MD->isPureVirtual())2028        Out << " [pure]";2029 2030      if (MD->isDeleted())2031        Out << " [deleted]";2032 2033      ThunkInfo Thunk = VTableThunks.lookup(I);2034      if (!Thunk.isEmpty()) {2035        // If this function pointer has a return adjustment, dump it.2036        if (!Thunk.Return.isEmpty()) {2037          Out << "\n       [return adjustment: ";2038          Out << Thunk.Return.NonVirtual << " non-virtual";2039 2040          if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {2041            Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;2042            Out << " vbase offset offset";2043          }2044 2045          Out << ']';2046          printThunkMethod(Thunk, Out);2047        }2048 2049        // If this function pointer has a 'this' pointer adjustment, dump it.2050        if (!Thunk.This.isEmpty()) {2051          Out << "\n       [this adjustment: ";2052          Out << Thunk.This.NonVirtual << " non-virtual";2053 2054          if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {2055            Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;2056            Out << " vcall offset offset";2057          }2058 2059          Out << ']';2060          printThunkMethod(Thunk, Out);2061        }2062      }2063 2064      break;2065    }2066 2067    case VTableComponent::CK_CompleteDtorPointer:2068    case VTableComponent::CK_DeletingDtorPointer: {2069      bool IsComplete =2070        Component.getKind() == VTableComponent::CK_CompleteDtorPointer;2071 2072      const CXXDestructorDecl *DD = Component.getDestructorDecl();2073 2074      DD->printQualifiedName(Out);2075      if (IsComplete)2076        Out << "() [complete]";2077      else2078        Out << "() [deleting]";2079 2080      if (DD->isPureVirtual())2081        Out << " [pure]";2082 2083      ThunkInfo Thunk = VTableThunks.lookup(I);2084      if (!Thunk.isEmpty()) {2085        // If this destructor has a 'this' pointer adjustment, dump it.2086        if (!Thunk.This.isEmpty()) {2087          Out << "\n       [this adjustment: ";2088          Out << Thunk.This.NonVirtual << " non-virtual";2089 2090          if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {2091            Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;2092            Out << " vcall offset offset";2093          }2094 2095          Out << ']';2096        }2097        printThunkMethod(Thunk, Out);2098      }2099 2100      break;2101    }2102 2103    case VTableComponent::CK_UnusedFunctionPointer: {2104      const CXXMethodDecl *MD = Component.getUnusedFunctionDecl();2105 2106      std::string Str = PredefinedExpr::ComputeName(2107          PredefinedIdentKind::PrettyFunctionNoVirtual, MD);2108      Out << "[unused] " << Str;2109      if (MD->isPureVirtual())2110        Out << " [pure]";2111    }2112 2113    }2114 2115    Out << '\n';2116 2117    // Dump the next address point.2118    uint64_t NextIndex = Index + 1;2119    if (unsigned Count = AddressPointsByIndex.count(NextIndex)) {2120      if (Count == 1) {2121        const BaseSubobject &Base =2122          AddressPointsByIndex.find(NextIndex)->second;2123 2124        Out << "       -- (";2125        Base.getBase()->printQualifiedName(Out);2126        Out << ", " << Base.getBaseOffset().getQuantity();2127        Out << ") vtable address --\n";2128      } else {2129        CharUnits BaseOffset =2130          AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset();2131 2132        // We store the class names in a set to get a stable order.2133        std::set<std::string> ClassNames;2134        for (const auto &I :2135             llvm::make_range(AddressPointsByIndex.equal_range(NextIndex))) {2136          assert(I.second.getBaseOffset() == BaseOffset &&2137                 "Invalid base offset!");2138          const CXXRecordDecl *RD = I.second.getBase();2139          ClassNames.insert(RD->getQualifiedNameAsString());2140        }2141 2142        for (const std::string &Name : ClassNames) {2143          Out << "       -- (" << Name;2144          Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n";2145        }2146      }2147    }2148  }2149 2150  Out << '\n';2151 2152  if (isBuildingConstructorVTable())2153    return;2154 2155  if (MostDerivedClass->getNumVBases()) {2156    // We store the virtual base class names and their offsets in a map to get2157    // a stable order.2158 2159    std::map<std::string, CharUnits> ClassNamesAndOffsets;2160    for (const auto &I : VBaseOffsetOffsets) {2161      std::string ClassName = I.first->getQualifiedNameAsString();2162      CharUnits OffsetOffset = I.second;2163      ClassNamesAndOffsets.insert(std::make_pair(ClassName, OffsetOffset));2164    }2165 2166    Out << "Virtual base offset offsets for '";2167    MostDerivedClass->printQualifiedName(Out);2168    Out << "' (";2169    Out << ClassNamesAndOffsets.size();2170    Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n";2171 2172    for (const auto &I : ClassNamesAndOffsets)2173      Out << "   " << I.first << " | " << I.second.getQuantity() << '\n';2174 2175    Out << "\n";2176  }2177 2178  if (!Thunks.empty()) {2179    // We store the method names in a map to get a stable order.2180    std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;2181 2182    for (const auto &I : Thunks) {2183      const CXXMethodDecl *MD = I.first;2184      std::string MethodName = PredefinedExpr::ComputeName(2185          PredefinedIdentKind::PrettyFunctionNoVirtual, MD);2186 2187      MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));2188    }2189 2190    for (const auto &I : MethodNamesAndDecls) {2191      const std::string &MethodName = I.first;2192      const CXXMethodDecl *MD = I.second;2193 2194      ThunkInfoVectorTy ThunksVector = Thunks[MD];2195      llvm::sort(ThunksVector, [](const ThunkInfo &LHS, const ThunkInfo &RHS) {2196        return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);2197      });2198 2199      Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();2200      Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";2201 2202      for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {2203        const ThunkInfo &Thunk = ThunksVector[I];2204 2205        Out << llvm::format("%4d | ", I);2206 2207        // If this function pointer has a return pointer adjustment, dump it.2208        if (!Thunk.Return.isEmpty()) {2209          Out << "return adjustment: " << Thunk.Return.NonVirtual;2210          Out << " non-virtual";2211          if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {2212            Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;2213            Out << " vbase offset offset";2214          }2215 2216          if (!Thunk.This.isEmpty())2217            Out << "\n       ";2218        }2219 2220        // If this function pointer has a 'this' pointer adjustment, dump it.2221        if (!Thunk.This.isEmpty()) {2222          Out << "this adjustment: ";2223          Out << Thunk.This.NonVirtual << " non-virtual";2224 2225          if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {2226            Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;2227            Out << " vcall offset offset";2228          }2229        }2230 2231        Out << '\n';2232      }2233 2234      Out << '\n';2235    }2236  }2237 2238  // Compute the vtable indices for all the member functions.2239  // Store them in a map keyed by the index so we'll get a sorted table.2240  std::map<uint64_t, std::string> IndicesMap;2241 2242  for (const auto *MD : MostDerivedClass->methods()) {2243    // We only want virtual member functions.2244    if (!ItaniumVTableContext::hasVtableSlot(MD))2245      continue;2246    MD = MD->getCanonicalDecl();2247 2248    std::string MethodName = PredefinedExpr::ComputeName(2249        PredefinedIdentKind::PrettyFunctionNoVirtual, MD);2250 2251    if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {2252      GlobalDecl GD(DD, Dtor_Complete);2253      assert(MethodVTableIndices.count(GD));2254      uint64_t VTableIndex = MethodVTableIndices[GD];2255      IndicesMap[VTableIndex] = MethodName + " [complete]";2256      IndicesMap[VTableIndex + 1] = MethodName + " [deleting]";2257    } else {2258      assert(MethodVTableIndices.count(MD));2259      IndicesMap[MethodVTableIndices[MD]] = MethodName;2260    }2261  }2262 2263  // Print the vtable indices for all the member functions.2264  if (!IndicesMap.empty()) {2265    Out << "VTable indices for '";2266    MostDerivedClass->printQualifiedName(Out);2267    Out << "' (" << IndicesMap.size() << " entries).\n";2268 2269    for (const auto &I : IndicesMap) {2270      uint64_t VTableIndex = I.first;2271      const std::string &MethodName = I.second;2272 2273      Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName2274          << '\n';2275    }2276  }2277 2278  Out << '\n';2279}2280}2281 2282static VTableLayout::AddressPointsIndexMapTy2283MakeAddressPointIndices(const VTableLayout::AddressPointsMapTy &addressPoints,2284                        unsigned numVTables) {2285  VTableLayout::AddressPointsIndexMapTy indexMap(numVTables);2286 2287  for (auto it = addressPoints.begin(); it != addressPoints.end(); ++it) {2288    const auto &addressPointLoc = it->second;2289    unsigned vtableIndex = addressPointLoc.VTableIndex;2290    unsigned addressPoint = addressPointLoc.AddressPointIndex;2291    if (indexMap[vtableIndex]) {2292      // Multiple BaseSubobjects can map to the same AddressPointLocation, but2293      // every vtable index should have a unique address point.2294      assert(indexMap[vtableIndex] == addressPoint &&2295             "Every vtable index should have a unique address point. Found a "2296             "vtable that has two different address points.");2297    } else {2298      indexMap[vtableIndex] = addressPoint;2299    }2300  }2301 2302  // Note that by this point, not all the address may be initialized if the2303  // AddressPoints map is empty. This is ok if the map isn't needed. See2304  // MicrosoftVTableContext::computeVTableRelatedInformation() which uses an2305  // emprt map.2306  return indexMap;2307}2308 2309VTableLayout::VTableLayout(ArrayRef<size_t> VTableIndices,2310                           ArrayRef<VTableComponent> VTableComponents,2311                           ArrayRef<VTableThunkTy> VTableThunks,2312                           const AddressPointsMapTy &AddressPoints)2313    : VTableComponents(VTableComponents), VTableThunks(VTableThunks),2314      AddressPoints(AddressPoints), AddressPointIndices(MakeAddressPointIndices(2315                                        AddressPoints, VTableIndices.size())) {2316  if (VTableIndices.size() <= 1)2317    assert(VTableIndices.size() == 1 && VTableIndices[0] == 0);2318  else2319    this->VTableIndices = OwningArrayRef<size_t>(VTableIndices);2320 2321  llvm::sort(this->VTableThunks, [](const VTableLayout::VTableThunkTy &LHS,2322                                    const VTableLayout::VTableThunkTy &RHS) {2323    assert((LHS.first != RHS.first || LHS.second == RHS.second) &&2324           "Different thunks should have unique indices!");2325    return LHS.first < RHS.first;2326  });2327}2328 2329VTableLayout::~VTableLayout() { }2330 2331bool VTableContextBase::hasVtableSlot(const CXXMethodDecl *MD) {2332  return MD->isVirtual() && !MD->isImmediateFunction();2333}2334 2335ItaniumVTableContext::ItaniumVTableContext(2336    ASTContext &Context, VTableComponentLayout ComponentLayout)2337    : VTableContextBase(/*MS=*/false), ComponentLayout(ComponentLayout) {}2338 2339ItaniumVTableContext::~ItaniumVTableContext() {}2340 2341uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {2342  GD = GD.getCanonicalDecl();2343  MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD);2344  if (I != MethodVTableIndices.end())2345    return I->second;2346 2347  const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();2348 2349  computeVTableRelatedInformation(RD);2350 2351  I = MethodVTableIndices.find(GD);2352  assert(I != MethodVTableIndices.end() && "Did not find index!");2353  return I->second;2354}2355 2356CharUnits2357ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,2358                                                 const CXXRecordDecl *VBase) {2359  ClassPairTy ClassPair(RD, VBase);2360 2361  VirtualBaseClassOffsetOffsetsMapTy::iterator I =2362    VirtualBaseClassOffsetOffsets.find(ClassPair);2363  if (I != VirtualBaseClassOffsetOffsets.end())2364    return I->second;2365 2366  VCallAndVBaseOffsetBuilder Builder(*this, RD, RD, /*Overriders=*/nullptr,2367                                     BaseSubobject(RD, CharUnits::Zero()),2368                                     /*BaseIsVirtual=*/false,2369                                     /*OffsetInLayoutClass=*/CharUnits::Zero());2370 2371  for (const auto &I : Builder.getVBaseOffsetOffsets()) {2372    // Insert all types.2373    ClassPairTy ClassPair(RD, I.first);2374 2375    VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));2376  }2377 2378  I = VirtualBaseClassOffsetOffsets.find(ClassPair);2379  assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");2380 2381  return I->second;2382}2383 2384GlobalDecl ItaniumVTableContext::findOriginalMethod(GlobalDecl GD) {2385  const auto *MD = cast<CXXMethodDecl>(GD.getDecl());2386  computeVTableRelatedInformation(MD->getParent());2387  const CXXMethodDecl *OriginalMD = findOriginalMethodInMap(MD);2388 2389  if (const auto *DD = dyn_cast<CXXDestructorDecl>(OriginalMD))2390    return GlobalDecl(DD, GD.getDtorType());2391  return OriginalMD;2392}2393 2394const CXXMethodDecl *2395ItaniumVTableContext::findOriginalMethodInMap(const CXXMethodDecl *MD) const {2396  // Traverse the chain of virtual methods until we find the method that added2397  // the v-table slot.2398  while (true) {2399    auto I = OriginalMethodMap.find(MD);2400 2401    // MD doesn't exist in OriginalMethodMap, so it must be the method we are2402    // looking for.2403    if (I == OriginalMethodMap.end())2404      break;2405 2406    // Set MD to the overridden method.2407    MD = I->second;2408  }2409 2410  return MD;2411}2412 2413static std::unique_ptr<VTableLayout>2414CreateVTableLayout(const ItaniumVTableBuilder &Builder) {2415  SmallVector<VTableLayout::VTableThunkTy, 1>2416    VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());2417 2418  return std::make_unique<VTableLayout>(2419      Builder.VTableIndices, Builder.vtable_components(), VTableThunks,2420      Builder.getAddressPoints());2421}2422 2423void2424ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {2425  std::unique_ptr<const VTableLayout> &Entry = VTableLayouts[RD];2426 2427  // Check if we've computed this information before.2428  if (Entry)2429    return;2430 2431  ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),2432                               /*MostDerivedClassIsVirtual=*/false, RD);2433  Entry = CreateVTableLayout(Builder);2434 2435  MethodVTableIndices.insert(Builder.vtable_indices_begin(),2436                             Builder.vtable_indices_end());2437 2438  // Add the known thunks.2439  Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());2440 2441  // If we don't have the vbase information for this class, insert it.2442  // getVirtualBaseOffsetOffset will compute it separately without computing2443  // the rest of the vtable related information.2444  if (!RD->getNumVBases())2445    return;2446 2447  const CXXRecordDecl *VBase =2448    RD->vbases_begin()->getType()->getAsCXXRecordDecl();2449 2450  if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase)))2451    return;2452 2453  for (const auto &I : Builder.getVBaseOffsetOffsets()) {2454    // Insert all types.2455    ClassPairTy ClassPair(RD, I.first);2456 2457    VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));2458  }2459}2460 2461std::unique_ptr<VTableLayout>2462ItaniumVTableContext::createConstructionVTableLayout(2463    const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,2464    bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {2465  ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,2466                               MostDerivedClassIsVirtual, LayoutClass);2467  return CreateVTableLayout(Builder);2468}2469 2470namespace {2471 2472// Vtables in the Microsoft ABI are different from the Itanium ABI.2473//2474// The main differences are:2475//  1. Separate vftable and vbtable.2476//2477//  2. Each subobject with a vfptr gets its own vftable rather than an address2478//     point in a single vtable shared between all the subobjects.2479//     Each vftable is represented by a separate section and virtual calls2480//     must be done using the vftable which has a slot for the function to be2481//     called.2482//2483//  3. Virtual method definitions expect their 'this' parameter to point to the2484//     first vfptr whose table provides a compatible overridden method.  In many2485//     cases, this permits the original vf-table entry to directly call2486//     the method instead of passing through a thunk.2487//     See example before VFTableBuilder::ComputeThisOffset below.2488//2489//     A compatible overridden method is one which does not have a non-trivial2490//     covariant-return adjustment.2491//2492//     The first vfptr is the one with the lowest offset in the complete-object2493//     layout of the defining class, and the method definition will subtract2494//     that constant offset from the parameter value to get the real 'this'2495//     value.  Therefore, if the offset isn't really constant (e.g. if a virtual2496//     function defined in a virtual base is overridden in a more derived2497//     virtual base and these bases have a reverse order in the complete2498//     object), the vf-table may require a this-adjustment thunk.2499//2500//  4. vftables do not contain new entries for overrides that merely require2501//     this-adjustment.  Together with #3, this keeps vf-tables smaller and2502//     eliminates the need for this-adjustment thunks in many cases, at the cost2503//     of often requiring redundant work to adjust the "this" pointer.2504//2505//  5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.2506//     Vtordisps are emitted into the class layout if a class has2507//      a) a user-defined ctor/dtor2508//     and2509//      b) a method overriding a method in a virtual base.2510//2511//  To get a better understanding of this code,2512//  you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp2513 2514class VFTableBuilder {2515public:2516  typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>2517    MethodVFTableLocationsTy;2518 2519  typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator>2520    method_locations_range;2521 2522private:2523  /// VTables - Global vtable information.2524  MicrosoftVTableContext &VTables;2525 2526  /// Context - The ASTContext which we will use for layout information.2527  ASTContext &Context;2528 2529  /// MostDerivedClass - The most derived class for which we're building this2530  /// vtable.2531  const CXXRecordDecl *MostDerivedClass;2532 2533  const ASTRecordLayout &MostDerivedClassLayout;2534 2535  const VPtrInfo &WhichVFPtr;2536 2537  /// FinalOverriders - The final overriders of the most derived class.2538  const FinalOverriders Overriders;2539 2540  /// Components - The components of the vftable being built.2541  SmallVector<VTableComponent, 64> Components;2542 2543  MethodVFTableLocationsTy MethodVFTableLocations;2544 2545  /// Does this class have an RTTI component?2546  bool HasRTTIComponent = false;2547 2548  /// MethodInfo - Contains information about a method in a vtable.2549  /// (Used for computing 'this' pointer adjustment thunks.2550  struct MethodInfo {2551    /// VBTableIndex - The nonzero index in the vbtable that2552    /// this method's base has, or zero.2553    const uint64_t VBTableIndex;2554 2555    /// VFTableIndex - The index in the vftable that this method has.2556    const uint64_t VFTableIndex;2557 2558    /// Shadowed - Indicates if this vftable slot is shadowed by2559    /// a slot for a covariant-return override. If so, it shouldn't be printed2560    /// or used for vcalls in the most derived class.2561    bool Shadowed;2562 2563    /// UsesExtraSlot - Indicates if this vftable slot was created because2564    /// any of the overridden slots required a return adjusting thunk.2565    bool UsesExtraSlot;2566 2567    MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex,2568               bool UsesExtraSlot = false)2569        : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),2570          Shadowed(false), UsesExtraSlot(UsesExtraSlot) {}2571 2572    MethodInfo()2573        : VBTableIndex(0), VFTableIndex(0), Shadowed(false),2574          UsesExtraSlot(false) {}2575  };2576 2577  typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;2578 2579  /// MethodInfoMap - The information for all methods in the vftable we're2580  /// currently building.2581  MethodInfoMapTy MethodInfoMap;2582 2583  typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;2584 2585  /// VTableThunks - The thunks by vftable index in the vftable currently being2586  /// built.2587  VTableThunksMapTy VTableThunks;2588 2589  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;2590  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;2591 2592  /// Thunks - A map that contains all the thunks needed for all methods in the2593  /// most derived class for which the vftable is currently being built.2594  ThunksMapTy Thunks;2595 2596  /// AddThunk - Add a thunk for the given method.2597  void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) {2598    SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD];2599 2600    // Check if we have this thunk already.2601    if (llvm::is_contained(ThunksVector, Thunk))2602      return;2603 2604    ThunksVector.push_back(Thunk);2605  }2606 2607  /// ComputeThisOffset - Returns the 'this' argument offset for the given2608  /// method, relative to the beginning of the MostDerivedClass.2609  CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider);2610 2611  void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,2612                                   CharUnits ThisOffset, ThisAdjustment &TA);2613 2614  /// AddMethod - Add a single virtual member function to the vftable2615  /// components vector.2616  void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {2617    if (!TI.isEmpty()) {2618      VTableThunks[Components.size()] = TI;2619      AddThunk(MD, TI);2620    }2621    if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {2622      assert(TI.Return.isEmpty() &&2623             "Destructor can't have return adjustment!");2624      Components.push_back(VTableComponent::MakeDeletingDtor(DD));2625    } else {2626      Components.push_back(VTableComponent::MakeFunction(MD));2627    }2628  }2629 2630  /// AddMethods - Add the methods of this base subobject and the relevant2631  /// subbases to the vftable we're currently laying out.2632  void AddMethods(BaseSubobject Base, unsigned BaseDepth,2633                  const CXXRecordDecl *LastVBase,2634                  BasesSetVectorTy &VisitedBases);2635 2636  void LayoutVFTable() {2637    // RTTI data goes before all other entries.2638    if (HasRTTIComponent)2639      Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));2640 2641    BasesSetVectorTy VisitedBases;2642    AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr,2643               VisitedBases);2644    // Note that it is possible for the vftable to contain only an RTTI2645    // pointer, if all virtual functions are constewval.2646    assert(!Components.empty() && "vftable can't be empty");2647 2648    assert(MethodVFTableLocations.empty());2649    for (const auto &I : MethodInfoMap) {2650      const CXXMethodDecl *MD = I.first;2651      const MethodInfo &MI = I.second;2652      assert(MD == MD->getCanonicalDecl());2653 2654      // Skip the methods that the MostDerivedClass didn't override2655      // and the entries shadowed by return adjusting thunks.2656      if (MD->getParent() != MostDerivedClass || MI.Shadowed)2657        continue;2658      MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),2659                                WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);2660      if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {2661        MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;2662      } else {2663        MethodVFTableLocations[MD] = Loc;2664      }2665    }2666  }2667 2668public:2669  VFTableBuilder(MicrosoftVTableContext &VTables,2670                 const CXXRecordDecl *MostDerivedClass, const VPtrInfo &Which)2671      : VTables(VTables),2672        Context(MostDerivedClass->getASTContext()),2673        MostDerivedClass(MostDerivedClass),2674        MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)),2675        WhichVFPtr(Which),2676        Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) {2677    // Provide the RTTI component if RTTIData is enabled. If the vftable would2678    // be available externally, we should not provide the RTTI componenent. It2679    // is currently impossible to get available externally vftables with either2680    // dllimport or extern template instantiations, but eventually we may add a2681    // flag to support additional devirtualization that needs this.2682    if (Context.getLangOpts().RTTIData)2683      HasRTTIComponent = true;2684 2685    LayoutVFTable();2686 2687    if (Context.getLangOpts().DumpVTableLayouts)2688      dumpLayout(llvm::outs());2689  }2690 2691  uint64_t getNumThunks() const { return Thunks.size(); }2692 2693  ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }2694 2695  ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }2696 2697  method_locations_range vtable_locations() const {2698    return method_locations_range(MethodVFTableLocations.begin(),2699                                  MethodVFTableLocations.end());2700  }2701 2702  ArrayRef<VTableComponent> vtable_components() const { return Components; }2703 2704  VTableThunksMapTy::const_iterator vtable_thunks_begin() const {2705    return VTableThunks.begin();2706  }2707 2708  VTableThunksMapTy::const_iterator vtable_thunks_end() const {2709    return VTableThunks.end();2710  }2711 2712  void dumpLayout(raw_ostream &);2713};2714 2715} // end namespace2716 2717// Let's study one class hierarchy as an example:2718//   struct A {2719//     virtual void f();2720//     int x;2721//   };2722//2723//   struct B : virtual A {2724//     virtual void f();2725//   };2726//2727// Record layouts:2728//   struct A:2729//   0 |   (A vftable pointer)2730//   4 |   int x2731//2732//   struct B:2733//   0 |   (B vbtable pointer)2734//   4 |   struct A (virtual base)2735//   4 |     (A vftable pointer)2736//   8 |     int x2737//2738// Let's assume we have a pointer to the A part of an object of dynamic type B:2739//   B b;2740//   A *a = (A*)&b;2741//   a->f();2742//2743// In this hierarchy, f() belongs to the vftable of A, so B::f() expects2744// "this" parameter to point at the A subobject, which is B+4.2745// In the B::f() prologue, it adjusts "this" back to B by subtracting 4,2746// performed as a *static* adjustment.2747//2748// Interesting thing happens when we alter the relative placement of A and B2749// subobjects in a class:2750//   struct C : virtual B { };2751//2752//   C c;2753//   A *a = (A*)&c;2754//   a->f();2755//2756// Respective record layout is:2757//   0 |   (C vbtable pointer)2758//   4 |   struct A (virtual base)2759//   4 |     (A vftable pointer)2760//   8 |     int x2761//  12 |   struct B (virtual base)2762//  12 |     (B vbtable pointer)2763//2764// The final overrider of f() in class C is still B::f(), so B+4 should be2765// passed as "this" to that code.  However, "a" points at B-8, so the respective2766// vftable entry should hold a thunk that adds 12 to the "this" argument before2767// performing a tail call to B::f().2768//2769// With this example in mind, we can now calculate the 'this' argument offset2770// for the given method, relative to the beginning of the MostDerivedClass.2771CharUnits2772VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {2773  BasesSetVectorTy Bases;2774 2775  {2776    // Find the set of least derived bases that define the given method.2777    OverriddenMethodsSetTy VisitedOverriddenMethods;2778    auto InitialOverriddenDefinitionCollector = [&](2779        const CXXMethodDecl *OverriddenMD) {2780      if (OverriddenMD->size_overridden_methods() == 0)2781        Bases.insert(OverriddenMD->getParent());2782      // Don't recurse on this method if we've already collected it.2783      return VisitedOverriddenMethods.insert(OverriddenMD).second;2784    };2785    visitAllOverriddenMethods(Overrider.Method,2786                              InitialOverriddenDefinitionCollector);2787  }2788 2789  // If there are no overrides then 'this' is located2790  // in the base that defines the method.2791  if (Bases.size() == 0)2792    return Overrider.Offset;2793 2794  CXXBasePaths Paths;2795  Overrider.Method->getParent()->lookupInBases(2796      [&Bases](const CXXBaseSpecifier *Specifier, CXXBasePath &) {2797        return Bases.count(Specifier->getType()->getAsCXXRecordDecl());2798      },2799      Paths);2800 2801  // This will hold the smallest this offset among overridees of MD.2802  // This implies that an offset of a non-virtual base will dominate an offset2803  // of a virtual base to potentially reduce the number of thunks required2804  // in the derived classes that inherit this method.2805  CharUnits Ret;2806  bool First = true;2807 2808  const ASTRecordLayout &OverriderRDLayout =2809      Context.getASTRecordLayout(Overrider.Method->getParent());2810  for (const CXXBasePath &Path : Paths) {2811    CharUnits ThisOffset = Overrider.Offset;2812    CharUnits LastVBaseOffset;2813 2814    // For each path from the overrider to the parents of the overridden2815    // methods, traverse the path, calculating the this offset in the most2816    // derived class.2817    for (const CXXBasePathElement &Element : Path) {2818      QualType CurTy = Element.Base->getType();2819      const CXXRecordDecl *PrevRD = Element.Class,2820                          *CurRD = CurTy->getAsCXXRecordDecl();2821      const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);2822 2823      if (Element.Base->isVirtual()) {2824        // The interesting things begin when you have virtual inheritance.2825        // The final overrider will use a static adjustment equal to the offset2826        // of the vbase in the final overrider class.2827        // For example, if the final overrider is in a vbase B of the most2828        // derived class and it overrides a method of the B's own vbase A,2829        // it uses A* as "this".  In its prologue, it can cast A* to B* with2830        // a static offset.  This offset is used regardless of the actual2831        // offset of A from B in the most derived class, requiring an2832        // this-adjusting thunk in the vftable if A and B are laid out2833        // differently in the most derived class.2834        LastVBaseOffset = ThisOffset =2835            Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD);2836      } else {2837        ThisOffset += Layout.getBaseClassOffset(CurRD);2838      }2839    }2840 2841    if (isa<CXXDestructorDecl>(Overrider.Method)) {2842      if (LastVBaseOffset.isZero()) {2843        // If a "Base" class has at least one non-virtual base with a virtual2844        // destructor, the "Base" virtual destructor will take the address2845        // of the "Base" subobject as the "this" argument.2846        ThisOffset = Overrider.Offset;2847      } else {2848        // A virtual destructor of a virtual base takes the address of the2849        // virtual base subobject as the "this" argument.2850        ThisOffset = LastVBaseOffset;2851      }2852    }2853 2854    if (Ret > ThisOffset || First) {2855      First = false;2856      Ret = ThisOffset;2857    }2858  }2859 2860  assert(!First && "Method not found in the given subobject?");2861  return Ret;2862}2863 2864// Things are getting even more complex when the "this" adjustment has to2865// use a dynamic offset instead of a static one, or even two dynamic offsets.2866// This is sometimes required when a virtual call happens in the middle of2867// a non-most-derived class construction or destruction.2868//2869// Let's take a look at the following example:2870//   struct A {2871//     virtual void f();2872//   };2873//2874//   void foo(A *a) { a->f(); }  // Knows nothing about siblings of A.2875//2876//   struct B : virtual A {2877//     virtual void f();2878//     B() {2879//       foo(this);2880//     }2881//   };2882//2883//   struct C : virtual B {2884//     virtual void f();2885//   };2886//2887// Record layouts for these classes are:2888//   struct A2889//   0 |   (A vftable pointer)2890//2891//   struct B2892//   0 |   (B vbtable pointer)2893//   4 |   (vtordisp for vbase A)2894//   8 |   struct A (virtual base)2895//   8 |     (A vftable pointer)2896//2897//   struct C2898//   0 |   (C vbtable pointer)2899//   4 |   (vtordisp for vbase A)2900//   8 |   struct A (virtual base)  // A precedes B!2901//   8 |     (A vftable pointer)2902//  12 |   struct B (virtual base)2903//  12 |     (B vbtable pointer)2904//2905// When one creates an object of type C, the C constructor:2906// - initializes all the vbptrs, then2907// - calls the A subobject constructor2908//   (initializes A's vfptr with an address of A vftable), then2909// - calls the B subobject constructor2910//   (initializes A's vfptr with an address of B vftable and vtordisp for A),2911//   that in turn calls foo(), then2912// - initializes A's vfptr with an address of C vftable and zeroes out the2913//   vtordisp2914//   FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable2915//   without vtordisp thunks?2916//   FIXME: how are vtordisp handled in the presence of nooverride/final?2917//2918// When foo() is called, an object with a layout of class C has a vftable2919// referencing B::f() that assumes a B layout, so the "this" adjustments are2920// incorrect, unless an extra adjustment is done.  This adjustment is called2921// "vtordisp adjustment".  Vtordisp basically holds the difference between the2922// actual location of a vbase in the layout class and the location assumed by2923// the vftable of the class being constructed/destructed.  Vtordisp is only2924// needed if "this" escapes a2925// structor (or we can't prove otherwise).2926// [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an2927// estimation of a dynamic adjustment]2928//2929// foo() gets a pointer to the A vbase and doesn't know anything about B or C,2930// so it just passes that pointer as "this" in a virtual call.2931// If there was no vtordisp, that would just dispatch to B::f().2932// However, B::f() assumes B+8 is passed as "this",2933// yet the pointer foo() passes along is B-4 (i.e. C+8).2934// An extra adjustment is needed, so we emit a thunk into the B vftable.2935// This vtordisp thunk subtracts the value of vtordisp2936// from the "this" argument (-12) before making a tailcall to B::f().2937//2938// Let's consider an even more complex example:2939//   struct D : virtual B, virtual C {2940//     D() {2941//       foo(this);2942//     }2943//   };2944//2945//   struct D2946//   0 |   (D vbtable pointer)2947//   4 |   (vtordisp for vbase A)2948//   8 |   struct A (virtual base)  // A precedes both B and C!2949//   8 |     (A vftable pointer)2950//  12 |   struct B (virtual base)  // B precedes C!2951//  12 |     (B vbtable pointer)2952//  16 |   struct C (virtual base)2953//  16 |     (C vbtable pointer)2954//2955// When D::D() calls foo(), we find ourselves in a thunk that should tailcall2956// to C::f(), which assumes C+8 as its "this" parameter.  This time, foo()2957// passes along A, which is C-8.  The A vtordisp holds2958//   "D.vbptr[index_of_A] - offset_of_A_in_D"2959// and we statically know offset_of_A_in_D, so can get a pointer to D.2960// When we know it, we can make an extra vbtable lookup to locate the C vbase2961// and one extra static adjustment to calculate the expected value of C+8.2962void VFTableBuilder::CalculateVtordispAdjustment(2963    FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,2964    ThisAdjustment &TA) {2965  const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap =2966      MostDerivedClassLayout.getVBaseOffsetsMap();2967  const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry =2968      VBaseMap.find(WhichVFPtr.getVBaseWithVPtr());2969  assert(VBaseMapEntry != VBaseMap.end());2970 2971  // If there's no vtordisp or the final overrider is defined in the same vbase2972  // as the initial declaration, we don't need any vtordisp adjustment.2973  if (!VBaseMapEntry->second.hasVtorDisp() ||2974      Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())2975    return;2976 2977  // OK, now we know we need to use a vtordisp thunk.2978  // The implicit vtordisp field is located right before the vbase.2979  CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset;2980  TA.Virtual.Microsoft.VtordispOffset =2981      (OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4;2982 2983  // A simple vtordisp thunk will suffice if the final overrider is defined2984  // in either the most derived class or its non-virtual base.2985  if (Overrider.Method->getParent() == MostDerivedClass ||2986      !Overrider.VirtualBase)2987    return;2988 2989  // Otherwise, we need to do use the dynamic offset of the final overrider2990  // in order to get "this" adjustment right.2991  TA.Virtual.Microsoft.VBPtrOffset =2992      (OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset -2993       MostDerivedClassLayout.getVBPtrOffset()).getQuantity();2994  TA.Virtual.Microsoft.VBOffsetOffset =2995      Context.getTypeSizeInChars(Context.IntTy).getQuantity() *2996      VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase);2997 2998  TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity();2999}3000 3001static void GroupNewVirtualOverloads(3002    const CXXRecordDecl *RD,3003    SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) {3004  // Put the virtual methods into VirtualMethods in the proper order:3005  // 1) Group overloads by declaration name. New groups are added to the3006  //    vftable in the order of their first declarations in this class3007  //    (including overrides, non-virtual methods and any other named decl that3008  //    might be nested within the class).3009  // 2) In each group, new overloads appear in the reverse order of declaration.3010  typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;3011  SmallVector<MethodGroup, 10> Groups;3012  typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;3013  VisitedGroupIndicesTy VisitedGroupIndices;3014  for (const auto *D : RD->decls()) {3015    const auto *ND = dyn_cast<NamedDecl>(D);3016    if (!ND)3017      continue;3018    VisitedGroupIndicesTy::iterator J;3019    bool Inserted;3020    std::tie(J, Inserted) = VisitedGroupIndices.insert(3021        std::make_pair(ND->getDeclName(), Groups.size()));3022    if (Inserted)3023      Groups.push_back(MethodGroup());3024    if (const auto *MD = dyn_cast<CXXMethodDecl>(ND))3025      if (MicrosoftVTableContext::hasVtableSlot(MD))3026        Groups[J->second].push_back(MD->getCanonicalDecl());3027  }3028 3029  for (const MethodGroup &Group : Groups)3030    VirtualMethods.append(Group.rbegin(), Group.rend());3031}3032 3033static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {3034  for (const auto &B : RD->bases()) {3035    if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base)3036      return true;3037  }3038  return false;3039}3040 3041void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,3042                                const CXXRecordDecl *LastVBase,3043                                BasesSetVectorTy &VisitedBases) {3044  const CXXRecordDecl *RD = Base.getBase();3045  if (!RD->isPolymorphic())3046    return;3047 3048  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3049 3050  // See if this class expands a vftable of the base we look at, which is either3051  // the one defined by the vfptr base path or the primary base of the current3052  // class.3053  const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;3054  CharUnits NextBaseOffset;3055  if (BaseDepth < WhichVFPtr.PathToIntroducingObject.size()) {3056    NextBase = WhichVFPtr.PathToIntroducingObject[BaseDepth];3057    if (isDirectVBase(NextBase, RD)) {3058      NextLastVBase = NextBase;3059      NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase);3060    } else {3061      NextBaseOffset =3062          Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase);3063    }3064  } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {3065    assert(!Layout.isPrimaryBaseVirtual() &&3066           "No primary virtual bases in this ABI");3067    NextBase = PrimaryBase;3068    NextBaseOffset = Base.getBaseOffset();3069  }3070 3071  if (NextBase) {3072    AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1,3073               NextLastVBase, VisitedBases);3074    if (!VisitedBases.insert(NextBase))3075      llvm_unreachable("Found a duplicate primary base!");3076  }3077 3078  SmallVector<const CXXMethodDecl*, 10> VirtualMethods;3079  // Put virtual methods in the proper order.3080  GroupNewVirtualOverloads(RD, VirtualMethods);3081 3082  // Now go through all virtual member functions and add them to the current3083  // vftable. This is done by3084  //  - replacing overridden methods in their existing slots, as long as they3085  //    don't require return adjustment; calculating This adjustment if needed.3086  //  - adding new slots for methods of the current base not present in any3087  //    sub-bases;3088  //  - adding new slots for methods that require Return adjustment.3089  // We keep track of the methods visited in the sub-bases in MethodInfoMap.3090  for (const CXXMethodDecl *MD : VirtualMethods) {3091    FinalOverriders::OverriderInfo FinalOverrider =3092        Overriders.getOverrider(MD, Base.getBaseOffset());3093    const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method;3094    const CXXMethodDecl *OverriddenMD =3095        FindNearestOverriddenMethod(MD, VisitedBases);3096 3097    ThisAdjustment ThisAdjustmentOffset;3098    bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false;3099    CharUnits ThisOffset = ComputeThisOffset(FinalOverrider);3100    ThisAdjustmentOffset.NonVirtual =3101        (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();3102    if ((OverriddenMD || FinalOverriderMD != MD) &&3103        WhichVFPtr.getVBaseWithVPtr())3104      CalculateVtordispAdjustment(FinalOverrider, ThisOffset,3105                                  ThisAdjustmentOffset);3106 3107    unsigned VBIndex =3108        LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0;3109 3110    if (OverriddenMD) {3111      // If MD overrides anything in this vftable, we need to update the3112      // entries.3113      MethodInfoMapTy::iterator OverriddenMDIterator =3114          MethodInfoMap.find(OverriddenMD);3115 3116      // If the overridden method went to a different vftable, skip it.3117      if (OverriddenMDIterator == MethodInfoMap.end())3118        continue;3119 3120      MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;3121 3122      VBIndex = OverriddenMethodInfo.VBTableIndex;3123 3124      // Let's check if the overrider requires any return adjustments.3125      // We must create a new slot if the MD's return type is not trivially3126      // convertible to the OverriddenMD's one.3127      // Once a chain of method overrides adds a return adjusting vftable slot,3128      // all subsequent overrides will also use an extra method slot.3129      ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset(3130                                  Context, MD, OverriddenMD).isEmpty() ||3131                             OverriddenMethodInfo.UsesExtraSlot;3132 3133      if (!ReturnAdjustingThunk) {3134        // No return adjustment needed - just replace the overridden method info3135        // with the current info.3136        MethodInfo MI(VBIndex, OverriddenMethodInfo.VFTableIndex);3137        MethodInfoMap.erase(OverriddenMDIterator);3138 3139        assert(!MethodInfoMap.count(MD) &&3140               "Should not have method info for this method yet!");3141        MethodInfoMap.insert(std::make_pair(MD, MI));3142        continue;3143      }3144 3145      // In case we need a return adjustment, we'll add a new slot for3146      // the overrider. Mark the overridden method as shadowed by the new slot.3147      OverriddenMethodInfo.Shadowed = true;3148 3149      // Force a special name mangling for a return-adjusting thunk3150      // unless the method is the final overrider without this adjustment.3151      ForceReturnAdjustmentMangling =3152          !(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty());3153    } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||3154               MD->size_overridden_methods()) {3155      // Skip methods that don't belong to the vftable of the current class,3156      // e.g. each method that wasn't seen in any of the visited sub-bases3157      // but overrides multiple methods of other sub-bases.3158      continue;3159    }3160 3161    // If we got here, MD is a method not seen in any of the sub-bases or3162    // it requires return adjustment. Insert the method info for this method.3163    MethodInfo MI(VBIndex,3164                  HasRTTIComponent ? Components.size() - 1 : Components.size(),3165                  ReturnAdjustingThunk);3166 3167    assert(!MethodInfoMap.count(MD) &&3168           "Should not have method info for this method yet!");3169    MethodInfoMap.insert(std::make_pair(MD, MI));3170 3171    // Check if this overrider needs a return adjustment.3172    // We don't want to do this for pure virtual member functions.3173    BaseOffset ReturnAdjustmentOffset;3174    ReturnAdjustment ReturnAdjustment;3175    if (!FinalOverriderMD->isPureVirtual()) {3176      ReturnAdjustmentOffset =3177          ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD);3178    }3179    if (!ReturnAdjustmentOffset.isEmpty()) {3180      ForceReturnAdjustmentMangling = true;3181      ReturnAdjustment.NonVirtual =3182          ReturnAdjustmentOffset.NonVirtualOffset.getQuantity();3183      if (ReturnAdjustmentOffset.VirtualBase) {3184        const ASTRecordLayout &DerivedLayout =3185            Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass);3186        ReturnAdjustment.Virtual.Microsoft.VBPtrOffset =3187            DerivedLayout.getVBPtrOffset().getQuantity();3188        ReturnAdjustment.Virtual.Microsoft.VBIndex =3189            VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass,3190                                    ReturnAdjustmentOffset.VirtualBase);3191      }3192    }3193    auto ThisType = (OverriddenMD ? OverriddenMD : MD)->getThisType().getTypePtr();3194    AddMethod(FinalOverriderMD,3195              ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment, ThisType,3196                        ForceReturnAdjustmentMangling ? MD : nullptr));3197  }3198}3199 3200static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {3201  for (const CXXRecordDecl *Elem : llvm::reverse(Path)) {3202    Out << "'";3203    Elem->printQualifiedName(Out);3204    Out << "' in ";3205  }3206}3207 3208static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,3209                                         bool ContinueFirstLine) {3210  const ReturnAdjustment &R = TI.Return;3211  bool Multiline = false;3212  const char *LinePrefix = "\n       ";3213  if (!R.isEmpty() || TI.Method) {3214    if (!ContinueFirstLine)3215      Out << LinePrefix;3216    Out << "[return adjustment (to type '"3217        << TI.Method->getReturnType().getCanonicalType() << "'): ";3218    if (R.Virtual.Microsoft.VBPtrOffset)3219      Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";3220    if (R.Virtual.Microsoft.VBIndex)3221      Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";3222    Out << R.NonVirtual << " non-virtual]";3223    Multiline = true;3224  }3225 3226  const ThisAdjustment &T = TI.This;3227  if (!T.isEmpty()) {3228    if (Multiline || !ContinueFirstLine)3229      Out << LinePrefix;3230    Out << "[this adjustment: ";3231    if (!TI.This.Virtual.isEmpty()) {3232      assert(T.Virtual.Microsoft.VtordispOffset < 0);3233      Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";3234      if (T.Virtual.Microsoft.VBPtrOffset) {3235        Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset3236            << " to the left,";3237        assert(T.Virtual.Microsoft.VBOffsetOffset > 0);3238        Out << LinePrefix << " vboffset at "3239            << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";3240      }3241    }3242    Out << T.NonVirtual << " non-virtual]";3243  }3244}3245 3246void VFTableBuilder::dumpLayout(raw_ostream &Out) {3247  Out << "VFTable for ";3248  PrintBasePath(WhichVFPtr.PathToIntroducingObject, Out);3249  Out << "'";3250  MostDerivedClass->printQualifiedName(Out);3251  Out << "' (" << Components.size()3252      << (Components.size() == 1 ? " entry" : " entries") << ").\n";3253 3254  for (unsigned I = 0, E = Components.size(); I != E; ++I) {3255    Out << llvm::format("%4d | ", I);3256 3257    const VTableComponent &Component = Components[I];3258 3259    // Dump the component.3260    switch (Component.getKind()) {3261    case VTableComponent::CK_RTTI:3262      Component.getRTTIDecl()->printQualifiedName(Out);3263      Out << " RTTI";3264      break;3265 3266    case VTableComponent::CK_FunctionPointer: {3267      const CXXMethodDecl *MD = Component.getFunctionDecl();3268 3269      // FIXME: Figure out how to print the real thunk type, since they can3270      // differ in the return type.3271      std::string Str = PredefinedExpr::ComputeName(3272          PredefinedIdentKind::PrettyFunctionNoVirtual, MD);3273      Out << Str;3274      if (MD->isPureVirtual())3275        Out << " [pure]";3276 3277      if (MD->isDeleted())3278        Out << " [deleted]";3279 3280      ThunkInfo Thunk = VTableThunks.lookup(I);3281      if (!Thunk.isEmpty())3282        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);3283 3284      break;3285    }3286 3287    case VTableComponent::CK_DeletingDtorPointer: {3288      const CXXDestructorDecl *DD = Component.getDestructorDecl();3289 3290      DD->printQualifiedName(Out);3291      Out << "() [scalar deleting]";3292 3293      if (DD->isPureVirtual())3294        Out << " [pure]";3295 3296      ThunkInfo Thunk = VTableThunks.lookup(I);3297      if (!Thunk.isEmpty()) {3298        assert(Thunk.Return.isEmpty() &&3299               "No return adjustment needed for destructors!");3300        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);3301      }3302 3303      break;3304    }3305 3306    default:3307      DiagnosticsEngine &Diags = Context.getDiagnostics();3308      unsigned DiagID = Diags.getCustomDiagID(3309          DiagnosticsEngine::Error,3310          "Unexpected vftable component type %0 for component number %1");3311      Diags.Report(MostDerivedClass->getLocation(), DiagID)3312          << I << Component.getKind();3313    }3314 3315    Out << '\n';3316  }3317 3318  Out << '\n';3319 3320  if (!Thunks.empty()) {3321    // We store the method names in a map to get a stable order.3322    std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;3323 3324    for (const auto &I : Thunks) {3325      const CXXMethodDecl *MD = I.first;3326      std::string MethodName = PredefinedExpr::ComputeName(3327          PredefinedIdentKind::PrettyFunctionNoVirtual, MD);3328 3329      MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));3330    }3331 3332    for (const auto &MethodNameAndDecl : MethodNamesAndDecls) {3333      const std::string &MethodName = MethodNameAndDecl.first;3334      const CXXMethodDecl *MD = MethodNameAndDecl.second;3335 3336      ThunkInfoVectorTy ThunksVector = Thunks[MD];3337      llvm::stable_sort(ThunksVector, [](const ThunkInfo &LHS,3338                                         const ThunkInfo &RHS) {3339        // Keep different thunks with the same adjustments in the order they3340        // were put into the vector.3341        return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);3342      });3343 3344      Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();3345      Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";3346 3347      for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {3348        const ThunkInfo &Thunk = ThunksVector[I];3349 3350        Out << llvm::format("%4d | ", I);3351        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true);3352        Out << '\n';3353      }3354 3355      Out << '\n';3356    }3357  }3358 3359  Out.flush();3360}3361 3362static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,3363                          ArrayRef<const CXXRecordDecl *> B) {3364  for (const CXXRecordDecl *Decl : B) {3365    if (A.count(Decl))3366      return true;3367  }3368  return false;3369}3370 3371static bool rebucketPaths(VPtrInfoVector &Paths);3372 3373/// Produces MSVC-compatible vbtable data.  The symbols produced by this3374/// algorithm match those produced by MSVC 2012 and newer, which is different3375/// from MSVC 2010.3376///3377/// MSVC 2012 appears to minimize the vbtable names using the following3378/// algorithm.  First, walk the class hierarchy in the usual order, depth first,3379/// left to right, to find all of the subobjects which contain a vbptr field.3380/// Visiting each class node yields a list of inheritance paths to vbptrs.  Each3381/// record with a vbptr creates an initially empty path.3382///3383/// To combine paths from child nodes, the paths are compared to check for3384/// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of3385/// components in the same order.  Each group of ambiguous paths is extended by3386/// appending the class of the base from which it came.  If the current class3387/// node produced an ambiguous path, its path is extended with the current class.3388/// After extending paths, MSVC again checks for ambiguity, and extends any3389/// ambiguous path which wasn't already extended.  Because each node yields an3390/// unambiguous set of paths, MSVC doesn't need to extend any path more than once3391/// to produce an unambiguous set of paths.3392///3393/// TODO: Presumably vftables use the same algorithm.3394void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,3395                                                const CXXRecordDecl *RD,3396                                                VPtrInfoVector &Paths) {3397  assert(Paths.empty());3398  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3399 3400  // Base case: this subobject has its own vptr.3401  if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr())3402    Paths.push_back(std::make_unique<VPtrInfo>(RD));3403 3404  // Recursive case: get all the vbtables from our bases and remove anything3405  // that shares a virtual base.3406  llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;3407  for (const auto &B : RD->bases()) {3408    const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();3409    if (B.isVirtual() && VBasesSeen.count(Base))3410      continue;3411 3412    if (!Base->isDynamicClass())3413      continue;3414 3415    const VPtrInfoVector &BasePaths =3416        ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base);3417 3418    for (const std::unique_ptr<VPtrInfo> &BaseInfo : BasePaths) {3419      // Don't include the path if it goes through a virtual base that we've3420      // already included.3421      if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases))3422        continue;3423 3424      // Copy the path and adjust it as necessary.3425      auto P = std::make_unique<VPtrInfo>(*BaseInfo);3426 3427      // We mangle Base into the path if the path would've been ambiguous and it3428      // wasn't already extended with Base.3429      if (P->MangledPath.empty() || P->MangledPath.back() != Base)3430        P->NextBaseToMangle = Base;3431 3432      // Keep track of which vtable the derived class is going to extend with3433      // new methods or bases.  We append to either the vftable of our primary3434      // base, or the first non-virtual base that has a vbtable.3435      if (P->ObjectWithVPtr == Base &&3436          Base == (ForVBTables ? Layout.getBaseSharingVBPtr()3437                               : Layout.getPrimaryBase()))3438        P->ObjectWithVPtr = RD;3439 3440      // Keep track of the full adjustment from the MDC to this vtable.  The3441      // adjustment is captured by an optional vbase and a non-virtual offset.3442      if (B.isVirtual())3443        P->ContainingVBases.push_back(Base);3444      else if (P->ContainingVBases.empty())3445        P->NonVirtualOffset += Layout.getBaseClassOffset(Base);3446 3447      // Update the full offset in the MDC.3448      P->FullOffsetInMDC = P->NonVirtualOffset;3449      if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())3450        P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB);3451 3452      Paths.push_back(std::move(P));3453    }3454 3455    if (B.isVirtual())3456      VBasesSeen.insert(Base);3457 3458    // After visiting any direct base, we've transitively visited all of its3459    // morally virtual bases.3460    for (const auto &VB : Base->vbases())3461      VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl());3462  }3463 3464  // Sort the paths into buckets, and if any of them are ambiguous, extend all3465  // paths in ambiguous buckets.3466  bool Changed = true;3467  while (Changed)3468    Changed = rebucketPaths(Paths);3469}3470 3471static bool extendPath(VPtrInfo &P) {3472  if (P.NextBaseToMangle) {3473    P.MangledPath.push_back(P.NextBaseToMangle);3474    P.NextBaseToMangle = nullptr;// Prevent the path from being extended twice.3475    return true;3476  }3477  return false;3478}3479 3480static bool rebucketPaths(VPtrInfoVector &Paths) {3481  // What we're essentially doing here is bucketing together ambiguous paths.3482  // Any bucket with more than one path in it gets extended by NextBase, which3483  // is usually the direct base of the inherited the vbptr.  This code uses a3484  // sorted vector to implement a multiset to form the buckets.  Note that the3485  // ordering is based on pointers, but it doesn't change our output order.  The3486  // current algorithm is designed to match MSVC 2012's names.3487  llvm::SmallVector<std::reference_wrapper<VPtrInfo>, 2> PathsSorted(3488      llvm::make_pointee_range(Paths));3489  llvm::sort(PathsSorted, [](const VPtrInfo &LHS, const VPtrInfo &RHS) {3490    return LHS.MangledPath < RHS.MangledPath;3491  });3492  bool Changed = false;3493  for (size_t I = 0, E = PathsSorted.size(); I != E;) {3494    // Scan forward to find the end of the bucket.3495    size_t BucketStart = I;3496    do {3497      ++I;3498    } while (I != E &&3499             PathsSorted[BucketStart].get().MangledPath ==3500                 PathsSorted[I].get().MangledPath);3501 3502    // If this bucket has multiple paths, extend them all.3503    if (I - BucketStart > 1) {3504      for (size_t II = BucketStart; II != I; ++II)3505        Changed |= extendPath(PathsSorted[II]);3506      assert(Changed && "no paths were extended to fix ambiguity");3507    }3508  }3509  return Changed;3510}3511 3512MicrosoftVTableContext::~MicrosoftVTableContext() {}3513 3514namespace {3515typedef llvm::SetVector<BaseSubobject, std::vector<BaseSubobject>,3516                        llvm::DenseSet<BaseSubobject>> FullPathTy;3517}3518 3519// This recursive function finds all paths from a subobject centered at3520// (RD, Offset) to the subobject located at IntroducingObject.3521static void findPathsToSubobject(ASTContext &Context,3522                                 const ASTRecordLayout &MostDerivedLayout,3523                                 const CXXRecordDecl *RD, CharUnits Offset,3524                                 BaseSubobject IntroducingObject,3525                                 FullPathTy &FullPath,3526                                 std::list<FullPathTy> &Paths) {3527  if (BaseSubobject(RD, Offset) == IntroducingObject) {3528    Paths.push_back(FullPath);3529    return;3530  }3531 3532  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3533 3534  for (const CXXBaseSpecifier &BS : RD->bases()) {3535    const CXXRecordDecl *Base = BS.getType()->getAsCXXRecordDecl();3536    CharUnits NewOffset = BS.isVirtual()3537                              ? MostDerivedLayout.getVBaseClassOffset(Base)3538                              : Offset + Layout.getBaseClassOffset(Base);3539    FullPath.insert(BaseSubobject(Base, NewOffset));3540    findPathsToSubobject(Context, MostDerivedLayout, Base, NewOffset,3541                         IntroducingObject, FullPath, Paths);3542    FullPath.pop_back();3543  }3544}3545 3546// Return the paths which are not subsets of other paths.3547static void removeRedundantPaths(std::list<FullPathTy> &FullPaths) {3548  FullPaths.remove_if([&](const FullPathTy &SpecificPath) {3549    for (const FullPathTy &OtherPath : FullPaths) {3550      if (&SpecificPath == &OtherPath)3551        continue;3552      if (llvm::all_of(SpecificPath, [&](const BaseSubobject &BSO) {3553            return OtherPath.contains(BSO);3554          })) {3555        return true;3556      }3557    }3558    return false;3559  });3560}3561 3562static CharUnits getOffsetOfFullPath(ASTContext &Context,3563                                     const CXXRecordDecl *RD,3564                                     const FullPathTy &FullPath) {3565  const ASTRecordLayout &MostDerivedLayout =3566      Context.getASTRecordLayout(RD);3567  CharUnits Offset = CharUnits::fromQuantity(-1);3568  for (const BaseSubobject &BSO : FullPath) {3569    const CXXRecordDecl *Base = BSO.getBase();3570    // The first entry in the path is always the most derived record, skip it.3571    if (Base == RD) {3572      assert(Offset.getQuantity() == -1);3573      Offset = CharUnits::Zero();3574      continue;3575    }3576    assert(Offset.getQuantity() != -1);3577    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3578    // While we know which base has to be traversed, we don't know if that base3579    // was a virtual base.3580    const CXXBaseSpecifier *BaseBS = std::find_if(3581        RD->bases_begin(), RD->bases_end(), [&](const CXXBaseSpecifier &BS) {3582          return BS.getType()->getAsCXXRecordDecl() == Base;3583        });3584    Offset = BaseBS->isVirtual() ? MostDerivedLayout.getVBaseClassOffset(Base)3585                                 : Offset + Layout.getBaseClassOffset(Base);3586    RD = Base;3587  }3588  return Offset;3589}3590 3591// We want to select the path which introduces the most covariant overrides.  If3592// two paths introduce overrides which the other path doesn't contain, issue a3593// diagnostic.3594static const FullPathTy *selectBestPath(ASTContext &Context,3595                                        const CXXRecordDecl *RD,3596                                        const VPtrInfo &Info,3597                                        std::list<FullPathTy> &FullPaths) {3598  // Handle some easy cases first.3599  if (FullPaths.empty())3600    return nullptr;3601  if (FullPaths.size() == 1)3602    return &FullPaths.front();3603 3604  const FullPathTy *BestPath = nullptr;3605  typedef std::set<const CXXMethodDecl *> OverriderSetTy;3606  OverriderSetTy LastOverrides;3607  for (const FullPathTy &SpecificPath : FullPaths) {3608    assert(!SpecificPath.empty());3609    OverriderSetTy CurrentOverrides;3610    const CXXRecordDecl *TopLevelRD = SpecificPath.begin()->getBase();3611    // Find the distance from the start of the path to the subobject with the3612    // VPtr.3613    CharUnits BaseOffset =3614        getOffsetOfFullPath(Context, TopLevelRD, SpecificPath);3615    FinalOverriders Overriders(TopLevelRD, CharUnits::Zero(), TopLevelRD);3616    for (const CXXMethodDecl *MD : Info.IntroducingObject->methods()) {3617      if (!MicrosoftVTableContext::hasVtableSlot(MD))3618        continue;3619      FinalOverriders::OverriderInfo OI =3620          Overriders.getOverrider(MD->getCanonicalDecl(), BaseOffset);3621      const CXXMethodDecl *OverridingMethod = OI.Method;3622      // Only overriders which have a return adjustment introduce problematic3623      // thunks.3624      if (ComputeReturnAdjustmentBaseOffset(Context, OverridingMethod, MD)3625              .isEmpty())3626        continue;3627      // It's possible that the overrider isn't in this path.  If so, skip it3628      // because this path didn't introduce it.3629      const CXXRecordDecl *OverridingParent = OverridingMethod->getParent();3630      if (llvm::none_of(SpecificPath, [&](const BaseSubobject &BSO) {3631            return BSO.getBase() == OverridingParent;3632          }))3633        continue;3634      CurrentOverrides.insert(OverridingMethod);3635    }3636    OverriderSetTy NewOverrides =3637        llvm::set_difference(CurrentOverrides, LastOverrides);3638    if (NewOverrides.empty())3639      continue;3640    OverriderSetTy MissingOverrides =3641        llvm::set_difference(LastOverrides, CurrentOverrides);3642    if (MissingOverrides.empty()) {3643      // This path is a strict improvement over the last path, let's use it.3644      BestPath = &SpecificPath;3645      std::swap(CurrentOverrides, LastOverrides);3646    } else {3647      // This path introduces an overrider with a conflicting covariant thunk.3648      DiagnosticsEngine &Diags = Context.getDiagnostics();3649      const CXXMethodDecl *CovariantMD = *NewOverrides.begin();3650      const CXXMethodDecl *ConflictMD = *MissingOverrides.begin();3651      Diags.Report(RD->getLocation(), diag::err_vftable_ambiguous_component)3652          << RD;3653      Diags.Report(CovariantMD->getLocation(), diag::note_covariant_thunk)3654          << CovariantMD;3655      Diags.Report(ConflictMD->getLocation(), diag::note_covariant_thunk)3656          << ConflictMD;3657    }3658  }3659  // Go with the path that introduced the most covariant overrides.  If there is3660  // no such path, pick the first path.3661  return BestPath ? BestPath : &FullPaths.front();3662}3663 3664static void computeFullPathsForVFTables(ASTContext &Context,3665                                        const CXXRecordDecl *RD,3666                                        VPtrInfoVector &Paths) {3667  const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD);3668  FullPathTy FullPath;3669  std::list<FullPathTy> FullPaths;3670  for (const std::unique_ptr<VPtrInfo>& Info : Paths) {3671    findPathsToSubobject(3672        Context, MostDerivedLayout, RD, CharUnits::Zero(),3673        BaseSubobject(Info->IntroducingObject, Info->FullOffsetInMDC), FullPath,3674        FullPaths);3675    FullPath.clear();3676    removeRedundantPaths(FullPaths);3677    Info->PathToIntroducingObject.clear();3678    if (const FullPathTy *BestPath =3679            selectBestPath(Context, RD, *Info, FullPaths))3680      for (const BaseSubobject &BSO : *BestPath)3681        Info->PathToIntroducingObject.push_back(BSO.getBase());3682    FullPaths.clear();3683  }3684}3685 3686static bool vfptrIsEarlierInMDC(const ASTRecordLayout &Layout,3687                                const MethodVFTableLocation &LHS,3688                                const MethodVFTableLocation &RHS) {3689  CharUnits L = LHS.VFPtrOffset;3690  CharUnits R = RHS.VFPtrOffset;3691  if (LHS.VBase)3692    L += Layout.getVBaseClassOffset(LHS.VBase);3693  if (RHS.VBase)3694    R += Layout.getVBaseClassOffset(RHS.VBase);3695  return L < R;3696}3697 3698void MicrosoftVTableContext::computeVTableRelatedInformation(3699    const CXXRecordDecl *RD) {3700  assert(RD->isDynamicClass());3701 3702  // Check if we've computed this information before.3703  if (VFPtrLocations.count(RD))3704    return;3705 3706  const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;3707 3708  {3709    auto VFPtrs = std::make_unique<VPtrInfoVector>();3710    computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs);3711    computeFullPathsForVFTables(Context, RD, *VFPtrs);3712    VFPtrLocations[RD] = std::move(VFPtrs);3713  }3714 3715  MethodVFTableLocationsTy NewMethodLocations;3716  for (const std::unique_ptr<VPtrInfo> &VFPtr : *VFPtrLocations[RD]) {3717    VFTableBuilder Builder(*this, RD, *VFPtr);3718 3719    VFTableIdTy id(RD, VFPtr->FullOffsetInMDC);3720    assert(VFTableLayouts.count(id) == 0);3721    SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(3722        Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());3723    VFTableLayouts[id] = std::make_unique<VTableLayout>(3724        ArrayRef<size_t>{0}, Builder.vtable_components(), VTableThunks,3725        EmptyAddressPointsMap);3726    Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());3727 3728    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3729    for (const auto &Loc : Builder.vtable_locations()) {3730      auto Insert = NewMethodLocations.insert(Loc);3731      if (!Insert.second) {3732        const MethodVFTableLocation &NewLoc = Loc.second;3733        MethodVFTableLocation &OldLoc = Insert.first->second;3734        if (vfptrIsEarlierInMDC(Layout, NewLoc, OldLoc))3735          OldLoc = NewLoc;3736      }3737    }3738  }3739 3740  MethodVFTableLocations.insert_range(NewMethodLocations);3741  if (Context.getLangOpts().DumpVTableLayouts)3742    dumpMethodLocations(RD, NewMethodLocations, llvm::outs());3743}3744 3745void MicrosoftVTableContext::dumpMethodLocations(3746    const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,3747    raw_ostream &Out) {3748  // Compute the vtable indices for all the member functions.3749  // Store them in a map keyed by the location so we'll get a sorted table.3750  std::map<MethodVFTableLocation, std::string> IndicesMap;3751  bool HasNonzeroOffset = false;3752 3753  for (const auto &I : NewMethods) {3754    const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I.first.getDecl());3755    assert(hasVtableSlot(MD));3756 3757    std::string MethodName = PredefinedExpr::ComputeName(3758        PredefinedIdentKind::PrettyFunctionNoVirtual, MD);3759 3760    if (isa<CXXDestructorDecl>(MD)) {3761      IndicesMap[I.second] = MethodName + " [scalar deleting]";3762    } else {3763      IndicesMap[I.second] = MethodName;3764    }3765 3766    if (!I.second.VFPtrOffset.isZero() || I.second.VBTableIndex != 0)3767      HasNonzeroOffset = true;3768  }3769 3770  // Print the vtable indices for all the member functions.3771  if (!IndicesMap.empty()) {3772    Out << "VFTable indices for ";3773    Out << "'";3774    RD->printQualifiedName(Out);3775    Out << "' (" << IndicesMap.size()3776        << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n";3777 3778    CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1);3779    uint64_t LastVBIndex = 0;3780    for (const auto &I : IndicesMap) {3781      CharUnits VFPtrOffset = I.first.VFPtrOffset;3782      uint64_t VBIndex = I.first.VBTableIndex;3783      if (HasNonzeroOffset &&3784          (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) {3785        assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);3786        Out << " -- accessible via ";3787        if (VBIndex)3788          Out << "vbtable index " << VBIndex << ", ";3789        Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";3790        LastVFPtrOffset = VFPtrOffset;3791        LastVBIndex = VBIndex;3792      }3793 3794      uint64_t VTableIndex = I.first.Index;3795      const std::string &MethodName = I.second;3796      Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n';3797    }3798    Out << '\n';3799  }3800 3801  Out.flush();3802}3803 3804const VirtualBaseInfo &MicrosoftVTableContext::computeVBTableRelatedInformation(3805    const CXXRecordDecl *RD) {3806  VirtualBaseInfo *VBI;3807 3808  {3809    // Get or create a VBI for RD.  Don't hold a reference to the DenseMap cell,3810    // as it may be modified and rehashed under us.3811    std::unique_ptr<VirtualBaseInfo> &Entry = VBaseInfo[RD];3812    if (Entry)3813      return *Entry;3814    Entry = std::make_unique<VirtualBaseInfo>();3815    VBI = Entry.get();3816  }3817 3818  computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths);3819 3820  // First, see if the Derived class shared the vbptr with a non-virtual base.3821  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);3822  if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {3823    // If the Derived class shares the vbptr with a non-virtual base, the shared3824    // virtual bases come first so that the layout is the same.3825    const VirtualBaseInfo &BaseInfo =3826        computeVBTableRelatedInformation(VBPtrBase);3827    VBI->VBTableIndices.insert_range(BaseInfo.VBTableIndices);3828  }3829 3830  // New vbases are added to the end of the vbtable.3831  // Skip the self entry and vbases visited in the non-virtual base, if any.3832  unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();3833  for (const auto &VB : RD->vbases()) {3834    const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();3835    if (VBI->VBTableIndices.try_emplace(CurVBase, VBTableIndex).second)3836      ++VBTableIndex;3837  }3838 3839  return *VBI;3840}3841 3842unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,3843                                                 const CXXRecordDecl *VBase) {3844  const VirtualBaseInfo &VBInfo = computeVBTableRelatedInformation(Derived);3845  assert(VBInfo.VBTableIndices.count(VBase));3846  return VBInfo.VBTableIndices.find(VBase)->second;3847}3848 3849const VPtrInfoVector &3850MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {3851  return computeVBTableRelatedInformation(RD).VBPtrPaths;3852}3853 3854const VPtrInfoVector &3855MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {3856  computeVTableRelatedInformation(RD);3857 3858  assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");3859  return *VFPtrLocations[RD];3860}3861 3862const VTableLayout &3863MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,3864                                         CharUnits VFPtrOffset) {3865  computeVTableRelatedInformation(RD);3866 3867  VFTableIdTy id(RD, VFPtrOffset);3868  assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");3869  return *VFTableLayouts[id];3870}3871 3872MethodVFTableLocation3873MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {3874  assert(hasVtableSlot(cast<CXXMethodDecl>(GD.getDecl())) &&3875         "Only use this method for virtual methods or dtors");3876  if (isa<CXXDestructorDecl>(GD.getDecl()))3877    assert(GD.getDtorType() == Dtor_Deleting);3878 3879  GD = GD.getCanonicalDecl();3880 3881  MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD);3882  if (I != MethodVFTableLocations.end())3883    return I->second;3884 3885  const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();3886 3887  computeVTableRelatedInformation(RD);3888 3889  I = MethodVFTableLocations.find(GD);3890  assert(I != MethodVFTableLocations.end() && "Did not find index!");3891  return I->second;3892}3893