Clang Project

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