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"
23 #include "llvm/ADT/SetVector.h"
30 /// \brief Represents a single component in a vtable.
31 class VTableComponent {
40 /// \brief A pointer to the complete destructor.
41 CK_CompleteDtorPointer,
43 /// \brief A pointer to the deleting destructor.
44 CK_DeletingDtorPointer,
46 /// \brief An entry that is never used.
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
54 VTableComponent() = default;
56 static VTableComponent MakeVCallOffset(CharUnits Offset) {
57 return VTableComponent(CK_VCallOffset, Offset);
60 static VTableComponent MakeVBaseOffset(CharUnits Offset) {
61 return VTableComponent(CK_VBaseOffset, Offset);
64 static VTableComponent MakeOffsetToTop(CharUnits Offset) {
65 return VTableComponent(CK_OffsetToTop, Offset);
68 static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
69 return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
72 static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
73 assert(!isa<CXXDestructorDecl>(MD) &&
74 "Don't use MakeFunction with destructors!");
76 return VTableComponent(CK_FunctionPointer,
77 reinterpret_cast<uintptr_t>(MD));
80 static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
81 return VTableComponent(CK_CompleteDtorPointer,
82 reinterpret_cast<uintptr_t>(DD));
85 static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
86 return VTableComponent(CK_DeletingDtorPointer,
87 reinterpret_cast<uintptr_t>(DD));
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));
97 static VTableComponent getFromOpaqueInteger(uint64_t I) {
98 return VTableComponent(I);
101 /// \brief Get the kind of this vtable component.
102 Kind getKind() const {
103 return (Kind)(Value & 0x7);
106 CharUnits getVCallOffset() const {
107 assert(getKind() == CK_VCallOffset && "Invalid component kind!");
112 CharUnits getVBaseOffset() const {
113 assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
118 CharUnits getOffsetToTop() const {
119 assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
124 const CXXRecordDecl *getRTTIDecl() const {
125 assert(isRTTIKind() && "Invalid component kind!");
126 return reinterpret_cast<CXXRecordDecl *>(getPointer());
129 const CXXMethodDecl *getFunctionDecl() const {
130 assert(isFunctionPointerKind() && "Invalid component kind!");
131 if (isDestructorKind())
132 return getDestructorDecl();
133 return reinterpret_cast<CXXMethodDecl *>(getPointer());
136 const CXXDestructorDecl *getDestructorDecl() const {
137 assert(isDestructorKind() && "Invalid component kind!");
138 return reinterpret_cast<CXXDestructorDecl *>(getPointer());
141 const CXXMethodDecl *getUnusedFunctionDecl() const {
142 assert(getKind() == CK_UnusedFunctionPointer && "Invalid component kind!");
143 return reinterpret_cast<CXXMethodDecl *>(getPointer());
146 bool isDestructorKind() const { return isDestructorKind(getKind()); }
148 bool isUsedFunctionPointerKind() const {
149 return isUsedFunctionPointerKind(getKind());
152 bool isFunctionPointerKind() const {
153 return isFunctionPointerKind(getKind());
156 bool isRTTIKind() const { return isRTTIKind(getKind()); }
159 static bool isFunctionPointerKind(Kind ComponentKind) {
160 return isUsedFunctionPointerKind(ComponentKind) ||
161 ComponentKind == CK_UnusedFunctionPointer;
163 static bool isUsedFunctionPointerKind(Kind ComponentKind) {
164 return ComponentKind == CK_FunctionPointer ||
165 isDestructorKind(ComponentKind);
167 static bool isDestructorKind(Kind ComponentKind) {
168 return ComponentKind == CK_CompleteDtorPointer ||
169 ComponentKind == CK_DeletingDtorPointer;
171 static bool isRTTIKind(Kind ComponentKind) {
172 return ComponentKind == CK_RTTI;
175 VTableComponent(Kind ComponentKind, CharUnits Offset) {
176 assert((ComponentKind == CK_VCallOffset ||
177 ComponentKind == CK_VBaseOffset ||
178 ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
179 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
180 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
182 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
185 VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
186 assert((isRTTIKind(ComponentKind) || isFunctionPointerKind(ComponentKind)) &&
187 "Invalid component kind!");
189 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
191 Value = Ptr | ComponentKind;
194 CharUnits getOffset() const {
195 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
196 getKind() == CK_OffsetToTop) && "Invalid component kind!");
198 return CharUnits::fromQuantity(Value >> 3);
201 uintptr_t getPointer() const {
202 assert((getKind() == CK_RTTI || isFunctionPointerKind()) &&
203 "Invalid component kind!");
205 return static_cast<uintptr_t>(Value & ~7ULL);
208 explicit VTableComponent(uint64_t Value)
211 /// The kind is stored in the lower 3 bits of the value. For offsets, we
212 /// make use of the facts that classes can't be larger than 2^55 bytes,
213 /// so we store the offset in the lower part of the 61 bits that remain.
214 /// (The reason that we're not simply using a PointerIntPair here is that we
215 /// need the offsets to be 64-bit, even when on a 32-bit machine).
221 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
223 typedef const VTableComponent *vtable_component_iterator;
224 typedef const VTableThunkTy *vtable_thunk_iterator;
225 typedef llvm::iterator_range<vtable_component_iterator>
226 vtable_component_range;
228 typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
231 uint64_t NumVTableComponents;
232 std::unique_ptr<VTableComponent[]> VTableComponents;
234 /// \brief Contains thunks needed by vtables, sorted by indices.
235 uint64_t NumVTableThunks;
236 std::unique_ptr<VTableThunkTy[]> VTableThunks;
238 /// \brief Address points for all vtables.
239 AddressPointsMapTy AddressPoints;
244 VTableLayout(uint64_t NumVTableComponents,
245 const VTableComponent *VTableComponents,
246 uint64_t NumVTableThunks,
247 const VTableThunkTy *VTableThunks,
248 const AddressPointsMapTy &AddressPoints,
249 bool IsMicrosoftABI);
252 uint64_t getNumVTableComponents() const {
253 return NumVTableComponents;
256 vtable_component_range vtable_components() const {
257 return vtable_component_range(vtable_component_begin(),
258 vtable_component_end());
261 vtable_component_iterator vtable_component_begin() const {
262 return VTableComponents.get();
265 vtable_component_iterator vtable_component_end() const {
266 return VTableComponents.get() + NumVTableComponents;
269 uint64_t getNumVTableThunks() const { return NumVTableThunks; }
271 vtable_thunk_iterator vtable_thunk_begin() const {
272 return VTableThunks.get();
275 vtable_thunk_iterator vtable_thunk_end() const {
276 return VTableThunks.get() + NumVTableThunks;
279 uint64_t getAddressPoint(BaseSubobject Base) const {
280 assert(AddressPoints.count(Base) &&
281 "Did not find address point!");
283 uint64_t AddressPoint = AddressPoints.lookup(Base);
284 assert(AddressPoint != 0 || IsMicrosoftABI);
285 (void)IsMicrosoftABI;
290 const AddressPointsMapTy &getAddressPoints() const {
291 return AddressPoints;
295 class VTableContextBase {
297 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
299 bool isMicrosoft() const { return IsMicrosoftABI; }
301 virtual ~VTableContextBase() {}
304 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
306 /// \brief Contains all thunks that a given method decl will need.
309 /// Compute and store all vtable related information (vtable layout, vbase
310 /// offset offsets, thunks etc) for the given record decl.
311 virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
313 VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
316 virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
317 const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
318 computeVTableRelatedInformation(MD->getParent());
320 // This assumes that all the destructors present in the vtable
321 // use exactly the same set of thunks.
322 ThunksMapTy::const_iterator I = Thunks.find(MD);
323 if (I == Thunks.end()) {
324 // We did not find a thunk for this method.
334 class ItaniumVTableContext : public VTableContextBase {
337 /// \brief Contains the index (relative to the vtable address point)
338 /// where the function pointer for a virtual function is stored.
339 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
340 MethodVTableIndicesTy MethodVTableIndices;
342 typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
344 VTableLayoutMapTy VTableLayouts;
346 typedef std::pair<const CXXRecordDecl *,
347 const CXXRecordDecl *> ClassPairTy;
349 /// \brief vtable offsets for offsets of virtual bases of a class.
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;
357 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
360 ItaniumVTableContext(ASTContext &Context);
361 ~ItaniumVTableContext() override;
363 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
364 computeVTableRelatedInformation(RD);
365 assert(VTableLayouts.count(RD) && "No layout for this record decl!");
367 return *VTableLayouts[RD];
371 createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
372 CharUnits MostDerivedClassOffset,
373 bool MostDerivedClassIsVirtual,
374 const CXXRecordDecl *LayoutClass);
376 /// \brief Locate a virtual function in the vtable.
378 /// Return the index (relative to the vtable address point) where the
379 /// function pointer for the given virtual function is stored.
380 uint64_t getMethodVTableIndex(GlobalDecl GD);
382 /// Return the offset in chars (relative to the vtable address point) where
383 /// the offset of the virtual base that contains the given base is stored,
384 /// otherwise, if no virtual base contains the given class, return 0.
386 /// Base must be a virtual base class or an unambiguous base.
387 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
388 const CXXRecordDecl *VBase);
390 static bool classof(const VTableContextBase *VT) {
391 return !VT->isMicrosoft();
395 /// Holds information about the inheritance path to a virtual base or function
396 /// table pointer. A record may contain as many vfptrs or vbptrs as there are
399 typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
401 VPtrInfo(const CXXRecordDecl *RD)
402 : ReusingBase(RD), BaseWithVPtr(RD), NextBaseToMangle(RD) {}
404 /// The vtable will hold all of the virtual bases or virtual methods of
405 /// ReusingBase. This may or may not be the same class as VPtrSubobject.Base.
406 /// A derived class will reuse the vptr of the first non-virtual base
407 /// subobject that has one.
408 const CXXRecordDecl *ReusingBase;
410 /// BaseWithVPtr is at this offset from its containing complete object or
412 CharUnits NonVirtualOffset;
414 /// The vptr is stored inside this subobject.
415 const CXXRecordDecl *BaseWithVPtr;
417 /// The bases from the inheritance path that got used to mangle the vbtable
418 /// name. This is not really a full path like a CXXBasePath. It holds the
419 /// subset of records that need to be mangled into the vbtable symbol name in
420 /// order to get a unique name.
421 BasePath MangledPath;
423 /// The next base to push onto the mangled path if this path is ambiguous in a
424 /// derived class. If it's null, then it's already been pushed onto the path.
425 const CXXRecordDecl *NextBaseToMangle;
427 /// The set of possibly indirect vbases that contain this vbtable. When a
428 /// derived class indirectly inherits from the same vbase twice, we only keep
429 /// vtables and their paths from the first instance.
430 BasePath ContainingVBases;
432 /// This holds the base classes path from the complete type to the first base
433 /// with the given vfptr offset, in the base-to-derived order. Only used for
435 BasePath PathToBaseWithVPtr;
437 /// Static offset from the top of the most derived class to this vfptr,
438 /// including any virtual base offset. Only used for vftables.
439 CharUnits FullOffsetInMDC;
441 /// The vptr is stored inside the non-virtual component of this virtual base.
442 const CXXRecordDecl *getVBaseWithVPtr() const {
443 return ContainingVBases.empty() ? nullptr : ContainingVBases.front();
447 typedef SmallVector<VPtrInfo *, 2> VPtrInfoVector;
449 /// All virtual base related information about a given record decl. Includes
450 /// information on all virtual base tables and the path components that are used
452 struct VirtualBaseInfo {
453 ~VirtualBaseInfo() { llvm::DeleteContainerPointers(VBPtrPaths); }
455 /// A map from virtual base to vbtable index for doing a conversion from the
456 /// the derived class to the a base.
457 llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices;
459 /// Information on all virtual base tables used when this record is the most
461 VPtrInfoVector VBPtrPaths;
464 class MicrosoftVTableContext : public VTableContextBase {
466 struct MethodVFTableLocation {
467 /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
468 uint64_t VBTableIndex;
470 /// If nonnull, holds the last vbase which contains the vfptr that the
471 /// method definition is adjusted to.
472 const CXXRecordDecl *VBase;
474 /// This is the offset of the vfptr from the start of the last vbase, or the
475 /// complete type if there are no virtual bases.
476 CharUnits VFPtrOffset;
478 /// Method's index in the vftable.
481 MethodVFTableLocation()
482 : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
485 MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
486 CharUnits VFPtrOffset, uint64_t Index)
487 : VBTableIndex(VBTableIndex), VBase(VBase),
488 VFPtrOffset(VFPtrOffset), Index(Index) {}
490 bool operator<(const MethodVFTableLocation &other) const {
491 if (VBTableIndex != other.VBTableIndex) {
492 assert(VBase != other.VBase);
493 return VBTableIndex < other.VBTableIndex;
495 return std::tie(VFPtrOffset, Index) <
496 std::tie(other.VFPtrOffset, other.Index);
503 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
504 MethodVFTableLocationsTy;
505 MethodVFTableLocationsTy MethodVFTableLocations;
507 typedef llvm::DenseMap<const CXXRecordDecl *, VPtrInfoVector *>
509 VFPtrLocationsMapTy VFPtrLocations;
511 typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
512 typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
513 VFTableLayoutMapTy VFTableLayouts;
515 llvm::DenseMap<const CXXRecordDecl *, VirtualBaseInfo *> VBaseInfo;
517 void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result);
519 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
521 void dumpMethodLocations(const CXXRecordDecl *RD,
522 const MethodVFTableLocationsTy &NewMethods,
525 const VirtualBaseInfo *
526 computeVBTableRelatedInformation(const CXXRecordDecl *RD);
528 void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD,
529 VPtrInfoVector &Paths);
532 MicrosoftVTableContext(ASTContext &Context)
533 : VTableContextBase(/*MS=*/true), Context(Context) {}
535 ~MicrosoftVTableContext() override;
537 const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD);
539 const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
540 CharUnits VFPtrOffset);
542 const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
544 const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override {
545 // Complete destructors don't have a slot in a vftable, so no thunks needed.
546 if (isa<CXXDestructorDecl>(GD.getDecl()) &&
547 GD.getDtorType() == Dtor_Complete)
549 return VTableContextBase::getThunkInfo(GD);
552 /// \brief Returns the index of VBase in the vbtable of Derived.
553 /// VBase must be a morally virtual base of Derived.
554 /// The vbtable is an array of i32 offsets. The first entry is a self entry,
555 /// and the rest are offsets from the vbptr to virtual bases.
556 unsigned getVBTableIndex(const CXXRecordDecl *Derived,
557 const CXXRecordDecl *VBase);
559 const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD);
561 static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }