Coverage Report

Created: 2020-09-22 08:39

/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/SmallPtrSet.h"
21
#include "llvm/Support/Format.h"
22
#include "llvm/Support/raw_ostream.h"
23
#include <algorithm>
24
#include <cstdio>
25
26
using namespace clang;
27
28
#define DUMP_OVERRIDERS 0
29
30
namespace {
31
32
/// BaseOffset - Represents an offset from a derived class to a direct or
33
/// indirect base class.
34
struct BaseOffset {
35
  /// DerivedClass - The derived class.
36
  const CXXRecordDecl *DerivedClass;
37
38
  /// VirtualBase - If the path from the derived class to the base class
39
  /// involves virtual base classes, this holds the declaration of the last
40
  /// virtual base in this path (i.e. closest to the base class).
41
  const CXXRecordDecl *VirtualBase;
42
43
  /// NonVirtualOffset - The offset from the derived class to the base class.
44
  /// (Or the offset from the virtual base class to the base class, if the
45
  /// path from the derived class to the base class involves a virtual base
46
  /// class.
47
  CharUnits NonVirtualOffset;
48
49
  BaseOffset() : DerivedClass(nullptr), VirtualBase(nullptr),
50
37.1k
                 NonVirtualOffset(CharUnits::Zero()) { }
51
  BaseOffset(const CXXRecordDecl *DerivedClass,
52
             const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
53
    : DerivedClass(DerivedClass), VirtualBase(VirtualBase),
54
7.36k
    NonVirtualOffset(NonVirtualOffset) { }
55
56
29.8k
  bool isEmpty() const { return NonVirtualOffset.isZero() && 
!VirtualBase29.3k
; }
57
};
58
59
/// FinalOverriders - Contains the final overrider member functions for all
60
/// member functions in the base subobjects of a class.
61
class FinalOverriders {
62
public:
63
  /// OverriderInfo - Information about a final overrider.
64
  struct OverriderInfo {
65
    /// Method - The method decl of the overrider.
66
    const CXXMethodDecl *Method;
67
68
    /// VirtualBase - The virtual base class subobject of this overrider.
69
    /// Note that this records the closest derived virtual base class subobject.
70
    const CXXRecordDecl *VirtualBase;
71
72
    /// Offset - the base offset of the overrider's parent in the layout class.
73
    CharUnits Offset;
74
75
    OverriderInfo() : Method(nullptr), VirtualBase(nullptr),
76
23.7k
                      Offset(CharUnits::Zero()) { }
77
  };
78
79
private:
80
  /// MostDerivedClass - The most derived class for which the final overriders
81
  /// are stored.
82
  const CXXRecordDecl *MostDerivedClass;
83
84
  /// MostDerivedClassOffset - If we're building final overriders for a
85
  /// construction vtable, this holds the offset from the layout class to the
86
  /// most derived class.
87
  const CharUnits MostDerivedClassOffset;
88
89
  /// LayoutClass - The class we're using for layout information. Will be
90
  /// different than the most derived class if the final overriders are for a
91
  /// construction vtable.
92
  const CXXRecordDecl *LayoutClass;
93
94
  ASTContext &Context;
95
96
  /// MostDerivedClassLayout - the AST record layout of the most derived class.
97
  const ASTRecordLayout &MostDerivedClassLayout;
98
99
  /// MethodBaseOffsetPairTy - Uniquely identifies a member function
100
  /// in a base subobject.
101
  typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
102
103
  typedef llvm::DenseMap<MethodBaseOffsetPairTy,
104
                         OverriderInfo> OverridersMapTy;
105
106
  /// OverridersMap - The final overriders for all virtual member functions of
107
  /// all the base subobjects of the most derived class.
108
  OverridersMapTy OverridersMap;
109
110
  /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
111
  /// as a record decl and a subobject number) and its offsets in the most
112
  /// derived class as well as the layout class.
113
  typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>,
114
                         CharUnits> SubobjectOffsetMapTy;
115
116
  typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
117
118
  /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
119
  /// given base.
120
  void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
121
                          CharUnits OffsetInLayoutClass,
122
                          SubobjectOffsetMapTy &SubobjectOffsets,
123
                          SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
124
                          SubobjectCountMapTy &SubobjectCounts);
125
126
  typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
127
128
  /// dump - dump the final overriders for a base subobject, and all its direct
129
  /// and indirect base subobjects.
130
  void dump(raw_ostream &Out, BaseSubobject Base,
131
            VisitedVirtualBasesSetTy& VisitedVirtualBases);
132
133
public:
134
  FinalOverriders(const CXXRecordDecl *MostDerivedClass,
135
                  CharUnits MostDerivedClassOffset,
136
                  const CXXRecordDecl *LayoutClass);
137
138
  /// getOverrider - Get the final overrider for the given method declaration in
139
  /// the subobject with the given base offset.
140
  OverriderInfo getOverrider(const CXXMethodDecl *MD,
141
50.4k
                             CharUnits BaseOffset) const {
142
50.4k
    assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) &&
143
50.4k
           "Did not find overrider!");
144
145
50.4k
    return OverridersMap.lookup(std::make_pair(MD, BaseOffset));
146
50.4k
  }
147
148
  /// dump - dump the final overriders.
149
0
  void dump() {
150
0
    VisitedVirtualBasesSetTy VisitedVirtualBases;
151
0
    dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()),
152
0
         VisitedVirtualBases);
153
0
  }
154
155
};
156
157
FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
158
                                 CharUnits MostDerivedClassOffset,
159
                                 const CXXRecordDecl *LayoutClass)
160
  : MostDerivedClass(MostDerivedClass),
161
  MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
162
  Context(MostDerivedClass->getASTContext()),
163
5.57k
  MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
164
165
  // Compute base offsets.
166
5.57k
  SubobjectOffsetMapTy SubobjectOffsets;
167
5.57k
  SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
168
5.57k
  SubobjectCountMapTy SubobjectCounts;
169
5.57k
  ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()),
170
5.57k
                     /*IsVirtual=*/false,
171
5.57k
                     MostDerivedClassOffset,
172
5.57k
                     SubobjectOffsets, SubobjectLayoutClassOffsets,
173
5.57k
                     SubobjectCounts);
174
175
  // Get the final overriders.
176
5.57k
  CXXFinalOverriderMap FinalOverriders;
177
5.57k
  MostDerivedClass->getFinalOverriders(FinalOverriders);
178
179
23.5k
  for (const auto &Overrider : FinalOverriders) {
180
23.5k
    const CXXMethodDecl *MD = Overrider.first;
181
23.5k
    const OverridingMethods &Methods = Overrider.second;
182
183
23.7k
    for (const auto &M : Methods) {
184
23.7k
      unsigned SubobjectNumber = M.first;
185
23.7k
      assert(SubobjectOffsets.count(std::make_pair(MD->getParent(),
186
23.7k
                                                   SubobjectNumber)) &&
187
23.7k
             "Did not find subobject offset!");
188
189
23.7k
      CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(),
190
23.7k
                                                            SubobjectNumber)];
191
192
23.7k
      assert(M.second.size() == 1 && "Final overrider is not unique!");
193
23.7k
      const UniqueVirtualMethod &Method = M.second.front();
194
195
23.7k
      const CXXRecordDecl *OverriderRD = Method.Method->getParent();
196
23.7k
      assert(SubobjectLayoutClassOffsets.count(
197
23.7k
             std::make_pair(OverriderRD, Method.Subobject))
198
23.7k
             && "Did not find subobject offset!");
199
23.7k
      CharUnits OverriderOffset =
200
23.7k
        SubobjectLayoutClassOffsets[std::make_pair(OverriderRD,
201
23.7k
                                                   Method.Subobject)];
202
203
23.7k
      OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)];
204
23.7k
      assert(!Overrider.Method && "Overrider should not exist yet!");
205
206
23.7k
      Overrider.Offset = OverriderOffset;
207
23.7k
      Overrider.Method = Method.Method;
208
23.7k
      Overrider.VirtualBase = Method.InVirtualSubobject;
209
23.7k
    }
210
23.5k
  }
211
212
#if DUMP_OVERRIDERS
213
  // And dump them (for now).
214
  dump();
215
#endif
216
5.57k
}
217
218
static BaseOffset ComputeBaseOffset(const ASTContext &Context,
219
                                    const CXXRecordDecl *DerivedRD,
220
7.36k
                                    const CXXBasePath &Path) {
221
7.36k
  CharUnits NonVirtualOffset = CharUnits::Zero();
222
223
7.36k
  unsigned NonVirtualStart = 0;
224
7.36k
  const CXXRecordDecl *VirtualBase = nullptr;
225
226
  // First, look for the virtual base class.
227
16.1k
  for (int I = Path.size(), E = 0; I != E; 
--I8.79k
) {
228
9.22k
    const CXXBasePathElement &Element = Path[I - 1];
229
230
9.22k
    if (Element.Base->isVirtual()) {
231
429
      NonVirtualStart = I;
232
429
      QualType VBaseType = Element.Base->getType();
233
429
      VirtualBase = VBaseType->getAsCXXRecordDecl();
234
429
      break;
235
429
    }
236
9.22k
  }
237
238
  // Now compute the non-virtual offset.
239
16.1k
  for (unsigned I = NonVirtualStart, E = Path.size(); I != E; 
++I8.79k
) {
240
8.79k
    const CXXBasePathElement &Element = Path[I];
241
242
    // Check the base class offset.
243
8.79k
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
244
245
8.79k
    const CXXRecordDecl *Base = Element.Base->getType()->getAsCXXRecordDecl();
246
247
8.79k
    NonVirtualOffset += Layout.getBaseClassOffset(Base);
248
8.79k
  }
249
250
  // FIXME: This should probably use CharUnits or something. Maybe we should
251
  // even change the base offsets in ASTRecordLayout to be specified in
252
  // CharUnits.
253
7.36k
  return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
254
255
7.36k
}
256
257
static BaseOffset ComputeBaseOffset(const ASTContext &Context,
258
                                    const CXXRecordDecl *BaseRD,
259
305
                                    const CXXRecordDecl *DerivedRD) {
260
305
  CXXBasePaths Paths(/*FindAmbiguities=*/false,
261
305
                     /*RecordPaths=*/true, /*DetectVirtual=*/false);
262
263
305
  if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
264
0
    llvm_unreachable("Class must be derived from the passed in base class!");
265
266
305
  return ComputeBaseOffset(Context, DerivedRD, Paths.front());
267
305
}
268
269
static BaseOffset
270
ComputeReturnAdjustmentBaseOffset(ASTContext &Context,
271
                                  const CXXMethodDecl *DerivedMD,
272
22.1k
                                  const CXXMethodDecl *BaseMD) {
273
22.1k
  const auto *BaseFT = BaseMD->getType()->castAs<FunctionType>();
274
22.1k
  const auto *DerivedFT = DerivedMD->getType()->castAs<FunctionType>();
275
276
  // Canonicalize the return types.
277
22.1k
  CanQualType CanDerivedReturnType =
278
22.1k
      Context.getCanonicalType(DerivedFT->getReturnType());
279
22.1k
  CanQualType CanBaseReturnType =
280
22.1k
      Context.getCanonicalType(BaseFT->getReturnType());
281
282
22.1k
  assert(CanDerivedReturnType->getTypeClass() ==
283
22.1k
         CanBaseReturnType->getTypeClass() &&
284
22.1k
         "Types must have same type class!");
285
286
22.1k
  if (CanDerivedReturnType == CanBaseReturnType) {
287
    // No adjustment needed.
288
21.8k
    return BaseOffset();
289
21.8k
  }
290
291
307
  if (isa<ReferenceType>(CanDerivedReturnType)) {
292
37
    CanDerivedReturnType =
293
37
      CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
294
37
    CanBaseReturnType =
295
37
      CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
296
270
  } else if (isa<PointerType>(CanDerivedReturnType)) {
297
270
    CanDerivedReturnType =
298
270
      CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
299
270
    CanBaseReturnType =
300
270
      CanBaseReturnType->getAs<PointerType>()->getPointeeType();
301
0
  } else {
302
0
    llvm_unreachable("Unexpected return type!");
303
0
  }
304
305
  // We need to compare unqualified types here; consider
306
  //   const T *Base::foo();
307
  //   T *Derived::foo();
308
307
  if (CanDerivedReturnType.getUnqualifiedType() ==
309
2
      CanBaseReturnType.getUnqualifiedType()) {
310
    // No adjustment needed.
311
2
    return BaseOffset();
312
2
  }
313
314
305
  const CXXRecordDecl *DerivedRD =
315
305
    cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl());
316
317
305
  const CXXRecordDecl *BaseRD =
318
305
    cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());
319
320
305
  return ComputeBaseOffset(Context, BaseRD, DerivedRD);
321
305
}
322
323
void
324
FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
325
                              CharUnits OffsetInLayoutClass,
326
                              SubobjectOffsetMapTy &SubobjectOffsets,
327
                              SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
328
12.9k
                              SubobjectCountMapTy &SubobjectCounts) {
329
12.9k
  const CXXRecordDecl *RD = Base.getBase();
330
331
12.9k
  unsigned SubobjectNumber = 0;
332
12.9k
  if (!IsVirtual)
333
11.5k
    SubobjectNumber = ++SubobjectCounts[RD];
334
335
  // Set up the subobject to offset mapping.
336
12.9k
  assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))
337
12.9k
         && "Subobject offset already exists!");
338
12.9k
  assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber))
339
12.9k
         && "Subobject offset already exists!");
340
341
12.9k
  SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();
342
12.9k
  SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =
343
12.9k
    OffsetInLayoutClass;
344
345
  // Traverse our bases.
346
7.68k
  for (const auto &B : RD->bases()) {
347
7.68k
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
348
349
7.68k
    CharUnits BaseOffset;
350
7.68k
    CharUnits BaseOffsetInLayoutClass;
351
7.68k
    if (B.isVirtual()) {
352
      // Check if we've visited this virtual base before.
353
1.68k
      if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))
354
343
        continue;
355
356
1.34k
      const ASTRecordLayout &LayoutClassLayout =
357
1.34k
        Context.getASTRecordLayout(LayoutClass);
358
359
1.34k
      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
360
1.34k
      BaseOffsetInLayoutClass =
361
1.34k
        LayoutClassLayout.getVBaseClassOffset(BaseDecl);
362
6.00k
    } else {
363
6.00k
      const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
364
6.00k
      CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);
365
366
6.00k
      BaseOffset = Base.getBaseOffset() + Offset;
367
6.00k
      BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
368
6.00k
    }
369
370
7.34k
    ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset),
371
7.34k
                       B.isVirtual(), BaseOffsetInLayoutClass,
372
7.34k
                       SubobjectOffsets, SubobjectLayoutClassOffsets,
373
7.34k
                       SubobjectCounts);
374
7.34k
  }
375
12.9k
}
376
377
void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
378
0
                           VisitedVirtualBasesSetTy &VisitedVirtualBases) {
379
0
  const CXXRecordDecl *RD = Base.getBase();
380
0
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
381
0
382
0
  for (const auto &B : RD->bases()) {
383
0
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
384
0
385
0
    // Ignore bases that don't have any virtual member functions.
386
0
    if (!BaseDecl->isPolymorphic())
387
0
      continue;
388
0
389
0
    CharUnits BaseOffset;
390
0
    if (B.isVirtual()) {
391
0
      if (!VisitedVirtualBases.insert(BaseDecl).second) {
392
0
        // We've visited this base before.
393
0
        continue;
394
0
      }
395
0
396
0
      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
397
0
    } else {
398
0
      BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();
399
0
    }
400
0
401
0
    dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
402
0
  }
403
0
404
0
  Out << "Final overriders for (";
405
0
  RD->printQualifiedName(Out);
406
0
  Out << ", ";
407
0
  Out << Base.getBaseOffset().getQuantity() << ")\n";
408
0
409
0
  // Now dump the overriders for this base subobject.
410
0
  for (const auto *MD : RD->methods()) {
411
0
    if (!VTableContextBase::hasVtableSlot(MD))
412
0
      continue;
413
0
    MD = MD->getCanonicalDecl();
414
0
415
0
    OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());
416
0
417
0
    Out << "  ";
418
0
    MD->printQualifiedName(Out);
419
0
    Out << " - (";
420
0
    Overrider.Method->printQualifiedName(Out);
421
0
    Out << ", " << Overrider.Offset.getQuantity() << ')';
422
0
423
0
    BaseOffset Offset;
424
0
    if (!Overrider.Method->isPure())
425
0
      Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
426
0
427
0
    if (!Offset.isEmpty()) {
428
0
      Out << " [ret-adj: ";
429
0
      if (Offset.VirtualBase) {
430
0
        Offset.VirtualBase->printQualifiedName(Out);
431
0
        Out << " vbase, ";
432
0
      }
433
0
434
0
      Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
435
0
    }
436
0
437
0
    Out << "\n";
438
0
  }
