Coverage Report

Created: 2019-07-24 05:18

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