contrib/llvm/tools/clang/include/clang/AST/VTableBuilder.h

   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 public:
 219   VTableLayout(uint64_t NumVTableComponents,
 220                const VTableComponent *VTableComponents,
 221                uint64_t NumVTableThunks,
 222                const VTableThunkTy *VTableThunks,
 223                const AddressPointsMapTy &AddressPoints);
 224   ~VTableLayout();
 225
 226   uint64_t getNumVTableComponents() const {
 227     return NumVTableComponents;
 228   }
 229
 230   vtable_component_iterator vtable_component_begin() const {
 231    return VTableComponents.get();
 232   }
 233
 234   vtable_component_iterator vtable_component_end() const {
 235    return VTableComponents.get()+NumVTableComponents;
 236   }
 237
 238   uint64_t getNumVTableThunks() const {
 239     return NumVTableThunks;
 240   }
 241
 242   vtable_thunk_iterator vtable_thunk_begin() const {
 243    return VTableThunks.get();
 244   }
 245
 246   vtable_thunk_iterator vtable_thunk_end() const {
 247    return VTableThunks.get()+NumVTableThunks;
 248   }
 249
 250   uint64_t getAddressPoint(BaseSubobject Base) const {
 251     assert(AddressPoints.count(Base) &&
 252            "Did not find address point!");
 253
 254     uint64_t AddressPoint = AddressPoints.lookup(Base);
 255     assert(AddressPoint && "Address point must not be zero!");
 256
 257     return AddressPoint;
 258   }
 259
 260   const AddressPointsMapTy &getAddressPoints() const {
 261     return AddressPoints;
 262   }
 263 };
 264
 265 class VTableContext {
 266   ASTContext &Context;
 267
 268 public:
 269   typedef SmallVector<std::pair<uint64_t, ThunkInfo>, 1>
 270     VTableThunksTy;
 271   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 272
 273 private:
 274   /// MethodVTableIndices - Contains the index (relative to the vtable address
 275   /// point) where the function pointer for a virtual function is stored.
 276   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
 277   MethodVTableIndicesTy MethodVTableIndices;
 278
 279   typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
 280     VTableLayoutMapTy;
 281   VTableLayoutMapTy VTableLayouts;
 282
 283   /// NumVirtualFunctionPointers - Contains the number of virtual function
 284   /// pointers in the vtable for a given record decl.
 285   llvm::DenseMap<const CXXRecordDecl *, uint64_t> NumVirtualFunctionPointers;
 286
 287   typedef std::pair<const CXXRecordDecl *,
 288                     const CXXRecordDecl *> ClassPairTy;
 289
 290   /// VirtualBaseClassOffsetOffsets - Contains the vtable offset (relative to
 291   /// the address point) in chars where the offsets for virtual bases of a class
 292   /// are stored.
 293   typedef llvm::DenseMap<ClassPairTy, CharUnits>
 294     VirtualBaseClassOffsetOffsetsMapTy;
 295   VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
 296
 297   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
 298
 299   /// Thunks - Contains all thunks that a given method decl will need.
 300   ThunksMapTy Thunks;
 301
 302   void ComputeMethodVTableIndices(const CXXRecordDecl *RD);
 303
 304   /// ComputeVTableRelatedInformation - Compute and store all vtable related
 305   /// information (vtable layout, vbase offset offsets, thunks etc) for the
 306   /// given record decl.
 307   void ComputeVTableRelatedInformation(const CXXRecordDecl *RD);
 308
 309 public:
 310   VTableContext(ASTContext &Context) : Context(Context) {}
 311   ~VTableContext();
 312
 313   const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
 314     ComputeVTableRelatedInformation(RD);
 315     assert(VTableLayouts.count(RD) && "No layout for this record decl!");
 316
 317     return *VTableLayouts[RD];
 318   }
 319
 320   VTableLayout *
 321   createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
 322                                  CharUnits MostDerivedClassOffset,
 323                                  bool MostDerivedClassIsVirtual,
 324                                  const CXXRecordDecl *LayoutClass);
 325
 326   const ThunkInfoVectorTy *getThunkInfo(const CXXMethodDecl *MD) {
 327     ComputeVTableRelatedInformation(MD->getParent());
 328
 329     ThunksMapTy::const_iterator I = Thunks.find(MD);
 330     if (I == Thunks.end()) {
 331       // We did not find a thunk for this method.
 332       return 0;
 333     }
 334
 335     return &I->second;
 336   }
 337
 338   /// getNumVirtualFunctionPointers - Return the number of virtual function
 339   /// pointers in the vtable for a given record decl.
 340   uint64_t getNumVirtualFunctionPointers(const CXXRecordDecl *RD);
 341
 342   /// getMethodVTableIndex - Return the index (relative to the vtable address
 343   /// point) where the function pointer for the given virtual function is
 344   /// stored.
 345   uint64_t getMethodVTableIndex(GlobalDecl GD);
 346
 347   /// getVirtualBaseOffsetOffset - Return the offset in chars (relative to the
 348   /// vtable address point) where the offset of the virtual base that contains
 349   /// the given base is stored, otherwise, if no virtual base contains the given
 350   /// class, return 0.  Base must be a virtual base class or an unambigious
 351   /// base.
 352   CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
 353                                        const CXXRecordDecl *VBase);
 354 };
 355
 356 }
 357
 358 #endif