VTableBuilder.h revision 6de6aab8248ef67d3a65018d4ad26f51ac35b3d3 
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/// VTableComponent - 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    /// CK_CompleteDtorPointer - A pointer to the complete destructor.
39    CK_CompleteDtorPointer,
40
41    /// CK_DeletingDtorPointer - A pointer to the deleting destructor.
42    CK_DeletingDtorPointer,
43
44    /// CK_UnusedFunctionPointer - In some cases, a vtable function pointer
45    /// will end up never being called. Such vtable function pointers are
46    /// represented as a CK_UnusedFunctionPointer.
47    CK_UnusedFunctionPointer
48  };
49
50  VTableComponent() { }
51
52  static VTableComponent MakeVCallOffset(CharUnits Offset) {
53    return VTableComponent(CK_VCallOffset, Offset);
54  }
55
56  static VTableComponent MakeVBaseOffset(CharUnits Offset) {
57    return VTableComponent(CK_VBaseOffset, Offset);
58  }
59
60  static VTableComponent MakeOffsetToTop(CharUnits Offset) {
61    return VTableComponent(CK_OffsetToTop, Offset);
62  }
63
64  static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
65    return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
66  }
67
68  static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
69    assert(!isa<CXXDestructorDecl>(MD) &&
70           "Don't use MakeFunction with destructors!");
71
72    return VTableComponent(CK_FunctionPointer,
73                           reinterpret_cast<uintptr_t>(MD));
74  }
75
76  static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
77    return VTableComponent(CK_CompleteDtorPointer,
78                           reinterpret_cast<uintptr_t>(DD));
79  }
80
81  static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
82    return VTableComponent(CK_DeletingDtorPointer,
83                           reinterpret_cast<uintptr_t>(DD));
84  }
85
86  static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) {
87    assert(!isa<CXXDestructorDecl>(MD) &&
88           "Don't use MakeUnusedFunction with destructors!");
89    return VTableComponent(CK_UnusedFunctionPointer,
90                           reinterpret_cast<uintptr_t>(MD));
91  }
92
93  static VTableComponent getFromOpaqueInteger(uint64_t I) {
94    return VTableComponent(I);
95  }
96
97  /// getKind - Get the kind of this vtable component.
98  Kind getKind() const {
99    return (Kind)(Value & 0x7);
100  }
101
102  CharUnits getVCallOffset() const {
103    assert(getKind() == CK_VCallOffset && "Invalid component kind!");
104
105    return getOffset();
106  }
107
108  CharUnits getVBaseOffset() const {
109    assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
110
111    return getOffset();
112  }
113
114  CharUnits getOffsetToTop() const {
115    assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
116
117    return getOffset();
118  }
119
120  const CXXRecordDecl *getRTTIDecl() const {
121    assert(getKind() == CK_RTTI && "Invalid component kind!");
122
123    return reinterpret_cast<CXXRecordDecl *>(getPointer());
124  }
125
126  const CXXMethodDecl *getFunctionDecl() const {
127    assert(getKind() == CK_FunctionPointer);
128
129    return reinterpret_cast<CXXMethodDecl *>(getPointer());
130  }
131
132  const CXXDestructorDecl *getDestructorDecl() const {
133    assert((getKind() == CK_CompleteDtorPointer ||
134            getKind() == CK_DeletingDtorPointer) && "Invalid component kind!");
135
136    return reinterpret_cast<CXXDestructorDecl *>(getPointer());
137  }
138
139  const CXXMethodDecl *getUnusedFunctionDecl() const {
140    assert(getKind() == CK_UnusedFunctionPointer);
141
142    return reinterpret_cast<CXXMethodDecl *>(getPointer());
143  }
144
145private:
146  VTableComponent(Kind ComponentKind, CharUnits Offset) {
147    assert((ComponentKind == CK_VCallOffset ||
148            ComponentKind == CK_VBaseOffset ||
149            ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
150    assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
151    assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
152
153    Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
154  }
155
156  VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
157    assert((ComponentKind == CK_RTTI ||
158            ComponentKind == CK_FunctionPointer ||
159            ComponentKind == CK_CompleteDtorPointer ||
160            ComponentKind == CK_DeletingDtorPointer ||
161            ComponentKind == CK_UnusedFunctionPointer) &&
162            "Invalid component kind!");
163
164    assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
165
166    Value = Ptr | ComponentKind;
167  }
168
169  CharUnits getOffset() const {
170    assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
171            getKind() == CK_OffsetToTop) && "Invalid component kind!");
172
173    return CharUnits::fromQuantity(Value >> 3);
174  }
175
176  uintptr_t getPointer() const {
177    assert((getKind() == CK_RTTI ||
178            getKind() == CK_FunctionPointer ||
179            getKind() == CK_CompleteDtorPointer ||
180            getKind() == CK_DeletingDtorPointer ||
181            getKind() == CK_UnusedFunctionPointer) &&
182           "Invalid component kind!");
183
184    return static_cast<uintptr_t>(Value & ~7ULL);
185  }
186
187  explicit VTableComponent(uint64_t Value)
188    : Value(Value) { }
189
190  /// The kind is stored in the lower 3 bits of the value. For offsets, we
191  /// make use of the facts that classes can't be larger than 2^55 bytes,
192  /// so we store the offset in the lower part of the 61 bytes that remain.
193  /// (The reason that we're not simply using a PointerIntPair here is that we
194  /// need the offsets to be 64-bit, even when on a 32-bit machine).
195  int64_t Value;
196};
197
198class VTableLayout {
199public:
200  typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
201  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
202
203  typedef const VTableComponent *vtable_component_iterator;
204  typedef const VTableThunkTy *vtable_thunk_iterator;
205
206  typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
207private:
208  uint64_t NumVTableComponents;
209  llvm::OwningArrayPtr<VTableComponent> VTableComponents;
210
211  /// VTableThunks - Contains thunks needed by vtables.
212  uint64_t NumVTableThunks;
213  llvm::OwningArrayPtr<VTableThunkTy> VTableThunks;
214
215  /// Address points - Address points for all vtables.
216  AddressPointsMapTy AddressPoints;
217
218  bool IsMicrosoftABI;
219
220public:
221  VTableLayout(uint64_t NumVTableComponents,
222               const VTableComponent *VTableComponents,
223               uint64_t NumVTableThunks,
224               const VTableThunkTy *VTableThunks,
225               const AddressPointsMapTy &AddressPoints,
226               bool IsMicrosoftABI);
227  ~VTableLayout();
228
229  uint64_t getNumVTableComponents() const {
230    return NumVTableComponents;
231  }
232
233  vtable_component_iterator vtable_component_begin() const {
234   return VTableComponents.get();
235  }
236
237  vtable_component_iterator vtable_component_end() const {
238   return VTableComponents.get()+NumVTableComponents;
239  }
240
241  uint64_t getNumVTableThunks() const {
242    return NumVTableThunks;
243  }
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 VTableContext {
270  ASTContext &Context;
271
272public:
273  typedef SmallVector<std::pair<uint64_t, ThunkInfo>, 1>
274    VTableThunksTy;
275  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
276
277private:
278  bool IsMicrosoftABI;
279
280  /// MethodVTableIndices - Contains the index (relative to the vtable address
281  /// point) where the function pointer for a virtual function is stored.
282  typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
283  MethodVTableIndicesTy MethodVTableIndices;
284
285  typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
286    VTableLayoutMapTy;
287  VTableLayoutMapTy VTableLayouts;
288
289  /// NumVirtualFunctionPointers - Contains the number of virtual function
290  /// pointers in the vtable for a given record decl.
291  llvm::DenseMap<const CXXRecordDecl *, uint64_t> NumVirtualFunctionPointers;
292
293  typedef std::pair<const CXXRecordDecl *,
294                    const CXXRecordDecl *> ClassPairTy;
295
296  /// VirtualBaseClassOffsetOffsets - Contains the vtable offset (relative to
297  /// the address point) in chars where the offsets for virtual bases of a class
298  /// are stored.
299  typedef llvm::DenseMap<ClassPairTy, CharUnits>
300    VirtualBaseClassOffsetOffsetsMapTy;
301  VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
302
303  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
304
305  /// Thunks - Contains all thunks that a given method decl will need.
306  ThunksMapTy Thunks;
307
308  void ComputeMethodVTableIndices(const CXXRecordDecl *RD);
309
310  /// ComputeVTableRelatedInformation - Compute and store all vtable related
311  /// information (vtable layout, vbase offset offsets, thunks etc) for the
312  /// given record decl.
313  void ComputeVTableRelatedInformation(const CXXRecordDecl *RD);
314
315  /// ErrorUnsupported - Print out an error that the v-table layout code
316  /// doesn't support the particular C++ feature yet.
317  void ErrorUnsupported(StringRef Feature, SourceLocation Location);
318
319public:
320  VTableContext(ASTContext &Context);
321  ~VTableContext();
322
323  bool isMicrosoftABI() const {
324    // FIXME: Currently, this method is only used in the VTableContext and
325    // VTableBuilder code which is ABI-specific. Probably we can remove it
326    // when we add a layer of abstraction for vtable generation.
327    return IsMicrosoftABI;
328  }
329
330  const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
331    ComputeVTableRelatedInformation(RD);
332    assert(VTableLayouts.count(RD) && "No layout for this record decl!");
333
334    return *VTableLayouts[RD];
335  }
336
337  VTableLayout *
338  createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
339                                 CharUnits MostDerivedClassOffset,
340                                 bool MostDerivedClassIsVirtual,
341                                 const CXXRecordDecl *LayoutClass);
342
343  const ThunkInfoVectorTy *getThunkInfo(const CXXMethodDecl *MD) {
344    ComputeVTableRelatedInformation(MD->getParent());
345
346    ThunksMapTy::const_iterator I = Thunks.find(MD);
347    if (I == Thunks.end()) {
348      // We did not find a thunk for this method.
349      return 0;
350    }
351
352    return &I->second;
353  }
354
355  /// getNumVirtualFunctionPointers - Return the number of virtual function
356  /// pointers in the vtable for a given record decl.
357  uint64_t getNumVirtualFunctionPointers(const CXXRecordDecl *RD);
358
359  /// getMethodVTableIndex - Return the index (relative to the vtable address
360  /// point) where the function pointer for the given virtual function is
361  /// stored.
362  uint64_t getMethodVTableIndex(GlobalDecl GD);
363
364  /// getVirtualBaseOffsetOffset - Return the offset in chars (relative to the
365  /// vtable address point) where the offset of the virtual base that contains
366  /// the given base is stored, otherwise, if no virtual base contains the given
367  /// class, return 0.  Base must be a virtual base class or an unambigious
368  /// base.
369  CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
370                                       const CXXRecordDecl *VBase);
371};
372
373}
374
375#endif
376