1//===--- VTableBuilder.h - C++ vtable layout builder --------------*- C++ -*-=//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This contains code dealing with generation of the layout of virtual tables.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_AST_VTABLEBUILDER_H
15#define LLVM_CLANG_AST_VTABLEBUILDER_H
16
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"
24#include <memory>
25#include <utility>
26
27namespace clang {
28  class CXXRecordDecl;
29
30/// \brief Represents a single component in a vtable.
31class VTableComponent {
32public:
33  enum Kind {
34    CK_VCallOffset,
35    CK_VBaseOffset,
36    CK_OffsetToTop,
37    CK_RTTI,
38    CK_FunctionPointer,
39
40    /// \brief A pointer to the complete destructor.
41    CK_CompleteDtorPointer,
42
43    /// \brief A pointer to the deleting destructor.
44    CK_DeletingDtorPointer,
45
46    /// \brief An entry that is never used.
47    ///
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
52  };
53
54  VTableComponent() = default;
55
56  static VTableComponent MakeVCallOffset(CharUnits Offset) {
57    return VTableComponent(CK_VCallOffset, Offset);
58  }
59
60  static VTableComponent MakeVBaseOffset(CharUnits Offset) {
61    return VTableComponent(CK_VBaseOffset, Offset);
62  }
63
64  static VTableComponent MakeOffsetToTop(CharUnits Offset) {
65    return VTableComponent(CK_OffsetToTop, Offset);
66  }
67
68  static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
69    return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
70  }
71
72  static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
73    assert(!isa<CXXDestructorDecl>(MD) &&
74           "Don't use MakeFunction with destructors!");
75
76    return VTableComponent(CK_FunctionPointer,
77                           reinterpret_cast<uintptr_t>(MD));
78  }
79
80  static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
81    return VTableComponent(CK_CompleteDtorPointer,
82                           reinterpret_cast<uintptr_t>(DD));
83  }
84
85  static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
86    return VTableComponent(CK_DeletingDtorPointer,
87                           reinterpret_cast<uintptr_t>(DD));
88  }
89
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));
95  }
96
97  static VTableComponent getFromOpaqueInteger(uint64_t I) {
98    return VTableComponent(I);
99  }
100
101  /// \brief Get the kind of this vtable component.
102  Kind getKind() const {
103    return (Kind)(Value & 0x7);
104  }
105
106  CharUnits getVCallOffset() const {
107    assert(getKind() == CK_VCallOffset && "Invalid component kind!");
108
109    return getOffset();
110  }
111
112  CharUnits getVBaseOffset() const {
113    assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
114
115    return getOffset();
116  }
117
118  CharUnits getOffsetToTop() const {
119    assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
120
121    return getOffset();
122  }
123
124  const CXXRecordDecl *getRTTIDecl() const {
125    assert(isRTTIKind() && "Invalid component kind!");
126    return reinterpret_cast<CXXRecordDecl *>(getPointer());
127  }
128
129  const CXXMethodDecl *getFunctionDecl() const {
130    assert(isFunctionPointerKind() && "Invalid component kind!");
131    if (isDestructorKind())
132      return getDestructorDecl();
133    return reinterpret_cast<CXXMethodDecl *>(getPointer());
134  }
135
136  const CXXDestructorDecl *getDestructorDecl() const {
137    assert(isDestructorKind() && "Invalid component kind!");
138    return reinterpret_cast<CXXDestructorDecl *>(getPointer());
139  }
140
141  const CXXMethodDecl *getUnusedFunctionDecl() const {
142    assert(getKind() == CK_UnusedFunctionPointer && "Invalid component kind!");
143    return reinterpret_cast<CXXMethodDecl *>(getPointer());
144  }
145
146  bool isDestructorKind() const { return isDestructorKind(getKind()); }
147
148  bool isUsedFunctionPointerKind() const {
149    return isUsedFunctionPointerKind(getKind());
150  }
151
152  bool isFunctionPointerKind() const {
153    return isFunctionPointerKind(getKind());
154  }
155
156  bool isRTTIKind() const { return isRTTIKind(getKind()); }
157
158private:
159  static bool isFunctionPointerKind(Kind ComponentKind) {
160    return isUsedFunctionPointerKind(ComponentKind) ||
161           ComponentKind == CK_UnusedFunctionPointer;
162  }
163  static bool isUsedFunctionPointerKind(Kind ComponentKind) {
164    return ComponentKind == CK_FunctionPointer ||
165           isDestructorKind(ComponentKind);
166  }
167  static bool isDestructorKind(Kind ComponentKind) {
168    return ComponentKind == CK_CompleteDtorPointer ||
169           ComponentKind == CK_DeletingDtorPointer;
170  }
171  static bool isRTTIKind(Kind ComponentKind) {
172    return ComponentKind == CK_RTTI;
173  }
174
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!");
181
182    Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
183  }
184
185  VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
186    assert((isRTTIKind(ComponentKind) || isFunctionPointerKind(ComponentKind)) &&
187           "Invalid component kind!");
188
189    assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
190
191    Value = Ptr | ComponentKind;
192  }
193
194  CharUnits getOffset() const {
195    assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
196            getKind() == CK_OffsetToTop) && "Invalid component kind!");
197
198    return CharUnits::fromQuantity(Value >> 3);
199  }
200
201  uintptr_t getPointer() const {
202    assert((getKind() == CK_RTTI || isFunctionPointerKind()) &&
203           "Invalid component kind!");
204
205    return static_cast<uintptr_t>(Value & ~7ULL);
206  }
207
208  explicit VTableComponent(uint64_t Value)
209    : Value(Value) { }
210
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).
216  int64_t Value;
217};
218
219class VTableLayout {
220public:
221  typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
222
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;
227
228  typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
229
230private:
231  uint64_t NumVTableComponents;
232  std::unique_ptr<VTableComponent[]> VTableComponents;
233
234  /// \brief Contains thunks needed by vtables, sorted by indices.
235  uint64_t NumVTableThunks;
236  std::unique_ptr<VTableThunkTy[]> VTableThunks;
237
238  /// \brief Address points for all vtables.
239  AddressPointsMapTy AddressPoints;
240
241  bool IsMicrosoftABI;
242
243public:
244  VTableLayout(uint64_t NumVTableComponents,
245               const VTableComponent *VTableComponents,
246               uint64_t NumVTableThunks,
247               const VTableThunkTy *VTableThunks,
248               const AddressPointsMapTy &AddressPoints,
249               bool IsMicrosoftABI);
250  ~VTableLayout();
251
252  uint64_t getNumVTableComponents() const {
253    return NumVTableComponents;
254  }
255
256  vtable_component_range vtable_components() const {
257    return vtable_component_range(vtable_component_begin(),
258                                  vtable_component_end());
259  }
260
261  vtable_component_iterator vtable_component_begin() const {
262    return VTableComponents.get();
263  }
264
265  vtable_component_iterator vtable_component_end() const {
266    return VTableComponents.get() + NumVTableComponents;
267  }
268
269  uint64_t getNumVTableThunks() const { return NumVTableThunks; }
270
271  vtable_thunk_iterator vtable_thunk_begin() const {
272    return VTableThunks.get();
273  }
274
275  vtable_thunk_iterator vtable_thunk_end() const {
276    return VTableThunks.get() + NumVTableThunks;
277  }
278
279  uint64_t getAddressPoint(BaseSubobject Base) const {
280    assert(AddressPoints.count(Base) &&
281           "Did not find address point!");
282
283    uint64_t AddressPoint = AddressPoints.lookup(Base);
284    assert(AddressPoint != 0 || IsMicrosoftABI);
285    (void)IsMicrosoftABI;
286
287    return AddressPoint;
288  }
289
290  const AddressPointsMapTy &getAddressPoints() const {
291    return AddressPoints;
292  }
293};
294
295class VTableContextBase {
296public:
297  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
298
299  bool isMicrosoft() const { return IsMicrosoftABI; }
300
301  virtual ~VTableContextBase() {}
302
303protected:
304  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
305
306  /// \brief Contains all thunks that a given method decl will need.
307  ThunksMapTy Thunks;
308
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;
312
313  VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
314
315public:
316  virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
317    const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
318    computeVTableRelatedInformation(MD->getParent());
319
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.
325      return nullptr;
326    }
327
328    return &I->second;
329  }
330
331  bool IsMicrosoftABI;
332};
333
334class ItaniumVTableContext : public VTableContextBase {
335private:
336
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;
341
342  typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
343    VTableLayoutMapTy;
344  VTableLayoutMapTy VTableLayouts;
345
346  typedef std::pair<const CXXRecordDecl *,
347                    const CXXRecordDecl *> ClassPairTy;
348
349  /// \brief vtable offsets for offsets of virtual bases of a class.
350  ///
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;
356
357  void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
358
359public:
360  ItaniumVTableContext(ASTContext &Context);
361  ~ItaniumVTableContext() override;
362
363  const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
364    computeVTableRelatedInformation(RD);
365    assert(VTableLayouts.count(RD) && "No layout for this record decl!");
366
367    return *VTableLayouts[RD];
368  }
369
370  VTableLayout *
371  createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
372                                 CharUnits MostDerivedClassOffset,
373                                 bool MostDerivedClassIsVirtual,
374                                 const CXXRecordDecl *LayoutClass);
375
376  /// \brief Locate a virtual function in the vtable.
377  ///
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);
381
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.
385  ///
386  /// Base must be a virtual base class or an unambiguous base.
387  CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
388                                       const CXXRecordDecl *VBase);
389
390  static bool classof(const VTableContextBase *VT) {
391    return !VT->isMicrosoft();
392  }
393};
394
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
397/// base subobjects.
398struct VPtrInfo {
399  typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
400
401  VPtrInfo(const CXXRecordDecl *RD)
402      : ReusingBase(RD), BaseWithVPtr(RD), NextBaseToMangle(RD) {}
403
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;
409
410  /// BaseWithVPtr is at this offset from its containing complete object or
411  /// virtual base.
412  CharUnits NonVirtualOffset;
413
414  /// The vptr is stored inside this subobject.
415  const CXXRecordDecl *BaseWithVPtr;
416
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;
422
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;
426
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;
431
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
434  /// vftables.
435  BasePath PathToBaseWithVPtr;
436
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;
440
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();
444  }
445};
446
447typedef SmallVector<VPtrInfo *, 2> VPtrInfoVector;
448
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
451/// to mangle them.
452struct VirtualBaseInfo {
453  ~VirtualBaseInfo() { llvm::DeleteContainerPointers(VBPtrPaths); }
454
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;
458
459  /// Information on all virtual base tables used when this record is the most
460  /// derived class.
461  VPtrInfoVector VBPtrPaths;
462};
463
464class MicrosoftVTableContext : public VTableContextBase {
465public:
466  struct MethodVFTableLocation {
467    /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
468    uint64_t VBTableIndex;
469
470    /// If nonnull, holds the last vbase which contains the vfptr that the
471    /// method definition is adjusted to.
472    const CXXRecordDecl *VBase;
473
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;
477
478    /// Method's index in the vftable.
479    uint64_t Index;
480
481    MethodVFTableLocation()
482        : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
483          Index(0) {}
484
485    MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
486                          CharUnits VFPtrOffset, uint64_t Index)
487        : VBTableIndex(VBTableIndex), VBase(VBase),
488          VFPtrOffset(VFPtrOffset), Index(Index) {}
489
490    bool operator<(const MethodVFTableLocation &other) const {
491      if (VBTableIndex != other.VBTableIndex) {
492        assert(VBase != other.VBase);
493        return VBTableIndex < other.VBTableIndex;
494      }
495      return std::tie(VFPtrOffset, Index) <
496             std::tie(other.VFPtrOffset, other.Index);
497    }
498  };
499
500private:
501  ASTContext &Context;
502
503  typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
504    MethodVFTableLocationsTy;
505  MethodVFTableLocationsTy MethodVFTableLocations;
506
507  typedef llvm::DenseMap<const CXXRecordDecl *, VPtrInfoVector *>
508    VFPtrLocationsMapTy;
509  VFPtrLocationsMapTy VFPtrLocations;
510
511  typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
512  typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
513  VFTableLayoutMapTy VFTableLayouts;
514
515  llvm::DenseMap<const CXXRecordDecl *, VirtualBaseInfo *> VBaseInfo;
516
517  void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result);
518
519  void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
520
521  void dumpMethodLocations(const CXXRecordDecl *RD,
522                           const MethodVFTableLocationsTy &NewMethods,
523                           raw_ostream &);
524
525  const VirtualBaseInfo *
526  computeVBTableRelatedInformation(const CXXRecordDecl *RD);
527
528  void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD,
529                          VPtrInfoVector &Paths);
530
531public:
532  MicrosoftVTableContext(ASTContext &Context)
533      : VTableContextBase(/*MS=*/true), Context(Context) {}
534
535  ~MicrosoftVTableContext() override;
536
537  const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD);
538
539  const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
540                                       CharUnits VFPtrOffset);
541
542  const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
543
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)
548      return nullptr;
549    return VTableContextBase::getThunkInfo(GD);
550  }
551
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);
558
559  const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD);
560
561  static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }
562};
563
564} // namespace clang
565
566#endif
567