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