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