1 //===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This contains code dealing with generation of the layout of virtual tables.
12 //===----------------------------------------------------------------------===//
14 #include "clang/AST/VTableBuilder.h"
15 #include "clang/AST/ASTContext.h"
16 #include "clang/AST/CXXInheritance.h"
17 #include "clang/AST/RecordLayout.h"
18 #include "clang/Basic/TargetInfo.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/Support/Format.h"
21 #include "llvm/Support/raw_ostream.h"
25 using namespace clang;
27 #define DUMP_OVERRIDERS 0
31 /// BaseOffset - Represents an offset from a derived class to a direct or
32 /// indirect base class.
34 /// DerivedClass - The derived class.
35 const CXXRecordDecl *DerivedClass;
37 /// VirtualBase - If the path from the derived class to the base class
38 /// involves virtual base classes, this holds the declaration of the last
39 /// virtual base in this path (i.e. closest to the base class).
40 const CXXRecordDecl *VirtualBase;
42 /// NonVirtualOffset - The offset from the derived class to the base class.
43 /// (Or the offset from the virtual base class to the base class, if the
44 /// path from the derived class to the base class involves a virtual base
46 CharUnits NonVirtualOffset;
48 BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
49 NonVirtualOffset(CharUnits::Zero()) { }
50 BaseOffset(const CXXRecordDecl *DerivedClass,
51 const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
52 : DerivedClass(DerivedClass), VirtualBase(VirtualBase),
53 NonVirtualOffset(NonVirtualOffset) { }
55 bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; }
58 /// FinalOverriders - Contains the final overrider member functions for all
59 /// member functions in the base subobjects of a class.
60 class FinalOverriders {
62 /// OverriderInfo - Information about a final overrider.
63 struct OverriderInfo {
64 /// Method - The method decl of the overrider.
65 const CXXMethodDecl *Method;
67 /// VirtualBase - The virtual base class subobject of this overridder.
68 /// Note that this records the closest derived virtual base class subobject.
69 const CXXRecordDecl *VirtualBase;
71 /// Offset - the base offset of the overrider's parent in the layout class.
74 OverriderInfo() : Method(nullptr), VirtualBase(nullptr),
75 Offset(CharUnits::Zero()) { }
79 /// MostDerivedClass - The most derived class for which the final overriders
81 const CXXRecordDecl *MostDerivedClass;
83 /// MostDerivedClassOffset - If we're building final overriders for a
84 /// construction vtable, this holds the offset from the layout class to the
85 /// most derived class.
86 const CharUnits MostDerivedClassOffset;
88 /// LayoutClass - The class we're using for layout information. Will be
89 /// different than the most derived class if the final overriders are for a
90 /// construction vtable.
91 const CXXRecordDecl *LayoutClass;
95 /// MostDerivedClassLayout - the AST record layout of the most derived class.
96 const ASTRecordLayout &MostDerivedClassLayout;
98 /// MethodBaseOffsetPairTy - Uniquely identifies a member function
99 /// in a base subobject.
100 typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
102 typedef llvm::DenseMap<MethodBaseOffsetPairTy,
103 OverriderInfo> OverridersMapTy;
105 /// OverridersMap - The final overriders for all virtual member functions of
106 /// all the base subobjects of the most derived class.
107 OverridersMapTy OverridersMap;
109 /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
110 /// as a record decl and a subobject number) and its offsets in the most
111 /// derived class as well as the layout class.
112 typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>,
113 CharUnits> SubobjectOffsetMapTy;
115 typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
117 /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
119 void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
120 CharUnits OffsetInLayoutClass,
121 SubobjectOffsetMapTy &SubobjectOffsets,
122 SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
123 SubobjectCountMapTy &SubobjectCounts);
125 typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
127 /// dump - dump the final overriders for a base subobject, and all its direct
128 /// and indirect base subobjects.
129 void dump(raw_ostream &Out, BaseSubobject Base,
130 VisitedVirtualBasesSetTy& VisitedVirtualBases);
133 FinalOverriders(const CXXRecordDecl *MostDerivedClass,
134 CharUnits MostDerivedClassOffset,
135 const CXXRecordDecl *LayoutClass);
137 /// getOverrider - Get the final overrider for the given method declaration in
138 /// the subobject with the given base offset.
139 OverriderInfo getOverrider(const CXXMethodDecl *MD,
140 CharUnits BaseOffset) const {
141 assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) &&
142 "Did not find overrider!");
144 return OverridersMap.lookup(std::make_pair(MD, BaseOffset));
147 /// dump - dump the final overriders.
149 VisitedVirtualBasesSetTy VisitedVirtualBases;
150 dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()),
151 VisitedVirtualBases);
156 FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
157 CharUnits MostDerivedClassOffset,
158 const CXXRecordDecl *LayoutClass)
159 : MostDerivedClass(MostDerivedClass),
160 MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
161 Context(MostDerivedClass->getASTContext()),
162 MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
164 // Compute base offsets.
165 SubobjectOffsetMapTy SubobjectOffsets;
166 SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
167 SubobjectCountMapTy SubobjectCounts;
168 ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()),
170 MostDerivedClassOffset,
171 SubobjectOffsets, SubobjectLayoutClassOffsets,
174 // Get the final overriders.
175 CXXFinalOverriderMap FinalOverriders;
176 MostDerivedClass->getFinalOverriders(FinalOverriders);
178 for (CXXFinalOverriderMap::const_iterator I = FinalOverriders.begin(),
179 E = FinalOverriders.end(); I != E; ++I) {
180 const CXXMethodDecl *MD = I->first;
181 const OverridingMethods& Methods = I->second;
183 for (OverridingMethods::const_iterator I = Methods.begin(),
184 E = Methods.end(); I != E; ++I) {
185 unsigned SubobjectNumber = I->first;
186 assert(SubobjectOffsets.count(std::make_pair(MD->getParent(),
188 "Did not find subobject offset!");
190 CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(),
193 assert(I->second.size() == 1 && "Final overrider is not unique!");
194 const UniqueVirtualMethod &Method = I->second.front();
196 const CXXRecordDecl *OverriderRD = Method.Method->getParent();
197 assert(SubobjectLayoutClassOffsets.count(
198 std::make_pair(OverriderRD, Method.Subobject))
199 && "Did not find subobject offset!");
200 CharUnits OverriderOffset =
201 SubobjectLayoutClassOffsets[std::make_pair(OverriderRD,
204 OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)];
205 assert(!Overrider.Method && "Overrider should not exist yet!");
207 Overrider.Offset = OverriderOffset;
208 Overrider.Method = Method.Method;
209 Overrider.VirtualBase = Method.InVirtualSubobject;
214 // And dump them (for now).
219 static BaseOffset ComputeBaseOffset(ASTContext &Context,
220 const CXXRecordDecl *DerivedRD,
221 const CXXBasePath &Path) {
222 CharUnits NonVirtualOffset = CharUnits::Zero();
224 unsigned NonVirtualStart = 0;
225 const CXXRecordDecl *VirtualBase = nullptr;
227 // First, look for the virtual base class.
228 for (int I = Path.size(), E = 0; I != E; --I) {
229 const CXXBasePathElement &Element = Path[I - 1];
231 if (Element.Base->isVirtual()) {
233 QualType VBaseType = Element.Base->getType();
234 VirtualBase = VBaseType->getAsCXXRecordDecl();
239 // Now compute the non-virtual offset.
240 for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) {
241 const CXXBasePathElement &Element = Path[I];
243 // Check the base class offset.
244 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
246 const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl();
248 NonVirtualOffset += Layout.getBaseClassOffset(Base);
251 // FIXME: This should probably use CharUnits or something. Maybe we should
252 // even change the base offsets in ASTRecordLayout to be specified in
254 return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
258 static BaseOffset ComputeBaseOffset(ASTContext &Context,
259 const CXXRecordDecl *BaseRD,
260 const CXXRecordDecl *DerivedRD) {
261 CXXBasePaths Paths(/*FindAmbiguities=*/false,
262 /*RecordPaths=*/true, /*DetectVirtual=*/false);
264 if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
265 llvm_unreachable("Class must be derived from the passed in base class!");
267 return ComputeBaseOffset(Context, DerivedRD, Paths.front());
271 ComputeReturnAdjustmentBaseOffset(ASTContext &Context,
272 const CXXMethodDecl *DerivedMD,
273 const CXXMethodDecl *BaseMD) {
274 const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>();
275 const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>();
277 // Canonicalize the return types.
278 CanQualType CanDerivedReturnType =
279 Context.getCanonicalType(DerivedFT->getReturnType());
280 CanQualType CanBaseReturnType =
281 Context.getCanonicalType(BaseFT->getReturnType());
283 assert(CanDerivedReturnType->getTypeClass() ==
284 CanBaseReturnType->getTypeClass() &&
285 "Types must have same type class!");
287 if (CanDerivedReturnType == CanBaseReturnType) {
288 // No adjustment needed.
292 if (isa<ReferenceType>(CanDerivedReturnType)) {
293 CanDerivedReturnType =
294 CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
296 CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
297 } else if (isa<PointerType>(CanDerivedReturnType)) {
298 CanDerivedReturnType =
299 CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
301 CanBaseReturnType->getAs<PointerType>()->getPointeeType();
303 llvm_unreachable("Unexpected return type!");
306 // We need to compare unqualified types here; consider
307 // const T *Base::foo();
308 // T *Derived::foo();
309 if (CanDerivedReturnType.getUnqualifiedType() ==
310 CanBaseReturnType.getUnqualifiedType()) {
311 // No adjustment needed.
315 const CXXRecordDecl *DerivedRD =
316 cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl());
318 const CXXRecordDecl *BaseRD =
319 cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());
321 return ComputeBaseOffset(Context, BaseRD, DerivedRD);
325 FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
326 CharUnits OffsetInLayoutClass,
327 SubobjectOffsetMapTy &SubobjectOffsets,
328 SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
329 SubobjectCountMapTy &SubobjectCounts) {
330 const CXXRecordDecl *RD = Base.getBase();
332 unsigned SubobjectNumber = 0;
334 SubobjectNumber = ++SubobjectCounts[RD];
336 // Set up the subobject to offset mapping.
337 assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))
338 && "Subobject offset already exists!");
339 assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber))
340 && "Subobject offset already exists!");
342 SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();
343 SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =
346 // Traverse our bases.
347 for (const auto &B : RD->bases()) {
348 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
350 CharUnits BaseOffset;
351 CharUnits BaseOffsetInLayoutClass;
353 // Check if we've visited this virtual base before.
354 if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))
357 const ASTRecordLayout &LayoutClassLayout =
358 Context.getASTRecordLayout(LayoutClass);
360 BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
361 BaseOffsetInLayoutClass =
362 LayoutClassLayout.getVBaseClassOffset(BaseDecl);
364 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
365 CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);
367 BaseOffset = Base.getBaseOffset() + Offset;
368 BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
371 ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset),
372 B.isVirtual(), BaseOffsetInLayoutClass,
373 SubobjectOffsets, SubobjectLayoutClassOffsets,
378 void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
379 VisitedVirtualBasesSetTy &VisitedVirtualBases) {
380 const CXXRecordDecl *RD = Base.getBase();
381 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
383 for (const auto &B : RD->bases()) {
384 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
386 // Ignore bases that don't have any virtual member functions.
387 if (!BaseDecl->isPolymorphic())
390 CharUnits BaseOffset;
392 if (!VisitedVirtualBases.insert(BaseDecl)) {
393 // We've visited this base before.
397 BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
399 BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();
402 dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
405 Out << "Final overriders for (";
406 RD->printQualifiedName(Out);
408 Out << Base.getBaseOffset().getQuantity() << ")\n";
410 // Now dump the overriders for this base subobject.
411 for (const auto *MD : RD->methods()) {
412 if (!MD->isVirtual())
415 OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());
418 MD->printQualifiedName(Out);
420 Overrider.Method->printQualifiedName(Out);
421 Out << ", " << Overrider.Offset.getQuantity() << ')';
424 if (!Overrider.Method->isPure())
425 Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
427 if (!Offset.isEmpty()) {
428 Out << " [ret-adj: ";
429 if (Offset.VirtualBase) {
430 Offset.VirtualBase->printQualifiedName(Out);
434 Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
441 /// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
442 struct VCallOffsetMap {
444 typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
446 /// Offsets - Keeps track of methods and their offsets.
447 // FIXME: This should be a real map and not a vector.
448 SmallVector<MethodAndOffsetPairTy, 16> Offsets;
450 /// MethodsCanShareVCallOffset - Returns whether two virtual member functions
451 /// can share the same vcall offset.
452 static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
453 const CXXMethodDecl *RHS);
456 /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
457 /// add was successful, or false if there was already a member function with
458 /// the same signature in the map.
459 bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
461 /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
462 /// vtable address point) for the given virtual member function.
463 CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
465 // empty - Return whether the offset map is empty or not.
466 bool empty() const { return Offsets.empty(); }
469 static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
470 const CXXMethodDecl *RHS) {
471 const FunctionProtoType *LT =
472 cast<FunctionProtoType>(LHS->getType().getCanonicalType());
473 const FunctionProtoType *RT =
474 cast<FunctionProtoType>(RHS->getType().getCanonicalType());
476 // Fast-path matches in the canonical types.
477 if (LT == RT) return true;
479 // Force the signatures to match. We can't rely on the overrides
480 // list here because there isn't necessarily an inheritance
481 // relationship between the two methods.
482 if (LT->getTypeQuals() != RT->getTypeQuals() ||
483 LT->getNumParams() != RT->getNumParams())
485 for (unsigned I = 0, E = LT->getNumParams(); I != E; ++I)
486 if (LT->getParamType(I) != RT->getParamType(I))
491 bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
492 const CXXMethodDecl *RHS) {
493 assert(LHS->isVirtual() && "LHS must be virtual!");
494 assert(RHS->isVirtual() && "LHS must be virtual!");
496 // A destructor can share a vcall offset with another destructor.
497 if (isa<CXXDestructorDecl>(LHS))
498 return isa<CXXDestructorDecl>(RHS);
500 // FIXME: We need to check more things here.
502 // The methods must have the same name.
503 DeclarationName LHSName = LHS->getDeclName();
504 DeclarationName RHSName = RHS->getDeclName();
505 if (LHSName != RHSName)
508 // And the same signatures.
509 return HasSameVirtualSignature(LHS, RHS);
512 bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,
513 CharUnits OffsetOffset) {
514 // Check if we can reuse an offset.
515 for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
516 if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
521 Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));
525 CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
526 // Look for an offset.
527 for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
528 if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
529 return Offsets[I].second;
532 llvm_unreachable("Should always find a vcall offset offset!");
535 /// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
536 class VCallAndVBaseOffsetBuilder {
538 typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
539 VBaseOffsetOffsetsMapTy;
542 /// MostDerivedClass - The most derived class for which we're building vcall
543 /// and vbase offsets.
544 const CXXRecordDecl *MostDerivedClass;
546 /// LayoutClass - The class we're using for layout information. Will be
547 /// different than the most derived class if we're building a construction
549 const CXXRecordDecl *LayoutClass;
551 /// Context - The ASTContext which we will use for layout information.
554 /// Components - vcall and vbase offset components
555 typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
556 VTableComponentVectorTy Components;
558 /// VisitedVirtualBases - Visited virtual bases.
559 llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
561 /// VCallOffsets - Keeps track of vcall offsets.
562 VCallOffsetMap VCallOffsets;
565 /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
566 /// relative to the address point.
567 VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
569 /// FinalOverriders - The final overriders of the most derived class.
570 /// (Can be null when we're not building a vtable of the most derived class).
571 const FinalOverriders *Overriders;
573 /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
574 /// given base subobject.
575 void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
576 CharUnits RealBaseOffset);
578 /// AddVCallOffsets - Add vcall offsets for the given base subobject.
579 void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
581 /// AddVBaseOffsets - Add vbase offsets for the given class.
582 void AddVBaseOffsets(const CXXRecordDecl *Base,
583 CharUnits OffsetInLayoutClass);
585 /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
586 /// chars, relative to the vtable address point.
587 CharUnits getCurrentOffsetOffset() const;
590 VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass,
591 const CXXRecordDecl *LayoutClass,
592 const FinalOverriders *Overriders,
593 BaseSubobject Base, bool BaseIsVirtual,
594 CharUnits OffsetInLayoutClass)
595 : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass),
596 Context(MostDerivedClass->getASTContext()), Overriders(Overriders) {
598 // Add vcall and vbase offsets.
599 AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);
602 /// Methods for iterating over the components.
603 typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
604 const_iterator components_begin() const { return Components.rbegin(); }
605 const_iterator components_end() const { return Components.rend(); }
607 const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
608 const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
609 return VBaseOffsetOffsets;
614 VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
616 CharUnits RealBaseOffset) {
617 const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
619 // Itanium C++ ABI 2.5.2:
620 // ..in classes sharing a virtual table with a primary base class, the vcall
621 // and vbase offsets added by the derived class all come before the vcall
622 // and vbase offsets required by the base class, so that the latter may be
623 // laid out as required by the base class without regard to additions from
624 // the derived class(es).
626 // (Since we're emitting the vcall and vbase offsets in reverse order, we'll
627 // emit them for the primary base first).
628 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
629 bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
631 CharUnits PrimaryBaseOffset;
633 // Get the base offset of the primary base.
634 if (PrimaryBaseIsVirtual) {
635 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
636 "Primary vbase should have a zero offset!");
638 const ASTRecordLayout &MostDerivedClassLayout =
639 Context.getASTRecordLayout(MostDerivedClass);
642 MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
644 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
645 "Primary base should have a zero offset!");
647 PrimaryBaseOffset = Base.getBaseOffset();
650 AddVCallAndVBaseOffsets(
651 BaseSubobject(PrimaryBase,PrimaryBaseOffset),
652 PrimaryBaseIsVirtual, RealBaseOffset);
655 AddVBaseOffsets(Base.getBase(), RealBaseOffset);
657 // We only want to add vcall offsets for virtual bases.
659 AddVCallOffsets(Base, RealBaseOffset);
662 CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
663 // OffsetIndex is the index of this vcall or vbase offset, relative to the
664 // vtable address point. (We subtract 3 to account for the information just
665 // above the address point, the RTTI info, the offset to top, and the
666 // vcall offset itself).
667 int64_t OffsetIndex = -(int64_t)(3 + Components.size());
669 CharUnits PointerWidth =
670 Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
671 CharUnits OffsetOffset = PointerWidth * OffsetIndex;
675 void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,
676 CharUnits VBaseOffset) {
677 const CXXRecordDecl *RD = Base.getBase();
678 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
680 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
682 // Handle the primary base first.
683 // We only want to add vcall offsets if the base is non-virtual; a virtual
684 // primary base will have its vcall and vbase offsets emitted already.
685 if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {
686 // Get the base offset of the primary base.
687 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
688 "Primary base should have a zero offset!");
690 AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),
694 // Add the vcall offsets.
695 for (const auto *MD : RD->methods()) {
696 if (!MD->isVirtual())
699 CharUnits OffsetOffset = getCurrentOffsetOffset();
701 // Don't add a vcall offset if we already have one for this member function
703 if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
706 CharUnits Offset = CharUnits::Zero();
709 // Get the final overrider.
710 FinalOverriders::OverriderInfo Overrider =
711 Overriders->getOverrider(MD, Base.getBaseOffset());
713 /// The vcall offset is the offset from the virtual base to the object
714 /// where the function was overridden.
715 Offset = Overrider.Offset - VBaseOffset;
718 Components.push_back(
719 VTableComponent::MakeVCallOffset(Offset));
722 // And iterate over all non-virtual bases (ignoring the primary base).
723 for (const auto &B : RD->bases()) {
727 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
728 if (BaseDecl == PrimaryBase)
731 // Get the base offset of this base.
732 CharUnits BaseOffset = Base.getBaseOffset() +
733 Layout.getBaseClassOffset(BaseDecl);
735 AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset),
741 VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
742 CharUnits OffsetInLayoutClass) {
743 const ASTRecordLayout &LayoutClassLayout =
744 Context.getASTRecordLayout(LayoutClass);
746 // Add vbase offsets.
747 for (const auto &B : RD->bases()) {
748 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
750 // Check if this is a virtual base that we haven't visited before.
751 if (B.isVirtual() && VisitedVirtualBases.insert(BaseDecl)) {
753 LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;
755 // Add the vbase offset offset.
756 assert(!VBaseOffsetOffsets.count(BaseDecl) &&
757 "vbase offset offset already exists!");
759 CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
760 VBaseOffsetOffsets.insert(
761 std::make_pair(BaseDecl, VBaseOffsetOffset));
763 Components.push_back(
764 VTableComponent::MakeVBaseOffset(Offset));
767 // Check the base class looking for more vbase offsets.
768 AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);
772 /// ItaniumVTableBuilder - Class for building vtable layout information.
773 class ItaniumVTableBuilder {
775 /// PrimaryBasesSetVectorTy - A set vector of direct and indirect
777 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8>
778 PrimaryBasesSetVectorTy;
780 typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
781 VBaseOffsetOffsetsMapTy;
783 typedef llvm::DenseMap<BaseSubobject, uint64_t>
786 typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
789 /// VTables - Global vtable information.
790 ItaniumVTableContext &VTables;
792 /// MostDerivedClass - The most derived class for which we're building this
794 const CXXRecordDecl *MostDerivedClass;
796 /// MostDerivedClassOffset - If we're building a construction vtable, this
797 /// holds the offset from the layout class to the most derived class.
798 const CharUnits MostDerivedClassOffset;
800 /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual
801 /// base. (This only makes sense when building a construction vtable).
802 bool MostDerivedClassIsVirtual;
804 /// LayoutClass - The class we're using for layout information. Will be
805 /// different than the most derived class if we're building a construction
807 const CXXRecordDecl *LayoutClass;
809 /// Context - The ASTContext which we will use for layout information.
812 /// FinalOverriders - The final overriders of the most derived class.
813 const FinalOverriders Overriders;
815 /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
816 /// bases in this vtable.
817 llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
819 /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
820 /// the most derived class.
821 VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
823 /// Components - The components of the vtable being built.
824 SmallVector<VTableComponent, 64> Components;
826 /// AddressPoints - Address points for the vtable being built.
827 AddressPointsMapTy AddressPoints;
829 /// MethodInfo - Contains information about a method in a vtable.
830 /// (Used for computing 'this' pointer adjustment thunks.
832 /// BaseOffset - The base offset of this method.
833 const CharUnits BaseOffset;
835 /// BaseOffsetInLayoutClass - The base offset in the layout class of this
837 const CharUnits BaseOffsetInLayoutClass;
839 /// VTableIndex - The index in the vtable that this method has.
840 /// (For destructors, this is the index of the complete destructor).
841 const uint64_t VTableIndex;
843 MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,
844 uint64_t VTableIndex)
845 : BaseOffset(BaseOffset),
846 BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
847 VTableIndex(VTableIndex) { }
850 : BaseOffset(CharUnits::Zero()),
851 BaseOffsetInLayoutClass(CharUnits::Zero()),
855 typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
857 /// MethodInfoMap - The information for all methods in the vtable we're
858 /// currently building.
859 MethodInfoMapTy MethodInfoMap;
861 /// MethodVTableIndices - Contains the index (relative to the vtable address
862 /// point) where the function pointer for a virtual function is stored.
863 MethodVTableIndicesTy MethodVTableIndices;
865 typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
867 /// VTableThunks - The thunks by vtable index in the vtable currently being
869 VTableThunksMapTy VTableThunks;
871 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
872 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
874 /// Thunks - A map that contains all the thunks needed for all methods in the
875 /// most derived class for which the vtable is currently being built.
878 /// AddThunk - Add a thunk for the given method.
879 void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
881 /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
882 /// part of the vtable we're currently building.
883 void ComputeThisAdjustments();
885 typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
887 /// PrimaryVirtualBases - All known virtual bases who are a primary base of
889 VisitedVirtualBasesSetTy PrimaryVirtualBases;
891 /// ComputeReturnAdjustment - Compute the return adjustment given a return
892 /// adjustment base offset.
893 ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
895 /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
896 /// the 'this' pointer from the base subobject to the derived subobject.
897 BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
898 BaseSubobject Derived) const;
900 /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
901 /// given virtual member function, its offset in the layout class and its
904 ComputeThisAdjustment(const CXXMethodDecl *MD,
905 CharUnits BaseOffsetInLayoutClass,
906 FinalOverriders::OverriderInfo Overrider);
908 /// AddMethod - Add a single virtual member function to the vtable
909 /// components vector.
910 void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
912 /// IsOverriderUsed - Returns whether the overrider will ever be used in this
913 /// part of the vtable.
915 /// Itanium C++ ABI 2.5.2:
917 /// struct A { virtual void f(); };
918 /// struct B : virtual public A { int i; };
919 /// struct C : virtual public A { int j; };
920 /// struct D : public B, public C {};
922 /// When B and C are declared, A is a primary base in each case, so although
923 /// vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
924 /// adjustment is required and no thunk is generated. However, inside D
925 /// objects, A is no longer a primary base of C, so if we allowed calls to
926 /// C::f() to use the copy of A's vtable in the C subobject, we would need
927 /// to adjust this from C* to B::A*, which would require a third-party
928 /// thunk. Since we require that a call to C::f() first convert to A*,
929 /// C-in-D's copy of A's vtable is never referenced, so this is not
931 bool IsOverriderUsed(const CXXMethodDecl *Overrider,
932 CharUnits BaseOffsetInLayoutClass,
933 const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
934 CharUnits FirstBaseOffsetInLayoutClass) const;
937 /// AddMethods - Add the methods of this base subobject and all its
938 /// primary bases to the vtable components vector.
939 void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
940 const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
941 CharUnits FirstBaseOffsetInLayoutClass,
942 PrimaryBasesSetVectorTy &PrimaryBases);
944 // LayoutVTable - Layout the vtable for the given base class, including its
945 // secondary vtables and any vtables for virtual bases.
948 /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the
949 /// given base subobject, as well as all its secondary vtables.
951 /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
952 /// or a direct or indirect base of a virtual base.
954 /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual
955 /// in the layout class.
956 void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,
957 bool BaseIsMorallyVirtual,
958 bool BaseIsVirtualInLayoutClass,
959 CharUnits OffsetInLayoutClass);
961 /// LayoutSecondaryVTables - Layout the secondary vtables for the given base
964 /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
965 /// or a direct or indirect base of a virtual base.
966 void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,
967 CharUnits OffsetInLayoutClass);
969 /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this
971 void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD,
972 CharUnits OffsetInLayoutClass,
973 VisitedVirtualBasesSetTy &VBases);
975 /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the
976 /// given base (excluding any primary bases).
977 void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD,
978 VisitedVirtualBasesSetTy &VBases);
980 /// isBuildingConstructionVTable - Return whether this vtable builder is
981 /// building a construction vtable.
982 bool isBuildingConstructorVTable() const {
983 return MostDerivedClass != LayoutClass;
987 ItaniumVTableBuilder(ItaniumVTableContext &VTables,
988 const CXXRecordDecl *MostDerivedClass,
989 CharUnits MostDerivedClassOffset,
990 bool MostDerivedClassIsVirtual,
991 const CXXRecordDecl *LayoutClass)
992 : VTables(VTables), MostDerivedClass(MostDerivedClass),
993 MostDerivedClassOffset(MostDerivedClassOffset),
994 MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
995 LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
996 Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {
997 assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());
1001 if (Context.getLangOpts().DumpVTableLayouts)
1002 dumpLayout(llvm::outs());
1005 uint64_t getNumThunks() const {
1006 return Thunks.size();
1009 ThunksMapTy::const_iterator thunks_begin() const {
1010 return Thunks.begin();
1013 ThunksMapTy::const_iterator thunks_end() const {
1014 return Thunks.end();
1017 const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
1018 return VBaseOffsetOffsets;
1021 const AddressPointsMapTy &getAddressPoints() const {
1022 return AddressPoints;
1025 MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
1026 return MethodVTableIndices.begin();
1029 MethodVTableIndicesTy::const_iterator vtable_indices_end() const {
1030 return MethodVTableIndices.end();
1033 /// getNumVTableComponents - Return the number of components in the vtable
1034 /// currently built.
1035 uint64_t getNumVTableComponents() const {
1036 return Components.size();
1039 const VTableComponent *vtable_component_begin() const {
1040 return Components.begin();
1043 const VTableComponent *vtable_component_end() const {
1044 return Components.end();
1047 AddressPointsMapTy::const_iterator address_points_begin() const {
1048 return AddressPoints.begin();
1051 AddressPointsMapTy::const_iterator address_points_end() const {
1052 return AddressPoints.end();
1055 VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
1056 return VTableThunks.begin();
1059 VTableThunksMapTy::const_iterator vtable_thunks_end() const {
1060 return VTableThunks.end();
1063 /// dumpLayout - Dump the vtable layout.
1064 void dumpLayout(raw_ostream&);
1067 void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
1068 const ThunkInfo &Thunk) {
1069 assert(!isBuildingConstructorVTable() &&
1070 "Can't add thunks for construction vtable");
1072 SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];
1074 // Check if we have this thunk already.
1075 if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) !=
1079 ThunksVector.push_back(Thunk);
1082 typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;
1084 /// Visit all the methods overridden by the given method recursively,
1085 /// in a depth-first pre-order. The Visitor's visitor method returns a bool
1086 /// indicating whether to continue the recursion for the given overridden
1087 /// method (i.e. returning false stops the iteration).
1088 template <class VisitorTy>
1090 visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1091 assert(MD->isVirtual() && "Method is not virtual!");
1093 for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
1094 E = MD->end_overridden_methods(); I != E; ++I) {
1095 const CXXMethodDecl *OverriddenMD = *I;
1096 if (!Visitor.visit(OverriddenMD))
1098 visitAllOverriddenMethods(OverriddenMD, Visitor);
1103 struct OverriddenMethodsCollector {
1104 OverriddenMethodsSetTy *Methods;
1106 bool visit(const CXXMethodDecl *MD) {
1107 // Don't recurse on this method if we've already collected it.
1108 return Methods->insert(MD);
1113 /// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
1114 /// the overridden methods that the function decl overrides.
1116 ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
1117 OverriddenMethodsSetTy& OverriddenMethods) {
1118 OverriddenMethodsCollector Collector = { &OverriddenMethods };
1119 visitAllOverriddenMethods(MD, Collector);
1122 void ItaniumVTableBuilder::ComputeThisAdjustments() {
1123 // Now go through the method info map and see if any of the methods need
1124 // 'this' pointer adjustments.
1125 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
1126 E = MethodInfoMap.end(); I != E; ++I) {
1127 const CXXMethodDecl *MD = I->first;
1128 const MethodInfo &MethodInfo = I->second;
1130 // Ignore adjustments for unused function pointers.
1131 uint64_t VTableIndex = MethodInfo.VTableIndex;
1132 if (Components[VTableIndex].getKind() ==
1133 VTableComponent::CK_UnusedFunctionPointer)
1136 // Get the final overrider for this method.
1137 FinalOverriders::OverriderInfo Overrider =
1138 Overriders.getOverrider(MD, MethodInfo.BaseOffset);
1140 // Check if we need an adjustment at all.
1141 if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {
1142 // When a return thunk is needed by a derived class that overrides a
1143 // virtual base, gcc uses a virtual 'this' adjustment as well.
1144 // While the thunk itself might be needed by vtables in subclasses or
1145 // in construction vtables, there doesn't seem to be a reason for using
1146 // the thunk in this vtable. Still, we do so to match gcc.
1147 if (VTableThunks.lookup(VTableIndex).Return.isEmpty())
1151 ThisAdjustment ThisAdjustment =
1152 ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider);
1154 if (ThisAdjustment.isEmpty())
1158 VTableThunks[VTableIndex].This = ThisAdjustment;
1160 if (isa<CXXDestructorDecl>(MD)) {
1161 // Add an adjustment for the deleting destructor as well.
1162 VTableThunks[VTableIndex + 1].This = ThisAdjustment;
1166 /// Clear the method info map.
1167 MethodInfoMap.clear();
1169 if (isBuildingConstructorVTable()) {
1170 // We don't need to store thunk information for construction vtables.
1174 for (VTableThunksMapTy::const_iterator I = VTableThunks.begin(),
1175 E = VTableThunks.end(); I != E; ++I) {
1176 const VTableComponent &Component = Components[I->first];
1177 const ThunkInfo &Thunk = I->second;
1178 const CXXMethodDecl *MD;
1180 switch (Component.getKind()) {
1182 llvm_unreachable("Unexpected vtable component kind!");
1183 case VTableComponent::CK_FunctionPointer:
1184 MD = Component.getFunctionDecl();
1186 case VTableComponent::CK_CompleteDtorPointer:
1187 MD = Component.getDestructorDecl();
1189 case VTableComponent::CK_DeletingDtorPointer:
1190 // We've already added the thunk when we saw the complete dtor pointer.
1194 if (MD->getParent() == MostDerivedClass)
1195 AddThunk(MD, Thunk);
1200 ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {
1201 ReturnAdjustment Adjustment;
1203 if (!Offset.isEmpty()) {
1204 if (Offset.VirtualBase) {
1205 // Get the virtual base offset offset.
1206 if (Offset.DerivedClass == MostDerivedClass) {
1207 // We can get the offset offset directly from our map.
1208 Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1209 VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity();
1211 Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1212 VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass,
1213 Offset.VirtualBase).getQuantity();
1217 Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1223 BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
1224 BaseSubobject Base, BaseSubobject Derived) const {
1225 const CXXRecordDecl *BaseRD = Base.getBase();
1226 const CXXRecordDecl *DerivedRD = Derived.getBase();
1228 CXXBasePaths Paths(/*FindAmbiguities=*/true,
1229 /*RecordPaths=*/true, /*DetectVirtual=*/true);
1231 if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
1232 llvm_unreachable("Class must be derived from the passed in base class!");
1234 // We have to go through all the paths, and see which one leads us to the
1235 // right base subobject.
1236 for (CXXBasePaths::const_paths_iterator I = Paths.begin(), E = Paths.end();
1238 BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, *I);
1240 CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;
1242 if (Offset.VirtualBase) {
1243 // If we have a virtual base class, the non-virtual offset is relative
1244 // to the virtual base class offset.
1245 const ASTRecordLayout &LayoutClassLayout =
1246 Context.getASTRecordLayout(LayoutClass);
1248 /// Get the virtual base offset, relative to the most derived class
1250 OffsetToBaseSubobject +=
1251 LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase);
1253 // Otherwise, the non-virtual offset is relative to the derived class
1255 OffsetToBaseSubobject += Derived.getBaseOffset();
1258 // Check if this path gives us the right base subobject.
1259 if (OffsetToBaseSubobject == Base.getBaseOffset()) {
1260 // Since we're going from the base class _to_ the derived class, we'll
1261 // invert the non-virtual offset here.
1262 Offset.NonVirtualOffset = -Offset.NonVirtualOffset;
1267 return BaseOffset();
1270 ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
1271 const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
1272 FinalOverriders::OverriderInfo Overrider) {
1273 // Ignore adjustments for pure virtual member functions.
1274 if (Overrider.Method->isPure())
1275 return ThisAdjustment();
1277 BaseSubobject OverriddenBaseSubobject(MD->getParent(),
1278 BaseOffsetInLayoutClass);
1280 BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),
1283 // Compute the adjustment offset.
1284 BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject,
1285 OverriderBaseSubobject);
1286 if (Offset.isEmpty())
1287 return ThisAdjustment();
1289 ThisAdjustment Adjustment;
1291 if (Offset.VirtualBase) {
1292 // Get the vcall offset map for this virtual base.
1293 VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];
1295 if (VCallOffsets.empty()) {
1296 // We don't have vcall offsets for this virtual base, go ahead and
1298 VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, MostDerivedClass,
1299 /*FinalOverriders=*/nullptr,
1300 BaseSubobject(Offset.VirtualBase,
1302 /*BaseIsVirtual=*/true,
1303 /*OffsetInLayoutClass=*/
1306 VCallOffsets = Builder.getVCallOffsets();
1309 Adjustment.Virtual.Itanium.VCallOffsetOffset =
1310 VCallOffsets.getVCallOffsetOffset(MD).getQuantity();
1313 // Set the non-virtual part of the adjustment.
1314 Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1319 void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
1320 ReturnAdjustment ReturnAdjustment) {
1321 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1322 assert(ReturnAdjustment.isEmpty() &&
1323 "Destructor can't have return adjustment!");
1325 // Add both the complete destructor and the deleting destructor.
1326 Components.push_back(VTableComponent::MakeCompleteDtor(DD));
1327 Components.push_back(VTableComponent::MakeDeletingDtor(DD));
1329 // Add the return adjustment if necessary.
1330 if (!ReturnAdjustment.isEmpty())
1331 VTableThunks[Components.size()].Return = ReturnAdjustment;
1333 // Add the function.
1334 Components.push_back(VTableComponent::MakeFunction(MD));
1338 /// OverridesIndirectMethodInBase - Return whether the given member function
1339 /// overrides any methods in the set of given bases.
1340 /// Unlike OverridesMethodInBase, this checks "overriders of overriders".
1341 /// For example, if we have:
1343 /// struct A { virtual void f(); }
1344 /// struct B : A { virtual void f(); }
1345 /// struct C : B { virtual void f(); }
1347 /// OverridesIndirectMethodInBase will return true if given C::f as the method
1348 /// and { A } as the set of bases.
1349 static bool OverridesIndirectMethodInBases(
1350 const CXXMethodDecl *MD,
1351 ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {
1352 if (Bases.count(MD->getParent()))
1355 for (CXXMethodDecl::method_iterator I = MD->begin_overridden_methods(),
1356 E = MD->end_overridden_methods(); I != E; ++I) {
1357 const CXXMethodDecl *OverriddenMD = *I;
1359 // Check "indirect overriders".
1360 if (OverridesIndirectMethodInBases(OverriddenMD, Bases))
1367 bool ItaniumVTableBuilder::IsOverriderUsed(
1368 const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
1369 const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1370 CharUnits FirstBaseOffsetInLayoutClass) const {
1371 // If the base and the first base in the primary base chain have the same
1372 // offsets, then this overrider will be used.
1373 if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)
1376 // We know now that Base (or a direct or indirect base of it) is a primary
1377 // base in part of the class hierarchy, but not a primary base in the most
1380 // If the overrider is the first base in the primary base chain, we know
1381 // that the overrider will be used.
1382 if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)
1385 ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;
1387 const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;
1388 PrimaryBases.insert(RD);
1390 // Now traverse the base chain, starting with the first base, until we find
1391 // the base that is no longer a primary base.
1393 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1394 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1399 if (Layout.isPrimaryBaseVirtual()) {
1400 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1401 "Primary base should always be at offset 0!");
1403 const ASTRecordLayout &LayoutClassLayout =
1404 Context.getASTRecordLayout(LayoutClass);
1406 // Now check if this is the primary base that is not a primary base in the
1407 // most derived class.
1408 if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1409 FirstBaseOffsetInLayoutClass) {
1410 // We found it, stop walking the chain.
1414 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1415 "Primary base should always be at offset 0!");
1418 if (!PrimaryBases.insert(PrimaryBase))
1419 llvm_unreachable("Found a duplicate primary base!");
1424 // If the final overrider is an override of one of the primary bases,
1425 // then we know that it will be used.
1426 return OverridesIndirectMethodInBases(Overrider, PrimaryBases);
1429 typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
1431 /// FindNearestOverriddenMethod - Given a method, returns the overridden method
1432 /// from the nearest base. Returns null if no method was found.
1433 /// The Bases are expected to be sorted in a base-to-derived order.
1434 static const CXXMethodDecl *
1435 FindNearestOverriddenMethod(const CXXMethodDecl *MD,
1436 BasesSetVectorTy &Bases) {
1437 OverriddenMethodsSetTy OverriddenMethods;
1438 ComputeAllOverriddenMethods(MD, OverriddenMethods);
1440 for (int I = Bases.size(), E = 0; I != E; --I) {
1441 const CXXRecordDecl *PrimaryBase = Bases[I - 1];
1443 // Now check the overridden methods.
1444 for (OverriddenMethodsSetTy::const_iterator I = OverriddenMethods.begin(),
1445 E = OverriddenMethods.end(); I != E; ++I) {
1446 const CXXMethodDecl *OverriddenMD = *I;
1448 // We found our overridden method.
1449 if (OverriddenMD->getParent() == PrimaryBase)
1450 return OverriddenMD;
1457 void ItaniumVTableBuilder::AddMethods(
1458 BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
1459 const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1460 CharUnits FirstBaseOffsetInLayoutClass,
1461 PrimaryBasesSetVectorTy &PrimaryBases) {
1462 // Itanium C++ ABI 2.5.2:
1463 // The order of the virtual function pointers in a virtual table is the
1464 // order of declaration of the corresponding member functions in the class.
1466 // There is an entry for any virtual function declared in a class,
1467 // whether it is a new function or overrides a base class function,
1468 // unless it overrides a function from the primary base, and conversion
1469 // between their return types does not require an adjustment.
1471 const CXXRecordDecl *RD = Base.getBase();
1472 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1474 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1475 CharUnits PrimaryBaseOffset;
1476 CharUnits PrimaryBaseOffsetInLayoutClass;
1477 if (Layout.isPrimaryBaseVirtual()) {
1478 assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1479 "Primary vbase should have a zero offset!");
1481 const ASTRecordLayout &MostDerivedClassLayout =
1482 Context.getASTRecordLayout(MostDerivedClass);
1485 MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
1487 const ASTRecordLayout &LayoutClassLayout =
1488 Context.getASTRecordLayout(LayoutClass);
1490 PrimaryBaseOffsetInLayoutClass =
1491 LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
1493 assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1494 "Primary base should have a zero offset!");
1496 PrimaryBaseOffset = Base.getBaseOffset();
1497 PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;
1500 AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset),
1501 PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain,
1502 FirstBaseOffsetInLayoutClass, PrimaryBases);
1504 if (!PrimaryBases.insert(PrimaryBase))
1505 llvm_unreachable("Found a duplicate primary base!");
1508 const CXXDestructorDecl *ImplicitVirtualDtor = nullptr;
1510 typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;
1511 NewVirtualFunctionsTy NewVirtualFunctions;
1513 // Now go through all virtual member functions and add them.
1514 for (const auto *MD : RD->methods()) {
1515 if (!MD->isVirtual())
1518 // Get the final overrider.
1519 FinalOverriders::OverriderInfo Overrider =
1520 Overriders.getOverrider(MD, Base.getBaseOffset());
1522 // Check if this virtual member function overrides a method in a primary
1523 // base. If this is the case, and the return type doesn't require adjustment
1524 // then we can just use the member function from the primary base.
1525 if (const CXXMethodDecl *OverriddenMD =
1526 FindNearestOverriddenMethod(MD, PrimaryBases)) {
1527 if (ComputeReturnAdjustmentBaseOffset(Context, MD,
1528 OverriddenMD).isEmpty()) {
1529 // Replace the method info of the overridden method with our own
1531 assert(MethodInfoMap.count(OverriddenMD) &&
1532 "Did not find the overridden method!");
1533 MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];
1535 MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1536 OverriddenMethodInfo.VTableIndex);
1538 assert(!MethodInfoMap.count(MD) &&
1539 "Should not have method info for this method yet!");
1541 MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1542 MethodInfoMap.erase(OverriddenMD);
1544 // If the overridden method exists in a virtual base class or a direct
1545 // or indirect base class of a virtual base class, we need to emit a
1546 // thunk if we ever have a class hierarchy where the base class is not
1547 // a primary base in the complete object.
1548 if (!isBuildingConstructorVTable() && OverriddenMD != MD) {
1549 // Compute the this adjustment.
1550 ThisAdjustment ThisAdjustment =
1551 ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass,
1554 if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&
1555 Overrider.Method->getParent() == MostDerivedClass) {
1557 // There's no return adjustment from OverriddenMD and MD,
1558 // but that doesn't mean there isn't one between MD and
1559 // the final overrider.
1560 BaseOffset ReturnAdjustmentOffset =
1561 ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
1562 ReturnAdjustment ReturnAdjustment =
1563 ComputeReturnAdjustment(ReturnAdjustmentOffset);
1565 // This is a virtual thunk for the most derived class, add it.
1566 AddThunk(Overrider.Method,
1567 ThunkInfo(ThisAdjustment, ReturnAdjustment));
1575 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1576 if (MD->isImplicit()) {
1577 // Itanium C++ ABI 2.5.2:
1578 // If a class has an implicitly-defined virtual destructor,
1579 // its entries come after the declared virtual function pointers.
1581 assert(!ImplicitVirtualDtor &&
1582 "Did already see an implicit virtual dtor!");
1583 ImplicitVirtualDtor = DD;
1588 NewVirtualFunctions.push_back(MD);
1591 if (ImplicitVirtualDtor)
1592 NewVirtualFunctions.push_back(ImplicitVirtualDtor);
1594 for (NewVirtualFunctionsTy::const_iterator I = NewVirtualFunctions.begin(),
1595 E = NewVirtualFunctions.end(); I != E; ++I) {
1596 const CXXMethodDecl *MD = *I;
1598 // Get the final overrider.
1599 FinalOverriders::OverriderInfo Overrider =
1600 Overriders.getOverrider(MD, Base.getBaseOffset());
1602 // Insert the method info for this method.
1603 MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1606 assert(!MethodInfoMap.count(MD) &&
1607 "Should not have method info for this method yet!");
1608 MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1610 // Check if this overrider is going to be used.
1611 const CXXMethodDecl *OverriderMD = Overrider.Method;
1612 if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass,
1613 FirstBaseInPrimaryBaseChain,
1614 FirstBaseOffsetInLayoutClass)) {
1615 Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD));
1619 // Check if this overrider needs a return adjustment.
1620 // We don't want to do this for pure virtual member functions.
1621 BaseOffset ReturnAdjustmentOffset;
1622 if (!OverriderMD->isPure()) {
1623 ReturnAdjustmentOffset =
1624 ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);
1627 ReturnAdjustment ReturnAdjustment =
1628 ComputeReturnAdjustment(ReturnAdjustmentOffset);
1630 AddMethod(Overrider.Method, ReturnAdjustment);
1634 void ItaniumVTableBuilder::LayoutVTable() {
1635 LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass,
1637 /*BaseIsMorallyVirtual=*/false,
1638 MostDerivedClassIsVirtual,
1639 MostDerivedClassOffset);
1641 VisitedVirtualBasesSetTy VBases;
1643 // Determine the primary virtual bases.
1644 DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset,
1648 LayoutVTablesForVirtualBases(MostDerivedClass, VBases);
1650 // -fapple-kext adds an extra entry at end of vtbl.
1651 bool IsAppleKext = Context.getLangOpts().AppleKext;
1653 Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));
1656 void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
1657 BaseSubobject Base, bool BaseIsMorallyVirtual,
1658 bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
1659 assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
1661 // Add vcall and vbase offsets for this vtable.
1662 VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders,
1663 Base, BaseIsVirtualInLayoutClass,
1664 OffsetInLayoutClass);
1665 Components.append(Builder.components_begin(), Builder.components_end());
1667 // Check if we need to add these vcall offsets.
1668 if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {
1669 VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];
1671 if (VCallOffsets.empty())
1672 VCallOffsets = Builder.getVCallOffsets();
1675 // If we're laying out the most derived class we want to keep track of the
1676 // virtual base class offset offsets.
1677 if (Base.getBase() == MostDerivedClass)
1678 VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();
1680 // Add the offset to top.
1681 CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;
1682 Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop));
1684 // Next, add the RTTI.
1685 Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
1687 uint64_t AddressPoint = Components.size();
1689 // Now go through all virtual member functions and add them.
1690 PrimaryBasesSetVectorTy PrimaryBases;
1691 AddMethods(Base, OffsetInLayoutClass,
1692 Base.getBase(), OffsetInLayoutClass,
1695 const CXXRecordDecl *RD = Base.getBase();
1696 if (RD == MostDerivedClass) {
1697 assert(MethodVTableIndices.empty());
1698 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
1699 E = MethodInfoMap.end(); I != E; ++I) {
1700 const CXXMethodDecl *MD = I->first;
1701 const MethodInfo &MI = I->second;
1702 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1703 MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]
1704 = MI.VTableIndex - AddressPoint;
1705 MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]
1706 = MI.VTableIndex + 1 - AddressPoint;
1708 MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;
1713 // Compute 'this' pointer adjustments.
1714 ComputeThisAdjustments();
1716 // Add all address points.
1718 AddressPoints.insert(std::make_pair(
1719 BaseSubobject(RD, OffsetInLayoutClass),
1722 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1723 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1728 if (Layout.isPrimaryBaseVirtual()) {
1729 // Check if this virtual primary base is a primary base in the layout
1730 // class. If it's not, we don't want to add it.
1731 const ASTRecordLayout &LayoutClassLayout =
1732 Context.getASTRecordLayout(LayoutClass);
1734 if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1735 OffsetInLayoutClass) {
1736 // We don't want to add this class (or any of its primary bases).
1744 // Layout secondary vtables.
1745 LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);
1749 ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
1750 bool BaseIsMorallyVirtual,
1751 CharUnits OffsetInLayoutClass) {
1752 // Itanium C++ ABI 2.5.2:
1753 // Following the primary virtual table of a derived class are secondary
1754 // virtual tables for each of its proper base classes, except any primary
1755 // base(s) with which it shares its primary virtual table.
1757 const CXXRecordDecl *RD = Base.getBase();
1758 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1759 const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1761 for (const auto &B : RD->bases()) {
1762 // Ignore virtual bases, we'll emit them later.
1766 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1768 // Ignore bases that don't have a vtable.
1769 if (!BaseDecl->isDynamicClass())
1772 if (isBuildingConstructorVTable()) {
1773 // Itanium C++ ABI 2.6.4:
1774 // Some of the base class subobjects may not need construction virtual
1775 // tables, which will therefore not be present in the construction
1776 // virtual table group, even though the subobject virtual tables are
1777 // present in the main virtual table group for the complete object.
1778 if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases())
1782 // Get the base offset of this base.
1783 CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(BaseDecl);
1784 CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset;
1786 CharUnits BaseOffsetInLayoutClass =
1787 OffsetInLayoutClass + RelativeBaseOffset;
1789 // Don't emit a secondary vtable for a primary base. We might however want
1790 // to emit secondary vtables for other bases of this base.
1791 if (BaseDecl == PrimaryBase) {
1792 LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset),
1793 BaseIsMorallyVirtual, BaseOffsetInLayoutClass);
1797 // Layout the primary vtable (and any secondary vtables) for this base.
1798 LayoutPrimaryAndSecondaryVTables(
1799 BaseSubobject(BaseDecl, BaseOffset),
1800 BaseIsMorallyVirtual,
1801 /*BaseIsVirtualInLayoutClass=*/false,
1802 BaseOffsetInLayoutClass);
1806 void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
1807 const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
1808 VisitedVirtualBasesSetTy &VBases) {
1809 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1811 // Check if this base has a primary base.
1812 if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1814 // Check if it's virtual.
1815 if (Layout.isPrimaryBaseVirtual()) {
1816 bool IsPrimaryVirtualBase = true;
1818 if (isBuildingConstructorVTable()) {
1819 // Check if the base is actually a primary base in the class we use for
1821 const ASTRecordLayout &LayoutClassLayout =
1822 Context.getASTRecordLayout(LayoutClass);
1824 CharUnits PrimaryBaseOffsetInLayoutClass =
1825 LayoutClassLayout.getVBaseClassOffset(PrimaryBase);
1827 // We know that the base is not a primary base in the layout class if
1828 // the base offsets are different.
1829 if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)
1830 IsPrimaryVirtualBase = false;
1833 if (IsPrimaryVirtualBase)
1834 PrimaryVirtualBases.insert(PrimaryBase);
1838 // Traverse bases, looking for more primary virtual bases.
1839 for (const auto &B : RD->bases()) {
1840 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1842 CharUnits BaseOffsetInLayoutClass;
1844 if (B.isVirtual()) {
1845 if (!VBases.insert(BaseDecl))
1848 const ASTRecordLayout &LayoutClassLayout =
1849 Context.getASTRecordLayout(LayoutClass);
1851 BaseOffsetInLayoutClass =
1852 LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1854 BaseOffsetInLayoutClass =
1855 OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl);
1858 DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases);
1862 void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
1863 const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) {
1864 // Itanium C++ ABI 2.5.2:
1865 // Then come the virtual base virtual tables, also in inheritance graph
1866 // order, and again excluding primary bases (which share virtual tables with
1867 // the classes for which they are primary).
1868 for (const auto &B : RD->bases()) {
1869 const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1871 // Check if this base needs a vtable. (If it's virtual, not a primary base
1872 // of some other class, and we haven't visited it before).
1873 if (B.isVirtual() && BaseDecl->isDynamicClass() &&
1874 !PrimaryVirtualBases.count(BaseDecl) && VBases.insert(BaseDecl)) {
1875 const ASTRecordLayout &MostDerivedClassLayout =
1876 Context.getASTRecordLayout(MostDerivedClass);
1877 CharUnits BaseOffset =
1878 MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
1880 const ASTRecordLayout &LayoutClassLayout =
1881 Context.getASTRecordLayout(LayoutClass);
1882 CharUnits BaseOffsetInLayoutClass =
1883 LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1885 LayoutPrimaryAndSecondaryVTables(
1886 BaseSubobject(BaseDecl, BaseOffset),
1887 /*BaseIsMorallyVirtual=*/true,
1888 /*BaseIsVirtualInLayoutClass=*/true,
1889 BaseOffsetInLayoutClass);
1892 // We only need to check the base for virtual base vtables if it actually
1893 // has virtual bases.
1894 if (BaseDecl->getNumVBases())
1895 LayoutVTablesForVirtualBases(BaseDecl, VBases);
1899 /// dumpLayout - Dump the vtable layout.
1900 void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {
1901 // FIXME: write more tests that actually use the dumpLayout output to prevent
1902 // ItaniumVTableBuilder regressions.
1904 if (isBuildingConstructorVTable()) {
1905 Out << "Construction vtable for ('";
1906 MostDerivedClass->printQualifiedName(Out);
1908 Out << MostDerivedClassOffset.getQuantity() << ") in '";
1909 LayoutClass->printQualifiedName(Out);
1911 Out << "Vtable for '";
1912 MostDerivedClass->printQualifiedName(Out);
1914 Out << "' (" << Components.size() << " entries).\n";
1916 // Iterate through the address points and insert them into a new map where
1917 // they are keyed by the index and not the base object.
1918 // Since an address point can be shared by multiple subobjects, we use an
1920 std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;
1921 for (AddressPointsMapTy::const_iterator I = AddressPoints.begin(),
1922 E = AddressPoints.end(); I != E; ++I) {
1923 const BaseSubobject& Base = I->first;
1924 uint64_t Index = I->second;
1926 AddressPointsByIndex.insert(std::make_pair(Index, Base));
1929 for (unsigned I = 0, E = Components.size(); I != E; ++I) {
1932 Out << llvm::format("%4d | ", I);
1934 const VTableComponent &Component = Components[I];
1936 // Dump the component.
1937 switch (Component.getKind()) {
1939 case VTableComponent::CK_VCallOffset:
1940 Out << "vcall_offset ("
1941 << Component.getVCallOffset().getQuantity()
1945 case VTableComponent::CK_VBaseOffset:
1946 Out << "vbase_offset ("
1947 << Component.getVBaseOffset().getQuantity()
1951 case VTableComponent::CK_OffsetToTop:
1952 Out << "offset_to_top ("
1953 << Component.getOffsetToTop().getQuantity()
1957 case VTableComponent::CK_RTTI:
1958 Component.getRTTIDecl()->printQualifiedName(Out);
1962 case VTableComponent::CK_FunctionPointer: {
1963 const CXXMethodDecl *MD = Component.getFunctionDecl();
1966 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
1972 if (MD->isDeleted())
1973 Out << " [deleted]";
1975 ThunkInfo Thunk = VTableThunks.lookup(I);
1976 if (!Thunk.isEmpty()) {
1977 // If this function pointer has a return adjustment, dump it.
1978 if (!Thunk.Return.isEmpty()) {
1979 Out << "\n [return adjustment: ";
1980 Out << Thunk.Return.NonVirtual << " non-virtual";
1982 if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
1983 Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
1984 Out << " vbase offset offset";
1990 // If this function pointer has a 'this' pointer adjustment, dump it.
1991 if (!Thunk.This.isEmpty()) {
1992 Out << "\n [this adjustment: ";
1993 Out << Thunk.This.NonVirtual << " non-virtual";
1995 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
1996 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
1997 Out << " vcall offset offset";
2007 case VTableComponent::CK_CompleteDtorPointer:
2008 case VTableComponent::CK_DeletingDtorPointer: {
2010 Component.getKind() == VTableComponent::CK_CompleteDtorPointer;
2012 const CXXDestructorDecl *DD = Component.getDestructorDecl();
2014 DD->printQualifiedName(Out);
2016 Out << "() [complete]";
2018 Out << "() [deleting]";
2023 ThunkInfo Thunk = VTableThunks.lookup(I);
2024 if (!Thunk.isEmpty()) {
2025 // If this destructor has a 'this' pointer adjustment, dump it.
2026 if (!Thunk.This.isEmpty()) {
2027 Out << "\n [this adjustment: ";
2028 Out << Thunk.This.NonVirtual << " non-virtual";
2030 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2031 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2032 Out << " vcall offset offset";
2042 case VTableComponent::CK_UnusedFunctionPointer: {
2043 const CXXMethodDecl *MD = Component.getUnusedFunctionDecl();
2046 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2048 Out << "[unused] " << Str;
2057 // Dump the next address point.
2058 uint64_t NextIndex = Index + 1;
2059 if (AddressPointsByIndex.count(NextIndex)) {
2060 if (AddressPointsByIndex.count(NextIndex) == 1) {
2061 const BaseSubobject &Base =
2062 AddressPointsByIndex.find(NextIndex)->second;
2065 Base.getBase()->printQualifiedName(Out);
2066 Out << ", " << Base.getBaseOffset().getQuantity();
2067 Out << ") vtable address --\n";
2069 CharUnits BaseOffset =
2070 AddressPointsByIndex.lower_bound(NextIndex)->second.getBaseOffset();
2072 // We store the class names in a set to get a stable order.
2073 std::set<std::string> ClassNames;
2074 for (std::multimap<uint64_t, BaseSubobject>::const_iterator I =
2075 AddressPointsByIndex.lower_bound(NextIndex), E =
2076 AddressPointsByIndex.upper_bound(NextIndex); I != E; ++I) {
2077 assert(I->second.getBaseOffset() == BaseOffset &&
2078 "Invalid base offset!");
2079 const CXXRecordDecl *RD = I->second.getBase();
2080 ClassNames.insert(RD->getQualifiedNameAsString());
2083 for (std::set<std::string>::const_iterator I = ClassNames.begin(),
2084 E = ClassNames.end(); I != E; ++I) {
2085 Out << " -- (" << *I;
2086 Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n";
2094 if (isBuildingConstructorVTable())
2097 if (MostDerivedClass->getNumVBases()) {
2098 // We store the virtual base class names and their offsets in a map to get
2101 std::map<std::string, CharUnits> ClassNamesAndOffsets;
2102 for (VBaseOffsetOffsetsMapTy::const_iterator I = VBaseOffsetOffsets.begin(),
2103 E = VBaseOffsetOffsets.end(); I != E; ++I) {
2104 std::string ClassName = I->first->getQualifiedNameAsString();
2105 CharUnits OffsetOffset = I->second;
2106 ClassNamesAndOffsets.insert(
2107 std::make_pair(ClassName, OffsetOffset));
2110 Out << "Virtual base offset offsets for '";
2111 MostDerivedClass->printQualifiedName(Out);
2113 Out << ClassNamesAndOffsets.size();
2114 Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n";
2116 for (std::map<std::string, CharUnits>::const_iterator I =
2117 ClassNamesAndOffsets.begin(), E = ClassNamesAndOffsets.end();
2119 Out << " " << I->first << " | " << I->second.getQuantity() << '\n';
2124 if (!Thunks.empty()) {
2125 // We store the method names in a map to get a stable order.
2126 std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
2128 for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end();
2130 const CXXMethodDecl *MD = I->first;
2131 std::string MethodName =
2132 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2135 MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
2138 for (std::map<std::string, const CXXMethodDecl *>::const_iterator I =
2139 MethodNamesAndDecls.begin(), E = MethodNamesAndDecls.end();
2141 const std::string &MethodName = I->first;
2142 const CXXMethodDecl *MD = I->second;
2144 ThunkInfoVectorTy ThunksVector = Thunks[MD];
2145 std::sort(ThunksVector.begin(), ThunksVector.end(),
2146 [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
2147 assert(LHS.Method == nullptr && RHS.Method == nullptr);
2148 return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
2151 Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
2152 Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
2154 for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
2155 const ThunkInfo &Thunk = ThunksVector[I];
2157 Out << llvm::format("%4d | ", I);
2159 // If this function pointer has a return pointer adjustment, dump it.
2160 if (!Thunk.Return.isEmpty()) {
2161 Out << "return adjustment: " << Thunk.Return.NonVirtual;
2162 Out << " non-virtual";
2163 if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
2164 Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
2165 Out << " vbase offset offset";
2168 if (!Thunk.This.isEmpty())
2172 // If this function pointer has a 'this' pointer adjustment, dump it.
2173 if (!Thunk.This.isEmpty()) {
2174 Out << "this adjustment: ";
2175 Out << Thunk.This.NonVirtual << " non-virtual";
2177 if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2178 Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2179 Out << " vcall offset offset";
2190 // Compute the vtable indices for all the member functions.
2191 // Store them in a map keyed by the index so we'll get a sorted table.
2192 std::map<uint64_t, std::string> IndicesMap;
2194 for (const auto *MD : MostDerivedClass->methods()) {
2195 // We only want virtual member functions.
2196 if (!MD->isVirtual())
2199 std::string MethodName =
2200 PredefinedExpr::ComputeName(PredefinedExpr::PrettyFunctionNoVirtual,
2203 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2204 GlobalDecl GD(DD, Dtor_Complete);
2205 assert(MethodVTableIndices.count(GD));
2206 uint64_t VTableIndex = MethodVTableIndices[GD];
2207 IndicesMap[VTableIndex] = MethodName + " [complete]";
2208 IndicesMap[VTableIndex + 1] = MethodName + " [deleting]";
2210 assert(MethodVTableIndices.count(MD));
2211 IndicesMap[MethodVTableIndices[MD]] = MethodName;
2215 // Print the vtable indices for all the member functions.
2216 if (!IndicesMap.empty()) {
2217 Out << "VTable indices for '";
2218 MostDerivedClass->printQualifiedName(Out);
2219 Out << "' (" << IndicesMap.size() << " entries).\n";
2221 for (std::map<uint64_t, std::string>::const_iterator I = IndicesMap.begin(),
2222 E = IndicesMap.end(); I != E; ++I) {
2223 uint64_t VTableIndex = I->first;
2224 const std::string &MethodName = I->second;
2226 Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName
2235 VTableLayout::VTableLayout(uint64_t NumVTableComponents,
2236 const VTableComponent *VTableComponents,
2237 uint64_t NumVTableThunks,
2238 const VTableThunkTy *VTableThunks,
2239 const AddressPointsMapTy &AddressPoints,
2240 bool IsMicrosoftABI)
2241 : NumVTableComponents(NumVTableComponents),
2242 VTableComponents(new VTableComponent[NumVTableComponents]),
2243 NumVTableThunks(NumVTableThunks),
2244 VTableThunks(new VTableThunkTy[NumVTableThunks]),
2245 AddressPoints(AddressPoints),
2246 IsMicrosoftABI(IsMicrosoftABI) {
2247 std::copy(VTableComponents, VTableComponents+NumVTableComponents,
2248 this->VTableComponents.get());
2249 std::copy(VTableThunks, VTableThunks+NumVTableThunks,
2250 this->VTableThunks.get());
2251 std::sort(this->VTableThunks.get(),
2252 this->VTableThunks.get() + NumVTableThunks,
2253 [](const VTableLayout::VTableThunkTy &LHS,
2254 const VTableLayout::VTableThunkTy &RHS) {
2255 assert((LHS.first != RHS.first || LHS.second == RHS.second) &&
2256 "Different thunks should have unique indices!");
2257 return LHS.first < RHS.first;
2261 VTableLayout::~VTableLayout() { }
2263 ItaniumVTableContext::ItaniumVTableContext(ASTContext &Context)
2264 : VTableContextBase(/*MS=*/false) {}
2266 ItaniumVTableContext::~ItaniumVTableContext() {
2267 llvm::DeleteContainerSeconds(VTableLayouts);
2270 uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {
2271 MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD);
2272 if (I != MethodVTableIndices.end())
2275 const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
2277 computeVTableRelatedInformation(RD);
2279 I = MethodVTableIndices.find(GD);
2280 assert(I != MethodVTableIndices.end() && "Did not find index!");
2285 ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
2286 const CXXRecordDecl *VBase) {
2287 ClassPairTy ClassPair(RD, VBase);
2289 VirtualBaseClassOffsetOffsetsMapTy::iterator I =
2290 VirtualBaseClassOffsetOffsets.find(ClassPair);
2291 if (I != VirtualBaseClassOffsetOffsets.end())
2294 VCallAndVBaseOffsetBuilder Builder(RD, RD, /*FinalOverriders=*/nullptr,
2295 BaseSubobject(RD, CharUnits::Zero()),
2296 /*BaseIsVirtual=*/false,
2297 /*OffsetInLayoutClass=*/CharUnits::Zero());
2299 for (VCallAndVBaseOffsetBuilder::VBaseOffsetOffsetsMapTy::const_iterator I =
2300 Builder.getVBaseOffsetOffsets().begin(),
2301 E = Builder.getVBaseOffsetOffsets().end(); I != E; ++I) {
2302 // Insert all types.
2303 ClassPairTy ClassPair(RD, I->first);
2305 VirtualBaseClassOffsetOffsets.insert(
2306 std::make_pair(ClassPair, I->second));
2309 I = VirtualBaseClassOffsetOffsets.find(ClassPair);
2310 assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");
2315 static VTableLayout *CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
2316 SmallVector<VTableLayout::VTableThunkTy, 1>
2317 VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
2319 return new VTableLayout(Builder.getNumVTableComponents(),
2320 Builder.vtable_component_begin(),
2321 VTableThunks.size(),
2322 VTableThunks.data(),
2323 Builder.getAddressPoints(),
2324 /*IsMicrosoftABI=*/false);
2328 ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
2329 const VTableLayout *&Entry = VTableLayouts[RD];
2331 // Check if we've computed this information before.
2335 ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),
2336 /*MostDerivedClassIsVirtual=*/0, RD);
2337 Entry = CreateVTableLayout(Builder);
2339 MethodVTableIndices.insert(Builder.vtable_indices_begin(),
2340 Builder.vtable_indices_end());
2342 // Add the known thunks.
2343 Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
2345 // If we don't have the vbase information for this class, insert it.
2346 // getVirtualBaseOffsetOffset will compute it separately without computing
2347 // the rest of the vtable related information.
2348 if (!RD->getNumVBases())
2351 const CXXRecordDecl *VBase =
2352 RD->vbases_begin()->getType()->getAsCXXRecordDecl();
2354 if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase)))
2357 for (ItaniumVTableBuilder::VBaseOffsetOffsetsMapTy::const_iterator
2358 I = Builder.getVBaseOffsetOffsets().begin(),
2359 E = Builder.getVBaseOffsetOffsets().end();
2361 // Insert all types.
2362 ClassPairTy ClassPair(RD, I->first);
2364 VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I->second));
2368 VTableLayout *ItaniumVTableContext::createConstructionVTableLayout(
2369 const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
2370 bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {
2371 ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,
2372 MostDerivedClassIsVirtual, LayoutClass);
2373 return CreateVTableLayout(Builder);
2378 // Vtables in the Microsoft ABI are different from the Itanium ABI.
2380 // The main differences are:
2381 // 1. Separate vftable and vbtable.
2383 // 2. Each subobject with a vfptr gets its own vftable rather than an address
2384 // point in a single vtable shared between all the subobjects.
2385 // Each vftable is represented by a separate section and virtual calls
2386 // must be done using the vftable which has a slot for the function to be
2389 // 3. Virtual method definitions expect their 'this' parameter to point to the
2390 // first vfptr whose table provides a compatible overridden method. In many
2391 // cases, this permits the original vf-table entry to directly call
2392 // the method instead of passing through a thunk.
2394 // A compatible overridden method is one which does not have a non-trivial
2395 // covariant-return adjustment.
2397 // The first vfptr is the one with the lowest offset in the complete-object
2398 // layout of the defining class, and the method definition will subtract
2399 // that constant offset from the parameter value to get the real 'this'
2400 // value. Therefore, if the offset isn't really constant (e.g. if a virtual
2401 // function defined in a virtual base is overridden in a more derived
2402 // virtual base and these bases have a reverse order in the complete
2403 // object), the vf-table may require a this-adjustment thunk.
2405 // 4. vftables do not contain new entries for overrides that merely require
2406 // this-adjustment. Together with #3, this keeps vf-tables smaller and
2407 // eliminates the need for this-adjustment thunks in many cases, at the cost
2408 // of often requiring redundant work to adjust the "this" pointer.
2410 // 5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.
2411 // Vtordisps are emitted into the class layout if a class has
2412 // a) a user-defined ctor/dtor
2414 // b) a method overriding a method in a virtual base.
2416 class VFTableBuilder {
2418 typedef MicrosoftVTableContext::MethodVFTableLocation MethodVFTableLocation;
2420 typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
2421 MethodVFTableLocationsTy;
2423 typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator>
2424 method_locations_range;
2427 /// VTables - Global vtable information.
2428 MicrosoftVTableContext &VTables;
2430 /// Context - The ASTContext which we will use for layout information.
2431 ASTContext &Context;
2433 /// MostDerivedClass - The most derived class for which we're building this
2435 const CXXRecordDecl *MostDerivedClass;
2437 const ASTRecordLayout &MostDerivedClassLayout;
2439 const VPtrInfo &WhichVFPtr;
2441 /// FinalOverriders - The final overriders of the most derived class.
2442 const FinalOverriders Overriders;
2444 /// Components - The components of the vftable being built.
2445 SmallVector<VTableComponent, 64> Components;
2447 MethodVFTableLocationsTy MethodVFTableLocations;
2449 /// \brief Does this class have an RTTI component?
2450 bool HasRTTIComponent;
2452 /// MethodInfo - Contains information about a method in a vtable.
2453 /// (Used for computing 'this' pointer adjustment thunks.
2455 /// VBTableIndex - The nonzero index in the vbtable that
2456 /// this method's base has, or zero.
2457 const uint64_t VBTableIndex;
2459 /// VFTableIndex - The index in the vftable that this method has.
2460 const uint64_t VFTableIndex;
2462 /// Shadowed - Indicates if this vftable slot is shadowed by
2463 /// a slot for a covariant-return override. If so, it shouldn't be printed
2464 /// or used for vcalls in the most derived class.
2467 MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex)
2468 : VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),
2471 MethodInfo() : VBTableIndex(0), VFTableIndex(0), Shadowed(false) {}
2474 typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
2476 /// MethodInfoMap - The information for all methods in the vftable we're
2477 /// currently building.
2478 MethodInfoMapTy MethodInfoMap;
2480 typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
2482 /// VTableThunks - The thunks by vftable index in the vftable currently being
2484 VTableThunksMapTy VTableThunks;
2486 typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
2487 typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
2489 /// Thunks - A map that contains all the thunks needed for all methods in the
2490 /// most derived class for which the vftable is currently being built.
2493 /// AddThunk - Add a thunk for the given method.
2494 void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) {
2495 SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD];
2497 // Check if we have this thunk already.
2498 if (std::find(ThunksVector.begin(), ThunksVector.end(), Thunk) !=
2502 ThunksVector.push_back(Thunk);
2505 /// ComputeThisOffset - Returns the 'this' argument offset for the given
2506 /// method, relative to the beginning of the MostDerivedClass.
2507 CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider);
2509 void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,
2510 CharUnits ThisOffset, ThisAdjustment &TA);
2512 /// AddMethod - Add a single virtual member function to the vftable
2513 /// components vector.
2514 void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {
2515 if (!TI.isEmpty()) {
2516 VTableThunks[Components.size()] = TI;
2519 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2520 assert(TI.Return.isEmpty() &&
2521 "Destructor can't have return adjustment!");
2522 Components.push_back(VTableComponent::MakeDeletingDtor(DD));
2524 Components.push_back(VTableComponent::MakeFunction(MD));
2528 bool NeedsReturnAdjustingThunk(const CXXMethodDecl *MD);
2530 /// AddMethods - Add the methods of this base subobject and the relevant
2531 /// subbases to the vftable we're currently laying out.
2532 void AddMethods(BaseSubobject Base, unsigned BaseDepth,
2533 const CXXRecordDecl *LastVBase,
2534 BasesSetVectorTy &VisitedBases);
2536 void LayoutVFTable() {
2537 // FIXME: add support for RTTI when we have proper LLVM support for symbols
2538 // pointing to the middle of a section.
2540 BasesSetVectorTy VisitedBases;
2541 AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr,
2543 assert(Components.size() && "vftable can't be empty");
2545 assert(MethodVFTableLocations.empty());
2546 for (MethodInfoMapTy::const_iterator I = MethodInfoMap.begin(),
2547 E = MethodInfoMap.end(); I != E; ++I) {
2548 const CXXMethodDecl *MD = I->first;
2549 const MethodInfo &MI = I->second;
2550 // Skip the methods that the MostDerivedClass didn't override
2551 // and the entries shadowed by return adjusting thunks.
2552 if (MD->getParent() != MostDerivedClass || MI.Shadowed)
2554 MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),
2555 WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);
2556 if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2557 MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;
2559 MethodVFTableLocations[MD] = Loc;
2564 void ErrorUnsupported(StringRef Feature, SourceLocation Location) {
2565 clang::DiagnosticsEngine &Diags = Context.getDiagnostics();
2566 unsigned DiagID = Diags.getCustomDiagID(
2567 DiagnosticsEngine::Error, "v-table layout for %0 is not supported yet");
2568 Diags.Report(Context.getFullLoc(Location), DiagID) << Feature;
2572 VFTableBuilder(MicrosoftVTableContext &VTables,
2573 const CXXRecordDecl *MostDerivedClass, const VPtrInfo *Which)
2575 Context(MostDerivedClass->getASTContext()),
2576 MostDerivedClass(MostDerivedClass),
2577 MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)),
2579 Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) {
2580 // Only include the RTTI component if we know that we will provide a
2581 // definition of the vftable.
2582 HasRTTIComponent = Context.getLangOpts().RTTIData &&
2583 !MostDerivedClass->hasAttr<DLLImportAttr>();
2584 if (HasRTTIComponent)
2585 Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
2589 if (Context.getLangOpts().DumpVTableLayouts)
2590 dumpLayout(llvm::outs());
2593 uint64_t getNumThunks() const { return Thunks.size(); }
2595 ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
2597 ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
2599 method_locations_range vtable_locations() const {
2600 return method_locations_range(MethodVFTableLocations.begin(),
2601 MethodVFTableLocations.end());
2604 uint64_t getNumVTableComponents() const { return Components.size(); }
2606 const VTableComponent *vtable_component_begin() const {
2607 return Components.begin();
2610 const VTableComponent *vtable_component_end() const {
2611 return Components.end();
2614 VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
2615 return VTableThunks.begin();
2618 VTableThunksMapTy::const_iterator vtable_thunks_end() const {
2619 return VTableThunks.end();
2622 void dumpLayout(raw_ostream &);
2627 /// InitialOverriddenDefinitionCollector - Finds the set of least derived bases
2628 /// that define the given method.
2629 struct InitialOverriddenDefinitionCollector {
2630 BasesSetVectorTy Bases;
2631 OverriddenMethodsSetTy VisitedOverriddenMethods;
2633 bool visit(const CXXMethodDecl *OverriddenMD) {
2634 if (OverriddenMD->size_overridden_methods() == 0)
2635 Bases.insert(OverriddenMD->getParent());
2636 // Don't recurse on this method if we've already collected it.
2637 return VisitedOverriddenMethods.insert(OverriddenMD);
2641 static bool BaseInSet(const CXXBaseSpecifier *Specifier,
2642 CXXBasePath &Path, void *BasesSet) {
2643 BasesSetVectorTy *Bases = (BasesSetVectorTy *)BasesSet;
2644 return Bases->count(Specifier->getType()->getAsCXXRecordDecl());
2648 VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {
2649 InitialOverriddenDefinitionCollector Collector;
2650 visitAllOverriddenMethods(Overrider.Method, Collector);
2652 // If there are no overrides then 'this' is located
2653 // in the base that defines the method.
2654 if (Collector.Bases.size() == 0)
2655 return Overrider.Offset;
2658 Overrider.Method->getParent()->lookupInBases(BaseInSet, &Collector.Bases,
2661 // This will hold the smallest this offset among overridees of MD.
2662 // This implies that an offset of a non-virtual base will dominate an offset
2663 // of a virtual base to potentially reduce the number of thunks required
2664 // in the derived classes that inherit this method.
2668 const ASTRecordLayout &OverriderRDLayout =
2669 Context.getASTRecordLayout(Overrider.Method->getParent());
2670 for (CXXBasePaths::paths_iterator I = Paths.begin(), E = Paths.end();
2672 const CXXBasePath &Path = (*I);
2673 CharUnits ThisOffset = Overrider.Offset;
2674 CharUnits LastVBaseOffset;
2676 // For each path from the overrider to the parents of the overridden methods,
2677 // traverse the path, calculating the this offset in the most derived class.
2678 for (int J = 0, F = Path.size(); J != F; ++J) {
2679 const CXXBasePathElement &Element = Path[J];
2680 QualType CurTy = Element.Base->getType();
2681 const CXXRecordDecl *PrevRD = Element.Class,
2682 *CurRD = CurTy->getAsCXXRecordDecl();
2683 const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);
2685 if (Element.Base->isVirtual()) {
2686 // The interesting things begin when you have virtual inheritance.
2687 // The final overrider will use a static adjustment equal to the offset
2688 // of the vbase in the final overrider class.
2689 // For example, if the final overrider is in a vbase B of the most
2690 // derived class and it overrides a method of the B's own vbase A,
2691 // it uses A* as "this". In its prologue, it can cast A* to B* with
2692 // a static offset. This offset is used regardless of the actual
2693 // offset of A from B in the most derived class, requiring an
2694 // this-adjusting thunk in the vftable if A and B are laid out
2695 // differently in the most derived class.
2696 LastVBaseOffset = ThisOffset =
2697 Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(CurRD);
2699 ThisOffset += Layout.getBaseClassOffset(CurRD);
2703 if (isa<CXXDestructorDecl>(Overrider.Method)) {
2704 if (LastVBaseOffset.isZero()) {
2705 // If a "Base" class has at least one non-virtual base with a virtual
2706 // destructor, the "Base" virtual destructor will take the address
2707 // of the "Base" subobject as the "this" argument.
2708 ThisOffset = Overrider.Offset;
2710 // A virtual destructor of a virtual base takes the address of the
2711 // virtual base subobject as the "this" argument.
2712 ThisOffset = LastVBaseOffset;
2716 if (Ret > ThisOffset || First) {
2722 assert(!First && "Method not found in the given subobject?");
2726 void VFTableBuilder::CalculateVtordispAdjustment(
2727 FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,
2728 ThisAdjustment &TA) {
2729 const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap =
2730 MostDerivedClassLayout.getVBaseOffsetsMap();
2731 const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry =
2732 VBaseMap.find(WhichVFPtr.getVBaseWithVPtr());
2733 assert(VBaseMapEntry != VBaseMap.end());
2735 // If there's no vtordisp or the final overrider is defined in the same vbase
2736 // as the initial declaration, we don't need any vtordisp adjustment.
2737 if (!VBaseMapEntry->second.hasVtorDisp() ||
2738 Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())
2741 // OK, now we know we need to use a vtordisp thunk.
2742 // The implicit vtordisp field is located right before the vbase.
2743 CharUnits VFPtrVBaseOffset = VBaseMapEntry->second.VBaseOffset;
2744 TA.Virtual.Microsoft.VtordispOffset =
2745 (VFPtrVBaseOffset - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4;
2747 // A simple vtordisp thunk will suffice if the final overrider is defined
2748 // in either the most derived class or its non-virtual base.
2749 if (Overrider.Method->getParent() == MostDerivedClass ||
2750 !Overrider.VirtualBase)
2753 // Otherwise, we need to do use the dynamic offset of the final overrider
2754 // in order to get "this" adjustment right.
2755 TA.Virtual.Microsoft.VBPtrOffset =
2756 (VFPtrVBaseOffset + WhichVFPtr.NonVirtualOffset -
2757 MostDerivedClassLayout.getVBPtrOffset()).getQuantity();
2758 TA.Virtual.Microsoft.VBOffsetOffset =
2759 Context.getTypeSizeInChars(Context.IntTy).getQuantity() *
2760 VTables.getVBTableIndex(MostDerivedClass, Overrider.VirtualBase);
2762 TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity();
2765 static void GroupNewVirtualOverloads(
2766 const CXXRecordDecl *RD,
2767 SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) {
2768 // Put the virtual methods into VirtualMethods in the proper order:
2769 // 1) Group overloads by declaration name. New groups are added to the
2770 // vftable in the order of their first declarations in this class
2771 // (including overrides and non-virtual methods).
2772 // 2) In each group, new overloads appear in the reverse order of declaration.
2773 typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;
2774 SmallVector<MethodGroup, 10> Groups;
2775 typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;
2776 VisitedGroupIndicesTy VisitedGroupIndices;
2777 for (const auto *MD : RD->methods()) {
2778 VisitedGroupIndicesTy::iterator J;
2780 std::tie(J, Inserted) = VisitedGroupIndices.insert(
2781 std::make_pair(MD->getDeclName(), Groups.size()));
2783 Groups.push_back(MethodGroup());
2784 if (MD->isVirtual())
2785 Groups[J->second].push_back(MD);
2788 for (unsigned I = 0, E = Groups.size(); I != E; ++I)
2789 VirtualMethods.append(Groups[I].rbegin(), Groups[I].rend());
2792 /// We need a return adjusting thunk for this method if its return type is
2793 /// not trivially convertible to the return type of any of its overridden
2795 bool VFTableBuilder::NeedsReturnAdjustingThunk(const CXXMethodDecl *MD) {
2796 OverriddenMethodsSetTy OverriddenMethods;
2797 ComputeAllOverriddenMethods(MD, OverriddenMethods);
2798 for (OverriddenMethodsSetTy::iterator I = OverriddenMethods.begin(),
2799 E = OverriddenMethods.end();
2801 const CXXMethodDecl *OverriddenMD = *I;
2802 BaseOffset Adjustment =
2803 ComputeReturnAdjustmentBaseOffset(Context, MD, OverriddenMD);
2804 if (!Adjustment.isEmpty())
2810 static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {
2811 for (const auto &B : RD->bases()) {
2812 if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base)
2818 void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
2819 const CXXRecordDecl *LastVBase,
2820 BasesSetVectorTy &VisitedBases) {
2821 const CXXRecordDecl *RD = Base.getBase();
2822 if (!RD->isPolymorphic())
2825 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
2827 // See if this class expands a vftable of the base we look at, which is either
2828 // the one defined by the vfptr base path or the primary base of the current class.
2829 const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;
2830 CharUnits NextBaseOffset;
2831 if (BaseDepth < WhichVFPtr.PathToBaseWithVPtr.size()) {
2832 NextBase = WhichVFPtr.PathToBaseWithVPtr[BaseDepth];
2833 if (isDirectVBase(NextBase, RD)) {
2834 NextLastVBase = NextBase;
2835 NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase);
2838 Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase);
2840 } else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
2841 assert(!Layout.isPrimaryBaseVirtual() &&
2842 "No primary virtual bases in this ABI");
2843 NextBase = PrimaryBase;
2844 NextBaseOffset = Base.getBaseOffset();
2848 AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1,
2849 NextLastVBase, VisitedBases);
2850 if (!VisitedBases.insert(NextBase))
2851 llvm_unreachable("Found a duplicate primary base!");
2854 SmallVector<const CXXMethodDecl*, 10> VirtualMethods;
2855 // Put virtual methods in the proper order.
2856 GroupNewVirtualOverloads(RD, VirtualMethods);
2858 // Now go through all virtual member functions and add them to the current
2859 // vftable. This is done by
2860 // - replacing overridden methods in their existing slots, as long as they
2861 // don't require return adjustment; calculating This adjustment if needed.
2862 // - adding new slots for methods of the current base not present in any
2864 // - adding new slots for methods that require Return adjustment.
2865 // We keep track of the methods visited in the sub-bases in MethodInfoMap.
2866 for (unsigned I = 0, E = VirtualMethods.size(); I != E; ++I) {
2867 const CXXMethodDecl *MD = VirtualMethods[I];
2869 FinalOverriders::OverriderInfo Overrider =
2870 Overriders.getOverrider(MD, Base.getBaseOffset());
2871 const CXXMethodDecl *OverriderMD = Overrider.Method;
2872 const CXXMethodDecl *OverriddenMD =
2873 FindNearestOverriddenMethod(MD, VisitedBases);
2875 ThisAdjustment ThisAdjustmentOffset;
2876 bool ReturnAdjustingThunk = false;
2877 CharUnits ThisOffset = ComputeThisOffset(Overrider);
2878 ThisAdjustmentOffset.NonVirtual =
2879 (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();
2880 if ((OverriddenMD || OverriderMD != MD) &&
2881 WhichVFPtr.getVBaseWithVPtr())
2882 CalculateVtordispAdjustment(Overrider, ThisOffset, ThisAdjustmentOffset);
2885 // If MD overrides anything in this vftable, we need to update the entries.
2886 MethodInfoMapTy::iterator OverriddenMDIterator =
2887 MethodInfoMap.find(OverriddenMD);
2889 // If the overridden method went to a different vftable, skip it.
2890 if (OverriddenMDIterator == MethodInfoMap.end())
2893 MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;
2895 if (!NeedsReturnAdjustingThunk(MD)) {
2896 // No return adjustment needed - just replace the overridden method info
2897 // with the current info.
2898 MethodInfo MI(OverriddenMethodInfo.VBTableIndex,
2899 OverriddenMethodInfo.VFTableIndex);
2900 MethodInfoMap.erase(OverriddenMDIterator);
2902 assert(!MethodInfoMap.count(MD) &&
2903 "Should not have method info for this method yet!");
2904 MethodInfoMap.insert(std::make_pair(MD, MI));
2908 // In case we need a return adjustment, we'll add a new slot for
2909 // the overrider. Mark the overriden method as shadowed by the new slot.
2910 OverriddenMethodInfo.Shadowed = true;
2912 // Force a special name mangling for a return-adjusting thunk
2913 // unless the method is the final overrider without this adjustment.
2914 ReturnAdjustingThunk =
2915 !(MD == OverriderMD && ThisAdjustmentOffset.isEmpty());
2916 } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||
2917 MD->size_overridden_methods()) {
2918 // Skip methods that don't belong to the vftable of the current class,
2919 // e.g. each method that wasn't seen in any of the visited sub-bases
2920 // but overrides multiple methods of other sub-bases.
2924 // If we got here, MD is a method not seen in any of the sub-bases or
2925 // it requires return adjustment. Insert the method info for this method.
2927 LastVBase ? VTables.getVBTableIndex(MostDerivedClass, LastVBase) : 0;
2928 MethodInfo MI(VBIndex,
2929 HasRTTIComponent ? Components.size() - 1 : Components.size());
2931 assert(!MethodInfoMap.count(MD) &&
2932 "Should not have method info for this method yet!");
2933 MethodInfoMap.insert(std::make_pair(MD, MI));
2935 // Check if this overrider needs a return adjustment.
2936 // We don't want to do this for pure virtual member functions.
2937 BaseOffset ReturnAdjustmentOffset;
2938 ReturnAdjustment ReturnAdjustment;
2939 if (!OverriderMD->isPure()) {
2940 ReturnAdjustmentOffset =
2941 ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);
2943 if (!ReturnAdjustmentOffset.isEmpty()) {
2944 ReturnAdjustingThunk = true;
2945 ReturnAdjustment.NonVirtual =
2946 ReturnAdjustmentOffset.NonVirtualOffset.getQuantity();
2947 if (ReturnAdjustmentOffset.VirtualBase) {
2948 const ASTRecordLayout &DerivedLayout =
2949 Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass);
2950 ReturnAdjustment.Virtual.Microsoft.VBPtrOffset =
2951 DerivedLayout.getVBPtrOffset().getQuantity();
2952 ReturnAdjustment.Virtual.Microsoft.VBIndex =
2953 VTables.getVBTableIndex(ReturnAdjustmentOffset.DerivedClass,
2954 ReturnAdjustmentOffset.VirtualBase);
2958 AddMethod(OverriderMD, ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment,
2959 ReturnAdjustingThunk ? MD : nullptr));
2963 static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {
2964 for (VPtrInfo::BasePath::const_reverse_iterator I = Path.rbegin(),
2965 E = Path.rend(); I != E; ++I) {
2967 (*I)->printQualifiedName(Out);
2972 static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
2973 bool ContinueFirstLine) {
2974 const ReturnAdjustment &R = TI.Return;
2975 bool Multiline = false;
2976 const char *LinePrefix = "\n ";
2977 if (!R.isEmpty() || TI.Method) {
2978 if (!ContinueFirstLine)
2980 Out << "[return adjustment (to type '"
2981 << TI.Method->getReturnType().getCanonicalType().getAsString()
2983 if (R.Virtual.Microsoft.VBPtrOffset)
2984 Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";
2985 if (R.Virtual.Microsoft.VBIndex)
2986 Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";
2987 Out << R.NonVirtual << " non-virtual]";
2991 const ThisAdjustment &T = TI.This;
2993 if (Multiline || !ContinueFirstLine)
2995 Out << "[this adjustment: ";
2996 if (!TI.This.Virtual.isEmpty()) {
2997 assert(T.Virtual.Microsoft.VtordispOffset < 0);
2998 Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";
2999 if (T.Virtual.Microsoft.VBPtrOffset) {
3000 Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset
3002 assert(T.Virtual.Microsoft.VBOffsetOffset > 0);
3003 Out << LinePrefix << " vboffset at "
3004 << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";
3007 Out << T.NonVirtual << " non-virtual]";
3011 void VFTableBuilder::dumpLayout(raw_ostream &Out) {
3012 Out << "VFTable for ";
3013 PrintBasePath(WhichVFPtr.PathToBaseWithVPtr, Out);
3015 MostDerivedClass->printQualifiedName(Out);
3016 Out << "' (" << Components.size()
3017 << (Components.size() == 1 ? " entry" : " entries") << ").\n";
3019 for (unsigned I = 0, E = Components.size(); I != E; ++I) {
3020 Out << llvm::format("%4d | ", I);
3022 const VTableComponent &Component = Components[I];
3024 // Dump the component.
3025 switch (Component.getKind()) {
3026 case VTableComponent::CK_RTTI:
3027 Component.getRTTIDecl()->printQualifiedName(Out);
3031 case VTableComponent::CK_FunctionPointer: {
3032 const CXXMethodDecl *MD = Component.getFunctionDecl();
3034 // FIXME: Figure out how to print the real thunk type, since they can
3035 // differ in the return type.
3036 std::string Str = PredefinedExpr::ComputeName(
3037 PredefinedExpr::PrettyFunctionNoVirtual, MD);
3042 if (MD->isDeleted()) {
3043 ErrorUnsupported("deleted methods", MD->getLocation());
3044 Out << " [deleted]";
3047 ThunkInfo Thunk = VTableThunks.lookup(I);
3048 if (!Thunk.isEmpty())
3049 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3054 case VTableComponent::CK_DeletingDtorPointer: {
3055 const CXXDestructorDecl *DD = Component.getDestructorDecl();
3057 DD->printQualifiedName(Out);
3058 Out << "() [scalar deleting]";
3063 ThunkInfo Thunk = VTableThunks.lookup(I);
3064 if (!Thunk.isEmpty()) {
3065 assert(Thunk.Return.isEmpty() &&
3066 "No return adjustment needed for destructors!");
3067 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3074 DiagnosticsEngine &Diags = Context.getDiagnostics();
3075 unsigned DiagID = Diags.getCustomDiagID(
3076 DiagnosticsEngine::Error,
3077 "Unexpected vftable component type %0 for component number %1");
3078 Diags.Report(MostDerivedClass->getLocation(), DiagID)
3079 << I << Component.getKind();
3087 if (!Thunks.empty()) {
3088 // We store the method names in a map to get a stable order.
3089 std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
3091 for (ThunksMapTy::const_iterator I = Thunks.begin(), E = Thunks.end();
3093 const CXXMethodDecl *MD = I->first;
3094 std::string MethodName = PredefinedExpr::ComputeName(
3095 PredefinedExpr::PrettyFunctionNoVirtual, MD);
3097 MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
3100 for (std::map<std::string, const CXXMethodDecl *>::const_iterator
3101 I = MethodNamesAndDecls.begin(),
3102 E = MethodNamesAndDecls.end();
3104 const std::string &MethodName = I->first;
3105 const CXXMethodDecl *MD = I->second;
3107 ThunkInfoVectorTy ThunksVector = Thunks[MD];
3108 std::stable_sort(ThunksVector.begin(), ThunksVector.end(),
3109 [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
3110 // Keep different thunks with the same adjustments in the order they
3111 // were put into the vector.
3112 return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
3115 Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
3116 Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
3118 for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
3119 const ThunkInfo &Thunk = ThunksVector[I];
3121 Out << llvm::format("%4d | ", I);
3122 dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true);
3133 static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
3134 const ArrayRef<const CXXRecordDecl *> &B) {
3135 for (ArrayRef<const CXXRecordDecl *>::iterator I = B.begin(), E = B.end();
3143 static bool rebucketPaths(VPtrInfoVector &Paths);
3145 /// Produces MSVC-compatible vbtable data. The symbols produced by this
3146 /// algorithm match those produced by MSVC 2012 and newer, which is different
3149 /// MSVC 2012 appears to minimize the vbtable names using the following
3150 /// algorithm. First, walk the class hierarchy in the usual order, depth first,
3151 /// left to right, to find all of the subobjects which contain a vbptr field.
3152 /// Visiting each class node yields a list of inheritance paths to vbptrs. Each
3153 /// record with a vbptr creates an initially empty path.
3155 /// To combine paths from child nodes, the paths are compared to check for
3156 /// ambiguity. Paths are "ambiguous" if multiple paths have the same set of
3157 /// components in the same order. Each group of ambiguous paths is extended by
3158 /// appending the class of the base from which it came. If the current class
3159 /// node produced an ambiguous path, its path is extended with the current class.
3160 /// After extending paths, MSVC again checks for ambiguity, and extends any
3161 /// ambiguous path which wasn't already extended. Because each node yields an
3162 /// unambiguous set of paths, MSVC doesn't need to extend any path more than once
3163 /// to produce an unambiguous set of paths.
3165 /// TODO: Presumably vftables use the same algorithm.
3166 void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
3167 const CXXRecordDecl *RD,
3168 VPtrInfoVector &Paths) {
3169 assert(Paths.empty());
3170 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3172 // Base case: this subobject has its own vptr.
3173 if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr())
3174 Paths.push_back(new VPtrInfo(RD));
3176 // Recursive case: get all the vbtables from our bases and remove anything
3177 // that shares a virtual base.
3178 llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
3179 for (const auto &B : RD->bases()) {
3180 const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
3181 if (B.isVirtual() && VBasesSeen.count(Base))
3184 if (!Base->isDynamicClass())
3187 const VPtrInfoVector &BasePaths =
3188 ForVBTables ? enumerateVBTables(Base) : getVFPtrOffsets(Base);
3190 for (VPtrInfo *BaseInfo : BasePaths) {
3191 // Don't include the path if it goes through a virtual base that we've
3192 // already included.
3193 if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases))
3196 // Copy the path and adjust it as necessary.
3197 VPtrInfo *P = new VPtrInfo(*BaseInfo);
3199 // We mangle Base into the path if the path would've been ambiguous and it
3200 // wasn't already extended with Base.
3201 if (P->MangledPath.empty() || P->MangledPath.back() != Base)
3202 P->NextBaseToMangle = Base;
3204 // Keep track of the full path.
3205 // FIXME: Why do we need this?
3206 P->PathToBaseWithVPtr.insert(P->PathToBaseWithVPtr.begin(), Base);
3208 // Keep track of which vtable the derived class is going to extend with
3209 // new methods or bases. We append to either the vftable of our primary
3210 // base, or the first non-virtual base that has a vbtable.
3211 if (P->ReusingBase == Base &&
3212 Base == (ForVBTables ? Layout.getBaseSharingVBPtr()
3213 : Layout.getPrimaryBase()))
3214 P->ReusingBase = RD;
3216 // Keep track of the full adjustment from the MDC to this vtable. The
3217 // adjustment is captured by an optional vbase and a non-virtual offset.
3219 P->ContainingVBases.push_back(Base);
3220 else if (P->ContainingVBases.empty())
3221 P->NonVirtualOffset += Layout.getBaseClassOffset(Base);
3223 // Update the full offset in the MDC.
3224 P->FullOffsetInMDC = P->NonVirtualOffset;
3225 if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())
3226 P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB);
3232 VBasesSeen.insert(Base);
3234 // After visiting any direct base, we've transitively visited all of its
3235 // morally virtual bases.
3236 for (const auto &VB : Base->vbases())
3237 VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl());
3240 // Sort the paths into buckets, and if any of them are ambiguous, extend all
3241 // paths in ambiguous buckets.
3242 bool Changed = true;
3244 Changed = rebucketPaths(Paths);
3247 static bool extendPath(VPtrInfo *P) {
3248 if (P->NextBaseToMangle) {
3249 P->MangledPath.push_back(P->NextBaseToMangle);
3250 P->NextBaseToMangle = nullptr;// Prevent the path from being extended twice.
3256 static bool rebucketPaths(VPtrInfoVector &Paths) {
3257 // What we're essentially doing here is bucketing together ambiguous paths.
3258 // Any bucket with more than one path in it gets extended by NextBase, which
3259 // is usually the direct base of the inherited the vbptr. This code uses a
3260 // sorted vector to implement a multiset to form the buckets. Note that the
3261 // ordering is based on pointers, but it doesn't change our output order. The
3262 // current algorithm is designed to match MSVC 2012's names.
3263 VPtrInfoVector PathsSorted(Paths);
3264 std::sort(PathsSorted.begin(), PathsSorted.end(),
3265 [](const VPtrInfo *LHS, const VPtrInfo *RHS) {
3266 return LHS->MangledPath < RHS->MangledPath;
3268 bool Changed = false;
3269 for (size_t I = 0, E = PathsSorted.size(); I != E;) {
3270 // Scan forward to find the end of the bucket.
3271 size_t BucketStart = I;
3274 } while (I != E && PathsSorted[BucketStart]->MangledPath ==
3275 PathsSorted[I]->MangledPath);
3277 // If this bucket has multiple paths, extend them all.
3278 if (I - BucketStart > 1) {
3279 for (size_t II = BucketStart; II != I; ++II)
3280 Changed |= extendPath(PathsSorted[II]);
3281 assert(Changed && "no paths were extended to fix ambiguity");
3287 MicrosoftVTableContext::~MicrosoftVTableContext() {
3288 for (auto &P : VFPtrLocations)
3289 llvm::DeleteContainerPointers(*P.second);
3290 llvm::DeleteContainerSeconds(VFPtrLocations);
3291 llvm::DeleteContainerSeconds(VFTableLayouts);
3292 llvm::DeleteContainerSeconds(VBaseInfo);
3295 void MicrosoftVTableContext::computeVTableRelatedInformation(
3296 const CXXRecordDecl *RD) {
3297 assert(RD->isDynamicClass());
3299 // Check if we've computed this information before.
3300 if (VFPtrLocations.count(RD))
3303 const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;
3305 VPtrInfoVector *VFPtrs = new VPtrInfoVector();
3306 computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs);
3307 VFPtrLocations[RD] = VFPtrs;
3309 MethodVFTableLocationsTy NewMethodLocations;
3310 for (VPtrInfoVector::iterator I = VFPtrs->begin(), E = VFPtrs->end();
3312 VFTableBuilder Builder(*this, RD, *I);
3314 VFTableIdTy id(RD, (*I)->FullOffsetInMDC);
3315 assert(VFTableLayouts.count(id) == 0);
3316 SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
3317 Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
3318 VFTableLayouts[id] = new VTableLayout(
3319 Builder.getNumVTableComponents(), Builder.vtable_component_begin(),
3320 VTableThunks.size(), VTableThunks.data(), EmptyAddressPointsMap, true);
3321 Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
3323 for (const auto &Loc : Builder.vtable_locations()) {
3324 GlobalDecl GD = Loc.first;
3325 MethodVFTableLocation NewLoc = Loc.second;
3326 auto M = NewMethodLocations.find(GD);
3327 if (M == NewMethodLocations.end() || NewLoc < M->second)
3328 NewMethodLocations[GD] = NewLoc;
3332 MethodVFTableLocations.insert(NewMethodLocations.begin(),
3333 NewMethodLocations.end());
3334 if (Context.getLangOpts().DumpVTableLayouts)
3335 dumpMethodLocations(RD, NewMethodLocations, llvm::outs());
3338 void MicrosoftVTableContext::dumpMethodLocations(
3339 const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
3341 // Compute the vtable indices for all the member functions.
3342 // Store them in a map keyed by the location so we'll get a sorted table.
3343 std::map<MethodVFTableLocation, std::string> IndicesMap;
3344 bool HasNonzeroOffset = false;
3346 for (MethodVFTableLocationsTy::const_iterator I = NewMethods.begin(),
3347 E = NewMethods.end(); I != E; ++I) {
3348 const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I->first.getDecl());
3349 assert(MD->isVirtual());
3351 std::string MethodName = PredefinedExpr::ComputeName(
3352 PredefinedExpr::PrettyFunctionNoVirtual, MD);
3354 if (isa<CXXDestructorDecl>(MD)) {
3355 IndicesMap[I->second] = MethodName + " [scalar deleting]";
3357 IndicesMap[I->second] = MethodName;
3360 if (!I->second.VFPtrOffset.isZero() || I->second.VBTableIndex != 0)
3361 HasNonzeroOffset = true;
3364 // Print the vtable indices for all the member functions.
3365 if (!IndicesMap.empty()) {
3366 Out << "VFTable indices for ";
3368 RD->printQualifiedName(Out);
3369 Out << "' (" << IndicesMap.size()
3370 << (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n";
3372 CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1);
3373 uint64_t LastVBIndex = 0;
3374 for (std::map<MethodVFTableLocation, std::string>::const_iterator
3375 I = IndicesMap.begin(),
3376 E = IndicesMap.end();
3378 CharUnits VFPtrOffset = I->first.VFPtrOffset;
3379 uint64_t VBIndex = I->first.VBTableIndex;
3380 if (HasNonzeroOffset &&
3381 (VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) {
3382 assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);
3383 Out << " -- accessible via ";
3385 Out << "vbtable index " << VBIndex << ", ";
3386 Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";
3387 LastVFPtrOffset = VFPtrOffset;
3388 LastVBIndex = VBIndex;
3391 uint64_t VTableIndex = I->first.Index;
3392 const std::string &MethodName = I->second;
3393 Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n';
3401 const VirtualBaseInfo *MicrosoftVTableContext::computeVBTableRelatedInformation(
3402 const CXXRecordDecl *RD) {
3403 VirtualBaseInfo *VBI;
3406 // Get or create a VBI for RD. Don't hold a reference to the DenseMap cell,
3407 // as it may be modified and rehashed under us.
3408 VirtualBaseInfo *&Entry = VBaseInfo[RD];
3411 Entry = VBI = new VirtualBaseInfo();
3414 computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths);
3416 // First, see if the Derived class shared the vbptr with a non-virtual base.
3417 const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3418 if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {
3419 // If the Derived class shares the vbptr with a non-virtual base, the shared
3420 // virtual bases come first so that the layout is the same.
3421 const VirtualBaseInfo *BaseInfo =
3422 computeVBTableRelatedInformation(VBPtrBase);
3423 VBI->VBTableIndices.insert(BaseInfo->VBTableIndices.begin(),
3424 BaseInfo->VBTableIndices.end());
3427 // New vbases are added to the end of the vbtable.
3428 // Skip the self entry and vbases visited in the non-virtual base, if any.
3429 unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();
3430 for (const auto &VB : RD->vbases()) {
3431 const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();
3432 if (!VBI->VBTableIndices.count(CurVBase))
3433 VBI->VBTableIndices[CurVBase] = VBTableIndex++;
3439 unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
3440 const CXXRecordDecl *VBase) {
3441 const VirtualBaseInfo *VBInfo = computeVBTableRelatedInformation(Derived);
3442 assert(VBInfo->VBTableIndices.count(VBase));
3443 return VBInfo->VBTableIndices.find(VBase)->second;
3446 const VPtrInfoVector &
3447 MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
3448 return computeVBTableRelatedInformation(RD)->VBPtrPaths;
3451 const VPtrInfoVector &
3452 MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {
3453 computeVTableRelatedInformation(RD);
3455 assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");
3456 return *VFPtrLocations[RD];
3459 const VTableLayout &
3460 MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
3461 CharUnits VFPtrOffset) {
3462 computeVTableRelatedInformation(RD);
3464 VFTableIdTy id(RD, VFPtrOffset);
3465 assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");
3466 return *VFTableLayouts[id];
3469 const MicrosoftVTableContext::MethodVFTableLocation &
3470 MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {
3471 assert(cast<CXXMethodDecl>(GD.getDecl())->isVirtual() &&
3472 "Only use this method for virtual methods or dtors");
3473 if (isa<CXXDestructorDecl>(GD.getDecl()))
3474 assert(GD.getDtorType() == Dtor_Deleting);
3476 MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD);
3477 if (I != MethodVFTableLocations.end())
3480 const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
3482 computeVTableRelatedInformation(RD);
3484 I = MethodVFTableLocations.find(GD);
3485 assert(I != MethodVFTableLocations.end() && "Did not find index!");