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

source code of clang/include/clang/AST/VTableBuilder.h