439
0
}
440
441
/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
442
struct VCallOffsetMap {
443
444
  typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
445
446
  /// Offsets - Keeps track of methods and their offsets.
447
  // FIXME: This should be a real map and not a vector.
448
  SmallVector<MethodAndOffsetPairTy, 16> Offsets;
449
450
  /// MethodsCanShareVCallOffset - Returns whether two virtual member functions
451
  /// can share the same vcall offset.
452
  static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
453
                                         const CXXMethodDecl *RHS);
454
455
public:
456
  /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
457
  /// add was successful, or false if there was already a member function with
458
  /// the same signature in the map.
459
  bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
460
461
  /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
462
  /// vtable address point) for the given virtual member function.
463
  CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
464
465
  // empty - Return whether the offset map is empty or not.
466
980
  bool empty() const { return Offsets.empty(); }
467
};
468
469
static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
470
211
                                    const CXXMethodDecl *RHS) {
471
211
  const FunctionProtoType *LT =
472
211
    cast<FunctionProtoType>(LHS->getType().getCanonicalType());
473
211
  const FunctionProtoType *RT =
474
211
    cast<FunctionProtoType>(RHS->getType().getCanonicalType());
475
476
  // Fast-path matches in the canonical types.
477
211
  if (LT == RT) 
return true208
;
478
479
  // Force the signatures to match.  We can't rely on the overrides
480
  // list here because there isn't necessarily an inheritance
481
  // relationship between the two methods.
482
3
  if (LT->getMethodQuals() != RT->getMethodQuals())
483
3
    return false;
484
0
  return LT->getParamTypes() == RT->getParamTypes();
485
0
}
486
487
bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
488
559
                                                const CXXMethodDecl *RHS) {
489
559
  assert(VTableContextBase::hasVtableSlot(LHS) && "LHS must be virtual!");
490
559
  assert(VTableContextBase::hasVtableSlot(RHS) && "LHS must be virtual!");
491
492
  // A destructor can share a vcall offset with another destructor.
493
559
  if (isa<CXXDestructorDecl>(LHS))
494
175
    return isa<CXXDestructorDecl>(RHS);
495
496
  // FIXME: We need to check more things here.
497
498
  // The methods must have the same name.
499
384
  DeclarationName LHSName = LHS->getDeclName();
500
384
  DeclarationName RHSName = RHS->getDeclName();
501
384
  if (LHSName != RHSName)
502
173
    return false;
503
504
  // And the same signatures.
505
211
  return HasSameVirtualSignature(LHS, RHS);
506
211
}
507
508
bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,
509
846
                                    CharUnits OffsetOffset) {
510
  // Check if we can reuse an offset.
511
223
  for (const auto &OffsetPair : Offsets) {
512
223
    if (MethodsCanShareVCallOffset(OffsetPair.first, MD))
513
83
      return false;
514
223
  }
515
516
  // Add the offset.
517
763
  Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));
518
763
  return true;
519
846
}
520
521
283
CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
522
  // Look for an offset.
523
336
  for (const auto &OffsetPair : Offsets) {
524
336
    if (MethodsCanShareVCallOffset(OffsetPair.first, MD))
525
283
      return OffsetPair.second;
526
336
  }
527
528
283
  
llvm_unreachable0
("Should always find a vcall offset offset!");
529
283
}
530
531
/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
532
class VCallAndVBaseOffsetBuilder {
533
public:
534
  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
535
    VBaseOffsetOffsetsMapTy;
536
537
private:
538
  const ItaniumVTableContext &VTables;
539
540
  /// MostDerivedClass - The most derived class for which we're building vcall
541
  /// and vbase offsets.
542
  const CXXRecordDecl *MostDerivedClass;
543
544
  /// LayoutClass - The class we're using for layout information. Will be
545
  /// different than the most derived class if we're building a construction
546
  /// vtable.
547
  const CXXRecordDecl *LayoutClass;
548
549
  /// Context - The ASTContext which we will use for layout information.
550
  ASTContext &Context;
551
552
  /// Components - vcall and vbase offset components
553
  typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
554
  VTableComponentVectorTy Components;
555
556
  /// VisitedVirtualBases - Visited virtual bases.
557
  llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
558
559
  /// VCallOffsets - Keeps track of vcall offsets.
560
  VCallOffsetMap VCallOffsets;
561
562
563
  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
564
  /// relative to the address point.
565
  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
566
567
  /// FinalOverriders - The final overriders of the most derived class.
568
  /// (Can be null when we're not building a vtable of the most derived class).
569
  const FinalOverriders *Overriders;
570
571
  /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
572
  /// given base subobject.
573
  void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
574
                               CharUnits RealBaseOffset);
575
576
  /// AddVCallOffsets - Add vcall offsets for the given base subobject.
577
  void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
578
579
  /// AddVBaseOffsets - Add vbase offsets for the given class.
580
  void AddVBaseOffsets(const CXXRecordDecl *Base,
581
                       CharUnits OffsetInLayoutClass);
582
583
  /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
584
  /// chars, relative to the vtable address point.
585
  CharUnits getCurrentOffsetOffset() const;
586
587
public:
588
  VCallAndVBaseOffsetBuilder(const ItaniumVTableContext &VTables,
589
                             const CXXRecordDecl *MostDerivedClass,
590
                             const CXXRecordDecl *LayoutClass,
591
                             const FinalOverriders *Overriders,
592
                             BaseSubobject Base, bool BaseIsVirtual,
593
                             CharUnits OffsetInLayoutClass)
594
      : VTables(VTables), MostDerivedClass(MostDerivedClass),
595
        LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
596
5.28k
        Overriders(Overriders) {
597
598
    // Add vcall and vbase offsets.
599
5.28k
    AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);
600
5.28k
  }
601
602
  /// Methods for iterating over the components.
603
  typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
604
4.90k
  const_iterator components_begin() const { return Components.rbegin(); }
605
4.90k
  const_iterator components_end() const { return Components.rend(); }
606
607
786
  const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
608
4.55k
  const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
609
4.55k
    return VBaseOffsetOffsets;
610
4.55k
  }
611
};
612
613
void
614
VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
615
                                                    bool BaseIsVirtual,
616
9.23k
                                                    CharUnits RealBaseOffset) {
617
9.23k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
618
619
  // Itanium C++ ABI 2.5.2:
620
  //   ..in classes sharing a virtual table with a primary base class, the vcall
621
  //   and vbase offsets added by the derived class all come before the vcall
622
  //   and vbase offsets required by the base class, so that the latter may be
623
  //   laid out as required by the base class without regard to additions from
624
  //   the derived class(es).
625
626
  // (Since we're emitting the vcall and vbase offsets in reverse order, we'll
627
  // emit them for the primary base first).
628
9.23k
  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
629
3.95k
    bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
630
631
3.95k
    CharUnits PrimaryBaseOffset;
632
633
    // Get the base offset of the primary base.
634
3.95k
    if (PrimaryBaseIsVirtual) {
635
382
      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
636
382
             "Primary vbase should have a zero offset!");
637
638
382
      const ASTRecordLayout &MostDerivedClassLayout =
639
382
        Context.getASTRecordLayout(MostDerivedClass);
640
641
382
      PrimaryBaseOffset =
642
382
        MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
643
3.57k
    } else {
644
3.57k
      assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
645
3.57k
             "Primary base should have a zero offset!");
646
647
3.57k
      PrimaryBaseOffset = Base.getBaseOffset();
648
3.57k
    }
649
650
3.95k
    AddVCallAndVBaseOffsets(
651
3.95k
      BaseSubobject(PrimaryBase,PrimaryBaseOffset),
652
3.95k
      PrimaryBaseIsVirtual, RealBaseOffset);
653
3.95k
  }
654
655
9.23k
  AddVBaseOffsets(Base.getBase(), RealBaseOffset);
656
657
  // We only want to add vcall offsets for virtual bases.
658
9.23k
  if (BaseIsVirtual)
659
891
    AddVCallOffsets(Base, RealBaseOffset);
660
9.23k
}
661
662
2.40k
CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
663
  // OffsetIndex is the index of this vcall or vbase offset, relative to the
664
  // vtable address point. (We subtract 3 to account for the information just
665
  // above the address point, the RTTI info, the offset to top, and the
666
  // vcall offset itself).
667
2.40k
  int64_t OffsetIndex = -(int64_t)(3 + Components.size());
668
669
  // Under the relative ABI, the offset widths are 32-bit ints instead of
670
  // pointer widths.
671
2.40k
  CharUnits OffsetWidth = Context.toCharUnitsFromBits(
672
19
      VTables.isRelativeLayout() ? 32
673
2.39k
                                 : Context.getTargetInfo().getPointerWidth(0));
674
2.40k
  CharUnits OffsetOffset = OffsetWidth * OffsetIndex;
675
676
2.40k
  return OffsetOffset;
677
2.40k
}
678
679
void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,
680
1.29k
                                                 CharUnits VBaseOffset) {
681
1.29k
  const CXXRecordDecl *RD = Base.getBase();
682
1.29k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
683
684
1.29k
  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
685
686
  // Handle the primary base first.
687
  // We only want to add vcall offsets if the base is non-virtual; a virtual
688
  // primary base will have its vcall and vbase offsets emitted already.
689
1.29k
  if (PrimaryBase && 
!Layout.isPrimaryBaseVirtual()274
) {
690
    // Get the base offset of the primary base.
691
166
    assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
692
166
           "Primary base should have a zero offset!");
693
694
166
    AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),
695
166
                    VBaseOffset);
696
166
  }
697
698
  // Add the vcall offsets.
699
6.71k
  for (const auto *MD : RD->methods()) {
700
6.71k
    if (!VTableContextBase::hasVtableSlot(MD))
701
5.86k
      continue;
702
846
    MD = MD->getCanonicalDecl();
703
704
846
    CharUnits OffsetOffset = getCurrentOffsetOffset();
705
706
    // Don't add a vcall offset if we already have one for this member function
707
    // signature.
708
846
    if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
709
83
      continue;
710
711
763
    CharUnits Offset = CharUnits::Zero();
712
713
763
    if (Overriders) {
714
      // Get the final overrider.
715
587
      FinalOverriders::OverriderInfo Overrider =
716
587
        Overriders->getOverrider(MD, Base.getBaseOffset());
717
718
      /// The vcall offset is the offset from the virtual base to the object
719
      /// where the function was overridden.
720
587
      Offset = Overrider.Offset - VBaseOffset;
721
587
    }
722
723
763
    Components.push_back(
724
763
      VTableComponent::MakeVCallOffset(Offset));
725
763
  }
726
727
  // And iterate over all non-virtual bases (ignoring the primary base).
728
885
  for (const auto &B : RD->bases()) {
729
885
    if (B.isVirtual())
730
477
      continue;
731
732
408
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
733
408
    if (BaseDecl == PrimaryBase)
734
166
      continue;
735
736
    // Get the base offset of this base.
737
242
    CharUnits BaseOffset = Base.getBaseOffset() +
738
242
      Layout.getBaseClassOffset(BaseDecl);
739
740
242
    AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset),
741
242
                    VBaseOffset);
742
242
  }
743
1.29k
}
744
745
void
746
VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
747
21.1k
                                            CharUnits OffsetInLayoutClass) {
748
21.1k
  const ASTRecordLayout &LayoutClassLayout =
749
21.1k
    Context.getASTRecordLayout(LayoutClass);
750
751
  // Add vbase offsets.
752
11.9k
  for (const auto &B : RD->bases()) {
753
11.9k
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
754
755
    // Check if this is a virtual base that we haven't visited before.
756
11.9k
    if (B.isVirtual() && 
VisitedVirtualBases.insert(BaseDecl).second3.93k
) {
757
1.56k
      CharUnits Offset =
758
1.56k
        LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;
759
760
      // Add the vbase offset offset.
761
1.56k
      assert(!VBaseOffsetOffsets.count(BaseDecl) &&
762
1.56k
             "vbase offset offset already exists!");
763
764
1.56k
      CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
765
1.56k
      VBaseOffsetOffsets.insert(
766
1.56k
          std::make_pair(BaseDecl, VBaseOffsetOffset));
767
768
1.56k
      Components.push_back(
769
1.56k
          VTableComponent::MakeVBaseOffset(Offset));
770
1.56k
    }
771
772
    // Check the base class looking for more vbase offsets.
773
11.9k
    AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);
774
11.9k
  }
775
21.1k
}
776
777
/// ItaniumVTableBuilder - Class for building vtable layout information.
778
class ItaniumVTableBuilder {
779
public:
780
  /// PrimaryBasesSetVectorTy - A set vector of direct and indirect
781
  /// primary bases.
782
  typedef llvm::SmallSetVector<const CXXRecordDecl *, 8>
783
    PrimaryBasesSetVectorTy;
784
785
  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits>
786
    VBaseOffsetOffsetsMapTy;
787
788
  typedef VTableLayout::AddressPointsMapTy AddressPointsMapTy;
789
790
  typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
791
792
private:
793
  /// VTables - Global vtable information.
794
  ItaniumVTableContext &VTables;
795
796
  /// MostDerivedClass - The most derived class for which we're building this
797
  /// vtable.
798
  const CXXRecordDecl *MostDerivedClass;
799
800
  /// MostDerivedClassOffset - If we're building a construction vtable, this
801
  /// holds the offset from the layout class to the most derived class.
802
  const CharUnits MostDerivedClassOffset;
803
804
  /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual
805
  /// base. (This only makes sense when building a construction vtable).
806
  bool MostDerivedClassIsVirtual;
807
808
  /// LayoutClass - The class we're using for layout information. Will be
809
  /// different than the most derived class if we're building a construction
810
  /// vtable.
811
  const CXXRecordDecl *LayoutClass;
812
813
  /// Context - The ASTContext which we will use for layout information.
814
  ASTContext &Context;
815
816
  /// FinalOverriders - The final overriders of the most derived class.
817
  const FinalOverriders Overriders;
818
819
  /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
820
  /// bases in this vtable.
821
  llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
822
823
  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
824
  /// the most derived class.
825
  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
826
827
  /// Components - The components of the vtable being built.
828
  SmallVector<VTableComponent, 64> Components;
829
830
  /// AddressPoints - Address points for the vtable being built.
831
  AddressPointsMapTy AddressPoints;
832
833
  /// MethodInfo - Contains information about a method in a vtable.
834
  /// (Used for computing 'this' pointer adjustment thunks.
835
  struct MethodInfo {
836
    /// BaseOffset - The base offset of this method.
837
    const CharUnits BaseOffset;
838
839
    /// BaseOffsetInLayoutClass - The base offset in the layout class of this
840
    /// method.
841
    const CharUnits BaseOffsetInLayoutClass;
842
843
    /// VTableIndex - The index in the vtable that this method has.
844
    /// (For destructors, this is the index of the complete destructor).
845
    const uint64_t VTableIndex;
846
847
    MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass,
848
               uint64_t VTableIndex)
849
      : BaseOffset(BaseOffset),
850
      BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
851
20.0k
      VTableIndex(VTableIndex) { }
852
853
    MethodInfo()
854
      : BaseOffset(CharUnits::Zero()),
855
      BaseOffsetInLayoutClass(CharUnits::Zero()),
856
0
      VTableIndex(0) { }
857
858
    MethodInfo(MethodInfo const&) = default;
859
  };
860
861
  typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
862
863
  /// MethodInfoMap - The information for all methods in the vtable we're
864
  /// currently building.
865
  MethodInfoMapTy MethodInfoMap;
866
867
  /// MethodVTableIndices - Contains the index (relative to the vtable address
868
  /// point) where the function pointer for a virtual function is stored.
869
  MethodVTableIndicesTy MethodVTableIndices;
870
871
  typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
872
873
  /// VTableThunks - The thunks by vtable index in the vtable currently being
874
  /// built.
875
  VTableThunksMapTy VTableThunks;
876
877
  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
878
  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
879
880
  /// Thunks - A map that contains all the thunks needed for all methods in the
881
  /// most derived class for which the vtable is currently being built.
882
  ThunksMapTy Thunks;
883
884
  /// AddThunk - Add a thunk for the given method.
885
  void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
886
887
  /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
888
  /// part of the vtable we're currently building.
889
  void ComputeThisAdjustments();
890
891
  typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
892
893
  /// PrimaryVirtualBases - All known virtual bases who are a primary base of
894
  /// some other base.
895
  VisitedVirtualBasesSetTy PrimaryVirtualBases;
896
897
  /// ComputeReturnAdjustment - Compute the return adjustment given a return
898
  /// adjustment base offset.
899
  ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
