1	//===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8	//
9	// This contains code dealing with generation of the layout of virtual tables.
10	//
11	//===----------------------------------------------------------------------===//
12
13	#include "clang/AST/VTableBuilder.h"
14	#include "clang/AST/ASTContext.h"
15	#include "clang/AST/ASTDiagnostic.h"
16	#include "clang/AST/CXXInheritance.h"
17	#include "clang/AST/RecordLayout.h"
18	#include "clang/Basic/TargetInfo.h"
19	#include "llvm/ADT/SetOperations.h"
20	#include "llvm/ADT/SetVector.h"
21	#include "llvm/ADT/SmallPtrSet.h"
22	#include "llvm/Support/Format.h"
23	#include "llvm/Support/raw_ostream.h"
24	#include <algorithm>
25	#include <cstdio>
26
27	using namespace clang;
28
29	#define DUMP_OVERRIDERS 0
30
31	namespace {
32
33	/// BaseOffset - Represents an offset from a derived class to a direct or
34	/// indirect base class.
35	struct BaseOffset {
36	/// DerivedClass - The derived class.
37	const CXXRecordDecl *DerivedClass;
38
39	/// VirtualBase - If the path from the derived class to the base class
40	/// involves virtual base classes, this holds the declaration of the last
41	/// virtual base in this path (i.e. closest to the base class).
42	const CXXRecordDecl *VirtualBase;
43
44	/// NonVirtualOffset - The offset from the derived class to the base class.
45	/// (Or the offset from the virtual base class to the base class, if the
46	/// path from the derived class to the base class involves a virtual base
47	/// class.
48	CharUnits NonVirtualOffset;
49
50	BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
51	NonVirtualOffset(CharUnits::Zero()) { }
52	BaseOffset(const CXXRecordDecl *DerivedClass,
53	const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
54	: DerivedClass(DerivedClass), VirtualBase(VirtualBase),
55	NonVirtualOffset(NonVirtualOffset) { }
56
57	bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; }
58	};
59
60	/// FinalOverriders - Contains the final overrider member functions for all
61	/// member functions in the base subobjects of a class.
62	class FinalOverriders {
63	public:
64	/// OverriderInfo - Information about a final overrider.
65	struct OverriderInfo {
66	/// Method - The method decl of the overrider.
67	const CXXMethodDecl *Method;
68
69	/// VirtualBase - The virtual base class subobject of this overrider.
70	/// Note that this records the closest derived virtual base class subobject.
71	const CXXRecordDecl *VirtualBase;
72
73	/// Offset - the base offset of the overrider's parent in the layout class.
74	CharUnits Offset;
75
76	OverriderInfo() : Method(nullptr), VirtualBase(nullptr),
77	Offset(CharUnits::Zero()) { }
78	};
79
80	private:
81	/// MostDerivedClass - The most derived class for which the final overriders
82	/// are stored.
83	const CXXRecordDecl *MostDerivedClass;
84
85	/// MostDerivedClassOffset - If we're building final overriders for a
86	/// construction vtable, this holds the offset from the layout class to the
87	/// most derived class.
88	const CharUnits MostDerivedClassOffset;
89
90	/// LayoutClass - The class we're using for layout information. Will be
91	/// different than the most derived class if the final overriders are for a
92	/// construction vtable.
93	const CXXRecordDecl *LayoutClass;
94
95	ASTContext &Context;
96
97	/// MostDerivedClassLayout - the AST record layout of the most derived class.
98	const ASTRecordLayout &MostDerivedClassLayout;
99
100	/// MethodBaseOffsetPairTy - Uniquely identifies a member function
101	/// in a base subobject.
102	typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
103
104	typedef llvm::DenseMap<MethodBaseOffsetPairTy,
105	OverriderInfo> OverridersMapTy;
106
107	/// OverridersMap - The final overriders for all virtual member functions of
108	/// all the base subobjects of the most derived class.
109	OverridersMapTy OverridersMap;
110
111	/// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
112	/// as a record decl and a subobject number) and its offsets in the most
113	/// derived class as well as the layout class.
114	typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>,
115	CharUnits> SubobjectOffsetMapTy;
116
117	typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
118
119	/// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
120	/// given base.
121	void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
122	CharUnits OffsetInLayoutClass,
123	SubobjectOffsetMapTy &SubobjectOffsets,
124	SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
125	SubobjectCountMapTy &SubobjectCounts);
126
127	typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
128
129	/// dump - dump the final overriders for a base subobject, and all its direct
130	/// and indirect base subobjects.
131	void dump(raw_ostream &Out, BaseSubobject Base,
132	VisitedVirtualBasesSetTy& VisitedVirtualBases);
133
134	public:
135	FinalOverriders(const CXXRecordDecl *MostDerivedClass,
136	CharUnits MostDerivedClassOffset,
137	const CXXRecordDecl *LayoutClass);
138
139	/// getOverrider - Get the final overrider for the given method declaration in
140	/// the subobject with the given base offset.
141	OverriderInfo getOverrider(const CXXMethodDecl *MD,
142	CharUnits BaseOffset) const {
143	assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) &&
144	"Did not find overrider!");
145
146	return OverridersMap.lookup(Val: std::make_pair(x&: MD, y&: BaseOffset));
147	}
148
149	/// dump - dump the final overriders.
150	void dump() {
151	VisitedVirtualBasesSetTy VisitedVirtualBases;
152	dump(Out&: llvm::errs(), Base: BaseSubobject(MostDerivedClass, CharUnits::Zero()),
153	VisitedVirtualBases);
154	}
155
156	};
157
158	FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
159	CharUnits MostDerivedClassOffset,
160	const CXXRecordDecl *LayoutClass)
161	: MostDerivedClass(MostDerivedClass),
162	MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
163	Context(MostDerivedClass->getASTContext()),
164	MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
165
166	// Compute base offsets.
167	SubobjectOffsetMapTy SubobjectOffsets;
168	SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
169	SubobjectCountMapTy SubobjectCounts;
170	ComputeBaseOffsets(Base: BaseSubobject(MostDerivedClass, CharUnits::Zero()),
171	/*IsVirtual=*/false,
172	OffsetInLayoutClass: MostDerivedClassOffset,
173	SubobjectOffsets, SubobjectLayoutClassOffsets,
174	SubobjectCounts);
175
176	// Get the final overriders.
177	CXXFinalOverriderMap FinalOverriders;
178	MostDerivedClass->getFinalOverriders(FinaOverriders&: FinalOverriders);
179
180	for (const auto &Overrider : FinalOverriders) {
181	const CXXMethodDecl *MD = Overrider.first;
182	const OverridingMethods &Methods = Overrider.second;
183
184	for (const auto &M : Methods) {
185	unsigned SubobjectNumber = M.first;
186	assert(SubobjectOffsets.count(std::make_pair(MD->getParent(),
187	SubobjectNumber)) &&
188	"Did not find subobject offset!");
189
190	CharUnits BaseOffset = SubobjectOffsets[std::make_pair(x: MD->getParent(),
191	y&: SubobjectNumber)];
192
193	assert(M.second.size() == 1 && "Final overrider is not unique!");
194	const UniqueVirtualMethod &Method = M.second.front();
195
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(x&: OverriderRD,
202	y: Method.Subobject)];
203
204	OverriderInfo& Overrider = OverridersMap[std::make_pair(x&: MD, y&: BaseOffset)];
205	assert(!Overrider.Method && "Overrider should not exist yet!");
206
207	Overrider.Offset = OverriderOffset;
208	Overrider.Method = Method.Method;
209	Overrider.VirtualBase = Method.InVirtualSubobject;
210	}
211	}
212
213	#if DUMP_OVERRIDERS
214	// And dump them (for now).
215	dump();
216	#endif
217	}
218
219	static BaseOffset ComputeBaseOffset(const ASTContext &Context,
220	const CXXRecordDecl *DerivedRD,
221	const CXXBasePath &Path) {
222	CharUnits NonVirtualOffset = CharUnits::Zero();
223
224	unsigned NonVirtualStart = 0;
225	const CXXRecordDecl *VirtualBase = nullptr;
226
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];
230
231	if (Element.Base->isVirtual()) {
232	NonVirtualStart = I;
233	QualType VBaseType = Element.Base->getType();
234	VirtualBase = VBaseType->getAsCXXRecordDecl();
235	break;
236	}
237	}
238
239	// Now compute the non-virtual offset.
240	for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) {
241	const CXXBasePathElement &Element = Path[I];
242
243	// Check the base class offset.
244	const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
245
246	const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl();
247
248	NonVirtualOffset += Layout.getBaseClassOffset(Base);
249	}
250
251	// FIXME: This should probably use CharUnits or something. Maybe we should
252	// even change the base offsets in ASTRecordLayout to be specified in
253	// CharUnits.
254	return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
255
256	}
257
258	static BaseOffset ComputeBaseOffset(const ASTContext &Context,
259	const CXXRecordDecl *BaseRD,
260	const CXXRecordDecl *DerivedRD) {
261	CXXBasePaths Paths(/*FindAmbiguities=*/false,
262	/*RecordPaths=*/true, /*DetectVirtual=*/false);
263
264	if (!DerivedRD->isDerivedFrom(Base: BaseRD, Paths))
265	llvm_unreachable("Class must be derived from the passed in base class!");
266
267	return ComputeBaseOffset(Context, DerivedRD, Path: Paths.front());
268	}
269
270	static BaseOffset
271	ComputeReturnAdjustmentBaseOffset(ASTContext &Context,
272	const CXXMethodDecl *DerivedMD,
273	const CXXMethodDecl *BaseMD) {
274	const auto *BaseFT = BaseMD->getType()->castAs<FunctionType>();
275	const auto *DerivedFT = DerivedMD->getType()->castAs<FunctionType>();
276
277	// Canonicalize the return types.
278	CanQualType CanDerivedReturnType =
279	Context.getCanonicalType(DerivedFT->getReturnType());
280	CanQualType CanBaseReturnType =
281	Context.getCanonicalType(BaseFT->getReturnType());
282
283	assert(CanDerivedReturnType->getTypeClass() ==
284	CanBaseReturnType->getTypeClass() &&
285	"Types must have same type class!");
286
287	if (CanDerivedReturnType == CanBaseReturnType) {
288	// No adjustment needed.
289	return BaseOffset();
290	}
291
292	if (isa<ReferenceType>(Val: CanDerivedReturnType)) {
293	CanDerivedReturnType =
294	CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
295	CanBaseReturnType =
296	CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
297	} else if (isa<PointerType>(Val: CanDerivedReturnType)) {
298	CanDerivedReturnType =
299	CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
300	CanBaseReturnType =
301	CanBaseReturnType->getAs<PointerType>()->getPointeeType();
302	} else {
303	llvm_unreachable("Unexpected return type!");
304	}
305
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.
312	return BaseOffset();
313	}
314
315	const CXXRecordDecl *DerivedRD =
316	cast<CXXRecordDecl>(Val: cast<RecordType>(Val&: CanDerivedReturnType)->getDecl());
317
318	const CXXRecordDecl *BaseRD =
319	cast<CXXRecordDecl>(Val: cast<RecordType>(Val&: CanBaseReturnType)->getDecl());
320
321	return ComputeBaseOffset(Context, BaseRD, DerivedRD);
322	}
323
324	void
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();
331
332	unsigned SubobjectNumber = 0;
333	if (!IsVirtual)
334	SubobjectNumber = ++SubobjectCounts[RD];
335
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!");
341
342	SubobjectOffsets[std::make_pair(x&: RD, y&: SubobjectNumber)] = Base.getBaseOffset();
343	SubobjectLayoutClassOffsets[std::make_pair(x&: RD, y&: SubobjectNumber)] =
344	OffsetInLayoutClass;
345
346	// Traverse our bases.
347	for (const auto &B : RD->bases()) {
348	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
349
350	CharUnits BaseOffset;
351	CharUnits BaseOffsetInLayoutClass;
352	if (B.isVirtual()) {
353	// Check if we've visited this virtual base before.
354	if (SubobjectOffsets.count(Val: std::make_pair(x&: BaseDecl, y: 0)))
355	continue;
356
357	const ASTRecordLayout &LayoutClassLayout =
358	Context.getASTRecordLayout(LayoutClass);
359
360	BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(VBase: BaseDecl);
361	BaseOffsetInLayoutClass =
362	LayoutClassLayout.getVBaseClassOffset(VBase: BaseDecl);
363	} else {
364	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
365	CharUnits Offset = Layout.getBaseClassOffset(Base: BaseDecl);
366
367	BaseOffset = Base.getBaseOffset() + Offset;
368	BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
369	}
370
371	ComputeBaseOffsets(Base: BaseSubobject(BaseDecl, BaseOffset),
372	IsVirtual: B.isVirtual(), OffsetInLayoutClass: BaseOffsetInLayoutClass,
373	SubobjectOffsets, SubobjectLayoutClassOffsets,
374	SubobjectCounts);
375	}
376	}
377
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);
382
383	for (const auto &B : RD->bases()) {
384	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
385
386	// Ignore bases that don't have any virtual member functions.
387	if (!BaseDecl->isPolymorphic())
388	continue;
389
390	CharUnits BaseOffset;
391	if (B.isVirtual()) {
392	if (!VisitedVirtualBases.insert(Ptr: BaseDecl).second) {
393	// We've visited this base before.
394	continue;
395	}
396
397	BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(VBase: BaseDecl);
398	} else {
399	BaseOffset = Layout.getBaseClassOffset(Base: BaseDecl) + Base.getBaseOffset();
400	}
401
402	dump(Out, Base: BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
403	}
404
405	Out << "Final overriders for (";
406	RD->printQualifiedName(Out);
407	Out << ", ";
408	Out << Base.getBaseOffset().getQuantity() << ")\n";
409
410	// Now dump the overriders for this base subobject.
411	for (const auto *MD : RD->methods()) {
412	if (!VTableContextBase::hasVtableSlot(MD))
413	continue;
414	MD = MD->getCanonicalDecl();
415
416	OverriderInfo Overrider = getOverrider(MD, BaseOffset: Base.getBaseOffset());
417
418	Out << " ";
419	MD->printQualifiedName(Out);
420	Out << " - (";
421	Overrider.Method->printQualifiedName(Out);
422	Out << ", " << Overrider.Offset.getQuantity() << ')';
423
424	BaseOffset Offset;
425	if (!Overrider.Method->isPureVirtual())
426	Offset = ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: Overrider.Method, BaseMD: MD);
427
428	if (!Offset.isEmpty()) {
429	Out << " [ret-adj: ";
430	if (Offset.VirtualBase) {
431	Offset.VirtualBase->printQualifiedName(Out);
432	Out << " vbase, ";
433	}
434
435	Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
436	}
437
438	Out << "\n";
439	}
440	}
441
442	/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
443	struct VCallOffsetMap {
444
445	typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
446
447	/// Offsets - Keeps track of methods and their offsets.
448	// FIXME: This should be a real map and not a vector.
449	SmallVector<MethodAndOffsetPairTy, 16> Offsets;
450
451	/// MethodsCanShareVCallOffset - Returns whether two virtual member functions
452	/// can share the same vcall offset.
453	static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
454	const CXXMethodDecl *RHS);
455
456	public:
457	/// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
458	/// add was successful, or false if there was already a member function with
459	/// the same signature in the map.
460	bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
461
462	/// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
463	/// vtable address point) for the given virtual member function.
464	CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
465
466	// empty - Return whether the offset map is empty or not.
467	bool empty() const { return Offsets.empty(); }
468	};
469
470	static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
471	const CXXMethodDecl *RHS) {
472	const FunctionProtoType *LT =
473	cast<FunctionProtoType>(LHS->getType().getCanonicalType());
474	const FunctionProtoType *RT =
475	cast<FunctionProtoType>(RHS->getType().getCanonicalType());
476
477	// Fast-path matches in the canonical types.
478	if (LT == RT) return true;
479
480	// Force the signatures to match. We can't rely on the overrides
481	// list here because there isn't necessarily an inheritance
482	// relationship between the two methods.
483	if (LT->getMethodQuals() != RT->getMethodQuals())
484	return false;
485	return LT->getParamTypes() == RT->getParamTypes();
486	}
487
488	bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
489	const CXXMethodDecl *RHS) {
490	assert(VTableContextBase::hasVtableSlot(LHS) && "LHS must be virtual!");
491	assert(VTableContextBase::hasVtableSlot(RHS) && "RHS must be virtual!");
492
493	// A destructor can share a vcall offset with another destructor.
494	if (isa<CXXDestructorDecl>(Val: LHS))
495	return isa<CXXDestructorDecl>(Val: RHS);
496
497	// FIXME: We need to check more things here.
498
499	// The methods must have the same name.
500	DeclarationName LHSName = LHS->getDeclName();
501	DeclarationName RHSName = RHS->getDeclName();
502	if (LHSName != RHSName)
503	return false;
504
505	// And the same signatures.
506	return HasSameVirtualSignature(LHS, RHS);
507	}
508
509	bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,
510	CharUnits OffsetOffset) {
511	// Check if we can reuse an offset.
512	for (const auto &OffsetPair : Offsets) {
513	if (MethodsCanShareVCallOffset(LHS: OffsetPair.first, RHS: MD))
514	return false;
515	}
516
517	// Add the offset.
518	Offsets.push_back(Elt: MethodAndOffsetPairTy(MD, OffsetOffset));
519	return true;
520	}
521
522	CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
523	// Look for an offset.
524	for (const auto &OffsetPair : Offsets) {
525	if (MethodsCanShareVCallOffset(LHS: OffsetPair.first, RHS: MD))
526	return OffsetPair.second;
527	}
528
529	llvm_unreachable("Should always find a vcall offset offset!");
530	}
531
532	/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
533	class VCallAndVBaseOffsetBuilder {
534	public:
535	typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
536	VBaseOffsetOffsetsMapTy;
537
538	private:
539	const ItaniumVTableContext &VTables;
540
541	/// MostDerivedClass - The most derived class for which we're building vcall
542	/// and vbase offsets.
543	const CXXRecordDecl *MostDerivedClass;
544
545	/// LayoutClass - The class we're using for layout information. Will be
546	/// different than the most derived class if we're building a construction
547	/// vtable.
548	const CXXRecordDecl *LayoutClass;
549
550	/// Context - The ASTContext which we will use for layout information.
551	ASTContext &Context;
552
553	/// Components - vcall and vbase offset components
554	typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
555	VTableComponentVectorTy Components;
556
557	/// VisitedVirtualBases - Visited virtual bases.
558	llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
559
560	/// VCallOffsets - Keeps track of vcall offsets.
561	VCallOffsetMap VCallOffsets;
562
563
564	/// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
565	/// relative to the address point.
566	VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
567
568	/// FinalOverriders - The final overriders of the most derived class.
569	/// (Can be null when we're not building a vtable of the most derived class).
570	const FinalOverriders *Overriders;
571
572	/// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
573	/// given base subobject.
574	void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
575	CharUnits RealBaseOffset);
576
577	/// AddVCallOffsets - Add vcall offsets for the given base subobject.
578	void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
579
580	/// AddVBaseOffsets - Add vbase offsets for the given class.
581	void AddVBaseOffsets(const CXXRecordDecl *Base,
582	CharUnits OffsetInLayoutClass);
583
584	/// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
585	/// chars, relative to the vtable address point.
586	CharUnits getCurrentOffsetOffset() const;
587
588	public:
589	VCallAndVBaseOffsetBuilder(const ItaniumVTableContext &VTables,
590	const CXXRecordDecl *MostDerivedClass,
591	const CXXRecordDecl *LayoutClass,
592	const FinalOverriders *Overriders,
593	BaseSubobject Base, bool BaseIsVirtual,
594	CharUnits OffsetInLayoutClass)
595	: VTables(VTables), MostDerivedClass(MostDerivedClass),
596	LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
597	Overriders(Overriders) {
598
599	// Add vcall and vbase offsets.
600	AddVCallAndVBaseOffsets(Base, BaseIsVirtual, RealBaseOffset: OffsetInLayoutClass);
601	}
602
603	/// Methods for iterating over the components.
604	typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
605	const_iterator components_begin() const { return Components.rbegin(); }
606	const_iterator components_end() const { return Components.rend(); }
607
608	const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
609	const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
610	return VBaseOffsetOffsets;
611	}
612	};
613
614	void
615	VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
616	bool BaseIsVirtual,
617	CharUnits RealBaseOffset) {
618	const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
619
620	// Itanium C++ ABI 2.5.2:
621	// ..in classes sharing a virtual table with a primary base class, the vcall
622	// and vbase offsets added by the derived class all come before the vcall
623	// and vbase offsets required by the base class, so that the latter may be
624	// laid out as required by the base class without regard to additions from
625	// the derived class(es).
626
627	// (Since we're emitting the vcall and vbase offsets in reverse order, we'll
628	// emit them for the primary base first).
629	if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
630	bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
631
632	CharUnits PrimaryBaseOffset;
633
634	// Get the base offset of the primary base.
635	if (PrimaryBaseIsVirtual) {
636	assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
637	"Primary vbase should have a zero offset!");
638
639	const ASTRecordLayout &MostDerivedClassLayout =
640	Context.getASTRecordLayout(MostDerivedClass);
641
642	PrimaryBaseOffset =
643	MostDerivedClassLayout.getVBaseClassOffset(VBase: PrimaryBase);
644	} else {
645	assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
646	"Primary base should have a zero offset!");
647
648	PrimaryBaseOffset = Base.getBaseOffset();
649	}
650
651	AddVCallAndVBaseOffsets(
652	Base: BaseSubobject(PrimaryBase,PrimaryBaseOffset),
653	BaseIsVirtual: PrimaryBaseIsVirtual, RealBaseOffset);
654	}
655
656	AddVBaseOffsets(Base: Base.getBase(), OffsetInLayoutClass: RealBaseOffset);
657
658	// We only want to add vcall offsets for virtual bases.
659	if (BaseIsVirtual)
660	AddVCallOffsets(Base, VBaseOffset: RealBaseOffset);
661	}
662
663	CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
664	// OffsetIndex is the index of this vcall or vbase offset, relative to the
665	// vtable address point. (We subtract 3 to account for the information just
666	// above the address point, the RTTI info, the offset to top, and the
667	// vcall offset itself).
668	size_t NumComponentsAboveAddrPoint = 3;
669	if (Context.getLangOpts().OmitVTableRTTI)
670	NumComponentsAboveAddrPoint--;
671	int64_t OffsetIndex =
672	-(int64_t)(NumComponentsAboveAddrPoint + Components.size());
673
674	// Under the relative ABI, the offset widths are 32-bit ints instead of
675	// pointer widths.
676	CharUnits OffsetWidth = Context.toCharUnitsFromBits(
677	BitSize: VTables.isRelativeLayout()
678	? 32
679	: Context.getTargetInfo().getPointerWidth(AddrSpace: LangAS::Default));
680	CharUnits OffsetOffset = OffsetWidth * OffsetIndex;
681
682	return OffsetOffset;
683	}
684
685	void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,
686	CharUnits VBaseOffset) {
687	const CXXRecordDecl *RD = Base.getBase();
688	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
689
690	const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
691
692	// Handle the primary base first.
693	// We only want to add vcall offsets if the base is non-virtual; a virtual
694	// primary base will have its vcall and vbase offsets emitted already.
695	if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {
696	// Get the base offset of the primary base.
697	assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
698	"Primary base should have a zero offset!");
699
700	AddVCallOffsets(Base: BaseSubobject(PrimaryBase, Base.getBaseOffset()),
701	VBaseOffset);
702	}
703
704	// Add the vcall offsets.
705	for (const auto *MD : RD->methods()) {
706	if (!VTableContextBase::hasVtableSlot(MD))
707	continue;
708	MD = MD->getCanonicalDecl();
709
710	CharUnits OffsetOffset = getCurrentOffsetOffset();
711
712	// Don't add a vcall offset if we already have one for this member function
713	// signature.
714	if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
715	continue;
716
717	CharUnits Offset = CharUnits::Zero();
718
719	if (Overriders) {
720	// Get the final overrider.
721	FinalOverriders::OverriderInfo Overrider =
722	Overriders->getOverrider(MD, BaseOffset: Base.getBaseOffset());
723
724	/// The vcall offset is the offset from the virtual base to the object
725	/// where the function was overridden.
726	Offset = Overrider.Offset - VBaseOffset;
727	}
728
729	Components.push_back(
730	Elt: VTableComponent::MakeVCallOffset(Offset));
731	}
732
733	// And iterate over all non-virtual bases (ignoring the primary base).
734	for (const auto &B : RD->bases()) {
735	if (B.isVirtual())
736	continue;
737
738	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
739	if (BaseDecl == PrimaryBase)
740	continue;
741
742	// Get the base offset of this base.
743	CharUnits BaseOffset = Base.getBaseOffset() +
744	Layout.getBaseClassOffset(Base: BaseDecl);
745
746	AddVCallOffsets(Base: BaseSubobject(BaseDecl, BaseOffset),
747	VBaseOffset);
748	}
749	}
750
751	void
752	VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
753	CharUnits OffsetInLayoutClass) {
754	const ASTRecordLayout &LayoutClassLayout =
755	Context.getASTRecordLayout(LayoutClass);
756
757	// Add vbase offsets.
758	for (const auto &B : RD->bases()) {
759	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
760
761	// Check if this is a virtual base that we haven't visited before.
762	if (B.isVirtual() && VisitedVirtualBases.insert(Ptr: BaseDecl).second) {
763	CharUnits Offset =
764	LayoutClassLayout.getVBaseClassOffset(VBase: BaseDecl) - OffsetInLayoutClass;
765
766	// Add the vbase offset offset.
767	assert(!VBaseOffsetOffsets.count(BaseDecl) &&
768	"vbase offset offset already exists!");
769
770	CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
771	VBaseOffsetOffsets.insert(
772	KV: std::make_pair(x&: BaseDecl, y&: VBaseOffsetOffset));
773
774	Components.push_back(
775	Elt: VTableComponent::MakeVBaseOffset(Offset));
776	}
777
778	// Check the base class looking for more vbase offsets.
779	AddVBaseOffsets(RD: BaseDecl, OffsetInLayoutClass);
780	}
781	}
782
783	/// ItaniumVTableBuilder - Class for building vtable layout information.
784	class ItaniumVTableBuilder {
785	public:
786	/// PrimaryBasesSetVectorTy - A set vector of direct and indirect
787	/// primary bases.
788	typedef llvm::SmallSetVector<const CXXRecordDecl *, 8>
789	PrimaryBasesSetVectorTy;
790
791	typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
792	VBaseOffsetOffsetsMapTy;
793
794	typedef VTableLayout::AddressPointsMapTy AddressPointsMapTy;
795
796	typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
797
798	private:
799	/// VTables - Global vtable information.
800	ItaniumVTableContext &VTables;
801
802	/// MostDerivedClass - The most derived class for which we're building this
803	/// vtable.
804	const CXXRecordDecl *MostDerivedClass;
805
806	/// MostDerivedClassOffset - If we're building a construction vtable, this
807	/// holds the offset from the layout class to the most derived class.
808	const CharUnits MostDerivedClassOffset;
809
810	/// MostDerivedClassIsVirtual - Whether the most derived class is a virtual
811	/// base. (This only makes sense when building a construction vtable).
812	bool MostDerivedClassIsVirtual;
813
814	/// LayoutClass - The class we're using for layout information. Will be
815	/// different than the most derived class if we're building a construction
816	/// vtable.
817	const CXXRecordDecl *LayoutClass;
818
819	/// Context - The ASTContext which we will use for layout information.
820	ASTContext &Context;
821
822	/// FinalOverriders - The final overriders of the most derived class.
823	const FinalOverriders Overriders;
824
825	/// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
826	/// bases in this vtable.
827	llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
828
829	/// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
830	/// the most derived class.
831	VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
832
833	/// Components - The components of the vtable being built.
834	SmallVector<VTableComponent, 64> Components;
835
836	/// AddressPoints - Address points for the vtable being built.
837	AddressPointsMapTy AddressPoints;
838
839	/// MethodInfo - Contains information about a method in a vtable.
840	/// (Used for computing 'this' pointer adjustment thunks.
841	struct MethodInfo {
842	/// BaseOffset - The base offset of this method.
843	const CharUnits BaseOffset;
844
845	/// BaseOffsetInLayoutClass - The base offset in the layout class of this
846	/// method.
847	const CharUnits BaseOffsetInLayoutClass;
848
849	/// VTableIndex - The index in the vtable that this method has.
850	/// (For destructors, this is the index of the complete destructor).
851	const uint64_t VTableIndex;
852
853	MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,
854	uint64_t VTableIndex)
855	: BaseOffset(BaseOffset),
856	BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
857	VTableIndex(VTableIndex) { }
858
859	MethodInfo()
860	: BaseOffset(CharUnits::Zero()),
861	BaseOffsetInLayoutClass(CharUnits::Zero()),
862	VTableIndex(0) { }
863
864	MethodInfo(MethodInfo const&) = default;
865	};
866
867	typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
868
869	/// MethodInfoMap - The information for all methods in the vtable we're
870	/// currently building.
871	MethodInfoMapTy MethodInfoMap;
872
873	/// MethodVTableIndices - Contains the index (relative to the vtable address
874	/// point) where the function pointer for a virtual function is stored.
875	MethodVTableIndicesTy MethodVTableIndices;
876
877	typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
878
879	/// VTableThunks - The thunks by vtable index in the vtable currently being
880	/// built.
881	VTableThunksMapTy VTableThunks;
882
883	typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
884	typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
885
886	/// Thunks - A map that contains all the thunks needed for all methods in the
887	/// most derived class for which the vtable is currently being built.
888	ThunksMapTy Thunks;
889
890	/// AddThunk - Add a thunk for the given method.
891	void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
892
893	/// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
894	/// part of the vtable we're currently building.
895	void ComputeThisAdjustments();
896
897	typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
898
899	/// PrimaryVirtualBases - All known virtual bases who are a primary base of
900	/// some other base.
901	VisitedVirtualBasesSetTy PrimaryVirtualBases;
902
903	/// ComputeReturnAdjustment - Compute the return adjustment given a return
904	/// adjustment base offset.
905	ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
906
907	/// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
908	/// the 'this' pointer from the base subobject to the derived subobject.
909	BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
910	BaseSubobject Derived) const;
911
912	/// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
913	/// given virtual member function, its offset in the layout class and its
914	/// final overrider.
915	ThisAdjustment
916	ComputeThisAdjustment(const CXXMethodDecl *MD,
917	CharUnits BaseOffsetInLayoutClass,
918	FinalOverriders::OverriderInfo Overrider);
919
920	/// AddMethod - Add a single virtual member function to the vtable
921	/// components vector.
922	void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
923
924	/// IsOverriderUsed - Returns whether the overrider will ever be used in this
925	/// part of the vtable.
926	///
927	/// Itanium C++ ABI 2.5.2:
928	///
929	/// struct A { virtual void f(); };
930	/// struct B : virtual public A { int i; };
931	/// struct C : virtual public A { int j; };
932	/// struct D : public B, public C {};
933	///
934	/// When B and C are declared, A is a primary base in each case, so although
935	/// vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
936	/// adjustment is required and no thunk is generated. However, inside D
937	/// objects, A is no longer a primary base of C, so if we allowed calls to
938	/// C::f() to use the copy of A's vtable in the C subobject, we would need
939	/// to adjust this from C* to B::A*, which would require a third-party
940	/// thunk. Since we require that a call to C::f() first convert to A*,
941	/// C-in-D's copy of A's vtable is never referenced, so this is not
942	/// necessary.
943	bool IsOverriderUsed(const CXXMethodDecl *Overrider,
944	CharUnits BaseOffsetInLayoutClass,
945	const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
946	CharUnits FirstBaseOffsetInLayoutClass) const;
947
948
949	/// AddMethods - Add the methods of this base subobject and all its
950	/// primary bases to the vtable components vector.
951	void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
952	const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
953	CharUnits FirstBaseOffsetInLayoutClass,
954	PrimaryBasesSetVectorTy &PrimaryBases);
955
956	// LayoutVTable - Layout the vtable for the given base class, including its
957	// secondary vtables and any vtables for virtual bases.
958	void LayoutVTable();
959
960	/// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the
961	/// given base subobject, as well as all its secondary vtables.
962	///
963	/// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
964	/// or a direct or indirect base of a virtual base.
965	///
966	/// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual
967	/// in the layout class.
968	void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,
969	bool BaseIsMorallyVirtual,
970	bool BaseIsVirtualInLayoutClass,
971	CharUnits OffsetInLayoutClass);
972
973	/// LayoutSecondaryVTables - Layout the secondary vtables for the given base
974	/// subobject.
975	///
976	/// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
977	/// or a direct or indirect base of a virtual base.
978	void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,
979	CharUnits OffsetInLayoutClass);
980
981	/// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this
982	/// class hierarchy.
983	void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD,
984	CharUnits OffsetInLayoutClass,
985	VisitedVirtualBasesSetTy &VBases);
986
987	/// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the
988	/// given base (excluding any primary bases).
989	void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD,
990	VisitedVirtualBasesSetTy &VBases);
991
992	/// isBuildingConstructionVTable - Return whether this vtable builder is
993	/// building a construction vtable.
994	bool isBuildingConstructorVTable() const {
995	return MostDerivedClass != LayoutClass;
996	}
997
998	public:
999	/// Component indices of the first component of each of the vtables in the
1000	/// vtable group.
1001	SmallVector<size_t, 4> VTableIndices;
1002
1003	ItaniumVTableBuilder(ItaniumVTableContext &VTables,
1004	const CXXRecordDecl *MostDerivedClass,
1005	CharUnits MostDerivedClassOffset,
1006	bool MostDerivedClassIsVirtual,
1007	const CXXRecordDecl *LayoutClass)
1008	: VTables(VTables), MostDerivedClass(MostDerivedClass),
1009	MostDerivedClassOffset(MostDerivedClassOffset),
1010	MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
1011	LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
1012	Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {
1013	assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());
1014
1015	LayoutVTable();
1016
1017	if (Context.getLangOpts().DumpVTableLayouts)
1018	dumpLayout(llvm::outs());
1019	}
1020
1021	uint64_t getNumThunks() const {
1022	return Thunks.size();
1023	}
1024
1025	ThunksMapTy::const_iterator thunks_begin() const {
1026	return Thunks.begin();
1027	}
1028
1029	ThunksMapTy::const_iterator thunks_end() const {
1030	return Thunks.end();
1031	}
1032
1033	const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
1034	return VBaseOffsetOffsets;
1035	}
1036
1037	const AddressPointsMapTy &getAddressPoints() const {
1038	return AddressPoints;
1039	}
1040
1041	MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
1042	return MethodVTableIndices.begin();
1043	}
1044
1045	MethodVTableIndicesTy::const_iterator vtable_indices_end() const {
1046	return MethodVTableIndices.end();
1047	}
1048
1049	ArrayRef<VTableComponent> vtable_components() const { return Components; }
1050
1051	AddressPointsMapTy::const_iterator address_points_begin() const {
1052	return AddressPoints.begin();
1053	}
1054
1055	AddressPointsMapTy::const_iterator address_points_end() const {
1056	return AddressPoints.end();
1057	}
1058
1059	VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
1060	return VTableThunks.begin();
1061	}
1062
1063	VTableThunksMapTy::const_iterator vtable_thunks_end() const {
1064	return VTableThunks.end();
1065	}
1066
1067	/// dumpLayout - Dump the vtable layout.
1068	void dumpLayout(raw_ostream&);
1069	};
1070
1071	void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
1072	const ThunkInfo &Thunk) {
1073	assert(!isBuildingConstructorVTable() &&
1074	"Can't add thunks for construction vtable");
1075
1076	SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];
1077
1078	// Check if we have this thunk already.
1079	if (llvm::is_contained(Range&: ThunksVector, Element: Thunk))
1080	return;
1081
1082	ThunksVector.push_back(Elt: Thunk);
1083	}
1084
1085	typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;
1086
1087	/// Visit all the methods overridden by the given method recursively,
1088	/// in a depth-first pre-order. The Visitor's visitor method returns a bool
1089	/// indicating whether to continue the recursion for the given overridden
1090	/// method (i.e. returning false stops the iteration).
1091	template <class VisitorTy>
1092	static void
1093	visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1094	assert(VTableContextBase::hasVtableSlot(MD) && "Method is not virtual!");
1095
1096	for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1097	if (!Visitor(OverriddenMD))
1098	continue;
1099	visitAllOverriddenMethods(OverriddenMD, Visitor);
1100	}
1101	}
1102
1103	/// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
1104	/// the overridden methods that the function decl overrides.
1105	static void
1106	ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
1107	OverriddenMethodsSetTy& OverriddenMethods) {
1108	auto OverriddenMethodsCollector = [&](const CXXMethodDecl *MD) {
1109	// Don't recurse on this method if we've already collected it.
1110	return OverriddenMethods.insert(Ptr: MD).second;
1111	};
1112	visitAllOverriddenMethods(MD, Visitor&: OverriddenMethodsCollector);
1113	}
1114
1115	void ItaniumVTableBuilder::ComputeThisAdjustments() {
1116	// Now go through the method info map and see if any of the methods need
1117	// 'this' pointer adjustments.
1118	for (const auto &MI : MethodInfoMap) {
1119	const CXXMethodDecl *MD = MI.first;
1120	const MethodInfo &MethodInfo = MI.second;
1121
1122	// Ignore adjustments for unused function pointers.
1123	uint64_t VTableIndex = MethodInfo.VTableIndex;
1124	if (Components[VTableIndex].getKind() ==
1125	VTableComponent::CK_UnusedFunctionPointer)
1126	continue;
1127
1128	// Get the final overrider for this method.
1129	FinalOverriders::OverriderInfo Overrider =
1130	Overriders.getOverrider(MD, BaseOffset: MethodInfo.BaseOffset);
1131
1132	// Check if we need an adjustment at all.
1133	if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {
1134	// When a return thunk is needed by a derived class that overrides a
1135	// virtual base, gcc uses a virtual 'this' adjustment as well.
1136	// While the thunk itself might be needed by vtables in subclasses or
1137	// in construction vtables, there doesn't seem to be a reason for using
1138	// the thunk in this vtable. Still, we do so to match gcc.
1139	if (VTableThunks.lookup(Val: VTableIndex).Return.isEmpty())
1140	continue;
1141	}
1142
1143	ThisAdjustment ThisAdjustment =
1144	ComputeThisAdjustment(MD, BaseOffsetInLayoutClass: MethodInfo.BaseOffsetInLayoutClass, Overrider);
1145
1146	if (ThisAdjustment.isEmpty())
1147	continue;
1148
1149	// Add it.
1150	VTableThunks[VTableIndex].This = ThisAdjustment;
1151
1152	if (isa<CXXDestructorDecl>(Val: MD)) {
1153	// Add an adjustment for the deleting destructor as well.
1154	VTableThunks[VTableIndex + 1].This = ThisAdjustment;
1155	}
1156	}
1157
1158	/// Clear the method info map.
1159	MethodInfoMap.clear();
1160
1161	if (isBuildingConstructorVTable()) {
1162	// We don't need to store thunk information for construction vtables.
1163	return;
1164	}
1165
1166	for (const auto &TI : VTableThunks) {
1167	const VTableComponent &Component = Components[TI.first];
1168	const ThunkInfo &Thunk = TI.second;
1169	const CXXMethodDecl *MD;
1170
1171	switch (Component.getKind()) {
1172	default:
1173	llvm_unreachable("Unexpected vtable component kind!");
1174	case VTableComponent::CK_FunctionPointer:
1175	MD = Component.getFunctionDecl();
1176	break;
1177	case VTableComponent::CK_CompleteDtorPointer:
1178	MD = Component.getDestructorDecl();
1179	break;
1180	case VTableComponent::CK_DeletingDtorPointer:
1181	// We've already added the thunk when we saw the complete dtor pointer.
1182	continue;
1183	}
1184
1185	if (MD->getParent() == MostDerivedClass)
1186	AddThunk(MD, Thunk);
1187	}
1188	}
1189
1190	ReturnAdjustment
1191	ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {
1192	ReturnAdjustment Adjustment;
1193
1194	if (!Offset.isEmpty()) {
1195	if (Offset.VirtualBase) {
1196	// Get the virtual base offset offset.
1197	if (Offset.DerivedClass == MostDerivedClass) {
1198	// We can get the offset offset directly from our map.
1199	Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1200	VBaseOffsetOffsets.lookup(Val: Offset.VirtualBase).getQuantity();
1201	} else {
1202	Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1203	VTables.getVirtualBaseOffsetOffset(RD: Offset.DerivedClass,
1204	VBase: Offset.VirtualBase).getQuantity();
1205	}
1206	}
1207
1208	Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1209	}
1210
1211	return Adjustment;
1212	}
1213
1214	BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
1215	BaseSubobject Base, BaseSubobject Derived) const {
1216	const CXXRecordDecl *BaseRD = Base.getBase();
1217	const CXXRecordDecl *DerivedRD = Derived.getBase();
1218
1219	CXXBasePaths Paths(/*FindAmbiguities=*/true,
1220	/*RecordPaths=*/true, /*DetectVirtual=*/true);
1221
1222	if (!DerivedRD->isDerivedFrom(Base: BaseRD, Paths))
1223	llvm_unreachable("Class must be derived from the passed in base class!");
1224
1225	// We have to go through all the paths, and see which one leads us to the
1226	// right base subobject.
1227	for (const CXXBasePath &Path : Paths) {
1228	BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, Path);
1229
1230	CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;
1231
1232	if (Offset.VirtualBase) {
1233	// If we have a virtual base class, the non-virtual offset is relative
1234	// to the virtual base class offset.
1235	const ASTRecordLayout &LayoutClassLayout =
1236	Context.getASTRecordLayout(LayoutClass);
1237
1238	/// Get the virtual base offset, relative to the most derived class
1239	/// layout.
1240	OffsetToBaseSubobject +=
1241	LayoutClassLayout.getVBaseClassOffset(VBase: Offset.VirtualBase);
1242	} else {
1243	// Otherwise, the non-virtual offset is relative to the derived class
1244	// offset.
1245	OffsetToBaseSubobject += Derived.getBaseOffset();
1246	}
1247
1248	// Check if this path gives us the right base subobject.
1249	if (OffsetToBaseSubobject == Base.getBaseOffset()) {
1250	// Since we're going from the base class _to_ the derived class, we'll
1251	// invert the non-virtual offset here.
1252	Offset.NonVirtualOffset = -Offset.NonVirtualOffset;
1253	return Offset;
1254	}
1255	}
1256
1257	return BaseOffset();
1258	}
1259
1260	ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
1261	const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
1262	FinalOverriders::OverriderInfo Overrider) {
1263	// Ignore adjustments for pure virtual member functions.
1264	if (Overrider.Method->isPureVirtual())
1265	return ThisAdjustment();
1266
1267	BaseSubobject OverriddenBaseSubobject(MD->getParent(),
1268	BaseOffsetInLayoutClass);
1269
1270	BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),
1271	Overrider.Offset);
1272
1273	// Compute the adjustment offset.
1274	BaseOffset Offset = ComputeThisAdjustmentBaseOffset(Base: OverriddenBaseSubobject,
1275	Derived: OverriderBaseSubobject);
1276	if (Offset.isEmpty())
1277	return ThisAdjustment();
1278
1279	ThisAdjustment Adjustment;
1280
1281	if (Offset.VirtualBase) {
1282	// Get the vcall offset map for this virtual base.
1283	VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];
1284
1285	if (VCallOffsets.empty()) {
1286	// We don't have vcall offsets for this virtual base, go ahead and
1287	// build them.
1288	VCallAndVBaseOffsetBuilder Builder(
1289	VTables, MostDerivedClass, MostDerivedClass,
1290	/*Overriders=*/nullptr,
1291	BaseSubobject(Offset.VirtualBase, CharUnits::Zero()),
1292	/*BaseIsVirtual=*/true,
1293	/*OffsetInLayoutClass=*/
1294	CharUnits::Zero());
1295
1296	VCallOffsets = Builder.getVCallOffsets();
1297	}
1298
1299	Adjustment.Virtual.Itanium.VCallOffsetOffset =
1300	VCallOffsets.getVCallOffsetOffset(MD).getQuantity();
1301	}
1302
1303	// Set the non-virtual part of the adjustment.
1304	Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1305
1306	return Adjustment;
1307	}
1308
1309	void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
1310	ReturnAdjustment ReturnAdjustment) {
1311	if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(Val: MD)) {
1312	assert(ReturnAdjustment.isEmpty() &&
1313	"Destructor can't have return adjustment!");
1314
1315	// Add both the complete destructor and the deleting destructor.
1316	Components.push_back(Elt: VTableComponent::MakeCompleteDtor(DD));
1317	Components.push_back(Elt: VTableComponent::MakeDeletingDtor(DD));
1318	} else {
1319	// Add the return adjustment if necessary.
1320	if (!ReturnAdjustment.isEmpty())
1321	VTableThunks[Components.size()].Return = ReturnAdjustment;
1322
1323	// Add the function.
1324	Components.push_back(Elt: VTableComponent::MakeFunction(MD));
1325	}
1326	}
1327
1328	/// OverridesIndirectMethodInBase - Return whether the given member function
1329	/// overrides any methods in the set of given bases.
1330	/// Unlike OverridesMethodInBase, this checks "overriders of overriders".
1331	/// For example, if we have:
1332	///
1333	/// struct A { virtual void f(); }
1334	/// struct B : A { virtual void f(); }
1335	/// struct C : B { virtual void f(); }
1336	///
1337	/// OverridesIndirectMethodInBase will return true if given C::f as the method
1338	/// and { A } as the set of bases.
1339	static bool OverridesIndirectMethodInBases(
1340	const CXXMethodDecl *MD,
1341	ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {
1342	if (Bases.count(key: MD->getParent()))
1343	return true;
1344
1345	for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1346	// Check "indirect overriders".
1347	if (OverridesIndirectMethodInBases(MD: OverriddenMD, Bases))
1348	return true;
1349	}
1350
1351	return false;
1352	}
1353
1354	bool ItaniumVTableBuilder::IsOverriderUsed(
1355	const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
1356	const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1357	CharUnits FirstBaseOffsetInLayoutClass) const {
1358	// If the base and the first base in the primary base chain have the same
1359	// offsets, then this overrider will be used.
1360	if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)
1361	return true;
1362
1363	// We know now that Base (or a direct or indirect base of it) is a primary
1364	// base in part of the class hierarchy, but not a primary base in the most
1365	// derived class.
1366
1367	// If the overrider is the first base in the primary base chain, we know
1368	// that the overrider will be used.
1369	if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)
1370	return true;
1371
1372	ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;
1373
1374	const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;
1375	PrimaryBases.insert(X: RD);
1376
1377	// Now traverse the base chain, starting with the first base, until we find
1378	// the base that is no longer a primary base.
1379	while (true) {
1380	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1381	const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1382
1383	if (!PrimaryBase)
1384	break;
1385
1386	if (Layout.isPrimaryBaseVirtual()) {
1387	assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1388	"Primary base should always be at offset 0!");
1389
1390	const ASTRecordLayout &LayoutClassLayout =
1391	Context.getASTRecordLayout(LayoutClass);
1392
1393	// Now check if this is the primary base that is not a primary base in the
1394	// most derived class.
1395	if (LayoutClassLayout.getVBaseClassOffset(VBase: PrimaryBase) !=
1396	FirstBaseOffsetInLayoutClass) {
1397	// We found it, stop walking the chain.
1398	break;
1399	}
1400	} else {
1401	assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1402	"Primary base should always be at offset 0!");
1403	}
1404
1405	if (!PrimaryBases.insert(X: PrimaryBase))
1406	llvm_unreachable("Found a duplicate primary base!");
1407
1408	RD = PrimaryBase;
1409	}
1410
1411	// If the final overrider is an override of one of the primary bases,
1412	// then we know that it will be used.
1413	return OverridesIndirectMethodInBases(MD: Overrider, Bases&: PrimaryBases);
1414	}
1415
1416	typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
1417
1418	/// FindNearestOverriddenMethod - Given a method, returns the overridden method
1419	/// from the nearest base. Returns null if no method was found.
1420	/// The Bases are expected to be sorted in a base-to-derived order.
1421	static const CXXMethodDecl *
1422	FindNearestOverriddenMethod(const CXXMethodDecl *MD,
1423	BasesSetVectorTy &Bases) {
1424	OverriddenMethodsSetTy OverriddenMethods;
1425	ComputeAllOverriddenMethods(MD, OverriddenMethods);
1426
1427	for (const CXXRecordDecl *PrimaryBase : llvm::reverse(C&: Bases)) {
1428	// Now check the overridden methods.
1429	for (const CXXMethodDecl *OverriddenMD : OverriddenMethods) {
1430	// We found our overridden method.
1431	if (OverriddenMD->getParent() == PrimaryBase)
1432	return OverriddenMD;
1433	}
1434	}
1435
1436	return nullptr;
1437	}
1438
1439	void ItaniumVTableBuilder::AddMethods(
1440	BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
1441	const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1442	CharUnits FirstBaseOffsetInLayoutClass,
1443	PrimaryBasesSetVectorTy &PrimaryBases) {
1444	// Itanium C++ ABI 2.5.2:
1445	// The order of the virtual function pointers in a virtual table is the
1446	// order of declaration of the corresponding member functions in the class.
1447	//
1448	// There is an entry for any virtual function declared in a class,
1449	// whether it is a new function or overrides a base class function,
1450	// unless it overrides a function from the primary base, and conversion
1451	// between their return types does not require an adjustment.
1452
1453	const CXXRecordDecl *RD = Base.getBase();
1454	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1455
1456	if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1457	CharUnits PrimaryBaseOffset;
1458	CharUnits PrimaryBaseOffsetInLayoutClass;
1459	if (Layout.isPrimaryBaseVirtual()) {
1460	assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1461	"Primary vbase should have a zero offset!");
1462
1463	const ASTRecordLayout &MostDerivedClassLayout =
1464	Context.getASTRecordLayout(MostDerivedClass);
1465
1466	PrimaryBaseOffset =
1467	MostDerivedClassLayout.getVBaseClassOffset(VBase: PrimaryBase);
1468
1469	const ASTRecordLayout &LayoutClassLayout =
1470	Context.getASTRecordLayout(LayoutClass);
1471
1472	PrimaryBaseOffsetInLayoutClass =
1473	LayoutClassLayout.getVBaseClassOffset(VBase: PrimaryBase);
1474	} else {
1475	assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1476	"Primary base should have a zero offset!");
1477
1478	PrimaryBaseOffset = Base.getBaseOffset();
1479	PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;
1480	}
1481
1482	AddMethods(Base: BaseSubobject(PrimaryBase, PrimaryBaseOffset),
1483	BaseOffsetInLayoutClass: PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain,
1484	FirstBaseOffsetInLayoutClass, PrimaryBases);
1485
1486	if (!PrimaryBases.insert(X: PrimaryBase))
1487	llvm_unreachable("Found a duplicate primary base!");
1488	}
1489
1490	typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;
1491	NewVirtualFunctionsTy NewVirtualFunctions;
1492
1493	llvm::SmallVector<const CXXMethodDecl*, 4> NewImplicitVirtualFunctions;
1494
1495	// Now go through all virtual member functions and add them.
1496	for (const auto *MD : RD->methods()) {
1497	if (!ItaniumVTableContext::hasVtableSlot(MD))
1498	continue;
1499	MD = MD->getCanonicalDecl();
1500
1501	// Get the final overrider.
1502	FinalOverriders::OverriderInfo Overrider =
1503	Overriders.getOverrider(MD, BaseOffset: Base.getBaseOffset());
1504
1505	// Check if this virtual member function overrides a method in a primary
1506	// base. If this is the case, and the return type doesn't require adjustment
1507	// then we can just use the member function from the primary base.
1508	if (const CXXMethodDecl *OverriddenMD =
1509	FindNearestOverriddenMethod(MD, Bases&: PrimaryBases)) {
1510	if (ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: MD,
1511	BaseMD: OverriddenMD).isEmpty()) {
1512	// Replace the method info of the overridden method with our own
1513	// method.
1514	assert(MethodInfoMap.count(OverriddenMD) &&
1515	"Did not find the overridden method!");
1516	MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];
1517
1518	MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1519	OverriddenMethodInfo.VTableIndex);
1520
1521	assert(!MethodInfoMap.count(MD) &&
1522	"Should not have method info for this method yet!");
1523
1524	MethodInfoMap.insert(KV: std::make_pair(x&: MD, y&: MethodInfo));
1525	MethodInfoMap.erase(Val: OverriddenMD);
1526
1527	// If the overridden method exists in a virtual base class or a direct
1528	// or indirect base class of a virtual base class, we need to emit a
1529	// thunk if we ever have a class hierarchy where the base class is not
1530	// a primary base in the complete object.
1531	if (!isBuildingConstructorVTable() && OverriddenMD != MD) {
1532	// Compute the this adjustment.
1533	ThisAdjustment ThisAdjustment =
1534	ComputeThisAdjustment(MD: OverriddenMD, BaseOffsetInLayoutClass,
1535	Overrider);
1536
1537	if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&
1538	Overrider.Method->getParent() == MostDerivedClass) {
1539
1540	// There's no return adjustment from OverriddenMD and MD,
1541	// but that doesn't mean there isn't one between MD and
1542	// the final overrider.
1543	BaseOffset ReturnAdjustmentOffset =
1544	ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: Overrider.Method, BaseMD: MD);
1545	ReturnAdjustment ReturnAdjustment =
1546	ComputeReturnAdjustment(Offset: ReturnAdjustmentOffset);
1547
1548	// This is a virtual thunk for the most derived class, add it.
1549	AddThunk(MD: Overrider.Method,
1550	Thunk: ThunkInfo(ThisAdjustment, ReturnAdjustment));
1551	}
1552	}
1553
1554	continue;
1555	}
1556	}
1557
1558	if (MD->isImplicit())
1559	NewImplicitVirtualFunctions.push_back(Elt: MD);
1560	else
1561	NewVirtualFunctions.push_back(Elt: MD);
1562	}
1563
1564	std::stable_sort(
1565	first: NewImplicitVirtualFunctions.begin(), last: NewImplicitVirtualFunctions.end(),
1566	comp: [](const CXXMethodDecl *A, const CXXMethodDecl *B) {
1567	if (A == B)
1568	return false;
1569	if (A->isCopyAssignmentOperator() != B->isCopyAssignmentOperator())
1570	return A->isCopyAssignmentOperator();
1571	if (A->isMoveAssignmentOperator() != B->isMoveAssignmentOperator())
1572	return A->isMoveAssignmentOperator();
1573	if (isa<CXXDestructorDecl>(Val: A) != isa<CXXDestructorDecl>(Val: B))
1574	return isa<CXXDestructorDecl>(Val: A);
1575	assert(A->getOverloadedOperator() == OO_EqualEqual &&
1576	B->getOverloadedOperator() == OO_EqualEqual &&
1577	"unexpected or duplicate implicit virtual function");
1578	// We rely on Sema to have declared the operator== members in the
1579	// same order as the corresponding operator<=> members.
1580	return false;
1581	});
1582	NewVirtualFunctions.append(in_start: NewImplicitVirtualFunctions.begin(),
1583	in_end: NewImplicitVirtualFunctions.end());
1584
1585	for (const CXXMethodDecl *MD : NewVirtualFunctions) {
1586	// Get the final overrider.
1587	FinalOverriders::OverriderInfo Overrider =
1588	Overriders.getOverrider(MD, BaseOffset: Base.getBaseOffset());
1589
1590	// Insert the method info for this method.
1591	MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1592	Components.size());
1593
1594	assert(!MethodInfoMap.count(MD) &&
1595	"Should not have method info for this method yet!");
1596	MethodInfoMap.insert(KV: std::make_pair(x&: MD, y&: MethodInfo));
1597
1598	// Check if this overrider is going to be used.
1599	const CXXMethodDecl *OverriderMD = Overrider.Method;
1600	if (!IsOverriderUsed(Overrider: OverriderMD, BaseOffsetInLayoutClass,
1601	FirstBaseInPrimaryBaseChain,
1602	FirstBaseOffsetInLayoutClass)) {
1603	Components.push_back(Elt: VTableComponent::MakeUnusedFunction(MD: OverriderMD));
1604	continue;
1605	}
1606
1607	// Check if this overrider needs a return adjustment.
1608	// We don't want to do this for pure virtual member functions.
1609	BaseOffset ReturnAdjustmentOffset;
1610	if (!OverriderMD->isPureVirtual()) {
1611	ReturnAdjustmentOffset =
1612	ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: OverriderMD, BaseMD: MD);
1613	}
1614
1615	ReturnAdjustment ReturnAdjustment =
1616	ComputeReturnAdjustment(Offset: ReturnAdjustmentOffset);
1617
1618	AddMethod(MD: Overrider.Method, ReturnAdjustment);
1619	}
1620	}
1621
1622	void ItaniumVTableBuilder::LayoutVTable() {
1623	LayoutPrimaryAndSecondaryVTables(Base: BaseSubobject(MostDerivedClass,
1624	CharUnits::Zero()),
1625	/*BaseIsMorallyVirtual=*/false,
1626	BaseIsVirtualInLayoutClass: MostDerivedClassIsVirtual,
1627	OffsetInLayoutClass: MostDerivedClassOffset);
1628
1629	VisitedVirtualBasesSetTy VBases;
1630
1631	// Determine the primary virtual bases.
1632	DeterminePrimaryVirtualBases(RD: MostDerivedClass, OffsetInLayoutClass: MostDerivedClassOffset,
1633	VBases);
1634	VBases.clear();
1635
1636	LayoutVTablesForVirtualBases(RD: MostDerivedClass, VBases);
1637
1638	// -fapple-kext adds an extra entry at end of vtbl.
1639	bool IsAppleKext = Context.getLangOpts().AppleKext;
1640	if (IsAppleKext)
1641	Components.push_back(Elt: VTableComponent::MakeVCallOffset(Offset: CharUnits::Zero()));
1642	}
1643
1644	void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
1645	BaseSubobject Base, bool BaseIsMorallyVirtual,
1646	bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
1647	assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
1648
1649	unsigned VTableIndex = Components.size();
1650	VTableIndices.push_back(Elt: VTableIndex);
1651
1652	// Add vcall and vbase offsets for this vtable.
1653	VCallAndVBaseOffsetBuilder Builder(
1654	VTables, MostDerivedClass, LayoutClass, &Overriders, Base,
1655	BaseIsVirtualInLayoutClass, OffsetInLayoutClass);
1656	Components.append(in_start: Builder.components_begin(), in_end: Builder.components_end());
1657
1658	// Check if we need to add these vcall offsets.
1659	if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {
1660	VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];
1661
1662	if (VCallOffsets.empty())
1663	VCallOffsets = Builder.getVCallOffsets();
1664	}
1665
1666	// If we're laying out the most derived class we want to keep track of the
1667	// virtual base class offset offsets.
1668	if (Base.getBase() == MostDerivedClass)
1669	VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();
1670
1671	// Add the offset to top.
1672	CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;
1673	Components.push_back(Elt: VTableComponent::MakeOffsetToTop(Offset: OffsetToTop));
1674
1675	// Next, add the RTTI.
1676	if (!Context.getLangOpts().OmitVTableRTTI)
1677	Components.push_back(Elt: VTableComponent::MakeRTTI(RD: MostDerivedClass));
1678
1679	uint64_t AddressPoint = Components.size();
1680
1681	// Now go through all virtual member functions and add them.
1682	PrimaryBasesSetVectorTy PrimaryBases;
1683	AddMethods(Base, BaseOffsetInLayoutClass: OffsetInLayoutClass,
1684	FirstBaseInPrimaryBaseChain: Base.getBase(), FirstBaseOffsetInLayoutClass: OffsetInLayoutClass,
1685	PrimaryBases);
1686
1687	const CXXRecordDecl *RD = Base.getBase();
1688	if (RD == MostDerivedClass) {
1689	assert(MethodVTableIndices.empty());
1690	for (const auto &I : MethodInfoMap) {
1691	const CXXMethodDecl *MD = I.first;
1692	const MethodInfo &MI = I.second;
1693	if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(Val: MD)) {
1694	MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]
1695	= MI.VTableIndex - AddressPoint;
1696	MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]
1697	= MI.VTableIndex + 1 - AddressPoint;
1698	} else {
1699	MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;
1700	}
1701	}
1702	}
1703
1704	// Compute 'this' pointer adjustments.
1705	ComputeThisAdjustments();
1706
1707	// Add all address points.
1708	while (true) {
1709	AddressPoints.insert(
1710	KV: std::make_pair(x: BaseSubobject(RD, OffsetInLayoutClass),
1711	y: VTableLayout::AddressPointLocation{
1712	.VTableIndex: unsigned(VTableIndices.size() - 1),
1713	.AddressPointIndex: unsigned(AddressPoint - VTableIndex)}));
1714
1715	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1716	const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1717
1718	if (!PrimaryBase)
1719	break;
1720
1721	if (Layout.isPrimaryBaseVirtual()) {
1722	// Check if this virtual primary base is a primary base in the layout
1723	// class. If it's not, we don't want to add it.
1724	const ASTRecordLayout &LayoutClassLayout =
1725	Context.getASTRecordLayout(LayoutClass);
1726
1727	if (LayoutClassLayout.getVBaseClassOffset(VBase: PrimaryBase) !=
1728	OffsetInLayoutClass) {
1729	// We don't want to add this class (or any of its primary bases).
1730	break;
1731	}
1732	}
1733
1734	RD = PrimaryBase;
1735	}
1736
1737	// Layout secondary vtables.
1738	LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);
1739	}
1740
1741	void
1742	ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
1743	bool BaseIsMorallyVirtual,
1744	CharUnits OffsetInLayoutClass) {
1745	// Itanium C++ ABI 2.5.2:
1746	// Following the primary virtual table of a derived class are secondary
1747	// virtual tables for each of its proper base classes, except any primary
1748	// base(s) with which it shares its primary virtual table.
1749
1750	const CXXRecordDecl *RD = Base.getBase();
1751	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1752	const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1753
1754	for (const auto &B : RD->bases()) {
1755	// Ignore virtual bases, we'll emit them later.
1756	if (B.isVirtual())
1757	continue;
1758
1759	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1760
1761	// Ignore bases that don't have a vtable.
1762	if (!BaseDecl->isDynamicClass())
1763	continue;
1764
1765	if (isBuildingConstructorVTable()) {
1766	// Itanium C++ ABI 2.6.4:
1767	// Some of the base class subobjects may not need construction virtual
1768	// tables, which will therefore not be present in the construction
1769	// virtual table group, even though the subobject virtual tables are
1770	// present in the main virtual table group for the complete object.
1771	if (!BaseIsMorallyVirtual && !BaseDecl->getNumVBases())
1772	continue;
1773	}
1774
1775	// Get the base offset of this base.
1776	CharUnits RelativeBaseOffset = Layout.getBaseClassOffset(Base: BaseDecl);
1777	CharUnits BaseOffset = Base.getBaseOffset() + RelativeBaseOffset;
1778
1779	CharUnits BaseOffsetInLayoutClass =
1780	OffsetInLayoutClass + RelativeBaseOffset;
1781
1782	// Don't emit a secondary vtable for a primary base. We might however want
1783	// to emit secondary vtables for other bases of this base.
1784	if (BaseDecl == PrimaryBase) {
1785	LayoutSecondaryVTables(Base: BaseSubobject(BaseDecl, BaseOffset),
1786	BaseIsMorallyVirtual, OffsetInLayoutClass: BaseOffsetInLayoutClass);
1787	continue;
1788	}
1789
1790	// Layout the primary vtable (and any secondary vtables) for this base.
1791	LayoutPrimaryAndSecondaryVTables(
1792	Base: BaseSubobject(BaseDecl, BaseOffset),
1793	BaseIsMorallyVirtual,
1794	/*BaseIsVirtualInLayoutClass=*/false,
1795	OffsetInLayoutClass: BaseOffsetInLayoutClass);
1796	}
1797	}
1798
1799	void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
1800	const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
1801	VisitedVirtualBasesSetTy &VBases) {
1802	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1803
1804	// Check if this base has a primary base.
1805	if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1806
1807	// Check if it's virtual.
1808	if (Layout.isPrimaryBaseVirtual()) {
1809	bool IsPrimaryVirtualBase = true;
1810
1811	if (isBuildingConstructorVTable()) {
1812	// Check if the base is actually a primary base in the class we use for
1813	// layout.
1814	const ASTRecordLayout &LayoutClassLayout =
1815	Context.getASTRecordLayout(LayoutClass);
1816
1817	CharUnits PrimaryBaseOffsetInLayoutClass =
1818	LayoutClassLayout.getVBaseClassOffset(VBase: PrimaryBase);
1819
1820	// We know that the base is not a primary base in the layout class if
1821	// the base offsets are different.
1822	if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)
1823	IsPrimaryVirtualBase = false;
1824	}
1825
1826	if (IsPrimaryVirtualBase)
1827	PrimaryVirtualBases.insert(Ptr: PrimaryBase);
1828	}
1829	}
1830
1831	// Traverse bases, looking for more primary virtual bases.
1832	for (const auto &B : RD->bases()) {
1833	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1834
1835	CharUnits BaseOffsetInLayoutClass;
1836
1837	if (B.isVirtual()) {
1838	if (!VBases.insert(Ptr: BaseDecl).second)
1839	continue;
1840
1841	const ASTRecordLayout &LayoutClassLayout =
1842	Context.getASTRecordLayout(LayoutClass);
1843
1844	BaseOffsetInLayoutClass =
1845	LayoutClassLayout.getVBaseClassOffset(VBase: BaseDecl);
1846	} else {
1847	BaseOffsetInLayoutClass =
1848	OffsetInLayoutClass + Layout.getBaseClassOffset(Base: BaseDecl);
1849	}
1850
1851	DeterminePrimaryVirtualBases(RD: BaseDecl, OffsetInLayoutClass: BaseOffsetInLayoutClass, VBases);
1852	}
1853	}
1854
1855	void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
1856	const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) {
1857	// Itanium C++ ABI 2.5.2:
1858	// Then come the virtual base virtual tables, also in inheritance graph
1859	// order, and again excluding primary bases (which share virtual tables with
1860	// the classes for which they are primary).
1861	for (const auto &B : RD->bases()) {
1862	const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1863
1864	// Check if this base needs a vtable. (If it's virtual, not a primary base
1865	// of some other class, and we haven't visited it before).
1866	if (B.isVirtual() && BaseDecl->isDynamicClass() &&
1867	!PrimaryVirtualBases.count(Ptr: BaseDecl) &&
1868	VBases.insert(Ptr: BaseDecl).second) {
1869	const ASTRecordLayout &MostDerivedClassLayout =
1870	Context.getASTRecordLayout(MostDerivedClass);
1871	CharUnits BaseOffset =
1872	MostDerivedClassLayout.getVBaseClassOffset(VBase: BaseDecl);
1873
1874	const ASTRecordLayout &LayoutClassLayout =
1875	Context.getASTRecordLayout(LayoutClass);
1876	CharUnits BaseOffsetInLayoutClass =
1877	LayoutClassLayout.getVBaseClassOffset(VBase: BaseDecl);
1878
1879	LayoutPrimaryAndSecondaryVTables(
1880	Base: BaseSubobject(BaseDecl, BaseOffset),
1881	/*BaseIsMorallyVirtual=*/true,
1882	/*BaseIsVirtualInLayoutClass=*/true,
1883	OffsetInLayoutClass: BaseOffsetInLayoutClass);
1884	}
1885
1886	// We only need to check the base for virtual base vtables if it actually
1887	// has virtual bases.
1888	if (BaseDecl->getNumVBases())
1889	LayoutVTablesForVirtualBases(RD: BaseDecl, VBases);
1890	}
1891	}
1892
1893	/// dumpLayout - Dump the vtable layout.
1894	void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {
1895	// FIXME: write more tests that actually use the dumpLayout output to prevent
1896	// ItaniumVTableBuilder regressions.
1897
1898	if (isBuildingConstructorVTable()) {
1899	Out << "Construction vtable for ('";
1900	MostDerivedClass->printQualifiedName(Out);
1901	Out << "', ";
1902	Out << MostDerivedClassOffset.getQuantity() << ") in '";
1903	LayoutClass->printQualifiedName(Out);
1904	} else {
1905	Out << "Vtable for '";
1906	MostDerivedClass->printQualifiedName(Out);
1907	}
1908	Out << "' (" << Components.size() << " entries).\n";
1909
1910	// Iterate through the address points and insert them into a new map where
1911	// they are keyed by the index and not the base object.
1912	// Since an address point can be shared by multiple subobjects, we use an
1913	// STL multimap.
1914	std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;
1915	for (const auto &AP : AddressPoints) {
1916	const BaseSubobject &Base = AP.first;
1917	uint64_t Index =
1918	VTableIndices[AP.second.VTableIndex] + AP.second.AddressPointIndex;
1919
1920	AddressPointsByIndex.insert(x: std::make_pair(x&: Index, y: Base));
1921	}
1922
1923	for (unsigned I = 0, E = Components.size(); I != E; ++I) {
1924	uint64_t Index = I;
1925
1926	Out << llvm::format(Fmt: "%4d | ", Vals: I);
1927
1928	const VTableComponent &Component = Components[I];
1929
1930	// Dump the component.
1931	switch (Component.getKind()) {
1932
1933	case VTableComponent::CK_VCallOffset:
1934	Out << "vcall_offset ("
1935	<< Component.getVCallOffset().getQuantity()
1936	<< ")";
1937	break;
1938
1939	case VTableComponent::CK_VBaseOffset:
1940	Out << "vbase_offset ("
1941	<< Component.getVBaseOffset().getQuantity()
1942	<< ")";
1943	break;
1944
1945	case VTableComponent::CK_OffsetToTop:
1946	Out << "offset_to_top ("
1947	<< Component.getOffsetToTop().getQuantity()
1948	<< ")";
1949	break;
1950
1951	case VTableComponent::CK_RTTI:
1952	Component.getRTTIDecl()->printQualifiedName(Out);
1953	Out << " RTTI";
1954	break;
1955
1956	case VTableComponent::CK_FunctionPointer: {
1957	const CXXMethodDecl *MD = Component.getFunctionDecl();
1958
1959	std::string Str = PredefinedExpr::ComputeName(
1960	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
1961	Out << Str;
1962	if (MD->isPureVirtual())
1963	Out << " [pure]";
1964
1965	if (MD->isDeleted())
1966	Out << " [deleted]";
1967
1968	ThunkInfo Thunk = VTableThunks.lookup(Val: I);
1969	if (!Thunk.isEmpty()) {
1970	// If this function pointer has a return adjustment, dump it.
1971	if (!Thunk.Return.isEmpty()) {
1972	Out << "\n [return adjustment: ";
1973	Out << Thunk.Return.NonVirtual << " non-virtual";
1974
1975	if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
1976	Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
1977	Out << " vbase offset offset";
1978	}
1979
1980	Out << ']';
1981	}
1982
1983	// If this function pointer has a 'this' pointer adjustment, dump it.
1984	if (!Thunk.This.isEmpty()) {
1985	Out << "\n [this adjustment: ";
1986	Out << Thunk.This.NonVirtual << " non-virtual";
1987
1988	if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
1989	Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
1990	Out << " vcall offset offset";
1991	}
1992
1993	Out << ']';
1994	}
1995	}
1996
1997	break;
1998	}
1999
2000	case VTableComponent::CK_CompleteDtorPointer:
2001	case VTableComponent::CK_DeletingDtorPointer: {
2002	bool IsComplete =
2003	Component.getKind() == VTableComponent::CK_CompleteDtorPointer;
2004
2005	const CXXDestructorDecl *DD = Component.getDestructorDecl();
2006
2007	DD->printQualifiedName(Out);
2008	if (IsComplete)
2009	Out << "() [complete]";
2010	else
2011	Out << "() [deleting]";
2012
2013	if (DD->isPureVirtual())
2014	Out << " [pure]";
2015
2016	ThunkInfo Thunk = VTableThunks.lookup(Val: I);
2017	if (!Thunk.isEmpty()) {
2018	// If this destructor has a 'this' pointer adjustment, dump it.
2019	if (!Thunk.This.isEmpty()) {
2020	Out << "\n [this adjustment: ";
2021	Out << Thunk.This.NonVirtual << " non-virtual";
2022
2023	if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2024	Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2025	Out << " vcall offset offset";
2026	}
2027
2028	Out << ']';
2029	}
2030	}
2031
2032	break;
2033	}
2034
2035	case VTableComponent::CK_UnusedFunctionPointer: {
2036	const CXXMethodDecl *MD = Component.getUnusedFunctionDecl();
2037
2038	std::string Str = PredefinedExpr::ComputeName(
2039	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
2040	Out << "[unused] " << Str;
2041	if (MD->isPureVirtual())
2042	Out << " [pure]";
2043	}
2044
2045	}
2046
2047	Out << '\n';
2048
2049	// Dump the next address point.
2050	uint64_t NextIndex = Index + 1;
2051	if (AddressPointsByIndex.count(x: NextIndex)) {
2052	if (AddressPointsByIndex.count(x: NextIndex) == 1) {
2053	const BaseSubobject &Base =
2054	AddressPointsByIndex.find(x: NextIndex)->second;
2055
2056	Out << " -- (";
2057	Base.getBase()->printQualifiedName(Out);
2058	Out << ", " << Base.getBaseOffset().getQuantity();
2059	Out << ") vtable address --\n";
2060	} else {
2061	CharUnits BaseOffset =
2062	AddressPointsByIndex.lower_bound(x: NextIndex)->second.getBaseOffset();
2063
2064	// We store the class names in a set to get a stable order.
2065	std::set<std::string> ClassNames;
2066	for (const auto &I :
2067	llvm::make_range(p: AddressPointsByIndex.equal_range(x: NextIndex))) {
2068	assert(I.second.getBaseOffset() == BaseOffset &&
2069	"Invalid base offset!");
2070	const CXXRecordDecl *RD = I.second.getBase();
2071	ClassNames.insert(RD->getQualifiedNameAsString());
2072	}
2073
2074	for (const std::string &Name : ClassNames) {
2075	Out << " -- (" << Name;
2076	Out << ", " << BaseOffset.getQuantity() << ") vtable address --\n";
2077	}
2078	}
2079	}
2080	}
2081
2082	Out << '\n';
2083
2084	if (isBuildingConstructorVTable())
2085	return;
2086
2087	if (MostDerivedClass->getNumVBases()) {
2088	// We store the virtual base class names and their offsets in a map to get
2089	// a stable order.
2090
2091	std::map<std::string, CharUnits> ClassNamesAndOffsets;
2092	for (const auto &I : VBaseOffsetOffsets) {
2093	std::string ClassName = I.first->getQualifiedNameAsString();
2094	CharUnits OffsetOffset = I.second;
2095	ClassNamesAndOffsets.insert(x: std::make_pair(x&: ClassName, y&: OffsetOffset));
2096	}
2097
2098	Out << "Virtual base offset offsets for '";
2099	MostDerivedClass->printQualifiedName(Out);
2100	Out << "' (";
2101	Out << ClassNamesAndOffsets.size();
2102	Out << (ClassNamesAndOffsets.size() == 1 ? " entry" : " entries") << ").\n";
2103
2104	for (const auto &I : ClassNamesAndOffsets)
2105	Out << " " << I.first << " | " << I.second.getQuantity() << '\n';
2106
2107	Out << "\n";
2108	}
2109
2110	if (!Thunks.empty()) {
2111	// We store the method names in a map to get a stable order.
2112	std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
2113
2114	for (const auto &I : Thunks) {
2115	const CXXMethodDecl *MD = I.first;
2116	std::string MethodName = PredefinedExpr::ComputeName(
2117	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
2118
2119	MethodNamesAndDecls.insert(x: std::make_pair(x&: MethodName, y&: MD));
2120	}
2121
2122	for (const auto &I : MethodNamesAndDecls) {
2123	const std::string &MethodName = I.first;
2124	const CXXMethodDecl *MD = I.second;
2125
2126	ThunkInfoVectorTy ThunksVector = Thunks[MD];
2127	llvm::sort(C&: ThunksVector, Comp: [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
2128	assert(LHS.Method == nullptr && RHS.Method == nullptr);
2129	return std::tie(args: LHS.This, args: LHS.Return) < std::tie(args: RHS.This, args: RHS.Return);
2130	});
2131
2132	Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
2133	Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
2134
2135	for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
2136	const ThunkInfo &Thunk = ThunksVector[I];
2137
2138	Out << llvm::format(Fmt: "%4d | ", Vals: I);
2139
2140	// If this function pointer has a return pointer adjustment, dump it.
2141	if (!Thunk.Return.isEmpty()) {
2142	Out << "return adjustment: " << Thunk.Return.NonVirtual;
2143	Out << " non-virtual";
2144	if (Thunk.Return.Virtual.Itanium.VBaseOffsetOffset) {
2145	Out << ", " << Thunk.Return.Virtual.Itanium.VBaseOffsetOffset;
2146	Out << " vbase offset offset";
2147	}
2148
2149	if (!Thunk.This.isEmpty())
2150	Out << "\n ";
2151	}
2152
2153	// If this function pointer has a 'this' pointer adjustment, dump it.
2154	if (!Thunk.This.isEmpty()) {
2155	Out << "this adjustment: ";
2156	Out << Thunk.This.NonVirtual << " non-virtual";
2157
2158	if (Thunk.This.Virtual.Itanium.VCallOffsetOffset) {
2159	Out << ", " << Thunk.This.Virtual.Itanium.VCallOffsetOffset;
2160	Out << " vcall offset offset";
2161	}
2162	}
2163
2164	Out << '\n';
2165	}
2166
2167	Out << '\n';
2168	}
2169	}
2170
2171	// Compute the vtable indices for all the member functions.
2172	// Store them in a map keyed by the index so we'll get a sorted table.
2173	std::map<uint64_t, std::string> IndicesMap;
2174
2175	for (const auto *MD : MostDerivedClass->methods()) {
2176	// We only want virtual member functions.
2177	if (!ItaniumVTableContext::hasVtableSlot(MD))
2178	continue;
2179	MD = MD->getCanonicalDecl();
2180
2181	std::string MethodName = PredefinedExpr::ComputeName(
2182	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
2183
2184	if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(Val: MD)) {
2185	GlobalDecl GD(DD, Dtor_Complete);
2186	assert(MethodVTableIndices.count(GD));
2187	uint64_t VTableIndex = MethodVTableIndices[GD];
2188	IndicesMap[VTableIndex] = MethodName + " [complete]";
2189	IndicesMap[VTableIndex + 1] = MethodName + " [deleting]";
2190	} else {
2191	assert(MethodVTableIndices.count(MD));
2192	IndicesMap[MethodVTableIndices[MD]] = MethodName;
2193	}
2194	}
2195
2196	// Print the vtable indices for all the member functions.
2197	if (!IndicesMap.empty()) {
2198	Out << "VTable indices for '";
2199	MostDerivedClass->printQualifiedName(Out);
2200	Out << "' (" << IndicesMap.size() << " entries).\n";
2201
2202	for (const auto &I : IndicesMap) {
2203	uint64_t VTableIndex = I.first;
2204	const std::string &MethodName = I.second;
2205
2206	Out << llvm::format(Fmt: "%4" PRIu64 " | ", Vals: VTableIndex) << MethodName
2207	<< '\n';
2208	}
2209	}
2210
2211	Out << '\n';
2212	}
2213	}
2214
2215	static VTableLayout::AddressPointsIndexMapTy
2216	MakeAddressPointIndices(const VTableLayout::AddressPointsMapTy &addressPoints,
2217	unsigned numVTables) {
2218	VTableLayout::AddressPointsIndexMapTy indexMap(numVTables);
2219
2220	for (auto it = addressPoints.begin(); it != addressPoints.end(); ++it) {
2221	const auto &addressPointLoc = it->second;
2222	unsigned vtableIndex = addressPointLoc.VTableIndex;
2223	unsigned addressPoint = addressPointLoc.AddressPointIndex;
2224	if (indexMap[vtableIndex]) {
2225	// Multiple BaseSubobjects can map to the same AddressPointLocation, but
2226	// every vtable index should have a unique address point.
2227	assert(indexMap[vtableIndex] == addressPoint &&
2228	"Every vtable index should have a unique address point. Found a "
2229	"vtable that has two different address points.");
2230	} else {
2231	indexMap[vtableIndex] = addressPoint;
2232	}
2233	}
2234
2235	// Note that by this point, not all the address may be initialized if the
2236	// AddressPoints map is empty. This is ok if the map isn't needed. See
2237	// MicrosoftVTableContext::computeVTableRelatedInformation() which uses an
2238	// emprt map.
2239	return indexMap;
2240	}
2241
2242	VTableLayout::VTableLayout(ArrayRef<size_t> VTableIndices,
2243	ArrayRef<VTableComponent> VTableComponents,
2244	ArrayRef<VTableThunkTy> VTableThunks,
2245	const AddressPointsMapTy &AddressPoints)
2246	: VTableComponents(VTableComponents), VTableThunks(VTableThunks),
2247	AddressPoints(AddressPoints), AddressPointIndices(MakeAddressPointIndices(
2248	addressPoints: AddressPoints, numVTables: VTableIndices.size())) {
2249	if (VTableIndices.size() <= 1)
2250	assert(VTableIndices.size() == 1 && VTableIndices[0] == 0);
2251	else
2252	this->VTableIndices = OwningArrayRef<size_t>(VTableIndices);
2253
2254	llvm::sort(C&: this->VTableThunks, Comp: [](const VTableLayout::VTableThunkTy &LHS,
2255	const VTableLayout::VTableThunkTy &RHS) {
2256	assert((LHS.first != RHS.first || LHS.second == RHS.second) &&
2257	"Different thunks should have unique indices!");
2258	return LHS.first < RHS.first;
2259	});
2260	}
2261
2262	VTableLayout::~VTableLayout() { }
2263
2264	bool VTableContextBase::hasVtableSlot(const CXXMethodDecl *MD) {
2265	return MD->isVirtual() && !MD->isImmediateFunction();
2266	}
2267
2268	ItaniumVTableContext::ItaniumVTableContext(
2269	ASTContext &Context, VTableComponentLayout ComponentLayout)
2270	: VTableContextBase(/*MS=*/false), ComponentLayout(ComponentLayout) {}
2271
2272	ItaniumVTableContext::~ItaniumVTableContext() {}
2273
2274	uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {
2275	GD = GD.getCanonicalDecl();
2276	MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(Val: GD);
2277	if (I != MethodVTableIndices.end())
2278	return I->second;
2279
2280	const CXXRecordDecl *RD = cast<CXXMethodDecl>(Val: GD.getDecl())->getParent();
2281
2282	computeVTableRelatedInformation(RD);
2283
2284	I = MethodVTableIndices.find(Val: GD);
2285	assert(I != MethodVTableIndices.end() && "Did not find index!");
2286	return I->second;
2287	}
2288
2289	CharUnits
2290	ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
2291	const CXXRecordDecl *VBase) {
2292	ClassPairTy ClassPair(RD, VBase);
2293
2294	VirtualBaseClassOffsetOffsetsMapTy::iterator I =
2295	VirtualBaseClassOffsetOffsets.find(Val: ClassPair);
2296	if (I != VirtualBaseClassOffsetOffsets.end())
2297	return I->second;
2298
2299	VCallAndVBaseOffsetBuilder Builder(*this, RD, RD, /*Overriders=*/nullptr,
2300	BaseSubobject(RD, CharUnits::Zero()),
2301	/*BaseIsVirtual=*/false,
2302	/*OffsetInLayoutClass=*/CharUnits::Zero());
2303
2304	for (const auto &I : Builder.getVBaseOffsetOffsets()) {
2305	// Insert all types.
2306	ClassPairTy ClassPair(RD, I.first);
2307
2308	VirtualBaseClassOffsetOffsets.insert(KV: std::make_pair(x&: ClassPair, y: I.second));
2309	}
2310
2311	I = VirtualBaseClassOffsetOffsets.find(Val: ClassPair);
2312	assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");
2313
2314	return I->second;
2315	}
2316
2317	static std::unique_ptr<VTableLayout>
2318	CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
2319	SmallVector<VTableLayout::VTableThunkTy, 1>
2320	VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
2321
2322	return std::make_unique<VTableLayout>(
2323	args: Builder.VTableIndices, args: Builder.vtable_components(), args&: VTableThunks,
2324	args: Builder.getAddressPoints());
2325	}
2326
2327	void
2328	ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
2329	std::unique_ptr<const VTableLayout> &Entry = VTableLayouts[RD];
2330
2331	// Check if we've computed this information before.
2332	if (Entry)
2333	return;
2334
2335	ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),
2336	/*MostDerivedClassIsVirtual=*/false, RD);
2337	Entry = CreateVTableLayout(Builder);
2338
2339	MethodVTableIndices.insert(I: Builder.vtable_indices_begin(),
2340	E: Builder.vtable_indices_end());
2341
2342	// Add the known thunks.
2343	Thunks.insert(I: Builder.thunks_begin(), E: Builder.thunks_end());
2344
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())
2349	return;
2350
2351	const CXXRecordDecl *VBase =
2352	RD->vbases_begin()->getType()->getAsCXXRecordDecl();
2353
2354	if (VirtualBaseClassOffsetOffsets.count(Val: std::make_pair(x&: RD, y&: VBase)))
2355	return;
2356
2357	for (const auto &I : Builder.getVBaseOffsetOffsets()) {
2358	// Insert all types.
2359	ClassPairTy ClassPair(RD, I.first);
2360
2361	VirtualBaseClassOffsetOffsets.insert(KV: std::make_pair(x&: ClassPair, y: I.second));
2362	}
2363	}
2364
2365	std::unique_ptr<VTableLayout>
2366	ItaniumVTableContext::createConstructionVTableLayout(
2367	const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
2368	bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {
2369	ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,
2370	MostDerivedClassIsVirtual, LayoutClass);
2371	return CreateVTableLayout(Builder);
2372	}
2373
2374	namespace {
2375
2376	// Vtables in the Microsoft ABI are different from the Itanium ABI.
2377	//
2378	// The main differences are:
2379	// 1. Separate vftable and vbtable.
2380	//
2381	// 2. Each subobject with a vfptr gets its own vftable rather than an address
2382	// point in a single vtable shared between all the subobjects.
2383	// Each vftable is represented by a separate section and virtual calls
2384	// must be done using the vftable which has a slot for the function to be
2385	// called.
2386	//
2387	// 3. Virtual method definitions expect their 'this' parameter to point to the
2388	// first vfptr whose table provides a compatible overridden method. In many
2389	// cases, this permits the original vf-table entry to directly call
2390	// the method instead of passing through a thunk.
2391	// See example before VFTableBuilder::ComputeThisOffset below.
2392	//
2393	// A compatible overridden method is one which does not have a non-trivial
2394	// covariant-return adjustment.
2395	//
2396	// The first vfptr is the one with the lowest offset in the complete-object
2397	// layout of the defining class, and the method definition will subtract
2398	// that constant offset from the parameter value to get the real 'this'
2399	// value. Therefore, if the offset isn't really constant (e.g. if a virtual
2400	// function defined in a virtual base is overridden in a more derived
2401	// virtual base and these bases have a reverse order in the complete
2402	// object), the vf-table may require a this-adjustment thunk.
2403	//
2404	// 4. vftables do not contain new entries for overrides that merely require
2405	// this-adjustment. Together with #3, this keeps vf-tables smaller and
2406	// eliminates the need for this-adjustment thunks in many cases, at the cost
2407	// of often requiring redundant work to adjust the "this" pointer.
2408	//
2409	// 5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.
2410	// Vtordisps are emitted into the class layout if a class has
2411	// a) a user-defined ctor/dtor
2412	// and
2413	// b) a method overriding a method in a virtual base.
2414	//
2415	// To get a better understanding of this code,
2416	// you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp
2417
2418	class VFTableBuilder {
2419	public:
2420	typedef llvm::DenseMap<GlobalDecl, MethodVFTableLocation>
2421	MethodVFTableLocationsTy;
2422
2423	typedef llvm::iterator_range<MethodVFTableLocationsTy::const_iterator>
2424	method_locations_range;
2425
2426	private:
2427	/// VTables - Global vtable information.
2428	MicrosoftVTableContext &VTables;
2429
2430	/// Context - The ASTContext which we will use for layout information.
2431	ASTContext &Context;
2432
2433	/// MostDerivedClass - The most derived class for which we're building this
2434	/// vtable.
2435	const CXXRecordDecl *MostDerivedClass;
2436
2437	const ASTRecordLayout &MostDerivedClassLayout;
2438
2439	const VPtrInfo &WhichVFPtr;
2440
2441	/// FinalOverriders - The final overriders of the most derived class.
2442	const FinalOverriders Overriders;
2443
2444	/// Components - The components of the vftable being built.
2445	SmallVector<VTableComponent, 64> Components;
2446
2447	MethodVFTableLocationsTy MethodVFTableLocations;
2448
2449	/// Does this class have an RTTI component?
2450	bool HasRTTIComponent = false;
2451
2452	/// MethodInfo - Contains information about a method in a vtable.
2453	/// (Used for computing 'this' pointer adjustment thunks.
2454	struct MethodInfo {
2455	/// VBTableIndex - The nonzero index in the vbtable that
2456	/// this method's base has, or zero.
2457	const uint64_t VBTableIndex;
2458
2459	/// VFTableIndex - The index in the vftable that this method has.
2460	const uint64_t VFTableIndex;
2461
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.
2465	bool Shadowed;
2466
2467	/// UsesExtraSlot - Indicates if this vftable slot was created because
2468	/// any of the overridden slots required a return adjusting thunk.
2469	bool UsesExtraSlot;
2470
2471	MethodInfo(uint64_t VBTableIndex, uint64_t VFTableIndex,
2472	bool UsesExtraSlot = false)
2473	: VBTableIndex(VBTableIndex), VFTableIndex(VFTableIndex),
2474	Shadowed(false), UsesExtraSlot(UsesExtraSlot) {}
2475
2476	MethodInfo()
2477	: VBTableIndex(0), VFTableIndex(0), Shadowed(false),
2478	UsesExtraSlot(false) {}
2479	};
2480
2481	typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
2482
2483	/// MethodInfoMap - The information for all methods in the vftable we're
2484	/// currently building.
2485	MethodInfoMapTy MethodInfoMap;
2486
2487	typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
2488
2489	/// VTableThunks - The thunks by vftable index in the vftable currently being
2490	/// built.
2491	VTableThunksMapTy VTableThunks;
2492
2493	typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
2494	typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
2495
2496	/// Thunks - A map that contains all the thunks needed for all methods in the
2497	/// most derived class for which the vftable is currently being built.
2498	ThunksMapTy Thunks;
2499
2500	/// AddThunk - Add a thunk for the given method.
2501	void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk) {
2502	SmallVector<ThunkInfo, 1> &ThunksVector = Thunks[MD];
2503
2504	// Check if we have this thunk already.
2505	if (llvm::is_contained(Range&: ThunksVector, Element: Thunk))
2506	return;
2507
2508	ThunksVector.push_back(Elt: Thunk);
2509	}
2510
2511	/// ComputeThisOffset - Returns the 'this' argument offset for the given
2512	/// method, relative to the beginning of the MostDerivedClass.
2513	CharUnits ComputeThisOffset(FinalOverriders::OverriderInfo Overrider);
2514
2515	void CalculateVtordispAdjustment(FinalOverriders::OverriderInfo Overrider,
2516	CharUnits ThisOffset, ThisAdjustment &TA);
2517
2518	/// AddMethod - Add a single virtual member function to the vftable
2519	/// components vector.
2520	void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {
2521	if (!TI.isEmpty()) {
2522	VTableThunks[Components.size()] = TI;
2523	AddThunk(MD, Thunk: TI);
2524	}
2525	if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(Val: MD)) {
2526	assert(TI.Return.isEmpty() &&
2527	"Destructor can't have return adjustment!");
2528	Components.push_back(Elt: VTableComponent::MakeDeletingDtor(DD));
2529	} else {
2530	Components.push_back(Elt: VTableComponent::MakeFunction(MD));
2531	}
2532	}
2533
2534	/// AddMethods - Add the methods of this base subobject and the relevant
2535	/// subbases to the vftable we're currently laying out.
2536	void AddMethods(BaseSubobject Base, unsigned BaseDepth,
2537	const CXXRecordDecl *LastVBase,
2538	BasesSetVectorTy &VisitedBases);
2539
2540	void LayoutVFTable() {
2541	// RTTI data goes before all other entries.
2542	if (HasRTTIComponent)
2543	Components.push_back(Elt: VTableComponent::MakeRTTI(RD: MostDerivedClass));
2544
2545	BasesSetVectorTy VisitedBases;
2546	AddMethods(Base: BaseSubobject(MostDerivedClass, CharUnits::Zero()), BaseDepth: 0, LastVBase: nullptr,
2547	VisitedBases);
2548	// Note that it is possible for the vftable to contain only an RTTI
2549	// pointer, if all virtual functions are constewval.
2550	assert(!Components.empty() && "vftable can't be empty");
2551
2552	assert(MethodVFTableLocations.empty());
2553	for (const auto &I : MethodInfoMap) {
2554	const CXXMethodDecl *MD = I.first;
2555	const MethodInfo &MI = I.second;
2556	assert(MD == MD->getCanonicalDecl());
2557
2558	// Skip the methods that the MostDerivedClass didn't override
2559	// and the entries shadowed by return adjusting thunks.
2560	if (MD->getParent() != MostDerivedClass || MI.Shadowed)
2561	continue;
2562	MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),
2563	WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);
2564	if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(Val: MD)) {
2565	MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;
2566	} else {
2567	MethodVFTableLocations[MD] = Loc;
2568	}
2569	}
2570	}
2571
2572	public:
2573	VFTableBuilder(MicrosoftVTableContext &VTables,
2574	const CXXRecordDecl *MostDerivedClass, const VPtrInfo &Which)
2575	: VTables(VTables),
2576	Context(MostDerivedClass->getASTContext()),
2577	MostDerivedClass(MostDerivedClass),
2578	MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)),
2579	WhichVFPtr(Which),
2580	Overriders(MostDerivedClass, CharUnits(), MostDerivedClass) {
2581	// Provide the RTTI component if RTTIData is enabled. If the vftable would
2582	// be available externally, we should not provide the RTTI componenent. It
2583	// is currently impossible to get available externally vftables with either
2584	// dllimport or extern template instantiations, but eventually we may add a
2585	// flag to support additional devirtualization that needs this.
2586	if (Context.getLangOpts().RTTIData)
2587	HasRTTIComponent = true;
2588
2589	LayoutVFTable();
2590
2591	if (Context.getLangOpts().DumpVTableLayouts)
2592	dumpLayout(llvm::outs());
2593	}
2594
2595	uint64_t getNumThunks() const { return Thunks.size(); }
2596
2597	ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
2598
2599	ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
2600
2601	method_locations_range vtable_locations() const {
2602	return method_locations_range(MethodVFTableLocations.begin(),
2603	MethodVFTableLocations.end());
2604	}
2605
2606	ArrayRef<VTableComponent> vtable_components() const { return Components; }
2607
2608	VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
2609	return VTableThunks.begin();
2610	}
2611
2612	VTableThunksMapTy::const_iterator vtable_thunks_end() const {
2613	return VTableThunks.end();
2614	}
2615
2616	void dumpLayout(raw_ostream &);
2617	};
2618
2619	} // end namespace
2620
2621	// Let's study one class hierarchy as an example:
2622	// struct A {
2623	// virtual void f();
2624	// int x;
2625	// };
2626	//
2627	// struct B : virtual A {
2628	// virtual void f();
2629	// };
2630	//
2631	// Record layouts:
2632	// struct A:
2633	// 0 | (A vftable pointer)
2634	// 4 | int x
2635	//
2636	// struct B:
2637	// 0 | (B vbtable pointer)
2638	// 4 | struct A (virtual base)
2639	// 4 | (A vftable pointer)
2640	// 8 | int x
2641	//
2642	// Let's assume we have a pointer to the A part of an object of dynamic type B:
2643	// B b;
2644	// A *a = (A*)&b;
2645	// a->f();
2646	//
2647	// In this hierarchy, f() belongs to the vftable of A, so B::f() expects
2648	// "this" parameter to point at the A subobject, which is B+4.
2649	// In the B::f() prologue, it adjusts "this" back to B by subtracting 4,
2650	// performed as a *static* adjustment.
2651	//
2652	// Interesting thing happens when we alter the relative placement of A and B
2653	// subobjects in a class:
2654	// struct C : virtual B { };
2655	//
2656	// C c;
2657	// A *a = (A*)&c;
2658	// a->f();
2659	//
2660	// Respective record layout is:
2661	// 0 | (C vbtable pointer)
2662	// 4 | struct A (virtual base)
2663	// 4 | (A vftable pointer)
2664	// 8 | int x
2665	// 12 | struct B (virtual base)
2666	// 12 | (B vbtable pointer)
2667	//
2668	// The final overrider of f() in class C is still B::f(), so B+4 should be
2669	// passed as "this" to that code. However, "a" points at B-8, so the respective
2670	// vftable entry should hold a thunk that adds 12 to the "this" argument before
2671	// performing a tail call to B::f().
2672	//
2673	// With this example in mind, we can now calculate the 'this' argument offset
2674	// for the given method, relative to the beginning of the MostDerivedClass.
2675	CharUnits
2676	VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {
2677	BasesSetVectorTy Bases;
2678
2679	{
2680	// Find the set of least derived bases that define the given method.
2681	OverriddenMethodsSetTy VisitedOverriddenMethods;
2682	auto InitialOverriddenDefinitionCollector = [&](
2683	const CXXMethodDecl *OverriddenMD) {
2684	if (OverriddenMD->size_overridden_methods() == 0)
2685	Bases.insert(X: OverriddenMD->getParent());
2686	// Don't recurse on this method if we've already collected it.
2687	return VisitedOverriddenMethods.insert(Ptr: OverriddenMD).second;
2688	};
2689	visitAllOverriddenMethods(MD: Overrider.Method,
2690	Visitor&: InitialOverriddenDefinitionCollector);
2691	}
2692
2693	// If there are no overrides then 'this' is located
2694	// in the base that defines the method.
2695	if (Bases.size() == 0)
2696	return Overrider.Offset;
2697
2698	CXXBasePaths Paths;
2699	Overrider.Method->getParent()->lookupInBases(
2700	BaseMatches: [&Bases](const CXXBaseSpecifier *Specifier, CXXBasePath &) {
2701	return Bases.count(key: Specifier->getType()->getAsCXXRecordDecl());
2702	},
2703	Paths);
2704
2705	// This will hold the smallest this offset among overridees of MD.
2706	// This implies that an offset of a non-virtual base will dominate an offset
2707	// of a virtual base to potentially reduce the number of thunks required
2708	// in the derived classes that inherit this method.
2709	CharUnits Ret;
2710	bool First = true;
2711
2712	const ASTRecordLayout &OverriderRDLayout =
2713	Context.getASTRecordLayout(Overrider.Method->getParent());
2714	for (const CXXBasePath &Path : Paths) {
2715	CharUnits ThisOffset = Overrider.Offset;
2716	CharUnits LastVBaseOffset;
2717
2718	// For each path from the overrider to the parents of the overridden
2719	// methods, traverse the path, calculating the this offset in the most
2720	// derived class.
2721	for (const CXXBasePathElement &Element : Path) {
2722	QualType CurTy = Element.Base->getType();
2723	const CXXRecordDecl *PrevRD = Element.Class,
2724	*CurRD = CurTy->getAsCXXRecordDecl();
2725	const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);
2726
2727	if (Element.Base->isVirtual()) {
2728	// The interesting things begin when you have virtual inheritance.
2729	// The final overrider will use a static adjustment equal to the offset
2730	// of the vbase in the final overrider class.
2731	// For example, if the final overrider is in a vbase B of the most
2732	// derived class and it overrides a method of the B's own vbase A,
2733	// it uses A* as "this". In its prologue, it can cast A* to B* with
2734	// a static offset. This offset is used regardless of the actual
2735	// offset of A from B in the most derived class, requiring an
2736	// this-adjusting thunk in the vftable if A and B are laid out
2737	// differently in the most derived class.
2738	LastVBaseOffset = ThisOffset =
2739	Overrider.Offset + OverriderRDLayout.getVBaseClassOffset(VBase: CurRD);
2740	} else {
2741	ThisOffset += Layout.getBaseClassOffset(Base: CurRD);
2742	}
2743	}
2744
2745	if (isa<CXXDestructorDecl>(Val: Overrider.Method)) {
2746	if (LastVBaseOffset.isZero()) {
2747	// If a "Base" class has at least one non-virtual base with a virtual
2748	// destructor, the "Base" virtual destructor will take the address
2749	// of the "Base" subobject as the "this" argument.
2750	ThisOffset = Overrider.Offset;
2751	} else {
2752	// A virtual destructor of a virtual base takes the address of the
2753	// virtual base subobject as the "this" argument.
2754	ThisOffset = LastVBaseOffset;
2755	}
2756	}
2757
2758	if (Ret > ThisOffset || First) {
2759	First = false;
2760	Ret = ThisOffset;
2761	}
2762	}
2763
2764	assert(!First && "Method not found in the given subobject?");
2765	return Ret;
2766	}
2767
2768	// Things are getting even more complex when the "this" adjustment has to
2769	// use a dynamic offset instead of a static one, or even two dynamic offsets.
2770	// This is sometimes required when a virtual call happens in the middle of
2771	// a non-most-derived class construction or destruction.
2772	//
2773	// Let's take a look at the following example:
2774	// struct A {
2775	// virtual void f();
2776	// };
2777	//
2778	// void foo(A *a) { a->f(); } // Knows nothing about siblings of A.
2779	//
2780	// struct B : virtual A {
2781	// virtual void f();
2782	// B() {
2783	// foo(this);
2784	// }
2785	// };
2786	//
2787	// struct C : virtual B {
2788	// virtual void f();
2789	// };
2790	//
2791	// Record layouts for these classes are:
2792	// struct A
2793	// 0 | (A vftable pointer)
2794	//
2795	// struct B
2796	// 0 | (B vbtable pointer)
2797	// 4 | (vtordisp for vbase A)
2798	// 8 | struct A (virtual base)
2799	// 8 | (A vftable pointer)
2800	//
2801	// struct C
2802	// 0 | (C vbtable pointer)
2803	// 4 | (vtordisp for vbase A)
2804	// 8 | struct A (virtual base) // A precedes B!
2805	// 8 | (A vftable pointer)
2806	// 12 | struct B (virtual base)
2807	// 12 | (B vbtable pointer)
2808	//
2809	// When one creates an object of type C, the C constructor:
2810	// - initializes all the vbptrs, then
2811	// - calls the A subobject constructor
2812	// (initializes A's vfptr with an address of A vftable), then
2813	// - calls the B subobject constructor
2814	// (initializes A's vfptr with an address of B vftable and vtordisp for A),
2815	// that in turn calls foo(), then
2816	// - initializes A's vfptr with an address of C vftable and zeroes out the
2817	// vtordisp
2818	// FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable
2819	// without vtordisp thunks?
2820	// FIXME: how are vtordisp handled in the presence of nooverride/final?
2821	//
2822	// When foo() is called, an object with a layout of class C has a vftable
2823	// referencing B::f() that assumes a B layout, so the "this" adjustments are
2824	// incorrect, unless an extra adjustment is done. This adjustment is called
2825	// "vtordisp adjustment". Vtordisp basically holds the difference between the
2826	// actual location of a vbase in the layout class and the location assumed by
2827	// the vftable of the class being constructed/destructed. Vtordisp is only
2828	// needed if "this" escapes a
2829	// structor (or we can't prove otherwise).
2830	// [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an
2831	// estimation of a dynamic adjustment]
2832	//
2833	// foo() gets a pointer to the A vbase and doesn't know anything about B or C,
2834	// so it just passes that pointer as "this" in a virtual call.
2835	// If there was no vtordisp, that would just dispatch to B::f().
2836	// However, B::f() assumes B+8 is passed as "this",
2837	// yet the pointer foo() passes along is B-4 (i.e. C+8).
2838	// An extra adjustment is needed, so we emit a thunk into the B vftable.
2839	// This vtordisp thunk subtracts the value of vtordisp
2840	// from the "this" argument (-12) before making a tailcall to B::f().
2841	//
2842	// Let's consider an even more complex example:
2843	// struct D : virtual B, virtual C {
2844	// D() {
2845	// foo(this);
2846	// }
2847	// };
2848	//
2849	// struct D
2850	// 0 | (D vbtable pointer)
2851	// 4 | (vtordisp for vbase A)
2852	// 8 | struct A (virtual base) // A precedes both B and C!
2853	// 8 | (A vftable pointer)
2854	// 12 | struct B (virtual base) // B precedes C!
2855	// 12 | (B vbtable pointer)
2856	// 16 | struct C (virtual base)
2857	// 16 | (C vbtable pointer)
2858	//
2859	// When D::D() calls foo(), we find ourselves in a thunk that should tailcall
2860	// to C::f(), which assumes C+8 as its "this" parameter. This time, foo()
2861	// passes along A, which is C-8. The A vtordisp holds
2862	// "D.vbptr[index_of_A] - offset_of_A_in_D"
2863	// and we statically know offset_of_A_in_D, so can get a pointer to D.
2864	// When we know it, we can make an extra vbtable lookup to locate the C vbase
2865	// and one extra static adjustment to calculate the expected value of C+8.
2866	void VFTableBuilder::CalculateVtordispAdjustment(
2867	FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,
2868	ThisAdjustment &TA) {
2869	const ASTRecordLayout::VBaseOffsetsMapTy &VBaseMap =
2870	MostDerivedClassLayout.getVBaseOffsetsMap();
2871	const ASTRecordLayout::VBaseOffsetsMapTy::const_iterator &VBaseMapEntry =
2872	VBaseMap.find(Val: WhichVFPtr.getVBaseWithVPtr());
2873	assert(VBaseMapEntry != VBaseMap.end());
2874
2875	// If there's no vtordisp or the final overrider is defined in the same vbase
2876	// as the initial declaration, we don't need any vtordisp adjustment.
2877	if (!VBaseMapEntry->second.hasVtorDisp() ||
2878	Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())
2879	return;
2880
2881	// OK, now we know we need to use a vtordisp thunk.
2882	// The implicit vtordisp field is located right before the vbase.
2883	CharUnits OffsetOfVBaseWithVFPtr = VBaseMapEntry->second.VBaseOffset;
2884	TA.Virtual.Microsoft.VtordispOffset =
2885	(OffsetOfVBaseWithVFPtr - WhichVFPtr.FullOffsetInMDC).getQuantity() - 4;
2886
2887	// A simple vtordisp thunk will suffice if the final overrider is defined
2888	// in either the most derived class or its non-virtual base.
2889	if (Overrider.Method->getParent() == MostDerivedClass ||
2890	!Overrider.VirtualBase)
2891	return;
2892
2893	// Otherwise, we need to do use the dynamic offset of the final overrider
2894	// in order to get "this" adjustment right.
2895	TA.Virtual.Microsoft.VBPtrOffset =
2896	(OffsetOfVBaseWithVFPtr + WhichVFPtr.NonVirtualOffset -
2897	MostDerivedClassLayout.getVBPtrOffset()).getQuantity();
2898	TA.Virtual.Microsoft.VBOffsetOffset =
2899	Context.getTypeSizeInChars(Context.IntTy).getQuantity() *
2900	VTables.getVBTableIndex(Derived: MostDerivedClass, VBase: Overrider.VirtualBase);
2901
2902	TA.NonVirtual = (ThisOffset - Overrider.Offset).getQuantity();
2903	}
2904
2905	static void GroupNewVirtualOverloads(
2906	const CXXRecordDecl *RD,
2907	SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) {
2908	// Put the virtual methods into VirtualMethods in the proper order:
2909	// 1) Group overloads by declaration name. New groups are added to the
2910	// vftable in the order of their first declarations in this class
2911	// (including overrides, non-virtual methods and any other named decl that
2912	// might be nested within the class).
2913	// 2) In each group, new overloads appear in the reverse order of declaration.
2914	typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;
2915	SmallVector<MethodGroup, 10> Groups;
2916	typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;
2917	VisitedGroupIndicesTy VisitedGroupIndices;
2918	for (const auto *D : RD->decls()) {
2919	const auto *ND = dyn_cast<NamedDecl>(D);
2920	if (!ND)
2921	continue;
2922	VisitedGroupIndicesTy::iterator J;
2923	bool Inserted;
2924	std::tie(J, Inserted) = VisitedGroupIndices.insert(
2925	std::make_pair(ND->getDeclName(), Groups.size()));
2926	if (Inserted)
2927	Groups.push_back(MethodGroup());
2928	if (const auto *MD = dyn_cast<CXXMethodDecl>(ND))
2929	if (MicrosoftVTableContext::hasVtableSlot(MD))
2930	Groups[J->second].push_back(MD->getCanonicalDecl());
2931	}
2932
2933	for (const MethodGroup &Group : Groups)
2934	VirtualMethods.append(in_start: Group.rbegin(), in_end: Group.rend());
2935	}
2936
2937	static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {
2938	for (const auto &B : RD->bases()) {
2939	if (B.isVirtual() && B.getType()->getAsCXXRecordDecl() == Base)
2940	return true;
2941	}
2942	return false;
2943	}
2944
2945	void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
2946	const CXXRecordDecl *LastVBase,
2947	BasesSetVectorTy &VisitedBases) {
2948	const CXXRecordDecl *RD = Base.getBase();
2949	if (!RD->isPolymorphic())
2950	return;
2951
2952	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
2953
2954	// See if this class expands a vftable of the base we look at, which is either
2955	// the one defined by the vfptr base path or the primary base of the current
2956	// class.
2957	const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;
2958	CharUnits NextBaseOffset;
2959	if (BaseDepth < WhichVFPtr.PathToIntroducingObject.size()) {
2960	NextBase = WhichVFPtr.PathToIntroducingObject[BaseDepth];
2961	if (isDirectVBase(Base: NextBase, RD)) {
2962	NextLastVBase = NextBase;
2963	NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(VBase: NextBase);
2964	} else {
2965	NextBaseOffset =
2966	Base.getBaseOffset() + Layout.getBaseClassOffset(Base: NextBase);
2967	}
2968	} else if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
2969	assert(!Layout.isPrimaryBaseVirtual() &&
2970	"No primary virtual bases in this ABI");
2971	NextBase = PrimaryBase;
2972	NextBaseOffset = Base.getBaseOffset();
2973	}
2974
2975	if (NextBase) {
2976	AddMethods(Base: BaseSubobject(NextBase, NextBaseOffset), BaseDepth: BaseDepth + 1,
2977	LastVBase: NextLastVBase, VisitedBases);
2978	if (!VisitedBases.insert(X: NextBase))
2979	llvm_unreachable("Found a duplicate primary base!");
2980	}
2981
2982	SmallVector<const CXXMethodDecl*, 10> VirtualMethods;
2983	// Put virtual methods in the proper order.
2984	GroupNewVirtualOverloads(RD, VirtualMethods);
2985
2986	// Now go through all virtual member functions and add them to the current
2987	// vftable. This is done by
2988	// - replacing overridden methods in their existing slots, as long as they
2989	// don't require return adjustment; calculating This adjustment if needed.
2990	// - adding new slots for methods of the current base not present in any
2991	// sub-bases;
2992	// - adding new slots for methods that require Return adjustment.
2993	// We keep track of the methods visited in the sub-bases in MethodInfoMap.
2994	for (const CXXMethodDecl *MD : VirtualMethods) {
2995	FinalOverriders::OverriderInfo FinalOverrider =
2996	Overriders.getOverrider(MD, BaseOffset: Base.getBaseOffset());
2997	const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method;
2998	const CXXMethodDecl *OverriddenMD =
2999	FindNearestOverriddenMethod(MD, Bases&: VisitedBases);
3000
3001	ThisAdjustment ThisAdjustmentOffset;
3002	bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false;
3003	CharUnits ThisOffset = ComputeThisOffset(Overrider: FinalOverrider);
3004	ThisAdjustmentOffset.NonVirtual =
3005	(ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();
3006	if ((OverriddenMD || FinalOverriderMD != MD) &&
3007	WhichVFPtr.getVBaseWithVPtr())
3008	CalculateVtordispAdjustment(Overrider: FinalOverrider, ThisOffset,
3009	TA&: ThisAdjustmentOffset);
3010
3011	unsigned VBIndex =
3012	LastVBase ? VTables.getVBTableIndex(Derived: MostDerivedClass, VBase: LastVBase) : 0;
3013
3014	if (OverriddenMD) {
3015	// If MD overrides anything in this vftable, we need to update the
3016	// entries.
3017	MethodInfoMapTy::iterator OverriddenMDIterator =
3018	MethodInfoMap.find(Val: OverriddenMD);
3019
3020	// If the overridden method went to a different vftable, skip it.
3021	if (OverriddenMDIterator == MethodInfoMap.end())
3022	continue;
3023
3024	MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;
3025
3026	VBIndex = OverriddenMethodInfo.VBTableIndex;
3027
3028	// Let's check if the overrider requires any return adjustments.
3029	// We must create a new slot if the MD's return type is not trivially
3030	// convertible to the OverriddenMD's one.
3031	// Once a chain of method overrides adds a return adjusting vftable slot,
3032	// all subsequent overrides will also use an extra method slot.
3033	ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset(
3034	Context, DerivedMD: MD, BaseMD: OverriddenMD).isEmpty() ||
3035	OverriddenMethodInfo.UsesExtraSlot;
3036
3037	if (!ReturnAdjustingThunk) {
3038	// No return adjustment needed - just replace the overridden method info
3039	// with the current info.
3040	MethodInfo MI(VBIndex, OverriddenMethodInfo.VFTableIndex);
3041	MethodInfoMap.erase(I: OverriddenMDIterator);
3042
3043	assert(!MethodInfoMap.count(MD) &&
3044	"Should not have method info for this method yet!");
3045	MethodInfoMap.insert(KV: std::make_pair(x&: MD, y&: MI));
3046	continue;
3047	}
3048
3049	// In case we need a return adjustment, we'll add a new slot for
3050	// the overrider. Mark the overridden method as shadowed by the new slot.
3051	OverriddenMethodInfo.Shadowed = true;
3052
3053	// Force a special name mangling for a return-adjusting thunk
3054	// unless the method is the final overrider without this adjustment.
3055	ForceReturnAdjustmentMangling =
3056	!(MD == FinalOverriderMD && ThisAdjustmentOffset.isEmpty());
3057	} else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||
3058	MD->size_overridden_methods()) {
3059	// Skip methods that don't belong to the vftable of the current class,
3060	// e.g. each method that wasn't seen in any of the visited sub-bases
3061	// but overrides multiple methods of other sub-bases.
3062	continue;
3063	}
3064
3065	// If we got here, MD is a method not seen in any of the sub-bases or
3066	// it requires return adjustment. Insert the method info for this method.
3067	MethodInfo MI(VBIndex,
3068	HasRTTIComponent ? Components.size() - 1 : Components.size(),
3069	ReturnAdjustingThunk);
3070
3071	assert(!MethodInfoMap.count(MD) &&
3072	"Should not have method info for this method yet!");
3073	MethodInfoMap.insert(KV: std::make_pair(x&: MD, y&: MI));
3074
3075	// Check if this overrider needs a return adjustment.
3076	// We don't want to do this for pure virtual member functions.
3077	BaseOffset ReturnAdjustmentOffset;
3078	ReturnAdjustment ReturnAdjustment;
3079	if (!FinalOverriderMD->isPureVirtual()) {
3080	ReturnAdjustmentOffset =
3081	ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: FinalOverriderMD, BaseMD: MD);
3082	}
3083	if (!ReturnAdjustmentOffset.isEmpty()) {
3084	ForceReturnAdjustmentMangling = true;
3085	ReturnAdjustment.NonVirtual =
3086	ReturnAdjustmentOffset.NonVirtualOffset.getQuantity();
3087	if (ReturnAdjustmentOffset.VirtualBase) {
3088	const ASTRecordLayout &DerivedLayout =
3089	Context.getASTRecordLayout(ReturnAdjustmentOffset.DerivedClass);
3090	ReturnAdjustment.Virtual.Microsoft.VBPtrOffset =
3091	DerivedLayout.getVBPtrOffset().getQuantity();
3092	ReturnAdjustment.Virtual.Microsoft.VBIndex =
3093	VTables.getVBTableIndex(Derived: ReturnAdjustmentOffset.DerivedClass,
3094	VBase: ReturnAdjustmentOffset.VirtualBase);
3095	}
3096	}
3097
3098	AddMethod(MD: FinalOverriderMD,
3099	TI: ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment,
3100	ForceReturnAdjustmentMangling ? MD : nullptr));
3101	}
3102	}
3103
3104	static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {
3105	for (const CXXRecordDecl *Elem : llvm::reverse(C: Path)) {
3106	Out << "'";
3107	Elem->printQualifiedName(Out);
3108	Out << "' in ";
3109	}
3110	}
3111
3112	static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
3113	bool ContinueFirstLine) {
3114	const ReturnAdjustment &R = TI.Return;
3115	bool Multiline = false;
3116	const char *LinePrefix = "\n ";
3117	if (!R.isEmpty() || TI.Method) {
3118	if (!ContinueFirstLine)
3119	Out << LinePrefix;
3120	Out << "[return adjustment (to type '"
3121	<< TI.Method->getReturnType().getCanonicalType() << "'): ";
3122	if (R.Virtual.Microsoft.VBPtrOffset)
3123	Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";
3124	if (R.Virtual.Microsoft.VBIndex)
3125	Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";
3126	Out << R.NonVirtual << " non-virtual]";
3127	Multiline = true;
3128	}
3129
3130	const ThisAdjustment &T = TI.This;
3131	if (!T.isEmpty()) {
3132	if (Multiline || !ContinueFirstLine)
3133	Out << LinePrefix;
3134	Out << "[this adjustment: ";
3135	if (!TI.This.Virtual.isEmpty()) {
3136	assert(T.Virtual.Microsoft.VtordispOffset < 0);
3137	Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";
3138	if (T.Virtual.Microsoft.VBPtrOffset) {
3139	Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset
3140	<< " to the left,";
3141	assert(T.Virtual.Microsoft.VBOffsetOffset > 0);
3142	Out << LinePrefix << " vboffset at "
3143	<< T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";
3144	}
3145	}
3146	Out << T.NonVirtual << " non-virtual]";
3147	}
3148	}
3149
3150	void VFTableBuilder::dumpLayout(raw_ostream &Out) {
3151	Out << "VFTable for ";
3152	PrintBasePath(Path: WhichVFPtr.PathToIntroducingObject, Out);
3153	Out << "'";
3154	MostDerivedClass->printQualifiedName(Out);
3155	Out << "' (" << Components.size()
3156	<< (Components.size() == 1 ? " entry" : " entries") << ").\n";
3157
3158	for (unsigned I = 0, E = Components.size(); I != E; ++I) {
3159	Out << llvm::format(Fmt: "%4d | ", Vals: I);
3160
3161	const VTableComponent &Component = Components[I];
3162
3163	// Dump the component.
3164	switch (Component.getKind()) {
3165	case VTableComponent::CK_RTTI:
3166	Component.getRTTIDecl()->printQualifiedName(Out);
3167	Out << " RTTI";
3168	break;
3169
3170	case VTableComponent::CK_FunctionPointer: {
3171	const CXXMethodDecl *MD = Component.getFunctionDecl();
3172
3173	// FIXME: Figure out how to print the real thunk type, since they can
3174	// differ in the return type.
3175	std::string Str = PredefinedExpr::ComputeName(
3176	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
3177	Out << Str;
3178	if (MD->isPureVirtual())
3179	Out << " [pure]";
3180
3181	if (MD->isDeleted())
3182	Out << " [deleted]";
3183
3184	ThunkInfo Thunk = VTableThunks.lookup(Val: I);
3185	if (!Thunk.isEmpty())
3186	dumpMicrosoftThunkAdjustment(TI: Thunk, Out, /*ContinueFirstLine=*/false);
3187
3188	break;
3189	}
3190
3191	case VTableComponent::CK_DeletingDtorPointer: {
3192	const CXXDestructorDecl *DD = Component.getDestructorDecl();
3193
3194	DD->printQualifiedName(Out);
3195	Out << "() [scalar deleting]";
3196
3197	if (DD->isPureVirtual())
3198	Out << " [pure]";
3199
3200	ThunkInfo Thunk = VTableThunks.lookup(Val: I);
3201	if (!Thunk.isEmpty()) {
3202	assert(Thunk.Return.isEmpty() &&
3203	"No return adjustment needed for destructors!");
3204	dumpMicrosoftThunkAdjustment(TI: Thunk, Out, /*ContinueFirstLine=*/false);
3205	}
3206
3207	break;
3208	}
3209
3210	default:
3211	DiagnosticsEngine &Diags = Context.getDiagnostics();
3212	unsigned DiagID = Diags.getCustomDiagID(
3213	L: DiagnosticsEngine::Error,
3214	FormatString: "Unexpected vftable component type %0 for component number %1");
3215	Diags.Report(MostDerivedClass->getLocation(), DiagID)
3216	<< I << Component.getKind();
3217	}
3218
3219	Out << '\n';
3220	}
3221
3222	Out << '\n';
3223
3224	if (!Thunks.empty()) {
3225	// We store the method names in a map to get a stable order.
3226	std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
3227
3228	for (const auto &I : Thunks) {
3229	const CXXMethodDecl *MD = I.first;
3230	std::string MethodName = PredefinedExpr::ComputeName(
3231	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
3232
3233	MethodNamesAndDecls.insert(x: std::make_pair(x&: MethodName, y&: MD));
3234	}
3235
3236	for (const auto &MethodNameAndDecl : MethodNamesAndDecls) {
3237	const std::string &MethodName = MethodNameAndDecl.first;
3238	const CXXMethodDecl *MD = MethodNameAndDecl.second;
3239
3240	ThunkInfoVectorTy ThunksVector = Thunks[MD];
3241	llvm::stable_sort(Range&: ThunksVector, C: [](const ThunkInfo &LHS,
3242	const ThunkInfo &RHS) {
3243	// Keep different thunks with the same adjustments in the order they
3244	// were put into the vector.
3245	return std::tie(args: LHS.This, args: LHS.Return) < std::tie(args: RHS.This, args: RHS.Return);
3246	});
3247
3248	Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
3249	Out << (ThunksVector.size() == 1 ? " entry" : " entries") << ").\n";
3250
3251	for (unsigned I = 0, E = ThunksVector.size(); I != E; ++I) {
3252	const ThunkInfo &Thunk = ThunksVector[I];
3253
3254	Out << llvm::format(Fmt: "%4d | ", Vals: I);
3255	dumpMicrosoftThunkAdjustment(TI: Thunk, Out, /*ContinueFirstLine=*/true);
3256	Out << '\n';
3257	}
3258
3259	Out << '\n';
3260	}
3261	}
3262
3263	Out.flush();
3264	}
3265
3266	static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
3267	ArrayRef<const CXXRecordDecl *> B) {
3268	for (const CXXRecordDecl *Decl : B) {
3269	if (A.count(Ptr: Decl))
3270	return true;
3271	}
3272	return false;
3273	}
3274
3275	static bool rebucketPaths(VPtrInfoVector &Paths);
3276
3277	/// Produces MSVC-compatible vbtable data. The symbols produced by this
3278	/// algorithm match those produced by MSVC 2012 and newer, which is different
3279	/// from MSVC 2010.
3280	///
3281	/// MSVC 2012 appears to minimize the vbtable names using the following
3282	/// algorithm. First, walk the class hierarchy in the usual order, depth first,
3283	/// left to right, to find all of the subobjects which contain a vbptr field.
3284	/// Visiting each class node yields a list of inheritance paths to vbptrs. Each
3285	/// record with a vbptr creates an initially empty path.
3286	///
3287	/// To combine paths from child nodes, the paths are compared to check for
3288	/// ambiguity. Paths are "ambiguous" if multiple paths have the same set of
3289	/// components in the same order. Each group of ambiguous paths is extended by
3290	/// appending the class of the base from which it came. If the current class
3291	/// node produced an ambiguous path, its path is extended with the current class.
3292	/// After extending paths, MSVC again checks for ambiguity, and extends any
3293	/// ambiguous path which wasn't already extended. Because each node yields an
3294	/// unambiguous set of paths, MSVC doesn't need to extend any path more than once
3295	/// to produce an unambiguous set of paths.
3296	///
3297	/// TODO: Presumably vftables use the same algorithm.
3298	void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
3299	const CXXRecordDecl *RD,
3300	VPtrInfoVector &Paths) {
3301	assert(Paths.empty());
3302	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3303
3304	// Base case: this subobject has its own vptr.
3305	if (ForVBTables ? Layout.hasOwnVBPtr() : Layout.hasOwnVFPtr())
3306	Paths.push_back(Elt: std::make_unique<VPtrInfo>(args&: RD));
3307
3308	// Recursive case: get all the vbtables from our bases and remove anything
3309	// that shares a virtual base.
3310	llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
3311	for (const auto &B : RD->bases()) {
3312	const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
3313	if (B.isVirtual() && VBasesSeen.count(Ptr: Base))
3314	continue;
3315
3316	if (!Base->isDynamicClass())
3317	continue;
3318
3319	const VPtrInfoVector &BasePaths =
3320	ForVBTables ? enumerateVBTables(RD: Base) : getVFPtrOffsets(RD: Base);
3321
3322	for (const std::unique_ptr<VPtrInfo> &BaseInfo : BasePaths) {
3323	// Don't include the path if it goes through a virtual base that we've
3324	// already included.
3325	if (setsIntersect(A: VBasesSeen, B: BaseInfo->ContainingVBases))
3326	continue;
3327
3328	// Copy the path and adjust it as necessary.
3329	auto P = std::make_unique<VPtrInfo>(args&: *BaseInfo);
3330
3331	// We mangle Base into the path if the path would've been ambiguous and it
3332	// wasn't already extended with Base.
3333	if (P->MangledPath.empty() || P->MangledPath.back() != Base)
3334	P->NextBaseToMangle = Base;
3335
3336	// Keep track of which vtable the derived class is going to extend with
3337	// new methods or bases. We append to either the vftable of our primary
3338	// base, or the first non-virtual base that has a vbtable.
3339	if (P->ObjectWithVPtr == Base &&
3340	Base == (ForVBTables ? Layout.getBaseSharingVBPtr()
3341	: Layout.getPrimaryBase()))
3342	P->ObjectWithVPtr = RD;
3343
3344	// Keep track of the full adjustment from the MDC to this vtable. The
3345	// adjustment is captured by an optional vbase and a non-virtual offset.
3346	if (B.isVirtual())
3347	P->ContainingVBases.push_back(Elt: Base);
3348	else if (P->ContainingVBases.empty())
3349	P->NonVirtualOffset += Layout.getBaseClassOffset(Base);
3350
3351	// Update the full offset in the MDC.
3352	P->FullOffsetInMDC = P->NonVirtualOffset;
3353	if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())
3354	P->FullOffsetInMDC += Layout.getVBaseClassOffset(VBase: VB);
3355
3356	Paths.push_back(Elt: std::move(P));
3357	}
3358
3359	if (B.isVirtual())
3360	VBasesSeen.insert(Ptr: Base);
3361
3362	// After visiting any direct base, we've transitively visited all of its
3363	// morally virtual bases.
3364	for (const auto &VB : Base->vbases())
3365	VBasesSeen.insert(Ptr: VB.getType()->getAsCXXRecordDecl());
3366	}
3367
3368	// Sort the paths into buckets, and if any of them are ambiguous, extend all
3369	// paths in ambiguous buckets.
3370	bool Changed = true;
3371	while (Changed)
3372	Changed = rebucketPaths(Paths);
3373	}
3374
3375	static bool extendPath(VPtrInfo &P) {
3376	if (P.NextBaseToMangle) {
3377	P.MangledPath.push_back(Elt: P.NextBaseToMangle);
3378	P.NextBaseToMangle = nullptr;// Prevent the path from being extended twice.
3379	return true;
3380	}
3381	return false;
3382	}
3383
3384	static bool rebucketPaths(VPtrInfoVector &Paths) {
3385	// What we're essentially doing here is bucketing together ambiguous paths.
3386	// Any bucket with more than one path in it gets extended by NextBase, which
3387	// is usually the direct base of the inherited the vbptr. This code uses a
3388	// sorted vector to implement a multiset to form the buckets. Note that the
3389	// ordering is based on pointers, but it doesn't change our output order. The
3390	// current algorithm is designed to match MSVC 2012's names.
3391	llvm::SmallVector<std::reference_wrapper<VPtrInfo>, 2> PathsSorted(
3392	llvm::make_pointee_range(Range&: Paths));
3393	llvm::sort(C&: PathsSorted, Comp: [](const VPtrInfo &LHS, const VPtrInfo &RHS) {
3394	return LHS.MangledPath < RHS.MangledPath;
3395	});
3396	bool Changed = false;
3397	for (size_t I = 0, E = PathsSorted.size(); I != E;) {
3398	// Scan forward to find the end of the bucket.
3399	size_t BucketStart = I;
3400	do {
3401	++I;
3402	} while (I != E &&
3403	PathsSorted[BucketStart].get().MangledPath ==
3404	PathsSorted[I].get().MangledPath);
3405
3406	// If this bucket has multiple paths, extend them all.
3407	if (I - BucketStart > 1) {
3408	for (size_t II = BucketStart; II != I; ++II)
3409	Changed |= extendPath(P&: PathsSorted[II]);
3410	assert(Changed && "no paths were extended to fix ambiguity");
3411	}
3412	}
3413	return Changed;
3414	}
3415
3416	MicrosoftVTableContext::~MicrosoftVTableContext() {}
3417
3418	namespace {
3419	typedef llvm::SetVector<BaseSubobject, std::vector<BaseSubobject>,
3420	llvm::DenseSet<BaseSubobject>> FullPathTy;
3421	}
3422
3423	// This recursive function finds all paths from a subobject centered at
3424	// (RD, Offset) to the subobject located at IntroducingObject.
3425	static void findPathsToSubobject(ASTContext &Context,
3426	const ASTRecordLayout &MostDerivedLayout,
3427	const CXXRecordDecl *RD, CharUnits Offset,
3428	BaseSubobject IntroducingObject,
3429	FullPathTy &FullPath,
3430	std::list<FullPathTy> &Paths) {
3431	if (BaseSubobject(RD, Offset) == IntroducingObject) {
3432	Paths.push_back(x: FullPath);
3433	return;
3434	}
3435
3436	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3437
3438	for (const CXXBaseSpecifier &BS : RD->bases()) {
3439	const CXXRecordDecl *Base = BS.getType()->getAsCXXRecordDecl();
3440	CharUnits NewOffset = BS.isVirtual()
3441	? MostDerivedLayout.getVBaseClassOffset(VBase: Base)
3442	: Offset + Layout.getBaseClassOffset(Base);
3443	FullPath.insert(X: BaseSubobject(Base, NewOffset));
3444	findPathsToSubobject(Context, MostDerivedLayout, RD: Base, Offset: NewOffset,
3445	IntroducingObject, FullPath, Paths);
3446	FullPath.pop_back();
3447	}
3448	}
3449
3450	// Return the paths which are not subsets of other paths.
3451	static void removeRedundantPaths(std::list<FullPathTy> &FullPaths) {
3452	FullPaths.remove_if(pred: [&](const FullPathTy &SpecificPath) {
3453	for (const FullPathTy &OtherPath : FullPaths) {
3454	if (&SpecificPath == &OtherPath)
3455	continue;
3456	if (llvm::all_of(Range: SpecificPath, P: [&](const BaseSubobject &BSO) {
3457	return OtherPath.contains(key: BSO);
3458	})) {
3459	return true;
3460	}
3461	}
3462	return false;
3463	});
3464	}
3465
3466	static CharUnits getOffsetOfFullPath(ASTContext &Context,
3467	const CXXRecordDecl *RD,
3468	const FullPathTy &FullPath) {
3469	const ASTRecordLayout &MostDerivedLayout =
3470	Context.getASTRecordLayout(RD);
3471	CharUnits Offset = CharUnits::fromQuantity(Quantity: -1);
3472	for (const BaseSubobject &BSO : FullPath) {
3473	const CXXRecordDecl *Base = BSO.getBase();
3474	// The first entry in the path is always the most derived record, skip it.
3475	if (Base == RD) {
3476	assert(Offset.getQuantity() == -1);
3477	Offset = CharUnits::Zero();
3478	continue;
3479	}
3480	assert(Offset.getQuantity() != -1);
3481	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3482	// While we know which base has to be traversed, we don't know if that base
3483	// was a virtual base.
3484	const CXXBaseSpecifier *BaseBS = std::find_if(
3485	first: RD->bases_begin(), last: RD->bases_end(), pred: [&](const CXXBaseSpecifier &BS) {
3486	return BS.getType()->getAsCXXRecordDecl() == Base;
3487	});
3488	Offset = BaseBS->isVirtual() ? MostDerivedLayout.getVBaseClassOffset(VBase: Base)
3489	: Offset + Layout.getBaseClassOffset(Base);
3490	RD = Base;
3491	}
3492	return Offset;
3493	}
3494
3495	// We want to select the path which introduces the most covariant overrides. If
3496	// two paths introduce overrides which the other path doesn't contain, issue a
3497	// diagnostic.
3498	static const FullPathTy *selectBestPath(ASTContext &Context,
3499	const CXXRecordDecl *RD,
3500	const VPtrInfo &Info,
3501	std::list<FullPathTy> &FullPaths) {
3502	// Handle some easy cases first.
3503	if (FullPaths.empty())
3504	return nullptr;
3505	if (FullPaths.size() == 1)
3506	return &FullPaths.front();
3507
3508	const FullPathTy *BestPath = nullptr;
3509	typedef std::set<const CXXMethodDecl *> OverriderSetTy;
3510	OverriderSetTy LastOverrides;
3511	for (const FullPathTy &SpecificPath : FullPaths) {
3512	assert(!SpecificPath.empty());
3513	OverriderSetTy CurrentOverrides;
3514	const CXXRecordDecl *TopLevelRD = SpecificPath.begin()->getBase();
3515	// Find the distance from the start of the path to the subobject with the
3516	// VPtr.
3517	CharUnits BaseOffset =
3518	getOffsetOfFullPath(Context, RD: TopLevelRD, FullPath: SpecificPath);
3519	FinalOverriders Overriders(TopLevelRD, CharUnits::Zero(), TopLevelRD);
3520	for (const CXXMethodDecl *MD : Info.IntroducingObject->methods()) {
3521	if (!MicrosoftVTableContext::hasVtableSlot(MD))
3522	continue;
3523	FinalOverriders::OverriderInfo OI =
3524	Overriders.getOverrider(MD: MD->getCanonicalDecl(), BaseOffset);
3525	const CXXMethodDecl *OverridingMethod = OI.Method;
3526	// Only overriders which have a return adjustment introduce problematic
3527	// thunks.
3528	if (ComputeReturnAdjustmentBaseOffset(Context, DerivedMD: OverridingMethod, BaseMD: MD)
3529	.isEmpty())
3530	continue;
3531	// It's possible that the overrider isn't in this path. If so, skip it
3532	// because this path didn't introduce it.
3533	const CXXRecordDecl *OverridingParent = OverridingMethod->getParent();
3534	if (llvm::none_of(Range: SpecificPath, P: [&](const BaseSubobject &BSO) {
3535	return BSO.getBase() == OverridingParent;
3536	}))
3537	continue;
3538	CurrentOverrides.insert(x: OverridingMethod);
3539	}
3540	OverriderSetTy NewOverrides =
3541	llvm::set_difference(S1: CurrentOverrides, S2: LastOverrides);
3542	if (NewOverrides.empty())
3543	continue;
3544	OverriderSetTy MissingOverrides =
3545	llvm::set_difference(S1: LastOverrides, S2: CurrentOverrides);
3546	if (MissingOverrides.empty()) {
3547	// This path is a strict improvement over the last path, let's use it.
3548	BestPath = &SpecificPath;
3549	std::swap(x&: CurrentOverrides, y&: LastOverrides);
3550	} else {
3551	// This path introduces an overrider with a conflicting covariant thunk.
3552	DiagnosticsEngine &Diags = Context.getDiagnostics();
3553	const CXXMethodDecl *CovariantMD = *NewOverrides.begin();
3554	const CXXMethodDecl *ConflictMD = *MissingOverrides.begin();
3555	Diags.Report(RD->getLocation(), diag::err_vftable_ambiguous_component)
3556	<< RD;
3557	Diags.Report(CovariantMD->getLocation(), diag::note_covariant_thunk)
3558	<< CovariantMD;
3559	Diags.Report(ConflictMD->getLocation(), diag::note_covariant_thunk)
3560	<< ConflictMD;
3561	}
3562	}
3563	// Go with the path that introduced the most covariant overrides. If there is
3564	// no such path, pick the first path.
3565	return BestPath ? BestPath : &FullPaths.front();
3566	}
3567
3568	static void computeFullPathsForVFTables(ASTContext &Context,
3569	const CXXRecordDecl *RD,
3570	VPtrInfoVector &Paths) {
3571	const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD);
3572	FullPathTy FullPath;
3573	std::list<FullPathTy> FullPaths;
3574	for (const std::unique_ptr<VPtrInfo>& Info : Paths) {
3575	findPathsToSubobject(
3576	Context, MostDerivedLayout, RD, Offset: CharUnits::Zero(),
3577	IntroducingObject: BaseSubobject(Info->IntroducingObject, Info->FullOffsetInMDC), FullPath,
3578	Paths&: FullPaths);
3579	FullPath.clear();
3580	removeRedundantPaths(FullPaths);
3581	Info->PathToIntroducingObject.clear();
3582	if (const FullPathTy *BestPath =
3583	selectBestPath(Context, RD, Info: *Info, FullPaths))
3584	for (const BaseSubobject &BSO : *BestPath)
3585	Info->PathToIntroducingObject.push_back(Elt: BSO.getBase());
3586	FullPaths.clear();
3587	}
3588	}
3589
3590	static bool vfptrIsEarlierInMDC(const ASTRecordLayout &Layout,
3591	const MethodVFTableLocation &LHS,
3592	const MethodVFTableLocation &RHS) {
3593	CharUnits L = LHS.VFPtrOffset;
3594	CharUnits R = RHS.VFPtrOffset;
3595	if (LHS.VBase)
3596	L += Layout.getVBaseClassOffset(VBase: LHS.VBase);
3597	if (RHS.VBase)
3598	R += Layout.getVBaseClassOffset(VBase: RHS.VBase);
3599	return L < R;
3600	}
3601
3602	void MicrosoftVTableContext::computeVTableRelatedInformation(
3603	const CXXRecordDecl *RD) {
3604	assert(RD->isDynamicClass());
3605
3606	// Check if we've computed this information before.
3607	if (VFPtrLocations.count(Val: RD))
3608	return;
3609
3610	const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;
3611
3612	{
3613	auto VFPtrs = std::make_unique<VPtrInfoVector>();
3614	computeVTablePaths(/*ForVBTables=*/false, RD, Paths&: *VFPtrs);
3615	computeFullPathsForVFTables(Context, RD, Paths&: *VFPtrs);
3616	VFPtrLocations[RD] = std::move(VFPtrs);
3617	}
3618
3619	MethodVFTableLocationsTy NewMethodLocations;
3620	for (const std::unique_ptr<VPtrInfo> &VFPtr : *VFPtrLocations[RD]) {
3621	VFTableBuilder Builder(*this, RD, *VFPtr);
3622
3623	VFTableIdTy id(RD, VFPtr->FullOffsetInMDC);
3624	assert(VFTableLayouts.count(id) == 0);
3625	SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
3626	Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
3627	VFTableLayouts[id] = std::make_unique<VTableLayout>(
3628	args: ArrayRef<size_t>{0}, args: Builder.vtable_components(), args&: VTableThunks,
3629	args: EmptyAddressPointsMap);
3630	Thunks.insert(I: Builder.thunks_begin(), E: Builder.thunks_end());
3631
3632	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3633	for (const auto &Loc : Builder.vtable_locations()) {
3634	auto Insert = NewMethodLocations.insert(KV: Loc);
3635	if (!Insert.second) {
3636	const MethodVFTableLocation &NewLoc = Loc.second;
3637	MethodVFTableLocation &OldLoc = Insert.first->second;
3638	if (vfptrIsEarlierInMDC(Layout, LHS: NewLoc, RHS: OldLoc))
3639	OldLoc = NewLoc;
3640	}
3641	}
3642	}
3643
3644	MethodVFTableLocations.insert(I: NewMethodLocations.begin(),
3645	E: NewMethodLocations.end());
3646	if (Context.getLangOpts().DumpVTableLayouts)
3647	dumpMethodLocations(RD, NewMethods: NewMethodLocations, llvm::outs());
3648	}
3649
3650	void MicrosoftVTableContext::dumpMethodLocations(
3651	const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
3652	raw_ostream &Out) {
3653	// Compute the vtable indices for all the member functions.
3654	// Store them in a map keyed by the location so we'll get a sorted table.
3655	std::map<MethodVFTableLocation, std::string> IndicesMap;
3656	bool HasNonzeroOffset = false;
3657
3658	for (const auto &I : NewMethods) {
3659	const CXXMethodDecl *MD = cast<const CXXMethodDecl>(Val: I.first.getDecl());
3660	assert(hasVtableSlot(MD));
3661
3662	std::string MethodName = PredefinedExpr::ComputeName(
3663	PredefinedIdentKind::PrettyFunctionNoVirtual, MD);
3664
3665	if (isa<CXXDestructorDecl>(Val: MD)) {
3666	IndicesMap[I.second] = MethodName + " [scalar deleting]";
3667	} else {
3668	IndicesMap[I.second] = MethodName;
3669	}
3670
3671	if (!I.second.VFPtrOffset.isZero() || I.second.VBTableIndex != 0)
3672	HasNonzeroOffset = true;
3673	}
3674
3675	// Print the vtable indices for all the member functions.
3676	if (!IndicesMap.empty()) {
3677	Out << "VFTable indices for ";
3678	Out << "'";
3679	RD->printQualifiedName(Out);
3680	Out << "' (" << IndicesMap.size()
3681	<< (IndicesMap.size() == 1 ? " entry" : " entries") << ").\n";
3682
3683	CharUnits LastVFPtrOffset = CharUnits::fromQuantity(Quantity: -1);
3684	uint64_t LastVBIndex = 0;
3685	for (const auto &I : IndicesMap) {
3686	CharUnits VFPtrOffset = I.first.VFPtrOffset;
3687	uint64_t VBIndex = I.first.VBTableIndex;
3688	if (HasNonzeroOffset &&
3689	(VFPtrOffset != LastVFPtrOffset || VBIndex != LastVBIndex)) {
3690	assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);
3691	Out << " -- accessible via ";
3692	if (VBIndex)
3693	Out << "vbtable index " << VBIndex << ", ";
3694	Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";
3695	LastVFPtrOffset = VFPtrOffset;
3696	LastVBIndex = VBIndex;
3697	}
3698
3699	uint64_t VTableIndex = I.first.Index;
3700	const std::string &MethodName = I.second;
3701	Out << llvm::format(Fmt: "%4" PRIu64 " | ", Vals: VTableIndex) << MethodName << '\n';
3702	}
3703	Out << '\n';
3704	}
3705
3706	Out.flush();
3707	}
3708
3709	const VirtualBaseInfo &MicrosoftVTableContext::computeVBTableRelatedInformation(
3710	const CXXRecordDecl *RD) {
3711	VirtualBaseInfo *VBI;
3712
3713	{
3714	// Get or create a VBI for RD. Don't hold a reference to the DenseMap cell,
3715	// as it may be modified and rehashed under us.
3716	std::unique_ptr<VirtualBaseInfo> &Entry = VBaseInfo[RD];
3717	if (Entry)
3718	return *Entry;
3719	Entry = std::make_unique<VirtualBaseInfo>();
3720	VBI = Entry.get();
3721	}
3722
3723	computeVTablePaths(/*ForVBTables=*/true, RD, Paths&: VBI->VBPtrPaths);
3724
3725	// First, see if the Derived class shared the vbptr with a non-virtual base.
3726	const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3727	if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {
3728	// If the Derived class shares the vbptr with a non-virtual base, the shared
3729	// virtual bases come first so that the layout is the same.
3730	const VirtualBaseInfo &BaseInfo =
3731	computeVBTableRelatedInformation(RD: VBPtrBase);
3732	VBI->VBTableIndices.insert(I: BaseInfo.VBTableIndices.begin(),
3733	E: BaseInfo.VBTableIndices.end());
3734	}
3735
3736	// New vbases are added to the end of the vbtable.
3737	// Skip the self entry and vbases visited in the non-virtual base, if any.
3738	unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();
3739	for (const auto &VB : RD->vbases()) {
3740	const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();
3741	if (!VBI->VBTableIndices.count(Val: CurVBase))
3742	VBI->VBTableIndices[CurVBase] = VBTableIndex++;
3743	}
3744
3745	return *VBI;
3746	}
3747
3748	unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
3749	const CXXRecordDecl *VBase) {
3750	const VirtualBaseInfo &VBInfo = computeVBTableRelatedInformation(RD: Derived);
3751	assert(VBInfo.VBTableIndices.count(VBase));
3752	return VBInfo.VBTableIndices.find(Val: VBase)->second;
3753	}
3754
3755	const VPtrInfoVector &
3756	MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
3757	return computeVBTableRelatedInformation(RD).VBPtrPaths;
3758	}
3759
3760	const VPtrInfoVector &
3761	MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {
3762	computeVTableRelatedInformation(RD);
3763
3764	assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");
3765	return *VFPtrLocations[RD];
3766	}
3767
3768	const VTableLayout &
3769	MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
3770	CharUnits VFPtrOffset) {
3771	computeVTableRelatedInformation(RD);
3772
3773	VFTableIdTy id(RD, VFPtrOffset);
3774	assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");
3775	return *VFTableLayouts[id];
3776	}
3777
3778	MethodVFTableLocation
3779	MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {
3780	assert(hasVtableSlot(cast<CXXMethodDecl>(GD.getDecl())) &&
3781	"Only use this method for virtual methods or dtors");
3782	if (isa<CXXDestructorDecl>(Val: GD.getDecl()))
3783	assert(GD.getDtorType() == Dtor_Deleting);
3784
3785	GD = GD.getCanonicalDecl();
3786
3787	MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(Val: GD);
3788	if (I != MethodVFTableLocations.end())
3789	return I->second;
3790
3791	const CXXRecordDecl *RD = cast<CXXMethodDecl>(Val: GD.getDecl())->getParent();
3792
3793	computeVTableRelatedInformation(RD);
3794
3795	I = MethodVFTableLocations.find(Val: GD);
3796	assert(I != MethodVFTableLocations.end() && "Did not find index!");
3797	return I->second;
3798	}
3799