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/DenseMap.h"
  23 #include "llvm/ADT/SetVector.h"
  24 #include <memory>
  25 #include <utility>
  26
  27 namespace clang {
  28   class CXXRecordDecl;
  29
  30 /// \brief Represents a single component in a vtable.
  31 class VTableComponent {
  32 public:
  33   enum Kind {
  34     CK_VCallOffset,
  35     CK_VBaseOffset,
  36     CK_OffsetToTop,
  37     CK_RTTI,
  38     CK_FunctionPointer,
  39
  40     /// \brief A pointer to the complete destructor.
  41     CK_CompleteDtorPointer,
  42
  43     /// \brief A pointer to the deleting destructor.
  44     CK_DeletingDtorPointer,
  45
  46     /// \brief An entry that is never used.
  47     ///
  48     /// In some cases, a vtable function pointer will end up never being
  49     /// called. Such vtable function pointers are represented as a
  50     /// CK_UnusedFunctionPointer.
  51     CK_UnusedFunctionPointer
  52   };
  53
  54   VTableComponent() { }
  55
  56   static VTableComponent MakeVCallOffset(CharUnits Offset) {
  57     return VTableComponent(CK_VCallOffset, Offset);
  58   }
  59
  60   static VTableComponent MakeVBaseOffset(CharUnits Offset) {
  61     return VTableComponent(CK_VBaseOffset, Offset);
  62   }
  63
  64   static VTableComponent MakeOffsetToTop(CharUnits Offset) {
  65     return VTableComponent(CK_OffsetToTop, Offset);
  66   }
  67
  68   static VTableComponent MakeRTTI(const CXXRecordDecl *RD) {
  69     return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD));
  70   }
  71
  72   static VTableComponent MakeFunction(const CXXMethodDecl *MD) {
  73     assert(!isa<CXXDestructorDecl>(MD) &&
  74            "Don't use MakeFunction with destructors!");
  75
  76     return VTableComponent(CK_FunctionPointer,
  77                            reinterpret_cast<uintptr_t>(MD));
  78   }
  79
  80   static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) {
  81     return VTableComponent(CK_CompleteDtorPointer,
  82                            reinterpret_cast<uintptr_t>(DD));
  83   }
  84
  85   static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) {
  86     return VTableComponent(CK_DeletingDtorPointer,
  87                            reinterpret_cast<uintptr_t>(DD));
  88   }
  89
  90   static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) {
  91     assert(!isa<CXXDestructorDecl>(MD) &&
  92            "Don't use MakeUnusedFunction with destructors!");
  93     return VTableComponent(CK_UnusedFunctionPointer,
  94                            reinterpret_cast<uintptr_t>(MD));
  95   }
  96
  97   static VTableComponent getFromOpaqueInteger(uint64_t I) {
  98     return VTableComponent(I);
  99   }
 100
 101   /// \brief Get the kind of this vtable component.
 102   Kind getKind() const {
 103     return (Kind)(Value & 0x7);
 104   }
 105
 106   CharUnits getVCallOffset() const {
 107     assert(getKind() == CK_VCallOffset && "Invalid component kind!");
 108
 109     return getOffset();
 110   }
 111
 112   CharUnits getVBaseOffset() const {
 113     assert(getKind() == CK_VBaseOffset && "Invalid component kind!");
 114
 115     return getOffset();
 116   }
 117
 118   CharUnits getOffsetToTop() const {
 119     assert(getKind() == CK_OffsetToTop && "Invalid component kind!");
 120
 121     return getOffset();
 122   }
 123
 124   const CXXRecordDecl *getRTTIDecl() const {
 125     assert(getKind() == CK_RTTI && "Invalid component kind!");
 126
 127     return reinterpret_cast<CXXRecordDecl *>(getPointer());
 128   }
 129
 130   const CXXMethodDecl *getFunctionDecl() const {
 131     assert(getKind() == CK_FunctionPointer);
 132
 133     return reinterpret_cast<CXXMethodDecl *>(getPointer());
 134   }
 135
 136   const CXXDestructorDecl *getDestructorDecl() const {
 137     assert((getKind() == CK_CompleteDtorPointer ||
 138             getKind() == CK_DeletingDtorPointer) && "Invalid component kind!");
 139
 140     return reinterpret_cast<CXXDestructorDecl *>(getPointer());
 141   }
 142
 143   const CXXMethodDecl *getUnusedFunctionDecl() const {
 144     assert(getKind() == CK_UnusedFunctionPointer);
 145
 146     return reinterpret_cast<CXXMethodDecl *>(getPointer());
 147   }
 148
 149 private:
 150   VTableComponent(Kind ComponentKind, CharUnits Offset) {
 151     assert((ComponentKind == CK_VCallOffset ||
 152             ComponentKind == CK_VBaseOffset ||
 153             ComponentKind == CK_OffsetToTop) && "Invalid component kind!");
 154     assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!");
 155     assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!");
 156
 157     Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind;
 158   }
 159
 160   VTableComponent(Kind ComponentKind, uintptr_t Ptr) {
 161     assert((ComponentKind == CK_RTTI ||
 162             ComponentKind == CK_FunctionPointer ||
 163             ComponentKind == CK_CompleteDtorPointer ||
 164             ComponentKind == CK_DeletingDtorPointer ||
 165             ComponentKind == CK_UnusedFunctionPointer) &&
 166             "Invalid component kind!");
 167
 168     assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!");
 169
 170     Value = Ptr | ComponentKind;
 171   }
 172
 173   CharUnits getOffset() const {
 174     assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset ||
 175             getKind() == CK_OffsetToTop) && "Invalid component kind!");
 176
 177     return CharUnits::fromQuantity(Value >> 3);
 178   }
 179
 180   uintptr_t getPointer() const {
 181     assert((getKind() == CK_RTTI ||
 182             getKind() == CK_FunctionPointer ||
 183             getKind() == CK_CompleteDtorPointer ||
 184             getKind() == CK_DeletingDtorPointer ||
 185             getKind() == CK_UnusedFunctionPointer) &&
 186            "Invalid component kind!");
 187
 188     return static_cast<uintptr_t>(Value & ~7ULL);
 189   }
 190
 191   explicit VTableComponent(uint64_t Value)
 192     : Value(Value) { }
 193
 194   /// The kind is stored in the lower 3 bits of the value. For offsets, we
 195   /// make use of the facts that classes can't be larger than 2^55 bytes,
 196   /// so we store the offset in the lower part of the 61 bits that remain.
 197   /// (The reason that we're not simply using a PointerIntPair here is that we
 198   /// need the offsets to be 64-bit, even when on a 32-bit machine).
 199   int64_t Value;
 200 };
 201
 202 class VTableLayout {
 203 public:
 204   typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
 205
 206   typedef const VTableComponent *vtable_component_iterator;
 207   typedef const VTableThunkTy *vtable_thunk_iterator;
 208
 209   typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
 210 private:
 211   uint64_t NumVTableComponents;
 212   std::unique_ptr<VTableComponent[]> VTableComponents;
 213
 214   /// \brief Contains thunks needed by vtables, sorted by indices.
 215   uint64_t NumVTableThunks;
 216   std::unique_ptr<VTableThunkTy[]> VTableThunks;
 217
 218   /// \brief Address points for all vtables.
 219   AddressPointsMapTy AddressPoints;
 220
 221   bool IsMicrosoftABI;
 222
 223 public:
 224   VTableLayout(uint64_t NumVTableComponents,
 225                const VTableComponent *VTableComponents,
 226                uint64_t NumVTableThunks,
 227                const VTableThunkTy *VTableThunks,
 228                const AddressPointsMapTy &AddressPoints,
 229                bool IsMicrosoftABI);
 230   ~VTableLayout();
 231
 232   uint64_t getNumVTableComponents() const {
 233     return NumVTableComponents;
 234   }
 235
 236   vtable_component_iterator vtable_component_begin() const {
 237     return VTableComponents.get();
 238   }
 239
 240   vtable_component_iterator vtable_component_end() const {
 241     return VTableComponents.get() + NumVTableComponents;
 242   }
 243
 244   uint64_t getNumVTableThunks() const { return NumVTableThunks; }
 245
 246   vtable_thunk_iterator vtable_thunk_begin() const {
 247     return VTableThunks.get();
 248   }
 249
 250   vtable_thunk_iterator vtable_thunk_end() const {
 251     return VTableThunks.get() + NumVTableThunks;
 252   }
 253
 254   uint64_t getAddressPoint(BaseSubobject Base) const {
 255     assert(AddressPoints.count(Base) &&
 256            "Did not find address point!");
 257
 258     uint64_t AddressPoint = AddressPoints.lookup(Base);
 259     assert(AddressPoint != 0 || IsMicrosoftABI);
 260     (void)IsMicrosoftABI;
 261
 262     return AddressPoint;
 263   }
 264
 265   const AddressPointsMapTy &getAddressPoints() const {
 266     return AddressPoints;
 267   }
 268 };
 269
 270 class VTableContextBase {
 271 public:
 272   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 273
 274   bool isMicrosoft() const { return IsMicrosoftABI; }
 275
 276   virtual ~VTableContextBase() {}
 277
 278 protected:
 279   typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
 280
 281   /// \brief Contains all thunks that a given method decl will need.
 282   ThunksMapTy Thunks;
 283
 284   /// Compute and store all vtable related information (vtable layout, vbase
 285   /// offset offsets, thunks etc) for the given record decl.
 286   virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0;
 287
 288   VTableContextBase(bool MS) : IsMicrosoftABI(MS) {}
 289
 290 public:
 291   virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) {
 292     const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl());
 293     computeVTableRelatedInformation(MD->getParent());
 294
 295     // This assumes that all the destructors present in the vtable
 296     // use exactly the same set of thunks.
 297     ThunksMapTy::const_iterator I = Thunks.find(MD);
 298     if (I == Thunks.end()) {
 299       // We did not find a thunk for this method.
 300       return nullptr;
 301     }
 302
 303     return &I->second;
 304   }
 305
 306   bool IsMicrosoftABI;
 307 };
 308
 309 class ItaniumVTableContext : public VTableContextBase {
 310 private:
 311
 312   /// \brief Contains the index (relative to the vtable address point)
 313   /// where the function pointer for a virtual function is stored.
 314   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
 315   MethodVTableIndicesTy MethodVTableIndices;
 316
 317   typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *>
 318     VTableLayoutMapTy;
 319   VTableLayoutMapTy VTableLayouts;
 320
 321   typedef std::pair<const CXXRecordDecl *,
 322                     const CXXRecordDecl *> ClassPairTy;
 323
 324   /// \brief vtable offsets for offsets of virtual bases of a class.
 325   ///
 326   /// Contains the vtable offset (relative to the address point) in chars
 327   /// where the offsets for virtual bases of a class are stored.
 328   typedef llvm::DenseMap<ClassPairTy, CharUnits>
 329     VirtualBaseClassOffsetOffsetsMapTy;
 330   VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets;
 331
 332   void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
 333
 334 public:
 335   ItaniumVTableContext(ASTContext &Context);
 336   ~ItaniumVTableContext();
 337
 338   const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) {
 339     computeVTableRelatedInformation(RD);
 340     assert(VTableLayouts.count(RD) && "No layout for this record decl!");
 341
 342     return *VTableLayouts[RD];
 343   }
 344
 345   VTableLayout *
 346   createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass,
 347                                  CharUnits MostDerivedClassOffset,
 348                                  bool MostDerivedClassIsVirtual,
 349                                  const CXXRecordDecl *LayoutClass);
 350
 351   /// \brief Locate a virtual function in the vtable.
 352   ///
 353   /// Return the index (relative to the vtable address point) where the
 354   /// function pointer for the given virtual function is stored.
 355   uint64_t getMethodVTableIndex(GlobalDecl GD);
 356
 357   /// Return the offset in chars (relative to the vtable address point) where
 358   /// the offset of the virtual base that contains the given base is stored,
 359   /// otherwise, if no virtual base contains the given class, return 0.
 360   ///
 361   /// Base must be a virtual base class or an unambiguous base.
 362   CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
 363                                        const CXXRecordDecl *VBase);
 364
 365   static bool classof(const VTableContextBase *VT) {
 366     return !VT->isMicrosoft();
 367   }
 368 };
 369
 370 /// Holds information about the inheritance path to a virtual base or function
 371 /// table pointer.  A record may contain as many vfptrs or vbptrs as there are
 372 /// base subobjects.
 373 struct VPtrInfo {
 374   typedef SmallVector<const CXXRecordDecl *, 1> BasePath;
 375
 376   VPtrInfo(const CXXRecordDecl *RD)
 377       : ReusingBase(RD), BaseWithVPtr(RD), NextBaseToMangle(RD) {}
 378
 379   // Copy constructor.
 380   // FIXME: Uncomment when we've moved to C++11.
 381   // VPtrInfo(const VPtrInfo &) = default;
 382
 383   /// The vtable will hold all of the virtual bases or virtual methods of
 384   /// ReusingBase.  This may or may not be the same class as VPtrSubobject.Base.
 385   /// A derived class will reuse the vptr of the first non-virtual base
 386   /// subobject that has one.
 387   const CXXRecordDecl *ReusingBase;
 388
 389   /// BaseWithVPtr is at this offset from its containing complete object or
 390   /// virtual base.
 391   CharUnits NonVirtualOffset;
 392
 393   /// The vptr is stored inside this subobject.
 394   const CXXRecordDecl *BaseWithVPtr;
 395
 396   /// The bases from the inheritance path that got used to mangle the vbtable
 397   /// name.  This is not really a full path like a CXXBasePath.  It holds the
 398   /// subset of records that need to be mangled into the vbtable symbol name in
 399   /// order to get a unique name.
 400   BasePath MangledPath;
 401
 402   /// The next base to push onto the mangled path if this path is ambiguous in a
 403   /// derived class.  If it's null, then it's already been pushed onto the path.
 404   const CXXRecordDecl *NextBaseToMangle;
 405
 406   /// The set of possibly indirect vbases that contain this vbtable.  When a
 407   /// derived class indirectly inherits from the same vbase twice, we only keep
 408   /// vtables and their paths from the first instance.
 409   BasePath ContainingVBases;
 410
 411   /// This holds the base classes path from the complete type to the first base
 412   /// with the given vfptr offset, in the base-to-derived order.  Only used for
 413   /// vftables.
 414   BasePath PathToBaseWithVPtr;
 415
 416   /// Static offset from the top of the most derived class to this vfptr,
 417   /// including any virtual base offset.  Only used for vftables.
 418   CharUnits FullOffsetInMDC;
 419
 420   /// The vptr is stored inside the non-virtual component of this virtual base.
 421   const CXXRecordDecl *getVBaseWithVPtr() const {
 422     return ContainingVBases.empty() ? nullptr : ContainingVBases.front();
 423   }
 424 };
 425
 426 typedef SmallVector<VPtrInfo *, 2> VPtrInfoVector;
 427
 428 /// All virtual base related information about a given record decl.  Includes
 429 /// information on all virtual base tables and the path components that are used
 430 /// to mangle them.
 431 struct VirtualBaseInfo {
 432   ~VirtualBaseInfo() { llvm::DeleteContainerPointers(VBPtrPaths); }
 433
 434   /// A map from virtual base to vbtable index for doing a conversion from the
 435   /// the derived class to the a base.
 436   llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices;
 437
 438   /// Information on all virtual base tables used when this record is the most
 439   /// derived class.
 440   VPtrInfoVector VBPtrPaths;
 441 };
 442
 443 class MicrosoftVTableContext : public VTableContextBase {
 444 public:
 445   struct MethodVFTableLocation {
 446     /// If nonzero, holds the vbtable index of the virtual base with the vfptr.
 447     uint64_t VBTableIndex;
 448
 449     /// If nonnull, holds the last vbase which contains the vfptr that the
 450     /// method definition is adjusted to.
 451     const CXXRecordDecl *VBase;
 452
 453     /// This is the offset of the vfptr from the start of the last vbase, or the
 454     /// complete type if there are no virtual bases.
 455     CharUnits VFPtrOffset;
 456
 457     /// Method's index in the vftable.
 458     uint64_t Index;
 459
 460     MethodVFTableLocation()
 461         : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()),
 462           Index(0) {}
 463
 464     MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase,
 465                           CharUnits VFPtrOffset, uint64_t Index)
 466         : VBTableIndex(VBTableIndex), VBase(VBase),
 467           VFPtrOffset(VFPtrOffset), Index(Index) {}
 468
 469     bool operator<(const MethodVFTableLocation &other) const {
 470       if (VBTableIndex != other.VBTableIndex) {
 471         assert(VBase != other.VBase);
 472         return VBTableIndex < other.VBTableIndex;
 473       }
 474       return std::tie(VFPtrOffset, Index) <
 475              std::tie(other.VFPtrOffset, other.Index);
 476     }
 477   };
 478
 479 private:
 480   ASTContext &Context;
 481
 482   typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
 483     MethodVFTableLocationsTy;
 484   MethodVFTableLocationsTy MethodVFTableLocations;
 485
 486   typedef llvm::DenseMap<const CXXRecordDecl *, VPtrInfoVector *>
 487     VFPtrLocationsMapTy;
 488   VFPtrLocationsMapTy VFPtrLocations;
 489
 490   typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy;
 491   typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy;
 492   VFTableLayoutMapTy VFTableLayouts;
 493
 494   llvm::DenseMap<const CXXRecordDecl *, VirtualBaseInfo *> VBaseInfo;
 495
 496   void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result);
 497
 498   void computeVTableRelatedInformation(const CXXRecordDecl *RD) override;
 499
 500   void dumpMethodLocations(const CXXRecordDecl *RD,
 501                            const MethodVFTableLocationsTy &NewMethods,
 502                            raw_ostream &);
 503
 504   const VirtualBaseInfo *
 505   computeVBTableRelatedInformation(const CXXRecordDecl *RD);
 506
 507   void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD,
 508                           VPtrInfoVector &Paths);
 509
 510 public:
 511   MicrosoftVTableContext(ASTContext &Context)
 512       : VTableContextBase(/*MS=*/true), Context(Context) {}
 513
 514   ~MicrosoftVTableContext();
 515
 516   const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD);
 517
 518   const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD,
 519                                        CharUnits VFPtrOffset);
 520
 521   const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD);
 522
 523   const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override {
 524     // Complete destructors don't have a slot in a vftable, so no thunks needed.
 525     if (isa<CXXDestructorDecl>(GD.getDecl()) &&
 526         GD.getDtorType() == Dtor_Complete)
 527       return nullptr;
 528     return VTableContextBase::getThunkInfo(GD);
 529   }
 530
 531   /// \brief Returns the index of VBase in the vbtable of Derived.
 532   /// VBase must be a morally virtual base of Derived.
 533   /// The vbtable is an array of i32 offsets.  The first entry is a self entry,
 534   /// and the rest are offsets from the vbptr to virtual bases.
 535   unsigned getVBTableIndex(const CXXRecordDecl *Derived,
 536                            const CXXRecordDecl *VBase);
 537
 538   const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD);
 539
 540   static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); }
 541 };
 542
 543 } // namespace clang
 544
 545 #endif