900
901
  /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
902
  /// the 'this' pointer from the base subobject to the derived subobject.
903
  BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
904
                                             BaseSubobject Derived) const;
905
906
  /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
907
  /// given virtual member function, its offset in the layout class and its
908
  /// final overrider.
909
  ThisAdjustment
910
  ComputeThisAdjustment(const CXXMethodDecl *MD,
911
                        CharUnits BaseOffsetInLayoutClass,
912
                        FinalOverriders::OverriderInfo Overrider);
913
914
  /// AddMethod - Add a single virtual member function to the vtable
915
  /// components vector.
916
  void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
917
918
  /// IsOverriderUsed - Returns whether the overrider will ever be used in this
919
  /// part of the vtable.
920
  ///
921
  /// Itanium C++ ABI 2.5.2:
922
  ///
923
  ///   struct A { virtual void f(); };
924
  ///   struct B : virtual public A { int i; };
925
  ///   struct C : virtual public A { int j; };
926
  ///   struct D : public B, public C {};
927
  ///
928
  ///   When B and C are declared, A is a primary base in each case, so although
929
  ///   vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
930
  ///   adjustment is required and no thunk is generated. However, inside D
931
  ///   objects, A is no longer a primary base of C, so if we allowed calls to
932
  ///   C::f() to use the copy of A's vtable in the C subobject, we would need
933
  ///   to adjust this from C* to B::A*, which would require a third-party
934
  ///   thunk. Since we require that a call to C::f() first convert to A*,
935
  ///   C-in-D's copy of A's vtable is never referenced, so this is not
936
  ///   necessary.
937
  bool IsOverriderUsed(const CXXMethodDecl *Overrider,
938
                       CharUnits BaseOffsetInLayoutClass,
939
                       const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
940
                       CharUnits FirstBaseOffsetInLayoutClass) const;
941
942
943
  /// AddMethods - Add the methods of this base subobject and all its
944
  /// primary bases to the vtable components vector.
945
  void AddMethods(BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
946
                  const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
947
                  CharUnits FirstBaseOffsetInLayoutClass,
948
                  PrimaryBasesSetVectorTy &PrimaryBases);
949
950
  // LayoutVTable - Layout the vtable for the given base class, including its
951
  // secondary vtables and any vtables for virtual bases.
952
  void LayoutVTable();
953
954
  /// LayoutPrimaryAndSecondaryVTables - Layout the primary vtable for the
955
  /// given base subobject, as well as all its secondary vtables.
956
  ///
957
  /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
958
  /// or a direct or indirect base of a virtual base.
959
  ///
960
  /// \param BaseIsVirtualInLayoutClass - Whether the base subobject is virtual
961
  /// in the layout class.
962
  void LayoutPrimaryAndSecondaryVTables(BaseSubobject Base,
963
                                        bool BaseIsMorallyVirtual,
964
                                        bool BaseIsVirtualInLayoutClass,
965
                                        CharUnits OffsetInLayoutClass);
966
967
  /// LayoutSecondaryVTables - Layout the secondary vtables for the given base
968
  /// subobject.
969
  ///
970
  /// \param BaseIsMorallyVirtual whether the base subobject is a virtual base
971
  /// or a direct or indirect base of a virtual base.
972
  void LayoutSecondaryVTables(BaseSubobject Base, bool BaseIsMorallyVirtual,
973
                              CharUnits OffsetInLayoutClass);
974
975
  /// DeterminePrimaryVirtualBases - Determine the primary virtual bases in this
976
  /// class hierarchy.
977
  void DeterminePrimaryVirtualBases(const CXXRecordDecl *RD,
978
                                    CharUnits OffsetInLayoutClass,
979
                                    VisitedVirtualBasesSetTy &VBases);
980
981
  /// LayoutVTablesForVirtualBases - Layout vtables for all virtual bases of the
982
  /// given base (excluding any primary bases).
983
  void LayoutVTablesForVirtualBases(const CXXRecordDecl *RD,
984
                                    VisitedVirtualBasesSetTy &VBases);
985
986
  /// isBuildingConstructionVTable - Return whether this vtable builder is
987
  /// building a construction vtable.
988
16.6k
  bool isBuildingConstructorVTable() const {
989
16.6k
    return MostDerivedClass != LayoutClass;
990
16.6k
  }
991
992
public:
993
  /// Component indices of the first component of each of the vtables in the
994
  /// vtable group.
995
  SmallVector<size_t, 4> VTableIndices;
996
997
  ItaniumVTableBuilder(ItaniumVTableContext &VTables,
998
                       const CXXRecordDecl *MostDerivedClass,
999
                       CharUnits MostDerivedClassOffset,
1000
                       bool MostDerivedClassIsVirtual,
1001
                       const CXXRecordDecl *LayoutClass)
1002
      : VTables(VTables), MostDerivedClass(MostDerivedClass),
1003
        MostDerivedClassOffset(MostDerivedClassOffset),
1004
        MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
1005
        LayoutClass(LayoutClass), Context(MostDerivedClass->getASTContext()),
1006
4.26k
        Overriders(MostDerivedClass, MostDerivedClassOffset, LayoutClass) {
1007
4.26k
    assert(!Context.getTargetInfo().getCXXABI().isMicrosoft());
1008
1009
4.26k
    LayoutVTable();
1010
1011
4.26k
    if (Context.getLangOpts().DumpVTableLayouts)
1012
230
      dumpLayout(llvm::outs());
1013
4.26k
  }
1014
1015
0
  uint64_t getNumThunks() const {
1016
0
    return Thunks.size();
1017
0
  }
1018
1019
3.95k
  ThunksMapTy::const_iterator thunks_begin() const {
1020
3.95k
    return Thunks.begin();
1021
3.95k
  }
1022
1023
3.95k
  ThunksMapTy::const_iterator thunks_end() const {
1024
3.95k
    return Thunks.end();
1025
3.95k
  }
1026
1027
232
  const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
1028
232
    return VBaseOffsetOffsets;
1029
232
  }
1030
1031
4.26k
  const AddressPointsMapTy &getAddressPoints() const {
1032
4.26k
    return AddressPoints;
1033
4.26k
  }
1034
1035
3.95k
  MethodVTableIndicesTy::const_iterator vtable_indices_begin() const {
1036
3.95k
    return MethodVTableIndices.begin();
1037
3.95k
  }
1038
1039
3.95k
  MethodVTableIndicesTy::const_iterator vtable_indices_end() const {
1040
3.95k
    return MethodVTableIndices.end();
1041
3.95k
  }
1042
1043
4.26k
  ArrayRef<VTableComponent> vtable_components() const { return Components; }
1044
1045
0
  AddressPointsMapTy::const_iterator address_points_begin() const {
1046
0
    return AddressPoints.begin();
1047
0
  }
1048
1049
0
  AddressPointsMapTy::const_iterator address_points_end() const {
1050
0
    return AddressPoints.end();
1051
0
  }
1052
1053
4.26k
  VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
1054
4.26k
    return VTableThunks.begin();
1055
4.26k
  }
1056
1057
4.26k
  VTableThunksMapTy::const_iterator vtable_thunks_end() const {
1058
4.26k
    return VTableThunks.end();
1059
4.26k
  }
1060
1061
  /// dumpLayout - Dump the vtable layout.
1062
  void dumpLayout(raw_ostream&);
1063
};
1064
1065
void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
1066
530
                                    const ThunkInfo &Thunk) {
1067
530
  assert(!isBuildingConstructorVTable() &&
1068
530
         "Can't add thunks for construction vtable");
1069
1070
530
  SmallVectorImpl<ThunkInfo> &ThunksVector = Thunks[MD];
1071
1072
  // Check if we have this thunk already.
1073
530
  if (llvm::find(ThunksVector, Thunk) != ThunksVector.end())
1074
64
    return;
1075
1076
466
  ThunksVector.push_back(Thunk);
1077
466
}
1078
1079
typedef llvm::SmallPtrSet<const CXXMethodDecl *, 8> OverriddenMethodsSetTy;
1080
1081
/// Visit all the methods overridden by the given method recursively,
1082
/// in a depth-first pre-order. The Visitor's visitor method returns a bool
1083
/// indicating whether to continue the recursion for the given overridden
1084
/// method (i.e. returning false stops the iteration).
1085
template <class VisitorTy>
1086
static void
1087
38.1k
visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1088
38.1k
  assert(VTableContextBase::hasVtableSlot(MD) && "Method is not virtual!");
1089
1090
12.7k
  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1091
12.7k
    if (!Visitor(OverriddenMD))
1092
124
      continue;
1093
12.6k
    visitAllOverriddenMethods(OverriddenMD, Visitor);
1094
12.6k
  }
1095
38.1k
}
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
1087
32.8k
visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1088
32.8k
  assert(VTableContextBase::hasVtableSlot(MD) && "Method is not virtual!");
1089
1090
10.0k
  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1091
10.0k
    if (!Visitor(OverriddenMD))
1092
58
      continue;
1093
10.0k
    visitAllOverriddenMethods(OverriddenMD, Visitor);
1094
10.0k
  }
1095
32.8k
}
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
1087
5.33k
visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) {
1088
5.33k
  assert(VTableContextBase::hasVtableSlot(MD) && "Method is not virtual!");
1089
1090
2.65k
  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1091
2.65k
    if (!Visitor(OverriddenMD))
1092
66
      continue;
1093
2.59k
    visitAllOverriddenMethods(OverriddenMD, Visitor);
1094
2.59k
  }
1095
5.33k
}
1096
1097
/// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
1098
/// the overridden methods that the function decl overrides.
1099
static void
1100
ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
1101
22.8k
                            OverriddenMethodsSetTy& OverriddenMethods) {
1102
10.0k
  auto OverriddenMethodsCollector = [&](const CXXMethodDecl *MD) {
1103
    // Don't recurse on this method if we've already collected it.
1104
10.0k
    return OverriddenMethods.insert(MD).second;
1105
10.0k
  };
1106
22.8k
  visitAllOverriddenMethods(MD, OverriddenMethodsCollector);
1107
22.8k
}
1108
1109
4.90k
void ItaniumVTableBuilder::ComputeThisAdjustments() {
1110
  // Now go through the method info map and see if any of the methods need
1111
  // 'this' pointer adjustments.
1112
13.4k
  for (const auto &MI : MethodInfoMap) {
1113
13.4k
    const CXXMethodDecl *MD = MI.first;
1114
13.4k
    const MethodInfo &MethodInfo = MI.second;
1115
1116
    // Ignore adjustments for unused function pointers.
1117
13.4k
    uint64_t VTableIndex = MethodInfo.VTableIndex;
1118
13.4k
    if (Components[VTableIndex].getKind() ==
1119
13.4k
        VTableComponent::CK_UnusedFunctionPointer)
1120
43
      continue;
1121
1122
    // Get the final overrider for this method.
1123
13.4k
    FinalOverriders::OverriderInfo Overrider =
1124
13.4k
      Overriders.getOverrider(MD, MethodInfo.BaseOffset);
1125
1126
    // Check if we need an adjustment at all.
1127
13.4k
    if (MethodInfo.BaseOffsetInLayoutClass == Overrider.Offset) {
1128
      // When a return thunk is needed by a derived class that overrides a
1129
      // virtual base, gcc uses a virtual 'this' adjustment as well.
1130
      // While the thunk itself might be needed by vtables in subclasses or
1131
      // in construction vtables, there doesn't seem to be a reason for using
1132
      // the thunk in this vtable. Still, we do so to match gcc.
1133
12.9k
      if (VTableThunks.lookup(VTableIndex).Return.isEmpty())
1134
12.9k
        continue;
1135
490
    }
1136
1137
490
    ThisAdjustment ThisAdjustment =
1138
490
      ComputeThisAdjustment(MD, MethodInfo.BaseOffsetInLayoutClass, Overrider);
1139
1140
490
    if (ThisAdjustment.isEmpty())
1141
14
      continue;
1142
1143
    // Add it.
1144
476
    VTableThunks[VTableIndex].This = ThisAdjustment;
1145
1146
476
    if (isa<CXXDestructorDecl>(MD)) {
1147
      // Add an adjustment for the deleting destructor as well.
1148
104
      VTableThunks[VTableIndex + 1].This = ThisAdjustment;
1149
104
    }
1150
476
  }
1151
1152
  /// Clear the method info map.
1153
4.90k
  MethodInfoMap.clear();
1154
1155
4.90k
  if (isBuildingConstructorVTable()) {
1156
    // We don't need to store thunk information for construction vtables.
1157
591
    return;
1158
591
  }
1159
1160
4.31k
  for (const auto &TI : VTableThunks) {
1161
530
    const VTableComponent &Component = Components[TI.first];
1162
530
    const ThunkInfo &Thunk = TI.second;
1163
530
    const CXXMethodDecl *MD;
1164
1165
530
    switch (Component.getKind()) {
1166
0
    default:
1167
0
      llvm_unreachable("Unexpected vtable component kind!");
1168
340
    case VTableComponent::CK_FunctionPointer:
1169
340
      MD = Component.getFunctionDecl();
1170
340
      break;
1171
95
    case VTableComponent::CK_CompleteDtorPointer:
1172
95
      MD = Component.getDestructorDecl();
1173
95
      break;
1174
95
    case VTableComponent::CK_DeletingDtorPointer:
1175
      // We've already added the thunk when we saw the complete dtor pointer.
1176
95
      continue;
1177
435
    }
1178
1179
435
    if (MD->getParent() == MostDerivedClass)
1180
415
      AddThunk(MD, Thunk);
1181
435
  }
1182
4.31k
}
1183
1184
ReturnAdjustment
1185
13.5k
ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) {
1186
13.5k
  ReturnAdjustment Adjustment;
1187
1188
13.5k
  if (!Offset.isEmpty()) {
1189
31
    if (Offset.VirtualBase) {
1190
      // Get the virtual base offset offset.
1191
26
      if (Offset.DerivedClass == MostDerivedClass) {
1192
        // We can get the offset offset directly from our map.
1193
18
        Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1194
18
          VBaseOffsetOffsets.lookup(Offset.VirtualBase).getQuantity();
1195
8
      } else {
1196
8
        Adjustment.Virtual.Itanium.VBaseOffsetOffset =
1197
8
          VTables.getVirtualBaseOffsetOffset(Offset.DerivedClass,
1198
8
                                             Offset.VirtualBase).getQuantity();
1199
8
      }
1200
26
    }
1201
1202
31
    Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1203
31
  }
1204
1205
13.5k
  return Adjustment;
1206
13.5k
}
1207
1208
BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
1209
7.01k
    BaseSubobject Base, BaseSubobject Derived) const {
1210
7.01k
  const CXXRecordDecl *BaseRD = Base.getBase();
1211
7.01k
  const CXXRecordDecl *DerivedRD = Derived.getBase();
1212
1213
7.01k
  CXXBasePaths Paths(/*FindAmbiguities=*/true,
1214
7.01k
                     /*RecordPaths=*/true, /*DetectVirtual=*/true);
1215
1216
7.01k
  if (!DerivedRD->isDerivedFrom(BaseRD, Paths))
1217
0
    llvm_unreachable("Class must be derived from the passed in base class!");
1218
1219
  // We have to go through all the paths, and see which one leads us to the
1220
  // right base subobject.
1221
7.06k
  
for (const CXXBasePath &Path : Paths)7.01k
{
1222
7.06k
    BaseOffset Offset = ComputeBaseOffset(Context, DerivedRD, Path);
1223
1224
7.06k
    CharUnits OffsetToBaseSubobject = Offset.NonVirtualOffset;
1225
1226
7.06k
    if (Offset.VirtualBase) {
1227
      // If we have a virtual base class, the non-virtual offset is relative
1228
      // to the virtual base class offset.
1229
307
      const ASTRecordLayout &LayoutClassLayout =
1230
307
        Context.getASTRecordLayout(LayoutClass);
1231
1232
      /// Get the virtual base offset, relative to the most derived class
1233
      /// layout.
1234
307
      OffsetToBaseSubobject +=
1235
307
        LayoutClassLayout.getVBaseClassOffset(Offset.VirtualBase);
1236
6.75k
    } else {
1237
      // Otherwise, the non-virtual offset is relative to the derived class
1238
      // offset.
1239
6.75k
      OffsetToBaseSubobject += Derived.getBaseOffset();
1240
6.75k
    }
1241
1242
    // Check if this path gives us the right base subobject.
1243
7.06k
    if (OffsetToBaseSubobject == Base.getBaseOffset()) {
1244
      // Since we're going from the base class _to_ the derived class, we'll
1245
      // invert the non-virtual offset here.
1246
7.01k
      Offset.NonVirtualOffset = -Offset.NonVirtualOffset;
1247
7.01k
      return Offset;
1248
7.01k
    }
1249
7.06k
  }
1250
1251
7
  return BaseOffset();
1252
7.01k
}
1253
1254
ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
1255
    const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
