1 //===--- VTableBuilder.h - C++ vtable layout builder --------------*- C++ -*-=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This contains code dealing with generation of the layout of virtual tables.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_AST_VTABLEBUILDER_H
15 #define LLVM_CLANG_AST_VTABLEBUILDER_H
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"
29 /// \brief Represents a single component in a vtable.
30 class VTableComponent {
39 /// \brief A pointer to the complete destructor.
40 CK_CompleteDtorPointer,
42 /// \brief A pointer to the deleting destructor.
43 CK_DeletingDtorPointer,
45 /// \brief An entry that is never used.
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
53 VTableComponent() = default;
55 static VTableComponent MakeVCallOffset(CharUnits Offset) {
56 return VTableComponent(CK_VCallOffset, Offset);
59 static VTableComponent MakeVBaseOffset(CharUnits Offset) {
60 return VTableComponent(CK_VBaseOffset, Offset);
63 static VTableComponent MakeOffsetToTop(CharUnits Offset) {
64 return VTableComponent(CK_OffsetToTop, Offset);
67 static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
68 return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
71 static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
72 assert(!isa<CXXDestructorDecl>(MD) &&
73 "Don't use MakeFunction with destructors!");
75 return VTableComponent(CK_FunctionPointer,
76 reinterpret_cast<uintptr_t>(MD));
79 static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
80 return VTableComponent(CK_CompleteDtorPointer,
81 reinterpret_cast<uintptr_t>(DD));
84 static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
85 return VTableComponent(CK_DeletingDtorPointer,
86 reinterpret_cast<uintptr_t>(DD));
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));
96 static VTableComponent getFromOpaqueInteger(uint64_t I) {
97 return VTableComponent(I);
100 /// \brief Get the kind of this vtable component.
101 Kind getKind() const {
102 return (Kind)(Value & 0x7);
105 CharUnits getVCallOffset() const {
106 assert(getKind() == CK_VCallOffset && "Invalid component kind!");
111 CharUnits getVBaseOffset() const {
112 assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
117 CharUnits getOffsetToTop() const {
118 assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
123 const CXXRecordDecl *getRTTIDecl() const {
124 assert(isRTTIKind() && "Invalid component kind!");
125 return reinterpret_cast<CXXRecordDecl *>(getPointer());
128 const CXXMethodDecl *getFunctionDecl() const {
129 assert(isFunctionPointerKind() && "Invalid component kind!");
130 if (isDestructorKind())
131 return getDestructorDecl();
132 return reinterpret_cast<CXXMethodDecl *>(getPointer());
135 const CXXDestructorDecl *getDestructorDecl() const {
136 assert(isDestructorKind() && "Invalid component kind!");
137 return reinterpret_cast<CXXDestructorDecl *>(getPointer());
140 const CXXMethodDecl *getUnusedFunctionDecl() const {
141 assert(getKind() == CK_UnusedFunctionPointer && "Invalid component kind!");
142 return reinterpret_cast<CXXMethodDecl *>(getPointer());
145 bool isDestructorKind() const { return isDestructorKind(getKind()); }
147 bool isUsedFunctionPointerKind() const {
148 return isUsedFunctionPointerKind(getKind());
151 bool isFunctionPointerKind() const {
152 return isFunctionPointerKind(getKind());
155 bool isRTTIKind() const { return isRTTIKind(getKind()); }
157 GlobalDecl getGlobalDecl() const {
158 assert(isUsedFunctionPointerKind() &&
159 "GlobalDecl can be created only from virtual function");
161 auto *DtorDecl = dyn_cast<CXXDestructorDecl>(getFunctionDecl());
163 case CK_FunctionPointer:
164 return GlobalDecl(getFunctionDecl());
165 case CK_CompleteDtorPointer:
166 return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Complete);
167 case CK_DeletingDtorPointer:
168 return GlobalDecl(DtorDecl, CXXDtorType::Dtor_Deleting);
173 case CK_UnusedFunctionPointer:
174 llvm_unreachable("Only function pointers kinds");
176 llvm_unreachable("Should already return");
180 static bool isFunctionPointerKind(Kind ComponentKind) {
181 return isUsedFunctionPointerKind(ComponentKind) ||
182 ComponentKind == CK_UnusedFunctionPointer;
184 static bool isUsedFunctionPointerKind(Kind ComponentKind) {
185 return ComponentKind == CK_FunctionPointer ||
186 isDestructorKind(ComponentKind);
188 static bool isDestructorKind(Kind ComponentKind) {
189 return ComponentKind == CK_CompleteDtorPointer ||
190 ComponentKind == CK_DeletingDtorPointer;
192 static bool isRTTIKind(Kind ComponentKind) {
193 return ComponentKind == CK_RTTI;
196 VTableComponent(Kind ComponentKind, CharUnits Offset) {
197 assert((ComponentKind == CK_VCallOffset ||
198 ComponentKind == CK_VBaseOffset ||
199 ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
200 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
201 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
203 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
206 VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
207 assert((isRTTIKind(ComponentKind) || isFunctionPointerKind(ComponentKind)) &&
208 "Invalid component kind!");
210 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
212 Value = Ptr | ComponentKind;
215 CharUnits getOffset() const {
216 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
217 getKind() == CK_OffsetToTop) && "Invalid component kind!");
219 return CharUnits::fromQuantity(Value >> 3);
222 uintptr_t getPointer() const {
223 assert((getKind() == CK_RTTI || isFunctionPointerKind()) &&
224 "Invalid component kind!");
226 return static_cast<uintptr_t>(Value & ~7ULL);
229 explicit VTableComponent(uint64_t Value)
232 /// The kind is stored in the lower 3 bits of the value. For offsets, we
233 /// make use of the facts that classes can't be larger than 2^55 bytes,
234 /// so we store the offset in the lower part of the 61 bits that remain.
235 /// (The reason that we're not simply using a PointerIntPair here is that we
236 /// need the offsets to be 64-bit, even when on a 32-bit machine).
242 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
243 struct AddressPointLocation {
244 unsigned VTableIndex, AddressPointIndex;
246 typedef llvm::DenseMap<BaseSubobject, AddressPointLocation>
250 // Stores the component indices of the first component of each virtual table in
251 // the virtual table group. To save a little memory in the common case where
252 // the vtable group contains a single vtable, an empty vector here represents
254 OwningArrayRef<size_t> VTableIndices;
256 OwningArrayRef<VTableComponent> VTableComponents;
258 /// \brief Contains thunks needed by vtables, sorted by indices.
259 OwningArrayRef<VTableThunkTy> VTableThunks;
261 /// \brief Address points for all vtables.
262 AddressPointsMapTy AddressPoints;
265 VTableLayout(ArrayRef<size_t> VTableIndices,
266 ArrayRef<VTableComponent> VTableComponents,
267 ArrayRef<VTableThunkTy> VTableThunks,
268 const AddressPointsMapTy &AddressPoints);
271 ArrayRef<VTableComponent> vtable_components() const {
272 return VTableComponents;
275 ArrayRef<VTableThunkTy> vtable_thunks() const {
279 AddressPointLocation getAddressPoint(BaseSubobject Base) const {
280 assert(AddressPoints.count(Base) && "Did not find address point!");
281 return AddressPoints.find(Base)->second;
284 const AddressPointsMapTy &getAddressPoints() const {
285 return AddressPoints;
288 size_t getNumVTables() const {
289 if (VTableIndices.empty())
291 return VTableIndices.size();
294 size_t getVTableOffset(size_t i) const {
295 if (VTableIndices.empty()) {
299 return VTableIndices[i];
302 size_t getVTableSize(size_t i) const {
303 if (VTableIndices.empty()) {
305 return vtable_components().size();
308 size_t thisIndex = VTableIndices[i];
309 size_t nextIndex = (i + 1 == VTableIndices.size())
310 ? vtable_components().size()
311 : VTableIndices[i + 1];
312 return nextIndex - thisIndex;
316 class VTableContextBase {
318 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
320 bool isMicrosoft() const { return IsMicrosoftABI; }
322 virtual ~VTableContextBase() {}
325 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
327 /// \brief Contains all thunks that a given method decl will need.
330 /// Compute and store all vtable related information (vtable layout, vbase
331 /// offset offsets, thunks etc) for the given record decl.
332 virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
334 VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
337 virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
338 const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
339 computeVTableRelatedInformation(MD->getParent());
341 // This assumes that all the destructors present in the vtable
342 // use exactly the same set of thunks.
343 ThunksMapTy::const_iterator I = Thunks.find(MD);
344 if (I == Thunks.end()) {
345 // We did not find a thunk for this method.
355 class ItaniumVTableContext : public VTableContextBase {
358 /// \brief Contains the index (relative to the vtable address point)
359 /// where the function pointer for a virtual function is stored.
360 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
361 MethodVTableIndicesTy MethodVTableIndices;
363 typedef llvm::DenseMap<const CXXRecordDecl *,
364 std::unique_ptr<const VTableLayout>>
366 VTableLayoutMapTy VTableLayouts;
368 typedef std::pair<const CXXRecordDecl *,
369 const CXXRecordDecl *> ClassPairTy;
371 /// \brief vtable offsets for offsets of virtual bases of a class.
373 /// Contains the vtable offset (relative to the address point) in chars
374 /// where the offsets for virtual bases of a class are stored.
375 typedef llvm::DenseMap<ClassPairTy, CharUnits>
376 VirtualBaseClassOffsetOffsetsMapTy;
377 VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
379 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
382 ItaniumVTableContext(ASTContext &Context);
383 ~ItaniumVTableContext() override;
385 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
386 computeVTableRelatedInformation(RD);
387 assert(VTableLayouts.count(RD) && "No layout for this record decl!");
389 return *VTableLayouts[RD];
392 std::unique_ptr<VTableLayout> createConstructionVTableLayout(
393 const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
394 bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass);
396 /// \brief Locate a virtual function in the vtable.
398 /// Return the index (relative to the vtable address point) where the
399 /// function pointer for the given virtual function is stored.
400 uint64_t getMethodVTableIndex(GlobalDecl GD);
402 /// Return the offset in chars (relative to the vtable address point) where
403 /// the offset of the virtual base that contains the given base is stored,
404 /// otherwise, if no virtual base contains the given class, return 0.
406 /// Base must be a virtual base class or an unambiguous base.
407 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
408 const CXXRecordDecl *VBase);
410 static bool classof(const VTableContextBase *VT) {
411 return !VT->isMicrosoft();
415 /// Holds information about the inheritance path to a virtual base or function
416 /// table pointer. A record may contain as many vfptrs or vbptrs as there are
419 typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
421 VPtrInfo(const CXXRecordDecl *RD)
422 : ObjectWithVPtr(RD), IntroducingObject(RD), NextBaseToMangle(RD) {}
424 /// This is the most derived class that has this vptr at offset zero. When
425 /// single inheritance is used, this is always the most derived class. If
426 /// multiple inheritance is used, it may be any direct or indirect base.
427 const CXXRecordDecl *ObjectWithVPtr;
429 /// This is the class that introduced the vptr by declaring new virtual
430 /// methods or virtual bases.
431 const CXXRecordDecl *IntroducingObject;
433 /// IntroducingObject is at this offset from its containing complete object or
435 CharUnits NonVirtualOffset;
437 /// The bases from the inheritance path that got used to mangle the vbtable
438 /// name. This is not really a full path like a CXXBasePath. It holds the
439 /// subset of records that need to be mangled into the vbtable symbol name in
440 /// order to get a unique name.
441 BasePath MangledPath;
443 /// The next base to push onto the mangled path if this path is ambiguous in a
444 /// derived class. If it's null, then it's already been pushed onto the path.
445 const CXXRecordDecl *NextBaseToMangle;
447 /// The set of possibly indirect vbases that contain this vbtable. When a
448 /// derived class indirectly inherits from the same vbase twice, we only keep
449 /// vtables and their paths from the first instance.
450 BasePath ContainingVBases;
452 /// This holds the base classes path from the complete type to the first base
453 /// with the given vfptr offset, in the base-to-derived order. Only used for
455 BasePath PathToIntroducingObject;
457 /// Static offset from the top of the most derived class to this vfptr,
458 /// including any virtual base offset. Only used for vftables.
459 CharUnits FullOffsetInMDC;
461 /// The vptr is stored inside the non-virtual component of this virtual base.
462 const CXXRecordDecl *getVBaseWithVPtr() const {
463 return ContainingVBases.empty() ? nullptr : ContainingVBases.front();
467 typedef SmallVector<std::unique_ptr<VPtrInfo>, 2> VPtrInfoVector;
469 /// All virtual base related information about a given record decl. Includes
470 /// information on all virtual base tables and the path components that are used
472 struct VirtualBaseInfo {
473 /// A map from virtual base to vbtable index for doing a conversion from the
474 /// the derived class to the a base.
475 llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices;
477 /// Information on all virtual base tables used when this record is the most
479 VPtrInfoVector VBPtrPaths;
482 class MicrosoftVTableContext : public VTableContextBase {
484 struct MethodVFTableLocation {
485 /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
486 uint64_t VBTableIndex;
488 /// If nonnull, holds the last vbase which contains the vfptr that the
489 /// method definition is adjusted to.
490 const CXXRecordDecl *VBase;
492 /// This is the offset of the vfptr from the start of the last vbase, or the
493 /// complete type if there are no virtual bases.
494 CharUnits VFPtrOffset;
496 /// Method's index in the vftable.
499 MethodVFTableLocation()
500 : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
503 MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
504 CharUnits VFPtrOffset, uint64_t Index)
505 : VBTableIndex(VBTableIndex), VBase(VBase),
506 VFPtrOffset(VFPtrOffset), Index(Index) {}
508 bool operator<(const MethodVFTableLocation &other) const {
509 if (VBTableIndex != other.VBTableIndex) {
510 assert(VBase != other.VBase);
511 return VBTableIndex < other.VBTableIndex;
513 return std::tie(VFPtrOffset, Index) <
514 std::tie(other.VFPtrOffset, other.Index);
521 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
522 MethodVFTableLocationsTy;
523 MethodVFTableLocationsTy MethodVFTableLocations;
525 typedef llvm::DenseMap<const CXXRecordDecl *, VPtrInfoVector>
527 VFPtrLocationsMapTy VFPtrLocations;
529 typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
530 typedef llvm::DenseMap<VFTableIdTy, std::unique_ptr<const VTableLayout>>
532 VFTableLayoutMapTy VFTableLayouts;
534 llvm::DenseMap<const CXXRecordDecl *, std::unique_ptr<VirtualBaseInfo>>
537 void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result);
539 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
541 void dumpMethodLocations(const CXXRecordDecl *RD,
542 const MethodVFTableLocationsTy &NewMethods,
545 const VirtualBaseInfo &
546 computeVBTableRelatedInformation(const CXXRecordDecl *RD);
548 void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD,
549 VPtrInfoVector &Paths);
552 MicrosoftVTableContext(ASTContext &Context)
553 : VTableContextBase(/*MS=*/true), Context(Context) {}
555 ~MicrosoftVTableContext() override;
557 const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD);
559 const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
560 CharUnits VFPtrOffset);
562 const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
564 const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override {
565 // Complete destructors don't have a slot in a vftable, so no thunks needed.
566 if (isa<CXXDestructorDecl>(GD.getDecl()) &&
567 GD.getDtorType() == Dtor_Complete)
569 return VTableContextBase::getThunkInfo(GD);
572 /// \brief Returns the index of VBase in the vbtable of Derived.
573 /// VBase must be a morally virtual base of Derived.
574 /// The vbtable is an array of i32 offsets. The first entry is a self entry,
575 /// and the rest are offsets from the vbptr to virtual bases.
576 unsigned getVBTableIndex(const CXXRecordDecl *Derived,
577 const CXXRecordDecl *VBase);
579 const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD);
581 static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }