Coverage Report

Created: 2022-07-16 07:03

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