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