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 /// \brief 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     /// \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 
    147 private:
    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 
    200 class VTableLayout {
    201 public:
    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;
    209 private:
    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 
    222 public:
    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 
    271 class VTableContextBase {
    272 public:
    273   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
    274 
    275 protected:
    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 
    287 public:
    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.
    302 class VTableContext : public VTableContextBase {
    303 private:
    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 
    328 public:
    329   VTableContext(ASTContext &Context);
    330   ~VTableContext();
    331 
    332   bool isMicrosoftABI() const {
    333     // FIXME: Currently, this method is only used in the VTableContext and
    334     // VTableBuilder code which is ABI-specific. Probably we can remove it
    335     // when we add a layer of abstraction for vtable generation.
    336     return IsMicrosoftABI;
    337   }
    338 
    339   const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
    340     computeVTableRelatedInformation(RD);
    341     assert(VTableLayouts.count(RD) && "No layout for this record decl!");
    342 
    343     return *VTableLayouts[RD];
    344   }
    345 
    346   VTableLayout *
    347   createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
    348                                  CharUnits MostDerivedClassOffset,
    349                                  bool MostDerivedClassIsVirtual,
    350                                  const CXXRecordDecl *LayoutClass);
    351 
    352   /// \brief Locate a virtual function in the vtable.
    353   ///
    354   /// Return the index (relative to the vtable address point) where the
    355   /// function pointer for the given virtual function is stored.
    356   uint64_t getMethodVTableIndex(GlobalDecl GD);
    357 
    358   /// Return the offset in chars (relative to the vtable address point) where
    359   /// the offset of the virtual base that contains the given base is stored,
    360   /// otherwise, if no virtual base contains the given class, return 0.
    361   ///
    362   /// Base must be a virtual base class or an unambiguous base.
    363   CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
    364                                        const CXXRecordDecl *VBase);
    365 };
    366 
    367 /// \brief Computes the index of VBase in the vbtable of Derived.
    368 /// VBase must be a morally virtual base of Derived.  The vbtable is
    369 /// an array of i32 offsets.  The first entry is a self entry, and the rest are
    370 /// offsets from the vbptr to virtual bases.  The bases are ordered the same way
    371 /// our vbases are ordered: as they appear in a left-to-right depth-first search
    372 /// of the hierarchy.
    373 // FIXME: make this a static method of VBTableBuilder when we move it to AST.
    374 unsigned GetVBTableIndex(const CXXRecordDecl *Derived,
    375                          const CXXRecordDecl *VBase);
    376 
    377 struct VFPtrInfo {
    378   typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
    379 
    380   VFPtrInfo(CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr)
    381       : VBTableIndex(0), LastVBase(0), VFPtrOffset(VFPtrOffset),
    382         PathToBaseWithVFPtr(PathToBaseWithVFPtr), VFPtrFullOffset(VFPtrOffset) {
    383   }
    384 
    385   VFPtrInfo(uint64_t VBTableIndex, const CXXRecordDecl *LastVBase,
    386             CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr,
    387             CharUnits VFPtrFullOffset)
    388       : VBTableIndex(VBTableIndex), LastVBase(LastVBase),
    389         VFPtrOffset(VFPtrOffset), PathToBaseWithVFPtr(PathToBaseWithVFPtr),
    390         VFPtrFullOffset(VFPtrFullOffset) {
    391     assert(VBTableIndex && "The full constructor should only be used "
    392                            "for vfptrs in virtual bases");
    393     assert(LastVBase);
    394   }
    395 
    396   /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
    397   uint64_t VBTableIndex;
    398 
    399   /// Stores the last vbase on the path from the complete type to the vfptr.
    400   const CXXRecordDecl *LastVBase;
    401 
    402   /// This is the offset of the vfptr from the start of the last vbase,
    403   /// or the complete type if there are no virtual bases.
    404   CharUnits VFPtrOffset;
    405 
    406   /// This holds the base classes path from the complete type to the first base
    407   /// with the given vfptr offset.
    408   BasePath PathToBaseWithVFPtr;
    409 
    410   /// This is the full offset of the vfptr from the start of the complete type.
    411   CharUnits VFPtrFullOffset;
    412 };
    413 
    414 class MicrosoftVFTableContext : public VTableContextBase {
    415 public:
    416   struct MethodVFTableLocation {
    417     /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
    418     uint64_t VBTableIndex;
    419 
    420     /// This is the offset of the vfptr from the start of the last vbase, or the
    421     /// complete type if there are no virtual bases.
    422     CharUnits VFTableOffset;
    423 
    424     /// Method's index in the vftable.
    425     uint64_t Index;
    426 
    427     MethodVFTableLocation()
    428         : VBTableIndex(0), VFTableOffset(CharUnits::Zero()), Index(0) {}
    429 
    430     MethodVFTableLocation(uint64_t VBTableIndex, CharUnits VFTableOffset,
    431                           uint64_t Index)
    432         : VBTableIndex(VBTableIndex), VFTableOffset(VFTableOffset),
    433           Index(Index) {}
    434 
    435     bool operator<(const MethodVFTableLocation &other) const {
    436       if (VBTableIndex != other.VBTableIndex)
    437         return VBTableIndex < other.VBTableIndex;
    438       if (VFTableOffset != other.VFTableOffset)
    439         return VFTableOffset < other.VFTableOffset;
    440       return Index < other.Index;
    441     }
    442   };
    443 
    444   typedef SmallVector<VFPtrInfo, 1> VFPtrListTy;
    445 
    446 private:
    447   ASTContext &Context;
    448 
    449   typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
    450     MethodVFTableLocationsTy;
    451   MethodVFTableLocationsTy MethodVFTableLocations;
    452 
    453   typedef llvm::DenseMap<const CXXRecordDecl *, VFPtrListTy>
    454     VFPtrLocationsMapTy;
    455   VFPtrLocationsMapTy VFPtrLocations;
    456 
    457   typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
    458   typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
    459   VFTableLayoutMapTy VFTableLayouts;
    460 
    461   void computeVTableRelatedInformation(const CXXRecordDecl *RD);
    462 
    463   void dumpMethodLocations(const CXXRecordDecl *RD,
    464                            const MethodVFTableLocationsTy &NewMethods,
    465                            raw_ostream &);
    466 
    467 public:
    468   MicrosoftVFTableContext(ASTContext &Context) : Context(Context) {}
    469 
    470   ~MicrosoftVFTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); }
    471 
    472   const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD);
    473 
    474   const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
    475                                        CharUnits VFPtrOffset);
    476 
    477   const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
    478 };
    479 }
    480 
    481 #endif
    482