1226586Sdim//===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===// 2226586Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6226586Sdim// 7226586Sdim//===----------------------------------------------------------------------===// 8226586Sdim// 9226586Sdim// This contains code dealing with generation of the layout of virtual tables. 10226586Sdim// 11226586Sdim//===----------------------------------------------------------------------===// 12226586Sdim 13226586Sdim#include "clang/AST/VTableBuilder.h" 14239462Sdim#include "clang/AST/ASTContext.h" 15288943Sdim#include "clang/AST/ASTDiagnostic.h" 16226586Sdim#include "clang/AST/CXXInheritance.h" 17226586Sdim#include "clang/AST/RecordLayout.h" 18226586Sdim#include "clang/Basic/TargetInfo.h" 19288943Sdim#include "llvm/ADT/SetOperations.h" 20276479Sdim#include "llvm/ADT/SmallPtrSet.h" 21226586Sdim#include "llvm/Support/Format.h" 22249423Sdim#include "llvm/Support/raw_ostream.h" 23226586Sdim#include <algorithm> 24226586Sdim#include <cstdio> 25226586Sdim 26226586Sdimusing namespace clang; 27226586Sdim 28226586Sdim#define DUMP_OVERRIDERS 0 29226586Sdim 30226586Sdimnamespace { 31226586Sdim 32226586Sdim/// BaseOffset - Represents an offset from a derived class to a direct or 33226586Sdim/// indirect base class. 34226586Sdimstruct BaseOffset { 35226586Sdim /// DerivedClass - The derived class. 36226586Sdim const CXXRecordDecl *DerivedClass; 37341825Sdim 38226586Sdim /// VirtualBase - If the path from the derived class to the base class 39261991Sdim /// involves virtual base classes, this holds the declaration of the last 40261991Sdim /// virtual base in this path (i.e. closest to the base class). 41226586Sdim const CXXRecordDecl *VirtualBase; 42226586Sdim 43226586Sdim /// NonVirtualOffset - The offset from the derived class to the base class. 44341825Sdim /// (Or the offset from the virtual base class to the base class, if the 45226586Sdim /// path from the derived class to the base class involves a virtual base 46226586Sdim /// class. 47226586Sdim CharUnits NonVirtualOffset; 48276479Sdim 49276479Sdim BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr), 50276479Sdim NonVirtualOffset(CharUnits::Zero()) { } 51226586Sdim BaseOffset(const CXXRecordDecl *DerivedClass, 52226586Sdim const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset) 53341825Sdim : DerivedClass(DerivedClass), VirtualBase(VirtualBase), 54226586Sdim NonVirtualOffset(NonVirtualOffset) { } 55226586Sdim 56226586Sdim bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; } 57226586Sdim}; 58226586Sdim 59226586Sdim/// FinalOverriders - Contains the final overrider member functions for all 60226586Sdim/// member functions in the base subobjects of a class. 61226586Sdimclass FinalOverriders { 62226586Sdimpublic: 63226586Sdim /// OverriderInfo - Information about a final overrider. 64226586Sdim struct OverriderInfo { 65226586Sdim /// Method - The method decl of the overrider. 66226586Sdim const CXXMethodDecl *Method; 67226586Sdim 68280031Sdim /// VirtualBase - The virtual base class subobject of this overrider. 69276479Sdim /// Note that this records the closest derived virtual base class subobject. 70276479Sdim const CXXRecordDecl *VirtualBase; 71276479Sdim 72261991Sdim /// Offset - the base offset of the overrider's parent in the layout class. 73226586Sdim CharUnits Offset; 74276479Sdim 75276479Sdim OverriderInfo() : Method(nullptr), VirtualBase(nullptr), 76276479Sdim Offset(CharUnits::Zero()) { } 77226586Sdim }; 78226586Sdim 79226586Sdimprivate: 80226586Sdim /// MostDerivedClass - The most derived class for which the final overriders 81226586Sdim /// are stored. 82226586Sdim const CXXRecordDecl *MostDerivedClass; 83341825Sdim 84341825Sdim /// MostDerivedClassOffset - If we're building final overriders for a 85226586Sdim /// construction vtable, this holds the offset from the layout class to the 86226586Sdim /// most derived class. 87226586Sdim const CharUnits MostDerivedClassOffset; 88226586Sdim 89341825Sdim /// LayoutClass - The class we're using for layout information. Will be 90226586Sdim /// different than the most derived class if the final overriders are for a 91341825Sdim /// construction vtable. 92341825Sdim const CXXRecordDecl *LayoutClass; 93226586Sdim 94226586Sdim ASTContext &Context; 95341825Sdim 96226586Sdim /// MostDerivedClassLayout - the AST record layout of the most derived class. 97226586Sdim const ASTRecordLayout &MostDerivedClassLayout; 98226586Sdim 99226586Sdim /// MethodBaseOffsetPairTy - Uniquely identifies a member function 100226586Sdim /// in a base subobject. 101226586Sdim typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy; 102226586Sdim 103226586Sdim typedef llvm::DenseMap<MethodBaseOffsetPairTy, 104226586Sdim OverriderInfo> OverridersMapTy; 105341825Sdim 106341825Sdim /// OverridersMap - The final overriders for all virtual member functions of 107226586Sdim /// all the base subobjects of the most derived class. 108226586Sdim OverridersMapTy OverridersMap; 109341825Sdim 110226586Sdim /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented 111226586Sdim /// as a record decl and a subobject number) and its offsets in the most 112226586Sdim /// derived class as well as the layout class. 113341825Sdim typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>, 114226586Sdim CharUnits> SubobjectOffsetMapTy; 115226586Sdim 116226586Sdim typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy; 117341825Sdim 118226586Sdim /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the 119226586Sdim /// given base. 120226586Sdim void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual, 121226586Sdim CharUnits OffsetInLayoutClass, 122226586Sdim SubobjectOffsetMapTy &SubobjectOffsets, 123226586Sdim SubobjectOffsetMapTy &SubobjectLayoutClassOffsets, 124226586Sdim SubobjectCountMapTy &SubobjectCounts); 125226586Sdim 126226586Sdim typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy; 127341825Sdim 128226586Sdim /// dump - dump the final overriders for a base subobject, and all its direct 129226586Sdim /// and indirect base subobjects. 130226586Sdim void dump(raw_ostream &Out, BaseSubobject Base, 131226586Sdim VisitedVirtualBasesSetTy& VisitedVirtualBases); 132341825Sdim 133226586Sdimpublic: 134226586Sdim FinalOverriders(const CXXRecordDecl *MostDerivedClass, 135226586Sdim CharUnits MostDerivedClassOffset, 136226586Sdim const CXXRecordDecl *LayoutClass); 137226586Sdim 138226586Sdim /// getOverrider - Get the final overrider for the given method declaration in 139341825Sdim /// the subobject with the given base offset. 140341825Sdim OverriderInfo getOverrider(const CXXMethodDecl *MD, 141226586Sdim CharUnits BaseOffset) const { 142341825Sdim assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) && 143226586Sdim "Did not find overrider!"); 144341825Sdim 145226586Sdim return OverridersMap.lookup(std::make_pair(MD, BaseOffset)); 146226586Sdim } 147341825Sdim 148226586Sdim /// dump - dump the final overriders. 149226586Sdim void dump() { 150226586Sdim VisitedVirtualBasesSetTy VisitedVirtualBases; 151341825Sdim dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()), 152226586Sdim VisitedVirtualBases); 153226586Sdim } 154341825Sdim 155226586Sdim}; 156226586Sdim 157226586SdimFinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass, 158226586Sdim CharUnits MostDerivedClassOffset, 159226586Sdim const CXXRecordDecl *LayoutClass) 160341825Sdim : MostDerivedClass(MostDerivedClass), 161226586Sdim MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass), 162226586Sdim Context(MostDerivedClass->getASTContext()), 163226586Sdim MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) { 164226586Sdim 165226586Sdim // Compute base offsets. 166226586Sdim SubobjectOffsetMapTy SubobjectOffsets; 167226586Sdim SubobjectOffsetMapTy SubobjectLayoutClassOffsets; 168226586Sdim SubobjectCountMapTy SubobjectCounts; 169341825Sdim ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 170226586Sdim /*IsVirtual=*/false, 171341825Sdim MostDerivedClassOffset, 172341825Sdim SubobjectOffsets, SubobjectLayoutClassOffsets, 173226586Sdim SubobjectCounts); 174226586Sdim 175239462Sdim // Get the final overriders. 176226586Sdim CXXFinalOverriderMap FinalOverriders; 177226586Sdim MostDerivedClass->getFinalOverriders(FinalOverriders); 178226586Sdim 179296417Sdim for (const auto &Overrider : FinalOverriders) { 180296417Sdim const CXXMethodDecl *MD = Overrider.first; 181296417Sdim const OverridingMethods &Methods = Overrider.second; 182226586Sdim 183296417Sdim for (const auto &M : Methods) { 184296417Sdim unsigned SubobjectNumber = M.first; 185341825Sdim assert(SubobjectOffsets.count(std::make_pair(MD->getParent(), 186226586Sdim SubobjectNumber)) && 187226586Sdim "Did not find subobject offset!"); 188341825Sdim 189226586Sdim CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(), 190226586Sdim SubobjectNumber)]; 191226586Sdim 192296417Sdim assert(M.second.size() == 1 && "Final overrider is not unique!"); 193296417Sdim const UniqueVirtualMethod &Method = M.second.front(); 194226586Sdim 195226586Sdim const CXXRecordDecl *OverriderRD = Method.Method->getParent(); 196226586Sdim assert(SubobjectLayoutClassOffsets.count( 197226586Sdim std::make_pair(OverriderRD, Method.Subobject)) 198226586Sdim && "Did not find subobject offset!"); 199226586Sdim CharUnits OverriderOffset = 200341825Sdim SubobjectLayoutClassOffsets[std::make_pair(OverriderRD, 201226586Sdim Method.Subobject)]; 202226586Sdim 203226586Sdim OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)]; 204226586Sdim assert(!Overrider.Method && "Overrider should not exist yet!"); 205341825Sdim 206226586Sdim Overrider.Offset = OverriderOffset; 207226586Sdim Overrider.Method = Method.Method; 208276479Sdim Overrider.VirtualBase = Method.InVirtualSubobject; 209226586Sdim } 210226586Sdim } 211226586Sdim 212226586Sdim#if DUMP_OVERRIDERS 213226586Sdim // And dump them (for now). 214226586Sdim dump(); 215226586Sdim#endif 216226586Sdim} 217226586Sdim 218288943Sdimstatic BaseOffset ComputeBaseOffset(const ASTContext &Context, 219226586Sdim const CXXRecordDecl *DerivedRD, 220226586Sdim const CXXBasePath &Path) { 221226586Sdim CharUnits NonVirtualOffset = CharUnits::Zero(); 222226586Sdim 223226586Sdim unsigned NonVirtualStart = 0; 224276479Sdim const CXXRecordDecl *VirtualBase = nullptr; 225276479Sdim 226226586Sdim // First, look for the virtual base class. 227261991Sdim for (int I = Path.size(), E = 0; I != E; --I) { 228261991Sdim const CXXBasePathElement &Element = Path[I - 1]; 229261991Sdim 230226586Sdim if (Element.Base->isVirtual()) { 231261991Sdim NonVirtualStart = I; 232226586Sdim QualType VBaseType = Element.Base->getType(); 233261991Sdim VirtualBase = VBaseType->getAsCXXRecordDecl(); 234261991Sdim break; 235226586Sdim } 236226586Sdim } 237341825Sdim 238226586Sdim // Now compute the non-virtual offset. 239226586Sdim for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) { 240226586Sdim const CXXBasePathElement &Element = Path[I]; 241341825Sdim 242226586Sdim // Check the base class offset. 243226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class); 244226586Sdim 245261991Sdim const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl(); 246226586Sdim 247226586Sdim NonVirtualOffset += Layout.getBaseClassOffset(Base); 248226586Sdim } 249341825Sdim 250226586Sdim // FIXME: This should probably use CharUnits or something. Maybe we should 251341825Sdim // even change the base offsets in ASTRecordLayout to be specified in 252226586Sdim // CharUnits. 253226586Sdim return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset); 254341825Sdim 255226586Sdim} 256226586Sdim 257288943Sdimstatic BaseOffset ComputeBaseOffset(const ASTContext &Context, 258226586Sdim const CXXRecordDecl *BaseRD, 259226586Sdim const CXXRecordDecl *DerivedRD) { 260226586Sdim CXXBasePaths Paths(/*FindAmbiguities=*/false, 261226586Sdim /*RecordPaths=*/true, /*DetectVirtual=*/false); 262249423Sdim 263249423Sdim if (!DerivedRD->isDerivedFrom(BaseRD, Paths)) 264226586Sdim llvm_unreachable("Class must be derived from the passed in base class!"); 265226586Sdim 266226586Sdim return ComputeBaseOffset(Context, DerivedRD, Paths.front()); 267226586Sdim} 268226586Sdim 269226586Sdimstatic BaseOffset 270341825SdimComputeReturnAdjustmentBaseOffset(ASTContext &Context, 271226586Sdim const CXXMethodDecl *DerivedMD, 272226586Sdim const CXXMethodDecl *BaseMD) { 273360784Sdim const auto *BaseFT = BaseMD->getType()->castAs<FunctionType>(); 274360784Sdim const auto *DerivedFT = DerivedMD->getType()->castAs<FunctionType>(); 275341825Sdim 276226586Sdim // Canonicalize the return types. 277276479Sdim CanQualType CanDerivedReturnType = 278276479Sdim Context.getCanonicalType(DerivedFT->getReturnType()); 279276479Sdim CanQualType CanBaseReturnType = 280276479Sdim Context.getCanonicalType(BaseFT->getReturnType()); 281276479Sdim 282341825Sdim assert(CanDerivedReturnType->getTypeClass() == 283341825Sdim CanBaseReturnType->getTypeClass() && 284226586Sdim "Types must have same type class!"); 285341825Sdim 286226586Sdim if (CanDerivedReturnType == CanBaseReturnType) { 287226586Sdim // No adjustment needed. 288226586Sdim return BaseOffset(); 289226586Sdim } 290341825Sdim 291226586Sdim if (isa<ReferenceType>(CanDerivedReturnType)) { 292341825Sdim CanDerivedReturnType = 293226586Sdim CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType(); 294341825Sdim CanBaseReturnType = 295226586Sdim CanBaseReturnType->getAs<ReferenceType>()->getPointeeType(); 296226586Sdim } else if (isa<PointerType>(CanDerivedReturnType)) { 297341825Sdim CanDerivedReturnType = 298226586Sdim CanDerivedReturnType->getAs<PointerType>()->getPointeeType(); 299341825Sdim CanBaseReturnType = 300226586Sdim CanBaseReturnType->getAs<PointerType>()->getPointeeType(); 301226586Sdim } else { 302226586Sdim llvm_unreachable("Unexpected return type!"); 303226586Sdim } 304341825Sdim 305226586Sdim // We need to compare unqualified types here; consider 306226586Sdim // const T *Base::foo(); 307226586Sdim // T *Derived::foo(); 308341825Sdim if (CanDerivedReturnType.getUnqualifiedType() == 309226586Sdim CanBaseReturnType.getUnqualifiedType()) { 310226586Sdim // No adjustment needed. 311226586Sdim return BaseOffset(); 312226586Sdim } 313341825Sdim 314341825Sdim const CXXRecordDecl *DerivedRD = 315226586Sdim cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl()); 316341825Sdim 317341825Sdim const CXXRecordDecl *BaseRD = 318226586Sdim cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl()); 319226586Sdim 320226586Sdim return ComputeBaseOffset(Context, BaseRD, DerivedRD); 321226586Sdim} 322226586Sdim 323341825Sdimvoid 324226586SdimFinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual, 325226586Sdim CharUnits OffsetInLayoutClass, 326226586Sdim SubobjectOffsetMapTy &SubobjectOffsets, 327226586Sdim SubobjectOffsetMapTy &SubobjectLayoutClassOffsets, 328226586Sdim SubobjectCountMapTy &SubobjectCounts) { 329226586Sdim const CXXRecordDecl *RD = Base.getBase(); 330341825Sdim 331226586Sdim unsigned SubobjectNumber = 0; 332226586Sdim if (!IsVirtual) 333226586Sdim SubobjectNumber = ++SubobjectCounts[RD]; 334226586Sdim 335226586Sdim // Set up the subobject to offset mapping. 336226586Sdim assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber)) 337226586Sdim && "Subobject offset already exists!"); 338341825Sdim assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber)) 339226586Sdim && "Subobject offset already exists!"); 340226586Sdim 341226586Sdim SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset(); 342226586Sdim SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] = 343226586Sdim OffsetInLayoutClass; 344341825Sdim 345226586Sdim // Traverse our bases. 346276479Sdim for (const auto &B : RD->bases()) { 347276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 348226586Sdim 349226586Sdim CharUnits BaseOffset; 350226586Sdim CharUnits BaseOffsetInLayoutClass; 351276479Sdim if (B.isVirtual()) { 352226586Sdim // Check if we've visited this virtual base before. 353226586Sdim if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0))) 354226586Sdim continue; 355226586Sdim 356226586Sdim const ASTRecordLayout &LayoutClassLayout = 357226586Sdim Context.getASTRecordLayout(LayoutClass); 358226586Sdim 359226586Sdim BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 360341825Sdim BaseOffsetInLayoutClass = 361226586Sdim LayoutClassLayout.getVBaseClassOffset(BaseDecl); 362226586Sdim } else { 363226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 364226586Sdim CharUnits Offset = Layout.getBaseClassOffset(BaseDecl); 365341825Sdim 366226586Sdim BaseOffset = Base.getBaseOffset() + Offset; 367226586Sdim BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset; 368226586Sdim } 369226586Sdim 370341825Sdim ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset), 371341825Sdim B.isVirtual(), BaseOffsetInLayoutClass, 372341825Sdim SubobjectOffsets, SubobjectLayoutClassOffsets, 373226586Sdim SubobjectCounts); 374226586Sdim } 375226586Sdim} 376226586Sdim 377226586Sdimvoid FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base, 378226586Sdim VisitedVirtualBasesSetTy &VisitedVirtualBases) { 379226586Sdim const CXXRecordDecl *RD = Base.getBase(); 380226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 381226586Sdim 382276479Sdim for (const auto &B : RD->bases()) { 383276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 384341825Sdim 385226586Sdim // Ignore bases that don't have any virtual member functions. 386226586Sdim if (!BaseDecl->isPolymorphic()) 387226586Sdim continue; 388226586Sdim 389226586Sdim CharUnits BaseOffset; 390276479Sdim if (B.isVirtual()) { 391280031Sdim if (!VisitedVirtualBases.insert(BaseDecl).second) { 392226586Sdim // We've visited this base before. 393226586Sdim continue; 394226586Sdim } 395341825Sdim 396226586Sdim BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 397226586Sdim } else { 398226586Sdim BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset(); 399226586Sdim } 400226586Sdim 401226586Sdim dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases); 402226586Sdim } 403226586Sdim 404276479Sdim Out << "Final overriders for ("; 405276479Sdim RD->printQualifiedName(Out); 406276479Sdim Out << ", "; 407226586Sdim Out << Base.getBaseOffset().getQuantity() << ")\n"; 408226586Sdim 409226586Sdim // Now dump the overriders for this base subobject. 410276479Sdim for (const auto *MD : RD->methods()) { 411226586Sdim if (!MD->isVirtual()) 412226586Sdim continue; 413288943Sdim MD = MD->getCanonicalDecl(); 414288943Sdim 415226586Sdim OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset()); 416226586Sdim 417276479Sdim Out << " "; 418276479Sdim MD->printQualifiedName(Out); 419276479Sdim Out << " - ("; 420276479Sdim Overrider.Method->printQualifiedName(Out); 421261991Sdim Out << ", " << Overrider.Offset.getQuantity() << ')'; 422226586Sdim 423226586Sdim BaseOffset Offset; 424226586Sdim if (!Overrider.Method->isPure()) 425226586Sdim Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD); 426226586Sdim 427226586Sdim if (!Offset.isEmpty()) { 428226586Sdim Out << " [ret-adj: "; 429276479Sdim if (Offset.VirtualBase) { 430276479Sdim Offset.VirtualBase->printQualifiedName(Out); 431276479Sdim Out << " vbase, "; 432276479Sdim } 433341825Sdim 434226586Sdim Out << Offset.NonVirtualOffset.getQuantity() << " nv]"; 435226586Sdim } 436341825Sdim 437226586Sdim Out << "\n"; 438341825Sdim } 439226586Sdim} 440226586Sdim 441226586Sdim/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable. 442226586Sdimstruct VCallOffsetMap { 443341825Sdim 444226586Sdim typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy; 445341825Sdim 446226586Sdim /// Offsets - Keeps track of methods and their offsets. 447226586Sdim // FIXME: This should be a real map and not a vector. 448226586Sdim SmallVector<MethodAndOffsetPairTy, 16> Offsets; 449226586Sdim 450226586Sdim /// MethodsCanShareVCallOffset - Returns whether two virtual member functions 451226586Sdim /// can share the same vcall offset. 452226586Sdim static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, 453226586Sdim const CXXMethodDecl *RHS); 454226586Sdim 455226586Sdimpublic: 456226586Sdim /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the 457226586Sdim /// add was successful, or false if there was already a member function with 458226586Sdim /// the same signature in the map. 459226586Sdim bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset); 460341825Sdim 461226586Sdim /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the 462226586Sdim /// vtable address point) for the given virtual member function. 463226586Sdim CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD); 464341825Sdim 465226586Sdim // empty - Return whether the offset map is empty or not. 466226586Sdim bool empty() const { return Offsets.empty(); } 467226586Sdim}; 468226586Sdim 469226586Sdimstatic bool HasSameVirtualSignature(const CXXMethodDecl *LHS, 470226586Sdim const CXXMethodDecl *RHS) { 471234353Sdim const FunctionProtoType *LT = 472234353Sdim cast<FunctionProtoType>(LHS->getType().getCanonicalType()); 473234353Sdim const FunctionProtoType *RT = 474234353Sdim cast<FunctionProtoType>(RHS->getType().getCanonicalType()); 475226586Sdim 476226586Sdim // Fast-path matches in the canonical types. 477226586Sdim if (LT == RT) return true; 478226586Sdim 479226586Sdim // Force the signatures to match. We can't rely on the overrides 480226586Sdim // list here because there isn't necessarily an inheritance 481226586Sdim // relationship between the two methods. 482353358Sdim if (LT->getMethodQuals() != RT->getMethodQuals()) 483226586Sdim return false; 484296417Sdim return LT->getParamTypes() == RT->getParamTypes(); 485226586Sdim} 486226586Sdim 487226586Sdimbool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, 488226586Sdim const CXXMethodDecl *RHS) { 489226586Sdim assert(LHS->isVirtual() && "LHS must be virtual!"); 490226586Sdim assert(RHS->isVirtual() && "LHS must be virtual!"); 491341825Sdim 492226586Sdim // A destructor can share a vcall offset with another destructor. 493226586Sdim if (isa<CXXDestructorDecl>(LHS)) 494226586Sdim return isa<CXXDestructorDecl>(RHS); 495226586Sdim 496226586Sdim // FIXME: We need to check more things here. 497341825Sdim 498226586Sdim // The methods must have the same name. 499226586Sdim DeclarationName LHSName = LHS->getDeclName(); 500226586Sdim DeclarationName RHSName = RHS->getDeclName(); 501226586Sdim if (LHSName != RHSName) 502226586Sdim return false; 503226586Sdim 504226586Sdim // And the same signatures. 505226586Sdim return HasSameVirtualSignature(LHS, RHS); 506226586Sdim} 507226586Sdim 508341825Sdimbool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD, 509226586Sdim CharUnits OffsetOffset) { 510226586Sdim // Check if we can reuse an offset. 511296417Sdim for (const auto &OffsetPair : Offsets) { 512296417Sdim if (MethodsCanShareVCallOffset(OffsetPair.first, MD)) 513226586Sdim return false; 514226586Sdim } 515341825Sdim 516226586Sdim // Add the offset. 517226586Sdim Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset)); 518226586Sdim return true; 519226586Sdim} 520226586Sdim 521226586SdimCharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) { 522226586Sdim // Look for an offset. 523296417Sdim for (const auto &OffsetPair : Offsets) { 524296417Sdim if (MethodsCanShareVCallOffset(OffsetPair.first, MD)) 525296417Sdim return OffsetPair.second; 526226586Sdim } 527341825Sdim 528226586Sdim llvm_unreachable("Should always find a vcall offset offset!"); 529226586Sdim} 530226586Sdim 531226586Sdim/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets. 532226586Sdimclass VCallAndVBaseOffsetBuilder { 533226586Sdimpublic: 534341825Sdim typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 535226586Sdim VBaseOffsetOffsetsMapTy; 536226586Sdim 537226586Sdimprivate: 538226586Sdim /// MostDerivedClass - The most derived class for which we're building vcall 539226586Sdim /// and vbase offsets. 540226586Sdim const CXXRecordDecl *MostDerivedClass; 541341825Sdim 542341825Sdim /// LayoutClass - The class we're using for layout information. Will be 543226586Sdim /// different than the most derived class if we're building a construction 544226586Sdim /// vtable. 545226586Sdim const CXXRecordDecl *LayoutClass; 546341825Sdim 547226586Sdim /// Context - The ASTContext which we will use for layout information. 548226586Sdim ASTContext &Context; 549226586Sdim 550226586Sdim /// Components - vcall and vbase offset components 551226586Sdim typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy; 552226586Sdim VTableComponentVectorTy Components; 553341825Sdim 554226586Sdim /// VisitedVirtualBases - Visited virtual bases. 555226586Sdim llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases; 556341825Sdim 557226586Sdim /// VCallOffsets - Keeps track of vcall offsets. 558226586Sdim VCallOffsetMap VCallOffsets; 559226586Sdim 560226586Sdim 561226586Sdim /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets, 562226586Sdim /// relative to the address point. 563226586Sdim VBaseOffsetOffsetsMapTy VBaseOffsetOffsets; 564341825Sdim 565226586Sdim /// FinalOverriders - The final overriders of the most derived class. 566226586Sdim /// (Can be null when we're not building a vtable of the most derived class). 567226586Sdim const FinalOverriders *Overriders; 568226586Sdim 569226586Sdim /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the 570226586Sdim /// given base subobject. 571226586Sdim void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual, 572226586Sdim CharUnits RealBaseOffset); 573341825Sdim 574226586Sdim /// AddVCallOffsets - Add vcall offsets for the given base subobject. 575226586Sdim void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset); 576341825Sdim 577226586Sdim /// AddVBaseOffsets - Add vbase offsets for the given class. 578341825Sdim void AddVBaseOffsets(const CXXRecordDecl *Base, 579226586Sdim CharUnits OffsetInLayoutClass); 580341825Sdim 581226586Sdim /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in 582226586Sdim /// chars, relative to the vtable address point. 583226586Sdim CharUnits getCurrentOffsetOffset() const; 584341825Sdim 585226586Sdimpublic: 586226586Sdim VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass, 587226586Sdim const CXXRecordDecl *LayoutClass, 588226586Sdim const FinalOverriders *Overriders, 589226586Sdim BaseSubobject Base, bool BaseIsVirtual, 590226586Sdim CharUnits OffsetInLayoutClass) 591341825Sdim : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass), 592226586Sdim Context(MostDerivedClass->getASTContext()), Overriders(Overriders) { 593341825Sdim 594226586Sdim // Add vcall and vbase offsets. 595226586Sdim AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass); 596226586Sdim } 597341825Sdim 598226586Sdim /// Methods for iterating over the components. 599226586Sdim typedef VTableComponentVectorTy::const_reverse_iterator const_iterator; 600226586Sdim const_iterator components_begin() const { return Components.rbegin(); } 601226586Sdim const_iterator components_end() const { return Components.rend(); } 602341825Sdim 603226586Sdim const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; } 604226586Sdim const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const { 605226586Sdim return VBaseOffsetOffsets; 606226586Sdim } 607226586Sdim}; 608341825Sdim 609341825Sdimvoid 610226586SdimVCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base, 611226586Sdim bool BaseIsVirtual, 612226586Sdim CharUnits RealBaseOffset) { 613226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase()); 614341825Sdim 615226586Sdim // Itanium C++ ABI 2.5.2: 616226586Sdim // ..in classes sharing a virtual table with a primary base class, the vcall 617226586Sdim // and vbase offsets added by the derived class all come before the vcall 618226586Sdim // and vbase offsets required by the base class, so that the latter may be 619226586Sdim // laid out as required by the base class without regard to additions from 620226586Sdim // the derived class(es). 621226586Sdim 622226586Sdim // (Since we're emitting the vcall and vbase offsets in reverse order, we'll 623226586Sdim // emit them for the primary base first). 624226586Sdim if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 625226586Sdim bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual(); 626226586Sdim 627226586Sdim CharUnits PrimaryBaseOffset; 628341825Sdim 629226586Sdim // Get the base offset of the primary base. 630226586Sdim if (PrimaryBaseIsVirtual) { 631239462Sdim assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 632226586Sdim "Primary vbase should have a zero offset!"); 633341825Sdim 634226586Sdim const ASTRecordLayout &MostDerivedClassLayout = 635226586Sdim Context.getASTRecordLayout(MostDerivedClass); 636341825Sdim 637341825Sdim PrimaryBaseOffset = 638226586Sdim MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase); 639226586Sdim } else { 640239462Sdim assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 641226586Sdim "Primary base should have a zero offset!"); 642226586Sdim 643226586Sdim PrimaryBaseOffset = Base.getBaseOffset(); 644226586Sdim } 645226586Sdim 646226586Sdim AddVCallAndVBaseOffsets( 647226586Sdim BaseSubobject(PrimaryBase,PrimaryBaseOffset), 648226586Sdim PrimaryBaseIsVirtual, RealBaseOffset); 649226586Sdim } 650226586Sdim 651226586Sdim AddVBaseOffsets(Base.getBase(), RealBaseOffset); 652226586Sdim 653226586Sdim // We only want to add vcall offsets for virtual bases. 654226586Sdim if (BaseIsVirtual) 655226586Sdim AddVCallOffsets(Base, RealBaseOffset); 656226586Sdim} 657226586Sdim 658226586SdimCharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const { 659341825Sdim // OffsetIndex is the index of this vcall or vbase offset, relative to the 660226586Sdim // vtable address point. (We subtract 3 to account for the information just 661226586Sdim // above the address point, the RTTI info, the offset to top, and the 662226586Sdim // vcall offset itself). 663226586Sdim int64_t OffsetIndex = -(int64_t)(3 + Components.size()); 664341825Sdim 665341825Sdim CharUnits PointerWidth = 666226586Sdim Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0)); 667226586Sdim CharUnits OffsetOffset = PointerWidth * OffsetIndex; 668226586Sdim return OffsetOffset; 669226586Sdim} 670226586Sdim 671341825Sdimvoid VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base, 672226586Sdim CharUnits VBaseOffset) { 673226586Sdim const CXXRecordDecl *RD = Base.getBase(); 674226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 675226586Sdim 676226586Sdim const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 677226586Sdim 678226586Sdim // Handle the primary base first. 679226586Sdim // We only want to add vcall offsets if the base is non-virtual; a virtual 680226586Sdim // primary base will have its vcall and vbase offsets emitted already. 681226586Sdim if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) { 682226586Sdim // Get the base offset of the primary base. 683239462Sdim assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 684226586Sdim "Primary base should have a zero offset!"); 685226586Sdim 686226586Sdim AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()), 687226586Sdim VBaseOffset); 688226586Sdim } 689341825Sdim 690226586Sdim // Add the vcall offsets. 691276479Sdim for (const auto *MD : RD->methods()) { 692226586Sdim if (!MD->isVirtual()) 693226586Sdim continue; 694288943Sdim MD = MD->getCanonicalDecl(); 695226586Sdim 696226586Sdim CharUnits OffsetOffset = getCurrentOffsetOffset(); 697341825Sdim 698226586Sdim // Don't add a vcall offset if we already have one for this member function 699226586Sdim // signature. 700226586Sdim if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset)) 701226586Sdim continue; 702226586Sdim 703226586Sdim CharUnits Offset = CharUnits::Zero(); 704226586Sdim 705226586Sdim if (Overriders) { 706226586Sdim // Get the final overrider. 707341825Sdim FinalOverriders::OverriderInfo Overrider = 708226586Sdim Overriders->getOverrider(MD, Base.getBaseOffset()); 709341825Sdim 710341825Sdim /// The vcall offset is the offset from the virtual base to the object 711226586Sdim /// where the function was overridden. 712226586Sdim Offset = Overrider.Offset - VBaseOffset; 713226586Sdim } 714341825Sdim 715226586Sdim Components.push_back( 716226586Sdim VTableComponent::MakeVCallOffset(Offset)); 717226586Sdim } 718226586Sdim 719226586Sdim // And iterate over all non-virtual bases (ignoring the primary base). 720341825Sdim for (const auto &B : RD->bases()) { 721276479Sdim if (B.isVirtual()) 722226586Sdim continue; 723226586Sdim 724276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 725226586Sdim if (BaseDecl == PrimaryBase) 726226586Sdim continue; 727226586Sdim 728226586Sdim // Get the base offset of this base. 729341825Sdim CharUnits BaseOffset = Base.getBaseOffset() + 730226586Sdim Layout.getBaseClassOffset(BaseDecl); 731341825Sdim 732341825Sdim AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset), 733226586Sdim VBaseOffset); 734226586Sdim } 735226586Sdim} 736226586Sdim 737341825Sdimvoid 738226586SdimVCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD, 739226586Sdim CharUnits OffsetInLayoutClass) { 740341825Sdim const ASTRecordLayout &LayoutClassLayout = 741226586Sdim Context.getASTRecordLayout(LayoutClass); 742226586Sdim 743226586Sdim // Add vbase offsets. 744276479Sdim for (const auto &B : RD->bases()) { 745276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 746226586Sdim 747226586Sdim // Check if this is a virtual base that we haven't visited before. 748280031Sdim if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl).second) { 749341825Sdim CharUnits Offset = 750226586Sdim LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass; 751226586Sdim 752226586Sdim // Add the vbase offset offset. 753226586Sdim assert(!VBaseOffsetOffsets.count(BaseDecl) && 754226586Sdim "vbase offset offset already exists!"); 755226586Sdim 756226586Sdim CharUnits VBaseOffsetOffset = getCurrentOffsetOffset(); 757226586Sdim VBaseOffsetOffsets.insert( 758226586Sdim std::make_pair(BaseDecl, VBaseOffsetOffset)); 759226586Sdim 760226586Sdim Components.push_back( 761226586Sdim VTableComponent::MakeVBaseOffset(Offset)); 762226586Sdim } 763226586Sdim 764226586Sdim // Check the base class looking for more vbase offsets. 765226586Sdim AddVBaseOffsets(BaseDecl, OffsetInLayoutClass); 766226586Sdim } 767226586Sdim} 768226586Sdim 769261991Sdim/// ItaniumVTableBuilder - Class for building vtable layout information. 770261991Sdimclass ItaniumVTableBuilder { 771226586Sdimpublic: 772341825Sdim /// PrimaryBasesSetVectorTy - A set vector of direct and indirect 773226586Sdim /// primary bases. 774341825Sdim typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> 775226586Sdim PrimaryBasesSetVectorTy; 776341825Sdim 777341825Sdim typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 778226586Sdim VBaseOffsetOffsetsMapTy; 779226586Sdim 780314564Sdim typedef VTableLayout::AddressPointsMapTy AddressPointsMapTy; 781314564Sdim 782261991Sdim typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy; 783261991Sdim 784226586Sdimprivate: 785226586Sdim /// VTables - Global vtable information. 786261991Sdim ItaniumVTableContext &VTables; 787341825Sdim 788226586Sdim /// MostDerivedClass - The most derived class for which we're building this 789226586Sdim /// vtable. 790226586Sdim const CXXRecordDecl *MostDerivedClass; 791226586Sdim 792226586Sdim /// MostDerivedClassOffset - If we're building a construction vtable, this 793226586Sdim /// holds the offset from the layout class to the most derived class. 794226586Sdim const CharUnits MostDerivedClassOffset; 795341825Sdim 796341825Sdim /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual 797226586Sdim /// base. (This only makes sense when building a construction vtable). 798226586Sdim bool MostDerivedClassIsVirtual; 799341825Sdim 800341825Sdim /// LayoutClass - The class we're using for layout information. Will be 801226586Sdim /// different than the most derived class if we're building a construction 802226586Sdim /// vtable. 803226586Sdim const CXXRecordDecl *LayoutClass; 804341825Sdim 805226586Sdim /// Context - The ASTContext which we will use for layout information. 806226586Sdim ASTContext &Context; 807341825Sdim 808226586Sdim /// FinalOverriders - The final overriders of the most derived class. 809226586Sdim const FinalOverriders Overriders; 810226586Sdim 811226586Sdim /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual 812226586Sdim /// bases in this vtable. 813226586Sdim llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases; 814226586Sdim 815226586Sdim /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for 816226586Sdim /// the most derived class. 817226586Sdim VBaseOffsetOffsetsMapTy VBaseOffsetOffsets; 818314564Sdim 819226586Sdim /// Components - The components of the vtable being built. 820226586Sdim SmallVector<VTableComponent, 64> Components; 821226586Sdim 822226586Sdim /// AddressPoints - Address points for the vtable being built. 823226586Sdim AddressPointsMapTy AddressPoints; 824226586Sdim 825226586Sdim /// MethodInfo - Contains information about a method in a vtable. 826226586Sdim /// (Used for computing 'this' pointer adjustment thunks. 827226586Sdim struct MethodInfo { 828226586Sdim /// BaseOffset - The base offset of this method. 829226586Sdim const CharUnits BaseOffset; 830341825Sdim 831226586Sdim /// BaseOffsetInLayoutClass - The base offset in the layout class of this 832226586Sdim /// method. 833226586Sdim const CharUnits BaseOffsetInLayoutClass; 834341825Sdim 835226586Sdim /// VTableIndex - The index in the vtable that this method has. 836226586Sdim /// (For destructors, this is the index of the complete destructor). 837226586Sdim const uint64_t VTableIndex; 838341825Sdim 839341825Sdim MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass, 840226586Sdim uint64_t VTableIndex) 841341825Sdim : BaseOffset(BaseOffset), 842226586Sdim BaseOffsetInLayoutClass(BaseOffsetInLayoutClass), 843226586Sdim VTableIndex(VTableIndex) { } 844341825Sdim 845341825Sdim MethodInfo() 846341825Sdim : BaseOffset(CharUnits::Zero()), 847341825Sdim BaseOffsetInLayoutClass(CharUnits::Zero()), 848226586Sdim VTableIndex(0) { } 849353358Sdim 850353358Sdim MethodInfo(MethodInfo const&) = default; 851226586Sdim }; 852341825Sdim 853226586Sdim typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy; 854341825Sdim 855226586Sdim /// MethodInfoMap - The information for all methods in the vtable we're 856226586Sdim /// currently building. 857226586Sdim MethodInfoMapTy MethodInfoMap; 858261991Sdim 859261991Sdim /// MethodVTableIndices - Contains the index (relative to the vtable address 860261991Sdim /// point) where the function pointer for a virtual function is stored. 861261991Sdim MethodVTableIndicesTy MethodVTableIndices; 862261991Sdim 863226586Sdim typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy; 864341825Sdim 865341825Sdim /// VTableThunks - The thunks by vtable index in the vtable currently being 866226586Sdim /// built. 867226586Sdim VTableThunksMapTy VTableThunks; 868226586Sdim 869226586Sdim typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 870226586Sdim typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 871341825Sdim 872226586Sdim /// Thunks - A map that contains all the thunks needed for all methods in the 873226586Sdim /// most derived class for which the vtable is currently being built. 874226586Sdim ThunksMapTy Thunks; 875341825Sdim 876226586Sdim /// AddThunk - Add a thunk for the given method. 877226586Sdim void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk); 878341825Sdim 879226586Sdim /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the 880226586Sdim /// part of the vtable we're currently building. 881226586Sdim void ComputeThisAdjustments(); 882341825Sdim 883226586Sdim typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy; 884226586Sdim 885226586Sdim /// PrimaryVirtualBases - All known virtual bases who are a primary base of 886226586Sdim /// some other base. 887226586Sdim VisitedVirtualBasesSetTy PrimaryVirtualBases; 888226586Sdim 889226586Sdim /// ComputeReturnAdjustment - Compute the return adjustment given a return 890226586Sdim /// adjustment base offset. 891226586Sdim ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset); 892341825Sdim 893226586Sdim /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting 894226586Sdim /// the 'this' pointer from the base subobject to the derived subobject. 895226586Sdim BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base, 896226586Sdim BaseSubobject Derived) const; 897226586Sdim 898226586Sdim /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the 899226586Sdim /// given virtual member function, its offset in the layout class and its 900226586Sdim /// final overrider. 901341825Sdim ThisAdjustment 902341825Sdim ComputeThisAdjustment(const CXXMethodDecl *MD, 903226586Sdim CharUnits BaseOffsetInLayoutClass, 904226586Sdim FinalOverriders::OverriderInfo Overrider); 905226586Sdim 906226586Sdim /// AddMethod - Add a single virtual member function to the vtable 907226586Sdim /// components vector. 908226586Sdim void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment); 909226586Sdim 910226586Sdim /// IsOverriderUsed - Returns whether the overrider will ever be used in this 911341825Sdim /// part of the vtable. 912226586Sdim /// 913226586Sdim /// Itanium C++ ABI 2.5.2: 914226586Sdim /// 915226586Sdim /// struct A { virtual void f(); }; 916226586Sdim /// struct B : virtual public A { int i; }; 917226586Sdim /// struct C : virtual public A { int j; }; 918226586Sdim /// struct D : public B, public C {}; 919226586Sdim /// 920226586Sdim /// When B and C are declared, A is a primary base in each case, so although 921226586Sdim /// vcall offsets are allocated in the A-in-B and A-in-C vtables, no this 922226586Sdim /// adjustment is required and no thunk is generated. However, inside D 923226586Sdim /// objects, A is no longer a primary base of C, so if we allowed calls to 924226586Sdim /// C::f() to use the copy of A's vtable in the C subobject, we would need 925341825Sdim /// to adjust this from C* to B::A*, which would require a third-party 926341825Sdim /// thunk. Since we require that a call to C::f() first convert to A*, 927341825Sdim /// C-in-D's copy of A's vtable is never referenced, so this is not 928226586Sdim /// necessary. 929226586Sdim bool IsOverriderUsed(const CXXMethodDecl *Overrider, 930226586Sdim CharUnits BaseOffsetInLayoutClass, 931226586Sdim const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 932226586Sdim CharUnits FirstBaseOffsetInLayoutClass) const; 933226586Sdim 934341825Sdim 935226586Sdim /// AddMethods - Add the methods of this base subobject and all its 936226586Sdim /// primary bases to the vtable components vector. 937226586Sdim void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass, 938226586Sdim const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 939226586Sdim CharUnits FirstBaseOffsetInLayoutClass, 940226586Sdim PrimaryBasesSetVectorTy &PrimaryBases); 941226586Sdim 942226586Sdim // LayoutVTable - Layout the vtable for the given base class, including its 943226586Sdim // secondary vtables and any vtables for virtual bases. 944226586Sdim void LayoutVTable(); 945226586Sdim 946226586Sdim /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the 947226586Sdim /// given base subobject, as well as all its secondary vtables. 948226586Sdim /// 949226586Sdim /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base 950226586Sdim /// or a direct or indirect base of a virtual base. 951226586Sdim /// 952226586Sdim /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual 953341825Sdim /// in the layout class. 954226586Sdim void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base, 955226586Sdim bool BaseIsMorallyVirtual, 956226586Sdim bool BaseIsVirtualInLayoutClass, 957226586Sdim CharUnits OffsetInLayoutClass); 958341825Sdim 959226586Sdim /// LayoutSecondaryVTables - Layout the secondary vtables for the given base 960226586Sdim /// subobject. 961226586Sdim /// 962226586Sdim /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base 963226586Sdim /// or a direct or indirect base of a virtual base. 964226586Sdim void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual, 965226586Sdim CharUnits OffsetInLayoutClass); 966226586Sdim 967226586Sdim /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this 968226586Sdim /// class hierarchy. 969341825Sdim void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD, 970226586Sdim CharUnits OffsetInLayoutClass, 971226586Sdim VisitedVirtualBasesSetTy &VBases); 972226586Sdim 973226586Sdim /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the 974226586Sdim /// given base (excluding any primary bases). 975341825Sdim void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD, 976226586Sdim VisitedVirtualBasesSetTy &VBases); 977226586Sdim 978226586Sdim /// isBuildingConstructionVTable - Return whether this vtable builder is 979226586Sdim /// building a construction vtable. 980341825Sdim bool isBuildingConstructorVTable() const { 981226586Sdim return MostDerivedClass != LayoutClass; 982226586Sdim } 983226586Sdim 984226586Sdimpublic: 985314564Sdim /// Component indices of the first component of each of the vtables in the 986314564Sdim /// vtable group. 987314564Sdim SmallVector<size_t, 4> VTableIndices; 988314564Sdim 989261991Sdim ItaniumVTableBuilder(ItaniumVTableContext &VTables, 990261991Sdim const CXXRecordDecl *MostDerivedClass, 991261991Sdim CharUnits MostDerivedClassOffset, 992261991Sdim bool MostDerivedClassIsVirtual, 993261991Sdim const CXXRecordDecl *LayoutClass) 994261991Sdim : VTables(VTables), MostDerivedClass(MostDerivedClass), 995261991Sdim MostDerivedClassOffset(MostDerivedClassOffset), 996261991Sdim MostDerivedClassIsVirtual(MostDerivedClassIsVirtual), 997261991Sdim LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()), 998261991Sdim Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) { 999261991Sdim assert(!Context.getTargetInfo().getCXXABI().isMicrosoft()); 1000226586Sdim 1001226586Sdim LayoutVTable(); 1002226586Sdim 1003234353Sdim if (Context.getLangOpts().DumpVTableLayouts) 1004261991Sdim dumpLayout(llvm::outs()); 1005226586Sdim } 1006226586Sdim 1007226586Sdim uint64_t getNumThunks() const { 1008226586Sdim return Thunks.size(); 1009226586Sdim } 1010226586Sdim 1011226586Sdim ThunksMapTy::const_iterator thunks_begin() const { 1012226586Sdim return Thunks.begin(); 1013226586Sdim } 1014226586Sdim 1015226586Sdim ThunksMapTy::const_iterator thunks_end() const { 1016226586Sdim return Thunks.end(); 1017226586Sdim } 1018226586Sdim 1019226586Sdim const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const { 1020226586Sdim return VBaseOffsetOffsets; 1021226586Sdim } 1022226586Sdim 1023226586Sdim const AddressPointsMapTy &getAddressPoints() const { 1024226586Sdim return AddressPoints; 1025226586Sdim } 1026226586Sdim 1027261991Sdim MethodVTableIndicesTy::const_iterator vtable_indices_begin() const { 1028261991Sdim return MethodVTableIndices.begin(); 1029261991Sdim } 1030261991Sdim 1031261991Sdim MethodVTableIndicesTy::const_iterator vtable_indices_end() const { 1032261991Sdim return MethodVTableIndices.end(); 1033261991Sdim } 1034261991Sdim 1035314564Sdim ArrayRef<VTableComponent> vtable_components() const { return Components; } 1036226586Sdim 1037226586Sdim AddressPointsMapTy::const_iterator address_points_begin() const { 1038226586Sdim return AddressPoints.begin(); 1039226586Sdim } 1040226586Sdim 1041226586Sdim AddressPointsMapTy::const_iterator address_points_end() const { 1042226586Sdim return AddressPoints.end(); 1043226586Sdim } 1044226586Sdim 1045226586Sdim VTableThunksMapTy::const_iterator vtable_thunks_begin() const { 1046226586Sdim return VTableThunks.begin(); 1047226586Sdim } 1048226586Sdim 1049226586Sdim VTableThunksMapTy::const_iterator vtable_thunks_end() const { 1050226586Sdim return VTableThunks.end(); 1051226586Sdim } 1052226586Sdim 1053226586Sdim /// dumpLayout - Dump the vtable layout. 1054226586Sdim void dumpLayout(raw_ostream&); 1055226586Sdim}; 1056226586Sdim 1057261991Sdimvoid ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD, 1058261991Sdim const ThunkInfo &Thunk) { 1059341825Sdim assert(!isBuildingConstructorVTable() && 1060226586Sdim "Can't add thunks for construction vtable"); 1061226586Sdim 1062261991Sdim SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD]; 1063261991Sdim 1064226586Sdim // Check if we have this thunk already. 1065353358Sdim if (llvm::find(ThunksVector, Thunk) != ThunksVector.end()) 1066226586Sdim return; 1067341825Sdim 1068226586Sdim ThunksVector.push_back(Thunk); 1069226586Sdim} 1070226586Sdim 1071226586Sdimtypedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy; 1072226586Sdim 1073261991Sdim/// Visit all the methods overridden by the given method recursively, 1074261991Sdim/// in a depth-first pre-order. The Visitor's visitor method returns a bool 1075261991Sdim/// indicating whether to continue the recursion for the given overridden 1076261991Sdim/// method (i.e. returning false stops the iteration). 1077261991Sdimtemplate <class VisitorTy> 1078261991Sdimstatic void 1079261991SdimvisitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) { 1080226586Sdim assert(MD->isVirtual() && "Method is not virtual!"); 1081226586Sdim 1082327952Sdim for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) { 1083296417Sdim if (!Visitor(OverriddenMD)) 1084261991Sdim continue; 1085261991Sdim visitAllOverriddenMethods(OverriddenMD, Visitor); 1086226586Sdim } 1087226586Sdim} 1088226586Sdim 1089261991Sdim/// ComputeAllOverriddenMethods - Given a method decl, will return a set of all 1090261991Sdim/// the overridden methods that the function decl overrides. 1091261991Sdimstatic void 1092261991SdimComputeAllOverriddenMethods(const CXXMethodDecl *MD, 1093261991Sdim OverriddenMethodsSetTy& OverriddenMethods) { 1094296417Sdim auto OverriddenMethodsCollector = [&](const CXXMethodDecl *MD) { 1095296417Sdim // Don't recurse on this method if we've already collected it. 1096296417Sdim return OverriddenMethods.insert(MD).second; 1097296417Sdim }; 1098296417Sdim visitAllOverriddenMethods(MD, OverriddenMethodsCollector); 1099261991Sdim} 1100261991Sdim 1101261991Sdimvoid ItaniumVTableBuilder::ComputeThisAdjustments() { 1102226586Sdim // Now go through the method info map and see if any of the methods need 1103226586Sdim // 'this' pointer adjustments. 1104296417Sdim for (const auto &MI : MethodInfoMap) { 1105296417Sdim const CXXMethodDecl *MD = MI.first; 1106296417Sdim const MethodInfo &MethodInfo = MI.second; 1107226586Sdim 1108226586Sdim // Ignore adjustments for unused function pointers. 1109226586Sdim uint64_t VTableIndex = MethodInfo.VTableIndex; 1110341825Sdim if (Components[VTableIndex].getKind() == 1111226586Sdim VTableComponent::CK_UnusedFunctionPointer) 1112226586Sdim continue; 1113341825Sdim 1114226586Sdim // Get the final overrider for this method. 1115226586Sdim FinalOverriders::OverriderInfo Overrider = 1116226586Sdim Overriders.getOverrider(MD, MethodInfo.BaseOffset); 1117341825Sdim 1118226586Sdim // Check if we need an adjustment at all. 1119226586Sdim if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) { 1120226586Sdim // When a return thunk is needed by a derived class that overrides a 1121341825Sdim // virtual base, gcc uses a virtual 'this' adjustment as well. 1122226586Sdim // While the thunk itself might be needed by vtables in subclasses or 1123226586Sdim // in construction vtables, there doesn't seem to be a reason for using 1124226586Sdim // the thunk in this vtable. Still, we do so to match gcc. 1125226586Sdim if (VTableThunks.lookup(VTableIndex).Return.isEmpty()) 1126226586Sdim continue; 1127226586Sdim } 1128226586Sdim 1129226586Sdim ThisAdjustment ThisAdjustment = 1130226586Sdim ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider); 1131226586Sdim 1132226586Sdim if (ThisAdjustment.isEmpty()) 1133226586Sdim continue; 1134226586Sdim 1135226586Sdim // Add it. 1136226586Sdim VTableThunks[VTableIndex].This = ThisAdjustment; 1137226586Sdim 1138226586Sdim if (isa<CXXDestructorDecl>(MD)) { 1139226586Sdim // Add an adjustment for the deleting destructor as well. 1140226586Sdim VTableThunks[VTableIndex + 1].This = ThisAdjustment; 1141226586Sdim } 1142226586Sdim } 1143226586Sdim 1144226586Sdim /// Clear the method info map. 1145226586Sdim MethodInfoMap.clear(); 1146341825Sdim 1147226586Sdim if (isBuildingConstructorVTable()) { 1148226586Sdim // We don't need to store thunk information for construction vtables. 1149226586Sdim return; 1150226586Sdim } 1151226586Sdim 1152296417Sdim for (const auto &TI : VTableThunks) { 1153296417Sdim const VTableComponent &Component = Components[TI.first]; 1154296417Sdim const ThunkInfo &Thunk = TI.second; 1155226586Sdim const CXXMethodDecl *MD; 1156341825Sdim 1157226586Sdim switch (Component.getKind()) { 1158226586Sdim default: 1159226586Sdim llvm_unreachable("Unexpected vtable component kind!"); 1160226586Sdim case VTableComponent::CK_FunctionPointer: 1161226586Sdim MD = Component.getFunctionDecl(); 1162226586Sdim break; 1163226586Sdim case VTableComponent::CK_CompleteDtorPointer: 1164226586Sdim MD = Component.getDestructorDecl(); 1165226586Sdim break; 1166226586Sdim case VTableComponent::CK_DeletingDtorPointer: 1167226586Sdim // We've already added the thunk when we saw the complete dtor pointer. 1168226586Sdim continue; 1169226586Sdim } 1170226586Sdim 1171226586Sdim if (MD->getParent() == MostDerivedClass) 1172226586Sdim AddThunk(MD, Thunk); 1173226586Sdim } 1174226586Sdim} 1175226586Sdim 1176261991SdimReturnAdjustment 1177261991SdimItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) { 1178226586Sdim ReturnAdjustment Adjustment; 1179341825Sdim 1180226586Sdim if (!Offset.isEmpty()) { 1181226586Sdim if (Offset.VirtualBase) { 1182226586Sdim // Get the virtual base offset offset. 1183226586Sdim if (Offset.DerivedClass == MostDerivedClass) { 1184226586Sdim // We can get the offset offset directly from our map. 1185261991Sdim Adjustment.Virtual.Itanium.VBaseOffsetOffset = 1186226586Sdim VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity(); 1187226586Sdim } else { 1188261991Sdim Adjustment.Virtual.Itanium.VBaseOffsetOffset = 1189226586Sdim VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass, 1190226586Sdim Offset.VirtualBase).getQuantity(); 1191226586Sdim } 1192226586Sdim } 1193226586Sdim 1194226586Sdim Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity(); 1195226586Sdim } 1196341825Sdim 1197226586Sdim return Adjustment; 1198226586Sdim} 1199226586Sdim 1200261991SdimBaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset( 1201261991Sdim BaseSubobject Base, BaseSubobject Derived) const { 1202226586Sdim const CXXRecordDecl *BaseRD = Base.getBase(); 1203226586Sdim const CXXRecordDecl *DerivedRD = Derived.getBase(); 1204341825Sdim 1205226586Sdim CXXBasePaths Paths(/*FindAmbiguities=*/true, 1206226586Sdim /*RecordPaths=*/true, /*DetectVirtual=*/true); 1207226586Sdim 1208249423Sdim if (!DerivedRD->isDerivedFrom(BaseRD, Paths)) 1209226586Sdim llvm_unreachable("Class must be derived from the passed in base class!"); 1210226586Sdim 1211226586Sdim // We have to go through all the paths, and see which one leads us to the 1212226586Sdim // right base subobject. 1213296417Sdim for (const CXXBasePath &Path : Paths) { 1214296417Sdim BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, Path); 1215296417Sdim 1216226586Sdim CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset; 1217341825Sdim 1218226586Sdim if (Offset.VirtualBase) { 1219226586Sdim // If we have a virtual base class, the non-virtual offset is relative 1220226586Sdim // to the virtual base class offset. 1221226586Sdim const ASTRecordLayout &LayoutClassLayout = 1222226586Sdim Context.getASTRecordLayout(LayoutClass); 1223341825Sdim 1224341825Sdim /// Get the virtual base offset, relative to the most derived class 1225226586Sdim /// layout. 1226341825Sdim OffsetToBaseSubobject += 1227226586Sdim LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase); 1228226586Sdim } else { 1229341825Sdim // Otherwise, the non-virtual offset is relative to the derived class 1230226586Sdim // offset. 1231226586Sdim OffsetToBaseSubobject += Derived.getBaseOffset(); 1232226586Sdim } 1233341825Sdim 1234226586Sdim // Check if this path gives us the right base subobject. 1235226586Sdim if (OffsetToBaseSubobject == Base.getBaseOffset()) { 1236226586Sdim // Since we're going from the base class _to_ the derived class, we'll 1237226586Sdim // invert the non-virtual offset here. 1238226586Sdim Offset.NonVirtualOffset = -Offset.NonVirtualOffset; 1239226586Sdim return Offset; 1240341825Sdim } 1241226586Sdim } 1242341825Sdim 1243226586Sdim return BaseOffset(); 1244226586Sdim} 1245261991Sdim 1246261991SdimThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment( 1247261991Sdim const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass, 1248261991Sdim FinalOverriders::OverriderInfo Overrider) { 1249226586Sdim // Ignore adjustments for pure virtual member functions. 1250226586Sdim if (Overrider.Method->isPure()) 1251226586Sdim return ThisAdjustment(); 1252341825Sdim 1253341825Sdim BaseSubobject OverriddenBaseSubobject(MD->getParent(), 1254226586Sdim BaseOffsetInLayoutClass); 1255341825Sdim 1256226586Sdim BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(), 1257226586Sdim Overrider.Offset); 1258341825Sdim 1259226586Sdim // Compute the adjustment offset. 1260226586Sdim BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject, 1261226586Sdim OverriderBaseSubobject); 1262226586Sdim if (Offset.isEmpty()) 1263226586Sdim return ThisAdjustment(); 1264226586Sdim 1265226586Sdim ThisAdjustment Adjustment; 1266341825Sdim 1267226586Sdim if (Offset.VirtualBase) { 1268226586Sdim // Get the vcall offset map for this virtual base. 1269226586Sdim VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase]; 1270226586Sdim 1271226586Sdim if (VCallOffsets.empty()) { 1272226586Sdim // We don't have vcall offsets for this virtual base, go ahead and 1273226586Sdim // build them. 1274226586Sdim VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, MostDerivedClass, 1275353358Sdim /*Overriders=*/nullptr, 1276226586Sdim BaseSubobject(Offset.VirtualBase, 1277226586Sdim CharUnits::Zero()), 1278226586Sdim /*BaseIsVirtual=*/true, 1279226586Sdim /*OffsetInLayoutClass=*/ 1280226586Sdim CharUnits::Zero()); 1281341825Sdim 1282226586Sdim VCallOffsets = Builder.getVCallOffsets(); 1283226586Sdim } 1284341825Sdim 1285261991Sdim Adjustment.Virtual.Itanium.VCallOffsetOffset = 1286226586Sdim VCallOffsets.getVCallOffsetOffset(MD).getQuantity(); 1287226586Sdim } 1288226586Sdim 1289226586Sdim // Set the non-virtual part of the adjustment. 1290226586Sdim Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity(); 1291341825Sdim 1292226586Sdim return Adjustment; 1293226586Sdim} 1294261991Sdim 1295261991Sdimvoid ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD, 1296261991Sdim ReturnAdjustment ReturnAdjustment) { 1297226586Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 1298341825Sdim assert(ReturnAdjustment.isEmpty() && 1299226586Sdim "Destructor can't have return adjustment!"); 1300226586Sdim 1301261991Sdim // Add both the complete destructor and the deleting destructor. 1302261991Sdim Components.push_back(VTableComponent::MakeCompleteDtor(DD)); 1303261991Sdim Components.push_back(VTableComponent::MakeDeletingDtor(DD)); 1304226586Sdim } else { 1305226586Sdim // Add the return adjustment if necessary. 1306226586Sdim if (!ReturnAdjustment.isEmpty()) 1307226586Sdim VTableThunks[Components.size()].Return = ReturnAdjustment; 1308226586Sdim 1309226586Sdim // Add the function. 1310226586Sdim Components.push_back(VTableComponent::MakeFunction(MD)); 1311226586Sdim } 1312226586Sdim} 1313226586Sdim 1314226586Sdim/// OverridesIndirectMethodInBase - Return whether the given member function 1315341825Sdim/// overrides any methods in the set of given bases. 1316226586Sdim/// Unlike OverridesMethodInBase, this checks "overriders of overriders". 1317226586Sdim/// For example, if we have: 1318226586Sdim/// 1319226586Sdim/// struct A { virtual void f(); } 1320226586Sdim/// struct B : A { virtual void f(); } 1321226586Sdim/// struct C : B { virtual void f(); } 1322226586Sdim/// 1323341825Sdim/// OverridesIndirectMethodInBase will return true if given C::f as the method 1324226586Sdim/// and { A } as the set of bases. 1325261991Sdimstatic bool OverridesIndirectMethodInBases( 1326261991Sdim const CXXMethodDecl *MD, 1327261991Sdim ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) { 1328226586Sdim if (Bases.count(MD->getParent())) 1329226586Sdim return true; 1330327952Sdim 1331327952Sdim for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) { 1332226586Sdim // Check "indirect overriders". 1333226586Sdim if (OverridesIndirectMethodInBases(OverriddenMD, Bases)) 1334226586Sdim return true; 1335226586Sdim } 1336341825Sdim 1337226586Sdim return false; 1338226586Sdim} 1339226586Sdim 1340261991Sdimbool ItaniumVTableBuilder::IsOverriderUsed( 1341261991Sdim const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass, 1342261991Sdim const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 1343261991Sdim CharUnits FirstBaseOffsetInLayoutClass) const { 1344226586Sdim // If the base and the first base in the primary base chain have the same 1345226586Sdim // offsets, then this overrider will be used. 1346226586Sdim if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass) 1347226586Sdim return true; 1348226586Sdim 1349226586Sdim // We know now that Base (or a direct or indirect base of it) is a primary 1350341825Sdim // base in part of the class hierarchy, but not a primary base in the most 1351226586Sdim // derived class. 1352341825Sdim 1353226586Sdim // If the overrider is the first base in the primary base chain, we know 1354226586Sdim // that the overrider will be used. 1355226586Sdim if (Overrider->getParent() == FirstBaseInPrimaryBaseChain) 1356226586Sdim return true; 1357226586Sdim 1358261991Sdim ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases; 1359261991Sdim 1360226586Sdim const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain; 1361226586Sdim PrimaryBases.insert(RD); 1362226586Sdim 1363226586Sdim // Now traverse the base chain, starting with the first base, until we find 1364226586Sdim // the base that is no longer a primary base. 1365226586Sdim while (true) { 1366226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1367226586Sdim const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 1368341825Sdim 1369226586Sdim if (!PrimaryBase) 1370226586Sdim break; 1371341825Sdim 1372226586Sdim if (Layout.isPrimaryBaseVirtual()) { 1373239462Sdim assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 1374226586Sdim "Primary base should always be at offset 0!"); 1375226586Sdim 1376226586Sdim const ASTRecordLayout &LayoutClassLayout = 1377226586Sdim Context.getASTRecordLayout(LayoutClass); 1378226586Sdim 1379226586Sdim // Now check if this is the primary base that is not a primary base in the 1380226586Sdim // most derived class. 1381226586Sdim if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) != 1382226586Sdim FirstBaseOffsetInLayoutClass) { 1383226586Sdim // We found it, stop walking the chain. 1384226586Sdim break; 1385226586Sdim } 1386226586Sdim } else { 1387239462Sdim assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 1388226586Sdim "Primary base should always be at offset 0!"); 1389226586Sdim } 1390341825Sdim 1391226586Sdim if (!PrimaryBases.insert(PrimaryBase)) 1392226586Sdim llvm_unreachable("Found a duplicate primary base!"); 1393226586Sdim 1394226586Sdim RD = PrimaryBase; 1395226586Sdim } 1396341825Sdim 1397226586Sdim // If the final overrider is an override of one of the primary bases, 1398226586Sdim // then we know that it will be used. 1399226586Sdim return OverridesIndirectMethodInBases(Overrider, PrimaryBases); 1400226586Sdim} 1401226586Sdim 1402261991Sdimtypedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy; 1403261991Sdim 1404226586Sdim/// FindNearestOverriddenMethod - Given a method, returns the overridden method 1405226586Sdim/// from the nearest base. Returns null if no method was found. 1406261991Sdim/// The Bases are expected to be sorted in a base-to-derived order. 1407261991Sdimstatic const CXXMethodDecl * 1408226586SdimFindNearestOverriddenMethod(const CXXMethodDecl *MD, 1409261991Sdim BasesSetVectorTy &Bases) { 1410226586Sdim OverriddenMethodsSetTy OverriddenMethods; 1411226586Sdim ComputeAllOverriddenMethods(MD, OverriddenMethods); 1412226586Sdim 1413296417Sdim for (const CXXRecordDecl *PrimaryBase : 1414296417Sdim llvm::make_range(Bases.rbegin(), Bases.rend())) { 1415261991Sdim // Now check the overridden methods. 1416296417Sdim for (const CXXMethodDecl *OverriddenMD : OverriddenMethods) { 1417226586Sdim // We found our overridden method. 1418226586Sdim if (OverriddenMD->getParent() == PrimaryBase) 1419226586Sdim return OverriddenMD; 1420226586Sdim } 1421226586Sdim } 1422276479Sdim 1423276479Sdim return nullptr; 1424261991Sdim} 1425226586Sdim 1426261991Sdimvoid ItaniumVTableBuilder::AddMethods( 1427261991Sdim BaseSubobject Base, CharUnits BaseOffsetInLayoutClass, 1428261991Sdim const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 1429261991Sdim CharUnits FirstBaseOffsetInLayoutClass, 1430261991Sdim PrimaryBasesSetVectorTy &PrimaryBases) { 1431261991Sdim // Itanium C++ ABI 2.5.2: 1432261991Sdim // The order of the virtual function pointers in a virtual table is the 1433261991Sdim // order of declaration of the corresponding member functions in the class. 1434261991Sdim // 1435261991Sdim // There is an entry for any virtual function declared in a class, 1436261991Sdim // whether it is a new function or overrides a base class function, 1437261991Sdim // unless it overrides a function from the primary base, and conversion 1438261991Sdim // between their return types does not require an adjustment. 1439261991Sdim 1440226586Sdim const CXXRecordDecl *RD = Base.getBase(); 1441226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1442226586Sdim 1443226586Sdim if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 1444226586Sdim CharUnits PrimaryBaseOffset; 1445226586Sdim CharUnits PrimaryBaseOffsetInLayoutClass; 1446226586Sdim if (Layout.isPrimaryBaseVirtual()) { 1447239462Sdim assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 1448226586Sdim "Primary vbase should have a zero offset!"); 1449341825Sdim 1450226586Sdim const ASTRecordLayout &MostDerivedClassLayout = 1451226586Sdim Context.getASTRecordLayout(MostDerivedClass); 1452341825Sdim 1453341825Sdim PrimaryBaseOffset = 1454226586Sdim MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase); 1455341825Sdim 1456226586Sdim const ASTRecordLayout &LayoutClassLayout = 1457226586Sdim Context.getASTRecordLayout(LayoutClass); 1458226586Sdim 1459226586Sdim PrimaryBaseOffsetInLayoutClass = 1460226586Sdim LayoutClassLayout.getVBaseClassOffset(PrimaryBase); 1461226586Sdim } else { 1462239462Sdim assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 1463226586Sdim "Primary base should have a zero offset!"); 1464226586Sdim 1465226586Sdim PrimaryBaseOffset = Base.getBaseOffset(); 1466226586Sdim PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass; 1467226586Sdim } 1468226586Sdim 1469226586Sdim AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset), 1470341825Sdim PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain, 1471226586Sdim FirstBaseOffsetInLayoutClass, PrimaryBases); 1472341825Sdim 1473226586Sdim if (!PrimaryBases.insert(PrimaryBase)) 1474226586Sdim llvm_unreachable("Found a duplicate primary base!"); 1475226586Sdim } 1476226586Sdim 1477276479Sdim const CXXDestructorDecl *ImplicitVirtualDtor = nullptr; 1478261991Sdim 1479261991Sdim typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy; 1480261991Sdim NewVirtualFunctionsTy NewVirtualFunctions; 1481261991Sdim 1482226586Sdim // Now go through all virtual member functions and add them. 1483276479Sdim for (const auto *MD : RD->methods()) { 1484226586Sdim if (!MD->isVirtual()) 1485226586Sdim continue; 1486288943Sdim MD = MD->getCanonicalDecl(); 1487226586Sdim 1488226586Sdim // Get the final overrider. 1489341825Sdim FinalOverriders::OverriderInfo Overrider = 1490226586Sdim Overriders.getOverrider(MD, Base.getBaseOffset()); 1491226586Sdim 1492226586Sdim // Check if this virtual member function overrides a method in a primary 1493226586Sdim // base. If this is the case, and the return type doesn't require adjustment 1494226586Sdim // then we can just use the member function from the primary base. 1495341825Sdim if (const CXXMethodDecl *OverriddenMD = 1496226586Sdim FindNearestOverriddenMethod(MD, PrimaryBases)) { 1497341825Sdim if (ComputeReturnAdjustmentBaseOffset(Context, MD, 1498226586Sdim OverriddenMD).isEmpty()) { 1499226586Sdim // Replace the method info of the overridden method with our own 1500226586Sdim // method. 1501341825Sdim assert(MethodInfoMap.count(OverriddenMD) && 1502226586Sdim "Did not find the overridden method!"); 1503226586Sdim MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD]; 1504341825Sdim 1505226586Sdim MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass, 1506226586Sdim OverriddenMethodInfo.VTableIndex); 1507226586Sdim 1508226586Sdim assert(!MethodInfoMap.count(MD) && 1509226586Sdim "Should not have method info for this method yet!"); 1510341825Sdim 1511226586Sdim MethodInfoMap.insert(std::make_pair(MD, MethodInfo)); 1512226586Sdim MethodInfoMap.erase(OverriddenMD); 1513341825Sdim 1514226586Sdim // If the overridden method exists in a virtual base class or a direct 1515226586Sdim // or indirect base class of a virtual base class, we need to emit a 1516226586Sdim // thunk if we ever have a class hierarchy where the base class is not 1517226586Sdim // a primary base in the complete object. 1518226586Sdim if (!isBuildingConstructorVTable() && OverriddenMD != MD) { 1519226586Sdim // Compute the this adjustment. 1520226586Sdim ThisAdjustment ThisAdjustment = 1521226586Sdim ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass, 1522226586Sdim Overrider); 1523226586Sdim 1524261991Sdim if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset && 1525226586Sdim Overrider.Method->getParent() == MostDerivedClass) { 1526226586Sdim 1527226586Sdim // There's no return adjustment from OverriddenMD and MD, 1528226586Sdim // but that doesn't mean there isn't one between MD and 1529226586Sdim // the final overrider. 1530226586Sdim BaseOffset ReturnAdjustmentOffset = 1531226586Sdim ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD); 1532341825Sdim ReturnAdjustment ReturnAdjustment = 1533226586Sdim ComputeReturnAdjustment(ReturnAdjustmentOffset); 1534226586Sdim 1535226586Sdim // This is a virtual thunk for the most derived class, add it. 1536341825Sdim AddThunk(Overrider.Method, 1537226586Sdim ThunkInfo(ThisAdjustment, ReturnAdjustment)); 1538226586Sdim } 1539226586Sdim } 1540226586Sdim 1541226586Sdim continue; 1542226586Sdim } 1543226586Sdim } 1544226586Sdim 1545261991Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 1546261991Sdim if (MD->isImplicit()) { 1547261991Sdim // Itanium C++ ABI 2.5.2: 1548261991Sdim // If a class has an implicitly-defined virtual destructor, 1549261991Sdim // its entries come after the declared virtual function pointers. 1550261991Sdim 1551261991Sdim assert(!ImplicitVirtualDtor && 1552261991Sdim "Did already see an implicit virtual dtor!"); 1553261991Sdim ImplicitVirtualDtor = DD; 1554261991Sdim continue; 1555261991Sdim } 1556261991Sdim } 1557261991Sdim 1558261991Sdim NewVirtualFunctions.push_back(MD); 1559261991Sdim } 1560261991Sdim 1561261991Sdim if (ImplicitVirtualDtor) 1562261991Sdim NewVirtualFunctions.push_back(ImplicitVirtualDtor); 1563261991Sdim 1564296417Sdim for (const CXXMethodDecl *MD : NewVirtualFunctions) { 1565261991Sdim // Get the final overrider. 1566261991Sdim FinalOverriders::OverriderInfo Overrider = 1567261991Sdim Overriders.getOverrider(MD, Base.getBaseOffset()); 1568261991Sdim 1569226586Sdim // Insert the method info for this method. 1570226586Sdim MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass, 1571226586Sdim Components.size()); 1572226586Sdim 1573226586Sdim assert(!MethodInfoMap.count(MD) && 1574226586Sdim "Should not have method info for this method yet!"); 1575226586Sdim MethodInfoMap.insert(std::make_pair(MD, MethodInfo)); 1576226586Sdim 1577226586Sdim // Check if this overrider is going to be used. 1578226586Sdim const CXXMethodDecl *OverriderMD = Overrider.Method; 1579226586Sdim if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass, 1580341825Sdim FirstBaseInPrimaryBaseChain, 1581226586Sdim FirstBaseOffsetInLayoutClass)) { 1582226586Sdim Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD)); 1583226586Sdim continue; 1584226586Sdim } 1585261991Sdim 1586226586Sdim // Check if this overrider needs a return adjustment. 1587226586Sdim // We don't want to do this for pure virtual member functions. 1588226586Sdim BaseOffset ReturnAdjustmentOffset; 1589226586Sdim if (!OverriderMD->isPure()) { 1590341825Sdim ReturnAdjustmentOffset = 1591226586Sdim ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD); 1592226586Sdim } 1593226586Sdim 1594341825Sdim ReturnAdjustment ReturnAdjustment = 1595226586Sdim ComputeReturnAdjustment(ReturnAdjustmentOffset); 1596341825Sdim 1597226586Sdim AddMethod(Overrider.Method, ReturnAdjustment); 1598226586Sdim } 1599226586Sdim} 1600226586Sdim 1601261991Sdimvoid ItaniumVTableBuilder::LayoutVTable() { 1602226586Sdim LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass, 1603226586Sdim CharUnits::Zero()), 1604226586Sdim /*BaseIsMorallyVirtual=*/false, 1605226586Sdim MostDerivedClassIsVirtual, 1606226586Sdim MostDerivedClassOffset); 1607341825Sdim 1608226586Sdim VisitedVirtualBasesSetTy VBases; 1609341825Sdim 1610226586Sdim // Determine the primary virtual bases. 1611341825Sdim DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset, 1612226586Sdim VBases); 1613226586Sdim VBases.clear(); 1614341825Sdim 1615226586Sdim LayoutVTablesForVirtualBases(MostDerivedClass, VBases); 1616226586Sdim 1617226586Sdim // -fapple-kext adds an extra entry at end of vtbl. 1618234353Sdim bool IsAppleKext = Context.getLangOpts().AppleKext; 1619226586Sdim if (IsAppleKext) 1620226586Sdim Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero())); 1621226586Sdim} 1622261991Sdim 1623261991Sdimvoid ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables( 1624261991Sdim BaseSubobject Base, bool BaseIsMorallyVirtual, 1625261991Sdim bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) { 1626226586Sdim assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!"); 1627226586Sdim 1628314564Sdim unsigned VTableIndex = Components.size(); 1629314564Sdim VTableIndices.push_back(VTableIndex); 1630314564Sdim 1631226586Sdim // Add vcall and vbase offsets for this vtable. 1632226586Sdim VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders, 1633341825Sdim Base, BaseIsVirtualInLayoutClass, 1634226586Sdim OffsetInLayoutClass); 1635226586Sdim Components.append(Builder.components_begin(), Builder.components_end()); 1636341825Sdim 1637226586Sdim // Check if we need to add these vcall offsets. 1638226586Sdim if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) { 1639226586Sdim VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()]; 1640341825Sdim 1641226586Sdim if (VCallOffsets.empty()) 1642226586Sdim VCallOffsets = Builder.getVCallOffsets(); 1643226586Sdim } 1644226586Sdim 1645226586Sdim // If we're laying out the most derived class we want to keep track of the 1646226586Sdim // virtual base class offset offsets. 1647226586Sdim if (Base.getBase() == MostDerivedClass) 1648226586Sdim VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets(); 1649226586Sdim 1650261991Sdim // Add the offset to top. 1651261991Sdim CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass; 1652261991Sdim Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop)); 1653249423Sdim 1654261991Sdim // Next, add the RTTI. 1655261991Sdim Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass)); 1656249423Sdim 1657226586Sdim uint64_t AddressPoint = Components.size(); 1658226586Sdim 1659226586Sdim // Now go through all virtual member functions and add them. 1660226586Sdim PrimaryBasesSetVectorTy PrimaryBases; 1661226586Sdim AddMethods(Base, OffsetInLayoutClass, 1662341825Sdim Base.getBase(), OffsetInLayoutClass, 1663226586Sdim PrimaryBases); 1664226586Sdim 1665261991Sdim const CXXRecordDecl *RD = Base.getBase(); 1666261991Sdim if (RD == MostDerivedClass) { 1667261991Sdim assert(MethodVTableIndices.empty()); 1668296417Sdim for (const auto &I : MethodInfoMap) { 1669296417Sdim const CXXMethodDecl *MD = I.first; 1670296417Sdim const MethodInfo &MI = I.second; 1671261991Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 1672261991Sdim MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)] 1673261991Sdim = MI.VTableIndex - AddressPoint; 1674261991Sdim MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)] 1675261991Sdim = MI.VTableIndex + 1 - AddressPoint; 1676261991Sdim } else { 1677261991Sdim MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint; 1678261991Sdim } 1679261991Sdim } 1680261991Sdim } 1681261991Sdim 1682226586Sdim // Compute 'this' pointer adjustments. 1683226586Sdim ComputeThisAdjustments(); 1684226586Sdim 1685226586Sdim // Add all address points. 1686226586Sdim while (true) { 1687314564Sdim AddressPoints.insert( 1688314564Sdim std::make_pair(BaseSubobject(RD, OffsetInLayoutClass), 1689314564Sdim VTableLayout::AddressPointLocation{ 1690314564Sdim unsigned(VTableIndices.size() - 1), 1691314564Sdim unsigned(AddressPoint - VTableIndex)})); 1692226586Sdim 1693226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1694226586Sdim const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 1695341825Sdim 1696226586Sdim if (!PrimaryBase) 1697226586Sdim break; 1698341825Sdim 1699226586Sdim if (Layout.isPrimaryBaseVirtual()) { 1700226586Sdim // Check if this virtual primary base is a primary base in the layout 1701226586Sdim // class. If it's not, we don't want to add it. 1702226586Sdim const ASTRecordLayout &LayoutClassLayout = 1703226586Sdim Context.getASTRecordLayout(LayoutClass); 1704226586Sdim 1705226586Sdim if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) != 1706226586Sdim OffsetInLayoutClass) { 1707226586Sdim // We don't want to add this class (or any of its primary bases). 1708226586Sdim break; 1709226586Sdim } 1710226586Sdim } 1711226586Sdim 1712226586Sdim RD = PrimaryBase; 1713226586Sdim } 1714226586Sdim 1715226586Sdim // Layout secondary vtables. 1716226586Sdim LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass); 1717226586Sdim} 1718226586Sdim 1719261991Sdimvoid 1720261991SdimItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base, 1721261991Sdim bool BaseIsMorallyVirtual, 1722261991Sdim CharUnits OffsetInLayoutClass) { 1723226586Sdim // Itanium C++ ABI 2.5.2: 1724341825Sdim // Following the primary virtual table of a derived class are secondary 1725226586Sdim // virtual tables for each of its proper base classes, except any primary 1726226586Sdim // base(s) with which it shares its primary virtual table. 1727226586Sdim 1728226586Sdim const CXXRecordDecl *RD = Base.getBase(); 1729226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1730226586Sdim const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 1731341825Sdim 1732276479Sdim for (const auto &B : RD->bases()) { 1733226586Sdim // Ignore virtual bases, we'll emit them later. 1734276479Sdim if (B.isVirtual()) 1735226586Sdim continue; 1736341825Sdim 1737276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 1738226586Sdim 1739226586Sdim // Ignore bases that don't have a vtable. 1740226586Sdim if (!BaseDecl->isDynamicClass()) 1741226586Sdim continue; 1742226586Sdim 1743226586Sdim if (isBuildingConstructorVTable()) { 1744226586Sdim // Itanium C++ ABI 2.6.4: 1745226586Sdim // Some of the base class subobjects may not need construction virtual 1746226586Sdim // tables, which will therefore not be present in the construction 1747226586Sdim // virtual table group, even though the subobject virtual tables are 1748226586Sdim // present in the main virtual table group for the complete object. 1749226586Sdim if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases()) 1750226586Sdim continue; 1751226586Sdim } 1752226586Sdim 1753226586Sdim // Get the base offset of this base. 1754226586Sdim CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl); 1755226586Sdim CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset; 1756341825Sdim 1757341825Sdim CharUnits BaseOffsetInLayoutClass = 1758226586Sdim OffsetInLayoutClass + RelativeBaseOffset; 1759341825Sdim 1760341825Sdim // Don't emit a secondary vtable for a primary base. We might however want 1761226586Sdim // to emit secondary vtables for other bases of this base. 1762226586Sdim if (BaseDecl == PrimaryBase) { 1763226586Sdim LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset), 1764226586Sdim BaseIsMorallyVirtual, BaseOffsetInLayoutClass); 1765226586Sdim continue; 1766226586Sdim } 1767226586Sdim 1768226586Sdim // Layout the primary vtable (and any secondary vtables) for this base. 1769226586Sdim LayoutPrimaryAndSecondaryVTables( 1770226586Sdim BaseSubobject(BaseDecl, BaseOffset), 1771226586Sdim BaseIsMorallyVirtual, 1772226586Sdim /*BaseIsVirtualInLayoutClass=*/false, 1773226586Sdim BaseOffsetInLayoutClass); 1774226586Sdim } 1775226586Sdim} 1776226586Sdim 1777261991Sdimvoid ItaniumVTableBuilder::DeterminePrimaryVirtualBases( 1778261991Sdim const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass, 1779261991Sdim VisitedVirtualBasesSetTy &VBases) { 1780226586Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 1781341825Sdim 1782226586Sdim // Check if this base has a primary base. 1783226586Sdim if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 1784226586Sdim 1785226586Sdim // Check if it's virtual. 1786226586Sdim if (Layout.isPrimaryBaseVirtual()) { 1787226586Sdim bool IsPrimaryVirtualBase = true; 1788226586Sdim 1789226586Sdim if (isBuildingConstructorVTable()) { 1790226586Sdim // Check if the base is actually a primary base in the class we use for 1791226586Sdim // layout. 1792226586Sdim const ASTRecordLayout &LayoutClassLayout = 1793226586Sdim Context.getASTRecordLayout(LayoutClass); 1794226586Sdim 1795226586Sdim CharUnits PrimaryBaseOffsetInLayoutClass = 1796226586Sdim LayoutClassLayout.getVBaseClassOffset(PrimaryBase); 1797341825Sdim 1798341825Sdim // We know that the base is not a primary base in the layout class if 1799226586Sdim // the base offsets are different. 1800226586Sdim if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass) 1801226586Sdim IsPrimaryVirtualBase = false; 1802226586Sdim } 1803341825Sdim 1804226586Sdim if (IsPrimaryVirtualBase) 1805226586Sdim PrimaryVirtualBases.insert(PrimaryBase); 1806226586Sdim } 1807226586Sdim } 1808226586Sdim 1809226586Sdim // Traverse bases, looking for more primary virtual bases. 1810276479Sdim for (const auto &B : RD->bases()) { 1811276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 1812226586Sdim 1813226586Sdim CharUnits BaseOffsetInLayoutClass; 1814341825Sdim 1815276479Sdim if (B.isVirtual()) { 1816280031Sdim if (!VBases.insert(BaseDecl).second) 1817226586Sdim continue; 1818341825Sdim 1819226586Sdim const ASTRecordLayout &LayoutClassLayout = 1820226586Sdim Context.getASTRecordLayout(LayoutClass); 1821226586Sdim 1822341825Sdim BaseOffsetInLayoutClass = 1823226586Sdim LayoutClassLayout.getVBaseClassOffset(BaseDecl); 1824226586Sdim } else { 1825341825Sdim BaseOffsetInLayoutClass = 1826226586Sdim OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl); 1827226586Sdim } 1828226586Sdim 1829226586Sdim DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases); 1830226586Sdim } 1831226586Sdim} 1832226586Sdim 1833261991Sdimvoid ItaniumVTableBuilder::LayoutVTablesForVirtualBases( 1834261991Sdim const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) { 1835226586Sdim // Itanium C++ ABI 2.5.2: 1836226586Sdim // Then come the virtual base virtual tables, also in inheritance graph 1837226586Sdim // order, and again excluding primary bases (which share virtual tables with 1838226586Sdim // the classes for which they are primary). 1839276479Sdim for (const auto &B : RD->bases()) { 1840276479Sdim const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 1841226586Sdim 1842226586Sdim // Check if this base needs a vtable. (If it's virtual, not a primary base 1843226586Sdim // of some other class, and we haven't visited it before). 1844280031Sdim if (B.isVirtual() && BaseDecl->isDynamicClass() && 1845280031Sdim !PrimaryVirtualBases.count(BaseDecl) && 1846280031Sdim VBases.insert(BaseDecl).second) { 1847226586Sdim const ASTRecordLayout &MostDerivedClassLayout = 1848226586Sdim Context.getASTRecordLayout(MostDerivedClass); 1849341825Sdim CharUnits BaseOffset = 1850226586Sdim MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 1851341825Sdim 1852226586Sdim const ASTRecordLayout &LayoutClassLayout = 1853226586Sdim Context.getASTRecordLayout(LayoutClass); 1854341825Sdim CharUnits BaseOffsetInLayoutClass = 1855226586Sdim LayoutClassLayout.getVBaseClassOffset(BaseDecl); 1856226586Sdim 1857226586Sdim LayoutPrimaryAndSecondaryVTables( 1858226586Sdim BaseSubobject(BaseDecl, BaseOffset), 1859226586Sdim /*BaseIsMorallyVirtual=*/true, 1860226586Sdim /*BaseIsVirtualInLayoutClass=*/true, 1861226586Sdim BaseOffsetInLayoutClass); 1862226586Sdim } 1863341825Sdim 1864226586Sdim // We only need to check the base for virtual base vtables if it actually 1865226586Sdim // has virtual bases. 1866226586Sdim if (BaseDecl->getNumVBases()) 1867226586Sdim LayoutVTablesForVirtualBases(BaseDecl, VBases); 1868226586Sdim } 1869226586Sdim} 1870226586Sdim 1871226586Sdim/// dumpLayout - Dump the vtable layout. 1872261991Sdimvoid ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) { 1873261991Sdim // FIXME: write more tests that actually use the dumpLayout output to prevent 1874261991Sdim // ItaniumVTableBuilder regressions. 1875226586Sdim 1876226586Sdim if (isBuildingConstructorVTable()) { 1877226586Sdim Out << "Construction vtable for ('"; 1878276479Sdim MostDerivedClass->printQualifiedName(Out); 1879276479Sdim Out << "', "; 1880226586Sdim Out << MostDerivedClassOffset.getQuantity() << ") in '"; 1881276479Sdim LayoutClass->printQualifiedName(Out); 1882226586Sdim } else { 1883226586Sdim Out << "Vtable for '"; 1884276479Sdim MostDerivedClass->printQualifiedName(Out); 1885226586Sdim } 1886226586Sdim Out << "' (" << Components.size() << " entries).\n"; 1887226586Sdim 1888226586Sdim // Iterate through the address points and insert them into a new map where 1889226586Sdim // they are keyed by the index and not the base object. 1890226586Sdim // Since an address point can be shared by multiple subobjects, we use an 1891226586Sdim // STL multimap. 1892226586Sdim std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex; 1893296417Sdim for (const auto &AP : AddressPoints) { 1894296417Sdim const BaseSubobject &Base = AP.first; 1895314564Sdim uint64_t Index = 1896314564Sdim VTableIndices[AP.second.VTableIndex] + AP.second.AddressPointIndex; 1897296417Sdim 1898226586Sdim AddressPointsByIndex.insert(std::make_pair(Index, Base)); 1899226586Sdim } 1900341825Sdim 1901226586Sdim for (unsigned I = 0, E = Components.size(); I != E; ++I) { 1902226586Sdim uint64_t Index = I; 1903226586Sdim 1904226586Sdim Out << llvm::format("%4d | ", I); 1905226586Sdim 1906226586Sdim const VTableComponent &Component = Components[I]; 1907226586Sdim 1908226586Sdim // Dump the component. 1909226586Sdim switch (Component.getKind()) { 1910226586Sdim 1911226586Sdim case VTableComponent::CK_VCallOffset: 1912226586Sdim Out << "vcall_offset (" 1913341825Sdim << Component.getVCallOffset().getQuantity() 1914226586Sdim << ")"; 1915226586Sdim break; 1916226586Sdim 1917226586Sdim case VTableComponent::CK_VBaseOffset: 1918226586Sdim Out << "vbase_offset (" 1919226586Sdim << Component.getVBaseOffset().getQuantity() 1920226586Sdim << ")"; 1921226586Sdim break; 1922226586Sdim 1923226586Sdim case VTableComponent::CK_OffsetToTop: 1924226586Sdim Out << "offset_to_top (" 1925226586Sdim << Component.getOffsetToTop().getQuantity() 1926226586Sdim << ")"; 1927226586Sdim break; 1928341825Sdim 1929226586Sdim case VTableComponent::CK_RTTI: 1930276479Sdim Component.getRTTIDecl()->printQualifiedName(Out); 1931276479Sdim Out << " RTTI"; 1932226586Sdim break; 1933341825Sdim 1934226586Sdim case VTableComponent::CK_FunctionPointer: { 1935226586Sdim const CXXMethodDecl *MD = Component.getFunctionDecl(); 1936226586Sdim 1937341825Sdim std::string Str = 1938341825Sdim PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 1939226586Sdim MD); 1940226586Sdim Out << Str; 1941226586Sdim if (MD->isPure()) 1942226586Sdim Out << " [pure]"; 1943226586Sdim 1944243830Sdim if (MD->isDeleted()) 1945243830Sdim Out << " [deleted]"; 1946243830Sdim 1947226586Sdim ThunkInfo Thunk = VTableThunks.lookup(I); 1948226586Sdim if (!Thunk.isEmpty()) { 1949226586Sdim // If this function pointer has a return adjustment, dump it. 1950226586Sdim if (!Thunk.Return.isEmpty()) { 1951226586Sdim Out << "\n [return adjustment: "; 1952226586Sdim Out << Thunk.Return.NonVirtual << " non-virtual"; 1953341825Sdim 1954261991Sdim if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) { 1955261991Sdim Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset; 1956226586Sdim Out << " vbase offset offset"; 1957226586Sdim } 1958226586Sdim 1959226586Sdim Out << ']'; 1960226586Sdim } 1961226586Sdim 1962226586Sdim // If this function pointer has a 'this' pointer adjustment, dump it. 1963226586Sdim if (!Thunk.This.isEmpty()) { 1964226586Sdim Out << "\n [this adjustment: "; 1965226586Sdim Out << Thunk.This.NonVirtual << " non-virtual"; 1966341825Sdim 1967261991Sdim if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 1968261991Sdim Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 1969226586Sdim Out << " vcall offset offset"; 1970226586Sdim } 1971226586Sdim 1972226586Sdim Out << ']'; 1973341825Sdim } 1974226586Sdim } 1975226586Sdim 1976226586Sdim break; 1977226586Sdim } 1978226586Sdim 1979341825Sdim case VTableComponent::CK_CompleteDtorPointer: 1980226586Sdim case VTableComponent::CK_DeletingDtorPointer: { 1981341825Sdim bool IsComplete = 1982226586Sdim Component.getKind() == VTableComponent::CK_CompleteDtorPointer; 1983341825Sdim 1984226586Sdim const CXXDestructorDecl *DD = Component.getDestructorDecl(); 1985341825Sdim 1986276479Sdim DD->printQualifiedName(Out); 1987226586Sdim if (IsComplete) 1988226586Sdim Out << "() [complete]"; 1989226586Sdim else 1990226586Sdim Out << "() [deleting]"; 1991226586Sdim 1992226586Sdim if (DD->isPure()) 1993226586Sdim Out << " [pure]"; 1994226586Sdim 1995226586Sdim ThunkInfo Thunk = VTableThunks.lookup(I); 1996226586Sdim if (!Thunk.isEmpty()) { 1997226586Sdim // If this destructor has a 'this' pointer adjustment, dump it. 1998226586Sdim if (!Thunk.This.isEmpty()) { 1999226586Sdim Out << "\n [this adjustment: "; 2000226586Sdim Out << Thunk.This.NonVirtual << " non-virtual"; 2001341825Sdim 2002261991Sdim if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 2003261991Sdim Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 2004226586Sdim Out << " vcall offset offset"; 2005226586Sdim } 2006341825Sdim 2007226586Sdim Out << ']'; 2008341825Sdim } 2009341825Sdim } 2010226586Sdim 2011226586Sdim break; 2012226586Sdim } 2013226586Sdim 2014226586Sdim case VTableComponent::CK_UnusedFunctionPointer: { 2015226586Sdim const CXXMethodDecl *MD = Component.getUnusedFunctionDecl(); 2016226586Sdim 2017341825Sdim std::string Str = 2018341825Sdim PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 2019226586Sdim MD); 2020226586Sdim Out << "[unused] " << Str; 2021226586Sdim if (MD->isPure()) 2022226586Sdim Out << " [pure]"; 2023226586Sdim } 2024226586Sdim 2025226586Sdim } 2026226586Sdim 2027226586Sdim Out << '\n'; 2028341825Sdim 2029226586Sdim // Dump the next address point. 2030226586Sdim uint64_t NextIndex = Index + 1; 2031226586Sdim if (AddressPointsByIndex.count(NextIndex)) { 2032226586Sdim if (AddressPointsByIndex.count(NextIndex) == 1) { 2033341825Sdim const BaseSubobject &Base = 2034226586Sdim AddressPointsByIndex.find(NextIndex)->second; 2035341825Sdim 2036276479Sdim Out << " -- ("; 2037276479Sdim Base.getBase()->printQualifiedName(Out); 2038226586Sdim Out << ", " << Base.getBaseOffset().getQuantity(); 2039226586Sdim Out << ") vtable address --\n"; 2040226586Sdim } else { 2041226586Sdim CharUnits BaseOffset = 2042226586Sdim AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset(); 2043341825Sdim 2044226586Sdim // We store the class names in a set to get a stable order. 2045226586Sdim std::set<std::string> ClassNames; 2046296417Sdim for (const auto &I : 2047296417Sdim llvm::make_range(AddressPointsByIndex.equal_range(NextIndex))) { 2048296417Sdim assert(I.second.getBaseOffset() == BaseOffset && 2049226586Sdim "Invalid base offset!"); 2050296417Sdim const CXXRecordDecl *RD = I.second.getBase(); 2051226586Sdim ClassNames.insert(RD->getQualifiedNameAsString()); 2052226586Sdim } 2053296417Sdim 2054296417Sdim for (const std::string &Name : ClassNames) { 2055296417Sdim Out << " -- (" << Name; 2056226586Sdim Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n"; 2057226586Sdim } 2058226586Sdim } 2059226586Sdim } 2060226586Sdim } 2061226586Sdim 2062226586Sdim Out << '\n'; 2063341825Sdim 2064226586Sdim if (isBuildingConstructorVTable()) 2065226586Sdim return; 2066341825Sdim 2067226586Sdim if (MostDerivedClass->getNumVBases()) { 2068226586Sdim // We store the virtual base class names and their offsets in a map to get 2069226586Sdim // a stable order. 2070226586Sdim 2071226586Sdim std::map<std::string, CharUnits> ClassNamesAndOffsets; 2072296417Sdim for (const auto &I : VBaseOffsetOffsets) { 2073296417Sdim std::string ClassName = I.first->getQualifiedNameAsString(); 2074296417Sdim CharUnits OffsetOffset = I.second; 2075296417Sdim ClassNamesAndOffsets.insert(std::make_pair(ClassName, OffsetOffset)); 2076226586Sdim } 2077341825Sdim 2078226586Sdim Out << "Virtual base offset offsets for '"; 2079276479Sdim MostDerivedClass->printQualifiedName(Out); 2080276479Sdim Out << "' ("; 2081226586Sdim Out << ClassNamesAndOffsets.size(); 2082226586Sdim Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n"; 2083226586Sdim 2084296417Sdim for (const auto &I : ClassNamesAndOffsets) 2085296417Sdim Out << " " << I.first << " | " << I.second.getQuantity() << '\n'; 2086226586Sdim 2087226586Sdim Out << "\n"; 2088226586Sdim } 2089341825Sdim 2090226586Sdim if (!Thunks.empty()) { 2091226586Sdim // We store the method names in a map to get a stable order. 2092226586Sdim std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls; 2093296417Sdim 2094296417Sdim for (const auto &I : Thunks) { 2095296417Sdim const CXXMethodDecl *MD = I.first; 2096341825Sdim std::string MethodName = 2097226586Sdim PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 2098226586Sdim MD); 2099341825Sdim 2100226586Sdim MethodNamesAndDecls.insert(std::make_pair(MethodName, MD)); 2101226586Sdim } 2102226586Sdim 2103296417Sdim for (const auto &I : MethodNamesAndDecls) { 2104296417Sdim const std::string &MethodName = I.first; 2105296417Sdim const CXXMethodDecl *MD = I.second; 2106226586Sdim 2107226586Sdim ThunkInfoVectorTy ThunksVector = Thunks[MD]; 2108344779Sdim llvm::sort(ThunksVector, [](const ThunkInfo &LHS, const ThunkInfo &RHS) { 2109276479Sdim assert(LHS.Method == nullptr && RHS.Method == nullptr); 2110276479Sdim return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return); 2111276479Sdim }); 2112226586Sdim 2113226586Sdim Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size(); 2114226586Sdim Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n"; 2115341825Sdim 2116226586Sdim for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) { 2117226586Sdim const ThunkInfo &Thunk = ThunksVector[I]; 2118226586Sdim 2119226586Sdim Out << llvm::format("%4d | ", I); 2120341825Sdim 2121226586Sdim // If this function pointer has a return pointer adjustment, dump it. 2122226586Sdim if (!Thunk.Return.isEmpty()) { 2123261991Sdim Out << "return adjustment: " << Thunk.Return.NonVirtual; 2124226586Sdim Out << " non-virtual"; 2125261991Sdim if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) { 2126261991Sdim Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset; 2127226586Sdim Out << " vbase offset offset"; 2128226586Sdim } 2129226586Sdim 2130226586Sdim if (!Thunk.This.isEmpty()) 2131226586Sdim Out << "\n "; 2132226586Sdim } 2133226586Sdim 2134226586Sdim // If this function pointer has a 'this' pointer adjustment, dump it. 2135226586Sdim if (!Thunk.This.isEmpty()) { 2136226586Sdim Out << "this adjustment: "; 2137226586Sdim Out << Thunk.This.NonVirtual << " non-virtual"; 2138341825Sdim 2139261991Sdim if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 2140261991Sdim Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 2141226586Sdim Out << " vcall offset offset"; 2142226586Sdim } 2143226586Sdim } 2144341825Sdim 2145226586Sdim Out << '\n'; 2146226586Sdim } 2147341825Sdim 2148226586Sdim Out << '\n'; 2149226586Sdim } 2150226586Sdim } 2151226586Sdim 2152226586Sdim // Compute the vtable indices for all the member functions. 2153226586Sdim // Store them in a map keyed by the index so we'll get a sorted table. 2154226586Sdim std::map<uint64_t, std::string> IndicesMap; 2155226586Sdim 2156276479Sdim for (const auto *MD : MostDerivedClass->methods()) { 2157226586Sdim // We only want virtual member functions. 2158226586Sdim if (!MD->isVirtual()) 2159226586Sdim continue; 2160288943Sdim MD = MD->getCanonicalDecl(); 2161226586Sdim 2162226586Sdim std::string MethodName = 2163226586Sdim PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 2164226586Sdim MD); 2165226586Sdim 2166226586Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 2167261991Sdim GlobalDecl GD(DD, Dtor_Complete); 2168261991Sdim assert(MethodVTableIndices.count(GD)); 2169261991Sdim uint64_t VTableIndex = MethodVTableIndices[GD]; 2170261991Sdim IndicesMap[VTableIndex] = MethodName + " [complete]"; 2171261991Sdim IndicesMap[VTableIndex + 1] = MethodName + " [deleting]"; 2172226586Sdim } else { 2173261991Sdim assert(MethodVTableIndices.count(MD)); 2174261991Sdim IndicesMap[MethodVTableIndices[MD]] = MethodName; 2175226586Sdim } 2176226586Sdim } 2177226586Sdim 2178226586Sdim // Print the vtable indices for all the member functions. 2179226586Sdim if (!IndicesMap.empty()) { 2180226586Sdim Out << "VTable indices for '"; 2181276479Sdim MostDerivedClass->printQualifiedName(Out); 2182226586Sdim Out << "' (" << IndicesMap.size() << " entries).\n"; 2183226586Sdim 2184296417Sdim for (const auto &I : IndicesMap) { 2185296417Sdim uint64_t VTableIndex = I.first; 2186296417Sdim const std::string &MethodName = I.second; 2187226586Sdim 2188261991Sdim Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName 2189234353Sdim << '\n'; 2190226586Sdim } 2191226586Sdim } 2192226586Sdim 2193226586Sdim Out << '\n'; 2194226586Sdim} 2195226586Sdim} 2196226586Sdim 2197314564SdimVTableLayout::VTableLayout(ArrayRef<size_t> VTableIndices, 2198314564Sdim ArrayRef<VTableComponent> VTableComponents, 2199314564Sdim ArrayRef<VTableThunkTy> VTableThunks, 2200314564Sdim const AddressPointsMapTy &AddressPoints) 2201314564Sdim : VTableComponents(VTableComponents), VTableThunks(VTableThunks), 2202314564Sdim AddressPoints(AddressPoints) { 2203314564Sdim if (VTableIndices.size() <= 1) 2204314564Sdim assert(VTableIndices.size() == 1 && VTableIndices[0] == 0); 2205314564Sdim else 2206314564Sdim this->VTableIndices = OwningArrayRef<size_t>(VTableIndices); 2207314564Sdim 2208344779Sdim llvm::sort(this->VTableThunks, [](const VTableLayout::VTableThunkTy &LHS, 2209344779Sdim const VTableLayout::VTableThunkTy &RHS) { 2210344779Sdim assert((LHS.first != RHS.first || LHS.second == RHS.second) && 2211344779Sdim "Different thunks should have unique indices!"); 2212344779Sdim return LHS.first < RHS.first; 2213344779Sdim }); 2214226586Sdim} 2215226586Sdim 2216234982SdimVTableLayout::~VTableLayout() { } 2217226586Sdim 2218261991SdimItaniumVTableContext::ItaniumVTableContext(ASTContext &Context) 2219276479Sdim : VTableContextBase(/*MS=*/false) {} 2220249423Sdim 2221314564SdimItaniumVTableContext::~ItaniumVTableContext() {} 2222226586Sdim 2223261991Sdimuint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) { 2224341825Sdim GD = GD.getCanonicalDecl(); 2225226586Sdim MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD); 2226226586Sdim if (I != MethodVTableIndices.end()) 2227226586Sdim return I->second; 2228341825Sdim 2229226586Sdim const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent(); 2230226586Sdim 2231261991Sdim computeVTableRelatedInformation(RD); 2232226586Sdim 2233226586Sdim I = MethodVTableIndices.find(GD); 2234226586Sdim assert(I != MethodVTableIndices.end() && "Did not find index!"); 2235226586Sdim return I->second; 2236226586Sdim} 2237226586Sdim 2238261991SdimCharUnits 2239261991SdimItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD, 2240261991Sdim const CXXRecordDecl *VBase) { 2241226586Sdim ClassPairTy ClassPair(RD, VBase); 2242341825Sdim 2243341825Sdim VirtualBaseClassOffsetOffsetsMapTy::iterator I = 2244226586Sdim VirtualBaseClassOffsetOffsets.find(ClassPair); 2245226586Sdim if (I != VirtualBaseClassOffsetOffsets.end()) 2246226586Sdim return I->second; 2247276479Sdim 2248353358Sdim VCallAndVBaseOffsetBuilder Builder(RD, RD, /*Overriders=*/nullptr, 2249226586Sdim BaseSubobject(RD, CharUnits::Zero()), 2250226586Sdim /*BaseIsVirtual=*/false, 2251226586Sdim /*OffsetInLayoutClass=*/CharUnits::Zero()); 2252226586Sdim 2253296417Sdim for (const auto &I : Builder.getVBaseOffsetOffsets()) { 2254226586Sdim // Insert all types. 2255296417Sdim ClassPairTy ClassPair(RD, I.first); 2256296417Sdim 2257296417Sdim VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second)); 2258226586Sdim } 2259341825Sdim 2260226586Sdim I = VirtualBaseClassOffsetOffsets.find(ClassPair); 2261226586Sdim assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!"); 2262341825Sdim 2263226586Sdim return I->second; 2264226586Sdim} 2265226586Sdim 2266314564Sdimstatic std::unique_ptr<VTableLayout> 2267314564SdimCreateVTableLayout(const ItaniumVTableBuilder &Builder) { 2268226586Sdim SmallVector<VTableLayout::VTableThunkTy, 1> 2269226586Sdim VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end()); 2270226586Sdim 2271360784Sdim return std::make_unique<VTableLayout>( 2272314564Sdim Builder.VTableIndices, Builder.vtable_components(), VTableThunks, 2273314564Sdim Builder.getAddressPoints()); 2274226586Sdim} 2275226586Sdim 2276261991Sdimvoid 2277261991SdimItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) { 2278314564Sdim std::unique_ptr<const VTableLayout> &Entry = VTableLayouts[RD]; 2279226586Sdim 2280226586Sdim // Check if we've computed this information before. 2281226586Sdim if (Entry) 2282226586Sdim return; 2283226586Sdim 2284261991Sdim ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(), 2285261991Sdim /*MostDerivedClassIsVirtual=*/0, RD); 2286226586Sdim Entry = CreateVTableLayout(Builder); 2287226586Sdim 2288261991Sdim MethodVTableIndices.insert(Builder.vtable_indices_begin(), 2289261991Sdim Builder.vtable_indices_end()); 2290261991Sdim 2291226586Sdim // Add the known thunks. 2292226586Sdim Thunks.insert(Builder.thunks_begin(), Builder.thunks_end()); 2293226586Sdim 2294226586Sdim // If we don't have the vbase information for this class, insert it. 2295226586Sdim // getVirtualBaseOffsetOffset will compute it separately without computing 2296226586Sdim // the rest of the vtable related information. 2297226586Sdim if (!RD->getNumVBases()) 2298226586Sdim return; 2299341825Sdim 2300261991Sdim const CXXRecordDecl *VBase = 2301261991Sdim RD->vbases_begin()->getType()->getAsCXXRecordDecl(); 2302341825Sdim 2303226586Sdim if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase))) 2304226586Sdim return; 2305261991Sdim 2306296417Sdim for (const auto &I : Builder.getVBaseOffsetOffsets()) { 2307226586Sdim // Insert all types. 2308296417Sdim ClassPairTy ClassPair(RD, I.first); 2309296417Sdim 2310296417Sdim VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second)); 2311226586Sdim } 2312226586Sdim} 2313226586Sdim 2314314564Sdimstd::unique_ptr<VTableLayout> 2315314564SdimItaniumVTableContext::createConstructionVTableLayout( 2316261991Sdim const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset, 2317261991Sdim bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) { 2318261991Sdim ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset, 2319261991Sdim MostDerivedClassIsVirtual, LayoutClass); 2320261991Sdim return CreateVTableLayout(Builder); 2321249423Sdim} 2322249423Sdim 2323261991Sdimnamespace { 2324261991Sdim 2325261991Sdim// Vtables in the Microsoft ABI are different from the Itanium ABI. 2326261991Sdim// 2327261991Sdim// The main differences are: 2328261991Sdim// 1. Separate vftable and vbtable. 2329261991Sdim// 2330261991Sdim// 2. Each subobject with a vfptr gets its own vftable rather than an address 2331261991Sdim// point in a single vtable shared between all the subobjects. 2332261991Sdim// Each vftable is represented by a separate section and virtual calls 2333261991Sdim// must be done using the vftable which has a slot for the function to be 2334261991Sdim// called. 2335261991Sdim// 2336261991Sdim// 3. Virtual method definitions expect their 'this' parameter to point to the 2337261991Sdim// first vfptr whose table provides a compatible overridden method. In many 2338261991Sdim// cases, this permits the original vf-table entry to directly call 2339261991Sdim// the method instead of passing through a thunk. 2340280031Sdim// See example before VFTableBuilder::ComputeThisOffset below. 2341261991Sdim// 2342261991Sdim// A compatible overridden method is one which does not have a non-trivial 2343261991Sdim// covariant-return adjustment. 2344261991Sdim// 2345261991Sdim// The first vfptr is the one with the lowest offset in the complete-object 2346261991Sdim// layout of the defining class, and the method definition will subtract 2347261991Sdim// that constant offset from the parameter value to get the real 'this' 2348261991Sdim// value. Therefore, if the offset isn't really constant (e.g. if a virtual 2349261991Sdim// function defined in a virtual base is overridden in a more derived 2350261991Sdim// virtual base and these bases have a reverse order in the complete 2351261991Sdim// object), the vf-table may require a this-adjustment thunk. 2352261991Sdim// 2353261991Sdim// 4. vftables do not contain new entries for overrides that merely require 2354261991Sdim// this-adjustment. Together with #3, this keeps vf-tables smaller and 2355261991Sdim// eliminates the need for this-adjustment thunks in many cases, at the cost 2356261991Sdim// of often requiring redundant work to adjust the "this" pointer. 2357261991Sdim// 2358261991Sdim// 5. Instead of VTT and constructor vtables, vbtables and vtordisps are used. 2359261991Sdim// Vtordisps are emitted into the class layout if a class has 2360261991Sdim// a) a user-defined ctor/dtor 2361261991Sdim// and 2362261991Sdim// b) a method overriding a method in a virtual base. 2363280031Sdim// 2364280031Sdim// To get a better understanding of this code, 2365280031Sdim// you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp 2366261991Sdim 2367261991Sdimclass VFTableBuilder { 2368261991Sdimpublic: 2369261991Sdim typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation> 2370261991Sdim MethodVFTableLocationsTy; 2371261991Sdim 2372276479Sdim typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator> 2373276479Sdim method_locations_range; 2374276479Sdim 2375261991Sdimprivate: 2376261991Sdim /// VTables - Global vtable information. 2377261991Sdim MicrosoftVTableContext &VTables; 2378261991Sdim 2379261991Sdim /// Context - The ASTContext which we will use for layout information. 2380261991Sdim ASTContext &Context; 2381261991Sdim 2382261991Sdim /// MostDerivedClass - The most derived class for which we're building this 2383261991Sdim /// vtable. 2384261991Sdim const CXXRecordDecl *MostDerivedClass; 2385261991Sdim 2386261991Sdim const ASTRecordLayout &MostDerivedClassLayout; 2387261991Sdim 2388276479Sdim const VPtrInfo &WhichVFPtr; 2389261991Sdim 2390261991Sdim /// FinalOverriders - The final overriders of the most derived class. 2391261991Sdim const FinalOverriders Overriders; 2392261991Sdim 2393261991Sdim /// Components - The components of the vftable being built. 2394261991Sdim SmallVector<VTableComponent, 64> Components; 2395261991Sdim 2396261991Sdim MethodVFTableLocationsTy MethodVFTableLocations; 2397261991Sdim 2398341825Sdim /// Does this class have an RTTI component? 2399309124Sdim bool HasRTTIComponent = false; 2400276479Sdim 2401261991Sdim /// MethodInfo - Contains information about a method in a vtable. 2402261991Sdim /// (Used for computing 'this' pointer adjustment thunks. 2403261991Sdim struct MethodInfo { 2404261991Sdim /// VBTableIndex - The nonzero index in the vbtable that 2405261991Sdim /// this method's base has, or zero. 2406261991Sdim const uint64_t VBTableIndex; 2407261991Sdim 2408261991Sdim /// VFTableIndex - The index in the vftable that this method has. 2409261991Sdim const uint64_t VFTableIndex; 2410261991Sdim 2411261991Sdim /// Shadowed - Indicates if this vftable slot is shadowed by 2412261991Sdim /// a slot for a covariant-return override. If so, it shouldn't be printed 2413261991Sdim /// or used for vcalls in the most derived class. 2414261991Sdim bool Shadowed; 2415261991Sdim 2416280031Sdim /// UsesExtraSlot - Indicates if this vftable slot was created because 2417280031Sdim /// any of the overridden slots required a return adjusting thunk. 2418280031Sdim bool UsesExtraSlot; 2419280031Sdim 2420280031Sdim MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex, 2421280031Sdim bool UsesExtraSlot = false) 2422261991Sdim : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex), 2423280031Sdim Shadowed(false), UsesExtraSlot(UsesExtraSlot) {} 2424261991Sdim 2425280031Sdim MethodInfo() 2426280031Sdim : VBTableIndex(0), VFTableIndex(0), Shadowed(false), 2427280031Sdim UsesExtraSlot(false) {} 2428261991Sdim }; 2429261991Sdim 2430261991Sdim typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy; 2431261991Sdim 2432261991Sdim /// MethodInfoMap - The information for all methods in the vftable we're 2433261991Sdim /// currently building. 2434261991Sdim MethodInfoMapTy MethodInfoMap; 2435261991Sdim 2436261991Sdim typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy; 2437261991Sdim 2438261991Sdim /// VTableThunks - The thunks by vftable index in the vftable currently being 2439261991Sdim /// built. 2440261991Sdim VTableThunksMapTy VTableThunks; 2441261991Sdim 2442261991Sdim typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 2443261991Sdim typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 2444261991Sdim 2445261991Sdim /// Thunks - A map that contains all the thunks needed for all methods in the 2446261991Sdim /// most derived class for which the vftable is currently being built. 2447261991Sdim ThunksMapTy Thunks; 2448261991Sdim 2449261991Sdim /// AddThunk - Add a thunk for the given method. 2450261991Sdim void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) { 2451261991Sdim SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD]; 2452261991Sdim 2453261991Sdim // Check if we have this thunk already. 2454353358Sdim if (llvm::find(ThunksVector, Thunk) != ThunksVector.end()) 2455261991Sdim return; 2456261991Sdim 2457261991Sdim ThunksVector.push_back(Thunk); 2458261991Sdim } 2459261991Sdim 2460261991Sdim /// ComputeThisOffset - Returns the 'this' argument offset for the given 2461276479Sdim /// method, relative to the beginning of the MostDerivedClass. 2462276479Sdim CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider); 2463261991Sdim 2464261991Sdim void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider, 2465261991Sdim CharUnits ThisOffset, ThisAdjustment &TA); 2466261991Sdim 2467261991Sdim /// AddMethod - Add a single virtual member function to the vftable 2468261991Sdim /// components vector. 2469261991Sdim void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) { 2470276479Sdim if (!TI.isEmpty()) { 2471276479Sdim VTableThunks[Components.size()] = TI; 2472276479Sdim AddThunk(MD, TI); 2473276479Sdim } 2474261991Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 2475261991Sdim assert(TI.Return.isEmpty() && 2476261991Sdim "Destructor can't have return adjustment!"); 2477261991Sdim Components.push_back(VTableComponent::MakeDeletingDtor(DD)); 2478261991Sdim } else { 2479261991Sdim Components.push_back(VTableComponent::MakeFunction(MD)); 2480261991Sdim } 2481261991Sdim } 2482261991Sdim 2483261991Sdim /// AddMethods - Add the methods of this base subobject and the relevant 2484261991Sdim /// subbases to the vftable we're currently laying out. 2485261991Sdim void AddMethods(BaseSubobject Base, unsigned BaseDepth, 2486261991Sdim const CXXRecordDecl *LastVBase, 2487261991Sdim BasesSetVectorTy &VisitedBases); 2488261991Sdim 2489261991Sdim void LayoutVFTable() { 2490280031Sdim // RTTI data goes before all other entries. 2491280031Sdim if (HasRTTIComponent) 2492280031Sdim Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass)); 2493261991Sdim 2494261991Sdim BasesSetVectorTy VisitedBases; 2495276479Sdim AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr, 2496261991Sdim VisitedBases); 2497280031Sdim assert((HasRTTIComponent ? Components.size() - 1 : Components.size()) && 2498280031Sdim "vftable can't be empty"); 2499261991Sdim 2500261991Sdim assert(MethodVFTableLocations.empty()); 2501296417Sdim for (const auto &I : MethodInfoMap) { 2502296417Sdim const CXXMethodDecl *MD = I.first; 2503296417Sdim const MethodInfo &MI = I.second; 2504341825Sdim assert(MD == MD->getCanonicalDecl()); 2505341825Sdim 2506261991Sdim // Skip the methods that the MostDerivedClass didn't override 2507261991Sdim // and the entries shadowed by return adjusting thunks. 2508261991Sdim if (MD->getParent() != MostDerivedClass || MI.Shadowed) 2509261991Sdim continue; 2510276479Sdim MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(), 2511276479Sdim WhichVFPtr.NonVirtualOffset, MI.VFTableIndex); 2512261991Sdim if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 2513261991Sdim MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc; 2514261991Sdim } else { 2515261991Sdim MethodVFTableLocations[MD] = Loc; 2516261991Sdim } 2517261991Sdim } 2518261991Sdim } 2519261991Sdim 2520261991Sdimpublic: 2521261991Sdim VFTableBuilder(MicrosoftVTableContext &VTables, 2522314564Sdim const CXXRecordDecl *MostDerivedClass, const VPtrInfo &Which) 2523261991Sdim : VTables(VTables), 2524261991Sdim Context(MostDerivedClass->getASTContext()), 2525261991Sdim MostDerivedClass(MostDerivedClass), 2526261991Sdim MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)), 2527314564Sdim WhichVFPtr(Which), 2528261991Sdim Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) { 2529309124Sdim // Provide the RTTI component if RTTIData is enabled. If the vftable would 2530309124Sdim // be available externally, we should not provide the RTTI componenent. It 2531309124Sdim // is currently impossible to get available externally vftables with either 2532309124Sdim // dllimport or extern template instantiations, but eventually we may add a 2533309124Sdim // flag to support additional devirtualization that needs this. 2534309124Sdim if (Context.getLangOpts().RTTIData) 2535309124Sdim HasRTTIComponent = true; 2536276479Sdim 2537261991Sdim LayoutVFTable(); 2538261991Sdim 2539261991Sdim if (Context.getLangOpts().DumpVTableLayouts) 2540261991Sdim dumpLayout(llvm::outs()); 2541261991Sdim } 2542261991Sdim 2543261991Sdim uint64_t getNumThunks() const { return Thunks.size(); } 2544261991Sdim 2545261991Sdim ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); } 2546261991Sdim 2547261991Sdim ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); } 2548261991Sdim 2549276479Sdim method_locations_range vtable_locations() const { 2550276479Sdim return method_locations_range(MethodVFTableLocations.begin(), 2551276479Sdim MethodVFTableLocations.end()); 2552261991Sdim } 2553261991Sdim 2554314564Sdim ArrayRef<VTableComponent> vtable_components() const { return Components; } 2555261991Sdim 2556261991Sdim VTableThunksMapTy::const_iterator vtable_thunks_begin() const { 2557261991Sdim return VTableThunks.begin(); 2558261991Sdim } 2559261991Sdim 2560261991Sdim VTableThunksMapTy::const_iterator vtable_thunks_end() const { 2561261991Sdim return VTableThunks.end(); 2562261991Sdim } 2563261991Sdim 2564261991Sdim void dumpLayout(raw_ostream &); 2565261991Sdim}; 2566261991Sdim 2567288943Sdim} // end namespace 2568288943Sdim 2569280031Sdim// Let's study one class hierarchy as an example: 2570280031Sdim// struct A { 2571280031Sdim// virtual void f(); 2572280031Sdim// int x; 2573280031Sdim// }; 2574280031Sdim// 2575280031Sdim// struct B : virtual A { 2576280031Sdim// virtual void f(); 2577280031Sdim// }; 2578280031Sdim// 2579280031Sdim// Record layouts: 2580280031Sdim// struct A: 2581280031Sdim// 0 | (A vftable pointer) 2582280031Sdim// 4 | int x 2583280031Sdim// 2584280031Sdim// struct B: 2585280031Sdim// 0 | (B vbtable pointer) 2586280031Sdim// 4 | struct A (virtual base) 2587280031Sdim// 4 | (A vftable pointer) 2588280031Sdim// 8 | int x 2589280031Sdim// 2590280031Sdim// Let's assume we have a pointer to the A part of an object of dynamic type B: 2591280031Sdim// B b; 2592280031Sdim// A *a = (A*)&b; 2593280031Sdim// a->f(); 2594280031Sdim// 2595280031Sdim// In this hierarchy, f() belongs to the vftable of A, so B::f() expects 2596280031Sdim// "this" parameter to point at the A subobject, which is B+4. 2597280031Sdim// In the B::f() prologue, it adjusts "this" back to B by subtracting 4, 2598280031Sdim// performed as a *static* adjustment. 2599280031Sdim// 2600280031Sdim// Interesting thing happens when we alter the relative placement of A and B 2601280031Sdim// subobjects in a class: 2602280031Sdim// struct C : virtual B { }; 2603280031Sdim// 2604280031Sdim// C c; 2605280031Sdim// A *a = (A*)&c; 2606280031Sdim// a->f(); 2607280031Sdim// 2608280031Sdim// Respective record layout is: 2609280031Sdim// 0 | (C vbtable pointer) 2610280031Sdim// 4 | struct A (virtual base) 2611280031Sdim// 4 | (A vftable pointer) 2612280031Sdim// 8 | int x 2613280031Sdim// 12 | struct B (virtual base) 2614280031Sdim// 12 | (B vbtable pointer) 2615280031Sdim// 2616280031Sdim// The final overrider of f() in class C is still B::f(), so B+4 should be 2617280031Sdim// passed as "this" to that code. However, "a" points at B-8, so the respective 2618280031Sdim// vftable entry should hold a thunk that adds 12 to the "this" argument before 2619280031Sdim// performing a tail call to B::f(). 2620280031Sdim// 2621280031Sdim// With this example in mind, we can now calculate the 'this' argument offset 2622280031Sdim// for the given method, relative to the beginning of the MostDerivedClass. 2623261991SdimCharUnits 2624276479SdimVFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) { 2625296417Sdim BasesSetVectorTy Bases; 2626261991Sdim 2627296417Sdim { 2628296417Sdim // Find the set of least derived bases that define the given method. 2629296417Sdim OverriddenMethodsSetTy VisitedOverriddenMethods; 2630296417Sdim auto InitialOverriddenDefinitionCollector = [&]( 2631296417Sdim const CXXMethodDecl *OverriddenMD) { 2632296417Sdim if (OverriddenMD->size_overridden_methods() == 0) 2633296417Sdim Bases.insert(OverriddenMD->getParent()); 2634296417Sdim // Don't recurse on this method if we've already collected it. 2635296417Sdim return VisitedOverriddenMethods.insert(OverriddenMD).second; 2636296417Sdim }; 2637296417Sdim visitAllOverriddenMethods(Overrider.Method, 2638296417Sdim InitialOverriddenDefinitionCollector); 2639296417Sdim } 2640296417Sdim 2641276479Sdim // If there are no overrides then 'this' is located 2642276479Sdim // in the base that defines the method. 2643296417Sdim if (Bases.size() == 0) 2644276479Sdim return Overrider.Offset; 2645276479Sdim 2646261991Sdim CXXBasePaths Paths; 2647296417Sdim Overrider.Method->getParent()->lookupInBases( 2648296417Sdim [&Bases](const CXXBaseSpecifier *Specifier, CXXBasePath &) { 2649296417Sdim return Bases.count(Specifier->getType()->getAsCXXRecordDecl()); 2650296417Sdim }, 2651296417Sdim Paths); 2652261991Sdim 2653261991Sdim // This will hold the smallest this offset among overridees of MD. 2654261991Sdim // This implies that an offset of a non-virtual base will dominate an offset 2655261991Sdim // of a virtual base to potentially reduce the number of thunks required 2656261991Sdim // in the derived classes that inherit this method. 2657261991Sdim CharUnits Ret; 2658261991Sdim bool First = true; 2659261991Sdim 2660276479Sdim const ASTRecordLayout &OverriderRDLayout = 2661276479Sdim Context.getASTRecordLayout(Overrider.Method->getParent()); 2662296417Sdim for (const CXXBasePath &Path : Paths) { 2663276479Sdim CharUnits ThisOffset = Overrider.Offset; 2664261991Sdim CharUnits LastVBaseOffset; 2665261991Sdim 2666288943Sdim // For each path from the overrider to the parents of the overridden 2667288943Sdim // methods, traverse the path, calculating the this offset in the most 2668288943Sdim // derived class. 2669296417Sdim for (const CXXBasePathElement &Element : Path) { 2670261991Sdim QualType CurTy = Element.Base->getType(); 2671261991Sdim const CXXRecordDecl *PrevRD = Element.Class, 2672261991Sdim *CurRD = CurTy->getAsCXXRecordDecl(); 2673261991Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD); 2674261991Sdim 2675261991Sdim if (Element.Base->isVirtual()) { 2676276479Sdim // The interesting things begin when you have virtual inheritance. 2677276479Sdim // The final overrider will use a static adjustment equal to the offset 2678276479Sdim // of the vbase in the final overrider class. 2679276479Sdim // For example, if the final overrider is in a vbase B of the most 2680276479Sdim // derived class and it overrides a method of the B's own vbase A, 2681276479Sdim // it uses A* as "this". In its prologue, it can cast A* to B* with 2682276479Sdim // a static offset. This offset is used regardless of the actual 2683276479Sdim // offset of A from B in the most derived class, requiring an 2684276479Sdim // this-adjusting thunk in the vftable if A and B are laid out 2685276479Sdim // differently in the most derived class. 2686276479Sdim LastVBaseOffset = ThisOffset = 2687276479Sdim Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD); 2688261991Sdim } else { 2689261991Sdim ThisOffset += Layout.getBaseClassOffset(CurRD); 2690261991Sdim } 2691261991Sdim } 2692261991Sdim 2693276479Sdim if (isa<CXXDestructorDecl>(Overrider.Method)) { 2694261991Sdim if (LastVBaseOffset.isZero()) { 2695261991Sdim // If a "Base" class has at least one non-virtual base with a virtual 2696261991Sdim // destructor, the "Base" virtual destructor will take the address 2697261991Sdim // of the "Base" subobject as the "this" argument. 2698276479Sdim ThisOffset = Overrider.Offset; 2699261991Sdim } else { 2700261991Sdim // A virtual destructor of a virtual base takes the address of the 2701261991Sdim // virtual base subobject as the "this" argument. 2702276479Sdim ThisOffset = LastVBaseOffset; 2703261991Sdim } 2704261991Sdim } 2705261991Sdim 2706261991Sdim if (Ret > ThisOffset || First) { 2707261991Sdim First = false; 2708261991Sdim Ret = ThisOffset; 2709261991Sdim } 2710261991Sdim } 2711261991Sdim 2712261991Sdim assert(!First && "Method not found in the given subobject?"); 2713261991Sdim return Ret; 2714261991Sdim} 2715261991Sdim 2716280031Sdim// Things are getting even more complex when the "this" adjustment has to 2717280031Sdim// use a dynamic offset instead of a static one, or even two dynamic offsets. 2718280031Sdim// This is sometimes required when a virtual call happens in the middle of 2719280031Sdim// a non-most-derived class construction or destruction. 2720280031Sdim// 2721280031Sdim// Let's take a look at the following example: 2722280031Sdim// struct A { 2723280031Sdim// virtual void f(); 2724280031Sdim// }; 2725280031Sdim// 2726280031Sdim// void foo(A *a) { a->f(); } // Knows nothing about siblings of A. 2727280031Sdim// 2728280031Sdim// struct B : virtual A { 2729280031Sdim// virtual void f(); 2730280031Sdim// B() { 2731280031Sdim// foo(this); 2732280031Sdim// } 2733280031Sdim// }; 2734280031Sdim// 2735280031Sdim// struct C : virtual B { 2736280031Sdim// virtual void f(); 2737280031Sdim// }; 2738280031Sdim// 2739280031Sdim// Record layouts for these classes are: 2740280031Sdim// struct A 2741280031Sdim// 0 | (A vftable pointer) 2742280031Sdim// 2743280031Sdim// struct B 2744280031Sdim// 0 | (B vbtable pointer) 2745280031Sdim// 4 | (vtordisp for vbase A) 2746280031Sdim// 8 | struct A (virtual base) 2747280031Sdim// 8 | (A vftable pointer) 2748280031Sdim// 2749280031Sdim// struct C 2750280031Sdim// 0 | (C vbtable pointer) 2751280031Sdim// 4 | (vtordisp for vbase A) 2752280031Sdim// 8 | struct A (virtual base) // A precedes B! 2753280031Sdim// 8 | (A vftable pointer) 2754280031Sdim// 12 | struct B (virtual base) 2755280031Sdim// 12 | (B vbtable pointer) 2756280031Sdim// 2757280031Sdim// When one creates an object of type C, the C constructor: 2758280031Sdim// - initializes all the vbptrs, then 2759280031Sdim// - calls the A subobject constructor 2760280031Sdim// (initializes A's vfptr with an address of A vftable), then 2761280031Sdim// - calls the B subobject constructor 2762280031Sdim// (initializes A's vfptr with an address of B vftable and vtordisp for A), 2763280031Sdim// that in turn calls foo(), then 2764280031Sdim// - initializes A's vfptr with an address of C vftable and zeroes out the 2765280031Sdim// vtordisp 2766280031Sdim// FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable 2767280031Sdim// without vtordisp thunks? 2768280031Sdim// FIXME: how are vtordisp handled in the presence of nooverride/final? 2769280031Sdim// 2770280031Sdim// When foo() is called, an object with a layout of class C has a vftable 2771280031Sdim// referencing B::f() that assumes a B layout, so the "this" adjustments are 2772280031Sdim// incorrect, unless an extra adjustment is done. This adjustment is called 2773280031Sdim// "vtordisp adjustment". Vtordisp basically holds the difference between the 2774280031Sdim// actual location of a vbase in the layout class and the location assumed by 2775280031Sdim// the vftable of the class being constructed/destructed. Vtordisp is only 2776280031Sdim// needed if "this" escapes a 2777280031Sdim// structor (or we can't prove otherwise). 2778280031Sdim// [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an 2779280031Sdim// estimation of a dynamic adjustment] 2780280031Sdim// 2781280031Sdim// foo() gets a pointer to the A vbase and doesn't know anything about B or C, 2782280031Sdim// so it just passes that pointer as "this" in a virtual call. 2783280031Sdim// If there was no vtordisp, that would just dispatch to B::f(). 2784280031Sdim// However, B::f() assumes B+8 is passed as "this", 2785280031Sdim// yet the pointer foo() passes along is B-4 (i.e. C+8). 2786280031Sdim// An extra adjustment is needed, so we emit a thunk into the B vftable. 2787280031Sdim// This vtordisp thunk subtracts the value of vtordisp 2788280031Sdim// from the "this" argument (-12) before making a tailcall to B::f(). 2789280031Sdim// 2790280031Sdim// Let's consider an even more complex example: 2791280031Sdim// struct D : virtual B, virtual C { 2792280031Sdim// D() { 2793280031Sdim// foo(this); 2794280031Sdim// } 2795280031Sdim// }; 2796280031Sdim// 2797280031Sdim// struct D 2798280031Sdim// 0 | (D vbtable pointer) 2799280031Sdim// 4 | (vtordisp for vbase A) 2800280031Sdim// 8 | struct A (virtual base) // A precedes both B and C! 2801280031Sdim// 8 | (A vftable pointer) 2802280031Sdim// 12 | struct B (virtual base) // B precedes C! 2803280031Sdim// 12 | (B vbtable pointer) 2804280031Sdim// 16 | struct C (virtual base) 2805280031Sdim// 16 | (C vbtable pointer) 2806280031Sdim// 2807280031Sdim// When D::D() calls foo(), we find ourselves in a thunk that should tailcall 2808280031Sdim// to C::f(), which assumes C+8 as its "this" parameter. This time, foo() 2809280031Sdim// passes along A, which is C-8. The A vtordisp holds 2810280031Sdim// "D.vbptr[index_of_A] - offset_of_A_in_D" 2811280031Sdim// and we statically know offset_of_A_in_D, so can get a pointer to D. 2812280031Sdim// When we know it, we can make an extra vbtable lookup to locate the C vbase 2813280031Sdim// and one extra static adjustment to calculate the expected value of C+8. 2814261991Sdimvoid VFTableBuilder::CalculateVtordispAdjustment( 2815261991Sdim FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset, 2816261991Sdim ThisAdjustment &TA) { 2817261991Sdim const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap = 2818261991Sdim MostDerivedClassLayout.getVBaseOffsetsMap(); 2819261991Sdim const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry = 2820276479Sdim VBaseMap.find(WhichVFPtr.getVBaseWithVPtr()); 2821261991Sdim assert(VBaseMapEntry != VBaseMap.end()); 2822261991Sdim 2823276479Sdim // If there's no vtordisp or the final overrider is defined in the same vbase 2824276479Sdim // as the initial declaration, we don't need any vtordisp adjustment. 2825276479Sdim if (!VBaseMapEntry->second.hasVtorDisp() || 2826276479Sdim Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr()) 2827261991Sdim return; 2828261991Sdim 2829276479Sdim // OK, now we know we need to use a vtordisp thunk. 2830276479Sdim // The implicit vtordisp field is located right before the vbase. 2831280031Sdim CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset; 2832261991Sdim TA.Virtual.Microsoft.VtordispOffset = 2833280031Sdim (OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4; 2834261991Sdim 2835276479Sdim // A simple vtordisp thunk will suffice if the final overrider is defined 2836276479Sdim // in either the most derived class or its non-virtual base. 2837276479Sdim if (Overrider.Method->getParent() == MostDerivedClass || 2838276479Sdim !Overrider.VirtualBase) 2839261991Sdim return; 2840261991Sdim 2841261991Sdim // Otherwise, we need to do use the dynamic offset of the final overrider 2842261991Sdim // in order to get "this" adjustment right. 2843261991Sdim TA.Virtual.Microsoft.VBPtrOffset = 2844280031Sdim (OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset - 2845261991Sdim MostDerivedClassLayout.getVBPtrOffset()).getQuantity(); 2846261991Sdim TA.Virtual.Microsoft.VBOffsetOffset = 2847261991Sdim Context.getTypeSizeInChars(Context.IntTy).getQuantity() * 2848276479Sdim VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase); 2849261991Sdim 2850261991Sdim TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity(); 2851261991Sdim} 2852261991Sdim 2853261991Sdimstatic void GroupNewVirtualOverloads( 2854261991Sdim const CXXRecordDecl *RD, 2855261991Sdim SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) { 2856261991Sdim // Put the virtual methods into VirtualMethods in the proper order: 2857261991Sdim // 1) Group overloads by declaration name. New groups are added to the 2858261991Sdim // vftable in the order of their first declarations in this class 2859296417Sdim // (including overrides, non-virtual methods and any other named decl that 2860296417Sdim // might be nested within the class). 2861261991Sdim // 2) In each group, new overloads appear in the reverse order of declaration. 2862261991Sdim typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup; 2863261991Sdim SmallVector<MethodGroup, 10> Groups; 2864261991Sdim typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy; 2865261991Sdim VisitedGroupIndicesTy VisitedGroupIndices; 2866296417Sdim for (const auto *D : RD->decls()) { 2867296417Sdim const auto *ND = dyn_cast<NamedDecl>(D); 2868296417Sdim if (!ND) 2869296417Sdim continue; 2870261991Sdim VisitedGroupIndicesTy::iterator J; 2871261991Sdim bool Inserted; 2872276479Sdim std::tie(J, Inserted) = VisitedGroupIndices.insert( 2873296417Sdim std::make_pair(ND->getDeclName(), Groups.size())); 2874261991Sdim if (Inserted) 2875276479Sdim Groups.push_back(MethodGroup()); 2876296417Sdim if (const auto *MD = dyn_cast<CXXMethodDecl>(ND)) 2877296417Sdim if (MD->isVirtual()) 2878296417Sdim Groups[J->second].push_back(MD->getCanonicalDecl()); 2879261991Sdim } 2880261991Sdim 2881296417Sdim for (const MethodGroup &Group : Groups) 2882296417Sdim VirtualMethods.append(Group.rbegin(), Group.rend()); 2883261991Sdim} 2884261991Sdim 2885276479Sdimstatic bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) { 2886276479Sdim for (const auto &B : RD->bases()) { 2887276479Sdim if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base) 2888276479Sdim return true; 2889276479Sdim } 2890276479Sdim return false; 2891276479Sdim} 2892276479Sdim 2893261991Sdimvoid VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth, 2894261991Sdim const CXXRecordDecl *LastVBase, 2895261991Sdim BasesSetVectorTy &VisitedBases) { 2896261991Sdim const CXXRecordDecl *RD = Base.getBase(); 2897261991Sdim if (!RD->isPolymorphic()) 2898261991Sdim return; 2899261991Sdim 2900261991Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 2901261991Sdim 2902261991Sdim // See if this class expands a vftable of the base we look at, which is either 2903288943Sdim // the one defined by the vfptr base path or the primary base of the current 2904288943Sdim // class. 2905276479Sdim const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase; 2906261991Sdim CharUnits NextBaseOffset; 2907314564Sdim if (BaseDepth < WhichVFPtr.PathToIntroducingObject.size()) { 2908314564Sdim NextBase = WhichVFPtr.PathToIntroducingObject[BaseDepth]; 2909276479Sdim if (isDirectVBase(NextBase, RD)) { 2910261991Sdim NextLastVBase = NextBase; 2911261991Sdim NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase); 2912261991Sdim } else { 2913261991Sdim NextBaseOffset = 2914261991Sdim Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase); 2915261991Sdim } 2916261991Sdim } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 2917261991Sdim assert(!Layout.isPrimaryBaseVirtual() && 2918261991Sdim "No primary virtual bases in this ABI"); 2919261991Sdim NextBase = PrimaryBase; 2920261991Sdim NextBaseOffset = Base.getBaseOffset(); 2921261991Sdim } 2922261991Sdim 2923261991Sdim if (NextBase) { 2924261991Sdim AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1, 2925261991Sdim NextLastVBase, VisitedBases); 2926261991Sdim if (!VisitedBases.insert(NextBase)) 2927261991Sdim llvm_unreachable("Found a duplicate primary base!"); 2928261991Sdim } 2929261991Sdim 2930261991Sdim SmallVector<const CXXMethodDecl*, 10> VirtualMethods; 2931261991Sdim // Put virtual methods in the proper order. 2932261991Sdim GroupNewVirtualOverloads(RD, VirtualMethods); 2933261991Sdim 2934261991Sdim // Now go through all virtual member functions and add them to the current 2935261991Sdim // vftable. This is done by 2936261991Sdim // - replacing overridden methods in their existing slots, as long as they 2937261991Sdim // don't require return adjustment; calculating This adjustment if needed. 2938261991Sdim // - adding new slots for methods of the current base not present in any 2939261991Sdim // sub-bases; 2940261991Sdim // - adding new slots for methods that require Return adjustment. 2941261991Sdim // We keep track of the methods visited in the sub-bases in MethodInfoMap. 2942296417Sdim for (const CXXMethodDecl *MD : VirtualMethods) { 2943280031Sdim FinalOverriders::OverriderInfo FinalOverrider = 2944261991Sdim Overriders.getOverrider(MD, Base.getBaseOffset()); 2945280031Sdim const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method; 2946276479Sdim const CXXMethodDecl *OverriddenMD = 2947276479Sdim FindNearestOverriddenMethod(MD, VisitedBases); 2948276479Sdim 2949261991Sdim ThisAdjustment ThisAdjustmentOffset; 2950280031Sdim bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false; 2951280031Sdim CharUnits ThisOffset = ComputeThisOffset(FinalOverrider); 2952276479Sdim ThisAdjustmentOffset.NonVirtual = 2953276479Sdim (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity(); 2954280031Sdim if ((OverriddenMD || FinalOverriderMD != MD) && 2955276479Sdim WhichVFPtr.getVBaseWithVPtr()) 2956280031Sdim CalculateVtordispAdjustment(FinalOverrider, ThisOffset, 2957280031Sdim ThisAdjustmentOffset); 2958261991Sdim 2959327952Sdim unsigned VBIndex = 2960327952Sdim LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0; 2961327952Sdim 2962276479Sdim if (OverriddenMD) { 2963288943Sdim // If MD overrides anything in this vftable, we need to update the 2964288943Sdim // entries. 2965261991Sdim MethodInfoMapTy::iterator OverriddenMDIterator = 2966261991Sdim MethodInfoMap.find(OverriddenMD); 2967261991Sdim 2968261991Sdim // If the overridden method went to a different vftable, skip it. 2969261991Sdim if (OverriddenMDIterator == MethodInfoMap.end()) 2970261991Sdim continue; 2971261991Sdim 2972261991Sdim MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second; 2973261991Sdim 2974327952Sdim VBIndex = OverriddenMethodInfo.VBTableIndex; 2975327952Sdim 2976280031Sdim // Let's check if the overrider requires any return adjustments. 2977280031Sdim // We must create a new slot if the MD's return type is not trivially 2978280031Sdim // convertible to the OverriddenMD's one. 2979280031Sdim // Once a chain of method overrides adds a return adjusting vftable slot, 2980280031Sdim // all subsequent overrides will also use an extra method slot. 2981280031Sdim ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset( 2982280031Sdim Context, MD, OverriddenMD).isEmpty() || 2983280031Sdim OverriddenMethodInfo.UsesExtraSlot; 2984280031Sdim 2985280031Sdim if (!ReturnAdjustingThunk) { 2986261991Sdim // No return adjustment needed - just replace the overridden method info 2987261991Sdim // with the current info. 2988327952Sdim MethodInfo MI(VBIndex, OverriddenMethodInfo.VFTableIndex); 2989261991Sdim MethodInfoMap.erase(OverriddenMDIterator); 2990261991Sdim 2991261991Sdim assert(!MethodInfoMap.count(MD) && 2992261991Sdim "Should not have method info for this method yet!"); 2993261991Sdim MethodInfoMap.insert(std::make_pair(MD, MI)); 2994261991Sdim continue; 2995276479Sdim } 2996261991Sdim 2997276479Sdim // In case we need a return adjustment, we'll add a new slot for 2998341825Sdim // the overrider. Mark the overridden method as shadowed by the new slot. 2999276479Sdim OverriddenMethodInfo.Shadowed = true; 3000276479Sdim 3001276479Sdim // Force a special name mangling for a return-adjusting thunk 3002276479Sdim // unless the method is the final overrider without this adjustment. 3003280031Sdim ForceReturnAdjustmentMangling = 3004280031Sdim !(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty()); 3005276479Sdim } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC || 3006261991Sdim MD->size_overridden_methods()) { 3007261991Sdim // Skip methods that don't belong to the vftable of the current class, 3008261991Sdim // e.g. each method that wasn't seen in any of the visited sub-bases 3009261991Sdim // but overrides multiple methods of other sub-bases. 3010261991Sdim continue; 3011261991Sdim } 3012261991Sdim 3013261991Sdim // If we got here, MD is a method not seen in any of the sub-bases or 3014261991Sdim // it requires return adjustment. Insert the method info for this method. 3015276479Sdim MethodInfo MI(VBIndex, 3016280031Sdim HasRTTIComponent ? Components.size() - 1 : Components.size(), 3017280031Sdim ReturnAdjustingThunk); 3018261991Sdim 3019261991Sdim assert(!MethodInfoMap.count(MD) && 3020261991Sdim "Should not have method info for this method yet!"); 3021261991Sdim MethodInfoMap.insert(std::make_pair(MD, MI)); 3022261991Sdim 3023261991Sdim // Check if this overrider needs a return adjustment. 3024261991Sdim // We don't want to do this for pure virtual member functions. 3025261991Sdim BaseOffset ReturnAdjustmentOffset; 3026261991Sdim ReturnAdjustment ReturnAdjustment; 3027280031Sdim if (!FinalOverriderMD->isPure()) { 3028261991Sdim ReturnAdjustmentOffset = 3029280031Sdim ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD); 3030261991Sdim } 3031261991Sdim if (!ReturnAdjustmentOffset.isEmpty()) { 3032280031Sdim ForceReturnAdjustmentMangling = true; 3033261991Sdim ReturnAdjustment.NonVirtual = 3034261991Sdim ReturnAdjustmentOffset.NonVirtualOffset.getQuantity(); 3035261991Sdim if (ReturnAdjustmentOffset.VirtualBase) { 3036261991Sdim const ASTRecordLayout &DerivedLayout = 3037261991Sdim Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass); 3038261991Sdim ReturnAdjustment.Virtual.Microsoft.VBPtrOffset = 3039261991Sdim DerivedLayout.getVBPtrOffset().getQuantity(); 3040261991Sdim ReturnAdjustment.Virtual.Microsoft.VBIndex = 3041261991Sdim VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass, 3042261991Sdim ReturnAdjustmentOffset.VirtualBase); 3043261991Sdim } 3044261991Sdim } 3045261991Sdim 3046280031Sdim AddMethod(FinalOverriderMD, 3047280031Sdim ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment, 3048280031Sdim ForceReturnAdjustmentMangling ? MD : nullptr)); 3049261991Sdim } 3050261991Sdim} 3051261991Sdim 3052276479Sdimstatic void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) { 3053296417Sdim for (const CXXRecordDecl *Elem : 3054296417Sdim llvm::make_range(Path.rbegin(), Path.rend())) { 3055276479Sdim Out << "'"; 3056296417Sdim Elem->printQualifiedName(Out); 3057276479Sdim Out << "' in "; 3058261991Sdim } 3059261991Sdim} 3060261991Sdim 3061261991Sdimstatic void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out, 3062261991Sdim bool ContinueFirstLine) { 3063261991Sdim const ReturnAdjustment &R = TI.Return; 3064261991Sdim bool Multiline = false; 3065276479Sdim const char *LinePrefix = "\n "; 3066276479Sdim if (!R.isEmpty() || TI.Method) { 3067261991Sdim if (!ContinueFirstLine) 3068261991Sdim Out << LinePrefix; 3069276479Sdim Out << "[return adjustment (to type '" 3070276479Sdim << TI.Method->getReturnType().getCanonicalType().getAsString() 3071276479Sdim << "'): "; 3072261991Sdim if (R.Virtual.Microsoft.VBPtrOffset) 3073261991Sdim Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", "; 3074261991Sdim if (R.Virtual.Microsoft.VBIndex) 3075261991Sdim Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", "; 3076261991Sdim Out << R.NonVirtual << " non-virtual]"; 3077261991Sdim Multiline = true; 3078261991Sdim } 3079261991Sdim 3080261991Sdim const ThisAdjustment &T = TI.This; 3081261991Sdim if (!T.isEmpty()) { 3082261991Sdim if (Multiline || !ContinueFirstLine) 3083261991Sdim Out << LinePrefix; 3084261991Sdim Out << "[this adjustment: "; 3085261991Sdim if (!TI.This.Virtual.isEmpty()) { 3086261991Sdim assert(T.Virtual.Microsoft.VtordispOffset < 0); 3087261991Sdim Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", "; 3088261991Sdim if (T.Virtual.Microsoft.VBPtrOffset) { 3089261991Sdim Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset 3090276479Sdim << " to the left,"; 3091261991Sdim assert(T.Virtual.Microsoft.VBOffsetOffset > 0); 3092261991Sdim Out << LinePrefix << " vboffset at " 3093261991Sdim << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, "; 3094261991Sdim } 3095261991Sdim } 3096261991Sdim Out << T.NonVirtual << " non-virtual]"; 3097261991Sdim } 3098261991Sdim} 3099261991Sdim 3100261991Sdimvoid VFTableBuilder::dumpLayout(raw_ostream &Out) { 3101261991Sdim Out << "VFTable for "; 3102314564Sdim PrintBasePath(WhichVFPtr.PathToIntroducingObject, Out); 3103276479Sdim Out << "'"; 3104276479Sdim MostDerivedClass->printQualifiedName(Out); 3105276479Sdim Out << "' (" << Components.size() 3106276479Sdim << (Components.size() == 1 ? " entry" : " entries") << ").\n"; 3107261991Sdim 3108261991Sdim for (unsigned I = 0, E = Components.size(); I != E; ++I) { 3109261991Sdim Out << llvm::format("%4d | ", I); 3110261991Sdim 3111261991Sdim const VTableComponent &Component = Components[I]; 3112261991Sdim 3113261991Sdim // Dump the component. 3114261991Sdim switch (Component.getKind()) { 3115261991Sdim case VTableComponent::CK_RTTI: 3116276479Sdim Component.getRTTIDecl()->printQualifiedName(Out); 3117276479Sdim Out << " RTTI"; 3118261991Sdim break; 3119261991Sdim 3120261991Sdim case VTableComponent::CK_FunctionPointer: { 3121261991Sdim const CXXMethodDecl *MD = Component.getFunctionDecl(); 3122261991Sdim 3123276479Sdim // FIXME: Figure out how to print the real thunk type, since they can 3124276479Sdim // differ in the return type. 3125261991Sdim std::string Str = PredefinedExpr::ComputeName( 3126261991Sdim PredefinedExpr::PrettyFunctionNoVirtual, MD); 3127261991Sdim Out << Str; 3128261991Sdim if (MD->isPure()) 3129261991Sdim Out << " [pure]"; 3130261991Sdim 3131280031Sdim if (MD->isDeleted()) 3132261991Sdim Out << " [deleted]"; 3133261991Sdim 3134261991Sdim ThunkInfo Thunk = VTableThunks.lookup(I); 3135261991Sdim if (!Thunk.isEmpty()) 3136261991Sdim dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false); 3137261991Sdim 3138261991Sdim break; 3139261991Sdim } 3140261991Sdim 3141261991Sdim case VTableComponent::CK_DeletingDtorPointer: { 3142261991Sdim const CXXDestructorDecl *DD = Component.getDestructorDecl(); 3143261991Sdim 3144276479Sdim DD->printQualifiedName(Out); 3145261991Sdim Out << "() [scalar deleting]"; 3146261991Sdim 3147261991Sdim if (DD->isPure()) 3148261991Sdim Out << " [pure]"; 3149261991Sdim 3150261991Sdim ThunkInfo Thunk = VTableThunks.lookup(I); 3151261991Sdim if (!Thunk.isEmpty()) { 3152261991Sdim assert(Thunk.Return.isEmpty() && 3153261991Sdim "No return adjustment needed for destructors!"); 3154261991Sdim dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false); 3155261991Sdim } 3156261991Sdim 3157261991Sdim break; 3158261991Sdim } 3159261991Sdim 3160261991Sdim default: 3161261991Sdim DiagnosticsEngine &Diags = Context.getDiagnostics(); 3162261991Sdim unsigned DiagID = Diags.getCustomDiagID( 3163261991Sdim DiagnosticsEngine::Error, 3164261991Sdim "Unexpected vftable component type %0 for component number %1"); 3165261991Sdim Diags.Report(MostDerivedClass->getLocation(), DiagID) 3166261991Sdim << I << Component.getKind(); 3167261991Sdim } 3168261991Sdim 3169261991Sdim Out << '\n'; 3170261991Sdim } 3171261991Sdim 3172261991Sdim Out << '\n'; 3173261991Sdim 3174261991Sdim if (!Thunks.empty()) { 3175261991Sdim // We store the method names in a map to get a stable order. 3176261991Sdim std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls; 3177261991Sdim 3178296417Sdim for (const auto &I : Thunks) { 3179296417Sdim const CXXMethodDecl *MD = I.first; 3180261991Sdim std::string MethodName = PredefinedExpr::ComputeName( 3181261991Sdim PredefinedExpr::PrettyFunctionNoVirtual, MD); 3182261991Sdim 3183261991Sdim MethodNamesAndDecls.insert(std::make_pair(MethodName, MD)); 3184261991Sdim } 3185261991Sdim 3186296417Sdim for (const auto &MethodNameAndDecl : MethodNamesAndDecls) { 3187296417Sdim const std::string &MethodName = MethodNameAndDecl.first; 3188296417Sdim const CXXMethodDecl *MD = MethodNameAndDecl.second; 3189261991Sdim 3190261991Sdim ThunkInfoVectorTy ThunksVector = Thunks[MD]; 3191353358Sdim llvm::stable_sort(ThunksVector, [](const ThunkInfo &LHS, 3192353358Sdim const ThunkInfo &RHS) { 3193276479Sdim // Keep different thunks with the same adjustments in the order they 3194276479Sdim // were put into the vector. 3195276479Sdim return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return); 3196276479Sdim }); 3197261991Sdim 3198261991Sdim Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size(); 3199261991Sdim Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n"; 3200261991Sdim 3201261991Sdim for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) { 3202261991Sdim const ThunkInfo &Thunk = ThunksVector[I]; 3203261991Sdim 3204261991Sdim Out << llvm::format("%4d | ", I); 3205261991Sdim dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true); 3206261991Sdim Out << '\n'; 3207261991Sdim } 3208261991Sdim 3209261991Sdim Out << '\n'; 3210261991Sdim } 3211261991Sdim } 3212276479Sdim 3213276479Sdim Out.flush(); 3214261991Sdim} 3215276479Sdim 3216276479Sdimstatic bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A, 3217280031Sdim ArrayRef<const CXXRecordDecl *> B) { 3218296417Sdim for (const CXXRecordDecl *Decl : B) { 3219296417Sdim if (A.count(Decl)) 3220276479Sdim return true; 3221276479Sdim } 3222276479Sdim return false; 3223261991Sdim} 3224261991Sdim 3225276479Sdimstatic bool rebucketPaths(VPtrInfoVector &Paths); 3226261991Sdim 3227276479Sdim/// Produces MSVC-compatible vbtable data. The symbols produced by this 3228276479Sdim/// algorithm match those produced by MSVC 2012 and newer, which is different 3229276479Sdim/// from MSVC 2010. 3230276479Sdim/// 3231276479Sdim/// MSVC 2012 appears to minimize the vbtable names using the following 3232276479Sdim/// algorithm. First, walk the class hierarchy in the usual order, depth first, 3233276479Sdim/// left to right, to find all of the subobjects which contain a vbptr field. 3234276479Sdim/// Visiting each class node yields a list of inheritance paths to vbptrs. Each 3235276479Sdim/// record with a vbptr creates an initially empty path. 3236276479Sdim/// 3237276479Sdim/// To combine paths from child nodes, the paths are compared to check for 3238276479Sdim/// ambiguity. Paths are "ambiguous" if multiple paths have the same set of 3239276479Sdim/// components in the same order. Each group of ambiguous paths is extended by 3240276479Sdim/// appending the class of the base from which it came. If the current class 3241276479Sdim/// node produced an ambiguous path, its path is extended with the current class. 3242276479Sdim/// After extending paths, MSVC again checks for ambiguity, and extends any 3243276479Sdim/// ambiguous path which wasn't already extended. Because each node yields an 3244276479Sdim/// unambiguous set of paths, MSVC doesn't need to extend any path more than once 3245276479Sdim/// to produce an unambiguous set of paths. 3246276479Sdim/// 3247276479Sdim/// TODO: Presumably vftables use the same algorithm. 3248276479Sdimvoid MicrosoftVTableContext::computeVTablePaths(bool ForVBTables, 3249276479Sdim const CXXRecordDecl *RD, 3250276479Sdim VPtrInfoVector &Paths) { 3251276479Sdim assert(Paths.empty()); 3252276479Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 3253261991Sdim 3254276479Sdim // Base case: this subobject has its own vptr. 3255276479Sdim if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr()) 3256360784Sdim Paths.push_back(std::make_unique<VPtrInfo>(RD)); 3257261991Sdim 3258276479Sdim // Recursive case: get all the vbtables from our bases and remove anything 3259276479Sdim // that shares a virtual base. 3260276479Sdim llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen; 3261276479Sdim for (const auto &B : RD->bases()) { 3262276479Sdim const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl(); 3263276479Sdim if (B.isVirtual() && VBasesSeen.count(Base)) 3264276479Sdim continue; 3265276479Sdim 3266276479Sdim if (!Base->isDynamicClass()) 3267276479Sdim continue; 3268276479Sdim 3269276479Sdim const VPtrInfoVector &BasePaths = 3270276479Sdim ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base); 3271276479Sdim 3272314564Sdim for (const std::unique_ptr<VPtrInfo> &BaseInfo : BasePaths) { 3273276479Sdim // Don't include the path if it goes through a virtual base that we've 3274276479Sdim // already included. 3275276479Sdim if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases)) 3276261991Sdim continue; 3277261991Sdim 3278276479Sdim // Copy the path and adjust it as necessary. 3279360784Sdim auto P = std::make_unique<VPtrInfo>(*BaseInfo); 3280261991Sdim 3281276479Sdim // We mangle Base into the path if the path would've been ambiguous and it 3282276479Sdim // wasn't already extended with Base. 3283276479Sdim if (P->MangledPath.empty() || P->MangledPath.back() != Base) 3284276479Sdim P->NextBaseToMangle = Base; 3285261991Sdim 3286276479Sdim // Keep track of which vtable the derived class is going to extend with 3287276479Sdim // new methods or bases. We append to either the vftable of our primary 3288276479Sdim // base, or the first non-virtual base that has a vbtable. 3289314564Sdim if (P->ObjectWithVPtr == Base && 3290276479Sdim Base == (ForVBTables ? Layout.getBaseSharingVBPtr() 3291276479Sdim : Layout.getPrimaryBase())) 3292314564Sdim P->ObjectWithVPtr = RD; 3293261991Sdim 3294276479Sdim // Keep track of the full adjustment from the MDC to this vtable. The 3295276479Sdim // adjustment is captured by an optional vbase and a non-virtual offset. 3296276479Sdim if (B.isVirtual()) 3297276479Sdim P->ContainingVBases.push_back(Base); 3298276479Sdim else if (P->ContainingVBases.empty()) 3299276479Sdim P->NonVirtualOffset += Layout.getBaseClassOffset(Base); 3300261991Sdim 3301276479Sdim // Update the full offset in the MDC. 3302276479Sdim P->FullOffsetInMDC = P->NonVirtualOffset; 3303276479Sdim if (const CXXRecordDecl *VB = P->getVBaseWithVPtr()) 3304276479Sdim P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB); 3305276479Sdim 3306314564Sdim Paths.push_back(std::move(P)); 3307261991Sdim } 3308276479Sdim 3309276479Sdim if (B.isVirtual()) 3310276479Sdim VBasesSeen.insert(Base); 3311276479Sdim 3312276479Sdim // After visiting any direct base, we've transitively visited all of its 3313276479Sdim // morally virtual bases. 3314276479Sdim for (const auto &VB : Base->vbases()) 3315276479Sdim VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl()); 3316261991Sdim } 3317261991Sdim 3318276479Sdim // Sort the paths into buckets, and if any of them are ambiguous, extend all 3319276479Sdim // paths in ambiguous buckets. 3320276479Sdim bool Changed = true; 3321276479Sdim while (Changed) 3322276479Sdim Changed = rebucketPaths(Paths); 3323276479Sdim} 3324261991Sdim 3325314564Sdimstatic bool extendPath(VPtrInfo &P) { 3326314564Sdim if (P.NextBaseToMangle) { 3327314564Sdim P.MangledPath.push_back(P.NextBaseToMangle); 3328314564Sdim P.NextBaseToMangle = nullptr;// Prevent the path from being extended twice. 3329276479Sdim return true; 3330261991Sdim } 3331276479Sdim return false; 3332261991Sdim} 3333261991Sdim 3334276479Sdimstatic bool rebucketPaths(VPtrInfoVector &Paths) { 3335276479Sdim // What we're essentially doing here is bucketing together ambiguous paths. 3336276479Sdim // Any bucket with more than one path in it gets extended by NextBase, which 3337276479Sdim // is usually the direct base of the inherited the vbptr. This code uses a 3338276479Sdim // sorted vector to implement a multiset to form the buckets. Note that the 3339276479Sdim // ordering is based on pointers, but it doesn't change our output order. The 3340276479Sdim // current algorithm is designed to match MSVC 2012's names. 3341314564Sdim llvm::SmallVector<std::reference_wrapper<VPtrInfo>, 2> PathsSorted; 3342314564Sdim PathsSorted.reserve(Paths.size()); 3343314564Sdim for (auto& P : Paths) 3344314564Sdim PathsSorted.push_back(*P); 3345344779Sdim llvm::sort(PathsSorted, [](const VPtrInfo &LHS, const VPtrInfo &RHS) { 3346314564Sdim return LHS.MangledPath < RHS.MangledPath; 3347276479Sdim }); 3348276479Sdim bool Changed = false; 3349276479Sdim for (size_t I = 0, E = PathsSorted.size(); I != E;) { 3350276479Sdim // Scan forward to find the end of the bucket. 3351276479Sdim size_t BucketStart = I; 3352276479Sdim do { 3353276479Sdim ++I; 3354314564Sdim } while (I != E && 3355314564Sdim PathsSorted[BucketStart].get().MangledPath == 3356314564Sdim PathsSorted[I].get().MangledPath); 3357276479Sdim 3358276479Sdim // If this bucket has multiple paths, extend them all. 3359276479Sdim if (I - BucketStart > 1) { 3360276479Sdim for (size_t II = BucketStart; II != I; ++II) 3361276479Sdim Changed |= extendPath(PathsSorted[II]); 3362276479Sdim assert(Changed && "no paths were extended to fix ambiguity"); 3363276479Sdim } 3364261991Sdim } 3365276479Sdim return Changed; 3366261991Sdim} 3367261991Sdim 3368314564SdimMicrosoftVTableContext::~MicrosoftVTableContext() {} 3369276479Sdim 3370288943Sdimnamespace { 3371288943Sdimtypedef llvm::SetVector<BaseSubobject, std::vector<BaseSubobject>, 3372288943Sdim llvm::DenseSet<BaseSubobject>> FullPathTy; 3373288943Sdim} 3374288943Sdim 3375288943Sdim// This recursive function finds all paths from a subobject centered at 3376314564Sdim// (RD, Offset) to the subobject located at IntroducingObject. 3377288943Sdimstatic void findPathsToSubobject(ASTContext &Context, 3378288943Sdim const ASTRecordLayout &MostDerivedLayout, 3379288943Sdim const CXXRecordDecl *RD, CharUnits Offset, 3380314564Sdim BaseSubobject IntroducingObject, 3381288943Sdim FullPathTy &FullPath, 3382288943Sdim std::list<FullPathTy> &Paths) { 3383314564Sdim if (BaseSubobject(RD, Offset) == IntroducingObject) { 3384288943Sdim Paths.push_back(FullPath); 3385288943Sdim return; 3386280031Sdim } 3387280031Sdim 3388280031Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 3389280031Sdim 3390288943Sdim for (const CXXBaseSpecifier &BS : RD->bases()) { 3391288943Sdim const CXXRecordDecl *Base = BS.getType()->getAsCXXRecordDecl(); 3392288943Sdim CharUnits NewOffset = BS.isVirtual() 3393288943Sdim ? MostDerivedLayout.getVBaseClassOffset(Base) 3394288943Sdim : Offset + Layout.getBaseClassOffset(Base); 3395288943Sdim FullPath.insert(BaseSubobject(Base, NewOffset)); 3396288943Sdim findPathsToSubobject(Context, MostDerivedLayout, Base, NewOffset, 3397314564Sdim IntroducingObject, FullPath, Paths); 3398288943Sdim FullPath.pop_back(); 3399288943Sdim } 3400288943Sdim} 3401280031Sdim 3402288943Sdim// Return the paths which are not subsets of other paths. 3403288943Sdimstatic void removeRedundantPaths(std::list<FullPathTy> &FullPaths) { 3404288943Sdim FullPaths.remove_if([&](const FullPathTy &SpecificPath) { 3405288943Sdim for (const FullPathTy &OtherPath : FullPaths) { 3406288943Sdim if (&SpecificPath == &OtherPath) 3407288943Sdim continue; 3408344779Sdim if (llvm::all_of(SpecificPath, [&](const BaseSubobject &BSO) { 3409344779Sdim return OtherPath.count(BSO) != 0; 3410344779Sdim })) { 3411288943Sdim return true; 3412288943Sdim } 3413280031Sdim } 3414288943Sdim return false; 3415288943Sdim }); 3416288943Sdim} 3417288943Sdim 3418288943Sdimstatic CharUnits getOffsetOfFullPath(ASTContext &Context, 3419288943Sdim const CXXRecordDecl *RD, 3420288943Sdim const FullPathTy &FullPath) { 3421288943Sdim const ASTRecordLayout &MostDerivedLayout = 3422288943Sdim Context.getASTRecordLayout(RD); 3423288943Sdim CharUnits Offset = CharUnits::fromQuantity(-1); 3424288943Sdim for (const BaseSubobject &BSO : FullPath) { 3425288943Sdim const CXXRecordDecl *Base = BSO.getBase(); 3426288943Sdim // The first entry in the path is always the most derived record, skip it. 3427288943Sdim if (Base == RD) { 3428288943Sdim assert(Offset.getQuantity() == -1); 3429288943Sdim Offset = CharUnits::Zero(); 3430288943Sdim continue; 3431288943Sdim } 3432288943Sdim assert(Offset.getQuantity() != -1); 3433288943Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 3434288943Sdim // While we know which base has to be traversed, we don't know if that base 3435288943Sdim // was a virtual base. 3436288943Sdim const CXXBaseSpecifier *BaseBS = std::find_if( 3437288943Sdim RD->bases_begin(), RD->bases_end(), [&](const CXXBaseSpecifier &BS) { 3438288943Sdim return BS.getType()->getAsCXXRecordDecl() == Base; 3439288943Sdim }); 3440288943Sdim Offset = BaseBS->isVirtual() ? MostDerivedLayout.getVBaseClassOffset(Base) 3441288943Sdim : Offset + Layout.getBaseClassOffset(Base); 3442288943Sdim RD = Base; 3443280031Sdim } 3444288943Sdim return Offset; 3445280031Sdim} 3446280031Sdim 3447288943Sdim// We want to select the path which introduces the most covariant overrides. If 3448288943Sdim// two paths introduce overrides which the other path doesn't contain, issue a 3449288943Sdim// diagnostic. 3450288943Sdimstatic const FullPathTy *selectBestPath(ASTContext &Context, 3451314564Sdim const CXXRecordDecl *RD, 3452314564Sdim const VPtrInfo &Info, 3453288943Sdim std::list<FullPathTy> &FullPaths) { 3454288943Sdim // Handle some easy cases first. 3455288943Sdim if (FullPaths.empty()) 3456288943Sdim return nullptr; 3457288943Sdim if (FullPaths.size() == 1) 3458288943Sdim return &FullPaths.front(); 3459288943Sdim 3460288943Sdim const FullPathTy *BestPath = nullptr; 3461288943Sdim typedef std::set<const CXXMethodDecl *> OverriderSetTy; 3462288943Sdim OverriderSetTy LastOverrides; 3463288943Sdim for (const FullPathTy &SpecificPath : FullPaths) { 3464288943Sdim assert(!SpecificPath.empty()); 3465288943Sdim OverriderSetTy CurrentOverrides; 3466288943Sdim const CXXRecordDecl *TopLevelRD = SpecificPath.begin()->getBase(); 3467288943Sdim // Find the distance from the start of the path to the subobject with the 3468288943Sdim // VPtr. 3469288943Sdim CharUnits BaseOffset = 3470288943Sdim getOffsetOfFullPath(Context, TopLevelRD, SpecificPath); 3471288943Sdim FinalOverriders Overriders(TopLevelRD, CharUnits::Zero(), TopLevelRD); 3472314564Sdim for (const CXXMethodDecl *MD : Info.IntroducingObject->methods()) { 3473288943Sdim if (!MD->isVirtual()) 3474288943Sdim continue; 3475288943Sdim FinalOverriders::OverriderInfo OI = 3476288943Sdim Overriders.getOverrider(MD->getCanonicalDecl(), BaseOffset); 3477288943Sdim const CXXMethodDecl *OverridingMethod = OI.Method; 3478288943Sdim // Only overriders which have a return adjustment introduce problematic 3479288943Sdim // thunks. 3480288943Sdim if (ComputeReturnAdjustmentBaseOffset(Context, OverridingMethod, MD) 3481288943Sdim .isEmpty()) 3482288943Sdim continue; 3483288943Sdim // It's possible that the overrider isn't in this path. If so, skip it 3484288943Sdim // because this path didn't introduce it. 3485288943Sdim const CXXRecordDecl *OverridingParent = OverridingMethod->getParent(); 3486344779Sdim if (llvm::none_of(SpecificPath, [&](const BaseSubobject &BSO) { 3487344779Sdim return BSO.getBase() == OverridingParent; 3488344779Sdim })) 3489288943Sdim continue; 3490288943Sdim CurrentOverrides.insert(OverridingMethod); 3491288943Sdim } 3492288943Sdim OverriderSetTy NewOverrides = 3493288943Sdim llvm::set_difference(CurrentOverrides, LastOverrides); 3494288943Sdim if (NewOverrides.empty()) 3495288943Sdim continue; 3496288943Sdim OverriderSetTy MissingOverrides = 3497288943Sdim llvm::set_difference(LastOverrides, CurrentOverrides); 3498288943Sdim if (MissingOverrides.empty()) { 3499288943Sdim // This path is a strict improvement over the last path, let's use it. 3500288943Sdim BestPath = &SpecificPath; 3501288943Sdim std::swap(CurrentOverrides, LastOverrides); 3502288943Sdim } else { 3503288943Sdim // This path introduces an overrider with a conflicting covariant thunk. 3504288943Sdim DiagnosticsEngine &Diags = Context.getDiagnostics(); 3505288943Sdim const CXXMethodDecl *CovariantMD = *NewOverrides.begin(); 3506288943Sdim const CXXMethodDecl *ConflictMD = *MissingOverrides.begin(); 3507288943Sdim Diags.Report(RD->getLocation(), diag::err_vftable_ambiguous_component) 3508288943Sdim << RD; 3509288943Sdim Diags.Report(CovariantMD->getLocation(), diag::note_covariant_thunk) 3510288943Sdim << CovariantMD; 3511288943Sdim Diags.Report(ConflictMD->getLocation(), diag::note_covariant_thunk) 3512288943Sdim << ConflictMD; 3513288943Sdim } 3514288943Sdim } 3515288943Sdim // Go with the path that introduced the most covariant overrides. If there is 3516288943Sdim // no such path, pick the first path. 3517288943Sdim return BestPath ? BestPath : &FullPaths.front(); 3518288943Sdim} 3519288943Sdim 3520280031Sdimstatic void computeFullPathsForVFTables(ASTContext &Context, 3521280031Sdim const CXXRecordDecl *RD, 3522280031Sdim VPtrInfoVector &Paths) { 3523280031Sdim const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD); 3524288943Sdim FullPathTy FullPath; 3525288943Sdim std::list<FullPathTy> FullPaths; 3526314564Sdim for (const std::unique_ptr<VPtrInfo>& Info : Paths) { 3527288943Sdim findPathsToSubobject( 3528288943Sdim Context, MostDerivedLayout, RD, CharUnits::Zero(), 3529314564Sdim BaseSubobject(Info->IntroducingObject, Info->FullOffsetInMDC), FullPath, 3530288943Sdim FullPaths); 3531280031Sdim FullPath.clear(); 3532288943Sdim removeRedundantPaths(FullPaths); 3533314564Sdim Info->PathToIntroducingObject.clear(); 3534288943Sdim if (const FullPathTy *BestPath = 3535314564Sdim selectBestPath(Context, RD, *Info, FullPaths)) 3536288943Sdim for (const BaseSubobject &BSO : *BestPath) 3537314564Sdim Info->PathToIntroducingObject.push_back(BSO.getBase()); 3538288943Sdim FullPaths.clear(); 3539280031Sdim } 3540280031Sdim} 3541280031Sdim 3542341825Sdimstatic bool vfptrIsEarlierInMDC(const ASTRecordLayout &Layout, 3543341825Sdim const MethodVFTableLocation &LHS, 3544341825Sdim const MethodVFTableLocation &RHS) { 3545341825Sdim CharUnits L = LHS.VFPtrOffset; 3546341825Sdim CharUnits R = RHS.VFPtrOffset; 3547341825Sdim if (LHS.VBase) 3548341825Sdim L += Layout.getVBaseClassOffset(LHS.VBase); 3549341825Sdim if (RHS.VBase) 3550341825Sdim R += Layout.getVBaseClassOffset(RHS.VBase); 3551341825Sdim return L < R; 3552341825Sdim} 3553341825Sdim 3554261991Sdimvoid MicrosoftVTableContext::computeVTableRelatedInformation( 3555261991Sdim const CXXRecordDecl *RD) { 3556261991Sdim assert(RD->isDynamicClass()); 3557261991Sdim 3558261991Sdim // Check if we've computed this information before. 3559261991Sdim if (VFPtrLocations.count(RD)) 3560261991Sdim return; 3561261991Sdim 3562261991Sdim const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap; 3563261991Sdim 3564314564Sdim { 3565360784Sdim auto VFPtrs = std::make_unique<VPtrInfoVector>(); 3566341825Sdim computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs); 3567341825Sdim computeFullPathsForVFTables(Context, RD, *VFPtrs); 3568314564Sdim VFPtrLocations[RD] = std::move(VFPtrs); 3569314564Sdim } 3570261991Sdim 3571261991Sdim MethodVFTableLocationsTy NewMethodLocations; 3572341825Sdim for (const std::unique_ptr<VPtrInfo> &VFPtr : *VFPtrLocations[RD]) { 3573314564Sdim VFTableBuilder Builder(*this, RD, *VFPtr); 3574261991Sdim 3575296417Sdim VFTableIdTy id(RD, VFPtr->FullOffsetInMDC); 3576261991Sdim assert(VFTableLayouts.count(id) == 0); 3577261991Sdim SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks( 3578261991Sdim Builder.vtable_thunks_begin(), Builder.vtable_thunks_end()); 3579360784Sdim VFTableLayouts[id] = std::make_unique<VTableLayout>( 3580314564Sdim ArrayRef<size_t>{0}, Builder.vtable_components(), VTableThunks, 3581314564Sdim EmptyAddressPointsMap); 3582261991Sdim Thunks.insert(Builder.thunks_begin(), Builder.thunks_end()); 3583276479Sdim 3584341825Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 3585276479Sdim for (const auto &Loc : Builder.vtable_locations()) { 3586341825Sdim auto Insert = NewMethodLocations.insert(Loc); 3587341825Sdim if (!Insert.second) { 3588341825Sdim const MethodVFTableLocation &NewLoc = Loc.second; 3589341825Sdim MethodVFTableLocation &OldLoc = Insert.first->second; 3590341825Sdim if (vfptrIsEarlierInMDC(Layout, NewLoc, OldLoc)) 3591341825Sdim OldLoc = NewLoc; 3592341825Sdim } 3593276479Sdim } 3594261991Sdim } 3595261991Sdim 3596261991Sdim MethodVFTableLocations.insert(NewMethodLocations.begin(), 3597261991Sdim NewMethodLocations.end()); 3598261991Sdim if (Context.getLangOpts().DumpVTableLayouts) 3599261991Sdim dumpMethodLocations(RD, NewMethodLocations, llvm::outs()); 3600261991Sdim} 3601261991Sdim 3602261991Sdimvoid MicrosoftVTableContext::dumpMethodLocations( 3603261991Sdim const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods, 3604261991Sdim raw_ostream &Out) { 3605261991Sdim // Compute the vtable indices for all the member functions. 3606261991Sdim // Store them in a map keyed by the location so we'll get a sorted table. 3607261991Sdim std::map<MethodVFTableLocation, std::string> IndicesMap; 3608261991Sdim bool HasNonzeroOffset = false; 3609261991Sdim 3610296417Sdim for (const auto &I : NewMethods) { 3611296417Sdim const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I.first.getDecl()); 3612261991Sdim assert(MD->isVirtual()); 3613261991Sdim 3614261991Sdim std::string MethodName = PredefinedExpr::ComputeName( 3615261991Sdim PredefinedExpr::PrettyFunctionNoVirtual, MD); 3616261991Sdim 3617261991Sdim if (isa<CXXDestructorDecl>(MD)) { 3618296417Sdim IndicesMap[I.second] = MethodName + " [scalar deleting]"; 3619261991Sdim } else { 3620296417Sdim IndicesMap[I.second] = MethodName; 3621261991Sdim } 3622261991Sdim 3623296417Sdim if (!I.second.VFPtrOffset.isZero() || I.second.VBTableIndex != 0) 3624261991Sdim HasNonzeroOffset = true; 3625261991Sdim } 3626261991Sdim 3627261991Sdim // Print the vtable indices for all the member functions. 3628261991Sdim if (!IndicesMap.empty()) { 3629261991Sdim Out << "VFTable indices for "; 3630276479Sdim Out << "'"; 3631276479Sdim RD->printQualifiedName(Out); 3632276479Sdim Out << "' (" << IndicesMap.size() 3633276479Sdim << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n"; 3634261991Sdim 3635261991Sdim CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1); 3636261991Sdim uint64_t LastVBIndex = 0; 3637296417Sdim for (const auto &I : IndicesMap) { 3638296417Sdim CharUnits VFPtrOffset = I.first.VFPtrOffset; 3639296417Sdim uint64_t VBIndex = I.first.VBTableIndex; 3640261991Sdim if (HasNonzeroOffset && 3641261991Sdim (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) { 3642261991Sdim assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset); 3643261991Sdim Out << " -- accessible via "; 3644261991Sdim if (VBIndex) 3645261991Sdim Out << "vbtable index " << VBIndex << ", "; 3646261991Sdim Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n"; 3647261991Sdim LastVFPtrOffset = VFPtrOffset; 3648261991Sdim LastVBIndex = VBIndex; 3649261991Sdim } 3650261991Sdim 3651296417Sdim uint64_t VTableIndex = I.first.Index; 3652296417Sdim const std::string &MethodName = I.second; 3653261991Sdim Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n'; 3654261991Sdim } 3655261991Sdim Out << '\n'; 3656261991Sdim } 3657276479Sdim 3658276479Sdim Out.flush(); 3659261991Sdim} 3660261991Sdim 3661314564Sdimconst VirtualBaseInfo &MicrosoftVTableContext::computeVBTableRelatedInformation( 3662261991Sdim const CXXRecordDecl *RD) { 3663276479Sdim VirtualBaseInfo *VBI; 3664261991Sdim 3665276479Sdim { 3666276479Sdim // Get or create a VBI for RD. Don't hold a reference to the DenseMap cell, 3667276479Sdim // as it may be modified and rehashed under us. 3668314564Sdim std::unique_ptr<VirtualBaseInfo> &Entry = VBaseInfo[RD]; 3669276479Sdim if (Entry) 3670314564Sdim return *Entry; 3671360784Sdim Entry = std::make_unique<VirtualBaseInfo>(); 3672314564Sdim VBI = Entry.get(); 3673276479Sdim } 3674261991Sdim 3675276479Sdim computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths); 3676276479Sdim 3677261991Sdim // First, see if the Derived class shared the vbptr with a non-virtual base. 3678276479Sdim const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 3679261991Sdim if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) { 3680276479Sdim // If the Derived class shares the vbptr with a non-virtual base, the shared 3681276479Sdim // virtual bases come first so that the layout is the same. 3682314564Sdim const VirtualBaseInfo &BaseInfo = 3683276479Sdim computeVBTableRelatedInformation(VBPtrBase); 3684314564Sdim VBI->VBTableIndices.insert(BaseInfo.VBTableIndices.begin(), 3685314564Sdim BaseInfo.VBTableIndices.end()); 3686261991Sdim } 3687261991Sdim 3688261991Sdim // New vbases are added to the end of the vbtable. 3689261991Sdim // Skip the self entry and vbases visited in the non-virtual base, if any. 3690276479Sdim unsigned VBTableIndex = 1 + VBI->VBTableIndices.size(); 3691276479Sdim for (const auto &VB : RD->vbases()) { 3692276479Sdim const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl(); 3693276479Sdim if (!VBI->VBTableIndices.count(CurVBase)) 3694276479Sdim VBI->VBTableIndices[CurVBase] = VBTableIndex++; 3695261991Sdim } 3696276479Sdim 3697314564Sdim return *VBI; 3698261991Sdim} 3699261991Sdim 3700276479Sdimunsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived, 3701276479Sdim const CXXRecordDecl *VBase) { 3702314564Sdim const VirtualBaseInfo &VBInfo = computeVBTableRelatedInformation(Derived); 3703314564Sdim assert(VBInfo.VBTableIndices.count(VBase)); 3704314564Sdim return VBInfo.VBTableIndices.find(VBase)->second; 3705276479Sdim} 3706276479Sdim 3707276479Sdimconst VPtrInfoVector & 3708276479SdimMicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) { 3709314564Sdim return computeVBTableRelatedInformation(RD).VBPtrPaths; 3710276479Sdim} 3711276479Sdim 3712276479Sdimconst VPtrInfoVector & 3713261991SdimMicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) { 3714261991Sdim computeVTableRelatedInformation(RD); 3715261991Sdim 3716261991Sdim assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations"); 3717341825Sdim return *VFPtrLocations[RD]; 3718261991Sdim} 3719261991Sdim 3720261991Sdimconst VTableLayout & 3721261991SdimMicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD, 3722261991Sdim CharUnits VFPtrOffset) { 3723261991Sdim computeVTableRelatedInformation(RD); 3724261991Sdim 3725261991Sdim VFTableIdTy id(RD, VFPtrOffset); 3726261991Sdim assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset"); 3727261991Sdim return *VFTableLayouts[id]; 3728261991Sdim} 3729261991Sdim 3730341825SdimMethodVFTableLocation 3731261991SdimMicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) { 3732261991Sdim assert(cast<CXXMethodDecl>(GD.getDecl())->isVirtual() && 3733261991Sdim "Only use this method for virtual methods or dtors"); 3734261991Sdim if (isa<CXXDestructorDecl>(GD.getDecl())) 3735261991Sdim assert(GD.getDtorType() == Dtor_Deleting); 3736261991Sdim 3737341825Sdim GD = GD.getCanonicalDecl(); 3738341825Sdim 3739261991Sdim MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD); 3740261991Sdim if (I != MethodVFTableLocations.end()) 3741261991Sdim return I->second; 3742261991Sdim 3743261991Sdim const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent(); 3744261991Sdim 3745261991Sdim computeVTableRelatedInformation(RD); 3746261991Sdim 3747261991Sdim I = MethodVFTableLocations.find(GD); 3748261991Sdim assert(I != MethodVFTableLocations.end() && "Did not find index!"); 3749261991Sdim return I->second; 3750261991Sdim} 3751