1 //===--- VTableBuilder.h - C++ vtable layout builder --------------*- C++ -*-=// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This contains code dealing with generation of the layout of virtual tables. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #ifndef LLVM_CLANG_AST_VTABLEBUILDER_H 14 #define LLVM_CLANG_AST_VTABLEBUILDER_H 15 16 #include "clang/AST/BaseSubobject.h" 17 #include "clang/AST/CXXInheritance.h" 18 #include "clang/AST/GlobalDecl.h" 19 #include "clang/AST/RecordLayout.h" 20 #include "clang/Basic/ABI.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include <memory> 23 #include <utility> 24 25 namespace clang { 26 class CXXRecordDecl; 27 28 /// Represents a single component in a vtable. 29 class VTableComponent { 30 public: 31 enum Kind { 32 CK_VCallOffset, 33 CK_VBaseOffset, 34 CK_OffsetToTop, 35 CK_RTTI, 36 CK_FunctionPointer, 37 38 /// A pointer to the complete destructor. 39 CK_CompleteDtorPointer, 40 41 /// A pointer to the deleting destructor. 42 CK_DeletingDtorPointer, 43 44 /// An entry that is never used. 45 /// 46 /// In some cases, a vtable function pointer will end up never being 47 /// called. Such vtable function pointers are represented as a 48 /// CK_UnusedFunctionPointer. 49 CK_UnusedFunctionPointer 50 }; 51 52 VTableComponent() = default; 53 MakeVCallOffset(CharUnits Offset)54 static VTableComponent MakeVCallOffset(CharUnits Offset) { 55 return VTableComponent(CK_VCallOffset, Offset); 56 } 57 MakeVBaseOffset(CharUnits Offset)58 static VTableComponent MakeVBaseOffset(CharUnits Offset) { 59 return VTableComponent(CK_VBaseOffset, Offset); 60 } 61 MakeOffsetToTop(CharUnits Offset)62 static VTableComponent MakeOffsetToTop(CharUnits Offset) { 63 return VTableComponent(CK_OffsetToTop, Offset); 64 } 65 MakeRTTI(const CXXRecordDecl * RD)66 static VTableComponent MakeRTTI(const CXXRecordDecl *RD) { 67 return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD)); 68 } 69 MakeFunction(const CXXMethodDecl * MD)70 static VTableComponent MakeFunction(const CXXMethodDecl *MD) { 71 assert(!isa<CXXDestructorDecl>(MD) && 72 "Don't use MakeFunction with destructors!"); 73 74 return VTableComponent(CK_FunctionPointer, 75 reinterpret_cast<uintptr_t>(MD)); 76 } 77 MakeCompleteDtor(const CXXDestructorDecl * DD)78 static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) { 79 return VTableComponent(CK_CompleteDtorPointer, 80 reinterpret_cast<uintptr_t>(DD)); 81 } 82 MakeDeletingDtor(const CXXDestructorDecl * DD)83 static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) { 84 return VTableComponent(CK_DeletingDtorPointer, 85 reinterpret_cast<uintptr_t>(DD)); 86 } 87 MakeUnusedFunction(const CXXMethodDecl * MD)88 static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) { 89 assert(!isa<CXXDestructorDecl>(MD) && 90 "Don't use MakeUnusedFunction with destructors!"); 91 return VTableComponent(CK_UnusedFunctionPointer, 92 reinterpret_cast<uintptr_t>(MD)); 93 } 94 95 /// Get the kind of this vtable component. getKind()96 Kind getKind() const { 97 return (Kind)(Value & 0x7); 98 } 99 getVCallOffset()100 CharUnits getVCallOffset() const { 101 assert(getKind() == CK_VCallOffset && "Invalid component kind!"); 102 103 return getOffset(); 104 } 105 getVBaseOffset()106 CharUnits getVBaseOffset() const { 107 assert(getKind() == CK_VBaseOffset && "Invalid component kind!"); 108 109 return getOffset(); 110 } 111 getOffsetToTop()112 CharUnits getOffsetToTop() const { 113 assert(getKind() == CK_OffsetToTop && "Invalid component kind!"); 114 115 return getOffset(); 116 } 117 getRTTIDecl()118 const CXXRecordDecl *getRTTIDecl() const { 119 assert(isRTTIKind() && "Invalid component kind!"); 120 return reinterpret_cast<CXXRecordDecl *>(getPointer()); 121 } 122 getFunctionDecl()123 const CXXMethodDecl *getFunctionDecl() const { 124 assert(isFunctionPointerKind() && "Invalid component kind!"); 125 if (isDestructorKind()) 126 return getDestructorDecl(); 127 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 128 } 129 getDestructorDecl()130 const CXXDestructorDecl *getDestructorDecl() const { 131 assert(isDestructorKind() && "Invalid component kind!"); 132 return reinterpret_cast<CXXDestructorDecl *>(getPointer()); 133 } 134 getUnusedFunctionDecl()135 const CXXMethodDecl *getUnusedFunctionDecl() const { 136 assert(getKind() == CK_UnusedFunctionPointer && "Invalid component kind!"); 137 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 138 } 139 isDestructorKind()140 bool isDestructorKind() const { return isDestructorKind(getKind()); } 141 isUsedFunctionPointerKind()142 bool isUsedFunctionPointerKind() const { 143 return isUsedFunctionPointerKind(getKind()); 144 } 145 isFunctionPointerKind()146 bool isFunctionPointerKind() const { 147 return isFunctionPointerKind(getKind()); 148 } 149 isRTTIKind()150 bool isRTTIKind() const { return isRTTIKind(getKind()); } 151 getGlobalDecl()152 GlobalDecl getGlobalDecl() const { 153 assert(isUsedFunctionPointerKind() && 154 "GlobalDecl can be created only from virtual function"); 155 156 auto *DtorDecl = dyn_cast<CXXDestructorDecl>(getFunctionDecl()); 157 switch (getKind()) { 158 case CK_FunctionPointer: 159 return GlobalDecl(getFunctionDecl()); 160 case CK_CompleteDtorPointer: 161 return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Complete); 162 case CK_DeletingDtorPointer: 163 return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Deleting); 164 case CK_VCallOffset: 165 case CK_VBaseOffset: 166 case CK_OffsetToTop: 167 case CK_RTTI: 168 case CK_UnusedFunctionPointer: 169 llvm_unreachable("Only function pointers kinds"); 170 } 171 llvm_unreachable("Should already return"); 172 } 173 174 private: isFunctionPointerKind(Kind ComponentKind)175 static bool isFunctionPointerKind(Kind ComponentKind) { 176 return isUsedFunctionPointerKind(ComponentKind) || 177 ComponentKind == CK_UnusedFunctionPointer; 178 } isUsedFunctionPointerKind(Kind ComponentKind)179 static bool isUsedFunctionPointerKind(Kind ComponentKind) { 180 return ComponentKind == CK_FunctionPointer || 181 isDestructorKind(ComponentKind); 182 } isDestructorKind(Kind ComponentKind)183 static bool isDestructorKind(Kind ComponentKind) { 184 return ComponentKind == CK_CompleteDtorPointer || 185 ComponentKind == CK_DeletingDtorPointer; 186 } isRTTIKind(Kind ComponentKind)187 static bool isRTTIKind(Kind ComponentKind) { 188 return ComponentKind == CK_RTTI; 189 } 190 VTableComponent(Kind ComponentKind,CharUnits Offset)191 VTableComponent(Kind ComponentKind, CharUnits Offset) { 192 assert((ComponentKind == CK_VCallOffset || 193 ComponentKind == CK_VBaseOffset || 194 ComponentKind == CK_OffsetToTop) && "Invalid component kind!"); 195 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!"); 196 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!"); 197 198 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind; 199 } 200 VTableComponent(Kind ComponentKind,uintptr_t Ptr)201 VTableComponent(Kind ComponentKind, uintptr_t Ptr) { 202 assert((isRTTIKind(ComponentKind) || isFunctionPointerKind(ComponentKind)) && 203 "Invalid component kind!"); 204 205 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!"); 206 207 Value = Ptr | ComponentKind; 208 } 209 getOffset()210 CharUnits getOffset() const { 211 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset || 212 getKind() == CK_OffsetToTop) && "Invalid component kind!"); 213 214 return CharUnits::fromQuantity(Value >> 3); 215 } 216 getPointer()217 uintptr_t getPointer() const { 218 assert((getKind() == CK_RTTI || isFunctionPointerKind()) && 219 "Invalid component kind!"); 220 221 return static_cast<uintptr_t>(Value & ~7ULL); 222 } 223 224 /// The kind is stored in the lower 3 bits of the value. For offsets, we 225 /// make use of the facts that classes can't be larger than 2^55 bytes, 226 /// so we store the offset in the lower part of the 61 bits that remain. 227 /// (The reason that we're not simply using a PointerIntPair here is that we 228 /// need the offsets to be 64-bit, even when on a 32-bit machine). 229 int64_t Value; 230 }; 231 232 class VTableLayout { 233 public: 234 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy; 235 struct AddressPointLocation { 236 unsigned VTableIndex, AddressPointIndex; 237 }; 238 typedef llvm::DenseMap<BaseSubobject, AddressPointLocation> 239 AddressPointsMapTy; 240 241 private: 242 // Stores the component indices of the first component of each virtual table in 243 // the virtual table group. To save a little memory in the common case where 244 // the vtable group contains a single vtable, an empty vector here represents 245 // the vector {0}. 246 OwningArrayRef<size_t> VTableIndices; 247 248 OwningArrayRef<VTableComponent> VTableComponents; 249 250 /// Contains thunks needed by vtables, sorted by indices. 251 OwningArrayRef<VTableThunkTy> VTableThunks; 252 253 /// Address points for all vtables. 254 AddressPointsMapTy AddressPoints; 255 256 public: 257 VTableLayout(ArrayRef<size_t> VTableIndices, 258 ArrayRef<VTableComponent> VTableComponents, 259 ArrayRef<VTableThunkTy> VTableThunks, 260 const AddressPointsMapTy &AddressPoints); 261 ~VTableLayout(); 262 vtable_components()263 ArrayRef<VTableComponent> vtable_components() const { 264 return VTableComponents; 265 } 266 vtable_thunks()267 ArrayRef<VTableThunkTy> vtable_thunks() const { 268 return VTableThunks; 269 } 270 getAddressPoint(BaseSubobject Base)271 AddressPointLocation getAddressPoint(BaseSubobject Base) const { 272 assert(AddressPoints.count(Base) && "Did not find address point!"); 273 return AddressPoints.find(Base)->second; 274 } 275 getAddressPoints()276 const AddressPointsMapTy &getAddressPoints() const { 277 return AddressPoints; 278 } 279 getNumVTables()280 size_t getNumVTables() const { 281 if (VTableIndices.empty()) 282 return 1; 283 return VTableIndices.size(); 284 } 285 getVTableOffset(size_t i)286 size_t getVTableOffset(size_t i) const { 287 if (VTableIndices.empty()) { 288 assert(i == 0); 289 return 0; 290 } 291 return VTableIndices[i]; 292 } 293 getVTableSize(size_t i)294 size_t getVTableSize(size_t i) const { 295 if (VTableIndices.empty()) { 296 assert(i == 0); 297 return vtable_components().size(); 298 } 299 300 size_t thisIndex = VTableIndices[i]; 301 size_t nextIndex = (i + 1 == VTableIndices.size()) 302 ? vtable_components().size() 303 : VTableIndices[i + 1]; 304 return nextIndex - thisIndex; 305 } 306 }; 307 308 class VTableContextBase { 309 public: 310 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 311 isMicrosoft()312 bool isMicrosoft() const { return IsMicrosoftABI; } 313 ~VTableContextBase()314 virtual ~VTableContextBase() {} 315 316 protected: 317 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 318 319 /// Contains all thunks that a given method decl will need. 320 ThunksMapTy Thunks; 321 322 /// Compute and store all vtable related information (vtable layout, vbase 323 /// offset offsets, thunks etc) for the given record decl. 324 virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0; 325 VTableContextBase(bool MS)326 VTableContextBase(bool MS) : IsMicrosoftABI(MS) {} 327 328 public: getThunkInfo(GlobalDecl GD)329 virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) { 330 const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl()); 331 computeVTableRelatedInformation(MD->getParent()); 332 333 // This assumes that all the destructors present in the vtable 334 // use exactly the same set of thunks. 335 ThunksMapTy::const_iterator I = Thunks.find(MD); 336 if (I == Thunks.end()) { 337 // We did not find a thunk for this method. 338 return nullptr; 339 } 340 341 return &I->second; 342 } 343 344 bool IsMicrosoftABI; 345 }; 346 347 class ItaniumVTableContext : public VTableContextBase { 348 private: 349 350 /// Contains the index (relative to the vtable address point) 351 /// where the function pointer for a virtual function is stored. 352 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy; 353 MethodVTableIndicesTy MethodVTableIndices; 354 355 typedef llvm::DenseMap<const CXXRecordDecl *, 356 std::unique_ptr<const VTableLayout>> 357 VTableLayoutMapTy; 358 VTableLayoutMapTy VTableLayouts; 359 360 typedef std::pair<const CXXRecordDecl *, 361 const CXXRecordDecl *> ClassPairTy; 362 363 /// vtable offsets for offsets of virtual bases of a class. 364 /// 365 /// Contains the vtable offset (relative to the address point) in chars 366 /// where the offsets for virtual bases of a class are stored. 367 typedef llvm::DenseMap<ClassPairTy, CharUnits> 368 VirtualBaseClassOffsetOffsetsMapTy; 369 VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets; 370 371 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override; 372 373 public: 374 ItaniumVTableContext(ASTContext &Context); 375 ~ItaniumVTableContext() override; 376 getVTableLayout(const CXXRecordDecl * RD)377 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) { 378 computeVTableRelatedInformation(RD); 379 assert(VTableLayouts.count(RD) && "No layout for this record decl!"); 380 381 return *VTableLayouts[RD]; 382 } 383 384 std::unique_ptr<VTableLayout> createConstructionVTableLayout( 385 const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset, 386 bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass); 387 388 /// Locate a virtual function in the vtable. 389 /// 390 /// Return the index (relative to the vtable address point) where the 391 /// function pointer for the given virtual function is stored. 392 uint64_t getMethodVTableIndex(GlobalDecl GD); 393 394 /// Return the offset in chars (relative to the vtable address point) where 395 /// the offset of the virtual base that contains the given base is stored, 396 /// otherwise, if no virtual base contains the given class, return 0. 397 /// 398 /// Base must be a virtual base class or an unambiguous base. 399 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD, 400 const CXXRecordDecl *VBase); 401 classof(const VTableContextBase * VT)402 static bool classof(const VTableContextBase *VT) { 403 return !VT->isMicrosoft(); 404 } 405 }; 406 407 /// Holds information about the inheritance path to a virtual base or function 408 /// table pointer. A record may contain as many vfptrs or vbptrs as there are 409 /// base subobjects. 410 struct VPtrInfo { 411 typedef SmallVector<const CXXRecordDecl *, 1> BasePath; 412 VPtrInfoVPtrInfo413 VPtrInfo(const CXXRecordDecl *RD) 414 : ObjectWithVPtr(RD), IntroducingObject(RD), NextBaseToMangle(RD) {} 415 416 /// This is the most derived class that has this vptr at offset zero. When 417 /// single inheritance is used, this is always the most derived class. If 418 /// multiple inheritance is used, it may be any direct or indirect base. 419 const CXXRecordDecl *ObjectWithVPtr; 420 421 /// This is the class that introduced the vptr by declaring new virtual 422 /// methods or virtual bases. 423 const CXXRecordDecl *IntroducingObject; 424 425 /// IntroducingObject is at this offset from its containing complete object or 426 /// virtual base. 427 CharUnits NonVirtualOffset; 428 429 /// The bases from the inheritance path that got used to mangle the vbtable 430 /// name. This is not really a full path like a CXXBasePath. It holds the 431 /// subset of records that need to be mangled into the vbtable symbol name in 432 /// order to get a unique name. 433 BasePath MangledPath; 434 435 /// The next base to push onto the mangled path if this path is ambiguous in a 436 /// derived class. If it's null, then it's already been pushed onto the path. 437 const CXXRecordDecl *NextBaseToMangle; 438 439 /// The set of possibly indirect vbases that contain this vbtable. When a 440 /// derived class indirectly inherits from the same vbase twice, we only keep 441 /// vtables and their paths from the first instance. 442 BasePath ContainingVBases; 443 444 /// This holds the base classes path from the complete type to the first base 445 /// with the given vfptr offset, in the base-to-derived order. Only used for 446 /// vftables. 447 BasePath PathToIntroducingObject; 448 449 /// Static offset from the top of the most derived class to this vfptr, 450 /// including any virtual base offset. Only used for vftables. 451 CharUnits FullOffsetInMDC; 452 453 /// The vptr is stored inside the non-virtual component of this virtual base. getVBaseWithVPtrVPtrInfo454 const CXXRecordDecl *getVBaseWithVPtr() const { 455 return ContainingVBases.empty() ? nullptr : ContainingVBases.front(); 456 } 457 }; 458 459 typedef SmallVector<std::unique_ptr<VPtrInfo>, 2> VPtrInfoVector; 460 461 /// All virtual base related information about a given record decl. Includes 462 /// information on all virtual base tables and the path components that are used 463 /// to mangle them. 464 struct VirtualBaseInfo { 465 /// A map from virtual base to vbtable index for doing a conversion from the 466 /// the derived class to the a base. 467 llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices; 468 469 /// Information on all virtual base tables used when this record is the most 470 /// derived class. 471 VPtrInfoVector VBPtrPaths; 472 }; 473 474 struct MethodVFTableLocation { 475 /// If nonzero, holds the vbtable index of the virtual base with the vfptr. 476 uint64_t VBTableIndex; 477 478 /// If nonnull, holds the last vbase which contains the vfptr that the 479 /// method definition is adjusted to. 480 const CXXRecordDecl *VBase; 481 482 /// This is the offset of the vfptr from the start of the last vbase, or the 483 /// complete type if there are no virtual bases. 484 CharUnits VFPtrOffset; 485 486 /// Method's index in the vftable. 487 uint64_t Index; 488 MethodVFTableLocationMethodVFTableLocation489 MethodVFTableLocation() 490 : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()), 491 Index(0) {} 492 MethodVFTableLocationMethodVFTableLocation493 MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase, 494 CharUnits VFPtrOffset, uint64_t Index) 495 : VBTableIndex(VBTableIndex), VBase(VBase), VFPtrOffset(VFPtrOffset), 496 Index(Index) {} 497 498 bool operator<(const MethodVFTableLocation &other) const { 499 if (VBTableIndex != other.VBTableIndex) { 500 assert(VBase != other.VBase); 501 return VBTableIndex < other.VBTableIndex; 502 } 503 return std::tie(VFPtrOffset, Index) < 504 std::tie(other.VFPtrOffset, other.Index); 505 } 506 }; 507 508 class MicrosoftVTableContext : public VTableContextBase { 509 public: 510 511 private: 512 ASTContext &Context; 513 514 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation> 515 MethodVFTableLocationsTy; 516 MethodVFTableLocationsTy MethodVFTableLocations; 517 518 typedef llvm::DenseMap<const CXXRecordDecl *, std::unique_ptr<VPtrInfoVector>> 519 VFPtrLocationsMapTy; 520 VFPtrLocationsMapTy VFPtrLocations; 521 522 typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy; 523 typedef llvm::DenseMap<VFTableIdTy, std::unique_ptr<const VTableLayout>> 524 VFTableLayoutMapTy; 525 VFTableLayoutMapTy VFTableLayouts; 526 527 llvm::DenseMap<const CXXRecordDecl *, std::unique_ptr<VirtualBaseInfo>> 528 VBaseInfo; 529 530 void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result); 531 532 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override; 533 534 void dumpMethodLocations(const CXXRecordDecl *RD, 535 const MethodVFTableLocationsTy &NewMethods, 536 raw_ostream &); 537 538 const VirtualBaseInfo & 539 computeVBTableRelatedInformation(const CXXRecordDecl *RD); 540 541 void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD, 542 VPtrInfoVector &Paths); 543 544 public: MicrosoftVTableContext(ASTContext & Context)545 MicrosoftVTableContext(ASTContext &Context) 546 : VTableContextBase(/*MS=*/true), Context(Context) {} 547 548 ~MicrosoftVTableContext() override; 549 550 const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD); 551 552 const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD, 553 CharUnits VFPtrOffset); 554 555 MethodVFTableLocation getMethodVFTableLocation(GlobalDecl GD); 556 getThunkInfo(GlobalDecl GD)557 const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override { 558 // Complete destructors don't have a slot in a vftable, so no thunks needed. 559 if (isa<CXXDestructorDecl>(GD.getDecl()) && 560 GD.getDtorType() == Dtor_Complete) 561 return nullptr; 562 return VTableContextBase::getThunkInfo(GD); 563 } 564 565 /// Returns the index of VBase in the vbtable of Derived. 566 /// VBase must be a morally virtual base of Derived. 567 /// The vbtable is an array of i32 offsets. The first entry is a self entry, 568 /// and the rest are offsets from the vbptr to virtual bases. 569 unsigned getVBTableIndex(const CXXRecordDecl *Derived, 570 const CXXRecordDecl *VBase); 571 572 const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD); 573 classof(const VTableContextBase * VT)574 static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); } 575 }; 576 577 } // namespace clang 578 579 #endif 580