Coverage Report

Created: 2022-01-18 06:27

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