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
241private:
242  // Stores the component indices of the first component of each virtual table in
243  // the virtual table group. To save a little memory in the common case where
244  // the vtable group contains a single vtable, an empty vector here represents
245  // the vector {0}.
246  OwningArrayRef<size_t> VTableIndices;
247
248  OwningArrayRef<VTableComponent> VTableComponents;
249
250  /// Contains thunks needed by vtables, sorted by indices.
251  OwningArrayRef<VTableThunkTy> VTableThunks;
252
253  /// Address points for all vtables.
254  AddressPointsMapTy AddressPoints;
255
256public:
257  VTableLayout(ArrayRef<size_t> VTableIndices,
258               ArrayRef<VTableComponent> VTableComponents,
259               ArrayRef<VTableThunkTy> VTableThunks,
260               const AddressPointsMapTy &AddressPoints);
261  ~VTableLayout();
262
263  ArrayRef<VTableComponent> vtable_components() const {
264    return VTableComponents;
265  }
266
267  ArrayRef<VTableThunkTy> vtable_thunks() const {
268    return VTableThunks;
269  }
270
271  AddressPointLocation getAddressPoint(BaseSubobject Base) const {
272    assert(AddressPoints.count(Base) && "Did not find address point!");
273    return AddressPoints.find(Base)->second;
274  }
275
276  const AddressPointsMapTy &getAddressPoints() const {
277    return AddressPoints;
278  }
279
280  size_t getNumVTables() const {
281    if (VTableIndices.empty())
282      return 1;
283    return VTableIndices.size();
284  }
285
286  size_t getVTableOffset(size_t i) const {
287    if (VTableIndices.empty()) {
288      assert(i == 0);
289      return 0;
290    }
291    return VTableIndices[i];
292  }
293
294  size_t getVTableSize(size_t i) const {
295    if (VTableIndices.empty()) {
296      assert(i == 0);
297      return vtable_components().size();
298    }
299
300    size_t thisIndex = VTableIndices[i];
301    size_t nextIndex = (i + 1 == VTableIndices.size())
302                           ? vtable_components().size()
303                           : VTableIndices[i + 1];
304    return nextIndex - thisIndex;
305  }
306};
307
308class VTableContextBase {
309public:
310  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
311
312  bool isMicrosoft() const { return IsMicrosoftABI; }
313
314  virtual ~VTableContextBase() {}
315
316protected:
317  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
318
319  /// Contains all thunks that a given method decl will need.
320  ThunksMapTy Thunks;
321
322  /// Compute and store all vtable related information (vtable layout, vbase
323  /// offset offsets, thunks etc) for the given record decl.
324  virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
325
326  VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
327
328public:
329  virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
330    const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
331    computeVTableRelatedInformation(MD->getParent());
332
333    // This assumes that all the destructors present in the vtable
334    // use exactly the same set of thunks.
335    ThunksMapTy::const_iterator I = Thunks.find(MD);
336    if (I == Thunks.end()) {
337      // We did not find a thunk for this method.
338      return nullptr;
339    }
340
341    return &I->second;
342  }
343
344  bool IsMicrosoftABI;
345};
346
347class ItaniumVTableContext : public VTableContextBase {
348private:
349
350  /// Contains the index (relative to the vtable address point)
351  /// where the function pointer for a virtual function is stored.
352  typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
353  MethodVTableIndicesTy MethodVTableIndices;
354
355  typedef llvm::DenseMap<const CXXRecordDecl *,
356                         std::unique_ptr<const VTableLayout>>
357      VTableLayoutMapTy;
358  VTableLayoutMapTy VTableLayouts;
359
360  typedef std::pair<const CXXRecordDecl *,
361                    const CXXRecordDecl *> ClassPairTy;
362
363  /// vtable offsets for offsets of virtual bases of a class.
364  ///
365  /// Contains the vtable offset (relative to the address point) in chars
366  /// where the offsets for virtual bases of a class are stored.
367  typedef llvm::DenseMap<ClassPairTy, CharUnits>
368    VirtualBaseClassOffsetOffsetsMapTy;
369  VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
370
371  void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
372
373public:
374  ItaniumVTableContext(ASTContext &Context);
375  ~ItaniumVTableContext() override;
376
377  const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
378    computeVTableRelatedInformation(RD);
379    assert(VTableLayouts.count(RD) && "No layout for this record decl!");
380
381    return *VTableLayouts[RD];
382  }
383
384  std::unique_ptr<VTableLayout> createConstructionVTableLayout(
385      const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
386      bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass);
387
388  /// Locate a virtual function in the vtable.
389  ///
390  /// Return the index (relative to the vtable address point) where the
391  /// function pointer for the given virtual function is stored.
392  uint64_t getMethodVTableIndex(GlobalDecl GD);
393
394  /// Return the offset in chars (relative to the vtable address point) where
395  /// the offset of the virtual base that contains the given base is stored,
396  /// otherwise, if no virtual base contains the given class, return 0.
397  ///
398  /// Base must be a virtual base class or an unambiguous base.
399  CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
400                                       const CXXRecordDecl *VBase);
401
402  static bool classof(const VTableContextBase *VT) {
403    return !VT->isMicrosoft();
404  }
405};
406
407/// Holds information about the inheritance path to a virtual base or function
408/// table pointer.  A record may contain as many vfptrs or vbptrs as there are
409/// base subobjects.
410struct VPtrInfo {
411  typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
412
413  VPtrInfo(const CXXRecordDecl *RD)
414      : ObjectWithVPtr(RD), IntroducingObject(RD), NextBaseToMangle(RD) {}
415
416  /// This is the most derived class that has this vptr at offset zero. When
417  /// single inheritance is used, this is always the most derived class. If
418  /// multiple inheritance is used, it may be any direct or indirect base.
419  const CXXRecordDecl *ObjectWithVPtr;
420
421  /// This is the class that introduced the vptr by declaring new virtual
422  /// methods or virtual bases.
423  const CXXRecordDecl *IntroducingObject;
424
425  /// IntroducingObject is at this offset from its containing complete object or
426  /// virtual base.
427  CharUnits NonVirtualOffset;
428
429  /// The bases from the inheritance path that got used to mangle the vbtable
430  /// name.  This is not really a full path like a CXXBasePath.  It holds the
431  /// subset of records that need to be mangled into the vbtable symbol name in
432  /// order to get a unique name.
433  BasePath MangledPath;
434
435  /// The next base to push onto the mangled path if this path is ambiguous in a
436  /// derived class.  If it's null, then it's already been pushed onto the path.
437  const CXXRecordDecl *NextBaseToMangle;
438
439  /// The set of possibly indirect vbases that contain this vbtable.  When a
440  /// derived class indirectly inherits from the same vbase twice, we only keep
441  /// vtables and their paths from the first instance.
442  BasePath ContainingVBases;
443
444  /// This holds the base classes path from the complete type to the first base
445  /// with the given vfptr offset, in the base-to-derived order.  Only used for
446  /// vftables.
447  BasePath PathToIntroducingObject;
448
449  /// Static offset from the top of the most derived class to this vfptr,
450  /// including any virtual base offset.  Only used for vftables.
451  CharUnits FullOffsetInMDC;
452
453  /// The vptr is stored inside the non-virtual component of this virtual base.
454  const CXXRecordDecl *getVBaseWithVPtr() const {
455    return ContainingVBases.empty() ? nullptr : ContainingVBases.front();
456  }
457};
458
459typedef SmallVector<std::unique_ptr<VPtrInfo>, 2> VPtrInfoVector;
460
461/// All virtual base related information about a given record decl.  Includes
462/// information on all virtual base tables and the path components that are used
463/// to mangle them.
464struct VirtualBaseInfo {
465  /// A map from virtual base to vbtable index for doing a conversion from the
466  /// the derived class to the a base.
467  llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices;
468
469  /// Information on all virtual base tables used when this record is the most
470  /// derived class.
471  VPtrInfoVector VBPtrPaths;
472};
473
474struct MethodVFTableLocation {
475  /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
476  uint64_t VBTableIndex;
477
478  /// If nonnull, holds the last vbase which contains the vfptr that the
479  /// method definition is adjusted to.
480  const CXXRecordDecl *VBase;
481
482  /// This is the offset of the vfptr from the start of the last vbase, or the
483  /// complete type if there are no virtual bases.
484  CharUnits VFPtrOffset;
485
486  /// Method's index in the vftable.
487  uint64_t Index;
488
489  MethodVFTableLocation()
490      : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
491        Index(0) {}
492
493  MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
494                        CharUnits VFPtrOffset, uint64_t Index)
495      : VBTableIndex(VBTableIndex), VBase(VBase), VFPtrOffset(VFPtrOffset),
496        Index(Index) {}
497
498  bool operator<(const MethodVFTableLocation &other) const {
499    if (VBTableIndex != other.VBTableIndex) {
500      assert(VBase != other.VBase);
501      return VBTableIndex < other.VBTableIndex;
502    }
503    return std::tie(VFPtrOffset, Index) <
504           std::tie(other.VFPtrOffset, other.Index);
505  }
506};
507
508class MicrosoftVTableContext : public VTableContextBase {
509public:
510
511private:
512  ASTContext &Context;
513
514  typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
515    MethodVFTableLocationsTy;
516  MethodVFTableLocationsTy MethodVFTableLocations;
517
518  typedef llvm::DenseMap<const CXXRecordDecl *, std::unique_ptr<VPtrInfoVector>>
519      VFPtrLocationsMapTy;
520  VFPtrLocationsMapTy VFPtrLocations;
521
522  typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
523  typedef llvm::DenseMap<VFTableIdTy, std::unique_ptr<const VTableLayout>>
524      VFTableLayoutMapTy;
525  VFTableLayoutMapTy VFTableLayouts;
526
527  llvm::DenseMap<const CXXRecordDecl *, std::unique_ptr<VirtualBaseInfo>>
528      VBaseInfo;
529
530  void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result);
531
532  void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
533
534  void dumpMethodLocations(const CXXRecordDecl *RD,
535                           const MethodVFTableLocationsTy &NewMethods,
536                           raw_ostream &);
537
538  const VirtualBaseInfo &
539  computeVBTableRelatedInformation(const CXXRecordDecl *RD);
540
541  void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD,
542                          VPtrInfoVector &Paths);
543
544public:
545  MicrosoftVTableContext(ASTContext &Context)
546      : VTableContextBase(/*MS=*/true), Context(Context) {}
547
548  ~MicrosoftVTableContext() override;
549
550  const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD);
551
552  const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
553                                       CharUnits VFPtrOffset);
554
555  MethodVFTableLocation getMethodVFTableLocation(GlobalDecl GD);
556
557  const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override {
558    // Complete destructors don't have a slot in a vftable, so no thunks needed.
559    if (isa<CXXDestructorDecl>(GD.getDecl()) &&
560        GD.getDtorType() == Dtor_Complete)
561      return nullptr;
562    return VTableContextBase::getThunkInfo(GD);
563  }
564
565  /// Returns the index of VBase in the vbtable of Derived.
566  /// VBase must be a morally virtual base of Derived.
567  /// The vbtable is an array of i32 offsets.  The first entry is a self entry,
568  /// and the rest are offsets from the vbptr to virtual bases.
569  unsigned getVBTableIndex(const CXXRecordDecl *Derived,
570                           const CXXRecordDecl *VBase);
571
572  const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD);
573
574  static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }
575};
576
577} // namespace clang
578
579#endif
580