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