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