contrib/llvm-project/clang/include/clang/AST/VTableBuilder.h

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