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/SetVector.h"
23 #include "llvm/ADT/DenseSet.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
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(getKind() == CK_RTTI && "Invalid component kind!");
126 return reinterpret_cast<CXXRecordDecl *>(getPointer());
129 const CXXMethodDecl *getFunctionDecl() const {
130 assert(getKind() == CK_FunctionPointer);
132 return reinterpret_cast<CXXMethodDecl *>(getPointer());
135 const CXXDestructorDecl *getDestructorDecl() const {
136 assert((getKind() == CK_CompleteDtorPointer ||
137 getKind() == CK_DeletingDtorPointer) && "Invalid component kind!");
139 return reinterpret_cast<CXXDestructorDecl *>(getPointer());
142 const CXXMethodDecl *getUnusedFunctionDecl() const {
143 assert(getKind() == CK_UnusedFunctionPointer);
145 return reinterpret_cast<CXXMethodDecl *>(getPointer());
149 VTableComponent(Kind ComponentKind, CharUnits Offset) {
150 assert((ComponentKind == CK_VCallOffset ||
151 ComponentKind == CK_VBaseOffset ||
152 ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
153 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
154 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
156 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
159 VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
160 assert((ComponentKind == CK_RTTI ||
161 ComponentKind == CK_FunctionPointer ||
162 ComponentKind == CK_CompleteDtorPointer ||
163 ComponentKind == CK_DeletingDtorPointer ||
164 ComponentKind == CK_UnusedFunctionPointer) &&
165 "Invalid component kind!");
167 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
169 Value = Ptr | ComponentKind;
172 CharUnits getOffset() const {
173 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
174 getKind() == CK_OffsetToTop) && "Invalid component kind!");
176 return CharUnits::fromQuantity(Value >> 3);
179 uintptr_t getPointer() const {
180 assert((getKind() == CK_RTTI ||
181 getKind() == CK_FunctionPointer ||
182 getKind() == CK_CompleteDtorPointer ||
183 getKind() == CK_DeletingDtorPointer ||
184 getKind() == CK_UnusedFunctionPointer) &&
185 "Invalid component kind!");
187 return static_cast<uintptr_t>(Value & ~7ULL);
190 explicit VTableComponent(uint64_t Value)
193 /// The kind is stored in the lower 3 bits of the value. For offsets, we
194 /// make use of the facts that classes can't be larger than 2^55 bytes,
195 /// so we store the offset in the lower part of the 61 bits that remain.
196 /// (The reason that we're not simply using a PointerIntPair here is that we
197 /// need the offsets to be 64-bit, even when on a 32-bit machine).
203 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
205 typedef const VTableComponent *vtable_component_iterator;
206 typedef const VTableThunkTy *vtable_thunk_iterator;
208 typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
210 uint64_t NumVTableComponents;
211 llvm::OwningArrayPtr<VTableComponent> VTableComponents;
213 /// \brief Contains thunks needed by vtables, sorted by indices.
214 uint64_t NumVTableThunks;
215 llvm::OwningArrayPtr<VTableThunkTy> VTableThunks;
217 /// \brief Address points for all vtables.
218 AddressPointsMapTy AddressPoints;
223 VTableLayout(uint64_t NumVTableComponents,
224 const VTableComponent *VTableComponents,
225 uint64_t NumVTableThunks,
226 const VTableThunkTy *VTableThunks,
227 const AddressPointsMapTy &AddressPoints,
228 bool IsMicrosoftABI);
231 uint64_t getNumVTableComponents() const {
232 return NumVTableComponents;
235 vtable_component_iterator vtable_component_begin() const {
236 return VTableComponents.get();
239 vtable_component_iterator vtable_component_end() const {
240 return VTableComponents.get() + NumVTableComponents;
243 uint64_t getNumVTableThunks() const { return NumVTableThunks; }
245 vtable_thunk_iterator vtable_thunk_begin() const {
246 return VTableThunks.get();
249 vtable_thunk_iterator vtable_thunk_end() const {
250 return VTableThunks.get() + NumVTableThunks;
253 uint64_t getAddressPoint(BaseSubobject Base) const {
254 assert(AddressPoints.count(Base) &&
255 "Did not find address point!");
257 uint64_t AddressPoint = AddressPoints.lookup(Base);
258 assert(AddressPoint != 0 || IsMicrosoftABI);
259 (void)IsMicrosoftABI;
264 const AddressPointsMapTy &getAddressPoints() const {
265 return AddressPoints;
269 class VTableContextBase {
271 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
274 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
276 /// \brief Contains all thunks that a given method decl will need.
279 /// Compute and store all vtable related information (vtable layout, vbase
280 /// offset offsets, thunks etc) for the given record decl.
281 virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
283 virtual ~VTableContextBase() {}
286 virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
287 const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
288 computeVTableRelatedInformation(MD->getParent());
290 // This assumes that all the destructors present in the vtable
291 // use exactly the same set of thunks.
292 ThunksMapTy::const_iterator I = Thunks.find(MD);
293 if (I == Thunks.end()) {
294 // We did not find a thunk for this method.
302 class ItaniumVTableContext : public VTableContextBase {
306 /// \brief Contains the index (relative to the vtable address point)
307 /// where the function pointer for a virtual function is stored.
308 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
309 MethodVTableIndicesTy MethodVTableIndices;
311 typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
313 VTableLayoutMapTy VTableLayouts;
315 typedef std::pair<const CXXRecordDecl *,
316 const CXXRecordDecl *> ClassPairTy;
318 /// \brief vtable offsets for offsets of virtual bases of a class.
320 /// Contains the vtable offset (relative to the address point) in chars
321 /// where the offsets for virtual bases of a class are stored.
322 typedef llvm::DenseMap<ClassPairTy, CharUnits>
323 VirtualBaseClassOffsetOffsetsMapTy;
324 VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
326 void computeVTableRelatedInformation(const CXXRecordDecl *RD);
329 ItaniumVTableContext(ASTContext &Context);
330 ~ItaniumVTableContext();
332 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
333 computeVTableRelatedInformation(RD);
334 assert(VTableLayouts.count(RD) && "No layout for this record decl!");
336 return *VTableLayouts[RD];
340 createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
341 CharUnits MostDerivedClassOffset,
342 bool MostDerivedClassIsVirtual,
343 const CXXRecordDecl *LayoutClass);
345 /// \brief Locate a virtual function in the vtable.
347 /// Return the index (relative to the vtable address point) where the
348 /// function pointer for the given virtual function is stored.
349 uint64_t getMethodVTableIndex(GlobalDecl GD);
351 /// Return the offset in chars (relative to the vtable address point) where
352 /// the offset of the virtual base that contains the given base is stored,
353 /// otherwise, if no virtual base contains the given class, return 0.
355 /// Base must be a virtual base class or an unambiguous base.
356 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
357 const CXXRecordDecl *VBase);
361 typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
363 // Don't pass the PathToMangle as it should be calculated later.
364 VFPtrInfo(CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr)
365 : VBTableIndex(0), LastVBase(0), VFPtrOffset(VFPtrOffset),
366 PathToBaseWithVFPtr(PathToBaseWithVFPtr), VFPtrFullOffset(VFPtrOffset) {
369 // Don't pass the PathToMangle as it should be calculated later.
370 VFPtrInfo(uint64_t VBTableIndex, const CXXRecordDecl *LastVBase,
371 CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr,
372 CharUnits VFPtrFullOffset)
373 : VBTableIndex(VBTableIndex), LastVBase(LastVBase),
374 VFPtrOffset(VFPtrOffset), PathToBaseWithVFPtr(PathToBaseWithVFPtr),
375 VFPtrFullOffset(VFPtrFullOffset) {
376 assert(VBTableIndex && "The full constructor should only be used "
377 "for vfptrs in virtual bases");
381 /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
382 uint64_t VBTableIndex;
384 /// Stores the last vbase on the path from the complete type to the vfptr.
385 const CXXRecordDecl *LastVBase;
387 /// This is the offset of the vfptr from the start of the last vbase,
388 /// or the complete type if there are no virtual bases.
389 CharUnits VFPtrOffset;
391 /// This holds the base classes path from the complete type to the first base
392 /// with the given vfptr offset, in the base-to-derived order.
393 BasePath PathToBaseWithVFPtr;
395 /// This holds the subset of records that need to be mangled into the vftable
396 /// symbol name in order to get a unique name, in the derived-to-base order.
397 BasePath PathToMangle;
399 /// This is the full offset of the vfptr from the start of the complete type.
400 CharUnits VFPtrFullOffset;
403 class MicrosoftVTableContext : public VTableContextBase {
405 struct MethodVFTableLocation {
406 /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
407 uint64_t VBTableIndex;
409 /// If nonnull, holds the last vbase which contains the vfptr that the
410 /// method definition is adjusted to.
411 const CXXRecordDecl *VBase;
413 /// This is the offset of the vfptr from the start of the last vbase, or the
414 /// complete type if there are no virtual bases.
415 CharUnits VFPtrOffset;
417 /// Method's index in the vftable.
420 MethodVFTableLocation()
421 : VBTableIndex(0), VBase(0), VFPtrOffset(CharUnits::Zero()),
424 MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
425 CharUnits VFPtrOffset, uint64_t Index)
426 : VBTableIndex(VBTableIndex), VBase(VBase),
427 VFPtrOffset(VFPtrOffset), Index(Index) {}
429 bool operator<(const MethodVFTableLocation &other) const {
430 if (VBTableIndex != other.VBTableIndex) {
431 assert(VBase != other.VBase);
432 return VBTableIndex < other.VBTableIndex;
434 if (VFPtrOffset != other.VFPtrOffset)
435 return VFPtrOffset < other.VFPtrOffset;
436 if (Index != other.Index)
437 return Index < other.Index;
442 typedef SmallVector<VFPtrInfo, 1> VFPtrListTy;
447 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
448 MethodVFTableLocationsTy;
449 MethodVFTableLocationsTy MethodVFTableLocations;
451 typedef llvm::DenseMap<const CXXRecordDecl *, VFPtrListTy>
453 VFPtrLocationsMapTy VFPtrLocations;
455 typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
456 typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
457 VFTableLayoutMapTy VFTableLayouts;
459 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
460 void enumerateVFPtrs(const CXXRecordDecl *MostDerivedClass,
461 const ASTRecordLayout &MostDerivedClassLayout,
462 BaseSubobject Base, const CXXRecordDecl *LastVBase,
463 const VFPtrInfo::BasePath &PathFromCompleteClass,
464 BasesSetVectorTy &VisitedVBases,
465 MicrosoftVTableContext::VFPtrListTy &Result);
467 void enumerateVFPtrs(const CXXRecordDecl *ForClass,
468 MicrosoftVTableContext::VFPtrListTy &Result);
470 void computeVTableRelatedInformation(const CXXRecordDecl *RD);
472 void dumpMethodLocations(const CXXRecordDecl *RD,
473 const MethodVFTableLocationsTy &NewMethods,
476 typedef std::pair<const CXXRecordDecl *, const CXXRecordDecl *> ClassPairTy;
477 typedef llvm::DenseMap<ClassPairTy, unsigned> VBTableIndicesTy;
478 VBTableIndicesTy VBTableIndices;
479 llvm::DenseSet<const CXXRecordDecl *> ComputedVBTableIndices;
481 void computeVBTableRelatedInformation(const CXXRecordDecl *RD);
484 MicrosoftVTableContext(ASTContext &Context) : Context(Context) {}
486 ~MicrosoftVTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); }
488 const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD);
490 const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
491 CharUnits VFPtrOffset);
493 const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
495 const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
496 // Complete destructors don't have a slot in a vftable, so no thunks needed.
497 if (isa<CXXDestructorDecl>(GD.getDecl()) &&
498 GD.getDtorType() == Dtor_Complete)
500 return VTableContextBase::getThunkInfo(GD);
503 /// \brief Returns the index of VBase in the vbtable of Derived.
504 /// VBase must be a morally virtual base of Derived.
505 /// The vbtable is an array of i32 offsets. The first entry is a self entry,
506 /// and the rest are offsets from the vbptr to virtual bases.
507 unsigned getVBTableIndex(const CXXRecordDecl *Derived,
508 const CXXRecordDecl *VBase) {
509 computeVBTableRelatedInformation(Derived);
510 ClassPairTy Pair(Derived, VBase);
511 assert(VBTableIndices.count(Pair) == 1 &&
512 "VBase must be a vbase of Derived");
513 return VBTableIndices[Pair];