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