1256
7.02k
    FinalOverriders::OverriderInfo Overrider) {
1257
  // Ignore adjustments for pure virtual member functions.
1258
7.02k
  if (Overrider.Method->isPure())
1259
2
    return ThisAdjustment();
1260
1261
7.01k
  BaseSubobject OverriddenBaseSubobject(MD->getParent(),
1262
7.01k
                                        BaseOffsetInLayoutClass);
1263
1264
7.01k
  BaseSubobject OverriderBaseSubobject(Overrider.Method->getParent(),
1265
7.01k
                                       Overrider.Offset);
1266
1267
  // Compute the adjustment offset.
1268
7.01k
  BaseOffset Offset = ComputeThisAdjustmentBaseOffset(OverriddenBaseSubobject,
1269
7.01k
                                                      OverriderBaseSubobject);
1270
7.01k
  if (Offset.isEmpty())
1271
6.41k
    return ThisAdjustment();
1272
1273
602
  ThisAdjustment Adjustment;
1274
1275
602
  if (Offset.VirtualBase) {
1276
    // Get the vcall offset map for this virtual base.
1277
283
    VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Offset.VirtualBase];
1278
1279
283
    if (VCallOffsets.empty()) {
1280
      // We don't have vcall offsets for this virtual base, go ahead and
1281
      // build them.
1282
89
      VCallAndVBaseOffsetBuilder Builder(
1283
89
          VTables, MostDerivedClass, MostDerivedClass,
1284
89
          /*Overriders=*/nullptr,
1285
89
          BaseSubobject(Offset.VirtualBase, CharUnits::Zero()),
1286
89
          /*BaseIsVirtual=*/true,
1287
          /*OffsetInLayoutClass=*/
1288
89
          CharUnits::Zero());
1289
1290
89
      VCallOffsets = Builder.getVCallOffsets();
1291
89
    }
1292
1293
283
    Adjustment.Virtual.Itanium.VCallOffsetOffset =
1294
283
      VCallOffsets.getVCallOffsetOffset(MD).getQuantity();
1295
283
  }
1296
1297
  // Set the non-virtual part of the adjustment.
1298
602
  Adjustment.NonVirtual = Offset.NonVirtualOffset.getQuantity();
1299
1300
602
  return Adjustment;
1301
602
}
1302
1303
void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
1304
13.4k
                                     ReturnAdjustment ReturnAdjustment) {
1305
13.4k
  if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1306
2.75k
    assert(ReturnAdjustment.isEmpty() &&
1307
2.75k
           "Destructor can't have return adjustment!");
1308
1309
    // Add both the complete destructor and the deleting destructor.
1310
2.75k
    Components.push_back(VTableComponent::MakeCompleteDtor(DD));
1311
2.75k
    Components.push_back(VTableComponent::MakeDeletingDtor(DD));
1312
10.6k
  } else {
1313
    // Add the return adjustment if necessary.
1314
10.6k
    if (!ReturnAdjustment.isEmpty())
1315
26
      VTableThunks[Components.size()].Return = ReturnAdjustment;
1316
1317
    // Add the function.
1318
10.6k
    Components.push_back(VTableComponent::MakeFunction(MD));
1319
10.6k
  }
1320
13.4k
}
1321
1322
/// OverridesIndirectMethodInBase - Return whether the given member function
1323
/// overrides any methods in the set of given bases.
1324
/// Unlike OverridesMethodInBase, this checks "overriders of overriders".
1325
/// For example, if we have:
1326
///
1327
/// struct A { virtual void f(); }
1328
/// struct B : A { virtual void f(); }
1329
/// struct C : B { virtual void f(); }
1330
///
1331
/// OverridesIndirectMethodInBase will return true if given C::f as the method
1332
/// and { A } as the set of bases.
1333
static bool OverridesIndirectMethodInBases(
1334
    const CXXMethodDecl *MD,
1335
88
    ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) {
1336
88
  if (Bases.count(MD->getParent()))
1337
9
    return true;
1338
1339
79
  for (const CXXMethodDecl *OverriddenMD : MD->overridden_methods()) {
1340
    // Check "indirect overriders".
1341
36
    if (OverridesIndirectMethodInBases(OverriddenMD, Bases))
1342
10
      return true;
1343
36
  }
1344
1345
69
  return false;
1346
79
}
1347
1348
bool ItaniumVTableBuilder::IsOverriderUsed(
1349
    const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
1350
    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1351
13.4k
    CharUnits FirstBaseOffsetInLayoutClass) const {
1352
  // If the base and the first base in the primary base chain have the same
1353
  // offsets, then this overrider will be used.
1354
13.4k
  if (BaseOffsetInLayoutClass == FirstBaseOffsetInLayoutClass)
1355
13.4k
   return true;
1356
1357
  // We know now that Base (or a direct or indirect base of it) is a primary
1358
  // base in part of the class hierarchy, but not a primary base in the most
1359
  // derived class.
1360
1361
  // If the overrider is the first base in the primary base chain, we know
1362
  // that the overrider will be used.
1363
63
  if (Overrider->getParent() == FirstBaseInPrimaryBaseChain)
1364
11
    return true;
1365
1366
52
  ItaniumVTableBuilder::PrimaryBasesSetVectorTy PrimaryBases;
1367
1368
52
  const CXXRecordDecl *RD = FirstBaseInPrimaryBaseChain;
1369
52
  PrimaryBases.insert(RD);
1370
1371
  // Now traverse the base chain, starting with the first base, until we find
1372
  // the base that is no longer a primary base.
1373
60
  while (true) {
1374
60
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1375
60
    const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1376
1377
60
    if (!PrimaryBase)
1378
0
      break;
1379
1380
60
    if (Layout.isPrimaryBaseVirtual()) {
1381
52
      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1382
52
             "Primary base should always be at offset 0!");
1383
1384
52
      const ASTRecordLayout &LayoutClassLayout =
1385
52
        Context.getASTRecordLayout(LayoutClass);
1386
1387
      // Now check if this is the primary base that is not a primary base in the
1388
      // most derived class.
1389
52
      if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1390
52
          FirstBaseOffsetInLayoutClass) {
1391
        // We found it, stop walking the chain.
1392
52
        break;
1393
52
      }
1394
8
    } else {
1395
8
      assert(Layout.getBaseClassOffset(PrimaryBase).isZero() &&
1396
8
             "Primary base should always be at offset 0!");
1397
8
    }
1398
1399
8
    if (!PrimaryBases.insert(PrimaryBase))
1400
0
      llvm_unreachable("Found a duplicate primary base!");
1401
1402
8
    RD = PrimaryBase;
1403
8
  }
1404
1405
  // If the final overrider is an override of one of the primary bases,
1406
  // then we know that it will be used.
1407
52
  return OverridesIndirectMethodInBases(Overrider, PrimaryBases);
1408
52
}
1409
1410
typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> BasesSetVectorTy;
1411
1412
/// FindNearestOverriddenMethod - Given a method, returns the overridden method
1413
/// from the nearest base. Returns null if no method was found.
1414
/// The Bases are expected to be sorted in a base-to-derived order.
1415
static const CXXMethodDecl *
1416
FindNearestOverriddenMethod(const CXXMethodDecl *MD,
1417
22.8k
                            BasesSetVectorTy &Bases) {
1418
22.8k
  OverriddenMethodsSetTy OverriddenMethods;
1419
22.8k
  ComputeAllOverriddenMethods(MD, OverriddenMethods);
1420
1421
22.8k
  for (const CXXRecordDecl *PrimaryBase :
1422
16.3k
       llvm::make_range(Bases.rbegin(), Bases.rend())) {
1423
    // Now check the overridden methods.
1424
8.44k
    for (const CXXMethodDecl *OverriddenMD : OverriddenMethods) {
1425
      // We found our overridden method.
1426
8.44k
      if (OverriddenMD->getParent() == PrimaryBase)
1427
7.37k
        return OverriddenMD;
1428
8.44k
    }
1429
16.3k
  }
1430
1431
15.4k
  return nullptr;
1432
22.8k
}
1433
1434
void ItaniumVTableBuilder::AddMethods(
1435
    BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
1436
    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
1437
    CharUnits FirstBaseOffsetInLayoutClass,
1438
8.74k
    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.74k
  const CXXRecordDecl *RD = Base.getBase();
1449
8.74k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1450
1451
8.74k
  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1452
3.83k
    CharUnits PrimaryBaseOffset;
1453
3.83k
    CharUnits PrimaryBaseOffsetInLayoutClass;
1454
3.83k
    if (Layout.isPrimaryBaseVirtual()) {
1455
293
      assert(Layout.getVBaseClassOffset(PrimaryBase).isZero() &&
1456
293
             "Primary vbase should have a zero offset!");
1457
1458
293
      const ASTRecordLayout &MostDerivedClassLayout =
1459
293
        Context.getASTRecordLayout(MostDerivedClass);
1460
1461
293
      PrimaryBaseOffset =
1462
293
        MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
1463
1464
293
      const ASTRecordLayout &LayoutClassLayout =
1465
293
        Context.getASTRecordLayout(LayoutClass);
1466
1467
293
      PrimaryBaseOffsetInLayoutClass =
1468
293
        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
3.54k
      PrimaryBaseOffset = Base.getBaseOffset();
1474
3.54k
      PrimaryBaseOffsetInLayoutClass = BaseOffsetInLayoutClass;
1475
3.54k
    }
1476
1477
3.83k
    AddMethods(BaseSubobject(PrimaryBase, PrimaryBaseOffset),
1478
3.83k
               PrimaryBaseOffsetInLayoutClass, FirstBaseInPrimaryBaseChain,
1479
3.83k
               FirstBaseOffsetInLayoutClass, PrimaryBases);
1480
1481
3.83k
    if (!PrimaryBases.insert(PrimaryBase))
1482
0
      llvm_unreachable("Found a duplicate primary base!");
1483
3.83k
  }
1484
1485
8.74k
  typedef llvm::SmallVector<const CXXMethodDecl *, 8> NewVirtualFunctionsTy;
1486
8.74k
  NewVirtualFunctionsTy NewVirtualFunctions;
1487
1488
8.74k
  llvm::SmallVector<const CXXMethodDecl*, 4> NewImplicitVirtualFunctions;
1489
1490
  // Now go through all virtual member functions and add them.
1491
65.4k
  for (const auto *MD : RD->methods()) {
1492
65.4k
    if (!ItaniumVTableContext::hasVtableSlot(MD))
1493
45.4k
      continue;
1494
20.0k
    MD = MD->getCanonicalDecl();
1495
1496
    // Get the final overrider.
1497
20.0k
    FinalOverriders::OverriderInfo Overrider =
1498
20.0k
      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.0k
    if (const CXXMethodDecl *OverriddenMD =
1504
6.60k
          FindNearestOverriddenMethod(MD, PrimaryBases)) {
1505
6.60k
      if (ComputeReturnAdjustmentBaseOffset(Context, MD,
1506
6.58k
                                            OverriddenMD).isEmpty()) {
1507
        // Replace the method info of the overridden method with our own
1508
        // method.
1509
6.58k
        assert(MethodInfoMap.count(OverriddenMD) &&
1510
6.58k
               "Did not find the overridden method!");
1511
6.58k
        MethodInfo &OverriddenMethodInfo = MethodInfoMap[OverriddenMD];
1512
1513
6.58k
        MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1514
6.58k
                              OverriddenMethodInfo.VTableIndex);
1515
1516
6.58k
        assert(!MethodInfoMap.count(MD) &&
1517
6.58k
               "Should not have method info for this method yet!");
1518
1519
6.58k
        MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1520
6.58k
        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.58k
        if (!isBuildingConstructorVTable() && 
OverriddenMD != MD6.53k
) {
1527
          // Compute the this adjustment.
1528
6.53k
          ThisAdjustment ThisAdjustment =
1529
6.53k
            ComputeThisAdjustment(OverriddenMD, BaseOffsetInLayoutClass,
1530
6.53k
                                  Overrider);
1531
1532
6.53k
          if (ThisAdjustment.Virtual.Itanium.VCallOffsetOffset &&
1533
115
              Overrider.Method->getParent() == MostDerivedClass) {
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
115
            BaseOffset ReturnAdjustmentOffset =
1539
115
              ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
1540
115
            ReturnAdjustment ReturnAdjustment =
1541
115
              ComputeReturnAdjustment(ReturnAdjustmentOffset);
1542
1543
            // This is a virtual thunk for the most derived class, add it.
1544
115
            AddThunk(Overrider.Method,
1545
115
                     ThunkInfo(ThisAdjustment, ReturnAdjustment));
1546
115
          }
1547
6.53k
        }
1548
1549
6.58k
        continue;
1550
6.58k
      }
1551
13.4k
    }
1552
1553
13.4k
    if (MD->isImplicit())
1554
37
      NewImplicitVirtualFunctions.push_back(MD);
1555
13.4k
    else
1556
13.4k
      NewVirtualFunctions.push_back(MD);
1557
13.4k
  }
1558
1559
8.74k
  std::stable_sort(
1560
8.74k
      NewImplicitVirtualFunctions.begin(), NewImplicitVirtualFunctions.end(),
1561
5
      [](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
1
        return false;
1574
1
      });
1575
8.74k
  NewVirtualFunctions.append(NewImplicitVirtualFunctions.begin(),
1576
8.74k
                             NewImplicitVirtualFunctions.end());
1577
1578
13.4k
  for (const CXXMethodDecl *MD : NewVirtualFunctions) {
1579
    // Get the final overrider.
1580
13.4k
    FinalOverriders::OverriderInfo Overrider =
1581
13.4k
      Overriders.getOverrider(MD, Base.getBaseOffset());
1582
1583
    // Insert the method info for this method.
1584
13.4k
    MethodInfo MethodInfo(Base.getBaseOffset(), BaseOffsetInLayoutClass,
1585
13.4k
                          Components.size());
1586
1587
13.4k
    assert(!MethodInfoMap.count(MD) &&
1588
13.4k
           "Should not have method info for this method yet!");
1589
13.4k
    MethodInfoMap.insert(std::make_pair(MD, MethodInfo));
1590
1591
    // Check if this overrider is going to be used.
1592
13.4k
    const CXXMethodDecl *OverriderMD = Overrider.Method;
1593
13.4k
    if (!IsOverriderUsed(OverriderMD, BaseOffsetInLayoutClass,
1594
13.4k
                         FirstBaseInPrimaryBaseChain,
1595
43
                         FirstBaseOffsetInLayoutClass)) {
1596
43
      Components.push_back(VTableComponent::MakeUnusedFunction(OverriderMD));
1597
43
      continue;
1598
43
    }
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.4k
    BaseOffset ReturnAdjustmentOffset;
1603
13.4k
    if (!OverriderMD->isPure()) {
1604
12.8k
      ReturnAdjustmentOffset =
1605
12.8k
        ComputeReturnAdjustmentBaseOffset(Context, OverriderMD, MD);
1606
12.8k
    }
1607
1608
13.4k
    ReturnAdjustment ReturnAdjustment =
1609
13.4k
      ComputeReturnAdjustment(ReturnAdjustmentOffset);
1610
1611
13.4k
    AddMethod(Overrider.Method, ReturnAdjustment);
1612
13.4k
  }
1613
8.74k
}
1614
1615
4.26k
void ItaniumVTableBuilder::LayoutVTable() {
1616
4.26k
  LayoutPrimaryAndSecondaryVTables(BaseSubobject(MostDerivedClass,
1617
4.26k
                                                 CharUnits::Zero()),
1618
4.26k
                                   /*BaseIsMorallyVirtual=*/false,
1619
4.26k
                                   MostDerivedClassIsVirtual,
1620
4.26k
                                   MostDerivedClassOffset);
1621
1622
4.26k
  VisitedVirtualBasesSetTy VBases;
1623
1624
  // Determine the primary virtual bases.
1625
4.26k
  DeterminePrimaryVirtualBases(MostDerivedClass, MostDerivedClassOffset,
1626
4.26k
                               VBases);
1627
4.26k
  VBases.clear();
1628
1629
4.26k
  LayoutVTablesForVirtualBases(MostDerivedClass, VBases);
1630
1631
  // -fapple-kext adds an extra entry at end of vtbl.
1632
4.26k
  bool IsAppleKext = Context.getLangOpts().AppleKext;
1633
4.26k
  if (IsAppleKext)
1634
14
    Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));
1635
4.26k
}
1636
1637
void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
1638
    BaseSubobject Base, bool BaseIsMorallyVirtual,
1639
4.90k
    bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
1640
4.90k
  assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
1641
1642
4.90k
  unsigned VTableIndex = Components.size();
