VTableBuilder.h revision 649c7316aa29181df7270732722fe5d07ab3c7ad
15d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)//===--- VTableBuilder.h - C++ vtable layout builder --------------*- C++ -*-=// 2eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// 3eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// The LLVM Compiler Infrastructure 4eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// 55d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 6eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// License. See LICENSE.TXT for details. 7eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// 8eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch//===----------------------------------------------------------------------===// 9eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// 10eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// This contains code dealing with generation of the layout of virtual tables. 115d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)// 12eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch//===----------------------------------------------------------------------===// 13eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 145f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#ifndef LLVM_CLANG_AST_VTABLEBUILDER_H 155f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles)#define LLVM_CLANG_AST_VTABLEBUILDER_H 163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 175d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles)#include "clang/AST/BaseSubobject.h" 18eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "clang/AST/CXXInheritance.h" 19eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "clang/AST/GlobalDecl.h" 20eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "clang/AST/RecordLayout.h" 21eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "clang/Basic/ABI.h" 22eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "llvm/ADT/SetVector.h" 23eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include <utility> 24eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 25eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochnamespace clang { 26eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch class CXXRecordDecl; 27eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 2858537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)/// VTableComponent - Represents a single component in a vtable. 2958537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles)class VTableComponent { 30eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochpublic: 31eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch enum Kind { 32eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_VCallOffset, 33eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_VBaseOffset, 34eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_OffsetToTop, 35eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_RTTI, 3658537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) CK_FunctionPointer, 3758537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 38eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch /// CK_CompleteDtorPointer - A pointer to the complete destructor. 39eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_CompleteDtorPointer, 40eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 41eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch /// CK_DeletingDtorPointer - A pointer to the deleting destructor. 42eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_DeletingDtorPointer, 43eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 44eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch /// CK_UnusedFunctionPointer - In some cases, a vtable function pointer 45eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch /// will end up never being called. Such vtable function pointers are 46eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch /// represented as a CK_UnusedFunctionPointer. 47eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CK_UnusedFunctionPointer 48eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch }; 49eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 50eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch VTableComponent() { } 5158537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 52eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch static VTableComponent MakeVCallOffset(CharUnits Offset) { 53eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return VTableComponent(CK_VCallOffset, Offset); 54eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch } 5558537e28ecd584eab876aee8be7156509866d23aTorne (Richard Coles) 56eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch static VTableComponent MakeVBaseOffset(CharUnits Offset) { 57eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return VTableComponent(CK_VBaseOffset, Offset); 58eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch } 59eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 60eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch static VTableComponent MakeOffsetToTop(CharUnits Offset) { 61eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return VTableComponent(CK_OffsetToTop, Offset); 62eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch } 63eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 64eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch static VTableComponent MakeRTTI(const CXXRecordDecl *RD) { 65eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return VTableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD)); 663551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 673551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 683551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) static VTableComponent MakeFunction(const CXXMethodDecl *MD) { 693551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assert(!isa<CXXDestructorDecl>(MD) && 703551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) "Don't use MakeFunction with destructors!"); 713551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 723551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return VTableComponent(CK_FunctionPointer, 733551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) reinterpret_cast<uintptr_t>(MD)); 743551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 753551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 763551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) static VTableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) { 773551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return VTableComponent(CK_CompleteDtorPointer, 785d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) reinterpret_cast<uintptr_t>(DD)); 793551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 803551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 813551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) static VTableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) { 823551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return VTableComponent(CK_DeletingDtorPointer, 833551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) reinterpret_cast<uintptr_t>(DD)); 843551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 853551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 863551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) static VTableComponent MakeUnusedFunction(const CXXMethodDecl *MD) { 873551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assert(!isa<CXXDestructorDecl>(MD) && 883551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) "Don't use MakeUnusedFunction with destructors!"); 893551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return VTableComponent(CK_UnusedFunctionPointer, 903551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) reinterpret_cast<uintptr_t>(MD)); 913551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 923551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 933551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) static VTableComponent getFromOpaqueInteger(uint64_t I) { 943551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return VTableComponent(I); 953551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 963551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 973551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) /// getKind - Get the kind of this vtable component. 983551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) Kind getKind() const { 993551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return (Kind)(Value & 0x7); 1003551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 1013551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1023551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) CharUnits getVCallOffset() const { 1035d1f7b1de12d16ceb2c938c56701a3e8bfa558f7Torne (Richard Coles) assert(getKind() == CK_VCallOffset && "Invalid component kind!"); 1043551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1053551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return getOffset(); 1063551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 1073551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1083551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) CharUnits getVBaseOffset() const { 1093551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assert(getKind() == CK_VBaseOffset && "Invalid component kind!"); 1103551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1113551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return getOffset(); 1123551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 1133551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1143551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) CharUnits getOffsetToTop() const { 1153551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assert(getKind() == CK_OffsetToTop && "Invalid component kind!"); 1163551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1173551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) return getOffset(); 1183551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) } 1193551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1203551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) const CXXRecordDecl *getRTTIDecl() const { 1213551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) assert(getKind() == CK_RTTI && "Invalid component kind!"); 1223551c9c881056c480085172ff9840cab31610854Torne (Richard Coles) 1235f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) return reinterpret_cast<CXXRecordDecl *>(getPointer()); 1245f1c94371a64b3196d4be9466099bb892df9b88eTorne (Richard Coles) } 125 126 const CXXMethodDecl *getFunctionDecl() const { 127 assert(getKind() == CK_FunctionPointer); 128 129 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 130 } 131 132 const CXXDestructorDecl *getDestructorDecl() const { 133 assert((getKind() == CK_CompleteDtorPointer || 134 getKind() == CK_DeletingDtorPointer) && "Invalid component kind!"); 135 136 return reinterpret_cast<CXXDestructorDecl *>(getPointer()); 137 } 138 139 const CXXMethodDecl *getUnusedFunctionDecl() const { 140 assert(getKind() == CK_UnusedFunctionPointer); 141 142 return reinterpret_cast<CXXMethodDecl *>(getPointer()); 143 } 144 145private: 146 VTableComponent(Kind ComponentKind, CharUnits Offset) { 147 assert((ComponentKind == CK_VCallOffset || 148 ComponentKind == CK_VBaseOffset || 149 ComponentKind == CK_OffsetToTop) && "Invalid component kind!"); 150 assert(Offset.getQuantity() < (1LL << 56) && "Offset is too big!"); 151 assert(Offset.getQuantity() >= -(1LL << 56) && "Offset is too small!"); 152 153 Value = (uint64_t(Offset.getQuantity()) << 3) | ComponentKind; 154 } 155 156 VTableComponent(Kind ComponentKind, uintptr_t Ptr) { 157 assert((ComponentKind == CK_RTTI || 158 ComponentKind == CK_FunctionPointer || 159 ComponentKind == CK_CompleteDtorPointer || 160 ComponentKind == CK_DeletingDtorPointer || 161 ComponentKind == CK_UnusedFunctionPointer) && 162 "Invalid component kind!"); 163 164 assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!"); 165 166 Value = Ptr | ComponentKind; 167 } 168 169 CharUnits getOffset() const { 170 assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset || 171 getKind() == CK_OffsetToTop) && "Invalid component kind!"); 172 173 return CharUnits::fromQuantity(Value >> 3); 174 } 175 176 uintptr_t getPointer() const { 177 assert((getKind() == CK_RTTI || 178 getKind() == CK_FunctionPointer || 179 getKind() == CK_CompleteDtorPointer || 180 getKind() == CK_DeletingDtorPointer || 181 getKind() == CK_UnusedFunctionPointer) && 182 "Invalid component kind!"); 183 184 return static_cast<uintptr_t>(Value & ~7ULL); 185 } 186 187 explicit VTableComponent(uint64_t Value) 188 : Value(Value) { } 189 190 /// The kind is stored in the lower 3 bits of the value. For offsets, we 191 /// make use of the facts that classes can't be larger than 2^55 bytes, 192 /// so we store the offset in the lower part of the 61 bytes that remain. 193 /// (The reason that we're not simply using a PointerIntPair here is that we 194 /// need the offsets to be 64-bit, even when on a 32-bit machine). 195 int64_t Value; 196}; 197 198class VTableLayout { 199public: 200 typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy; 201 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 202 203 typedef const VTableComponent *vtable_component_iterator; 204 typedef const VTableThunkTy *vtable_thunk_iterator; 205 206 typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy; 207private: 208 uint64_t NumVTableComponents; 209 llvm::OwningArrayPtr<VTableComponent> VTableComponents; 210 211 /// VTableThunks - Contains thunks needed by vtables. 212 uint64_t NumVTableThunks; 213 llvm::OwningArrayPtr<VTableThunkTy> VTableThunks; 214 215 /// Address points - Address points for all vtables. 216 AddressPointsMapTy AddressPoints; 217 218 bool IsMicrosoftABI; 219 220public: 221 VTableLayout(uint64_t NumVTableComponents, 222 const VTableComponent *VTableComponents, 223 uint64_t NumVTableThunks, 224 const VTableThunkTy *VTableThunks, 225 const AddressPointsMapTy &AddressPoints, 226 bool IsMicrosoftABI); 227 ~VTableLayout(); 228 229 uint64_t getNumVTableComponents() const { 230 return NumVTableComponents; 231 } 232 233 vtable_component_iterator vtable_component_begin() const { 234 return VTableComponents.get(); 235 } 236 237 vtable_component_iterator vtable_component_end() const { 238 return VTableComponents.get()+NumVTableComponents; 239 } 240 241 uint64_t getNumVTableThunks() const { 242 return NumVTableThunks; 243 } 244 245 vtable_thunk_iterator vtable_thunk_begin() const { 246 return VTableThunks.get(); 247 } 248 249 vtable_thunk_iterator vtable_thunk_end() const { 250 return VTableThunks.get()+NumVTableThunks; 251 } 252 253 uint64_t getAddressPoint(BaseSubobject Base) const { 254 assert(AddressPoints.count(Base) && 255 "Did not find address point!"); 256 257 uint64_t AddressPoint = AddressPoints.lookup(Base); 258 assert(AddressPoint != 0 || IsMicrosoftABI); 259 260 return AddressPoint; 261 } 262 263 const AddressPointsMapTy &getAddressPoints() const { 264 return AddressPoints; 265 } 266}; 267 268class VTableContext { 269 ASTContext &Context; 270 271public: 272 typedef SmallVector<std::pair<uint64_t, ThunkInfo>, 1> 273 VTableThunksTy; 274 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 275 276private: 277 bool IsMicrosoftABI; 278 279 /// MethodVTableIndices - Contains the index (relative to the vtable address 280 /// point) where the function pointer for a virtual function is stored. 281 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy; 282 MethodVTableIndicesTy MethodVTableIndices; 283 284 typedef llvm::DenseMap<const CXXRecordDecl *, const VTableLayout *> 285 VTableLayoutMapTy; 286 VTableLayoutMapTy VTableLayouts; 287 288 /// NumVirtualFunctionPointers - Contains the number of virtual function 289 /// pointers in the vtable for a given record decl. 290 llvm::DenseMap<const CXXRecordDecl *, uint64_t> NumVirtualFunctionPointers; 291 292 typedef std::pair<const CXXRecordDecl *, 293 const CXXRecordDecl *> ClassPairTy; 294 295 /// VirtualBaseClassOffsetOffsets - Contains the vtable offset (relative to 296 /// the address point) in chars where the offsets for virtual bases of a class 297 /// are stored. 298 typedef llvm::DenseMap<ClassPairTy, CharUnits> 299 VirtualBaseClassOffsetOffsetsMapTy; 300 VirtualBaseClassOffsetOffsetsMapTy VirtualBaseClassOffsetOffsets; 301 302 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 303 304 /// Thunks - Contains all thunks that a given method decl will need. 305 ThunksMapTy Thunks; 306 307 void ComputeMethodVTableIndices(const CXXRecordDecl *RD); 308 309 /// ComputeVTableRelatedInformation - Compute and store all vtable related 310 /// information (vtable layout, vbase offset offsets, thunks etc) for the 311 /// given record decl. 312 void ComputeVTableRelatedInformation(const CXXRecordDecl *RD); 313 314 /// ErrorUnsupported - Print out an error that the v-table layout code 315 /// doesn't support the particular C++ feature yet. 316 void ErrorUnsupported(StringRef Feature, SourceLocation Location); 317 318public: 319 VTableContext(ASTContext &Context); 320 ~VTableContext(); 321 322 bool isMicrosoftABI() const { 323 // FIXME: Currently, this method is only used in the VTableContext and 324 // VTableBuilder code which is ABI-specific. Probably we can remove it 325 // when we add a layer of abstraction for vtable generation. 326 return IsMicrosoftABI; 327 } 328 329 const VTableLayout &getVTableLayout(const CXXRecordDecl *RD) { 330 ComputeVTableRelatedInformation(RD); 331 assert(VTableLayouts.count(RD) && "No layout for this record decl!"); 332 333 return *VTableLayouts[RD]; 334 } 335 336 VTableLayout * 337 createConstructionVTableLayout(const CXXRecordDecl *MostDerivedClass, 338 CharUnits MostDerivedClassOffset, 339 bool MostDerivedClassIsVirtual, 340 const CXXRecordDecl *LayoutClass); 341 342 const ThunkInfoVectorTy *getThunkInfo(const CXXMethodDecl *MD) { 343 ComputeVTableRelatedInformation(MD->getParent()); 344 345 ThunksMapTy::const_iterator I = Thunks.find(MD); 346 if (I == Thunks.end()) { 347 // We did not find a thunk for this method. 348 return 0; 349 } 350 351 return &I->second; 352 } 353 354 /// getNumVirtualFunctionPointers - Return the number of virtual function 355 /// pointers in the vtable for a given record decl. 356 uint64_t getNumVirtualFunctionPointers(const CXXRecordDecl *RD); 357 358 /// getMethodVTableIndex - Return the index (relative to the vtable address 359 /// point) where the function pointer for the given virtual function is 360 /// stored. 361 uint64_t getMethodVTableIndex(GlobalDecl GD); 362 363 /// getVirtualBaseOffsetOffset - Return the offset in chars (relative to the 364 /// vtable address point) where the offset of the virtual base that contains 365 /// the given base is stored, otherwise, if no virtual base contains the given 366 /// class, return 0. Base must be a virtual base class or an unambigious 367 /// base. 368 CharUnits getVirtualBaseOffsetOffset(const CXXRecordDecl *RD, 369 const CXXRecordDecl *VBase); 370}; 371 372} 373 374#endif 375