Home | History | Annotate | Download | only in AST 
      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 
     56   static VTableComponent MakeVCallOffset(CharUnits Offset) {
     57     return VTableComponent(CK_VCallOffset, Offset);
     58   }
     59 
     60   static VTableComponent MakeVBaseOffset(CharUnits Offset) {
     61     return VTableComponent(CK_VBaseOffset, Offset);
     62   }
     63 
     64   static VTableComponent MakeOffsetToTop(CharUnits Offset) {
     65     return VTableComponent(CK_OffsetToTop, Offset);
     66   }
     67 
     68   static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
     69     return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
     70   }
     71 
     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 
     80   static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
     81     return VTableComponent(CK_CompleteDtorPointer,
     82                            reinterpret_cast<uintptr_t>(DD));
     83   }
     84 
     85   static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
     86     return VTableComponent(CK_DeletingDtorPointer,
     87                            reinterpret_cast<uintptr_t>(DD));
     88   }
     89 
     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 
     97   static VTableComponent getFromOpaqueInteger(uint64_t I) {
     98     return VTableComponent(I);
     99   }
    100 
    101   /// \brief Get the kind of this vtable component.
    102   Kind getKind() const {
    103     return (Kind)(Value & 0x7);
    104   }
    105 
    106   CharUnits getVCallOffset() const {
    107     assert(getKind() == CK_VCallOffset && "Invalid component kind!");
    108 
    109     return getOffset();
    110   }
    111 
    112   CharUnits getVBaseOffset() const {
    113     assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
    114 
    115     return getOffset();
    116   }
    117 
    118   CharUnits getOffsetToTop() const {
    119     assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
    120 
    121     return getOffset();
    122   }
    123 
    124   const CXXRecordDecl *getRTTIDecl() const {
    125     assert(isRTTIKind() && "Invalid component kind!");
    126     return reinterpret_cast<CXXRecordDecl *>(getPointer());
    127   }
    128 
    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 
    136   const CXXDestructorDecl *getDestructorDecl() const {
    137     assert(isDestructorKind() && "Invalid component kind!");
    138     return reinterpret_cast<CXXDestructorDecl *>(getPointer());
    139   }
    140 
    141   const CXXMethodDecl *getUnusedFunctionDecl() const {
    142     assert(getKind() == CK_UnusedFunctionPointer && "Invalid component kind!");
    143     return reinterpret_cast<CXXMethodDecl *>(getPointer());
    144   }
    145 
    146   bool isDestructorKind() const { return isDestructorKind(getKind()); }
    147 
    148   bool isUsedFunctionPointerKind() const {
    149     return isUsedFunctionPointerKind(getKind());
    150   }
    151 
    152   bool isFunctionPointerKind() const {
    153     return isFunctionPointerKind(getKind());
    154   }
    155 
    156   bool isRTTIKind() const { return isRTTIKind(getKind()); }
    157 
    158 private:
    159   static bool isFunctionPointerKind(Kind ComponentKind) {
    160     return isUsedFunctionPointerKind(ComponentKind) ||
    161            ComponentKind == CK_UnusedFunctionPointer;
    162   }
    163   static bool isUsedFunctionPointerKind(Kind ComponentKind) {
    164     return ComponentKind == CK_FunctionPointer ||
    165            isDestructorKind(ComponentKind);
    166   }
    167   static bool isDestructorKind(Kind ComponentKind) {
    168     return ComponentKind == CK_CompleteDtorPointer ||
    169            ComponentKind == CK_DeletingDtorPointer;
    170   }
    171   static bool isRTTIKind(Kind ComponentKind) {
    172     return ComponentKind == CK_RTTI;
    173   }
    174 
    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 
    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 
    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 
    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 
    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 
    252   uint64_t getNumVTableComponents() const {
    253     return NumVTableComponents;
    254   }
    255 
    256   vtable_component_range vtable_components() const {
    257     return vtable_component_range(vtable_component_begin(),
    258                                   vtable_component_end());
    259   }
    260 
    261   vtable_component_iterator vtable_component_begin() const {
    262     return VTableComponents.get();
    263   }
    264 
    265   vtable_component_iterator vtable_component_end() const {
    266     return VTableComponents.get() + NumVTableComponents;
    267   }
    268 
    269   uint64_t getNumVTableThunks() const { return NumVTableThunks; }
    270 
    271   vtable_thunk_iterator vtable_thunk_begin() const {
    272     return VTableThunks.get();
    273   }
    274 
    275   vtable_thunk_iterator vtable_thunk_end() const {
    276     return VTableThunks.get() + NumVTableThunks;
    277   }
    278 
    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 
    290   const AddressPointsMapTy &getAddressPoints() const {
    291     return AddressPoints;
    292   }
    293 };
    294 
    295 class VTableContextBase {
    296 public:
    297   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
    298 
    299   bool isMicrosoft() const { return IsMicrosoftABI; }
    300 
    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 
    313   VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
    314 
    315 public:
    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 
    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 
    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 
    401   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.
    442   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 {
    453   ~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 
    481     MethodVFTableLocation()
    482         : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
    483           Index(0) {}
    484 
    485     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:
    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 
    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 
    561   static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }
    562 };
    563 
    564 } // namespace clang
    565 
    566 #endif
    567