1643
4.90k
  VTableIndices.push_back(VTableIndex);
1644
1645
  // Add vcall and vbase offsets for this vtable.
1646
4.90k
  VCallAndVBaseOffsetBuilder Builder(
1647
4.90k
      VTables, MostDerivedClass, LayoutClass, &Overriders, Base,
1648
4.90k
      BaseIsVirtualInLayoutClass, OffsetInLayoutClass);
1649
4.90k
  Components.append(Builder.components_begin(), Builder.components_end());
1650
1651
  // Check if we need to add these vcall offsets.
1652
4.90k
  if (BaseIsVirtualInLayoutClass && 
!Builder.getVCallOffsets().empty()420
) {
1653
277
    VCallOffsetMap &VCallOffsets = VCallOffsetsForVBases[Base.getBase()];
1654
1655
277
    if (VCallOffsets.empty())
1656
277
      VCallOffsets = Builder.getVCallOffsets();
1657
277
  }
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
4.90k
  if (Base.getBase() == MostDerivedClass)
1662
4.26k
    VBaseOffsetOffsets = Builder.getVBaseOffsetOffsets();
1663
1664
  // Add the offset to top.
1665
4.90k
  CharUnits OffsetToTop = MostDerivedClassOffset - OffsetInLayoutClass;
1666
4.90k
  Components.push_back(VTableComponent::MakeOffsetToTop(OffsetToTop));
1667
1668
  // Next, add the RTTI.
1669
4.90k
  Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
1670
1671
4.90k
  uint64_t AddressPoint = Components.size();
1672
1673
  // Now go through all virtual member functions and add them.
1674
4.90k
  PrimaryBasesSetVectorTy PrimaryBases;
1675
4.90k
  AddMethods(Base, OffsetInLayoutClass,
1676
4.90k
             Base.getBase(), OffsetInLayoutClass,
1677
4.90k
             PrimaryBases);
1678
1679
4.90k
  const CXXRecordDecl *RD = Base.getBase();
1680
4.90k
  if (RD == MostDerivedClass) {
1681
4.26k
    assert(MethodVTableIndices.empty());
1682
12.6k
    for (const auto &I : MethodInfoMap) {
1683
12.6k
      const CXXMethodDecl *MD = I.first;
1684
12.6k
      const MethodInfo &MI = I.second;
1685
12.6k
      if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
1686
2.65k
        MethodVTableIndices[GlobalDecl(DD, Dtor_Complete)]
1687
2.65k
            = MI.VTableIndex - AddressPoint;
1688
2.65k
        MethodVTableIndices[GlobalDecl(DD, Dtor_Deleting)]
1689
2.65k
            = MI.VTableIndex + 1 - AddressPoint;
1690
10.0k
      } else {
1691
10.0k
        MethodVTableIndices[MD] = MI.VTableIndex - AddressPoint;
1692
10.0k
      }
1693
12.6k
    }
1694
4.26k
  }
1695
1696
  // Compute 'this' pointer adjustments.
1697
4.90k
  ComputeThisAdjustments();
1698
1699
  // Add all address points.
1700
8.68k
  while (true) {
1701
8.68k
    AddressPoints.insert(
1702
8.68k
        std::make_pair(BaseSubobject(RD, OffsetInLayoutClass),
1703
8.68k
                       VTableLayout::AddressPointLocation{
1704
8.68k
                           unsigned(VTableIndices.size() - 1),
1705
8.68k
                           unsigned(AddressPoint - VTableIndex)}));
1706
1707
8.68k
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1708
8.68k
    const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1709
1710
8.68k
    if (!PrimaryBase)
1711
4.84k
      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
287
      const ASTRecordLayout &LayoutClassLayout =
1717
287
        Context.getASTRecordLayout(LayoutClass);
1718
1719
287
      if (LayoutClassLayout.getVBaseClassOffset(PrimaryBase) !=
1720
58
          OffsetInLayoutClass) {
1721
        // We don't want to add this class (or any of its primary bases).
1722
58
        break;
1723
58
      }
1724
3.77k
    }
1725
1726
3.77k
    RD = PrimaryBase;
1727
3.77k
  }
1728
1729
  // Layout secondary vtables.
1730
4.90k
  LayoutSecondaryVTables(Base, BaseIsMorallyVirtual, OffsetInLayoutClass);
1731
4.90k
}
1732
1733
void
1734
ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
1735
                                             bool BaseIsMorallyVirtual,
1736
8.42k
                                             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.42k
  const CXXRecordDecl *RD = Base.getBase();
1743
8.42k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1744
8.42k
  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
1745
1746
5.71k
  for (const auto &B : RD->bases()) {
1747
    // Ignore virtual bases, we'll emit them later.
1748
5.71k
    if (B.isVirtual())
1749
1.05k
      continue;
1750
1751
4.66k
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1752
1753
    // Ignore bases that don't have a vtable.
1754
4.66k
    if (!BaseDecl->isDynamicClass())
1755
816
      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
195
      if (!BaseIsMorallyVirtual && 
!BaseDecl->getNumVBases()100
)
1764
22
        continue;
1765
3.82k
    }
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.52k
      LayoutSecondaryVTables(BaseSubobject(BaseDecl, BaseOffset),
1778
3.52k
                             BaseIsMorallyVirtual, BaseOffsetInLayoutClass);
1779
3.52k
      continue;
1780
3.52k
    }
1781
1782
    // Layout the primary vtable (and any secondary vtables) for this base.
1783
303
    LayoutPrimaryAndSecondaryVTables(
1784
303
      BaseSubobject(BaseDecl, BaseOffset),
1785
303
      BaseIsMorallyVirtual,
1786
303
      /*BaseIsVirtualInLayoutClass=*/false,
1787
303
      BaseOffsetInLayoutClass);
1788
303
  }
1789
8.42k
}
1790
1791
void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
1792
    const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
1793
9.82k
    VisitedVirtualBasesSetTy &VBases) {
1794
9.82k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
1795
1796
  // Check if this base has a primary base.
1797
9.82k
  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
1798
1799
    // Check if it's virtual.
1800
3.83k
    if (Layout.isPrimaryBaseVirtual()) {
1801
287
      bool IsPrimaryVirtualBase = true;
1802
1803
287
      if (isBuildingConstructorVTable()) {
1804
        // Check if the base is actually a primary base in the class we use for
1805
        // layout.
1806
133
        const ASTRecordLayout &LayoutClassLayout =
1807
133
          Context.getASTRecordLayout(LayoutClass);
1808
1809
133
        CharUnits PrimaryBaseOffsetInLayoutClass =
1810
133
          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
133
        if (PrimaryBaseOffsetInLayoutClass != OffsetInLayoutClass)
1815
37
          IsPrimaryVirtualBase = false;
1816
133
      }
1817
1818
287
      if (IsPrimaryVirtualBase)
1819
250
        PrimaryVirtualBases.insert(PrimaryBase);
1820
287
    }
1821
3.83k
  }
1822
1823
  // Traverse bases, looking for more primary virtual bases.
1824
5.83k
  for (const auto &B : RD->bases()) {
1825
5.83k
    const CXXRecordDecl *BaseDecl = B.getType()->getAsCXXRecordDecl();
1826
1827
5.83k
    CharUnits BaseOffsetInLayoutClass;
1828
1829
5.83k
    if (B.isVirtual()) {
1830
1.09k
      if (!VBases.insert(BaseDecl).second)
1831
273
        continue;
1832
1833
818
      const ASTRecordLayout &LayoutClassLayout =
1834
818
        Context.getASTRecordLayout(LayoutClass);
1835
1836
818
      BaseOffsetInLayoutClass =
1837
818
        LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1838
4.74k
    } else {
1839
4.74k
      BaseOffsetInLayoutClass =
1840
4.74k
        OffsetInLayoutClass + Layout.getBaseClassOffset(BaseDecl);
1841
4.74k
    }
1842
1843
5.56k
    DeterminePrimaryVirtualBases(BaseDecl, BaseOffsetInLayoutClass, VBases);
1844
5.56k
  }
1845
9.82k
}
1846
1847
void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
1848
5.16k
    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
4.82k
  for (const auto &B : RD->bases()) {
1854
4.82k
    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.82k
    if (B.isVirtual() && 
BaseDecl->isDynamicClass()1.54k
&&
1859
926
        !PrimaryVirtualBases.count(BaseDecl) &&
1860
663
        VBases.insert(BaseDecl).second) {
1861
341
      const ASTRecordLayout &MostDerivedClassLayout =
1862
341
        Context.getASTRecordLayout(MostDerivedClass);
1863
341
      CharUnits BaseOffset =
1864
341
        MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
1865
1866
341
      const ASTRecordLayout &LayoutClassLayout =
1867
341
        Context.getASTRecordLayout(LayoutClass);
1868
341
      CharUnits BaseOffsetInLayoutClass =
1869
341
        LayoutClassLayout.getVBaseClassOffset(BaseDecl);
1870
1871
341
      LayoutPrimaryAndSecondaryVTables(
1872
341
        BaseSubobject(BaseDecl, BaseOffset),
1873
341
        /*BaseIsMorallyVirtual=*/true,
1874
341
        /*BaseIsVirtualInLayoutClass=*/true,
1875
341
        BaseOffsetInLayoutClass);
1876
341
    }
1877
1878
    // We only need to check the base for virtual base vtables if it actually
1879
    // has virtual bases.
1880
4.82k
    if (BaseDecl->getNumVBases())
1881
898
      LayoutVTablesForVirtualBases(BaseDecl, VBases);
1882
4.82k
  }
1883
5.16k
}
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
58
  } 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
10
    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
10
    }
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
234
      } 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
535
          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
20
    Out << (ClassNamesAndOffsets.size() == 1 ? 
" entry"16
: " entries") << ").\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
11
      llvm::sort(ThunksVector, [](const ThunkInfo &LHS, const ThunkInfo &RHS) {
2123
11
        assert(LHS.Method == nullptr && RHS.Method == nullptr);
2124
11
        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
21
      Out << (ThunksVector.size() == 1 ? " entry" : 
" 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
3
      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
82
      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.52k
                        unsigned numVTables) {
2214
5.52k
  VTableLayout::AddressPointsIndexMapTy indexMap(numVTables);
2215
2216
14.2k
  for (auto it = addressPoints.begin(); it != addressPoints.end(); 
++it8.68k
) {
2217
8.68k
    const auto &addressPointLoc = it->second;
2218
8.68k
    unsigned vtableIndex = addressPointLoc.VTableIndex;
2219
8.68k
    unsigned addressPoint = addressPointLoc.AddressPointIndex;
2220
8.68k
    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
4.90k
    } else {
2227
4.90k
      indexMap[vtableIndex] = addressPoint;
2228
4.90k
    }
2229
8.68k
  }
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.52k
  return indexMap;
2236
5.52k
}
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.52k
                                        AddressPoints, VTableIndices.size())) {
2245
5.52k
  if (VTableIndices.size() <= 1)
2246
5.52k
    assert(VTableIndices.size() == 1 && VTableIndices[0] == 0);
2247
5.52k
  else
2248
479
    this->VTableIndices = OwningArrayRef<size_t>(VTableIndices);
2249
2250
5.52k
  llvm::sort(this->VTableThunks, [](const VTableLayout::VTableThunkTy &LHS,
2251
663
                                    const VTableLayout::VTableThunkTy &RHS) {
2252
663
    assert((LHS.first != RHS.first || LHS.second == RHS.second) &&
2253
663
           "Different thunks should have unique indices!");
2254
663
    return LHS.first < RHS.first;
2255
663
  });
2256
5.52k
}
2257
2258
4.13k
VTableLayout::~VTableLayout() { }
2259
2260
133k
bool VTableContextBase::hasVtableSlot(const CXXMethodDecl *MD) {
2261
133k
  return MD->isVirtual() && 
!MD->isConsteval()68.3k
;
2262
133k
}
2263
2264
ItaniumVTableContext::ItaniumVTableContext(
2265
    ASTContext &Context, VTableComponentLayout ComponentLayout)
2266
29.0k
    : VTableContextBase(/*MS=*/false), ComponentLayout(ComponentLayout) {}
2267
2268
25.2k
ItaniumVTableContext::~ItaniumVTableContext() {}
2269
2270
7.48k
uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) {
2271
7.48k
  GD = GD.getCanonicalDecl();
2272
7.48k
  MethodVTableIndicesTy::iterator I = MethodVTableIndices.find(GD);
2273
7.48k
  if (I != MethodVTableIndices.end())
2274
5.32k
    return I->second;
2275
2276
2.15k
  const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
2277
2278
2.15k
  computeVTableRelatedInformation(RD);
2279
2280
2.15k
  I = MethodVTableIndices.find(GD);
2281
2.15k
  assert(I != MethodVTableIndices.end() && "Did not find index!");
2282
2.15k
  return I->second;
2283
2.15k
}
2284
2285
CharUnits
2286
ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
2287
873
                                                 const CXXRecordDecl *VBase) {
2288
873
  ClassPairTy ClassPair(RD, VBase);
2289
2290
873
  VirtualBaseClassOffsetOffsetsMapTy::iterator I =
2291
873
    VirtualBaseClassOffsetOffsets.find(ClassPair);
2292
873
  if (I != VirtualBaseClassOffsetOffsets.end())
2293
585
    return I->second;
2294
2295
288
  VCallAndVBaseOffsetBuilder Builder(*this, RD, RD, /*Overriders=*/nullptr,
2296
288
                                     BaseSubobject(RD, CharUnits::Zero()),
2297
288
                                     /*BaseIsVirtual=*/false,
2298
288
                                     /*OffsetInLayoutClass=*/CharUnits::Zero());
2299
2300
341
  for (const auto &I : Builder.getVBaseOffsetOffsets()) {
2301
    // Insert all types.
2302
341
    ClassPairTy ClassPair(RD, I.first);
2303
2304
341
    VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));
2305
341
  }
2306
2307
288
  I = VirtualBaseClassOffsetOffsets.find(ClassPair);
2308
288
  assert(I != VirtualBaseClassOffsetOffsets.end() && "Did not find index!");
2309
2310
288
  return I->second;
2311
288
}
2312
2313
static std::unique_ptr<VTableLayout>
2314
4.26k
CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
2315
4.26k
  SmallVector<VTableLayout::VTableThunkTy, 1>
2316
4.26k
    VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
2317
2318
4.26k
  return std::make_unique<VTableLayout>(
2319
4.26k
      Builder.VTableIndices, Builder.vtable_components(), VTableThunks,
2320
4.26k
      Builder.getAddressPoints());
2321
4.26k
}
2322
2323
void
2324
12.7k
ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
2325
12.7k
  std::unique_ptr<const VTableLayout> &Entry = VTableLayouts[RD];
2326
2327
  // Check if we've computed this information before.
2328
12.7k
  if (Entry)
2329
8.82k
    return;
2330
2331
3.95k
  ItaniumVTableBuilder Builder(*this, RD, CharUnits::Zero(),
2332
3.95k
                               /*MostDerivedClassIsVirtual=*/0, RD);
2333
3.95k
  Entry = CreateVTableLayout(Builder);
2334
2335
3.95k
  MethodVTableIndices.insert(Builder.vtable_indices_begin(),
2336
3.95k
                             Builder.vtable_indices_end());
2337
2338
  // Add the known thunks.
2339
3.95k
  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
3.95k
  if (!RD->getNumVBases())
2345
3.65k
    return;
2346
2347
302
  const CXXRecordDecl *VBase =
2348
302
    RD->vbases_begin()->getType()->getAsCXXRecordDecl();
2349
2350
302
  if (VirtualBaseClassOffsetOffsets.count(std::make_pair(RD, VBase)))
2351
70
    return;
2352
2353
290
  
for (const auto &I : Builder.getVBaseOffsetOffsets())232
{
2354
    // Insert all types.
2355
290
    ClassPairTy ClassPair(RD, I.first);
2356
2357
290
    VirtualBaseClassOffsetOffsets.insert(std::make_pair(ClassPair, I.second));
2358
290
  }
2359
232
}
2360
2361
std::unique_ptr<VTableLayout>
2362
ItaniumVTableContext::createConstructionVTableLayout(
2363
    const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
2364
305
    bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) {
2365
305
  ItaniumVTableBuilder Builder(*this, MostDerivedClass, MostDerivedClassOffset,
2366
305
                               MostDerivedClassIsVirtual, LayoutClass);
2367
305
  return CreateVTableLayout(Builder);
2368
305
}
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.48k
          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::find(ThunksVector, Thunk) != ThunksVector.end())
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.82k
  void AddMethod(const CXXMethodDecl *MD, ThunkInfo TI) {
2517
1.82k
    if (!TI.isEmpty()) {
2518
340
      VTableThunks[Components.size()] = TI;
2519
340
      AddThunk(MD, TI);
2520
340
    }
2521
1.82k
    if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2522
353
      assert(TI.Return.isEmpty() &&
2523
353
             "Destructor can't have return adjustment!");
2524
353
      Components.push_back(VTableComponent::MakeDeletingDtor(DD));
2525
1.46k
    } else {
2526
1.46k
      Components.push_back(VTableComponent::MakeFunction(MD));
2527
1.46k
    }
