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