VTableBuilder.h revision a53d7a0259ff88f78ba8ecac7d0cb3ea96302b1d 
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  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
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.
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 {
244    return NumVTableThunks;
245  }
246
247  vtable_thunk_iterator vtable_thunk_begin() const {
248   return VTableThunks.get();
249  }
250
251  vtable_thunk_iterator vtable_thunk_end() const {
252   return VTableThunks.get()+NumVTableThunks;
253  }
254
255  uint64_t getAddressPoint(BaseSubobject Base) const {
256    assert(AddressPoints.count(Base) &&
257           "Did not find address point!");
258
259    uint64_t AddressPoint = AddressPoints.lookup(Base);
260    assert(AddressPoint != 0 || IsMicrosoftABI);
261    (void)IsMicrosoftABI;
262
263    return AddressPoint;
264  }
265
266  const AddressPointsMapTy &getAddressPoints() const {
267    return AddressPoints;
268  }
269};
270
271class VTableContextBase {
272public:
273  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
274
275protected:
276  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
277
278  /// \brief Contains all thunks that a given method decl will need.
279  ThunksMapTy Thunks;
280
281  /// Compute and store all vtable related information (vtable layout, vbase
282  /// offset offsets, thunks etc) for the given record decl.
283  virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
284
285  virtual ~VTableContextBase() {}
286
287public:
288  const ThunkInfoVectorTy *getThunkInfo(const CXXMethodDecl *MD) {
289    computeVTableRelatedInformation(MD->getParent());
290
291    ThunksMapTy::const_iterator I = Thunks.find(MD);
292    if (I == Thunks.end()) {
293      // We did not find a thunk for this method.
294      return 0;
295    }
296
297    return &I->second;
298  }
299};
300
301// FIXME: rename to ItaniumVTableContext.
302class VTableContext : 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  VTableContext(ASTContext &Context);
330  ~VTableContext();
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
360/// \brief Computes the index of VBase in the vbtable of Derived.
361/// VBase must be a morally virtual base of Derived.  The vbtable is
362/// an array of i32 offsets.  The first entry is a self entry, and the rest are
363/// offsets from the vbptr to virtual bases.  The bases are ordered the same way
364/// our vbases are ordered: as they appear in a left-to-right depth-first search
365/// of the hierarchy.
366// FIXME: make this a static method of VBTableBuilder when we move it to AST.
367unsigned GetVBTableIndex(const CXXRecordDecl *Derived,
368                         const CXXRecordDecl *VBase);
369
370struct VFPtrInfo {
371  typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
372
373  // Don't pass the PathToMangle as it should be calculated later.
374  VFPtrInfo(CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr)
375      : VBTableIndex(0), LastVBase(0), VFPtrOffset(VFPtrOffset),
376        PathToBaseWithVFPtr(PathToBaseWithVFPtr), VFPtrFullOffset(VFPtrOffset) {
377  }
378
379  // Don't pass the PathToMangle as it should be calculated later.
380  VFPtrInfo(uint64_t VBTableIndex, const CXXRecordDecl *LastVBase,
381            CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr,
382            CharUnits VFPtrFullOffset)
383      : VBTableIndex(VBTableIndex), LastVBase(LastVBase),
384        VFPtrOffset(VFPtrOffset), PathToBaseWithVFPtr(PathToBaseWithVFPtr),
385        VFPtrFullOffset(VFPtrFullOffset) {
386    assert(VBTableIndex && "The full constructor should only be used "
387                           "for vfptrs in virtual bases");
388    assert(LastVBase);
389  }
390
391  /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
392  uint64_t VBTableIndex;
393
394  /// Stores the last vbase on the path from the complete type to the vfptr.
395  const CXXRecordDecl *LastVBase;
396
397  /// This is the offset of the vfptr from the start of the last vbase,
398  /// or the complete type if there are no virtual bases.
399  CharUnits VFPtrOffset;
400
401  /// This holds the base classes path from the complete type to the first base
402  /// with the given vfptr offset, in the base-to-derived order.
403  BasePath PathToBaseWithVFPtr;
404
405  /// This holds the subset of records that need to be mangled into the vftable
406  /// symbol name in order to get a unique name, in the derived-to-base order.
407  BasePath PathToMangle;
408
409  /// This is the full offset of the vfptr from the start of the complete type.
410  CharUnits VFPtrFullOffset;
411};
412
413class MicrosoftVFTableContext : public VTableContextBase {
414public:
415  struct MethodVFTableLocation {
416    /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
417    uint64_t VBTableIndex;
418
419    /// If nonnull, holds the last vbase which contains the vfptr that the
420    /// method definition is adjusted to.
421    const CXXRecordDecl *VBase;
422
423    /// This is the offset of the vfptr from the start of the last vbase, or the
424    /// complete type if there are no virtual bases.
425    CharUnits VFTableOffset;
426
427    /// Method's index in the vftable.
428    uint64_t Index;
429
430    MethodVFTableLocation()
431        : VBTableIndex(0), VBase(0), VFTableOffset(CharUnits::Zero()),
432          Index(0) {}
433
434    MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
435                          CharUnits VFTableOffset, uint64_t Index)
436        : VBTableIndex(VBTableIndex), VBase(VBase),
437          VFTableOffset(VFTableOffset), Index(Index) {}
438
439    bool operator<(const MethodVFTableLocation &other) const {
440      if (VBTableIndex != other.VBTableIndex) {
441        assert(VBase != other.VBase);
442        return VBTableIndex < other.VBTableIndex;
443      }
444      if (VFTableOffset != other.VFTableOffset)
445        return VFTableOffset < other.VFTableOffset;
446      if (Index != other.Index)
447        return Index < other.Index;
448      return false;
449    }
450  };
451
452  typedef SmallVector<VFPtrInfo, 1> VFPtrListTy;
453
454private:
455  ASTContext &Context;
456
457  typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
458    MethodVFTableLocationsTy;
459  MethodVFTableLocationsTy MethodVFTableLocations;
460
461  typedef llvm::DenseMap<const CXXRecordDecl *, VFPtrListTy>
462    VFPtrLocationsMapTy;
463  VFPtrLocationsMapTy VFPtrLocations;
464
465  typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
466  typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
467  VFTableLayoutMapTy VFTableLayouts;
468
469  void computeVTableRelatedInformation(const CXXRecordDecl *RD);
470
471  void dumpMethodLocations(const CXXRecordDecl *RD,
472                           const MethodVFTableLocationsTy &NewMethods,
473                           raw_ostream &);
474
475public:
476  MicrosoftVFTableContext(ASTContext &Context) : Context(Context) {}
477
478  ~MicrosoftVFTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); }
479
480  const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD);
481
482  const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
483                                       CharUnits VFPtrOffset);
484
485  const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
486};
487}
488
489#endif
490