2528
1.82k
  }
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.26k
  void LayoutVFTable() {
2537
    // RTTI data goes before all other entries.
2538
1.26k
    if (HasRTTIComponent)
2539
478
      Components.push_back(VTableComponent::MakeRTTI(MostDerivedClass));
2540
2541
1.26k
    BasesSetVectorTy VisitedBases;
2542
1.26k
    AddMethods(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 0, nullptr,
2543
1.26k
               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.26k
    assert(!Components.empty() && "vftable can't be empty");
2547
2548
1.26k
    assert(MethodVFTableLocations.empty());
2549
1.82k
    for (const auto &I : MethodInfoMap) {
2550
1.82k
      const CXXMethodDecl *MD = I.first;
2551
1.82k
      const MethodInfo &MI = I.second;
2552
1.82k
      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.82k
      if (MD->getParent() != MostDerivedClass || 
MI.Shadowed1.29k
)
2557
528
        continue;
2558
1.29k
      MethodVFTableLocation Loc(MI.VBTableIndex, WhichVFPtr.getVBaseWithVPtr(),
2559
1.29k
                                WhichVFPtr.NonVirtualOffset, MI.VFTableIndex);
2560
1.29k
      if (const CXXDestructorDecl *DD = dyn_cast<CXXDestructorDecl>(MD)) {
2561
353
        MethodVFTableLocations[GlobalDecl(DD, Dtor_Deleting)] = Loc;
2562
939
      } else {
2563
939
        MethodVFTableLocations[MD] = Loc;
2564
939
      }
2565
1.29k
    }
2566
1.26k
  }
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.26k
        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.26k
    if (Context.getLangOpts().RTTIData)
2583
478
      HasRTTIComponent = true;
2584
2585
1.26k
    LayoutVFTable();
2586
2587
1.26k
    if (Context.getLangOpts().DumpVTableLayouts)
2588
394
      dumpLayout(llvm::outs());
2589
1.26k
  }
2590
2591
0
  uint64_t getNumThunks() const { return Thunks.size(); }
2592
2593
1.26k
  ThunksMapTy::const_iterator thunks_begin() const { return Thunks.begin(); }
2594
2595
1.26k
  ThunksMapTy::const_iterator thunks_end() const { return Thunks.end(); }
2596
2597
1.26k
  method_locations_range vtable_locations() const {
2598
1.26k
    return method_locations_range(MethodVFTableLocations.begin(),
2599
1.26k
                                  MethodVFTableLocations.end());
2600
1.26k
  }
2601
2602
1.26k
  ArrayRef<VTableComponent> vtable_components() const { return Components; }
2603
2604
1.26k
  VTableThunksMapTy::const_iterator vtable_thunks_begin() const {
2605
1.26k
    return VTableThunks.begin();
2606
1.26k
  }
2607
2608
1.26k
  VTableThunksMapTy::const_iterator vtable_thunks_end() const {
2609
1.26k
    return VTableThunks.end();
2610
1.26k
  }
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.74k
VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) {
2673
2.74k
  BasesSetVectorTy Bases;
2674
2675
2.74k
  {
2676
    // Find the set of least derived bases that define the given method.
2677
2.74k
    OverriddenMethodsSetTy VisitedOverriddenMethods;
2678
2.74k
    auto InitialOverriddenDefinitionCollector = [&](
2679
2.65k
        const CXXMethodDecl *OverriddenMD) {
2680
2.65k
      if (OverriddenMD->size_overridden_methods() == 0)
2681
2.06k
        Bases.insert(OverriddenMD->getParent());
2682
      // Don't recurse on this method if we've already collected it.
2683
2.65k
      return VisitedOverriddenMethods.insert(OverriddenMD).second;
2684
2.65k
    };
2685
2.74k
    visitAllOverriddenMethods(Overrider.Method,
2686
2.74k
                              InitialOverriddenDefinitionCollector);
2687
2.74k
  }
2688
2689
  // If there are no overrides then 'this' is located
2690
  // in the base that defines the method.
2691
2.74k
  if (Bases.size() == 0)
2692
1.20k
    return Overrider.Offset;
2693
2694
1.54k
  CXXBasePaths Paths;
2695
1.54k
  Overrider.Method->getParent()->lookupInBases(
2696
3.72k
      [&Bases](const CXXBaseSpecifier *Specifier, CXXBasePath &) {
2697
3.72k
        return Bases.count(Specifier->getType()->getAsCXXRecordDecl());
2698
3.72k
      },
2699
1.54k
      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.54k
  CharUnits Ret;
2706
1.54k
  bool First = true;
2707
2708
1.54k
  const ASTRecordLayout &OverriderRDLayout =
2709
1.54k
      Context.getASTRecordLayout(Overrider.Method->getParent());
2710
2.12k
  for (const CXXBasePath &Path : Paths) {
2711
2.12k
    CharUnits ThisOffset = Overrider.Offset;
2712
2.12k
    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.21k
    for (const CXXBasePathElement &Element : Path) {
2718
3.21k
      QualType CurTy = Element.Base->getType();
2719
3.21k
      const CXXRecordDecl *PrevRD = Element.Class,
2720
3.21k
                          *CurRD = CurTy->getAsCXXRecordDecl();
2721
3.21k
      const ASTRecordLayout &Layout = Context.getASTRecordLayout(PrevRD);
2722
2723
3.21k
      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.14k
      } else {
2737
2.14k
        ThisOffset += Layout.getBaseClassOffset(CurRD);
2738
2.14k
      }
2739
3.21k
    }
2740
2741
2.12k
    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.12k
    if (Ret > ThisOffset || 
First2.11k
) {
2755
1.55k
      First = false;
2756
1.55k
      Ret = ThisOffset;
2757
1.55k
    }
2758
2.12k
  }
2759
2760
1.54k
  assert(!First && "Method not found in the given subobject?");
2761
1.54k
  return Ret;
2762
1.54k
}
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
399
      Overrider.VirtualBase == WhichVFPtr.getVBaseWithVPtr())
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
70
      !Overrider.VirtualBase)
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.25k
    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.25k
  typedef SmallVector<const CXXMethodDecl *, 1> MethodGroup;
2911
2.25k
  SmallVector<MethodGroup, 10> Groups;
2912
2.25k
  typedef llvm::DenseMap<DeclarationName, unsigned> VisitedGroupIndicesTy;
2913
2.25k
  VisitedGroupIndicesTy VisitedGroupIndices;
2914
16.2k
  for (const auto *D : RD->decls()) {
2915
16.2k
    const auto *ND = dyn_cast<NamedDecl>(D);
2916
16.2k
    if (!ND)
2917
201
      continue;
2918
16.0k
    VisitedGroupIndicesTy::iterator J;
2919
16.0k
    bool Inserted;
2920
16.0k
    std::tie(J, Inserted) = VisitedGroupIndices.insert(
2921
16.0k
        std::make_pair(ND->getDeclName(), Groups.size()));
2922
16.0k
    if (Inserted)
2923
11.2k
      Groups.push_back(MethodGroup());
2924
16.0k
    if (const auto *MD = dyn_cast<CXXMethodDecl>(ND))
2925
13.3k
      if (MicrosoftVTableContext::hasVtableSlot(MD))
2926
2.74k
        Groups[J->second].push_back(MD->getCanonicalDecl());
2927
16.0k
  }
2928
2929
2.25k
  for (const MethodGroup &Group : Groups)
2930
11.2k
    VirtualMethods.append(Group.rbegin(), Group.rend());
2931
2.25k
}
2932
2933
991
static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) {
2934
1.52k
  for (const auto &B : RD->bases()) {
2935
1.52k
    if (B.isVirtual() && 
B.getType()->getAsCXXRecordDecl() == Base410
)
2936
320
      return true;
2937
1.52k
  }
2938
671
  return false;
2939
991
}
2940
2941
void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
2942
                                const CXXRecordDecl *LastVBase,
2943
2.25k
                                BasesSetVectorTy &VisitedBases) {
2944
2.25k
  const CXXRecordDecl *RD = Base.getBase();
2945
2.25k
  if (!RD->isPolymorphic())
2946
0
    return;
2947
2948
2.25k
  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.25k
  const CXXRecordDecl *NextBase = nullptr, *NextLastVBase = LastVBase;
2954
2.25k
  CharUnits NextBaseOffset;
2955
2.25k
  if (BaseDepth < WhichVFPtr.PathToIntroducingObject.size()) {
2956
991
    NextBase = WhichVFPtr.PathToIntroducingObject[BaseDepth];
2957
991
    if (isDirectVBase(NextBase, RD)) {
2958
320
      NextLastVBase = NextBase;
2959
320
      NextBaseOffset = MostDerivedClassLayout.getVBaseClassOffset(NextBase);
2960
671
    } else {
2961
671
      NextBaseOffset =
2962
671
          Base.getBaseOffset() + Layout.getBaseClassOffset(NextBase);
2963
671
    }
2964
1.26k
  } 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.25k
  if (NextBase) {
2972
991
    AddMethods(BaseSubobject(NextBase, NextBaseOffset), BaseDepth + 1,
2973
991
               NextLastVBase, VisitedBases);
2974
991
    if (!VisitedBases.insert(NextBase))
2975
0
      llvm_unreachable("Found a duplicate primary base!");
2976
991
  }
2977
2978
2.25k
  SmallVector<const CXXMethodDecl*, 10> VirtualMethods;
2979
  // Put virtual methods in the proper order.
2980
2.25k
  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.74k
  for (const CXXMethodDecl *MD : VirtualMethods) {
2991
2.74k
    FinalOverriders::OverriderInfo FinalOverrider =
2992
2.74k
        Overriders.getOverrider(MD, Base.getBaseOffset());
2993
2.74k
    const CXXMethodDecl *FinalOverriderMD = FinalOverrider.Method;
2994
2.74k
    const CXXMethodDecl *OverriddenMD =
2995
2.74k
        FindNearestOverriddenMethod(MD, VisitedBases);
2996
2997
2.74k
    ThisAdjustment ThisAdjustmentOffset;
2998
2.74k
    bool ReturnAdjustingThunk = false, ForceReturnAdjustmentMangling = false;
2999
2.74k
    CharUnits ThisOffset = ComputeThisOffset(FinalOverrider);
3000
2.74k
    ThisAdjustmentOffset.NonVirtual =
3001
2.74k
        (ThisOffset - WhichVFPtr.FullOffsetInMDC).getQuantity();
3002
2.74k
    if ((OverriddenMD || 
FinalOverriderMD != MD1.97k
) &&
3003
1.40k
        WhichVFPtr.getVBaseWithVPtr())
3004
692
      CalculateVtordispAdjustment(FinalOverrider, ThisOffset,
3005
692
                                  ThisAdjustmentOffset);
3006
3007
2.74k
    unsigned VBIndex =
3008
2.19k
        LastVBase ? 
VTables.getVBTableIndex(MostDerivedClass, LastVBase)553
: 0;
3009
3010
2.74k
    if (OverriddenMD) {
3011
      // If MD overrides anything in this vftable, we need to update the
3012
      // entries.
3013
767
      MethodInfoMapTy::iterator OverriddenMDIterator =
3014
767
          MethodInfoMap.find(OverriddenMD);
3015
3016
      // If the overridden method went to a different vftable, skip it.
3017
767
      if (OverriddenMDIterator == MethodInfoMap.end())
3018
32
        continue;
3019
3020
735
      MethodInfo &OverriddenMethodInfo = OverriddenMDIterator->second;
3021
3022
735
      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
735
      ReturnAdjustingThunk = !ComputeReturnAdjustmentBaseOffset(
3030
735
                                  Context, MD, OverriddenMD).isEmpty() ||
3031
669
                             OverriddenMethodInfo.UsesExtraSlot;
3032
3033
735
      if (!ReturnAdjustingThunk) {
3034
        // No return adjustment needed - just replace the overridden method info
3035
        // with the current info.
3036
660
        MethodInfo MI(VBIndex, OverriddenMethodInfo.VFTableIndex);
3037
660
        MethodInfoMap.erase(OverriddenMDIterator);
3038
3039
660
        assert(!MethodInfoMap.count(MD) &&
3040
660
               "Should not have method info for this method yet!");
3041
660
        MethodInfoMap.insert(std::make_pair(MD, MI));
3042
660
        continue;
3043
660
      }
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.97k
    } else if (Base.getBaseOffset() != WhichVFPtr.FullOffsetInMDC ||
3054
1.84k
               MD->size_overridden_methods()) {
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
234
      continue;
3059
234
    }
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.82k
    MethodInfo MI(VBIndex,
3064
1.21k
                  HasRTTIComponent ? 
Components.size() - 1605
: Components.size(),
3065
1.82k
                  ReturnAdjustingThunk);
3066
3067
1.82k
    assert(!MethodInfoMap.count(MD) &&
3068
1.82k
           "Should not have method info for this method yet!");
3069
1.82k
    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.82k
    BaseOffset ReturnAdjustmentOffset;
3074
1.82k
    ReturnAdjustment ReturnAdjustment;
3075
1.82k
    if (!FinalOverriderMD->isPure()) {
3076
1.78k
      ReturnAdjustmentOffset =
3077
1.78k
          ComputeReturnAdjustmentBaseOffset(Context, FinalOverriderMD, MD);
3078
1.78k
    }
3079
1.82k
    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.82k
    AddMethod(FinalOverriderMD,
3095
1.82k
              ThunkInfo(ThisAdjustmentOffset, ReturnAdjustment,
3096
1.72k
                        ForceReturnAdjustmentMangling ? 
MD91
: nullptr));
3097
1.82k
  }
3098
2.25k
}
3099
3100
394
static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) {
3101
394
  for (const CXXRecordDecl *Elem :
3102
485
       llvm::make_range(Path.rbegin(), Path.rend())) {
3103
485
    Out << "'";
3104
485
    Elem->printQualifiedName(Out);
3105
485
    Out << "' in ";
3106
485
  }
3107
394
}
3108
3109
static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
3110
366
                                         bool ContinueFirstLine) {
3111
366
  const ReturnAdjustment &R = TI.Return;
3112
366
  bool Multiline = false;
3113
366
  const char *LinePrefix = "\n       ";
3114
366
  if (!R.isEmpty() || 
TI.Method290
) {
3115
104
    if (!ContinueFirstLine)
3116
52
      Out << LinePrefix;
3117
104
    Out << "[return adjustment (to type '"
3118
104
        << TI.Method->getReturnType().getCanonicalType().getAsString()
3119
104
        << "'): ";
3120
104
    if (R.Virtual.Microsoft.VBPtrOffset)
3121
2
      Out << "vbptr at offset " << R.Virtual.Microsoft.VBPtrOffset << ", ";
3122
104
    if (R.Virtual.Microsoft.VBIndex)
3123
34
      Out << "vbase #" << R.Virtual.Microsoft.VBIndex << ", ";
3124
104
    Out << R.NonVirtual << " non-virtual]";
3125
104
    Multiline = true;
3126
104
  }
3127
3128
366
  const ThisAdjustment &T = TI.This;
3129
366
  if (!T.isEmpty()) {
3130
300
    if (Multiline || 
!ContinueFirstLine262
)
3131
169
      Out << LinePrefix;
3132
300
    Out << "[this adjustment: ";
3133
300
    if (!TI.This.Virtual.isEmpty()) {
3134
210
      assert(T.Virtual.Microsoft.VtordispOffset < 0);
3135
210
      Out << "vtordisp at " << T.Virtual.Microsoft.VtordispOffset << ", ";
3136
210
      if (T.Virtual.Microsoft.VBPtrOffset) {
3137
40
        Out << "vbptr at " << T.Virtual.Microsoft.VBPtrOffset
3138
40
            << " to the left,";
3139
40
        assert(T.Virtual.Microsoft.VBOffsetOffset > 0);
3140
40
        Out << LinePrefix << " vboffset at "
3141
40
            << T.Virtual.Microsoft.VBOffsetOffset << " in the vbtable, ";
3142
40
      }
3143
210
    }
3144
300
    Out << T.NonVirtual << " non-virtual]";
3145
300
  }
3146
366
}
3147
3148
394
void VFTableBuilder::dumpLayout(raw_ostream &Out) {
3149
394
  Out << "VFTable for ";
3150
394
  PrintBasePath(WhichVFPtr.PathToIntroducingObject, Out);
3151
394
  Out << "'";
3152
394
  MostDerivedClass->printQualifiedName(Out);
3153
394
  Out << "' (" << Components.size()
3154
257
      << (Components.size() == 1 ? 
" entry"137
: " entries") << ").\n";
3155
3156
1.12k
  for (unsigned I = 0, E = Components.size(); I != E; 
++I733
) {
3157
733
    Out << llvm::format("%4d | ", I);
3158
3159
733
    const VTableComponent &Component = Components[I];
3160
3161
    // Dump the component.
3162
733
    switch (Component.getKind()) {
3163
0
    case VTableComponent::CK_RTTI:
3164
0
      Component.getRTTIDecl()->printQualifiedName(Out);
3165
0
      Out << " RTTI";
3166
0
      break;
3167
3168
634
    case VTableComponent::CK_FunctionPointer: {
3169
634
      const CXXMethodDecl *MD = Component.getFunctionDecl();
3170
3171
      // FIXME: Figure out how to print the real thunk type, since they can
3172
      // differ in the return type.
3173
634
      std::string Str = PredefinedExpr::ComputeName(
3174
634
          PredefinedExpr::PrettyFunctionNoVirtual, MD);
3175
634
      Out << Str;
3176
634
      if (MD->isPure())
3177
5
        Out << " [pure]";
3178
3179
634
      if (MD->isDeleted())
3180
1
        Out << " [deleted]";
3181
3182
634
      ThunkInfo Thunk = VTableThunks.lookup(I);
3183
634
      if (!Thunk.isEmpty())
3184
119
        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3185
3186
634
      break;
3187
0
    }
3188
3189
99
    case VTableComponent::CK_DeletingDtorPointer: {
3190
99
      const CXXDestructorDecl *DD = Component.getDestructorDecl();
3191
3192
99
      DD->printQualifiedName(Out);
3193
99
      Out << "() [scalar deleting]";
3194
3195
99
      if (DD->isPure())
3196
0
        Out << " [pure]";
3197
3198
99
      ThunkInfo Thunk = VTableThunks.lookup(I);
3199
99
      if (!Thunk.isEmpty()) {
3200
64
        assert(Thunk.Return.isEmpty() &&
3201
64
               "No return adjustment needed for destructors!");
3202
64
        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/false);
3203
64
      }
3204
3205
99
      break;
3206
0
    }
3207
3208
0
    default:
3209
0
      DiagnosticsEngine &Diags = Context.getDiagnostics();
3210
0
      unsigned DiagID = Diags.getCustomDiagID(
3211
0
          DiagnosticsEngine::Error,
3212
0
          "Unexpected vftable component type %0 for component number %1");
3213
0
      Diags.Report(MostDerivedClass->getLocation(), DiagID)
3214
0
          << I << Component.getKind();
3215
733
    }
3216
3217
733
    Out << '\n';
3218
733
  }
