VTableBuilder.h revision 263508 
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/SetVector.h"
23#include "llvm/ADT/DenseSet.h"
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() { }
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(getKind() == CK_RTTI && "Invalid component kind!");
125
126    return reinterpret_cast<CXXRecordDecl *>(getPointer());
127  }
128
129  const CXXMethodDecl *getFunctionDecl() const {
130    assert(getKind() == CK_FunctionPointer);
131
132    return reinterpret_cast<CXXMethodDecl *>(getPointer());
133  }
134
135  const CXXDestructorDecl *getDestructorDecl() const {
136    assert((getKind() == CK_CompleteDtorPointer ||
137            getKind() == CK_DeletingDtorPointer) && "Invalid component kind!");
138
139    return reinterpret_cast<CXXDestructorDecl *>(getPointer());
140  }
141
142  const CXXMethodDecl *getUnusedFunctionDecl() const {
143    assert(getKind() == CK_UnusedFunctionPointer);
144
145    return reinterpret_cast<CXXMethodDecl *>(getPointer());
146  }
147
148private:
149  VTableComponent(Kind ComponentKind, CharUnits Offset) {
150    assert((ComponentKind == CK_VCallOffset ||
151            ComponentKind == CK_VBaseOffset ||
152            ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
153    assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
154    assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
155
156    Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
157  }
158
159  VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
160    assert((ComponentKind == CK_RTTI ||
161            ComponentKind == CK_FunctionPointer ||
162            ComponentKind == CK_CompleteDtorPointer ||
163            ComponentKind == CK_DeletingDtorPointer ||
164            ComponentKind == CK_UnusedFunctionPointer) &&
165            "Invalid component kind!");
166
167    assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
168
169    Value = Ptr | ComponentKind;
170  }
171
172  CharUnits getOffset() const {
173    assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
174            getKind() == CK_OffsetToTop) && "Invalid component kind!");
175
176    return CharUnits::fromQuantity(Value >> 3);
177  }
178
179  uintptr_t getPointer() const {
180    assert((getKind() == CK_RTTI ||
181            getKind() == CK_FunctionPointer ||
182            getKind() == CK_CompleteDtorPointer ||
183            getKind() == CK_DeletingDtorPointer ||
184            getKind() == CK_UnusedFunctionPointer) &&
185           "Invalid component kind!");
186
187    return static_cast<uintptr_t>(Value & ~7ULL);
188  }
189
190  explicit VTableComponent(uint64_t Value)
191    : Value(Value) { }
192
193  /// The kind is stored in the lower 3 bits of the value. For offsets, we
194  /// make use of the facts that classes can't be larger than 2^55 bytes,
195  /// so we store the offset in the lower part of the 61 bits that remain.
196  /// (The reason that we're not simply using a PointerIntPair here is that we
197  /// need the offsets to be 64-bit, even when on a 32-bit machine).
198  int64_t Value;
199};
200
201class VTableLayout {
202public:
203  typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
204
205  typedef const VTableComponent *vtable_component_iterator;
206  typedef const VTableThunkTy *vtable_thunk_iterator;
207
208  typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
209private:
210  uint64_t NumVTableComponents;
211  llvm::OwningArrayPtr<VTableComponent> VTableComponents;
212
213  /// \brief Contains thunks needed by vtables, sorted by indices.
214  uint64_t NumVTableThunks;
215  llvm::OwningArrayPtr<VTableThunkTy> VTableThunks;
216
217  /// \brief Address points for all vtables.
218  AddressPointsMapTy AddressPoints;
219
220  bool IsMicrosoftABI;
221
222public:
223  VTableLayout(uint64_t NumVTableComponents,
224               const VTableComponent *VTableComponents,
225               uint64_t NumVTableThunks,
226               const VTableThunkTy *VTableThunks,
227               const AddressPointsMapTy &AddressPoints,
228               bool IsMicrosoftABI);
229  ~VTableLayout();
230
231  uint64_t getNumVTableComponents() const {
232    return NumVTableComponents;
233  }
234
235  vtable_component_iterator vtable_component_begin() const {
236    return VTableComponents.get();
237  }
238
239  vtable_component_iterator vtable_component_end() const {
240    return VTableComponents.get() + NumVTableComponents;
241  }
242
243  uint64_t getNumVTableThunks() const { return NumVTableThunks; }
244
245  vtable_thunk_iterator vtable_thunk_begin() const {
246    return VTableThunks.get();
247  }
248
249  vtable_thunk_iterator vtable_thunk_end() const {
250    return VTableThunks.get() + NumVTableThunks;
251  }
252
253  uint64_t getAddressPoint(BaseSubobject Base) const {
254    assert(AddressPoints.count(Base) &&
255           "Did not find address point!");
256
257    uint64_t AddressPoint = AddressPoints.lookup(Base);
258    assert(AddressPoint != 0 || IsMicrosoftABI);
259    (void)IsMicrosoftABI;
260
261    return AddressPoint;
262  }
263
264  const AddressPointsMapTy &getAddressPoints() const {
265    return AddressPoints;
266  }
267};
268
269class VTableContextBase {
270public:
271  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
272
273protected:
274  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
275
276  /// \brief Contains all thunks that a given method decl will need.
277  ThunksMapTy Thunks;
278
279  /// Compute and store all vtable related information (vtable layout, vbase
280  /// offset offsets, thunks etc) for the given record decl.
281  virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
282
283  virtual ~VTableContextBase() {}
284
285public:
286  virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
287    const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
288    computeVTableRelatedInformation(MD->getParent());
289
290    // This assumes that all the destructors present in the vtable
291    // use exactly the same set of thunks.
292    ThunksMapTy::const_iterator I = Thunks.find(MD);
293    if (I == Thunks.end()) {
294      // We did not find a thunk for this method.
295      return 0;
296    }
297
298    return &I->second;
299  }
300};
301
302class ItaniumVTableContext : public VTableContextBase {
303private:
304  bool IsMicrosoftABI;
305
306  /// \brief Contains the index (relative to the vtable address point)
307  /// where the function pointer for a virtual function is stored.
308  typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
309  MethodVTableIndicesTy MethodVTableIndices;
310
311  typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
312    VTableLayoutMapTy;
313  VTableLayoutMapTy VTableLayouts;
314
315  typedef std::pair<const CXXRecordDecl *,
316                    const CXXRecordDecl *> ClassPairTy;
317
318  /// \brief vtable offsets for offsets of virtual bases of a class.
319  ///
320  /// Contains the vtable offset (relative to the address point) in chars
321  /// where the offsets for virtual bases of a class are stored.
322  typedef llvm::DenseMap<ClassPairTy, CharUnits>
323    VirtualBaseClassOffsetOffsetsMapTy;
324  VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
325
326  void computeVTableRelatedInformation(const CXXRecordDecl *RD);
327
328public:
329  ItaniumVTableContext(ASTContext &Context);
330  ~ItaniumVTableContext();
331
332  const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
333    computeVTableRelatedInformation(RD);
334    assert(VTableLayouts.count(RD) && "No layout for this record decl!");
335
336    return *VTableLayouts[RD];
337  }
338
339  VTableLayout *
340  createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
341                                 CharUnits MostDerivedClassOffset,
342                                 bool MostDerivedClassIsVirtual,
343                                 const CXXRecordDecl *LayoutClass);
344
345  /// \brief Locate a virtual function in the vtable.
346  ///
347  /// Return the index (relative to the vtable address point) where the
348  /// function pointer for the given virtual function is stored.
349  uint64_t getMethodVTableIndex(GlobalDecl GD);
350
351  /// Return the offset in chars (relative to the vtable address point) where
352  /// the offset of the virtual base that contains the given base is stored,
353  /// otherwise, if no virtual base contains the given class, return 0.
354  ///
355  /// Base must be a virtual base class or an unambiguous base.
356  CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
357                                       const CXXRecordDecl *VBase);
358};
359
360struct VFPtrInfo {
361  typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
362
363  // Don't pass the PathToMangle as it should be calculated later.
364  VFPtrInfo(CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr)
365      : VBTableIndex(0), LastVBase(0), VFPtrOffset(VFPtrOffset),
366        PathToBaseWithVFPtr(PathToBaseWithVFPtr), VFPtrFullOffset(VFPtrOffset) {
367  }
368
369  // Don't pass the PathToMangle as it should be calculated later.
370  VFPtrInfo(uint64_t VBTableIndex, const CXXRecordDecl *LastVBase,
371            CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr,
372            CharUnits VFPtrFullOffset)
373      : VBTableIndex(VBTableIndex), LastVBase(LastVBase),
374        VFPtrOffset(VFPtrOffset), PathToBaseWithVFPtr(PathToBaseWithVFPtr),
375        VFPtrFullOffset(VFPtrFullOffset) {
376    assert(VBTableIndex && "The full constructor should only be used "
377                           "for vfptrs in virtual bases");
378    assert(LastVBase);
379  }
380
381  /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
382  uint64_t VBTableIndex;
383
384  /// Stores the last vbase on the path from the complete type to the vfptr.
385  const CXXRecordDecl *LastVBase;
386
387  /// This is the offset of the vfptr from the start of the last vbase,
388  /// or the complete type if there are no virtual bases.
389  CharUnits VFPtrOffset;
390
391  /// This holds the base classes path from the complete type to the first base
392  /// with the given vfptr offset, in the base-to-derived order.
393  BasePath PathToBaseWithVFPtr;
394
395  /// This holds the subset of records that need to be mangled into the vftable
396  /// symbol name in order to get a unique name, in the derived-to-base order.
397  BasePath PathToMangle;
398
399  /// This is the full offset of the vfptr from the start of the complete type.
400  CharUnits VFPtrFullOffset;
401};
402
403class MicrosoftVTableContext : public VTableContextBase {
404public:
405  struct MethodVFTableLocation {
406    /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
407    uint64_t VBTableIndex;
408
409    /// If nonnull, holds the last vbase which contains the vfptr that the
410    /// method definition is adjusted to.
411    const CXXRecordDecl *VBase;
412
413    /// This is the offset of the vfptr from the start of the last vbase, or the
414    /// complete type if there are no virtual bases.
415    CharUnits VFPtrOffset;
416
417    /// Method's index in the vftable.
418    uint64_t Index;
419
420    MethodVFTableLocation()
421        : VBTableIndex(0), VBase(0), VFPtrOffset(CharUnits::Zero()),
422          Index(0) {}
423
424    MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
425                          CharUnits VFPtrOffset, uint64_t Index)
426        : VBTableIndex(VBTableIndex), VBase(VBase),
427          VFPtrOffset(VFPtrOffset), Index(Index) {}
428
429    bool operator<(const MethodVFTableLocation &other) const {
430      if (VBTableIndex != other.VBTableIndex) {
431        assert(VBase != other.VBase);
432        return VBTableIndex < other.VBTableIndex;
433      }
434      if (VFPtrOffset != other.VFPtrOffset)
435        return VFPtrOffset < other.VFPtrOffset;
436      if (Index != other.Index)
437        return Index < other.Index;
438      return false;
439    }
440  };
441
442  typedef SmallVector<VFPtrInfo, 1> VFPtrListTy;
443
444private:
445  ASTContext &Context;
446
447  typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
448    MethodVFTableLocationsTy;
449  MethodVFTableLocationsTy MethodVFTableLocations;
450
451  typedef llvm::DenseMap<const CXXRecordDecl *, VFPtrListTy>
452    VFPtrLocationsMapTy;
453  VFPtrLocationsMapTy VFPtrLocations;
454
455  typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
456  typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
457  VFTableLayoutMapTy VFTableLayouts;
458
459  typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
460  void enumerateVFPtrs(const CXXRecordDecl *MostDerivedClass,
461                       const ASTRecordLayout &MostDerivedClassLayout,
462                       BaseSubobject Base, const CXXRecordDecl *LastVBase,
463                       const VFPtrInfo::BasePath &PathFromCompleteClass,
464                       BasesSetVectorTy &VisitedVBases,
465                       MicrosoftVTableContext::VFPtrListTy &Result);
466
467  void enumerateVFPtrs(const CXXRecordDecl *ForClass,
468                       MicrosoftVTableContext::VFPtrListTy &Result);
469
470  void computeVTableRelatedInformation(const CXXRecordDecl *RD);
471
472  void dumpMethodLocations(const CXXRecordDecl *RD,
473                           const MethodVFTableLocationsTy &NewMethods,
474                           raw_ostream &);
475
476  typedef std::pair<const CXXRecordDecl *, const CXXRecordDecl *> ClassPairTy;
477  typedef llvm::DenseMap<ClassPairTy, unsigned> VBTableIndicesTy;
478  VBTableIndicesTy VBTableIndices;
479  llvm::DenseSet<const CXXRecordDecl *> ComputedVBTableIndices;
480
481  void computeVBTableRelatedInformation(const CXXRecordDecl *RD);
482
483public:
484  MicrosoftVTableContext(ASTContext &Context) : Context(Context) {}
485
486  ~MicrosoftVTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); }
487
488  const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD);
489
490  const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
491                                       CharUnits VFPtrOffset);
492
493  const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
494
495  const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
496    // Complete destructors don't have a slot in a vftable, so no thunks needed.
497    if (isa<CXXDestructorDecl>(GD.getDecl()) &&
498        GD.getDtorType() == Dtor_Complete)
499      return 0;
500    return VTableContextBase::getThunkInfo(GD);
501  }
502
503  /// \brief Returns the index of VBase in the vbtable of Derived.
504  /// VBase must be a morally virtual base of Derived.
505  /// The vbtable is an array of i32 offsets.  The first entry is a self entry,
506  /// and the rest are offsets from the vbptr to virtual bases.
507  unsigned getVBTableIndex(const CXXRecordDecl *Derived,
508                           const CXXRecordDecl *VBase) {
509    computeVBTableRelatedInformation(Derived);
510    ClassPairTy Pair(Derived, VBase);
511    assert(VBTableIndices.count(Pair) == 1 &&
512           "VBase must be a vbase of Derived");
513    return VBTableIndices[Pair];
514  }
515};
516}
517
518#endif
519