clang API Documentation
00001 //===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===// 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 #include "clang/AST/VTableBuilder.h" 00015 #include "clang/AST/ASTContext.h" 00016 #include "clang/AST/CXXInheritance.h" 00017 #include "clang/AST/RecordLayout.h" 00018 #include "clang/Basic/TargetInfo.h" 00019 #include "llvm/ADT/SmallPtrSet.h" 00020 #include "llvm/Support/Format.h" 00021 #include "llvm/Support/raw_ostream.h" 00022 #include <algorithm> 00023 #include <cstdio> 00024 00025 using namespace clang; 00026 00027 #define DUMP_OVERRIDERS 0 00028 00029 namespace { 00030 00031 /// BaseOffset - Represents an offset from a derived class to a direct or 00032 /// indirect base class. 00033 struct BaseOffset { 00034 /// DerivedClass - The derived class. 00035 const CXXRecordDecl *DerivedClass; 00036 00037 /// VirtualBase - If the path from the derived class to the base class 00038 /// involves virtual base classes, this holds the declaration of the last 00039 /// virtual base in this path (i.e. closest to the base class). 00040 const CXXRecordDecl *VirtualBase; 00041 00042 /// NonVirtualOffset - The offset from the derived class to the base class. 00043 /// (Or the offset from the virtual base class to the base class, if the 00044 /// path from the derived class to the base class involves a virtual base 00045 /// class. 00046 CharUnits NonVirtualOffset; 00047 00048 BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr), 00049 NonVirtualOffset(CharUnits::Zero()) { } 00050 BaseOffset(const CXXRecordDecl *DerivedClass, 00051 const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset) 00052 : DerivedClass(DerivedClass), VirtualBase(VirtualBase), 00053 NonVirtualOffset(NonVirtualOffset) { } 00054 00055 bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; } 00056 }; 00057 00058 /// FinalOverriders - Contains the final overrider member functions for all 00059 /// member functions in the base subobjects of a class. 00060 class FinalOverriders { 00061 public: 00062 /// OverriderInfo - Information about a final overrider. 00063 struct OverriderInfo { 00064 /// Method - The method decl of the overrider. 00065 const CXXMethodDecl *Method; 00066 00067 /// VirtualBase - The virtual base class subobject of this overrider. 00068 /// Note that this records the closest derived virtual base class subobject. 00069 const CXXRecordDecl *VirtualBase; 00070 00071 /// Offset - the base offset of the overrider's parent in the layout class. 00072 CharUnits Offset; 00073 00074 OverriderInfo() : Method(nullptr), VirtualBase(nullptr), 00075 Offset(CharUnits::Zero()) { } 00076 }; 00077 00078 private: 00079 /// MostDerivedClass - The most derived class for which the final overriders 00080 /// are stored. 00081 const CXXRecordDecl *MostDerivedClass; 00082 00083 /// MostDerivedClassOffset - If we're building final overriders for a 00084 /// construction vtable, this holds the offset from the layout class to the 00085 /// most derived class. 00086 const CharUnits MostDerivedClassOffset; 00087 00088 /// LayoutClass - The class we're using for layout information. Will be 00089 /// different than the most derived class if the final overriders are for a 00090 /// construction vtable. 00091 const CXXRecordDecl *LayoutClass; 00092 00093 ASTContext &Context; 00094 00095 /// MostDerivedClassLayout - the AST record layout of the most derived class. 00096 const ASTRecordLayout &MostDerivedClassLayout; 00097 00098 /// MethodBaseOffsetPairTy - Uniquely identifies a member function 00099 /// in a base subobject. 00100 typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy; 00101 00102 typedef llvm::DenseMap<MethodBaseOffsetPairTy, 00103 OverriderInfo> OverridersMapTy; 00104 00105 /// OverridersMap - The final overriders for all virtual member functions of 00106 /// all the base subobjects of the most derived class. 00107 OverridersMapTy OverridersMap; 00108 00109 /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented 00110 /// as a record decl and a subobject number) and its offsets in the most 00111 /// derived class as well as the layout class. 00112 typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>, 00113 CharUnits> SubobjectOffsetMapTy; 00114 00115 typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy; 00116 00117 /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the 00118 /// given base. 00119 void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual, 00120 CharUnits OffsetInLayoutClass, 00121 SubobjectOffsetMapTy &SubobjectOffsets, 00122 SubobjectOffsetMapTy &SubobjectLayoutClassOffsets, 00123 SubobjectCountMapTy &SubobjectCounts); 00124 00125 typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy; 00126 00127 /// dump - dump the final overriders for a base subobject, and all its direct 00128 /// and indirect base subobjects. 00129 void dump(raw_ostream &Out, BaseSubobject Base, 00130 VisitedVirtualBasesSetTy& VisitedVirtualBases); 00131 00132 public: 00133 FinalOverriders(const CXXRecordDecl *MostDerivedClass, 00134 CharUnits MostDerivedClassOffset, 00135 const CXXRecordDecl *LayoutClass); 00136 00137 /// getOverrider - Get the final overrider for the given method declaration in 00138 /// the subobject with the given base offset. 00139 OverriderInfo getOverrider(const CXXMethodDecl *MD, 00140 CharUnits BaseOffset) const { 00141 assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) && 00142 "Did not find overrider!"); 00143 00144 return OverridersMap.lookup(std::make_pair(MD, BaseOffset)); 00145 } 00146 00147 /// dump - dump the final overriders. 00148 void dump() { 00149 VisitedVirtualBasesSetTy VisitedVirtualBases; 00150 dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()), 00151 VisitedVirtualBases); 00152 } 00153 00154 }; 00155 00156 FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass, 00157 CharUnits MostDerivedClassOffset, 00158 const CXXRecordDecl *LayoutClass) 00159 : MostDerivedClass(MostDerivedClass), 00160 MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass), 00161 Context(MostDerivedClass->getASTContext()), 00162 MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) { 00163 00164 // Compute base offsets. 00165 SubobjectOffsetMapTy SubobjectOffsets; 00166 SubobjectOffsetMapTy SubobjectLayoutClassOffsets; 00167 SubobjectCountMapTy SubobjectCounts; 00168 ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 00169 /*IsVirtual=*/false, 00170 MostDerivedClassOffset, 00171 SubobjectOffsets, SubobjectLayoutClassOffsets, 00172 SubobjectCounts); 00173 00174 // Get the final overriders. 00175 CXXFinalOverriderMap FinalOverriders; 00176 MostDerivedClass->getFinalOverriders(FinalOverriders); 00177 00178 for (CXXFinalOverriderMap::const_iterator I = FinalOverriders.begin(), 00179 E = FinalOverriders.end(); I != E; ++I) { 00180 const CXXMethodDecl *MD = I->first; 00181 const OverridingMethods& Methods = I->second; 00182 00183 for (OverridingMethods::const_iterator I = Methods.begin(), 00184 E = Methods.end(); I != E; ++I) { 00185 unsigned SubobjectNumber = I->first; 00186 assert(SubobjectOffsets.count(std::make_pair(MD->getParent(), 00187 SubobjectNumber)) && 00188 "Did not find subobject offset!"); 00189 00190 CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(), 00191 SubobjectNumber)]; 00192 00193 assert(I->second.size() == 1 && "Final overrider is not unique!"); 00194 const UniqueVirtualMethod &Method = I->second.front(); 00195 00196 const CXXRecordDecl *OverriderRD = Method.Method->getParent(); 00197 assert(SubobjectLayoutClassOffsets.count( 00198 std::make_pair(OverriderRD, Method.Subobject)) 00199 && "Did not find subobject offset!"); 00200 CharUnits OverriderOffset = 00201 SubobjectLayoutClassOffsets[std::make_pair(OverriderRD, 00202 Method.Subobject)]; 00203 00204 OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)]; 00205 assert(!Overrider.Method && "Overrider should not exist yet!"); 00206 00207 Overrider.Offset = OverriderOffset; 00208 Overrider.Method = Method.Method; 00209 Overrider.VirtualBase = Method.InVirtualSubobject; 00210 } 00211 } 00212 00213 #if DUMP_OVERRIDERS 00214 // And dump them (for now). 00215 dump(); 00216 #endif 00217 } 00218 00219 static BaseOffset ComputeBaseOffset(ASTContext &Context, 00220 const CXXRecordDecl *DerivedRD, 00221 const CXXBasePath &Path) { 00222 CharUnits NonVirtualOffset = CharUnits::Zero(); 00223 00224 unsigned NonVirtualStart = 0; 00225 const CXXRecordDecl *VirtualBase = nullptr; 00226 00227 // First, look for the virtual base class. 00228 for (int I = Path.size(), E = 0; I != E; --I) { 00229 const CXXBasePathElement &Element = Path[I - 1]; 00230 00231 if (Element.Base->isVirtual()) { 00232 NonVirtualStart = I; 00233 QualType VBaseType = Element.Base->getType(); 00234 VirtualBase = VBaseType->getAsCXXRecordDecl(); 00235 break; 00236 } 00237 } 00238 00239 // Now compute the non-virtual offset. 00240 for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) { 00241 const CXXBasePathElement &Element = Path[I]; 00242 00243 // Check the base class offset. 00244 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class); 00245 00246 const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl(); 00247 00248 NonVirtualOffset += Layout.getBaseClassOffset(Base); 00249 } 00250 00251 // FIXME: This should probably use CharUnits or something. Maybe we should 00252 // even change the base offsets in ASTRecordLayout to be specified in 00253 // CharUnits. 00254 return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset); 00255 00256 } 00257 00258 static BaseOffset ComputeBaseOffset(ASTContext &Context, 00259 const CXXRecordDecl *BaseRD, 00260 const CXXRecordDecl *DerivedRD) { 00261 CXXBasePaths Paths(/*FindAmbiguities=*/false, 00262 /*RecordPaths=*/true, /*DetectVirtual=*/false); 00263 00264 if (!DerivedRD->isDerivedFrom(BaseRD, Paths)) 00265 llvm_unreachable("Class must be derived from the passed in base class!"); 00266 00267 return ComputeBaseOffset(Context, DerivedRD, Paths.front()); 00268 } 00269 00270 static BaseOffset 00271 ComputeReturnAdjustmentBaseOffset(ASTContext &Context, 00272 const CXXMethodDecl *DerivedMD, 00273 const CXXMethodDecl *BaseMD) { 00274 const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>(); 00275 const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>(); 00276 00277 // Canonicalize the return types. 00278 CanQualType CanDerivedReturnType = 00279 Context.getCanonicalType(DerivedFT->getReturnType()); 00280 CanQualType CanBaseReturnType = 00281 Context.getCanonicalType(BaseFT->getReturnType()); 00282 00283 assert(CanDerivedReturnType->getTypeClass() == 00284 CanBaseReturnType->getTypeClass() && 00285 "Types must have same type class!"); 00286 00287 if (CanDerivedReturnType == CanBaseReturnType) { 00288 // No adjustment needed. 00289 return BaseOffset(); 00290 } 00291 00292 if (isa<ReferenceType>(CanDerivedReturnType)) { 00293 CanDerivedReturnType = 00294 CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType(); 00295 CanBaseReturnType = 00296 CanBaseReturnType->getAs<ReferenceType>()->getPointeeType(); 00297 } else if (isa<PointerType>(CanDerivedReturnType)) { 00298 CanDerivedReturnType = 00299 CanDerivedReturnType->getAs<PointerType>()->getPointeeType(); 00300 CanBaseReturnType = 00301 CanBaseReturnType->getAs<PointerType>()->getPointeeType(); 00302 } else { 00303 llvm_unreachable("Unexpected return type!"); 00304 } 00305 00306 // We need to compare unqualified types here; consider 00307 // const T *Base::foo(); 00308 // T *Derived::foo(); 00309 if (CanDerivedReturnType.getUnqualifiedType() == 00310 CanBaseReturnType.getUnqualifiedType()) { 00311 // No adjustment needed. 00312 return BaseOffset(); 00313 } 00314 00315 const CXXRecordDecl *DerivedRD = 00316 cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl()); 00317 00318 const CXXRecordDecl *BaseRD = 00319 cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl()); 00320 00321 return ComputeBaseOffset(Context, BaseRD, DerivedRD); 00322 } 00323 00324 void 00325 FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual, 00326 CharUnits OffsetInLayoutClass, 00327 SubobjectOffsetMapTy &SubobjectOffsets, 00328 SubobjectOffsetMapTy &SubobjectLayoutClassOffsets, 00329 SubobjectCountMapTy &SubobjectCounts) { 00330 const CXXRecordDecl *RD = Base.getBase(); 00331 00332 unsigned SubobjectNumber = 0; 00333 if (!IsVirtual) 00334 SubobjectNumber = ++SubobjectCounts[RD]; 00335 00336 // Set up the subobject to offset mapping. 00337 assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber)) 00338 && "Subobject offset already exists!"); 00339 assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber)) 00340 && "Subobject offset already exists!"); 00341 00342 SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset(); 00343 SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] = 00344 OffsetInLayoutClass; 00345 00346 // Traverse our bases. 00347 for (const auto &B : RD->bases()) { 00348 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 00349 00350 CharUnits BaseOffset; 00351 CharUnits BaseOffsetInLayoutClass; 00352 if (B.isVirtual()) { 00353 // Check if we've visited this virtual base before. 00354 if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0))) 00355 continue; 00356 00357 const ASTRecordLayout &LayoutClassLayout = 00358 Context.getASTRecordLayout(LayoutClass); 00359 00360 BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 00361 BaseOffsetInLayoutClass = 00362 LayoutClassLayout.getVBaseClassOffset(BaseDecl); 00363 } else { 00364 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 00365 CharUnits Offset = Layout.getBaseClassOffset(BaseDecl); 00366 00367 BaseOffset = Base.getBaseOffset() + Offset; 00368 BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset; 00369 } 00370 00371 ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset), 00372 B.isVirtual(), BaseOffsetInLayoutClass, 00373 SubobjectOffsets, SubobjectLayoutClassOffsets, 00374 SubobjectCounts); 00375 } 00376 } 00377 00378 void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base, 00379 VisitedVirtualBasesSetTy &VisitedVirtualBases) { 00380 const CXXRecordDecl *RD = Base.getBase(); 00381 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 00382 00383 for (const auto &B : RD->bases()) { 00384 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 00385 00386 // Ignore bases that don't have any virtual member functions. 00387 if (!BaseDecl->isPolymorphic()) 00388 continue; 00389 00390 CharUnits BaseOffset; 00391 if (B.isVirtual()) { 00392 if (!VisitedVirtualBases.insert(BaseDecl)) { 00393 // We've visited this base before. 00394 continue; 00395 } 00396 00397 BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 00398 } else { 00399 BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset(); 00400 } 00401 00402 dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases); 00403 } 00404 00405 Out << "Final overriders for ("; 00406 RD->printQualifiedName(Out); 00407 Out << ", "; 00408 Out << Base.getBaseOffset().getQuantity() << ")\n"; 00409 00410 // Now dump the overriders for this base subobject. 00411 for (const auto *MD : RD->methods()) { 00412 if (!MD->isVirtual()) 00413 continue; 00414 00415 OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset()); 00416 00417 Out << " "; 00418 MD->printQualifiedName(Out); 00419 Out << " - ("; 00420 Overrider.Method->printQualifiedName(Out); 00421 Out << ", " << Overrider.Offset.getQuantity() << ')'; 00422 00423 BaseOffset Offset; 00424 if (!Overrider.Method->isPure()) 00425 Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD); 00426 00427 if (!Offset.isEmpty()) { 00428 Out << " [ret-adj: "; 00429 if (Offset.VirtualBase) { 00430 Offset.VirtualBase->printQualifiedName(Out); 00431 Out << " vbase, "; 00432 } 00433 00434 Out << Offset.NonVirtualOffset.getQuantity() << " nv]"; 00435 } 00436 00437 Out << "\n"; 00438 } 00439 } 00440 00441 /// VCallOffsetMap - Keeps track of vcall offsets when building a vtable. 00442 struct VCallOffsetMap { 00443 00444 typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy; 00445 00446 /// Offsets - Keeps track of methods and their offsets. 00447 // FIXME: This should be a real map and not a vector. 00448 SmallVector<MethodAndOffsetPairTy, 16> Offsets; 00449 00450 /// MethodsCanShareVCallOffset - Returns whether two virtual member functions 00451 /// can share the same vcall offset. 00452 static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, 00453 const CXXMethodDecl *RHS); 00454 00455 public: 00456 /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the 00457 /// add was successful, or false if there was already a member function with 00458 /// the same signature in the map. 00459 bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset); 00460 00461 /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the 00462 /// vtable address point) for the given virtual member function. 00463 CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD); 00464 00465 // empty - Return whether the offset map is empty or not. 00466 bool empty() const { return Offsets.empty(); } 00467 }; 00468 00469 static bool HasSameVirtualSignature(const CXXMethodDecl *LHS, 00470 const CXXMethodDecl *RHS) { 00471 const FunctionProtoType *LT = 00472 cast<FunctionProtoType>(LHS->getType().getCanonicalType()); 00473 const FunctionProtoType *RT = 00474 cast<FunctionProtoType>(RHS->getType().getCanonicalType()); 00475 00476 // Fast-path matches in the canonical types. 00477 if (LT == RT) return true; 00478 00479 // Force the signatures to match. We can't rely on the overrides 00480 // list here because there isn't necessarily an inheritance 00481 // relationship between the two methods. 00482 if (LT->getTypeQuals() != RT->getTypeQuals() || 00483 LT->getNumParams() != RT->getNumParams()) 00484 return false; 00485 for (unsigned I = 0, E = LT->getNumParams(); I != E; ++I) 00486 if (LT->getParamType(I) != RT->getParamType(I)) 00487 return false; 00488 return true; 00489 } 00490 00491 bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, 00492 const CXXMethodDecl *RHS) { 00493 assert(LHS->isVirtual() && "LHS must be virtual!"); 00494 assert(RHS->isVirtual() && "LHS must be virtual!"); 00495 00496 // A destructor can share a vcall offset with another destructor. 00497 if (isa<CXXDestructorDecl>(LHS)) 00498 return isa<CXXDestructorDecl>(RHS); 00499 00500 // FIXME: We need to check more things here. 00501 00502 // The methods must have the same name. 00503 DeclarationName LHSName = LHS->getDeclName(); 00504 DeclarationName RHSName = RHS->getDeclName(); 00505 if (LHSName != RHSName) 00506 return false; 00507 00508 // And the same signatures. 00509 return HasSameVirtualSignature(LHS, RHS); 00510 } 00511 00512 bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD, 00513 CharUnits OffsetOffset) { 00514 // Check if we can reuse an offset. 00515 for (unsigned I = 0, E = Offsets.size(); I != E; ++I) { 00516 if (MethodsCanShareVCallOffset(Offsets[I].first, MD)) 00517 return false; 00518 } 00519 00520 // Add the offset. 00521 Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset)); 00522 return true; 00523 } 00524 00525 CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) { 00526 // Look for an offset. 00527 for (unsigned I = 0, E = Offsets.size(); I != E; ++I) { 00528 if (MethodsCanShareVCallOffset(Offsets[I].first, MD)) 00529 return Offsets[I].second; 00530 } 00531 00532 llvm_unreachable("Should always find a vcall offset offset!"); 00533 } 00534 00535 /// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets. 00536 class VCallAndVBaseOffsetBuilder { 00537 public: 00538 typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 00539 VBaseOffsetOffsetsMapTy; 00540 00541 private: 00542 /// MostDerivedClass - The most derived class for which we're building vcall 00543 /// and vbase offsets. 00544 const CXXRecordDecl *MostDerivedClass; 00545 00546 /// LayoutClass - The class we're using for layout information. Will be 00547 /// different than the most derived class if we're building a construction 00548 /// vtable. 00549 const CXXRecordDecl *LayoutClass; 00550 00551 /// Context - The ASTContext which we will use for layout information. 00552 ASTContext &Context; 00553 00554 /// Components - vcall and vbase offset components 00555 typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy; 00556 VTableComponentVectorTy Components; 00557 00558 /// VisitedVirtualBases - Visited virtual bases. 00559 llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases; 00560 00561 /// VCallOffsets - Keeps track of vcall offsets. 00562 VCallOffsetMap VCallOffsets; 00563 00564 00565 /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets, 00566 /// relative to the address point. 00567 VBaseOffsetOffsetsMapTy VBaseOffsetOffsets; 00568 00569 /// FinalOverriders - The final overriders of the most derived class. 00570 /// (Can be null when we're not building a vtable of the most derived class). 00571 const FinalOverriders *Overriders; 00572 00573 /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the 00574 /// given base subobject. 00575 void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual, 00576 CharUnits RealBaseOffset); 00577 00578 /// AddVCallOffsets - Add vcall offsets for the given base subobject. 00579 void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset); 00580 00581 /// AddVBaseOffsets - Add vbase offsets for the given class. 00582 void AddVBaseOffsets(const CXXRecordDecl *Base, 00583 CharUnits OffsetInLayoutClass); 00584 00585 /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in 00586 /// chars, relative to the vtable address point. 00587 CharUnits getCurrentOffsetOffset() const; 00588 00589 public: 00590 VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass, 00591 const CXXRecordDecl *LayoutClass, 00592 const FinalOverriders *Overriders, 00593 BaseSubobject Base, bool BaseIsVirtual, 00594 CharUnits OffsetInLayoutClass) 00595 : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass), 00596 Context(MostDerivedClass->getASTContext()), Overriders(Overriders) { 00597 00598 // Add vcall and vbase offsets. 00599 AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass); 00600 } 00601 00602 /// Methods for iterating over the components. 00603 typedef VTableComponentVectorTy::const_reverse_iterator const_iterator; 00604 const_iterator components_begin() const { return Components.rbegin(); } 00605 const_iterator components_end() const { return Components.rend(); } 00606 00607 const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; } 00608 const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const { 00609 return VBaseOffsetOffsets; 00610 } 00611 }; 00612 00613 void 00614 VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base, 00615 bool BaseIsVirtual, 00616 CharUnits RealBaseOffset) { 00617 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase()); 00618 00619 // Itanium C++ ABI 2.5.2: 00620 // ..in classes sharing a virtual table with a primary base class, the vcall 00621 // and vbase offsets added by the derived class all come before the vcall 00622 // and vbase offsets required by the base class, so that the latter may be 00623 // laid out as required by the base class without regard to additions from 00624 // the derived class(es). 00625 00626 // (Since we're emitting the vcall and vbase offsets in reverse order, we'll 00627 // emit them for the primary base first). 00628 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 00629 bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual(); 00630 00631 CharUnits PrimaryBaseOffset; 00632 00633 // Get the base offset of the primary base. 00634 if (PrimaryBaseIsVirtual) { 00635 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 00636 "Primary vbase should have a zero offset!"); 00637 00638 const ASTRecordLayout &MostDerivedClassLayout = 00639 Context.getASTRecordLayout(MostDerivedClass); 00640 00641 PrimaryBaseOffset = 00642 MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase); 00643 } else { 00644 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 00645 "Primary base should have a zero offset!"); 00646 00647 PrimaryBaseOffset = Base.getBaseOffset(); 00648 } 00649 00650 AddVCallAndVBaseOffsets( 00651 BaseSubobject(PrimaryBase,PrimaryBaseOffset), 00652 PrimaryBaseIsVirtual, RealBaseOffset); 00653 } 00654 00655 AddVBaseOffsets(Base.getBase(), RealBaseOffset); 00656 00657 // We only want to add vcall offsets for virtual bases. 00658 if (BaseIsVirtual) 00659 AddVCallOffsets(Base, RealBaseOffset); 00660 } 00661 00662 CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const { 00663 // OffsetIndex is the index of this vcall or vbase offset, relative to the 00664 // vtable address point. (We subtract 3 to account for the information just 00665 // above the address point, the RTTI info, the offset to top, and the 00666 // vcall offset itself). 00667 int64_t OffsetIndex = -(int64_t)(3 + Components.size()); 00668 00669 CharUnits PointerWidth = 00670 Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0)); 00671 CharUnits OffsetOffset = PointerWidth * OffsetIndex; 00672 return OffsetOffset; 00673 } 00674 00675 void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base, 00676 CharUnits VBaseOffset) { 00677 const CXXRecordDecl *RD = Base.getBase(); 00678 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 00679 00680 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 00681 00682 // Handle the primary base first. 00683 // We only want to add vcall offsets if the base is non-virtual; a virtual 00684 // primary base will have its vcall and vbase offsets emitted already. 00685 if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) { 00686 // Get the base offset of the primary base. 00687 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 00688 "Primary base should have a zero offset!"); 00689 00690 AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()), 00691 VBaseOffset); 00692 } 00693 00694 // Add the vcall offsets. 00695 for (const auto *MD : RD->methods()) { 00696 if (!MD->isVirtual()) 00697 continue; 00698 00699 CharUnits OffsetOffset = getCurrentOffsetOffset(); 00700 00701 // Don't add a vcall offset if we already have one for this member function 00702 // signature. 00703 if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset)) 00704 continue; 00705 00706 CharUnits Offset = CharUnits::Zero(); 00707 00708 if (Overriders) { 00709 // Get the final overrider. 00710 FinalOverriders::OverriderInfo Overrider = 00711 Overriders->getOverrider(MD, Base.getBaseOffset()); 00712 00713 /// The vcall offset is the offset from the virtual base to the object 00714 /// where the function was overridden. 00715 Offset = Overrider.Offset - VBaseOffset; 00716 } 00717 00718 Components.push_back( 00719 VTableComponent::MakeVCallOffset(Offset)); 00720 } 00721 00722 // And iterate over all non-virtual bases (ignoring the primary base). 00723 for (const auto &B : RD->bases()) { 00724 if (B.isVirtual()) 00725 continue; 00726 00727 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 00728 if (BaseDecl == PrimaryBase) 00729 continue; 00730 00731 // Get the base offset of this base. 00732 CharUnits BaseOffset = Base.getBaseOffset() + 00733 Layout.getBaseClassOffset(BaseDecl); 00734 00735 AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset), 00736 VBaseOffset); 00737 } 00738 } 00739 00740 void 00741 VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD, 00742 CharUnits OffsetInLayoutClass) { 00743 const ASTRecordLayout &LayoutClassLayout = 00744 Context.getASTRecordLayout(LayoutClass); 00745 00746 // Add vbase offsets. 00747 for (const auto &B : RD->bases()) { 00748 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 00749 00750 // Check if this is a virtual base that we haven't visited before. 00751 if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl)) { 00752 CharUnits Offset = 00753 LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass; 00754 00755 // Add the vbase offset offset. 00756 assert(!VBaseOffsetOffsets.count(BaseDecl) && 00757 "vbase offset offset already exists!"); 00758 00759 CharUnits VBaseOffsetOffset = getCurrentOffsetOffset(); 00760 VBaseOffsetOffsets.insert( 00761 std::make_pair(BaseDecl, VBaseOffsetOffset)); 00762 00763 Components.push_back( 00764 VTableComponent::MakeVBaseOffset(Offset)); 00765 } 00766 00767 // Check the base class looking for more vbase offsets. 00768 AddVBaseOffsets(BaseDecl, OffsetInLayoutClass); 00769 } 00770 } 00771 00772 /// ItaniumVTableBuilder - Class for building vtable layout information. 00773 class ItaniumVTableBuilder { 00774 public: 00775 /// PrimaryBasesSetVectorTy - A set vector of direct and indirect 00776 /// primary bases. 00777 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> 00778 PrimaryBasesSetVectorTy; 00779 00780 typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 00781 VBaseOffsetOffsetsMapTy; 00782 00783 typedef llvm::DenseMap<BaseSubobject, uint64_t> 00784 AddressPointsMapTy; 00785 00786 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy; 00787 00788 private: 00789 /// VTables - Global vtable information. 00790 ItaniumVTableContext &VTables; 00791 00792 /// MostDerivedClass - The most derived class for which we're building this 00793 /// vtable. 00794 const CXXRecordDecl *MostDerivedClass; 00795 00796 /// MostDerivedClassOffset - If we're building a construction vtable, this 00797 /// holds the offset from the layout class to the most derived class. 00798 const CharUnits MostDerivedClassOffset; 00799 00800 /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual 00801 /// base. (This only makes sense when building a construction vtable). 00802 bool MostDerivedClassIsVirtual; 00803 00804 /// LayoutClass - The class we're using for layout information. Will be 00805 /// different than the most derived class if we're building a construction 00806 /// vtable. 00807 const CXXRecordDecl *LayoutClass; 00808 00809 /// Context - The ASTContext which we will use for layout information. 00810 ASTContext &Context; 00811 00812 /// FinalOverriders - The final overriders of the most derived class. 00813 const FinalOverriders Overriders; 00814 00815 /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual 00816 /// bases in this vtable. 00817 llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases; 00818 00819 /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for 00820 /// the most derived class. 00821 VBaseOffsetOffsetsMapTy VBaseOffsetOffsets; 00822 00823 /// Components - The components of the vtable being built. 00824 SmallVector<VTableComponent, 64> Components; 00825 00826 /// AddressPoints - Address points for the vtable being built. 00827 AddressPointsMapTy AddressPoints; 00828 00829 /// MethodInfo - Contains information about a method in a vtable. 00830 /// (Used for computing 'this' pointer adjustment thunks. 00831 struct MethodInfo { 00832 /// BaseOffset - The base offset of this method. 00833 const CharUnits BaseOffset; 00834 00835 /// BaseOffsetInLayoutClass - The base offset in the layout class of this 00836 /// method. 00837 const CharUnits BaseOffsetInLayoutClass; 00838 00839 /// VTableIndex - The index in the vtable that this method has. 00840 /// (For destructors, this is the index of the complete destructor). 00841 const uint64_t VTableIndex; 00842 00843 MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass, 00844 uint64_t VTableIndex) 00845 : BaseOffset(BaseOffset), 00846 BaseOffsetInLayoutClass(BaseOffsetInLayoutClass), 00847 VTableIndex(VTableIndex) { } 00848 00849 MethodInfo() 00850 : BaseOffset(CharUnits::Zero()), 00851 BaseOffsetInLayoutClass(CharUnits::Zero()), 00852 VTableIndex(0) { } 00853 }; 00854 00855 typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy; 00856 00857 /// MethodInfoMap - The information for all methods in the vtable we're 00858 /// currently building. 00859 MethodInfoMapTy MethodInfoMap; 00860 00861 /// MethodVTableIndices - Contains the index (relative to the vtable address 00862 /// point) where the function pointer for a virtual function is stored. 00863 MethodVTableIndicesTy MethodVTableIndices; 00864 00865 typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy; 00866 00867 /// VTableThunks - The thunks by vtable index in the vtable currently being 00868 /// built. 00869 VTableThunksMapTy VTableThunks; 00870 00871 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 00872 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 00873 00874 /// Thunks - A map that contains all the thunks needed for all methods in the 00875 /// most derived class for which the vtable is currently being built. 00876 ThunksMapTy Thunks; 00877 00878 /// AddThunk - Add a thunk for the given method. 00879 void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk); 00880 00881 /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the 00882 /// part of the vtable we're currently building. 00883 void ComputeThisAdjustments(); 00884 00885 typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy; 00886 00887 /// PrimaryVirtualBases - All known virtual bases who are a primary base of 00888 /// some other base. 00889 VisitedVirtualBasesSetTy PrimaryVirtualBases; 00890 00891 /// ComputeReturnAdjustment - Compute the return adjustment given a return 00892 /// adjustment base offset. 00893 ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset); 00894 00895 /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting 00896 /// the 'this' pointer from the base subobject to the derived subobject. 00897 BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base, 00898 BaseSubobject Derived) const; 00899 00900 /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the 00901 /// given virtual member function, its offset in the layout class and its 00902 /// final overrider. 00903 ThisAdjustment 00904 ComputeThisAdjustment(const CXXMethodDecl *MD, 00905 CharUnits BaseOffsetInLayoutClass, 00906 FinalOverriders::OverriderInfo Overrider); 00907 00908 /// AddMethod - Add a single virtual member function to the vtable 00909 /// components vector. 00910 void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment); 00911 00912 /// IsOverriderUsed - Returns whether the overrider will ever be used in this 00913 /// part of the vtable. 00914 /// 00915 /// Itanium C++ ABI 2.5.2: 00916 /// 00917 /// struct A { virtual void f(); }; 00918 /// struct B : virtual public A { int i; }; 00919 /// struct C : virtual public A { int j; }; 00920 /// struct D : public B, public C {}; 00921 /// 00922 /// When B and C are declared, A is a primary base in each case, so although 00923 /// vcall offsets are allocated in the A-in-B and A-in-C vtables, no this 00924 /// adjustment is required and no thunk is generated. However, inside D 00925 /// objects, A is no longer a primary base of C, so if we allowed calls to 00926 /// C::f() to use the copy of A's vtable in the C subobject, we would need 00927 /// to adjust this from C* to B::A*, which would require a third-party 00928 /// thunk. Since we require that a call to C::f() first convert to A*, 00929 /// C-in-D's copy of A's vtable is never referenced, so this is not 00930 /// necessary. 00931 bool IsOverriderUsed(const CXXMethodDecl *Overrider, 00932 CharUnits BaseOffsetInLayoutClass, 00933 const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 00934 CharUnits FirstBaseOffsetInLayoutClass) const; 00935 00936 00937 /// AddMethods - Add the methods of this base subobject and all its 00938 /// primary bases to the vtable components vector. 00939 void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass, 00940 const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 00941 CharUnits FirstBaseOffsetInLayoutClass, 00942 PrimaryBasesSetVectorTy &PrimaryBases); 00943 00944 // LayoutVTable - Layout the vtable for the given base class, including its 00945 // secondary vtables and any vtables for virtual bases. 00946 void LayoutVTable(); 00947 00948 /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the 00949 /// given base subobject, as well as all its secondary vtables. 00950 /// 00951 /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base 00952 /// or a direct or indirect base of a virtual base. 00953 /// 00954 /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual 00955 /// in the layout class. 00956 void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base, 00957 bool BaseIsMorallyVirtual, 00958 bool BaseIsVirtualInLayoutClass, 00959 CharUnits OffsetInLayoutClass); 00960 00961 /// LayoutSecondaryVTables - Layout the secondary vtables for the given base 00962 /// subobject. 00963 /// 00964 /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base 00965 /// or a direct or indirect base of a virtual base. 00966 void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual, 00967 CharUnits OffsetInLayoutClass); 00968 00969 /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this 00970 /// class hierarchy. 00971 void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD, 00972 CharUnits OffsetInLayoutClass, 00973 VisitedVirtualBasesSetTy &VBases); 00974 00975 /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the 00976 /// given base (excluding any primary bases). 00977 void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD, 00978 VisitedVirtualBasesSetTy &VBases); 00979 00980 /// isBuildingConstructionVTable - Return whether this vtable builder is 00981 /// building a construction vtable. 00982 bool isBuildingConstructorVTable() const { 00983 return MostDerivedClass != LayoutClass; 00984 } 00985 00986 public: 00987 ItaniumVTableBuilder(ItaniumVTableContext &VTables, 00988 const CXXRecordDecl *MostDerivedClass, 00989 CharUnits MostDerivedClassOffset, 00990 bool MostDerivedClassIsVirtual, 00991 const CXXRecordDecl *LayoutClass) 00992 : VTables(VTables), MostDerivedClass(MostDerivedClass), 00993 MostDerivedClassOffset(MostDerivedClassOffset), 00994 MostDerivedClassIsVirtual(MostDerivedClassIsVirtual), 00995 LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()), 00996 Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) { 00997 assert(!Context.getTargetInfo().getCXXABI().isMicrosoft()); 00998 00999 LayoutVTable(); 01000 01001 if (Context.getLangOpts().DumpVTableLayouts) 01002 dumpLayout(llvm::outs()); 01003 } 01004 01005 uint64_t getNumThunks() const { 01006 return Thunks.size(); 01007 } 01008 01009 ThunksMapTy::const_iterator thunks_begin() const { 01010 return Thunks.begin(); 01011 } 01012 01013 ThunksMapTy::const_iterator thunks_end() const { 01014 return Thunks.end(); 01015 } 01016 01017 const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const { 01018 return VBaseOffsetOffsets; 01019 } 01020 01021 const AddressPointsMapTy &getAddressPoints() const { 01022 return AddressPoints; 01023 } 01024 01025 MethodVTableIndicesTy::const_iterator vtable_indices_begin() const { 01026 return MethodVTableIndices.begin(); 01027 } 01028 01029 MethodVTableIndicesTy::const_iterator vtable_indices_end() const { 01030 return MethodVTableIndices.end(); 01031 } 01032 01033 /// getNumVTableComponents - Return the number of components in the vtable 01034 /// currently built. 01035 uint64_t getNumVTableComponents() const { 01036 return Components.size(); 01037 } 01038 01039 const VTableComponent *vtable_component_begin() const { 01040 return Components.begin(); 01041 } 01042 01043 const VTableComponent *vtable_component_end() const { 01044 return Components.end(); 01045 } 01046 01047 AddressPointsMapTy::const_iterator address_points_begin() const { 01048 return AddressPoints.begin(); 01049 } 01050 01051 AddressPointsMapTy::const_iterator address_points_end() const { 01052 return AddressPoints.end(); 01053 } 01054 01055 VTableThunksMapTy::const_iterator vtable_thunks_begin() const { 01056 return VTableThunks.begin(); 01057 } 01058 01059 VTableThunksMapTy::const_iterator vtable_thunks_end() const { 01060 return VTableThunks.end(); 01061 } 01062 01063 /// dumpLayout - Dump the vtable layout. 01064 void dumpLayout(raw_ostream&); 01065 }; 01066 01067 void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD, 01068 const ThunkInfo &Thunk) { 01069 assert(!isBuildingConstructorVTable() && 01070 "Can't add thunks for construction vtable"); 01071 01072 SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD]; 01073 01074 // Check if we have this thunk already. 01075 if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) != 01076 ThunksVector.end()) 01077 return; 01078 01079 ThunksVector.push_back(Thunk); 01080 } 01081 01082 typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy; 01083 01084 /// Visit all the methods overridden by the given method recursively, 01085 /// in a depth-first pre-order. The Visitor's visitor method returns a bool 01086 /// indicating whether to continue the recursion for the given overridden 01087 /// method (i.e. returning false stops the iteration). 01088 template <class VisitorTy> 01089 static void 01090 visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) { 01091 assert(MD->isVirtual() && "Method is not virtual!"); 01092 01093 for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(), 01094 E = MD->end_overridden_methods(); I != E; ++I) { 01095 const CXXMethodDecl *OverriddenMD = *I; 01096 if (!Visitor.visit(OverriddenMD)) 01097 continue; 01098 visitAllOverriddenMethods(OverriddenMD, Visitor); 01099 } 01100 } 01101 01102 namespace { 01103 struct OverriddenMethodsCollector { 01104 OverriddenMethodsSetTy *Methods; 01105 01106 bool visit(const CXXMethodDecl *MD) { 01107 // Don't recurse on this method if we've already collected it. 01108 return Methods->insert(MD); 01109 } 01110 }; 01111 } 01112 01113 /// ComputeAllOverriddenMethods - Given a method decl, will return a set of all 01114 /// the overridden methods that the function decl overrides. 01115 static void 01116 ComputeAllOverriddenMethods(const CXXMethodDecl *MD, 01117 OverriddenMethodsSetTy& OverriddenMethods) { 01118 OverriddenMethodsCollector Collector = { &OverriddenMethods }; 01119 visitAllOverriddenMethods(MD, Collector); 01120 } 01121 01122 void ItaniumVTableBuilder::ComputeThisAdjustments() { 01123 // Now go through the method info map and see if any of the methods need 01124 // 'this' pointer adjustments. 01125 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(), 01126 E = MethodInfoMap.end(); I != E; ++I) { 01127 const CXXMethodDecl *MD = I->first; 01128 const MethodInfo &MethodInfo = I->second; 01129 01130 // Ignore adjustments for unused function pointers. 01131 uint64_t VTableIndex = MethodInfo.VTableIndex; 01132 if (Components[VTableIndex].getKind() == 01133 VTableComponent::CK_UnusedFunctionPointer) 01134 continue; 01135 01136 // Get the final overrider for this method. 01137 FinalOverriders::OverriderInfo Overrider = 01138 Overriders.getOverrider(MD, MethodInfo.BaseOffset); 01139 01140 // Check if we need an adjustment at all. 01141 if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) { 01142 // When a return thunk is needed by a derived class that overrides a 01143 // virtual base, gcc uses a virtual 'this' adjustment as well. 01144 // While the thunk itself might be needed by vtables in subclasses or 01145 // in construction vtables, there doesn't seem to be a reason for using 01146 // the thunk in this vtable. Still, we do so to match gcc. 01147 if (VTableThunks.lookup(VTableIndex).Return.isEmpty()) 01148 continue; 01149 } 01150 01151 ThisAdjustment ThisAdjustment = 01152 ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider); 01153 01154 if (ThisAdjustment.isEmpty()) 01155 continue; 01156 01157 // Add it. 01158 VTableThunks[VTableIndex].This = ThisAdjustment; 01159 01160 if (isa<CXXDestructorDecl>(MD)) { 01161 // Add an adjustment for the deleting destructor as well. 01162 VTableThunks[VTableIndex + 1].This = ThisAdjustment; 01163 } 01164 } 01165 01166 /// Clear the method info map. 01167 MethodInfoMap.clear(); 01168 01169 if (isBuildingConstructorVTable()) { 01170 // We don't need to store thunk information for construction vtables. 01171 return; 01172 } 01173 01174 for (VTableThunksMapTy::const_iterator I = VTableThunks.begin(), 01175 E = VTableThunks.end(); I != E; ++I) { 01176 const VTableComponent &Component = Components[I->first]; 01177 const ThunkInfo &Thunk = I->second; 01178 const CXXMethodDecl *MD; 01179 01180 switch (Component.getKind()) { 01181 default: 01182 llvm_unreachable("Unexpected vtable component kind!"); 01183 case VTableComponent::CK_FunctionPointer: 01184 MD = Component.getFunctionDecl(); 01185 break; 01186 case VTableComponent::CK_CompleteDtorPointer: 01187 MD = Component.getDestructorDecl(); 01188 break; 01189 case VTableComponent::CK_DeletingDtorPointer: 01190 // We've already added the thunk when we saw the complete dtor pointer. 01191 continue; 01192 } 01193 01194 if (MD->getParent() == MostDerivedClass) 01195 AddThunk(MD, Thunk); 01196 } 01197 } 01198 01199 ReturnAdjustment 01200 ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) { 01201 ReturnAdjustment Adjustment; 01202 01203 if (!Offset.isEmpty()) { 01204 if (Offset.VirtualBase) { 01205 // Get the virtual base offset offset. 01206 if (Offset.DerivedClass == MostDerivedClass) { 01207 // We can get the offset offset directly from our map. 01208 Adjustment.Virtual.Itanium.VBaseOffsetOffset = 01209 VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity(); 01210 } else { 01211 Adjustment.Virtual.Itanium.VBaseOffsetOffset = 01212 VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass, 01213 Offset.VirtualBase).getQuantity(); 01214 } 01215 } 01216 01217 Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity(); 01218 } 01219 01220 return Adjustment; 01221 } 01222 01223 BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset( 01224 BaseSubobject Base, BaseSubobject Derived) const { 01225 const CXXRecordDecl *BaseRD = Base.getBase(); 01226 const CXXRecordDecl *DerivedRD = Derived.getBase(); 01227 01228 CXXBasePaths Paths(/*FindAmbiguities=*/true, 01229 /*RecordPaths=*/true, /*DetectVirtual=*/true); 01230 01231 if (!DerivedRD->isDerivedFrom(BaseRD, Paths)) 01232 llvm_unreachable("Class must be derived from the passed in base class!"); 01233 01234 // We have to go through all the paths, and see which one leads us to the 01235 // right base subobject. 01236 for (CXXBasePaths::const_paths_iterator I = Paths.begin(), E = Paths.end(); 01237 I != E; ++I) { 01238 BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, *I); 01239 01240 CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset; 01241 01242 if (Offset.VirtualBase) { 01243 // If we have a virtual base class, the non-virtual offset is relative 01244 // to the virtual base class offset. 01245 const ASTRecordLayout &LayoutClassLayout = 01246 Context.getASTRecordLayout(LayoutClass); 01247 01248 /// Get the virtual base offset, relative to the most derived class 01249 /// layout. 01250 OffsetToBaseSubobject += 01251 LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase); 01252 } else { 01253 // Otherwise, the non-virtual offset is relative to the derived class 01254 // offset. 01255 OffsetToBaseSubobject += Derived.getBaseOffset(); 01256 } 01257 01258 // Check if this path gives us the right base subobject. 01259 if (OffsetToBaseSubobject == Base.getBaseOffset()) { 01260 // Since we're going from the base class _to_ the derived class, we'll 01261 // invert the non-virtual offset here. 01262 Offset.NonVirtualOffset = -Offset.NonVirtualOffset; 01263 return Offset; 01264 } 01265 } 01266 01267 return BaseOffset(); 01268 } 01269 01270 ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment( 01271 const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass, 01272 FinalOverriders::OverriderInfo Overrider) { 01273 // Ignore adjustments for pure virtual member functions. 01274 if (Overrider.Method->isPure()) 01275 return ThisAdjustment(); 01276 01277 BaseSubobject OverriddenBaseSubobject(MD->getParent(), 01278 BaseOffsetInLayoutClass); 01279 01280 BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(), 01281 Overrider.Offset); 01282 01283 // Compute the adjustment offset. 01284 BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject, 01285 OverriderBaseSubobject); 01286 if (Offset.isEmpty()) 01287 return ThisAdjustment(); 01288 01289 ThisAdjustment Adjustment; 01290 01291 if (Offset.VirtualBase) { 01292 // Get the vcall offset map for this virtual base. 01293 VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase]; 01294 01295 if (VCallOffsets.empty()) { 01296 // We don't have vcall offsets for this virtual base, go ahead and 01297 // build them. 01298 VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, MostDerivedClass, 01299 /*FinalOverriders=*/nullptr, 01300 BaseSubobject(Offset.VirtualBase, 01301 CharUnits::Zero()), 01302 /*BaseIsVirtual=*/true, 01303 /*OffsetInLayoutClass=*/ 01304 CharUnits::Zero()); 01305 01306 VCallOffsets = Builder.getVCallOffsets(); 01307 } 01308 01309 Adjustment.Virtual.Itanium.VCallOffsetOffset = 01310 VCallOffsets.getVCallOffsetOffset(MD).getQuantity(); 01311 } 01312 01313 // Set the non-virtual part of the adjustment. 01314 Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity(); 01315 01316 return Adjustment; 01317 } 01318 01319 void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD, 01320 ReturnAdjustment ReturnAdjustment) { 01321 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 01322 assert(ReturnAdjustment.isEmpty() && 01323 "Destructor can't have return adjustment!"); 01324 01325 // Add both the complete destructor and the deleting destructor. 01326 Components.push_back(VTableComponent::MakeCompleteDtor(DD)); 01327 Components.push_back(VTableComponent::MakeDeletingDtor(DD)); 01328 } else { 01329 // Add the return adjustment if necessary. 01330 if (!ReturnAdjustment.isEmpty()) 01331 VTableThunks[Components.size()].Return = ReturnAdjustment; 01332 01333 // Add the function. 01334 Components.push_back(VTableComponent::MakeFunction(MD)); 01335 } 01336 } 01337 01338 /// OverridesIndirectMethodInBase - Return whether the given member function 01339 /// overrides any methods in the set of given bases. 01340 /// Unlike OverridesMethodInBase, this checks "overriders of overriders". 01341 /// For example, if we have: 01342 /// 01343 /// struct A { virtual void f(); } 01344 /// struct B : A { virtual void f(); } 01345 /// struct C : B { virtual void f(); } 01346 /// 01347 /// OverridesIndirectMethodInBase will return true if given C::f as the method 01348 /// and { A } as the set of bases. 01349 static bool OverridesIndirectMethodInBases( 01350 const CXXMethodDecl *MD, 01351 ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) { 01352 if (Bases.count(MD->getParent())) 01353 return true; 01354 01355 for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(), 01356 E = MD->end_overridden_methods(); I != E; ++I) { 01357 const CXXMethodDecl *OverriddenMD = *I; 01358 01359 // Check "indirect overriders". 01360 if (OverridesIndirectMethodInBases(OverriddenMD, Bases)) 01361 return true; 01362 } 01363 01364 return false; 01365 } 01366 01367 bool ItaniumVTableBuilder::IsOverriderUsed( 01368 const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass, 01369 const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 01370 CharUnits FirstBaseOffsetInLayoutClass) const { 01371 // If the base and the first base in the primary base chain have the same 01372 // offsets, then this overrider will be used. 01373 if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass) 01374 return true; 01375 01376 // We know now that Base (or a direct or indirect base of it) is a primary 01377 // base in part of the class hierarchy, but not a primary base in the most 01378 // derived class. 01379 01380 // If the overrider is the first base in the primary base chain, we know 01381 // that the overrider will be used. 01382 if (Overrider->getParent() == FirstBaseInPrimaryBaseChain) 01383 return true; 01384 01385 ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases; 01386 01387 const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain; 01388 PrimaryBases.insert(RD); 01389 01390 // Now traverse the base chain, starting with the first base, until we find 01391 // the base that is no longer a primary base. 01392 while (true) { 01393 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 01394 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 01395 01396 if (!PrimaryBase) 01397 break; 01398 01399 if (Layout.isPrimaryBaseVirtual()) { 01400 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 01401 "Primary base should always be at offset 0!"); 01402 01403 const ASTRecordLayout &LayoutClassLayout = 01404 Context.getASTRecordLayout(LayoutClass); 01405 01406 // Now check if this is the primary base that is not a primary base in the 01407 // most derived class. 01408 if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) != 01409 FirstBaseOffsetInLayoutClass) { 01410 // We found it, stop walking the chain. 01411 break; 01412 } 01413 } else { 01414 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 01415 "Primary base should always be at offset 0!"); 01416 } 01417 01418 if (!PrimaryBases.insert(PrimaryBase)) 01419 llvm_unreachable("Found a duplicate primary base!"); 01420 01421 RD = PrimaryBase; 01422 } 01423 01424 // If the final overrider is an override of one of the primary bases, 01425 // then we know that it will be used. 01426 return OverridesIndirectMethodInBases(Overrider, PrimaryBases); 01427 } 01428 01429 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy; 01430 01431 /// FindNearestOverriddenMethod - Given a method, returns the overridden method 01432 /// from the nearest base. Returns null if no method was found. 01433 /// The Bases are expected to be sorted in a base-to-derived order. 01434 static const CXXMethodDecl * 01435 FindNearestOverriddenMethod(const CXXMethodDecl *MD, 01436 BasesSetVectorTy &Bases) { 01437 OverriddenMethodsSetTy OverriddenMethods; 01438 ComputeAllOverriddenMethods(MD, OverriddenMethods); 01439 01440 for (int I = Bases.size(), E = 0; I != E; --I) { 01441 const CXXRecordDecl *PrimaryBase = Bases[I - 1]; 01442 01443 // Now check the overridden methods. 01444 for (OverriddenMethodsSetTy::const_iterator I = OverriddenMethods.begin(), 01445 E = OverriddenMethods.end(); I != E; ++I) { 01446 const CXXMethodDecl *OverriddenMD = *I; 01447 01448 // We found our overridden method. 01449 if (OverriddenMD->getParent() == PrimaryBase) 01450 return OverriddenMD; 01451 } 01452 } 01453 01454 return nullptr; 01455 } 01456 01457 void ItaniumVTableBuilder::AddMethods( 01458 BaseSubobject Base, CharUnits BaseOffsetInLayoutClass, 01459 const CXXRecordDecl *FirstBaseInPrimaryBaseChain, 01460 CharUnits FirstBaseOffsetInLayoutClass, 01461 PrimaryBasesSetVectorTy &PrimaryBases) { 01462 // Itanium C++ ABI 2.5.2: 01463 // The order of the virtual function pointers in a virtual table is the 01464 // order of declaration of the corresponding member functions in the class. 01465 // 01466 // There is an entry for any virtual function declared in a class, 01467 // whether it is a new function or overrides a base class function, 01468 // unless it overrides a function from the primary base, and conversion 01469 // between their return types does not require an adjustment. 01470 01471 const CXXRecordDecl *RD = Base.getBase(); 01472 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 01473 01474 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 01475 CharUnits PrimaryBaseOffset; 01476 CharUnits PrimaryBaseOffsetInLayoutClass; 01477 if (Layout.isPrimaryBaseVirtual()) { 01478 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() && 01479 "Primary vbase should have a zero offset!"); 01480 01481 const ASTRecordLayout &MostDerivedClassLayout = 01482 Context.getASTRecordLayout(MostDerivedClass); 01483 01484 PrimaryBaseOffset = 01485 MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase); 01486 01487 const ASTRecordLayout &LayoutClassLayout = 01488 Context.getASTRecordLayout(LayoutClass); 01489 01490 PrimaryBaseOffsetInLayoutClass = 01491 LayoutClassLayout.getVBaseClassOffset(PrimaryBase); 01492 } else { 01493 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() && 01494 "Primary base should have a zero offset!"); 01495 01496 PrimaryBaseOffset = Base.getBaseOffset(); 01497 PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass; 01498 } 01499 01500 AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset), 01501 PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain, 01502 FirstBaseOffsetInLayoutClass, PrimaryBases); 01503 01504 if (!PrimaryBases.insert(PrimaryBase)) 01505 llvm_unreachable("Found a duplicate primary base!"); 01506 } 01507 01508 const CXXDestructorDecl *ImplicitVirtualDtor = nullptr; 01509 01510 typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy; 01511 NewVirtualFunctionsTy NewVirtualFunctions; 01512 01513 // Now go through all virtual member functions and add them. 01514 for (const auto *MD : RD->methods()) { 01515 if (!MD->isVirtual()) 01516 continue; 01517 01518 // Get the final overrider. 01519 FinalOverriders::OverriderInfo Overrider = 01520 Overriders.getOverrider(MD, Base.getBaseOffset()); 01521 01522 // Check if this virtual member function overrides a method in a primary 01523 // base. If this is the case, and the return type doesn't require adjustment 01524 // then we can just use the member function from the primary base. 01525 if (const CXXMethodDecl *OverriddenMD = 01526 FindNearestOverriddenMethod(MD, PrimaryBases)) { 01527 if (ComputeReturnAdjustmentBaseOffset(Context, MD, 01528 OverriddenMD).isEmpty()) { 01529 // Replace the method info of the overridden method with our own 01530 // method. 01531 assert(MethodInfoMap.count(OverriddenMD) && 01532 "Did not find the overridden method!"); 01533 MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD]; 01534 01535 MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass, 01536 OverriddenMethodInfo.VTableIndex); 01537 01538 assert(!MethodInfoMap.count(MD) && 01539 "Should not have method info for this method yet!"); 01540 01541 MethodInfoMap.insert(std::make_pair(MD, MethodInfo)); 01542 MethodInfoMap.erase(OverriddenMD); 01543 01544 // If the overridden method exists in a virtual base class or a direct 01545 // or indirect base class of a virtual base class, we need to emit a 01546 // thunk if we ever have a class hierarchy where the base class is not 01547 // a primary base in the complete object. 01548 if (!isBuildingConstructorVTable() && OverriddenMD != MD) { 01549 // Compute the this adjustment. 01550 ThisAdjustment ThisAdjustment = 01551 ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass, 01552 Overrider); 01553 01554 if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset && 01555 Overrider.Method->getParent() == MostDerivedClass) { 01556 01557 // There's no return adjustment from OverriddenMD and MD, 01558 // but that doesn't mean there isn't one between MD and 01559 // the final overrider. 01560 BaseOffset ReturnAdjustmentOffset = 01561 ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD); 01562 ReturnAdjustment ReturnAdjustment = 01563 ComputeReturnAdjustment(ReturnAdjustmentOffset); 01564 01565 // This is a virtual thunk for the most derived class, add it. 01566 AddThunk(Overrider.Method, 01567 ThunkInfo(ThisAdjustment, ReturnAdjustment)); 01568 } 01569 } 01570 01571 continue; 01572 } 01573 } 01574 01575 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 01576 if (MD->isImplicit()) { 01577 // Itanium C++ ABI 2.5.2: 01578 // If a class has an implicitly-defined virtual destructor, 01579 // its entries come after the declared virtual function pointers. 01580 01581 assert(!ImplicitVirtualDtor && 01582 "Did already see an implicit virtual dtor!"); 01583 ImplicitVirtualDtor = DD; 01584 continue; 01585 } 01586 } 01587 01588 NewVirtualFunctions.push_back(MD); 01589 } 01590 01591 if (ImplicitVirtualDtor) 01592 NewVirtualFunctions.push_back(ImplicitVirtualDtor); 01593 01594 for (NewVirtualFunctionsTy::const_iterator I = NewVirtualFunctions.begin(), 01595 E = NewVirtualFunctions.end(); I != E; ++I) { 01596 const CXXMethodDecl *MD = *I; 01597 01598 // Get the final overrider. 01599 FinalOverriders::OverriderInfo Overrider = 01600 Overriders.getOverrider(MD, Base.getBaseOffset()); 01601 01602 // Insert the method info for this method. 01603 MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass, 01604 Components.size()); 01605 01606 assert(!MethodInfoMap.count(MD) && 01607 "Should not have method info for this method yet!"); 01608 MethodInfoMap.insert(std::make_pair(MD, MethodInfo)); 01609 01610 // Check if this overrider is going to be used. 01611 const CXXMethodDecl *OverriderMD = Overrider.Method; 01612 if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass, 01613 FirstBaseInPrimaryBaseChain, 01614 FirstBaseOffsetInLayoutClass)) { 01615 Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD)); 01616 continue; 01617 } 01618 01619 // Check if this overrider needs a return adjustment. 01620 // We don't want to do this for pure virtual member functions. 01621 BaseOffset ReturnAdjustmentOffset; 01622 if (!OverriderMD->isPure()) { 01623 ReturnAdjustmentOffset = 01624 ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD); 01625 } 01626 01627 ReturnAdjustment ReturnAdjustment = 01628 ComputeReturnAdjustment(ReturnAdjustmentOffset); 01629 01630 AddMethod(Overrider.Method, ReturnAdjustment); 01631 } 01632 } 01633 01634 void ItaniumVTableBuilder::LayoutVTable() { 01635 LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass, 01636 CharUnits::Zero()), 01637 /*BaseIsMorallyVirtual=*/false, 01638 MostDerivedClassIsVirtual, 01639 MostDerivedClassOffset); 01640 01641 VisitedVirtualBasesSetTy VBases; 01642 01643 // Determine the primary virtual bases. 01644 DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset, 01645 VBases); 01646 VBases.clear(); 01647 01648 LayoutVTablesForVirtualBases(MostDerivedClass, VBases); 01649 01650 // -fapple-kext adds an extra entry at end of vtbl. 01651 bool IsAppleKext = Context.getLangOpts().AppleKext; 01652 if (IsAppleKext) 01653 Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero())); 01654 } 01655 01656 void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables( 01657 BaseSubobject Base, bool BaseIsMorallyVirtual, 01658 bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) { 01659 assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!"); 01660 01661 // Add vcall and vbase offsets for this vtable. 01662 VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders, 01663 Base, BaseIsVirtualInLayoutClass, 01664 OffsetInLayoutClass); 01665 Components.append(Builder.components_begin(), Builder.components_end()); 01666 01667 // Check if we need to add these vcall offsets. 01668 if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) { 01669 VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()]; 01670 01671 if (VCallOffsets.empty()) 01672 VCallOffsets = Builder.getVCallOffsets(); 01673 } 01674 01675 // If we're laying out the most derived class we want to keep track of the 01676 // virtual base class offset offsets. 01677 if (Base.getBase() == MostDerivedClass) 01678 VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets(); 01679 01680 // Add the offset to top. 01681 CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass; 01682 Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop)); 01683 01684 // Next, add the RTTI. 01685 Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass)); 01686 01687 uint64_t AddressPoint = Components.size(); 01688 01689 // Now go through all virtual member functions and add them. 01690 PrimaryBasesSetVectorTy PrimaryBases; 01691 AddMethods(Base, OffsetInLayoutClass, 01692 Base.getBase(), OffsetInLayoutClass, 01693 PrimaryBases); 01694 01695 const CXXRecordDecl *RD = Base.getBase(); 01696 if (RD == MostDerivedClass) { 01697 assert(MethodVTableIndices.empty()); 01698 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(), 01699 E = MethodInfoMap.end(); I != E; ++I) { 01700 const CXXMethodDecl *MD = I->first; 01701 const MethodInfo &MI = I->second; 01702 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 01703 MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)] 01704 = MI.VTableIndex - AddressPoint; 01705 MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)] 01706 = MI.VTableIndex + 1 - AddressPoint; 01707 } else { 01708 MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint; 01709 } 01710 } 01711 } 01712 01713 // Compute 'this' pointer adjustments. 01714 ComputeThisAdjustments(); 01715 01716 // Add all address points. 01717 while (true) { 01718 AddressPoints.insert(std::make_pair( 01719 BaseSubobject(RD, OffsetInLayoutClass), 01720 AddressPoint)); 01721 01722 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 01723 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 01724 01725 if (!PrimaryBase) 01726 break; 01727 01728 if (Layout.isPrimaryBaseVirtual()) { 01729 // Check if this virtual primary base is a primary base in the layout 01730 // class. If it's not, we don't want to add it. 01731 const ASTRecordLayout &LayoutClassLayout = 01732 Context.getASTRecordLayout(LayoutClass); 01733 01734 if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) != 01735 OffsetInLayoutClass) { 01736 // We don't want to add this class (or any of its primary bases). 01737 break; 01738 } 01739 } 01740 01741 RD = PrimaryBase; 01742 } 01743 01744 // Layout secondary vtables. 01745 LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass); 01746 } 01747 01748 void 01749 ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base, 01750 bool BaseIsMorallyVirtual, 01751 CharUnits OffsetInLayoutClass) { 01752 // Itanium C++ ABI 2.5.2: 01753 // Following the primary virtual table of a derived class are secondary 01754 // virtual tables for each of its proper base classes, except any primary 01755 // base(s) with which it shares its primary virtual table. 01756 01757 const CXXRecordDecl *RD = Base.getBase(); 01758 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 01759 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); 01760 01761 for (const auto &B : RD->bases()) { 01762 // Ignore virtual bases, we'll emit them later. 01763 if (B.isVirtual()) 01764 continue; 01765 01766 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 01767 01768 // Ignore bases that don't have a vtable. 01769 if (!BaseDecl->isDynamicClass()) 01770 continue; 01771 01772 if (isBuildingConstructorVTable()) { 01773 // Itanium C++ ABI 2.6.4: 01774 // Some of the base class subobjects may not need construction virtual 01775 // tables, which will therefore not be present in the construction 01776 // virtual table group, even though the subobject virtual tables are 01777 // present in the main virtual table group for the complete object. 01778 if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases()) 01779 continue; 01780 } 01781 01782 // Get the base offset of this base. 01783 CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl); 01784 CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset; 01785 01786 CharUnits BaseOffsetInLayoutClass = 01787 OffsetInLayoutClass + RelativeBaseOffset; 01788 01789 // Don't emit a secondary vtable for a primary base. We might however want 01790 // to emit secondary vtables for other bases of this base. 01791 if (BaseDecl == PrimaryBase) { 01792 LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset), 01793 BaseIsMorallyVirtual, BaseOffsetInLayoutClass); 01794 continue; 01795 } 01796 01797 // Layout the primary vtable (and any secondary vtables) for this base. 01798 LayoutPrimaryAndSecondaryVTables( 01799 BaseSubobject(BaseDecl, BaseOffset), 01800 BaseIsMorallyVirtual, 01801 /*BaseIsVirtualInLayoutClass=*/false, 01802 BaseOffsetInLayoutClass); 01803 } 01804 } 01805 01806 void ItaniumVTableBuilder::DeterminePrimaryVirtualBases( 01807 const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass, 01808 VisitedVirtualBasesSetTy &VBases) { 01809 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 01810 01811 // Check if this base has a primary base. 01812 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 01813 01814 // Check if it's virtual. 01815 if (Layout.isPrimaryBaseVirtual()) { 01816 bool IsPrimaryVirtualBase = true; 01817 01818 if (isBuildingConstructorVTable()) { 01819 // Check if the base is actually a primary base in the class we use for 01820 // layout. 01821 const ASTRecordLayout &LayoutClassLayout = 01822 Context.getASTRecordLayout(LayoutClass); 01823 01824 CharUnits PrimaryBaseOffsetInLayoutClass = 01825 LayoutClassLayout.getVBaseClassOffset(PrimaryBase); 01826 01827 // We know that the base is not a primary base in the layout class if 01828 // the base offsets are different. 01829 if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass) 01830 IsPrimaryVirtualBase = false; 01831 } 01832 01833 if (IsPrimaryVirtualBase) 01834 PrimaryVirtualBases.insert(PrimaryBase); 01835 } 01836 } 01837 01838 // Traverse bases, looking for more primary virtual bases. 01839 for (const auto &B : RD->bases()) { 01840 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 01841 01842 CharUnits BaseOffsetInLayoutClass; 01843 01844 if (B.isVirtual()) { 01845 if (!VBases.insert(BaseDecl)) 01846 continue; 01847 01848 const ASTRecordLayout &LayoutClassLayout = 01849 Context.getASTRecordLayout(LayoutClass); 01850 01851 BaseOffsetInLayoutClass = 01852 LayoutClassLayout.getVBaseClassOffset(BaseDecl); 01853 } else { 01854 BaseOffsetInLayoutClass = 01855 OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl); 01856 } 01857 01858 DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases); 01859 } 01860 } 01861 01862 void ItaniumVTableBuilder::LayoutVTablesForVirtualBases( 01863 const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) { 01864 // Itanium C++ ABI 2.5.2: 01865 // Then come the virtual base virtual tables, also in inheritance graph 01866 // order, and again excluding primary bases (which share virtual tables with 01867 // the classes for which they are primary). 01868 for (const auto &B : RD->bases()) { 01869 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl(); 01870 01871 // Check if this base needs a vtable. (If it's virtual, not a primary base 01872 // of some other class, and we haven't visited it before). 01873 if (B.isVirtual() && BaseDecl->isDynamicClass() && 01874 !PrimaryVirtualBases.count(BaseDecl) && VBases.insert(BaseDecl)) { 01875 const ASTRecordLayout &MostDerivedClassLayout = 01876 Context.getASTRecordLayout(MostDerivedClass); 01877 CharUnits BaseOffset = 01878 MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); 01879 01880 const ASTRecordLayout &LayoutClassLayout = 01881 Context.getASTRecordLayout(LayoutClass); 01882 CharUnits BaseOffsetInLayoutClass = 01883 LayoutClassLayout.getVBaseClassOffset(BaseDecl); 01884 01885 LayoutPrimaryAndSecondaryVTables( 01886 BaseSubobject(BaseDecl, BaseOffset), 01887 /*BaseIsMorallyVirtual=*/true, 01888 /*BaseIsVirtualInLayoutClass=*/true, 01889 BaseOffsetInLayoutClass); 01890 } 01891 01892 // We only need to check the base for virtual base vtables if it actually 01893 // has virtual bases. 01894 if (BaseDecl->getNumVBases()) 01895 LayoutVTablesForVirtualBases(BaseDecl, VBases); 01896 } 01897 } 01898 01899 /// dumpLayout - Dump the vtable layout. 01900 void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) { 01901 // FIXME: write more tests that actually use the dumpLayout output to prevent 01902 // ItaniumVTableBuilder regressions. 01903 01904 if (isBuildingConstructorVTable()) { 01905 Out << "Construction vtable for ('"; 01906 MostDerivedClass->printQualifiedName(Out); 01907 Out << "', "; 01908 Out << MostDerivedClassOffset.getQuantity() << ") in '"; 01909 LayoutClass->printQualifiedName(Out); 01910 } else { 01911 Out << "Vtable for '"; 01912 MostDerivedClass->printQualifiedName(Out); 01913 } 01914 Out << "' (" << Components.size() << " entries).\n"; 01915 01916 // Iterate through the address points and insert them into a new map where 01917 // they are keyed by the index and not the base object. 01918 // Since an address point can be shared by multiple subobjects, we use an 01919 // STL multimap. 01920 std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex; 01921 for (AddressPointsMapTy::const_iterator I = AddressPoints.begin(), 01922 E = AddressPoints.end(); I != E; ++I) { 01923 const BaseSubobject& Base = I->first; 01924 uint64_t Index = I->second; 01925 01926 AddressPointsByIndex.insert(std::make_pair(Index, Base)); 01927 } 01928 01929 for (unsigned I = 0, E = Components.size(); I != E; ++I) { 01930 uint64_t Index = I; 01931 01932 Out << llvm::format("%4d | ", I); 01933 01934 const VTableComponent &Component = Components[I]; 01935 01936 // Dump the component. 01937 switch (Component.getKind()) { 01938 01939 case VTableComponent::CK_VCallOffset: 01940 Out << "vcall_offset (" 01941 << Component.getVCallOffset().getQuantity() 01942 << ")"; 01943 break; 01944 01945 case VTableComponent::CK_VBaseOffset: 01946 Out << "vbase_offset (" 01947 << Component.getVBaseOffset().getQuantity() 01948 << ")"; 01949 break; 01950 01951 case VTableComponent::CK_OffsetToTop: 01952 Out << "offset_to_top (" 01953 << Component.getOffsetToTop().getQuantity() 01954 << ")"; 01955 break; 01956 01957 case VTableComponent::CK_RTTI: 01958 Component.getRTTIDecl()->printQualifiedName(Out); 01959 Out << " RTTI"; 01960 break; 01961 01962 case VTableComponent::CK_FunctionPointer: { 01963 const CXXMethodDecl *MD = Component.getFunctionDecl(); 01964 01965 std::string Str = 01966 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 01967 MD); 01968 Out << Str; 01969 if (MD->isPure()) 01970 Out << " [pure]"; 01971 01972 if (MD->isDeleted()) 01973 Out << " [deleted]"; 01974 01975 ThunkInfo Thunk = VTableThunks.lookup(I); 01976 if (!Thunk.isEmpty()) { 01977 // If this function pointer has a return adjustment, dump it. 01978 if (!Thunk.Return.isEmpty()) { 01979 Out << "\n [return adjustment: "; 01980 Out << Thunk.Return.NonVirtual << " non-virtual"; 01981 01982 if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) { 01983 Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset; 01984 Out << " vbase offset offset"; 01985 } 01986 01987 Out << ']'; 01988 } 01989 01990 // If this function pointer has a 'this' pointer adjustment, dump it. 01991 if (!Thunk.This.isEmpty()) { 01992 Out << "\n [this adjustment: "; 01993 Out << Thunk.This.NonVirtual << " non-virtual"; 01994 01995 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 01996 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 01997 Out << " vcall offset offset"; 01998 } 01999 02000 Out << ']'; 02001 } 02002 } 02003 02004 break; 02005 } 02006 02007 case VTableComponent::CK_CompleteDtorPointer: 02008 case VTableComponent::CK_DeletingDtorPointer: { 02009 bool IsComplete = 02010 Component.getKind() == VTableComponent::CK_CompleteDtorPointer; 02011 02012 const CXXDestructorDecl *DD = Component.getDestructorDecl(); 02013 02014 DD->printQualifiedName(Out); 02015 if (IsComplete) 02016 Out << "() [complete]"; 02017 else 02018 Out << "() [deleting]"; 02019 02020 if (DD->isPure()) 02021 Out << " [pure]"; 02022 02023 ThunkInfo Thunk = VTableThunks.lookup(I); 02024 if (!Thunk.isEmpty()) { 02025 // If this destructor has a 'this' pointer adjustment, dump it. 02026 if (!Thunk.This.isEmpty()) { 02027 Out << "\n [this adjustment: "; 02028 Out << Thunk.This.NonVirtual << " non-virtual"; 02029 02030 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 02031 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 02032 Out << " vcall offset offset"; 02033 } 02034 02035 Out << ']'; 02036 } 02037 } 02038 02039 break; 02040 } 02041 02042 case VTableComponent::CK_UnusedFunctionPointer: { 02043 const CXXMethodDecl *MD = Component.getUnusedFunctionDecl(); 02044 02045 std::string Str = 02046 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 02047 MD); 02048 Out << "[unused] " << Str; 02049 if (MD->isPure()) 02050 Out << " [pure]"; 02051 } 02052 02053 } 02054 02055 Out << '\n'; 02056 02057 // Dump the next address point. 02058 uint64_t NextIndex = Index + 1; 02059 if (AddressPointsByIndex.count(NextIndex)) { 02060 if (AddressPointsByIndex.count(NextIndex) == 1) { 02061 const BaseSubobject &Base = 02062 AddressPointsByIndex.find(NextIndex)->second; 02063 02064 Out << " -- ("; 02065 Base.getBase()->printQualifiedName(Out); 02066 Out << ", " << Base.getBaseOffset().getQuantity(); 02067 Out << ") vtable address --\n"; 02068 } else { 02069 CharUnits BaseOffset = 02070 AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset(); 02071 02072 // We store the class names in a set to get a stable order. 02073 std::set<std::string> ClassNames; 02074 for (std::multimap<uint64_t, BaseSubobject>::const_iterator I = 02075 AddressPointsByIndex.lower_bound(NextIndex), E = 02076 AddressPointsByIndex.upper_bound(NextIndex); I != E; ++I) { 02077 assert(I->second.getBaseOffset() == BaseOffset && 02078 "Invalid base offset!"); 02079 const CXXRecordDecl *RD = I->second.getBase(); 02080 ClassNames.insert(RD->getQualifiedNameAsString()); 02081 } 02082 02083 for (std::set<std::string>::const_iterator I = ClassNames.begin(), 02084 E = ClassNames.end(); I != E; ++I) { 02085 Out << " -- (" << *I; 02086 Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n"; 02087 } 02088 } 02089 } 02090 } 02091 02092 Out << '\n'; 02093 02094 if (isBuildingConstructorVTable()) 02095 return; 02096 02097 if (MostDerivedClass->getNumVBases()) { 02098 // We store the virtual base class names and their offsets in a map to get 02099 // a stable order. 02100 02101 std::map<std::string, CharUnits> ClassNamesAndOffsets; 02102 for (VBaseOffsetOffsetsMapTy::const_iterator I = VBaseOffsetOffsets.begin(), 02103 E = VBaseOffsetOffsets.end(); I != E; ++I) { 02104 std::string ClassName = I->first->getQualifiedNameAsString(); 02105 CharUnits OffsetOffset = I->second; 02106 ClassNamesAndOffsets.insert( 02107 std::make_pair(ClassName, OffsetOffset)); 02108 } 02109 02110 Out << "Virtual base offset offsets for '"; 02111 MostDerivedClass->printQualifiedName(Out); 02112 Out << "' ("; 02113 Out << ClassNamesAndOffsets.size(); 02114 Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n"; 02115 02116 for (std::map<std::string, CharUnits>::const_iterator I = 02117 ClassNamesAndOffsets.begin(), E = ClassNamesAndOffsets.end(); 02118 I != E; ++I) 02119 Out << " " << I->first << " | " << I->second.getQuantity() << '\n'; 02120 02121 Out << "\n"; 02122 } 02123 02124 if (!Thunks.empty()) { 02125 // We store the method names in a map to get a stable order. 02126 std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls; 02127 02128 for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end(); 02129 I != E; ++I) { 02130 const CXXMethodDecl *MD = I->first; 02131 std::string MethodName = 02132 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 02133 MD); 02134 02135 MethodNamesAndDecls.insert(std::make_pair(MethodName, MD)); 02136 } 02137 02138 for (std::map<std::string, const CXXMethodDecl *>::const_iterator I = 02139 MethodNamesAndDecls.begin(), E = MethodNamesAndDecls.end(); 02140 I != E; ++I) { 02141 const std::string &MethodName = I->first; 02142 const CXXMethodDecl *MD = I->second; 02143 02144 ThunkInfoVectorTy ThunksVector = Thunks[MD]; 02145 std::sort(ThunksVector.begin(), ThunksVector.end(), 02146 [](const ThunkInfo &LHS, const ThunkInfo &RHS) { 02147 assert(LHS.Method == nullptr && RHS.Method == nullptr); 02148 return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return); 02149 }); 02150 02151 Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size(); 02152 Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n"; 02153 02154 for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) { 02155 const ThunkInfo &Thunk = ThunksVector[I]; 02156 02157 Out << llvm::format("%4d | ", I); 02158 02159 // If this function pointer has a return pointer adjustment, dump it. 02160 if (!Thunk.Return.isEmpty()) { 02161 Out << "return adjustment: " << Thunk.Return.NonVirtual; 02162 Out << " non-virtual"; 02163 if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) { 02164 Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset; 02165 Out << " vbase offset offset"; 02166 } 02167 02168 if (!Thunk.This.isEmpty()) 02169 Out << "\n "; 02170 } 02171 02172 // If this function pointer has a 'this' pointer adjustment, dump it. 02173 if (!Thunk.This.isEmpty()) { 02174 Out << "this adjustment: "; 02175 Out << Thunk.This.NonVirtual << " non-virtual"; 02176 02177 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) { 02178 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset; 02179 Out << " vcall offset offset"; 02180 } 02181 } 02182 02183 Out << '\n'; 02184 } 02185 02186 Out << '\n'; 02187 } 02188 } 02189 02190 // Compute the vtable indices for all the member functions. 02191 // Store them in a map keyed by the index so we'll get a sorted table. 02192 std::map<uint64_t, std::string> IndicesMap; 02193 02194 for (const auto *MD : MostDerivedClass->methods()) { 02195 // We only want virtual member functions. 02196 if (!MD->isVirtual()) 02197 continue; 02198 02199 std::string MethodName = 02200 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual, 02201 MD); 02202 02203 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 02204 GlobalDecl GD(DD, Dtor_Complete); 02205 assert(MethodVTableIndices.count(GD)); 02206 uint64_t VTableIndex = MethodVTableIndices[GD]; 02207 IndicesMap[VTableIndex] = MethodName + " [complete]"; 02208 IndicesMap[VTableIndex + 1] = MethodName + " [deleting]"; 02209 } else { 02210 assert(MethodVTableIndices.count(MD)); 02211 IndicesMap[MethodVTableIndices[MD]] = MethodName; 02212 } 02213 } 02214 02215 // Print the vtable indices for all the member functions. 02216 if (!IndicesMap.empty()) { 02217 Out << "VTable indices for '"; 02218 MostDerivedClass->printQualifiedName(Out); 02219 Out << "' (" << IndicesMap.size() << " entries).\n"; 02220 02221 for (std::map<uint64_t, std::string>::const_iterator I = IndicesMap.begin(), 02222 E = IndicesMap.end(); I != E; ++I) { 02223 uint64_t VTableIndex = I->first; 02224 const std::string &MethodName = I->second; 02225 02226 Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName 02227 << '\n'; 02228 } 02229 } 02230 02231 Out << '\n'; 02232 } 02233 } 02234 02235 VTableLayout::VTableLayout(uint64_t NumVTableComponents, 02236 const VTableComponent *VTableComponents, 02237 uint64_t NumVTableThunks, 02238 const VTableThunkTy *VTableThunks, 02239 const AddressPointsMapTy &AddressPoints, 02240 bool IsMicrosoftABI) 02241 : NumVTableComponents(NumVTableComponents), 02242 VTableComponents(new VTableComponent[NumVTableComponents]), 02243 NumVTableThunks(NumVTableThunks), 02244 VTableThunks(new VTableThunkTy[NumVTableThunks]), 02245 AddressPoints(AddressPoints), 02246 IsMicrosoftABI(IsMicrosoftABI) { 02247 std::copy(VTableComponents, VTableComponents+NumVTableComponents, 02248 this->VTableComponents.get()); 02249 std::copy(VTableThunks, VTableThunks+NumVTableThunks, 02250 this->VTableThunks.get()); 02251 std::sort(this->VTableThunks.get(), 02252 this->VTableThunks.get() + NumVTableThunks, 02253 [](const VTableLayout::VTableThunkTy &LHS, 02254 const VTableLayout::VTableThunkTy &RHS) { 02255 assert((LHS.first != RHS.first || LHS.second == RHS.second) && 02256 "Different thunks should have unique indices!"); 02257 return LHS.first < RHS.first; 02258 }); 02259 } 02260 02261 VTableLayout::~VTableLayout() { } 02262 02263 ItaniumVTableContext::ItaniumVTableContext(ASTContext &Context) 02264 : VTableContextBase(/*MS=*/false) {} 02265 02266 ItaniumVTableContext::~ItaniumVTableContext() { 02267 llvm::DeleteContainerSeconds(VTableLayouts); 02268 } 02269 02270 uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) { 02271 MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD); 02272 if (I != MethodVTableIndices.end()) 02273 return I->second; 02274 02275 const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent(); 02276 02277 computeVTableRelatedInformation(RD); 02278 02279 I = MethodVTableIndices.find(GD); 02280 assert(I != MethodVTableIndices.end() && "Did not find index!"); 02281 return I->second; 02282 } 02283 02284 CharUnits 02285 ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD, 02286 const CXXRecordDecl *VBase) { 02287 ClassPairTy ClassPair(RD, VBase); 02288 02289 VirtualBaseClassOffsetOffsetsMapTy::iterator I = 02290 VirtualBaseClassOffsetOffsets.find(ClassPair); 02291 if (I != VirtualBaseClassOffsetOffsets.end()) 02292 return I->second; 02293 02294 VCallAndVBaseOffsetBuilder Builder(RD, RD, /*FinalOverriders=*/nullptr, 02295 BaseSubobject(RD, CharUnits::Zero()), 02296 /*BaseIsVirtual=*/false, 02297 /*OffsetInLayoutClass=*/CharUnits::Zero()); 02298 02299 for (VCallAndVBaseOffsetBuilder::VBaseOffsetOffsetsMapTy::const_iterator I = 02300 Builder.getVBaseOffsetOffsets().begin(), 02301 E = Builder.getVBaseOffsetOffsets().end(); I != E; ++I) { 02302 // Insert all types. 02303 ClassPairTy ClassPair(RD, I->first); 02304 02305 VirtualBaseClassOffsetOffsets.insert( 02306 std::make_pair(ClassPair, I->second)); 02307 } 02308 02309 I = VirtualBaseClassOffsetOffsets.find(ClassPair); 02310 assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!"); 02311 02312 return I->second; 02313 } 02314 02315 static VTableLayout *CreateVTableLayout(const ItaniumVTableBuilder &Builder) { 02316 SmallVector<VTableLayout::VTableThunkTy, 1> 02317 VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end()); 02318 02319 return new VTableLayout(Builder.getNumVTableComponents(), 02320 Builder.vtable_component_begin(), 02321 VTableThunks.size(), 02322 VTableThunks.data(), 02323 Builder.getAddressPoints(), 02324 /*IsMicrosoftABI=*/false); 02325 } 02326 02327 void 02328 ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) { 02329 const VTableLayout *&Entry = VTableLayouts[RD]; 02330 02331 // Check if we've computed this information before. 02332 if (Entry) 02333 return; 02334 02335 ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(), 02336 /*MostDerivedClassIsVirtual=*/0, RD); 02337 Entry = CreateVTableLayout(Builder); 02338 02339 MethodVTableIndices.insert(Builder.vtable_indices_begin(), 02340 Builder.vtable_indices_end()); 02341 02342 // Add the known thunks. 02343 Thunks.insert(Builder.thunks_begin(), Builder.thunks_end()); 02344 02345 // If we don't have the vbase information for this class, insert it. 02346 // getVirtualBaseOffsetOffset will compute it separately without computing 02347 // the rest of the vtable related information. 02348 if (!RD->getNumVBases()) 02349 return; 02350 02351 const CXXRecordDecl *VBase = 02352 RD->vbases_begin()->getType()->getAsCXXRecordDecl(); 02353 02354 if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase))) 02355 return; 02356 02357 for (ItaniumVTableBuilder::VBaseOffsetOffsetsMapTy::const_iterator 02358 I = Builder.getVBaseOffsetOffsets().begin(), 02359 E = Builder.getVBaseOffsetOffsets().end(); 02360 I != E; ++I) { 02361 // Insert all types. 02362 ClassPairTy ClassPair(RD, I->first); 02363 02364 VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I->second)); 02365 } 02366 } 02367 02368 VTableLayout *ItaniumVTableContext::createConstructionVTableLayout( 02369 const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset, 02370 bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) { 02371 ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset, 02372 MostDerivedClassIsVirtual, LayoutClass); 02373 return CreateVTableLayout(Builder); 02374 } 02375 02376 namespace { 02377 02378 // Vtables in the Microsoft ABI are different from the Itanium ABI. 02379 // 02380 // The main differences are: 02381 // 1. Separate vftable and vbtable. 02382 // 02383 // 2. Each subobject with a vfptr gets its own vftable rather than an address 02384 // point in a single vtable shared between all the subobjects. 02385 // Each vftable is represented by a separate section and virtual calls 02386 // must be done using the vftable which has a slot for the function to be 02387 // called. 02388 // 02389 // 3. Virtual method definitions expect their 'this' parameter to point to the 02390 // first vfptr whose table provides a compatible overridden method. In many 02391 // cases, this permits the original vf-table entry to directly call 02392 // the method instead of passing through a thunk. 02393 // See example before VFTableBuilder::ComputeThisOffset below. 02394 // 02395 // A compatible overridden method is one which does not have a non-trivial 02396 // covariant-return adjustment. 02397 // 02398 // The first vfptr is the one with the lowest offset in the complete-object 02399 // layout of the defining class, and the method definition will subtract 02400 // that constant offset from the parameter value to get the real 'this' 02401 // value. Therefore, if the offset isn't really constant (e.g. if a virtual 02402 // function defined in a virtual base is overridden in a more derived 02403 // virtual base and these bases have a reverse order in the complete 02404 // object), the vf-table may require a this-adjustment thunk. 02405 // 02406 // 4. vftables do not contain new entries for overrides that merely require 02407 // this-adjustment. Together with #3, this keeps vf-tables smaller and 02408 // eliminates the need for this-adjustment thunks in many cases, at the cost 02409 // of often requiring redundant work to adjust the "this" pointer. 02410 // 02411 // 5. Instead of VTT and constructor vtables, vbtables and vtordisps are used. 02412 // Vtordisps are emitted into the class layout if a class has 02413 // a) a user-defined ctor/dtor 02414 // and 02415 // b) a method overriding a method in a virtual base. 02416 // 02417 // To get a better understanding of this code, 02418 // you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp 02419 02420 class VFTableBuilder { 02421 public: 02422 typedef MicrosoftVTableContext::MethodVFTableLocation MethodVFTableLocation; 02423 02424 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation> 02425 MethodVFTableLocationsTy; 02426 02427 typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator> 02428 method_locations_range; 02429 02430 private: 02431 /// VTables - Global vtable information. 02432 MicrosoftVTableContext &VTables; 02433 02434 /// Context - The ASTContext which we will use for layout information. 02435 ASTContext &Context; 02436 02437 /// MostDerivedClass - The most derived class for which we're building this 02438 /// vtable. 02439 const CXXRecordDecl *MostDerivedClass; 02440 02441 const ASTRecordLayout &MostDerivedClassLayout; 02442 02443 const VPtrInfo &WhichVFPtr; 02444 02445 /// FinalOverriders - The final overriders of the most derived class. 02446 const FinalOverriders Overriders; 02447 02448 /// Components - The components of the vftable being built. 02449 SmallVector<VTableComponent, 64> Components; 02450 02451 MethodVFTableLocationsTy MethodVFTableLocations; 02452 02453 /// \brief Does this class have an RTTI component? 02454 bool HasRTTIComponent; 02455 02456 /// MethodInfo - Contains information about a method in a vtable. 02457 /// (Used for computing 'this' pointer adjustment thunks. 02458 struct MethodInfo { 02459 /// VBTableIndex - The nonzero index in the vbtable that 02460 /// this method's base has, or zero. 02461 const uint64_t VBTableIndex; 02462 02463 /// VFTableIndex - The index in the vftable that this method has. 02464 const uint64_t VFTableIndex; 02465 02466 /// Shadowed - Indicates if this vftable slot is shadowed by 02467 /// a slot for a covariant-return override. If so, it shouldn't be printed 02468 /// or used for vcalls in the most derived class. 02469 bool Shadowed; 02470 02471 /// UsesExtraSlot - Indicates if this vftable slot was created because 02472 /// any of the overridden slots required a return adjusting thunk. 02473 bool UsesExtraSlot; 02474 02475 MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex, 02476 bool UsesExtraSlot = false) 02477 : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex), 02478 Shadowed(false), UsesExtraSlot(UsesExtraSlot) {} 02479 02480 MethodInfo() 02481 : VBTableIndex(0), VFTableIndex(0), Shadowed(false), 02482 UsesExtraSlot(false) {} 02483 }; 02484 02485 typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy; 02486 02487 /// MethodInfoMap - The information for all methods in the vftable we're 02488 /// currently building. 02489 MethodInfoMapTy MethodInfoMap; 02490 02491 typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy; 02492 02493 /// VTableThunks - The thunks by vftable index in the vftable currently being 02494 /// built. 02495 VTableThunksMapTy VTableThunks; 02496 02497 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy; 02498 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy; 02499 02500 /// Thunks - A map that contains all the thunks needed for all methods in the 02501 /// most derived class for which the vftable is currently being built. 02502 ThunksMapTy Thunks; 02503 02504 /// AddThunk - Add a thunk for the given method. 02505 void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) { 02506 SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD]; 02507 02508 // Check if we have this thunk already. 02509 if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) != 02510 ThunksVector.end()) 02511 return; 02512 02513 ThunksVector.push_back(Thunk); 02514 } 02515 02516 /// ComputeThisOffset - Returns the 'this' argument offset for the given 02517 /// method, relative to the beginning of the MostDerivedClass. 02518 CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider); 02519 02520 void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider, 02521 CharUnits ThisOffset, ThisAdjustment &TA); 02522 02523 /// AddMethod - Add a single virtual member function to the vftable 02524 /// components vector. 02525 void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) { 02526 if (!TI.isEmpty()) { 02527 VTableThunks[Components.size()] = TI; 02528 AddThunk(MD, TI); 02529 } 02530 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 02531 assert(TI.Return.isEmpty() && 02532 "Destructor can't have return adjustment!"); 02533 Components.push_back(VTableComponent::MakeDeletingDtor(DD)); 02534 } else { 02535 Components.push_back(VTableComponent::MakeFunction(MD)); 02536 } 02537 } 02538 02539 /// AddMethods - Add the methods of this base subobject and the relevant 02540 /// subbases to the vftable we're currently laying out. 02541 void AddMethods(BaseSubobject Base, unsigned BaseDepth, 02542 const CXXRecordDecl *LastVBase, 02543 BasesSetVectorTy &VisitedBases); 02544 02545 void LayoutVFTable() { 02546 // RTTI data goes before all other entries. 02547 if (HasRTTIComponent) 02548 Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass)); 02549 02550 BasesSetVectorTy VisitedBases; 02551 AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr, 02552 VisitedBases); 02553 assert((HasRTTIComponent ? Components.size() - 1 : Components.size()) && 02554 "vftable can't be empty"); 02555 02556 assert(MethodVFTableLocations.empty()); 02557 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(), 02558 E = MethodInfoMap.end(); I != E; ++I) { 02559 const CXXMethodDecl *MD = I->first; 02560 const MethodInfo &MI = I->second; 02561 // Skip the methods that the MostDerivedClass didn't override 02562 // and the entries shadowed by return adjusting thunks. 02563 if (MD->getParent() != MostDerivedClass || MI.Shadowed) 02564 continue; 02565 MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(), 02566 WhichVFPtr.NonVirtualOffset, MI.VFTableIndex); 02567 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) { 02568 MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc; 02569 } else { 02570 MethodVFTableLocations[MD] = Loc; 02571 } 02572 } 02573 } 02574 02575 public: 02576 VFTableBuilder(MicrosoftVTableContext &VTables, 02577 const CXXRecordDecl *MostDerivedClass, const VPtrInfo *Which) 02578 : VTables(VTables), 02579 Context(MostDerivedClass->getASTContext()), 02580 MostDerivedClass(MostDerivedClass), 02581 MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)), 02582 WhichVFPtr(*Which), 02583 Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) { 02584 // Only include the RTTI component if we know that we will provide a 02585 // definition of the vftable. 02586 HasRTTIComponent = Context.getLangOpts().RTTIData && 02587 !MostDerivedClass->hasAttr<DLLImportAttr>(); 02588 02589 LayoutVFTable(); 02590 02591 if (Context.getLangOpts().DumpVTableLayouts) 02592 dumpLayout(llvm::outs()); 02593 } 02594 02595 uint64_t getNumThunks() const { return Thunks.size(); } 02596 02597 ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); } 02598 02599 ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); } 02600 02601 method_locations_range vtable_locations() const { 02602 return method_locations_range(MethodVFTableLocations.begin(), 02603 MethodVFTableLocations.end()); 02604 } 02605 02606 uint64_t getNumVTableComponents() const { return Components.size(); } 02607 02608 const VTableComponent *vtable_component_begin() const { 02609 return Components.begin(); 02610 } 02611 02612 const VTableComponent *vtable_component_end() const { 02613 return Components.end(); 02614 } 02615 02616 VTableThunksMapTy::const_iterator vtable_thunks_begin() const { 02617 return VTableThunks.begin(); 02618 } 02619 02620 VTableThunksMapTy::const_iterator vtable_thunks_end() const { 02621 return VTableThunks.end(); 02622 } 02623 02624 void dumpLayout(raw_ostream &); 02625 }; 02626 02627 } // end namespace 02628 02629 /// InitialOverriddenDefinitionCollector - Finds the set of least derived bases 02630 /// that define the given method. 02631 struct InitialOverriddenDefinitionCollector { 02632 BasesSetVectorTy Bases; 02633 OverriddenMethodsSetTy VisitedOverriddenMethods; 02634 02635 bool visit(const CXXMethodDecl *OverriddenMD) { 02636 if (OverriddenMD->size_overridden_methods() == 0) 02637 Bases.insert(OverriddenMD->getParent()); 02638 // Don't recurse on this method if we've already collected it. 02639 return VisitedOverriddenMethods.insert(OverriddenMD); 02640 } 02641 }; 02642 02643 static bool BaseInSet(const CXXBaseSpecifier *Specifier, 02644 CXXBasePath &Path, void *BasesSet) { 02645 BasesSetVectorTy *Bases = (BasesSetVectorTy *)BasesSet; 02646 return Bases->count(Specifier->getType()->getAsCXXRecordDecl()); 02647 } 02648 02649 // Let's study one class hierarchy as an example: 02650 // struct A { 02651 // virtual void f(); 02652 // int x; 02653 // }; 02654 // 02655 // struct B : virtual A { 02656 // virtual void f(); 02657 // }; 02658 // 02659 // Record layouts: 02660 // struct A: 02661 // 0 | (A vftable pointer) 02662 // 4 | int x 02663 // 02664 // struct B: 02665 // 0 | (B vbtable pointer) 02666 // 4 | struct A (virtual base) 02667 // 4 | (A vftable pointer) 02668 // 8 | int x 02669 // 02670 // Let's assume we have a pointer to the A part of an object of dynamic type B: 02671 // B b; 02672 // A *a = (A*)&b; 02673 // a->f(); 02674 // 02675 // In this hierarchy, f() belongs to the vftable of A, so B::f() expects 02676 // "this" parameter to point at the A subobject, which is B+4. 02677 // In the B::f() prologue, it adjusts "this" back to B by subtracting 4, 02678 // peformed as a *static* adjustment. 02679 // 02680 // Interesting thing happens when we alter the relative placement of A and B 02681 // subobjects in a class: 02682 // struct C : virtual B { }; 02683 // 02684 // C c; 02685 // A *a = (A*)&c; 02686 // a->f(); 02687 // 02688 // Respective record layout is: 02689 // 0 | (C vbtable pointer) 02690 // 4 | struct A (virtual base) 02691 // 4 | (A vftable pointer) 02692 // 8 | int x 02693 // 12 | struct B (virtual base) 02694 // 12 | (B vbtable pointer) 02695 // 02696 // The final overrider of f() in class C is still B::f(), so B+4 should be 02697 // passed as "this" to that code. However, "a" points at B-8, so the respective 02698 // vftable entry should hold a thunk that adds 12 to the "this" argument before 02699 // performing a tail call to B::f(). 02700 // 02701 // With this example in mind, we can now calculate the 'this' argument offset 02702 // for the given method, relative to the beginning of the MostDerivedClass. 02703 CharUnits 02704 VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) { 02705 InitialOverriddenDefinitionCollector Collector; 02706 visitAllOverriddenMethods(Overrider.Method, Collector); 02707 02708 // If there are no overrides then 'this' is located 02709 // in the base that defines the method. 02710 if (Collector.Bases.size() == 0) 02711 return Overrider.Offset; 02712 02713 CXXBasePaths Paths; 02714 Overrider.Method->getParent()->lookupInBases(BaseInSet, &Collector.Bases, 02715 Paths); 02716 02717 // This will hold the smallest this offset among overridees of MD. 02718 // This implies that an offset of a non-virtual base will dominate an offset 02719 // of a virtual base to potentially reduce the number of thunks required 02720 // in the derived classes that inherit this method. 02721 CharUnits Ret; 02722 bool First = true; 02723 02724 const ASTRecordLayout &OverriderRDLayout = 02725 Context.getASTRecordLayout(Overrider.Method->getParent()); 02726 for (CXXBasePaths::paths_iterator I = Paths.begin(), E = Paths.end(); 02727 I != E; ++I) { 02728 const CXXBasePath &Path = (*I); 02729 CharUnits ThisOffset = Overrider.Offset; 02730 CharUnits LastVBaseOffset; 02731 02732 // For each path from the overrider to the parents of the overridden methods, 02733 // traverse the path, calculating the this offset in the most derived class. 02734 for (int J = 0, F = Path.size(); J != F; ++J) { 02735 const CXXBasePathElement &Element = Path[J]; 02736 QualType CurTy = Element.Base->getType(); 02737 const CXXRecordDecl *PrevRD = Element.Class, 02738 *CurRD = CurTy->getAsCXXRecordDecl(); 02739 const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD); 02740 02741 if (Element.Base->isVirtual()) { 02742 // The interesting things begin when you have virtual inheritance. 02743 // The final overrider will use a static adjustment equal to the offset 02744 // of the vbase in the final overrider class. 02745 // For example, if the final overrider is in a vbase B of the most 02746 // derived class and it overrides a method of the B's own vbase A, 02747 // it uses A* as "this". In its prologue, it can cast A* to B* with 02748 // a static offset. This offset is used regardless of the actual 02749 // offset of A from B in the most derived class, requiring an 02750 // this-adjusting thunk in the vftable if A and B are laid out 02751 // differently in the most derived class. 02752 LastVBaseOffset = ThisOffset = 02753 Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD); 02754 } else { 02755 ThisOffset += Layout.getBaseClassOffset(CurRD); 02756 } 02757 } 02758 02759 if (isa<CXXDestructorDecl>(Overrider.Method)) { 02760 if (LastVBaseOffset.isZero()) { 02761 // If a "Base" class has at least one non-virtual base with a virtual 02762 // destructor, the "Base" virtual destructor will take the address 02763 // of the "Base" subobject as the "this" argument. 02764 ThisOffset = Overrider.Offset; 02765 } else { 02766 // A virtual destructor of a virtual base takes the address of the 02767 // virtual base subobject as the "this" argument. 02768 ThisOffset = LastVBaseOffset; 02769 } 02770 } 02771 02772 if (Ret > ThisOffset || First) { 02773 First = false; 02774 Ret = ThisOffset; 02775 } 02776 } 02777 02778 assert(!First && "Method not found in the given subobject?"); 02779 return Ret; 02780 } 02781 02782 // Things are getting even more complex when the "this" adjustment has to 02783 // use a dynamic offset instead of a static one, or even two dynamic offsets. 02784 // This is sometimes required when a virtual call happens in the middle of 02785 // a non-most-derived class construction or destruction. 02786 // 02787 // Let's take a look at the following example: 02788 // struct A { 02789 // virtual void f(); 02790 // }; 02791 // 02792 // void foo(A *a) { a->f(); } // Knows nothing about siblings of A. 02793 // 02794 // struct B : virtual A { 02795 // virtual void f(); 02796 // B() { 02797 // foo(this); 02798 // } 02799 // }; 02800 // 02801 // struct C : virtual B { 02802 // virtual void f(); 02803 // }; 02804 // 02805 // Record layouts for these classes are: 02806 // struct A 02807 // 0 | (A vftable pointer) 02808 // 02809 // struct B 02810 // 0 | (B vbtable pointer) 02811 // 4 | (vtordisp for vbase A) 02812 // 8 | struct A (virtual base) 02813 // 8 | (A vftable pointer) 02814 // 02815 // struct C 02816 // 0 | (C vbtable pointer) 02817 // 4 | (vtordisp for vbase A) 02818 // 8 | struct A (virtual base) // A precedes B! 02819 // 8 | (A vftable pointer) 02820 // 12 | struct B (virtual base) 02821 // 12 | (B vbtable pointer) 02822 // 02823 // When one creates an object of type C, the C constructor: 02824 // - initializes all the vbptrs, then 02825 // - calls the A subobject constructor 02826 // (initializes A's vfptr with an address of A vftable), then 02827 // - calls the B subobject constructor 02828 // (initializes A's vfptr with an address of B vftable and vtordisp for A), 02829 // that in turn calls foo(), then 02830 // - initializes A's vfptr with an address of C vftable and zeroes out the 02831 // vtordisp 02832 // FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable 02833 // without vtordisp thunks? 02834 // FIXME: how are vtordisp handled in the presence of nooverride/final? 02835 // 02836 // When foo() is called, an object with a layout of class C has a vftable 02837 // referencing B::f() that assumes a B layout, so the "this" adjustments are 02838 // incorrect, unless an extra adjustment is done. This adjustment is called 02839 // "vtordisp adjustment". Vtordisp basically holds the difference between the 02840 // actual location of a vbase in the layout class and the location assumed by 02841 // the vftable of the class being constructed/destructed. Vtordisp is only 02842 // needed if "this" escapes a 02843 // structor (or we can't prove otherwise). 02844 // [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an 02845 // estimation of a dynamic adjustment] 02846 // 02847 // foo() gets a pointer to the A vbase and doesn't know anything about B or C, 02848 // so it just passes that pointer as "this" in a virtual call. 02849 // If there was no vtordisp, that would just dispatch to B::f(). 02850 // However, B::f() assumes B+8 is passed as "this", 02851 // yet the pointer foo() passes along is B-4 (i.e. C+8). 02852 // An extra adjustment is needed, so we emit a thunk into the B vftable. 02853 // This vtordisp thunk subtracts the value of vtordisp 02854 // from the "this" argument (-12) before making a tailcall to B::f(). 02855 // 02856 // Let's consider an even more complex example: 02857 // struct D : virtual B, virtual C { 02858 // D() { 02859 // foo(this); 02860 // } 02861 // }; 02862 // 02863 // struct D 02864 // 0 | (D vbtable pointer) 02865 // 4 | (vtordisp for vbase A) 02866 // 8 | struct A (virtual base) // A precedes both B and C! 02867 // 8 | (A vftable pointer) 02868 // 12 | struct B (virtual base) // B precedes C! 02869 // 12 | (B vbtable pointer) 02870 // 16 | struct C (virtual base) 02871 // 16 | (C vbtable pointer) 02872 // 02873 // When D::D() calls foo(), we find ourselves in a thunk that should tailcall 02874 // to C::f(), which assumes C+8 as its "this" parameter. This time, foo() 02875 // passes along A, which is C-8. The A vtordisp holds 02876 // "D.vbptr[index_of_A] - offset_of_A_in_D" 02877 // and we statically know offset_of_A_in_D, so can get a pointer to D. 02878 // When we know it, we can make an extra vbtable lookup to locate the C vbase 02879 // and one extra static adjustment to calculate the expected value of C+8. 02880 void VFTableBuilder::CalculateVtordispAdjustment( 02881 FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset, 02882 ThisAdjustment &TA) { 02883 const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap = 02884 MostDerivedClassLayout.getVBaseOffsetsMap(); 02885 const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry = 02886 VBaseMap.find(WhichVFPtr.getVBaseWithVPtr()); 02887 assert(VBaseMapEntry != VBaseMap.end()); 02888 02889 // If there's no vtordisp or the final overrider is defined in the same vbase 02890 // as the initial declaration, we don't need any vtordisp adjustment. 02891 if (!VBaseMapEntry->second.hasVtorDisp() || 02892 Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr()) 02893 return; 02894 02895 // OK, now we know we need to use a vtordisp thunk. 02896 // The implicit vtordisp field is located right before the vbase. 02897 CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset; 02898 TA.Virtual.Microsoft.VtordispOffset = 02899 (OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4; 02900 02901 // A simple vtordisp thunk will suffice if the final overrider is defined 02902 // in either the most derived class or its non-virtual base. 02903 if (Overrider.Method->getParent() == MostDerivedClass || 02904 !Overrider.VirtualBase) 02905 return; 02906 02907 // Otherwise, we need to do use the dynamic offset of the final overrider 02908 // in order to get "this" adjustment right. 02909 TA.Virtual.Microsoft.VBPtrOffset = 02910 (OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset - 02911 MostDerivedClassLayout.getVBPtrOffset()).getQuantity(); 02912 TA.Virtual.Microsoft.VBOffsetOffset = 02913 Context.getTypeSizeInChars(Context.IntTy).getQuantity() * 02914 VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase); 02915 02916 TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity(); 02917 } 02918 02919 static void GroupNewVirtualOverloads( 02920 const CXXRecordDecl *RD, 02921 SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) { 02922 // Put the virtual methods into VirtualMethods in the proper order: 02923 // 1) Group overloads by declaration name. New groups are added to the 02924 // vftable in the order of their first declarations in this class 02925 // (including overrides and non-virtual methods). 02926 // 2) In each group, new overloads appear in the reverse order of declaration. 02927 typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup; 02928 SmallVector<MethodGroup, 10> Groups; 02929 typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy; 02930 VisitedGroupIndicesTy VisitedGroupIndices; 02931 for (const auto *MD : RD->methods()) { 02932 VisitedGroupIndicesTy::iterator J; 02933 bool Inserted; 02934 std::tie(J, Inserted) = VisitedGroupIndices.insert( 02935 std::make_pair(MD->getDeclName(), Groups.size())); 02936 if (Inserted) 02937 Groups.push_back(MethodGroup()); 02938 if (MD->isVirtual()) 02939 Groups[J->second].push_back(MD); 02940 } 02941 02942 for (unsigned I = 0, E = Groups.size(); I != E; ++I) 02943 VirtualMethods.append(Groups[I].rbegin(), Groups[I].rend()); 02944 } 02945 02946 static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) { 02947 for (const auto &B : RD->bases()) { 02948 if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base) 02949 return true; 02950 } 02951 return false; 02952 } 02953 02954 void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth, 02955 const CXXRecordDecl *LastVBase, 02956 BasesSetVectorTy &VisitedBases) { 02957 const CXXRecordDecl *RD = Base.getBase(); 02958 if (!RD->isPolymorphic()) 02959 return; 02960 02961 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 02962 02963 // See if this class expands a vftable of the base we look at, which is either 02964 // the one defined by the vfptr base path or the primary base of the current class. 02965 const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase; 02966 CharUnits NextBaseOffset; 02967 if (BaseDepth < WhichVFPtr.PathToBaseWithVPtr.size()) { 02968 NextBase = WhichVFPtr.PathToBaseWithVPtr[BaseDepth]; 02969 if (isDirectVBase(NextBase, RD)) { 02970 NextLastVBase = NextBase; 02971 NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase); 02972 } else { 02973 NextBaseOffset = 02974 Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase); 02975 } 02976 } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { 02977 assert(!Layout.isPrimaryBaseVirtual() && 02978 "No primary virtual bases in this ABI"); 02979 NextBase = PrimaryBase; 02980 NextBaseOffset = Base.getBaseOffset(); 02981 } 02982 02983 if (NextBase) { 02984 AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1, 02985 NextLastVBase, VisitedBases); 02986 if (!VisitedBases.insert(NextBase)) 02987 llvm_unreachable("Found a duplicate primary base!"); 02988 } 02989 02990 SmallVector<const CXXMethodDecl*, 10> VirtualMethods; 02991 // Put virtual methods in the proper order. 02992 GroupNewVirtualOverloads(RD, VirtualMethods); 02993 02994 // Now go through all virtual member functions and add them to the current 02995 // vftable. This is done by 02996 // - replacing overridden methods in their existing slots, as long as they 02997 // don't require return adjustment; calculating This adjustment if needed. 02998 // - adding new slots for methods of the current base not present in any 02999 // sub-bases; 03000 // - adding new slots for methods that require Return adjustment. 03001 // We keep track of the methods visited in the sub-bases in MethodInfoMap. 03002 for (unsigned I = 0, E = VirtualMethods.size(); I != E; ++I) { 03003 const CXXMethodDecl *MD = VirtualMethods[I]; 03004 03005 FinalOverriders::OverriderInfo FinalOverrider = 03006 Overriders.getOverrider(MD, Base.getBaseOffset()); 03007 const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method; 03008 const CXXMethodDecl *OverriddenMD = 03009 FindNearestOverriddenMethod(MD, VisitedBases); 03010 03011 ThisAdjustment ThisAdjustmentOffset; 03012 bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false; 03013 CharUnits ThisOffset = ComputeThisOffset(FinalOverrider); 03014 ThisAdjustmentOffset.NonVirtual = 03015 (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity(); 03016 if ((OverriddenMD || FinalOverriderMD != MD) && 03017 WhichVFPtr.getVBaseWithVPtr()) 03018 CalculateVtordispAdjustment(FinalOverrider, ThisOffset, 03019 ThisAdjustmentOffset); 03020 03021 if (OverriddenMD) { 03022 // If MD overrides anything in this vftable, we need to update the entries. 03023 MethodInfoMapTy::iterator OverriddenMDIterator = 03024 MethodInfoMap.find(OverriddenMD); 03025 03026 // If the overridden method went to a different vftable, skip it. 03027 if (OverriddenMDIterator == MethodInfoMap.end()) 03028 continue; 03029 03030 MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second; 03031 03032 // Let's check if the overrider requires any return adjustments. 03033 // We must create a new slot if the MD's return type is not trivially 03034 // convertible to the OverriddenMD's one. 03035 // Once a chain of method overrides adds a return adjusting vftable slot, 03036 // all subsequent overrides will also use an extra method slot. 03037 ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset( 03038 Context, MD, OverriddenMD).isEmpty() || 03039 OverriddenMethodInfo.UsesExtraSlot; 03040 03041 if (!ReturnAdjustingThunk) { 03042 // No return adjustment needed - just replace the overridden method info 03043 // with the current info. 03044 MethodInfo MI(OverriddenMethodInfo.VBTableIndex, 03045 OverriddenMethodInfo.VFTableIndex); 03046 MethodInfoMap.erase(OverriddenMDIterator); 03047 03048 assert(!MethodInfoMap.count(MD) && 03049 "Should not have method info for this method yet!"); 03050 MethodInfoMap.insert(std::make_pair(MD, MI)); 03051 continue; 03052 } 03053 03054 // In case we need a return adjustment, we'll add a new slot for 03055 // the overrider. Mark the overriden method as shadowed by the new slot. 03056 OverriddenMethodInfo.Shadowed = true; 03057 03058 // Force a special name mangling for a return-adjusting thunk 03059 // unless the method is the final overrider without this adjustment. 03060 ForceReturnAdjustmentMangling = 03061 !(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty()); 03062 } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC || 03063 MD->size_overridden_methods()) { 03064 // Skip methods that don't belong to the vftable of the current class, 03065 // e.g. each method that wasn't seen in any of the visited sub-bases 03066 // but overrides multiple methods of other sub-bases. 03067 continue; 03068 } 03069 03070 // If we got here, MD is a method not seen in any of the sub-bases or 03071 // it requires return adjustment. Insert the method info for this method. 03072 unsigned VBIndex = 03073 LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0; 03074 MethodInfo MI(VBIndex, 03075 HasRTTIComponent ? Components.size() - 1 : Components.size(), 03076 ReturnAdjustingThunk); 03077 03078 assert(!MethodInfoMap.count(MD) && 03079 "Should not have method info for this method yet!"); 03080 MethodInfoMap.insert(std::make_pair(MD, MI)); 03081 03082 // Check if this overrider needs a return adjustment. 03083 // We don't want to do this for pure virtual member functions. 03084 BaseOffset ReturnAdjustmentOffset; 03085 ReturnAdjustment ReturnAdjustment; 03086 if (!FinalOverriderMD->isPure()) { 03087 ReturnAdjustmentOffset = 03088 ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD); 03089 } 03090 if (!ReturnAdjustmentOffset.isEmpty()) { 03091 ForceReturnAdjustmentMangling = true; 03092 ReturnAdjustment.NonVirtual = 03093 ReturnAdjustmentOffset.NonVirtualOffset.getQuantity(); 03094 if (ReturnAdjustmentOffset.VirtualBase) { 03095 const ASTRecordLayout &DerivedLayout = 03096 Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass); 03097 ReturnAdjustment.Virtual.Microsoft.VBPtrOffset = 03098 DerivedLayout.getVBPtrOffset().getQuantity(); 03099 ReturnAdjustment.Virtual.Microsoft.VBIndex = 03100 VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass, 03101 ReturnAdjustmentOffset.VirtualBase); 03102 } 03103 } 03104 03105 AddMethod(FinalOverriderMD, 03106 ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment, 03107 ForceReturnAdjustmentMangling ? MD : nullptr)); 03108 } 03109 } 03110 03111 static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) { 03112 for (VPtrInfo::BasePath::const_reverse_iterator I = Path.rbegin(), 03113 E = Path.rend(); I != E; ++I) { 03114 Out << "'"; 03115 (*I)->printQualifiedName(Out); 03116 Out << "' in "; 03117 } 03118 } 03119 03120 static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out, 03121 bool ContinueFirstLine) { 03122 const ReturnAdjustment &R = TI.Return; 03123 bool Multiline = false; 03124 const char *LinePrefix = "\n "; 03125 if (!R.isEmpty() || TI.Method) { 03126 if (!ContinueFirstLine) 03127 Out << LinePrefix; 03128 Out << "[return adjustment (to type '" 03129 << TI.Method->getReturnType().getCanonicalType().getAsString() 03130 << "'): "; 03131 if (R.Virtual.Microsoft.VBPtrOffset) 03132 Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", "; 03133 if (R.Virtual.Microsoft.VBIndex) 03134 Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", "; 03135 Out << R.NonVirtual << " non-virtual]"; 03136 Multiline = true; 03137 } 03138 03139 const ThisAdjustment &T = TI.This; 03140 if (!T.isEmpty()) { 03141 if (Multiline || !ContinueFirstLine) 03142 Out << LinePrefix; 03143 Out << "[this adjustment: "; 03144 if (!TI.This.Virtual.isEmpty()) { 03145 assert(T.Virtual.Microsoft.VtordispOffset < 0); 03146 Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", "; 03147 if (T.Virtual.Microsoft.VBPtrOffset) { 03148 Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset 03149 << " to the left,"; 03150 assert(T.Virtual.Microsoft.VBOffsetOffset > 0); 03151 Out << LinePrefix << " vboffset at " 03152 << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, "; 03153 } 03154 } 03155 Out << T.NonVirtual << " non-virtual]"; 03156 } 03157 } 03158 03159 void VFTableBuilder::dumpLayout(raw_ostream &Out) { 03160 Out << "VFTable for "; 03161 PrintBasePath(WhichVFPtr.PathToBaseWithVPtr, Out); 03162 Out << "'"; 03163 MostDerivedClass->printQualifiedName(Out); 03164 Out << "' (" << Components.size() 03165 << (Components.size() == 1 ? " entry" : " entries") << ").\n"; 03166 03167 for (unsigned I = 0, E = Components.size(); I != E; ++I) { 03168 Out << llvm::format("%4d | ", I); 03169 03170 const VTableComponent &Component = Components[I]; 03171 03172 // Dump the component. 03173 switch (Component.getKind()) { 03174 case VTableComponent::CK_RTTI: 03175 Component.getRTTIDecl()->printQualifiedName(Out); 03176 Out << " RTTI"; 03177 break; 03178 03179 case VTableComponent::CK_FunctionPointer: { 03180 const CXXMethodDecl *MD = Component.getFunctionDecl(); 03181 03182 // FIXME: Figure out how to print the real thunk type, since they can 03183 // differ in the return type. 03184 std::string Str = PredefinedExpr::ComputeName( 03185 PredefinedExpr::PrettyFunctionNoVirtual, MD); 03186 Out << Str; 03187 if (MD->isPure()) 03188 Out << " [pure]"; 03189 03190 if (MD->isDeleted()) 03191 Out << " [deleted]"; 03192 03193 ThunkInfo Thunk = VTableThunks.lookup(I); 03194 if (!Thunk.isEmpty()) 03195 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false); 03196 03197 break; 03198 } 03199 03200 case VTableComponent::CK_DeletingDtorPointer: { 03201 const CXXDestructorDecl *DD = Component.getDestructorDecl(); 03202 03203 DD->printQualifiedName(Out); 03204 Out << "() [scalar deleting]"; 03205 03206 if (DD->isPure()) 03207 Out << " [pure]"; 03208 03209 ThunkInfo Thunk = VTableThunks.lookup(I); 03210 if (!Thunk.isEmpty()) { 03211 assert(Thunk.Return.isEmpty() && 03212 "No return adjustment needed for destructors!"); 03213 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false); 03214 } 03215 03216 break; 03217 } 03218 03219 default: 03220 DiagnosticsEngine &Diags = Context.getDiagnostics(); 03221 unsigned DiagID = Diags.getCustomDiagID( 03222 DiagnosticsEngine::Error, 03223 "Unexpected vftable component type %0 for component number %1"); 03224 Diags.Report(MostDerivedClass->getLocation(), DiagID) 03225 << I << Component.getKind(); 03226 } 03227 03228 Out << '\n'; 03229 } 03230 03231 Out << '\n'; 03232 03233 if (!Thunks.empty()) { 03234 // We store the method names in a map to get a stable order. 03235 std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls; 03236 03237 for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end(); 03238 I != E; ++I) { 03239 const CXXMethodDecl *MD = I->first; 03240 std::string MethodName = PredefinedExpr::ComputeName( 03241 PredefinedExpr::PrettyFunctionNoVirtual, MD); 03242 03243 MethodNamesAndDecls.insert(std::make_pair(MethodName, MD)); 03244 } 03245 03246 for (std::map<std::string, const CXXMethodDecl *>::const_iterator 03247 I = MethodNamesAndDecls.begin(), 03248 E = MethodNamesAndDecls.end(); 03249 I != E; ++I) { 03250 const std::string &MethodName = I->first; 03251 const CXXMethodDecl *MD = I->second; 03252 03253 ThunkInfoVectorTy ThunksVector = Thunks[MD]; 03254 std::stable_sort(ThunksVector.begin(), ThunksVector.end(), 03255 [](const ThunkInfo &LHS, const ThunkInfo &RHS) { 03256 // Keep different thunks with the same adjustments in the order they 03257 // were put into the vector. 03258 return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return); 03259 }); 03260 03261 Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size(); 03262 Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n"; 03263 03264 for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) { 03265 const ThunkInfo &Thunk = ThunksVector[I]; 03266 03267 Out << llvm::format("%4d | ", I); 03268 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true); 03269 Out << '\n'; 03270 } 03271 03272 Out << '\n'; 03273 } 03274 } 03275 03276 Out.flush(); 03277 } 03278 03279 static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A, 03280 ArrayRef<const CXXRecordDecl *> B) { 03281 for (ArrayRef<const CXXRecordDecl *>::iterator I = B.begin(), E = B.end(); 03282 I != E; ++I) { 03283 if (A.count(*I)) 03284 return true; 03285 } 03286 return false; 03287 } 03288 03289 static bool rebucketPaths(VPtrInfoVector &Paths); 03290 03291 /// Produces MSVC-compatible vbtable data. The symbols produced by this 03292 /// algorithm match those produced by MSVC 2012 and newer, which is different 03293 /// from MSVC 2010. 03294 /// 03295 /// MSVC 2012 appears to minimize the vbtable names using the following 03296 /// algorithm. First, walk the class hierarchy in the usual order, depth first, 03297 /// left to right, to find all of the subobjects which contain a vbptr field. 03298 /// Visiting each class node yields a list of inheritance paths to vbptrs. Each 03299 /// record with a vbptr creates an initially empty path. 03300 /// 03301 /// To combine paths from child nodes, the paths are compared to check for 03302 /// ambiguity. Paths are "ambiguous" if multiple paths have the same set of 03303 /// components in the same order. Each group of ambiguous paths is extended by 03304 /// appending the class of the base from which it came. If the current class 03305 /// node produced an ambiguous path, its path is extended with the current class. 03306 /// After extending paths, MSVC again checks for ambiguity, and extends any 03307 /// ambiguous path which wasn't already extended. Because each node yields an 03308 /// unambiguous set of paths, MSVC doesn't need to extend any path more than once 03309 /// to produce an unambiguous set of paths. 03310 /// 03311 /// TODO: Presumably vftables use the same algorithm. 03312 void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables, 03313 const CXXRecordDecl *RD, 03314 VPtrInfoVector &Paths) { 03315 assert(Paths.empty()); 03316 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 03317 03318 // Base case: this subobject has its own vptr. 03319 if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr()) 03320 Paths.push_back(new VPtrInfo(RD)); 03321 03322 // Recursive case: get all the vbtables from our bases and remove anything 03323 // that shares a virtual base. 03324 llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen; 03325 for (const auto &B : RD->bases()) { 03326 const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl(); 03327 if (B.isVirtual() && VBasesSeen.count(Base)) 03328 continue; 03329 03330 if (!Base->isDynamicClass()) 03331 continue; 03332 03333 const VPtrInfoVector &BasePaths = 03334 ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base); 03335 03336 for (VPtrInfo *BaseInfo : BasePaths) { 03337 // Don't include the path if it goes through a virtual base that we've 03338 // already included. 03339 if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases)) 03340 continue; 03341 03342 // Copy the path and adjust it as necessary. 03343 VPtrInfo *P = new VPtrInfo(*BaseInfo); 03344 03345 // We mangle Base into the path if the path would've been ambiguous and it 03346 // wasn't already extended with Base. 03347 if (P->MangledPath.empty() || P->MangledPath.back() != Base) 03348 P->NextBaseToMangle = Base; 03349 03350 // Keep track of which vtable the derived class is going to extend with 03351 // new methods or bases. We append to either the vftable of our primary 03352 // base, or the first non-virtual base that has a vbtable. 03353 if (P->ReusingBase == Base && 03354 Base == (ForVBTables ? Layout.getBaseSharingVBPtr() 03355 : Layout.getPrimaryBase())) 03356 P->ReusingBase = RD; 03357 03358 // Keep track of the full adjustment from the MDC to this vtable. The 03359 // adjustment is captured by an optional vbase and a non-virtual offset. 03360 if (B.isVirtual()) 03361 P->ContainingVBases.push_back(Base); 03362 else if (P->ContainingVBases.empty()) 03363 P->NonVirtualOffset += Layout.getBaseClassOffset(Base); 03364 03365 // Update the full offset in the MDC. 03366 P->FullOffsetInMDC = P->NonVirtualOffset; 03367 if (const CXXRecordDecl *VB = P->getVBaseWithVPtr()) 03368 P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB); 03369 03370 Paths.push_back(P); 03371 } 03372 03373 if (B.isVirtual()) 03374 VBasesSeen.insert(Base); 03375 03376 // After visiting any direct base, we've transitively visited all of its 03377 // morally virtual bases. 03378 for (const auto &VB : Base->vbases()) 03379 VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl()); 03380 } 03381 03382 // Sort the paths into buckets, and if any of them are ambiguous, extend all 03383 // paths in ambiguous buckets. 03384 bool Changed = true; 03385 while (Changed) 03386 Changed = rebucketPaths(Paths); 03387 } 03388 03389 static bool extendPath(VPtrInfo *P) { 03390 if (P->NextBaseToMangle) { 03391 P->MangledPath.push_back(P->NextBaseToMangle); 03392 P->NextBaseToMangle = nullptr;// Prevent the path from being extended twice. 03393 return true; 03394 } 03395 return false; 03396 } 03397 03398 static bool rebucketPaths(VPtrInfoVector &Paths) { 03399 // What we're essentially doing here is bucketing together ambiguous paths. 03400 // Any bucket with more than one path in it gets extended by NextBase, which 03401 // is usually the direct base of the inherited the vbptr. This code uses a 03402 // sorted vector to implement a multiset to form the buckets. Note that the 03403 // ordering is based on pointers, but it doesn't change our output order. The 03404 // current algorithm is designed to match MSVC 2012's names. 03405 VPtrInfoVector PathsSorted(Paths); 03406 std::sort(PathsSorted.begin(), PathsSorted.end(), 03407 [](const VPtrInfo *LHS, const VPtrInfo *RHS) { 03408 return LHS->MangledPath < RHS->MangledPath; 03409 }); 03410 bool Changed = false; 03411 for (size_t I = 0, E = PathsSorted.size(); I != E;) { 03412 // Scan forward to find the end of the bucket. 03413 size_t BucketStart = I; 03414 do { 03415 ++I; 03416 } while (I != E && PathsSorted[BucketStart]->MangledPath == 03417 PathsSorted[I]->MangledPath); 03418 03419 // If this bucket has multiple paths, extend them all. 03420 if (I - BucketStart > 1) { 03421 for (size_t II = BucketStart; II != I; ++II) 03422 Changed |= extendPath(PathsSorted[II]); 03423 assert(Changed && "no paths were extended to fix ambiguity"); 03424 } 03425 } 03426 return Changed; 03427 } 03428 03429 MicrosoftVTableContext::~MicrosoftVTableContext() { 03430 for (auto &P : VFPtrLocations) 03431 llvm::DeleteContainerPointers(*P.second); 03432 llvm::DeleteContainerSeconds(VFPtrLocations); 03433 llvm::DeleteContainerSeconds(VFTableLayouts); 03434 llvm::DeleteContainerSeconds(VBaseInfo); 03435 } 03436 03437 static bool 03438 findPathForVPtr(ASTContext &Context, const ASTRecordLayout &MostDerivedLayout, 03439 const CXXRecordDecl *RD, CharUnits Offset, 03440 llvm::SmallPtrSetImpl<const CXXRecordDecl *> &VBasesSeen, 03441 VPtrInfo::BasePath &FullPath, VPtrInfo *Info) { 03442 if (RD == Info->BaseWithVPtr && Offset == Info->FullOffsetInMDC) { 03443 Info->PathToBaseWithVPtr = FullPath; 03444 return true; 03445 } 03446 03447 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 03448 03449 // Recurse with non-virtual bases first. 03450 // FIXME: Does this need to be in layout order? Virtual bases will be in base 03451 // specifier order, which isn't necessarily layout order. 03452 SmallVector<CXXBaseSpecifier, 4> Bases(RD->bases_begin(), RD->bases_end()); 03453 std::stable_partition(Bases.begin(), Bases.end(), 03454 [](CXXBaseSpecifier bs) { return !bs.isVirtual(); }); 03455 03456 for (const auto &B : Bases) { 03457 const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl(); 03458 CharUnits NewOffset; 03459 if (!B.isVirtual()) 03460 NewOffset = Offset + Layout.getBaseClassOffset(Base); 03461 else { 03462 if (!VBasesSeen.insert(Base)) 03463 return false; 03464 NewOffset = MostDerivedLayout.getVBaseClassOffset(Base); 03465 } 03466 FullPath.push_back(Base); 03467 if (findPathForVPtr(Context, MostDerivedLayout, Base, NewOffset, VBasesSeen, 03468 FullPath, Info)) 03469 return true; 03470 FullPath.pop_back(); 03471 } 03472 return false; 03473 } 03474 03475 static void computeFullPathsForVFTables(ASTContext &Context, 03476 const CXXRecordDecl *RD, 03477 VPtrInfoVector &Paths) { 03478 llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen; 03479 const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD); 03480 VPtrInfo::BasePath FullPath; 03481 for (VPtrInfo *Info : Paths) { 03482 findPathForVPtr(Context, MostDerivedLayout, RD, CharUnits::Zero(), 03483 VBasesSeen, FullPath, Info); 03484 VBasesSeen.clear(); 03485 FullPath.clear(); 03486 } 03487 } 03488 03489 void MicrosoftVTableContext::computeVTableRelatedInformation( 03490 const CXXRecordDecl *RD) { 03491 assert(RD->isDynamicClass()); 03492 03493 // Check if we've computed this information before. 03494 if (VFPtrLocations.count(RD)) 03495 return; 03496 03497 const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap; 03498 03499 VPtrInfoVector *VFPtrs = new VPtrInfoVector(); 03500 computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs); 03501 computeFullPathsForVFTables(Context, RD, *VFPtrs); 03502 VFPtrLocations[RD] = VFPtrs; 03503 03504 MethodVFTableLocationsTy NewMethodLocations; 03505 for (VPtrInfoVector::iterator I = VFPtrs->begin(), E = VFPtrs->end(); 03506 I != E; ++I) { 03507 VFTableBuilder Builder(*this, RD, *I); 03508 03509 VFTableIdTy id(RD, (*I)->FullOffsetInMDC); 03510 assert(VFTableLayouts.count(id) == 0); 03511 SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks( 03512 Builder.vtable_thunks_begin(), Builder.vtable_thunks_end()); 03513 VFTableLayouts[id] = new VTableLayout( 03514 Builder.getNumVTableComponents(), Builder.vtable_component_begin(), 03515 VTableThunks.size(), VTableThunks.data(), EmptyAddressPointsMap, true); 03516 Thunks.insert(Builder.thunks_begin(), Builder.thunks_end()); 03517 03518 for (const auto &Loc : Builder.vtable_locations()) { 03519 GlobalDecl GD = Loc.first; 03520 MethodVFTableLocation NewLoc = Loc.second; 03521 auto M = NewMethodLocations.find(GD); 03522 if (M == NewMethodLocations.end() || NewLoc < M->second) 03523 NewMethodLocations[GD] = NewLoc; 03524 } 03525 } 03526 03527 MethodVFTableLocations.insert(NewMethodLocations.begin(), 03528 NewMethodLocations.end()); 03529 if (Context.getLangOpts().DumpVTableLayouts) 03530 dumpMethodLocations(RD, NewMethodLocations, llvm::outs()); 03531 } 03532 03533 void MicrosoftVTableContext::dumpMethodLocations( 03534 const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods, 03535 raw_ostream &Out) { 03536 // Compute the vtable indices for all the member functions. 03537 // Store them in a map keyed by the location so we'll get a sorted table. 03538 std::map<MethodVFTableLocation, std::string> IndicesMap; 03539 bool HasNonzeroOffset = false; 03540 03541 for (MethodVFTableLocationsTy::const_iterator I = NewMethods.begin(), 03542 E = NewMethods.end(); I != E; ++I) { 03543 const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I->first.getDecl()); 03544 assert(MD->isVirtual()); 03545 03546 std::string MethodName = PredefinedExpr::ComputeName( 03547 PredefinedExpr::PrettyFunctionNoVirtual, MD); 03548 03549 if (isa<CXXDestructorDecl>(MD)) { 03550 IndicesMap[I->second] = MethodName + " [scalar deleting]"; 03551 } else { 03552 IndicesMap[I->second] = MethodName; 03553 } 03554 03555 if (!I->second.VFPtrOffset.isZero() || I->second.VBTableIndex != 0) 03556 HasNonzeroOffset = true; 03557 } 03558 03559 // Print the vtable indices for all the member functions. 03560 if (!IndicesMap.empty()) { 03561 Out << "VFTable indices for "; 03562 Out << "'"; 03563 RD->printQualifiedName(Out); 03564 Out << "' (" << IndicesMap.size() 03565 << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n"; 03566 03567 CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1); 03568 uint64_t LastVBIndex = 0; 03569 for (std::map<MethodVFTableLocation, std::string>::const_iterator 03570 I = IndicesMap.begin(), 03571 E = IndicesMap.end(); 03572 I != E; ++I) { 03573 CharUnits VFPtrOffset = I->first.VFPtrOffset; 03574 uint64_t VBIndex = I->first.VBTableIndex; 03575 if (HasNonzeroOffset && 03576 (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) { 03577 assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset); 03578 Out << " -- accessible via "; 03579 if (VBIndex) 03580 Out << "vbtable index " << VBIndex << ", "; 03581 Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n"; 03582 LastVFPtrOffset = VFPtrOffset; 03583 LastVBIndex = VBIndex; 03584 } 03585 03586 uint64_t VTableIndex = I->first.Index; 03587 const std::string &MethodName = I->second; 03588 Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n'; 03589 } 03590 Out << '\n'; 03591 } 03592 03593 Out.flush(); 03594 } 03595 03596 const VirtualBaseInfo *MicrosoftVTableContext::computeVBTableRelatedInformation( 03597 const CXXRecordDecl *RD) { 03598 VirtualBaseInfo *VBI; 03599 03600 { 03601 // Get or create a VBI for RD. Don't hold a reference to the DenseMap cell, 03602 // as it may be modified and rehashed under us. 03603 VirtualBaseInfo *&Entry = VBaseInfo[RD]; 03604 if (Entry) 03605 return Entry; 03606 Entry = VBI = new VirtualBaseInfo(); 03607 } 03608 03609 computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths); 03610 03611 // First, see if the Derived class shared the vbptr with a non-virtual base. 03612 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); 03613 if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) { 03614 // If the Derived class shares the vbptr with a non-virtual base, the shared 03615 // virtual bases come first so that the layout is the same. 03616 const VirtualBaseInfo *BaseInfo = 03617 computeVBTableRelatedInformation(VBPtrBase); 03618 VBI->VBTableIndices.insert(BaseInfo->VBTableIndices.begin(), 03619 BaseInfo->VBTableIndices.end()); 03620 } 03621 03622 // New vbases are added to the end of the vbtable. 03623 // Skip the self entry and vbases visited in the non-virtual base, if any. 03624 unsigned VBTableIndex = 1 + VBI->VBTableIndices.size(); 03625 for (const auto &VB : RD->vbases()) { 03626 const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl(); 03627 if (!VBI->VBTableIndices.count(CurVBase)) 03628 VBI->VBTableIndices[CurVBase] = VBTableIndex++; 03629 } 03630 03631 return VBI; 03632 } 03633 03634 unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived, 03635 const CXXRecordDecl *VBase) { 03636 const VirtualBaseInfo *VBInfo = computeVBTableRelatedInformation(Derived); 03637 assert(VBInfo->VBTableIndices.count(VBase)); 03638 return VBInfo->VBTableIndices.find(VBase)->second; 03639 } 03640 03641 const VPtrInfoVector & 03642 MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) { 03643 return computeVBTableRelatedInformation(RD)->VBPtrPaths; 03644 } 03645 03646 const VPtrInfoVector & 03647 MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) { 03648 computeVTableRelatedInformation(RD); 03649 03650 assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations"); 03651 return *VFPtrLocations[RD]; 03652 } 03653 03654 const VTableLayout & 03655 MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD, 03656 CharUnits VFPtrOffset) { 03657 computeVTableRelatedInformation(RD); 03658 03659 VFTableIdTy id(RD, VFPtrOffset); 03660 assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset"); 03661 return *VFTableLayouts[id]; 03662 } 03663 03664 const MicrosoftVTableContext::MethodVFTableLocation & 03665 MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) { 03666 assert(cast<CXXMethodDecl>(GD.getDecl())->isVirtual() && 03667 "Only use this method for virtual methods or dtors"); 03668 if (isa<CXXDestructorDecl>(GD.getDecl())) 03669 assert(GD.getDtorType() == Dtor_Deleting); 03670 03671 MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD); 03672 if (I != MethodVFTableLocations.end()) 03673 return I->second; 03674 03675 const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent(); 03676 03677 computeVTableRelatedInformation(RD); 03678 03679 I = MethodVFTableLocations.find(GD); 03680 assert(I != MethodVFTableLocations.end() && "Did not find index!"); 03681 return I->second; 03682 }