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 "llvm/ADT/DenseSet.h"
  24 #include <utility>
  25
  26 namespace clang {
  27   class CXXRecordDecl;
  28
  29 /// \brief Represents a single component in a vtable.
  30 class VTableComponent {
  31 public:
  32   enum Kind {
  33     CK_VCallOffset,
  34     CK_VBaseOffset,
  35     CK_OffsetToTop,
  36     CK_RTTI,
  37     CK_FunctionPointer,
  38
  39     /// \brief A pointer to the complete destructor.
  40     CK_CompleteDtorPointer,
  41
  42     /// \brief A pointer to the deleting destructor.
  43     CK_DeletingDtorPointer,
  44
  45     /// \brief An entry that is never used.
  46     ///
  47     /// In some cases, a vtable function pointer will end up never being
  48     /// called. Such vtable function pointers are represented as a
  49     /// CK_UnusedFunctionPointer.
  50     CK_UnusedFunctionPointer
  51   };
  52
  53   VTableComponent() { }
  54
  55   static VTableComponent MakeVCallOffset(CharUnits Offset) {
  56     return VTableComponent(CK_VCallOffset, Offset);
  57   }
  58
  59   static VTableComponent MakeVBaseOffset(CharUnits Offset) {
  60     return VTableComponent(CK_VBaseOffset, Offset);
  61   }
  62
  63   static VTableComponent MakeOffsetToTop(CharUnits Offset) {
  64     return VTableComponent(CK_OffsetToTop, Offset);
  65   }
  66
  67   static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
  68     return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
  69   }
  70
  71   static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
  72     assert(!isa<CXXDestructorDecl>(MD) &&
  73            "Don't use MakeFunction with destructors!");
  74
  75     return VTableComponent(CK_FunctionPointer,
  76                            reinterpret_cast<uintptr_t>(MD));
  77   }
  78
  79   static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
  80     return VTableComponent(CK_CompleteDtorPointer,
  81                            reinterpret_cast<uintptr_t>(DD));
  82   }
  83
  84   static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
  85     return VTableComponent(CK_DeletingDtorPointer,
  86                            reinterpret_cast<uintptr_t>(DD));
  87   }
  88
  89   static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) {
  90     assert(!isa<CXXDestructorDecl>(MD) &&
  91            "Don't use MakeUnusedFunction with destructors!");
  92     return VTableComponent(CK_UnusedFunctionPointer,
  93                            reinterpret_cast<uintptr_t>(MD));
  94   }
  95
  96   static VTableComponent getFromOpaqueInteger(uint64_t I) {
  97     return VTableComponent(I);
  98   }
  99
 100   /// \brief Get the kind of this vtable component.
 101   Kind getKind() const {
 102     return (Kind)(Value & 0x7);
 103   }
 104
 105   CharUnits getVCallOffset() const {
 106     assert(getKind() == CK_VCallOffset && "Invalid component kind!");
 107
 108     return getOffset();
 109   }
 110
 111   CharUnits getVBaseOffset() const {
 112     assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
 113
 114     return getOffset();
 115   }
 116
 117   CharUnits getOffsetToTop() const {
 118     assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
 119
 120     return getOffset();
 121   }
 122
 123   const CXXRecordDecl *getRTTIDecl() const {
 124     assert(getKind() == CK_RTTI && "Invalid component kind!");
 125
 126     return reinterpret_cast<CXXRecordDecl *>(getPointer());
 127   }
 128
 129   const CXXMethodDecl *getFunctionDecl() const {
 130     assert(getKind() == CK_FunctionPointer);
 131
 132     return reinterpret_cast<CXXMethodDecl *>(getPointer());
 133   }
 134
 135   const CXXDestructorDecl *getDestructorDecl() const {
 136     assert((getKind() == CK_CompleteDtorPointer ||
 137             getKind() == CK_DeletingDtorPointer) && "Invalid component kind!");
 138
 139     return reinterpret_cast<CXXDestructorDecl *>(getPointer());
 140   }
 141
 142   const CXXMethodDecl *getUnusedFunctionDecl() const {
 143     assert(getKind() == CK_UnusedFunctionPointer);
 144
 145     return reinterpret_cast<CXXMethodDecl *>(getPointer());
 146   }
 147
 148 private:
 149   VTableComponent(Kind ComponentKind, CharUnits Offset) {
 150     assert((ComponentKind == CK_VCallOffset ||
 151             ComponentKind == CK_VBaseOffset ||
 152             ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
 153     assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
 154     assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
 155
 156     Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
 157   }
 158
 159   VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
 160     assert((ComponentKind == CK_RTTI ||
 161             ComponentKind == CK_FunctionPointer ||
 162             ComponentKind == CK_CompleteDtorPointer ||
 163             ComponentKind == CK_DeletingDtorPointer ||
 164             ComponentKind == CK_UnusedFunctionPointer) &&
 165             "Invalid component kind!");
 166
 167     assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
 168
 169     Value = Ptr | ComponentKind;
 170   }
 171
 172   CharUnits getOffset() const {
 173     assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
 174             getKind() == CK_OffsetToTop) && "Invalid component kind!");
 175
 176     return CharUnits::fromQuantity(Value >> 3);
 177   }
 178
 179   uintptr_t getPointer() const {
 180     assert((getKind() == CK_RTTI ||
 181             getKind() == CK_FunctionPointer ||
 182             getKind() == CK_CompleteDtorPointer ||
 183             getKind() == CK_DeletingDtorPointer ||
 184             getKind() == CK_UnusedFunctionPointer) &&
 185            "Invalid component kind!");
 186
 187     return static_cast<uintptr_t>(Value & ~7ULL);
 188   }
 189
 190   explicit VTableComponent(uint64_t Value)
 191     : Value(Value) { }
 192
 193   /// The kind is stored in the lower 3 bits of the value. For offsets, we
 194   /// make use of the facts that classes can't be larger than 2^55 bytes,
 195   /// so we store the offset in the lower part of the 61 bits that remain.
 196   /// (The reason that we're not simply using a PointerIntPair here is that we
 197   /// need the offsets to be 64-bit, even when on a 32-bit machine).
 198   int64_t Value;
 199 };
 200
 201 class VTableLayout {
 202 public:
 203   typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
 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, sorted by indices.
 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 { return NumVTableThunks; }
 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 VTableContextBase {
 270 public:
 271   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 272
 273 protected:
 274   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
 275
 276   /// \brief Contains all thunks that a given method decl will need.
 277   ThunksMapTy Thunks;
 278
 279   /// Compute and store all vtable related information (vtable layout, vbase
 280   /// offset offsets, thunks etc) for the given record decl.
 281   virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
 282
 283   virtual ~VTableContextBase() {}
 284
 285 public:
 286   virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
 287     const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
 288     computeVTableRelatedInformation(MD->getParent());
 289
 290     // This assumes that all the destructors present in the vtable
 291     // use exactly the same set of thunks.
 292     ThunksMapTy::const_iterator I = Thunks.find(MD);
 293     if (I == Thunks.end()) {
 294       // We did not find a thunk for this method.
 295       return 0;
 296     }
 297
 298     return &I->second;
 299   }
 300 };
 301
 302 class ItaniumVTableContext : 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   ItaniumVTableContext(ASTContext &Context);
 330   ~ItaniumVTableContext();
 331
 332   const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
 333     computeVTableRelatedInformation(RD);
 334     assert(VTableLayouts.count(RD) && "No layout for this record decl!");
 335
 336     return *VTableLayouts[RD];
 337   }
 338
 339   VTableLayout *
 340   createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
 341                                  CharUnits MostDerivedClassOffset,
 342                                  bool MostDerivedClassIsVirtual,
 343                                  const CXXRecordDecl *LayoutClass);
 344
 345   /// \brief Locate a virtual function in the vtable.
 346   ///
 347   /// Return the index (relative to the vtable address point) where the
 348   /// function pointer for the given virtual function is stored.
 349   uint64_t getMethodVTableIndex(GlobalDecl GD);
 350
 351   /// Return the offset in chars (relative to the vtable address point) where
 352   /// the offset of the virtual base that contains the given base is stored,
 353   /// otherwise, if no virtual base contains the given class, return 0.
 354   ///
 355   /// Base must be a virtual base class or an unambiguous base.
 356   CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
 357                                        const CXXRecordDecl *VBase);
 358 };
 359
 360 struct VFPtrInfo {
 361   typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
 362
 363   // Don't pass the PathToMangle as it should be calculated later.
 364   VFPtrInfo(CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr)
 365       : VBTableIndex(0), LastVBase(0), VFPtrOffset(VFPtrOffset),
 366         PathToBaseWithVFPtr(PathToBaseWithVFPtr), VFPtrFullOffset(VFPtrOffset) {
 367   }
 368
 369   // Don't pass the PathToMangle as it should be calculated later.
 370   VFPtrInfo(uint64_t VBTableIndex, const CXXRecordDecl *LastVBase,
 371             CharUnits VFPtrOffset, const BasePath &PathToBaseWithVFPtr,
 372             CharUnits VFPtrFullOffset)
 373       : VBTableIndex(VBTableIndex), LastVBase(LastVBase),
 374         VFPtrOffset(VFPtrOffset), PathToBaseWithVFPtr(PathToBaseWithVFPtr),
 375         VFPtrFullOffset(VFPtrFullOffset) {
 376     assert(VBTableIndex && "The full constructor should only be used "
 377                            "for vfptrs in virtual bases");
 378     assert(LastVBase);
 379   }
 380
 381   /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
 382   uint64_t VBTableIndex;
 383
 384   /// Stores the last vbase on the path from the complete type to the vfptr.
 385   const CXXRecordDecl *LastVBase;
 386
 387   /// This is the offset of the vfptr from the start of the last vbase,
 388   /// or the complete type if there are no virtual bases.
 389   CharUnits VFPtrOffset;
 390
 391   /// This holds the base classes path from the complete type to the first base
 392   /// with the given vfptr offset, in the base-to-derived order.
 393   BasePath PathToBaseWithVFPtr;
 394
 395   /// This holds the subset of records that need to be mangled into the vftable
 396   /// symbol name in order to get a unique name, in the derived-to-base order.
 397   BasePath PathToMangle;
 398
 399   /// This is the full offset of the vfptr from the start of the complete type.
 400   CharUnits VFPtrFullOffset;
 401 };
 402
 403 class MicrosoftVTableContext : public VTableContextBase {
 404 public:
 405   struct MethodVFTableLocation {
 406     /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
 407     uint64_t VBTableIndex;
 408
 409     /// If nonnull, holds the last vbase which contains the vfptr that the
 410     /// method definition is adjusted to.
 411     const CXXRecordDecl *VBase;
 412
 413     /// This is the offset of the vfptr from the start of the last vbase, or the
 414     /// complete type if there are no virtual bases.
 415     CharUnits VFPtrOffset;
 416
 417     /// Method's index in the vftable.
 418     uint64_t Index;
 419
 420     MethodVFTableLocation()
 421         : VBTableIndex(0), VBase(0), VFPtrOffset(CharUnits::Zero()),
 422           Index(0) {}
 423
 424     MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
 425                           CharUnits VFPtrOffset, uint64_t Index)
 426         : VBTableIndex(VBTableIndex), VBase(VBase),
 427           VFPtrOffset(VFPtrOffset), Index(Index) {}
 428
 429     bool operator<(const MethodVFTableLocation &other) const {
 430       if (VBTableIndex != other.VBTableIndex) {
 431         assert(VBase != other.VBase);
 432         return VBTableIndex < other.VBTableIndex;
 433       }
 434       if (VFPtrOffset != other.VFPtrOffset)
 435         return VFPtrOffset < other.VFPtrOffset;
 436       if (Index != other.Index)
 437         return Index < other.Index;
 438       return false;
 439     }
 440   };
 441
 442   typedef SmallVector<VFPtrInfo, 1> VFPtrListTy;
 443
 444 private:
 445   ASTContext &Context;
 446
 447   typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
 448     MethodVFTableLocationsTy;
 449   MethodVFTableLocationsTy MethodVFTableLocations;
 450
 451   typedef llvm::DenseMap<const CXXRecordDecl *, VFPtrListTy>
 452     VFPtrLocationsMapTy;
 453   VFPtrLocationsMapTy VFPtrLocations;
 454
 455   typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
 456   typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
 457   VFTableLayoutMapTy VFTableLayouts;
 458
 459   typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
 460   void enumerateVFPtrs(const CXXRecordDecl *MostDerivedClass,
 461                        const ASTRecordLayout &MostDerivedClassLayout,
 462                        BaseSubobject Base, const CXXRecordDecl *LastVBase,
 463                        const VFPtrInfo::BasePath &PathFromCompleteClass,
 464                        BasesSetVectorTy &VisitedVBases,
 465                        MicrosoftVTableContext::VFPtrListTy &Result);
 466
 467   void enumerateVFPtrs(const CXXRecordDecl *ForClass,
 468                        MicrosoftVTableContext::VFPtrListTy &Result);
 469
 470   void computeVTableRelatedInformation(const CXXRecordDecl *RD);
 471
 472   void dumpMethodLocations(const CXXRecordDecl *RD,
 473                            const MethodVFTableLocationsTy &NewMethods,
 474                            raw_ostream &);
 475
 476   typedef std::pair<const CXXRecordDecl *, const CXXRecordDecl *> ClassPairTy;
 477   typedef llvm::DenseMap<ClassPairTy, unsigned> VBTableIndicesTy;
 478   VBTableIndicesTy VBTableIndices;
 479   llvm::DenseSet<const CXXRecordDecl *> ComputedVBTableIndices;
 480
 481   void computeVBTableRelatedInformation(const CXXRecordDecl *RD);
 482
 483 public:
 484   MicrosoftVTableContext(ASTContext &Context) : Context(Context) {}
 485
 486   ~MicrosoftVTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); }
 487
 488   const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD);
 489
 490   const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
 491                                        CharUnits VFPtrOffset);
 492
 493   const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
 494
 495   const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
 496     // Complete destructors don't have a slot in a vftable, so no thunks needed.
 497     if (isa<CXXDestructorDecl>(GD.getDecl()) &&
 498         GD.getDtorType() == Dtor_Complete)
 499       return 0;
 500     return VTableContextBase::getThunkInfo(GD);
 501   }
 502
 503   /// \brief Returns the index of VBase in the vbtable of Derived.
 504   /// VBase must be a morally virtual base of Derived.
 505   /// The vbtable is an array of i32 offsets.  The first entry is a self entry,
 506   /// and the rest are offsets from the vbptr to virtual bases.
 507   unsigned getVBTableIndex(const CXXRecordDecl *Derived,
 508                            const CXXRecordDecl *VBase) {
 509     computeVBTableRelatedInformation(Derived);
 510     ClassPairTy Pair(Derived, VBase);
 511     assert(VBTableIndices.count(Pair) == 1 &&
 512            "VBase must be a vbase of Derived");
 513     return VBTableIndices[Pair];
 514   }
 515 };
 516 }
 517
 518 #endif