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/SetVector.h"
     23 #include <utility>
     24 
     25 namespace clang {
     26   class CXXRecordDecl;
     27 
     28 /// VTableComponent - Represents a single component in a vtable.
     29 class VTableComponent {
     30 public:
     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 
    145 private:
    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 
    198 class VTableLayout {
    199 public:
    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;
    207 private:
    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 
    220 public:
    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 
    269 class VTableContext {
    270   ASTContext &Context;
    271 
    272 public:
    273   typedef SmallVector<std::pair<uint64_t, ThunkInfo>, 1>
    274     VTableThunksTy;
    275   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
    276 
    277 private:
    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 
    319 public:
    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