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