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