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) - 1) && "Offset is too big!");
 151
 152     Value = ((Offset.getQuantity() << 3) | ComponentKind);
 153   }
 154
 155   VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
 156     assert((ComponentKind == CK_RTTI ||
 157             ComponentKind == CK_FunctionPointer ||
 158             ComponentKind == CK_CompleteDtorPointer ||
 159             ComponentKind == CK_DeletingDtorPointer ||
 160             ComponentKind == CK_UnusedFunctionPointer) &&
 161             "Invalid component kind!");
 162
 163     assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
 164
 165     Value = Ptr | ComponentKind;
 166   }
 167
 168   CharUnits getOffset() const {
 169     assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
 170             getKind() == CK_OffsetToTop) && "Invalid component kind!");
 171
 172     return CharUnits::fromQuantity(Value >> 3);
 173   }
 174
 175   uintptr_t getPointer() const {
 176     assert((getKind() == CK_RTTI ||
 177             getKind() == CK_FunctionPointer ||
 178             getKind() == CK_CompleteDtorPointer ||
 179             getKind() == CK_DeletingDtorPointer ||
 180             getKind() == CK_UnusedFunctionPointer) &&
 181            "Invalid component kind!");
 182
 183     return static_cast<uintptr_t>(Value & ~7ULL);
 184   }
 185
 186   explicit VTableComponent(uint64_t Value)
 187     : Value(Value) { }
 188
 189   /// The kind is stored in the lower 3 bits of the value. For offsets, we
 190   /// make use of the facts that classes can't be larger than 2^55 bytes,
 191   /// so we store the offset in the lower part of the 61 bytes that remain.
 192   /// (The reason that we're not simply using a PointerIntPair here is that we
 193   /// need the offsets to be 64-bit, even when on a 32-bit machine).
 194   int64_t Value;
 195 };
 196
 197 class VTableLayout {
 198 public:
 199   typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
 200   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 201
 202   typedef const VTableComponent *vtable_component_iterator;
 203   typedef const VTableThunkTy *vtable_thunk_iterator;
 204
 205   typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
 206 private:
 207   uint64_t NumVTableComponents;
 208   VTableComponent *VTableComponents;
 209
 210   /// VTableThunks - Contains thunks needed by vtables.
 211   uint64_t NumVTableThunks;
 212   VTableThunkTy *VTableThunks;
 213
 214   /// Address points - Address points for all vtables.
 215   AddressPointsMapTy AddressPoints;
 216
 217 public:
 218   VTableLayout(uint64_t NumVTableComponents,
 219                const VTableComponent *VTableComponents,
 220                uint64_t NumVTableThunks,
 221                const VTableThunkTy *VTableThunks,
 222                const AddressPointsMapTy &AddressPoints);
 223   ~VTableLayout();
 224
 225   uint64_t getNumVTableComponents() const {
 226     return NumVTableComponents;
 227   }
 228
 229   vtable_component_iterator vtable_component_begin() const {
 230    return VTableComponents;
 231   }
 232
 233   vtable_component_iterator vtable_component_end() const {
 234    return VTableComponents+NumVTableComponents;
 235   }
 236
 237   uint64_t getNumVTableThunks() const {
 238     return NumVTableThunks;
 239   }
 240
 241   vtable_thunk_iterator vtable_thunk_begin() const {
 242    return VTableThunks;
 243   }
 244
 245   vtable_thunk_iterator vtable_thunk_end() const {
 246    return VTableThunks+NumVTableThunks;
 247   }
 248
 249   uint64_t getAddressPoint(BaseSubobject Base) const {
 250     assert(AddressPoints.count(Base) &&
 251            "Did not find address point!");
 252
 253     uint64_t AddressPoint = AddressPoints.lookup(Base);
 254     assert(AddressPoint && "Address point must not be zero!");
 255
 256     return AddressPoint;
 257   }
 258
 259   const AddressPointsMapTy &getAddressPoints() const {
 260     return AddressPoints;
 261   }
 262 };
 263
 264 class VTableContext {
 265   ASTContext &Context;
 266
 267 public:
 268   typedef SmallVector<std::pair<uint64_t, ThunkInfo>, 1>
 269     VTableThunksTy;
 270   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 271
 272 private:
 273   /// MethodVTableIndices - Contains the index (relative to the vtable address
 274   /// point) where the function pointer for a virtual function is stored.
 275   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
 276   MethodVTableIndicesTy MethodVTableIndices;
 277
 278   typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
 279     VTableLayoutMapTy;
 280   VTableLayoutMapTy VTableLayouts;
 281
 282   /// NumVirtualFunctionPointers - Contains the number of virtual function
 283   /// pointers in the vtable for a given record decl.
 284   llvm::DenseMap<const CXXRecordDecl *, uint64_t> NumVirtualFunctionPointers;
 285
 286   typedef std::pair<const CXXRecordDecl *,
 287                     const CXXRecordDecl *> ClassPairTy;
 288
 289   /// VirtualBaseClassOffsetOffsets - Contains the vtable offset (relative to
 290   /// the address point) in chars where the offsets for virtual bases of a class
 291   /// are stored.
 292   typedef llvm::DenseMap<ClassPairTy, CharUnits>
 293     VirtualBaseClassOffsetOffsetsMapTy;
 294   VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
 295
 296   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
 297
 298   /// Thunks - Contains all thunks that a given method decl will need.
 299   ThunksMapTy Thunks;
 300
 301   void ComputeMethodVTableIndices(const CXXRecordDecl *RD);
 302
 303   /// ComputeVTableRelatedInformation - Compute and store all vtable related
 304   /// information (vtable layout, vbase offset offsets, thunks etc) for the
 305   /// given record decl.
 306   void ComputeVTableRelatedInformation(const CXXRecordDecl *RD);
 307
 308 public:
 309   VTableContext(ASTContext &Context) : Context(Context) {}
 310   ~VTableContext();
 311
 312   const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
 313     ComputeVTableRelatedInformation(RD);
 314     assert(VTableLayouts.count(RD) && "No layout for this record decl!");
 315
 316     return *VTableLayouts[RD];
 317   }
 318
 319   VTableLayout *
 320   createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
 321                                  CharUnits MostDerivedClassOffset,
 322                                  bool MostDerivedClassIsVirtual,
 323                                  const CXXRecordDecl *LayoutClass);
 324
 325   const ThunkInfoVectorTy *getThunkInfo(const CXXMethodDecl *MD) {
 326     ComputeVTableRelatedInformation(MD->getParent());
 327
 328     ThunksMapTy::const_iterator I = Thunks.find(MD);
 329     if (I == Thunks.end()) {
 330       // We did not find a thunk for this method.
 331       return 0;
 332     }
 333
 334     return &I->second;
 335   }
 336
 337   /// getNumVirtualFunctionPointers - Return the number of virtual function
 338   /// pointers in the vtable for a given record decl.
 339   uint64_t getNumVirtualFunctionPointers(const CXXRecordDecl *RD);
 340
 341   /// getMethodVTableIndex - Return the index (relative to the vtable address
 342   /// point) where the function pointer for the given virtual function is
 343   /// stored.
 344   uint64_t getMethodVTableIndex(GlobalDecl GD);
 345
 346   /// getVirtualBaseOffsetOffset - Return the offset in chars (relative to the
 347   /// vtable address point) where the offset of the virtual base that contains
 348   /// the given base is stored, otherwise, if no virtual base contains the given
 349   /// class, return 0.  Base must be a virtual base class or an unambigious
 350   /// base.
 351   CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
 352                                        const CXXRecordDecl *VBase);
 353 };
 354
 355 }
 356
 357 #endif