3219
3220
394
  Out << '\n';
3221
3222
394
  if (!Thunks.empty()) {
3223
    // We store the method names in a map to get a stable order.
3224
121
    std::map<std::string, const CXXMethodDecl *> MethodNamesAndDecls;
3225
3226
164
    for (const auto &I : Thunks) {
3227
164
      const CXXMethodDecl *MD = I.first;
3228
164
      std::string MethodName = PredefinedExpr::ComputeName(
3229
164
          PredefinedExpr::PrettyFunctionNoVirtual, MD);
3230
3231
164
      MethodNamesAndDecls.insert(std::make_pair(MethodName, MD));
3232
164
    }
3233
3234
164
    for (const auto &MethodNameAndDecl : MethodNamesAndDecls) {
3235
164
      const std::string &MethodName = MethodNameAndDecl.first;
3236
164
      const CXXMethodDecl *MD = MethodNameAndDecl.second;
3237
3238
164
      ThunkInfoVectorTy ThunksVector = Thunks[MD];
3239
164
      llvm::stable_sort(ThunksVector, [](const ThunkInfo &LHS,
3240
23
                                         const ThunkInfo &RHS) {
3241
        // Keep different thunks with the same adjustments in the order they
3242
        // were put into the vector.
3243
23
        return std::tie(LHS.This, LHS.Return) < std::tie(RHS.This, RHS.Return);
3244
23
      });
3245
3246
164
      Out << "Thunks for '" << MethodName << "' (" << ThunksVector.size();
3247
149
      Out << (ThunksVector.size() == 1 ? " entry" : 
" entries"15
) << ").\n";
3248
3249
347
      for (unsigned I = 0, E = ThunksVector.size(); I != E; 
++I183
) {
3250
183
        const ThunkInfo &Thunk = ThunksVector[I];
3251
3252
183
        Out << llvm::format("%4d | ", I);
3253
183
        dumpMicrosoftThunkAdjustment(Thunk, Out, /*ContinueFirstLine=*/true);
3254
183
        Out << '\n';
3255
183
      }
3256
3257
164
      Out << '\n';
3258
164
    }
3259
121
  }
3260
3261
394
  Out.flush();
3262
394
}
3263
3264
static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
3265
1.10k
                          ArrayRef<const CXXRecordDecl *> B) {
3266
310
  for (const CXXRecordDecl *Decl : B) {
3267
310
    if (A.count(Decl))
3268
39
      return true;
3269
310
  }
3270
1.06k
  return false;
3271
1.10k
}
3272
3273
static bool rebucketPaths(VPtrInfoVector &Paths);
3274
3275
/// Produces MSVC-compatible vbtable data.  The symbols produced by this
3276
/// algorithm match those produced by MSVC 2012 and newer, which is different
3277
/// from MSVC 2010.
3278
///
3279
/// MSVC 2012 appears to minimize the vbtable names using the following
3280
/// algorithm.  First, walk the class hierarchy in the usual order, depth first,
3281
/// left to right, to find all of the subobjects which contain a vbptr field.
3282
/// Visiting each class node yields a list of inheritance paths to vbptrs.  Each
3283
/// record with a vbptr creates an initially empty path.
3284
///
3285
/// To combine paths from child nodes, the paths are compared to check for
3286
/// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of
3287
/// components in the same order.  Each group of ambiguous paths is extended by
3288
/// appending the class of the base from which it came.  If the current class
3289
/// node produced an ambiguous path, its path is extended with the current class.
3290
/// After extending paths, MSVC again checks for ambiguity, and extends any
3291
/// ambiguous path which wasn't already extended.  Because each node yields an
3292
/// unambiguous set of paths, MSVC doesn't need to extend any path more than once
3293
/// to produce an unambiguous set of paths.
3294
///
3295
/// TODO: Presumably vftables use the same algorithm.
3296
void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
3297
                                                const CXXRecordDecl *RD,
