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