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   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