clang API Documentation
00001 //===--- VTableBuilder.h - C++ vtable layout builder --------------*- C++ -*-=// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This contains code dealing with generation of the layout of virtual tables. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_CLANG_AST_VTABLEBUILDER_H 00015 #define LLVM_CLANG_AST_VTABLEBUILDER_H 00016 00017 #include "clang/AST/BaseSubobject.h" 00018 #include "clang/AST/CXXInheritance.h" 00019 #include "clang/AST/GlobalDecl.h" 00020 #include "clang/AST/RecordLayout.h" 00021 #include "clang/Basic/ABI.h" 00022 #include "llvm/ADT/DenseMap.h" 00023 #include "llvm/ADT/SetVector.h" 00024 #include <memory> 00025 #include <utility> 00026 00027 namespace clang { 00028 class CXXRecordDecl; 00029 00030 /// \brief Represents a single component in a vtable. 00031 class VTableComponent { 00032 public: 00033 enum Kind { 00034 CK_VCallOffset, 00035 CK_VBaseOffset, 00036 CK_OffsetToTop, 00037 CK_RTTI, 00038 CK_FunctionPointer, 00039 00040 /// \brief A pointer to the complete destructor. 00041 CK_CompleteDtorPointer, 00042 00043 /// \brief A pointer to the deleting destructor. 00044 CK_DeletingDtorPointer, 00045 00046 /// \brief An entry that is never used. 00047 /// 00048 /// In some cases, a vtable function pointer will end up never being 00049 /// called. Such vtable function pointers are represented as a 00050 /// CK_UnusedFunctionPointer. 00051 CK_UnusedFunctionPointer 00052 }; 00053 00054 VTableComponent() { } 00055 00056 static VTableComponent MakeVCallOffset(CharUnits Offset) { 00057 return VTableComponent(CK_VCallOffset, Offset); 00058 } 00059 00060 static VTableComponent MakeVBaseOffset(CharUnits Offset) { 00061 return VTableComponent(CK_VBaseOffset, Offset); 00062 } 00063 00064 static VTableComponent MakeOffsetToTop(CharUnits Offset) { 00065 return VTableComponent(CK_OffsetToTop, Offset); 00066 } 00067 00068 static VTableComponent MakeRTTI(const CXXRecordDecl *RD) { 00069 return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD)); 00070 } 00071 00072 static VTableComponent MakeFunction(const CXXMethodDecl *MD) { 00073 assert(!isa<CXXDestructorDecl>(MD) && 00074 "Don't use MakeFunction with destructors!"); 00075 00076 return VTableComponent(CK_FunctionPointer, 00077 reinterpret_cast<uintptr_t>(MD)); 00078 } 00079 00080 static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) { 00081 return VTableComponent(CK_CompleteDtorPointer, 00082 reinterpret_cast<uintptr_t>(DD)); 00083 } 00084 00085 static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) { 00086 return VTableComponent(CK_DeletingDtorPointer, 00087 reinterpret_cast<uintptr_t>(DD)); 00088 } 00089 00090 static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) { 00091 assert(!isa<CXXDestructorDecl>(MD) && 00092 "Don't use MakeUnusedFunction with destructors!"); 00093 return VTableComponent(CK_UnusedFunctionPointer, 00094 reinterpret_cast<uintptr_t>(MD)); 00095 } 00096 00097 static VTableComponent getFromOpaqueInteger(uint64_t I) { 00098 return VTableComponent(I); 00099 } 00100 00101 /// \brief Get the kind of this vtable component. 00102 Kind getKind() const { 00103 return (Kind)(Value & 0x7); 00104 } 00105 00106 CharUnits getVCallOffset() const { 00107 assert(getKind() == CK_VCallOffset && "Invalid component kind!"); 00108 00109 return getOffset(); 00110 } 00111 00112 CharUnits getVBaseOffset() const { 00113 assert(getKind() == CK_VBaseOffset && "Invalid component kind!"); 00114 00115 return getOffset(); 00116 } 00117 00118 CharUnits getOffsetToTop() const { 00119 assert(getKind() == CK_OffsetToTop && "Invalid component kind!"); 00120 00121 return getOffset(); 00122 } 00123 00124 const CXXRecordDecl *getRTTIDecl() const { 00125 assert(getKind() == CK_RTTI && "Invalid component kind!"); 00126 00127 return reinterpret_cast<CXXRecordDecl *>(getPointer()); 00128 } 00129 00130 const CXXMethodDecl *getFunctionDecl() const { 00131 assert(getKind() == CK_FunctionPointer); 00132 00133 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 00134 } 00135 00136 const CXXDestructorDecl *getDestructorDecl() const { 00137 assert((getKind() == CK_CompleteDtorPointer || 00138 getKind() == CK_DeletingDtorPointer) && "Invalid component kind!"); 00139 00140 return reinterpret_cast<CXXDestructorDecl *>(getPointer()); 00141 } 00142 00143 const CXXMethodDecl *getUnusedFunctionDecl() const { 00144 assert(getKind() == CK_UnusedFunctionPointer); 00145 00146 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 00147 } 00148 00149 private: 00150 VTableComponent(Kind ComponentKind, CharUnits Offset) { 00151 assert((ComponentKind == CK_VCallOffset || 00152 ComponentKind == CK_VBaseOffset || 00153 ComponentKind == CK_OffsetToTop) && "Invalid component kind!"); 00154 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!"); 00155 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!"); 00156 00157 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind; 00158 } 00159 00160 VTableComponent(Kind ComponentKind, uintptr_t Ptr) { 00161 assert((ComponentKind == CK_RTTI || 00162 ComponentKind == CK_FunctionPointer || 00163 ComponentKind == CK_CompleteDtorPointer || 00164 ComponentKind == CK_DeletingDtorPointer || 00165 ComponentKind == CK_UnusedFunctionPointer) && 00166 "Invalid component kind!"); 00167 00168 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!"); 00169 00170 Value = Ptr | ComponentKind; 00171 } 00172 00173 CharUnits getOffset() const { 00174 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset || 00175 getKind() == CK_OffsetToTop) && "Invalid component kind!"); 00176 00177 return CharUnits::fromQuantity(Value >> 3); 00178 } 00179 00180 uintptr_t getPointer() const { 00181 assert((getKind() == CK_RTTI || 00182 getKind() == CK_FunctionPointer || 00183 getKind() == CK_CompleteDtorPointer || 00184 getKind() == CK_DeletingDtorPointer || 00185 getKind() == CK_UnusedFunctionPointer) && 00186 "Invalid component kind!"); 00187 00188 return static_cast<uintptr_t>(Value & ~7ULL); 00189 } 00190 00191 explicit VTableComponent(uint64_t Value) 00192 : Value(Value) { } 00193 00194 /// The kind is stored in the lower 3 bits of the value. For offsets, we 00195 /// make use of the facts that classes can't be larger than 2^55 bytes, 00196 /// so we store the offset in the lower part of the 61 bits that remain. 00197 /// (The reason that we're not simply using a PointerIntPair here is that we 00198 /// need the offsets to be 64-bit, even when on a 32-bit machine). 00199 int64_t Value; 00200 }; 00201 00202 class VTableLayout { 00203 public: 00204 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy; 00205 00206 typedef const VTableComponent *vtable_component_iterator; 00207 typedef const VTableThunkTy *vtable_thunk_iterator; 00208 00209 typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy; 00210 private: 00211 uint64_t NumVTableComponents; 00212 std::unique_ptr<VTableComponent[]> VTableComponents; 00213 00214 /// \brief Contains thunks needed by vtables, sorted by indices. 00215 uint64_t NumVTableThunks; 00216 std::unique_ptr<VTableThunkTy[]> VTableThunks; 00217 00218 /// \brief Address points for all vtables. 00219 AddressPointsMapTy AddressPoints; 00220 00221 bool IsMicrosoftABI; 00222 00223 public: 00224 VTableLayout(uint64_t NumVTableComponents, 00225 const VTableComponent *VTableComponents, 00226 uint64_t NumVTableThunks, 00227 const VTableThunkTy *VTableThunks, 00228 const AddressPointsMapTy &AddressPoints, 00229 bool IsMicrosoftABI); 00230 ~VTableLayout(); 00231 00232 uint64_t getNumVTableComponents() const { 00233 return NumVTableComponents; 00234 } 00235 00236 vtable_component_iterator vtable_component_begin() const { 00237 return VTableComponents.get(); 00238 } 00239 00240 vtable_component_iterator vtable_component_end() const { 00241 return VTableComponents.get() + NumVTableComponents; 00242 } 00243 00244 uint64_t getNumVTableThunks() const { return NumVTableThunks; } 00245 00246 vtable_thunk_iterator vtable_thunk_begin() const { 00247 return VTableThunks.get(); 00248 } 00249 00250 vtable_thunk_iterator vtable_thunk_end() const { 00251 return VTableThunks.get() + NumVTableThunks; 00252 } 00253 00254 uint64_t getAddressPoint(BaseSubobject Base) const { 00255 assert(AddressPoints.count(Base) && 00256 "Did not find address point!"); 00257 00258 uint64_t AddressPoint = AddressPoints.lookup(Base); 00259 assert(AddressPoint != 0 || IsMicrosoftABI); 00260 (void)IsMicrosoftABI; 00261 00262 return AddressPoint; 00263 } 00264 00265 const AddressPointsMapTy &getAddressPoints() const { 00266 return AddressPoints; 00267 } 00268 }; 00269 00270 class VTableContextBase { 00271 public: 00272 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 00273 00274 bool isMicrosoft() const { return IsMicrosoftABI; } 00275 00276 virtual ~VTableContextBase() {} 00277 00278 protected: 00279 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 00280 00281 /// \brief Contains all thunks that a given method decl will need. 00282 ThunksMapTy Thunks; 00283 00284 /// Compute and store all vtable related information (vtable layout, vbase 00285 /// offset offsets, thunks etc) for the given record decl. 00286 virtual void computeVTableRelatedInformation(const CXXRecordDecl *RD) = 0; 00287 00288 VTableContextBase(bool MS) : IsMicrosoftABI(MS) {} 00289 00290 public: 00291 virtual const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) { 00292 const CXXMethodDecl *MD = cast<CXXMethodDecl>(GD.getDecl()->getCanonicalDecl()); 00293 computeVTableRelatedInformation(MD->getParent()); 00294 00295 // This assumes that all the destructors present in the vtable 00296 // use exactly the same set of thunks. 00297 ThunksMapTy::const_iterator I = Thunks.find(MD); 00298 if (I == Thunks.end()) { 00299 // We did not find a thunk for this method. 00300 return nullptr; 00301 } 00302 00303 return &I->second; 00304 } 00305 00306 bool IsMicrosoftABI; 00307 }; 00308 00309 class ItaniumVTableContext : public VTableContextBase { 00310 private: 00311 00312 /// \brief Contains the index (relative to the vtable address point) 00313 /// where the function pointer for a virtual function is stored. 00314 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy; 00315 MethodVTableIndicesTy MethodVTableIndices; 00316 00317 typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *> 00318 VTableLayoutMapTy; 00319 VTableLayoutMapTy VTableLayouts; 00320 00321 typedef std::pair<const CXXRecordDecl *, 00322 const CXXRecordDecl *> ClassPairTy; 00323 00324 /// \brief vtable offsets for offsets of virtual bases of a class. 00325 /// 00326 /// Contains the vtable offset (relative to the address point) in chars 00327 /// where the offsets for virtual bases of a class are stored. 00328 typedef llvm::DenseMap<ClassPairTy, CharUnits> 00329 VirtualBaseClassOffsetOffsetsMapTy; 00330 VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets; 00331 00332 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override; 00333 00334 public: 00335 ItaniumVTableContext(ASTContext &Context); 00336 ~ItaniumVTableContext(); 00337 00338 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) { 00339 computeVTableRelatedInformation(RD); 00340 assert(VTableLayouts.count(RD) && "No layout for this record decl!"); 00341 00342 return *VTableLayouts[RD]; 00343 } 00344 00345 VTableLayout * 00346 createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass, 00347 CharUnits MostDerivedClassOffset, 00348 bool MostDerivedClassIsVirtual, 00349 const CXXRecordDecl *LayoutClass); 00350 00351 /// \brief Locate a virtual function in the vtable. 00352 /// 00353 /// Return the index (relative to the vtable address point) where the 00354 /// function pointer for the given virtual function is stored. 00355 uint64_t getMethodVTableIndex(GlobalDecl GD); 00356 00357 /// Return the offset in chars (relative to the vtable address point) where 00358 /// the offset of the virtual base that contains the given base is stored, 00359 /// otherwise, if no virtual base contains the given class, return 0. 00360 /// 00361 /// Base must be a virtual base class or an unambiguous base. 00362 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD, 00363 const CXXRecordDecl *VBase); 00364 00365 static bool classof(const VTableContextBase *VT) { 00366 return !VT->isMicrosoft(); 00367 } 00368 }; 00369 00370 /// Holds information about the inheritance path to a virtual base or function 00371 /// table pointer. A record may contain as many vfptrs or vbptrs as there are 00372 /// base subobjects. 00373 struct VPtrInfo { 00374 typedef SmallVector<const CXXRecordDecl *, 1> BasePath; 00375 00376 VPtrInfo(const CXXRecordDecl *RD) 00377 : ReusingBase(RD), BaseWithVPtr(RD), NextBaseToMangle(RD) {} 00378 00379 // Copy constructor. 00380 // FIXME: Uncomment when we've moved to C++11. 00381 // VPtrInfo(const VPtrInfo &) = default; 00382 00383 /// The vtable will hold all of the virtual bases or virtual methods of 00384 /// ReusingBase. This may or may not be the same class as VPtrSubobject.Base. 00385 /// A derived class will reuse the vptr of the first non-virtual base 00386 /// subobject that has one. 00387 const CXXRecordDecl *ReusingBase; 00388 00389 /// BaseWithVPtr is at this offset from its containing complete object or 00390 /// virtual base. 00391 CharUnits NonVirtualOffset; 00392 00393 /// The vptr is stored inside this subobject. 00394 const CXXRecordDecl *BaseWithVPtr; 00395 00396 /// The bases from the inheritance path that got used to mangle the vbtable 00397 /// name. This is not really a full path like a CXXBasePath. It holds the 00398 /// subset of records that need to be mangled into the vbtable symbol name in 00399 /// order to get a unique name. 00400 BasePath MangledPath; 00401 00402 /// The next base to push onto the mangled path if this path is ambiguous in a 00403 /// derived class. If it's null, then it's already been pushed onto the path. 00404 const CXXRecordDecl *NextBaseToMangle; 00405 00406 /// The set of possibly indirect vbases that contain this vbtable. When a 00407 /// derived class indirectly inherits from the same vbase twice, we only keep 00408 /// vtables and their paths from the first instance. 00409 BasePath ContainingVBases; 00410 00411 /// This holds the base classes path from the complete type to the first base 00412 /// with the given vfptr offset, in the base-to-derived order. Only used for 00413 /// vftables. 00414 BasePath PathToBaseWithVPtr; 00415 00416 /// Static offset from the top of the most derived class to this vfptr, 00417 /// including any virtual base offset. Only used for vftables. 00418 CharUnits FullOffsetInMDC; 00419 00420 /// The vptr is stored inside the non-virtual component of this virtual base. 00421 const CXXRecordDecl *getVBaseWithVPtr() const { 00422 return ContainingVBases.empty() ? nullptr : ContainingVBases.front(); 00423 } 00424 }; 00425 00426 typedef SmallVector<VPtrInfo *, 2> VPtrInfoVector; 00427 00428 /// All virtual base related information about a given record decl. Includes 00429 /// information on all virtual base tables and the path components that are used 00430 /// to mangle them. 00431 struct VirtualBaseInfo { 00432 ~VirtualBaseInfo() { llvm::DeleteContainerPointers(VBPtrPaths); } 00433 00434 /// A map from virtual base to vbtable index for doing a conversion from the 00435 /// the derived class to the a base. 00436 llvm::DenseMap<const CXXRecordDecl *, unsigned> VBTableIndices; 00437 00438 /// Information on all virtual base tables used when this record is the most 00439 /// derived class. 00440 VPtrInfoVector VBPtrPaths; 00441 }; 00442 00443 class MicrosoftVTableContext : public VTableContextBase { 00444 public: 00445 struct MethodVFTableLocation { 00446 /// If nonzero, holds the vbtable index of the virtual base with the vfptr. 00447 uint64_t VBTableIndex; 00448 00449 /// If nonnull, holds the last vbase which contains the vfptr that the 00450 /// method definition is adjusted to. 00451 const CXXRecordDecl *VBase; 00452 00453 /// This is the offset of the vfptr from the start of the last vbase, or the 00454 /// complete type if there are no virtual bases. 00455 CharUnits VFPtrOffset; 00456 00457 /// Method's index in the vftable. 00458 uint64_t Index; 00459 00460 MethodVFTableLocation() 00461 : VBTableIndex(0), VBase(nullptr), VFPtrOffset(CharUnits::Zero()), 00462 Index(0) {} 00463 00464 MethodVFTableLocation(uint64_t VBTableIndex, const CXXRecordDecl *VBase, 00465 CharUnits VFPtrOffset, uint64_t Index) 00466 : VBTableIndex(VBTableIndex), VBase(VBase), 00467 VFPtrOffset(VFPtrOffset), Index(Index) {} 00468 00469 bool operator<(const MethodVFTableLocation &other) const { 00470 if (VBTableIndex != other.VBTableIndex) { 00471 assert(VBase != other.VBase); 00472 return VBTableIndex < other.VBTableIndex; 00473 } 00474 return std::tie(VFPtrOffset, Index) < 00475 std::tie(other.VFPtrOffset, other.Index); 00476 } 00477 }; 00478 00479 private: 00480 ASTContext &Context; 00481 00482 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation> 00483 MethodVFTableLocationsTy; 00484 MethodVFTableLocationsTy MethodVFTableLocations; 00485 00486 typedef llvm::DenseMap<const CXXRecordDecl *, VPtrInfoVector *> 00487 VFPtrLocationsMapTy; 00488 VFPtrLocationsMapTy VFPtrLocations; 00489 00490 typedef std::pair<const CXXRecordDecl *, CharUnits> VFTableIdTy; 00491 typedef llvm::DenseMap<VFTableIdTy, const VTableLayout *> VFTableLayoutMapTy; 00492 VFTableLayoutMapTy VFTableLayouts; 00493 00494 llvm::DenseMap<const CXXRecordDecl *, VirtualBaseInfo *> VBaseInfo; 00495 00496 void enumerateVFPtrs(const CXXRecordDecl *ForClass, VPtrInfoVector &Result); 00497 00498 void computeVTableRelatedInformation(const CXXRecordDecl *RD) override; 00499 00500 void dumpMethodLocations(const CXXRecordDecl *RD, 00501 const MethodVFTableLocationsTy &NewMethods, 00502 raw_ostream &); 00503 00504 const VirtualBaseInfo * 00505 computeVBTableRelatedInformation(const CXXRecordDecl *RD); 00506 00507 void computeVTablePaths(bool ForVBTables, const CXXRecordDecl *RD, 00508 VPtrInfoVector &Paths); 00509 00510 public: 00511 MicrosoftVTableContext(ASTContext &Context) 00512 : VTableContextBase(/*MS=*/true), Context(Context) {} 00513 00514 ~MicrosoftVTableContext(); 00515 00516 const VPtrInfoVector &getVFPtrOffsets(const CXXRecordDecl *RD); 00517 00518 const VTableLayout &getVFTableLayout(const CXXRecordDecl *RD, 00519 CharUnits VFPtrOffset); 00520 00521 const MethodVFTableLocation &getMethodVFTableLocation(GlobalDecl GD); 00522 00523 const ThunkInfoVectorTy *getThunkInfo(GlobalDecl GD) override { 00524 // Complete destructors don't have a slot in a vftable, so no thunks needed. 00525 if (isa<CXXDestructorDecl>(GD.getDecl()) && 00526 GD.getDtorType() == Dtor_Complete) 00527 return nullptr; 00528 return VTableContextBase::getThunkInfo(GD); 00529 } 00530 00531 /// \brief Returns the index of VBase in the vbtable of Derived. 00532 /// VBase must be a morally virtual base of Derived. 00533 /// The vbtable is an array of i32 offsets. The first entry is a self entry, 00534 /// and the rest are offsets from the vbptr to virtual bases. 00535 unsigned getVBTableIndex(const CXXRecordDecl *Derived, 00536 const CXXRecordDecl *VBase); 00537 00538 const VPtrInfoVector &enumerateVBTables(const CXXRecordDecl *RD); 00539 00540 static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); } 00541 }; 00542 00543 } // namespace clang 00544 00545 #endif