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