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