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