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