3298
1.79k
                                                VPtrInfoVector &Paths) {
3299
1.79k
  assert(Paths.empty());
3300
1.79k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3301
3302
  // Base case: this subobject has its own vptr.
3303
1.79k
  if (ForVBTables ? 
Layout.hasOwnVBPtr()615
:
Layout.hasOwnVFPtr()1.17k
)
3304
856
    Paths.push_back(std::make_unique<VPtrInfo>(RD));
3305
3306
  // Recursive case: get all the vbtables from our bases and remove anything
3307
  // that shares a virtual base.
3308
1.79k
  llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
3309
1.61k
  for (const auto &B : RD->bases()) {
3310
1.61k
    const CXXRecordDecl *Base = B.getType()->getAsCXXRecordDecl();
3311
1.61k
    if (B.isVirtual() && 
VBasesSeen.count(Base)706
)
3312
54
      continue;
3313
3314
1.55k
    if (!Base->isDynamicClass())
3315
245
      continue;
3316
3317
1.31k
    const VPtrInfoVector &BasePaths =
3318
795
        ForVBTables ? 
enumerateVBTables(Base)519
: getVFPtrOffsets(Base);
3319
3320
1.10k
    for (const std::unique_ptr<VPtrInfo> &BaseInfo : BasePaths) {
3321
      // Don't include the path if it goes through a virtual base that we've
3322
      // already included.
3323
1.10k
      if (setsIntersect(VBasesSeen, BaseInfo->ContainingVBases))
3324
39
        continue;
3325
3326
      // Copy the path and adjust it as necessary.
3327
1.06k
      auto P = std::make_unique<VPtrInfo>(*BaseInfo);
3328
3329
      // We mangle Base into the path if the path would've been ambiguous and it
3330
      // wasn't already extended with Base.
3331
1.06k
      if (P->MangledPath.empty() || 
P->MangledPath.back() != Base259
)
3332
1.02k
        P->NextBaseToMangle = Base;
3333
3334
      // Keep track of which vtable the derived class is going to extend with
3335
      // new methods or bases.  We append to either the vftable of our primary
3336
      // base, or the first non-virtual base that has a vbtable.
3337
1.06k
      if (P->ObjectWithVPtr == Base &&
3338
823
          Base == (ForVBTables ? 
Layout.getBaseSharingVBPtr()266
3339
557
                               : Layout.getPrimaryBase()))
3340
416
        P->ObjectWithVPtr = RD;
3341
3342
      // Keep track of the full adjustment from the MDC to this vtable.  The
3343
      // adjustment is captured by an optional vbase and a non-virtual offset.
3344
1.06k
      if (B.isVirtual())
3345
335
        P->ContainingVBases.push_back(Base);
3346
728
      else if (P->ContainingVBases.empty())
3347
629
        P->NonVirtualOffset += Layout.getBaseClassOffset(Base);
3348
3349
      // Update the full offset in the MDC.
3350
1.06k
      P->FullOffsetInMDC = P->NonVirtualOffset;
3351
1.06k
      if (const CXXRecordDecl *VB = P->getVBaseWithVPtr())
3352
434
        P->FullOffsetInMDC += Layout.getVBaseClassOffset(VB);
3353
3354
1.06k
      Paths.push_back(std::move(P));
3355
1.06k
    }
3356
3357
1.31k
    if (B.isVirtual())
3358
469
      VBasesSeen.insert(Base);
3359
3360
    // After visiting any direct base, we've transitively visited all of its
3361
    // morally virtual bases.
3362
1.31k
    for (const auto &VB : Base->vbases())
3363
699
      VBasesSeen.insert(VB.getType()->getAsCXXRecordDecl());
3364
1.31k
  }
3365
3366
  // Sort the paths into buckets, and if any of them are ambiguous, extend all
3367
  // paths in ambiguous buckets.
3368
1.79k
  bool Changed = true;
3369
3.85k
  while (Changed)
3370
2.06k
    Changed = rebucketPaths(Paths);
3371
1.79k
}
3372
3373
580
static bool extendPath(VPtrInfo &P) {
3374
580
  if (P.NextBaseToMangle) {
3375
560
    P.MangledPath.push_back(P.NextBaseToMangle);
3376
560
    P.NextBaseToMangle = nullptr;// Prevent the path from being extended twice.
3377
560
    return true;
3378
560
  }
3379
20
  return false;
3380
20
}
3381
3382
2.06k
static bool rebucketPaths(VPtrInfoVector &Paths) {
3383
  // What we're essentially doing here is bucketing together ambiguous paths.
3384
  // Any bucket with more than one path in it gets extended by NextBase, which
3385
  // is usually the direct base of the inherited the vbptr.  This code uses a
3386
  // sorted vector to implement a multiset to form the buckets.  Note that the
3387
  // ordering is based on pointers, but it doesn't change our output order.  The
3388
  // current algorithm is designed to match MSVC 2012's names.
3389
2.06k
  llvm::SmallVector<std::reference_wrapper<VPtrInfo>, 2> PathsSorted;
3390
2.06k
  PathsSorted.reserve(Paths.size());
3391
2.06k
  for (auto& P : Paths)
3392
2.57k
    PathsSorted.push_back(*P);
3393
1.26k
  llvm::sort(PathsSorted, [](const VPtrInfo &LHS, const VPtrInfo &RHS) {
3394
1.26k
    return LHS.MangledPath < RHS.MangledPath;
3395
1.26k
  });
3396
2.06k
  bool Changed = false;
3397
4.33k
  for (size_t I = 0, E = PathsSorted.size(); I != E;) {
3398
    // Scan forward to find the end of the bucket.
3399
2.27k
    size_t BucketStart = I;
3400
2.57k
    do {
3401
2.57k
      ++I;
3402
2.57k
    } while (I != E &&
3403
852
             PathsSorted[BucketStart].get().MangledPath ==
3404
852
                 PathsSorted[I].get().MangledPath);
3405
3406
    // If this bucket has multiple paths, extend them all.
3407
2.27k
    if (I - BucketStart > 1) {
3408
860
      for (size_t II = BucketStart; II != I; 
++II580
)
3409
580
        Changed |= extendPath(PathsSorted[II]);
3410
280
      assert(Changed && "no paths were extended to fix ambiguity");
3411
280
    }
3412
2.27k
  }
3413
2.06k
  return Changed;
3414
2.06k
}
3415
3416
669
MicrosoftVTableContext::~MicrosoftVTableContext() {}
3417
3418
namespace {
3419
typedef llvm::SetVector<BaseSubobject, std::vector<BaseSubobject>,
3420
                        llvm::DenseSet<BaseSubobject>> FullPathTy;
3421
}
3422
3423
// This recursive function finds all paths from a subobject centered at
3424
// (RD, Offset) to the subobject located at IntroducingObject.
3425
static void findPathsToSubobject(ASTContext &Context,
3426
                                 const ASTRecordLayout &MostDerivedLayout,
3427
                                 const CXXRecordDecl *RD, CharUnits Offset,
3428
                                 BaseSubobject IntroducingObject,
3429
                                 FullPathTy &FullPath,
3430
2.96k
                                 std::list<FullPathTy> &Paths) {
3431
2.96k
  if (BaseSubobject(RD, Offset) == IntroducingObject) {
3432
1.30k
    Paths.push_back(FullPath);
3433
1.30k
    return;
3434
1.30k
  }
3435
3436
1.66k
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3437
3438
1.70k
  for (const CXXBaseSpecifier &BS : RD->bases()) {
3439
1.70k
    const CXXRecordDecl *Base = BS.getType()->getAsCXXRecordDecl();
3440
1.70k
    CharUnits NewOffset = BS.isVirtual()
3441
493
                              ? MostDerivedLayout.getVBaseClassOffset(Base)
3442
1.20k
                              : Offset + Layout.getBaseClassOffset(Base);
3443
1.70k
    FullPath.insert(BaseSubobject(Base, NewOffset));
3444
1.70k
    findPathsToSubobject(Context, MostDerivedLayout, Base, NewOffset,
3445
1.70k
                         IntroducingObject, FullPath, Paths);
3446
1.70k
    FullPath.pop_back();
3447
1.70k
  }
3448
1.66k
}
3449
3450
// Return the paths which are not subsets of other paths.
3451
1.26k
static void removeRedundantPaths(std::list<FullPathTy> &FullPaths) {
3452
1.30k
  FullPaths.remove_if([&](const FullPathTy &SpecificPath) {
3453
1.36k
    for (const FullPathTy &OtherPath : FullPaths) {
3454
1.36k
      if (&SpecificPath == &OtherPath)
3455
1.29k
        continue;
3456
84
      
if (77
llvm::all_of(SpecificPath, [&](const BaseSubobject &BSO) 77
{
3457
84
            return OtherPath.count(BSO) != 0;
3458
16
          })) {
3459
16
        return true;
3460
16
      }
3461
77
    }
3462
1.28k
    return false;
3463
1.30k
  });
3464
1.26k
}
3465
3466
static CharUnits getOffsetOfFullPath(ASTContext &Context,
3467
                                     const CXXRecordDecl *RD,
3468
44
                                     const FullPathTy &FullPath) {
3469
44
  const ASTRecordLayout &MostDerivedLayout =
3470
44
      Context.getASTRecordLayout(RD);
3471
44
  CharUnits Offset = CharUnits::fromQuantity(-1);
3472
102
  for (const BaseSubobject &BSO : FullPath) {
3473
102
    const CXXRecordDecl *Base = BSO.getBase();
3474
    // The first entry in the path is always the most derived record, skip it.
3475
102
    if (Base == RD) {
3476
44
      assert(Offset.getQuantity() == -1);
3477
44
      Offset = CharUnits::Zero();
3478
44
      continue;
3479
44
    }
3480
58
    assert(Offset.getQuantity() != -1);
3481
58
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3482
    // While we know which base has to be traversed, we don't know if that base
3483
    // was a virtual base.
3484
58
    const CXXBaseSpecifier *BaseBS = std::find_if(
3485
63
        RD->bases_begin(), RD->bases_end(), [&](const CXXBaseSpecifier &BS) {
3486
63
          return BS.getType()->getAsCXXRecordDecl() == Base;
3487
63
        });
3488
48
    Offset = BaseBS->isVirtual() ? MostDerivedLayout.getVBaseClassOffset(Base)
3489
10
                                 : Offset + Layout.getBaseClassOffset(Base);
3490
58
    RD = Base;
3491
58
  }
3492
44
  return Offset;
3493
44
}
3494
3495
// We want to select the path which introduces the most covariant overrides.  If
3496
// two paths introduce overrides which the other path doesn't contain, issue a
3497
// diagnostic.
3498
static const FullPathTy *selectBestPath(ASTContext &Context,
3499
                                        const CXXRecordDecl *RD,
3500
                                        const VPtrInfo &Info,
3501
1.26k
                                        std::list<FullPathTy> &FullPaths) {
3502
  // Handle some easy cases first.
3503
1.26k
  if (FullPaths.empty())
3504
0
    return nullptr;
3505
1.26k
  if (FullPaths.size() == 1)
3506
1.24k
    return &FullPaths.front();
3507
3508
22
  const FullPathTy *BestPath = nullptr;
3509
22
  typedef std::set<const CXXMethodDecl *> OverriderSetTy;
3510
22
  OverriderSetTy LastOverrides;
3511
44
  for (const FullPathTy &SpecificPath : FullPaths) {
3512
44
    assert(!SpecificPath.empty());
3513
44
    OverriderSetTy CurrentOverrides;
3514
44
    const CXXRecordDecl *TopLevelRD = SpecificPath.begin()->getBase();
3515
    // Find the distance from the start of the path to the subobject with the
3516
    // VPtr.
3517
44
    CharUnits BaseOffset =
3518
44
        getOffsetOfFullPath(Context, TopLevelRD, SpecificPath);
3519
44
    FinalOverriders Overriders(TopLevelRD, CharUnits::Zero(), TopLevelRD);
3520
280
    for (const CXXMethodDecl *MD : Info.IntroducingObject->methods()) {
3521
280
      if (!MicrosoftVTableContext::hasVtableSlot(MD))
3522
222
        continue;
3523
58
      FinalOverriders::OverriderInfo OI =
3524
58
          Overriders.getOverrider(MD->getCanonicalDecl(), BaseOffset);
3525
58
      const CXXMethodDecl *OverridingMethod = OI.Method;
3526
      // Only overriders which have a return adjustment introduce problematic
3527
      // thunks.
3528
58
      if (ComputeReturnAdjustmentBaseOffset(Context, OverridingMethod, MD)
3529
58
              .isEmpty())
3530
49
        continue;
3531
      // It's possible that the overrider isn't in this path.  If so, skip it
3532
      // because this path didn't introduce it.
3533
9
      const CXXRecordDecl *OverridingParent = OverridingMethod->getParent();
3534
15
      if (
llvm::none_of(SpecificPath, [&](const BaseSubobject &BSO) 9
{
3535
15
            return BSO.getBase() == OverridingParent;
3536
15
          }))
3537
0
        continue;
3538
9
      CurrentOverrides.insert(OverridingMethod);
3539
9
    }
3540
44
    OverriderSetTy NewOverrides =
3541
44
        llvm::set_difference(CurrentOverrides, LastOverrides);
3542
44
    if (NewOverrides.empty())
3543
37
      continue;
3544
7
    OverriderSetTy MissingOverrides =
3545
7
        llvm::set_difference(LastOverrides, CurrentOverrides);
3546
7
    if (MissingOverrides.empty()) {
3547
      // This path is a strict improvement over the last path, let's use it.
3548
5
      BestPath = &SpecificPath;
3549
5
      std::swap(CurrentOverrides, LastOverrides);
3550
2
    } else {
3551
      // This path introduces an overrider with a conflicting covariant thunk.
3552
2
      DiagnosticsEngine &Diags = Context.getDiagnostics();
3553
2
      const CXXMethodDecl *CovariantMD = *NewOverrides.begin();
3554
2
      const CXXMethodDecl *ConflictMD = *MissingOverrides.begin();
3555
2
      Diags.Report(RD->getLocation(), diag::err_vftable_ambiguous_component)
3556
2
          << RD;
3557
2
      Diags.Report(CovariantMD->getLocation(), diag::note_covariant_thunk)
3558
2
          << CovariantMD;
3559
2
      Diags.Report(ConflictMD->getLocation(), diag::note_covariant_thunk)
3560
2
          << ConflictMD;
3561
2
    }
3562
7
  }
3563
  // Go with the path that introduced the most covariant overrides.  If there is
3564
  // no such path, pick the first path.
3565
17
  return BestPath ? 
BestPath5
: &FullPaths.front();
3566
22
}
3567
3568
static void computeFullPathsForVFTables(ASTContext &Context,
3569
                                        const CXXRecordDecl *RD,
3570
1.17k
                                        VPtrInfoVector &Paths) {
3571
1.17k
  const ASTRecordLayout &MostDerivedLayout = Context.getASTRecordLayout(RD);
3572
1.17k
  FullPathTy FullPath;
3573
1.17k
  std::list<FullPathTy> FullPaths;
3574
1.26k
  for (const std::unique_ptr<VPtrInfo>& Info : Paths) {
3575
1.26k
    findPathsToSubobject(
3576
1.26k
        Context, MostDerivedLayout, RD, CharUnits::Zero(),
3577
1.26k
        BaseSubobject(Info->IntroducingObject, Info->FullOffsetInMDC), FullPath,
3578
1.26k
        FullPaths);
3579
1.26k
    FullPath.clear();
3580
1.26k
    removeRedundantPaths(FullPaths);
3581
1.26k
    Info->PathToIntroducingObject.clear();
3582
1.26k
    if (const FullPathTy *BestPath =
3583
1.26k
            selectBestPath(Context, RD, *Info, FullPaths))
3584
1.26k
      for (const BaseSubobject &BSO : *BestPath)
3585
991
        Info->PathToIntroducingObject.push_back(BSO.getBase());
3586
1.26k
    FullPaths.clear();
3587
1.26k
  }
3588
1.17k
}
3589
3590
static bool vfptrIsEarlierInMDC(const ASTRecordLayout &Layout,
3591
                                const MethodVFTableLocation &LHS,
3592
102
                                const MethodVFTableLocation &RHS) {
3593
102
  CharUnits L = LHS.VFPtrOffset;
3594
102
  CharUnits R = RHS.VFPtrOffset;
3595
102
  if (LHS.VBase)
3596
34
    L += Layout.getVBaseClassOffset(LHS.VBase);
3597
102
  if (RHS.VBase)
3598
31
    R += Layout.getVBaseClassOffset(RHS.VBase);
3599
102
  return L < R;
3600
102
}
3601
3602
void MicrosoftVTableContext::computeVTableRelatedInformation(
3603
5.32k
    const CXXRecordDecl *RD) {
3604
5.32k
  assert(RD->isDynamicClass());
3605
3606
  // Check if we've computed this information before.
3607
5.32k
  if (VFPtrLocations.count(RD))
3608
4.14k
    return;
3609
3610
1.17k
  const VTableLayout::AddressPointsMapTy EmptyAddressPointsMap;
3611
3612
1.17k
  {
3613
1.17k
    auto VFPtrs = std::make_unique<VPtrInfoVector>();
3614
1.17k
    computeVTablePaths(/*ForVBTables=*/false, RD, *VFPtrs);
3615
1.17k
    computeFullPathsForVFTables(Context, RD, *VFPtrs);
3616
1.17k
    VFPtrLocations[RD] = std::move(VFPtrs);
3617
1.17k
  }
3618
3619
1.17k
  MethodVFTableLocationsTy NewMethodLocations;
3620
1.26k
  for (const std::unique_ptr<VPtrInfo> &VFPtr : *VFPtrLocations[RD]) {
3621
1.26k
    VFTableBuilder Builder(*this, RD, *VFPtr);
3622
3623
1.26k
    VFTableIdTy id(RD, VFPtr->FullOffsetInMDC);
3624
1.26k
    assert(VFTableLayouts.count(id) == 0);
3625
1.26k
    SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
3626
1.26k
        Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
3627
1.26k
    VFTableLayouts[id] = std::make_unique<VTableLayout>(
3628
1.26k
        ArrayRef<size_t>{0}, Builder.vtable_components(), VTableThunks,
3629
1.26k
        EmptyAddressPointsMap);
3630
1.26k
    Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
3631
3632
1.26k
    const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3633
1.29k
    for (const auto &Loc : Builder.vtable_locations()) {
3634
1.29k
      auto Insert = NewMethodLocations.insert(Loc);
3635
1.29k
      if (!Insert.second) {
3636
102
        const MethodVFTableLocation &NewLoc = Loc.second;
3637
102
        MethodVFTableLocation &OldLoc = Insert.first->second;
3638
102
        if (vfptrIsEarlierInMDC(Layout, NewLoc, OldLoc))
3639
3
          OldLoc = NewLoc;
3640
102
      }
3641
1.29k
    }
3642
1.26k
  }
3643
3644
1.17k
  MethodVFTableLocations.insert(NewMethodLocations.begin(),
3645
1.17k
                                NewMethodLocations.end());
3646
1.17k
  if (Context.getLangOpts().DumpVTableLayouts)
3647
288
    dumpMethodLocations(RD, NewMethodLocations, llvm::outs());
3648
1.17k
}
3649
3650
void MicrosoftVTableContext::dumpMethodLocations(
3651
    const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
3652
288
    raw_ostream &Out) {
3653
  // Compute the vtable indices for all the member functions.
3654
  // Store them in a map keyed by the location so we'll get a sorted table.
3655
288
  std::map<MethodVFTableLocation, std::string> IndicesMap;
3656
288
  bool HasNonzeroOffset = false;
3657
3658
340
  for (const auto &I : NewMethods) {
3659
340
    const CXXMethodDecl *MD = cast<const CXXMethodDecl>(I.first.getDecl());
3660
340
    assert(hasVtableSlot(MD));
3661
3662
340
    std::string MethodName = PredefinedExpr::ComputeName(
3663
340
        PredefinedExpr::PrettyFunctionNoVirtual, MD);
3664
3665
340
    if (isa<CXXDestructorDecl>(MD)) {
3666
71
      IndicesMap[I.second] = MethodName + " [scalar deleting]";
3667
269
    } else {
3668
269
      IndicesMap[I.second] = MethodName;
3669
269
    }
3670
3671
340
    if (!I.second.VFPtrOffset.isZero() || 
I.second.VBTableIndex != 0310
)
3672
101
      HasNonzeroOffset = true;
3673
340
  }
3674
3675
  // Print the vtable indices for all the member functions.
3676
288
  if (!IndicesMap.empty()) {
3677
239
    Out << "VFTable indices for ";
3678
239
    Out << "'";
3679
239
    RD->printQualifiedName(Out);
3680
239
    Out << "' (" << IndicesMap.size()
3681
162
        << (IndicesMap.size() == 1 ? " entry" : 
" entries"77
) << ").\n";
3682
3683
239
    CharUnits LastVFPtrOffset = CharUnits::fromQuantity(-1);
3684
239
    uint64_t LastVBIndex = 0;
3685
340
    for (const auto &I : IndicesMap) {
3686
340
      CharUnits VFPtrOffset = I.first.VFPtrOffset;
3687
340
      uint64_t VBIndex = I.first.VBTableIndex;
3688
340
      if (HasNonzeroOffset &&
3689
110
          (VFPtrOffset != LastVFPtrOffset || 
VBIndex != LastVBIndex19
)) {
3690
96
        assert(VBIndex > LastVBIndex || VFPtrOffset > LastVFPtrOffset);
3691
96
        Out << " -- accessible via ";
3692
96
        if (VBIndex)
3693
65
          Out << "vbtable index " << VBIndex << ", ";
3694
96
        Out << "vfptr at offset " << VFPtrOffset.getQuantity() << " --\n";
3695
96
        LastVFPtrOffset = VFPtrOffset;
3696
96
        LastVBIndex = VBIndex;
3697
96
      }
3698
3699
340
      uint64_t VTableIndex = I.first.Index;
3700
340
      const std::string &MethodName = I.second;
3701
340
      Out << llvm::format("%4" PRIu64 " | ", VTableIndex) << MethodName << '\n';
3702
340
    }
3703
239
    Out << '\n';
3704
239
  }
3705
3706
288
  Out.flush();
3707
288
}
3708
3709
const VirtualBaseInfo &MicrosoftVTableContext::computeVBTableRelatedInformation(
3710
3.14k
    const CXXRecordDecl *RD) {
3711
3.14k
  VirtualBaseInfo *VBI;
3712
3713
3.14k
  {
3714
    // Get or create a VBI for RD.  Don't hold a reference to the DenseMap cell,
3715
    // as it may be modified and rehashed under us.
3716
3.14k
    std::unique_ptr<VirtualBaseInfo> &Entry = VBaseInfo[RD];
3717
3.14k
    if (Entry)
3718
2.53k
      return *Entry;
3719
615
    Entry = std::make_unique<VirtualBaseInfo>();
3720
615
    VBI = Entry.get();
3721
615
  }
3722
3723
615
  computeVTablePaths(/*ForVBTables=*/true, RD, VBI->VBPtrPaths);
3724
3725
  // First, see if the Derived class shared the vbptr with a non-virtual base.
3726
615
  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
3727
615
  if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) {
3728
    // If the Derived class shares the vbptr with a non-virtual base, the shared
3729
    // virtual bases come first so that the layout is the same.
3730
140
    const VirtualBaseInfo &BaseInfo =
3731
140
        computeVBTableRelatedInformation(VBPtrBase);
3732
140
    VBI->VBTableIndices.insert(BaseInfo.VBTableIndices.begin(),
3733
140
                               BaseInfo.VBTableIndices.end());
3734
140
  }
3735
3736
  // New vbases are added to the end of the vbtable.
3737
  // Skip the self entry and vbases visited in the non-virtual base, if any.
3738
615
  unsigned VBTableIndex = 1 + VBI->VBTableIndices.size();
3739
618
  for (const auto &VB : RD->vbases()) {
3740
618
    const CXXRecordDecl *CurVBase = VB.getType()->getAsCXXRecordDecl();
3741
618
    if (!VBI->VBTableIndices.count(CurVBase))
3742
449
      VBI->VBTableIndices[CurVBase] = VBTableIndex++;
3743
618
  }
3744
3745
615
  return *VBI;
3746
615
}
3747
3748
unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
3749
2.11k
                                                 const CXXRecordDecl *VBase) {
3750
2.11k
  const VirtualBaseInfo &VBInfo = computeVBTableRelatedInformation(Derived);
3751
2.11k
  assert(VBInfo.VBTableIndices.count(VBase));
3752
2.11k
  return VBInfo.VBTableIndices.find(VBase)->second;
3753
2.11k
}
3754
3755
const VPtrInfoVector &
3756
892
MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) {
3757
892
  return computeVBTableRelatedInformation(RD).VBPtrPaths;
3758
892
}
3759
3760
const VPtrInfoVector &
3761
3.01k
MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) {
3762
3.01k
  computeVTableRelatedInformation(RD);
3763
3764
3.01k
  assert(VFPtrLocations.count(RD) && "Couldn't find vfptr locations");
3765
3.01k
  return *VFPtrLocations[RD];
3766
3.01k
}
3767
3768
const VTableLayout &
3769
MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
3770
1.62k
                                         CharUnits VFPtrOffset) {
3771
1.62k
  computeVTableRelatedInformation(RD);
3772
3773
1.62k
  VFTableIdTy id(RD, VFPtrOffset);
3774
1.62k
  assert(VFTableLayouts.count(id) && "Couldn't find a VFTable at this offset");
3775
1.62k
  return *VFTableLayouts[id];
3776
1.62k
}
3777
3778
MethodVFTableLocation
3779
4.34k
MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) {
3780
4.34k
  assert(hasVtableSlot(cast<CXXMethodDecl>(GD.getDecl())) &&
3781
4.34k
         "Only use this method for virtual methods or dtors");
3782
4.34k
  if (isa<CXXDestructorDecl>(GD.getDecl()))
3783
4.34k
    assert(GD.getDtorType() == Dtor_Deleting);
3784
3785
4.34k
  GD = GD.getCanonicalDecl();
3786
3787
4.34k
  MethodVFTableLocationsTy::iterator I = MethodVFTableLocations.find(GD);
3788
4.34k
  if (I != MethodVFTableLocations.end())
3789
4.08k
    return I->second;
3790
3791
259
  const CXXRecordDecl *RD = cast<CXXMethodDecl>(GD.getDecl())->getParent();
3792
3793
259
  computeVTableRelatedInformation(RD);
3794
3795
259
  I = MethodVFTableLocations.find(GD);
3796
259
  assert(I != MethodVFTableLocations.end() && "Did not find index!");
3797
259
  return I->second;
3798
259
}