llvm/clang/lib/AST/VTableBuilder.cpp

//===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This contains code dealing with generation of the layout of virtual tables.
//
//===----------------------------------------------------------------------===//

#include "clang/AST/VTableBuilder.h"
#include "clang/AST/ASTContext.h"
#include "clang/AST/ASTDiagnostic.h"
#include "clang/AST/CXXInheritance.h"
#include "clang/AST/RecordLayout.h"
#include "clang/Basic/TargetInfo.h"
#include "llvm/ADT/SetOperations.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Format.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cstdio>

usingnamespaceclang;

#define DUMP_OVERRIDERS …

namespace {

/// BaseOffset - Represents an offset from a derived class to a direct or
/// indirect base class.
struct BaseOffset { … };

/// FinalOverriders - Contains the final overrider member functions for all
/// member functions in the base subobjects of a class.
class FinalOverriders { … };

FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
                                 CharUnits MostDerivedClassOffset,
                                 const CXXRecordDecl *LayoutClass)
  : … { … }

static BaseOffset ComputeBaseOffset(const ASTContext &Context,
                                    const CXXRecordDecl *DerivedRD,
                                    const CXXBasePath &Path) { … }

static BaseOffset ComputeBaseOffset(const ASTContext &Context,
                                    const CXXRecordDecl *BaseRD,
                                    const CXXRecordDecl *DerivedRD) { … }

static BaseOffset
ComputeReturnAdjustmentBaseOffset(ASTContext &Context,
                                  const CXXMethodDecl *DerivedMD,
                                  const CXXMethodDecl *BaseMD) { … }

void
FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
                              CharUnits OffsetInLayoutClass,
                              SubobjectOffsetMapTy &SubobjectOffsets,
                              SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
                              SubobjectCountMapTy &SubobjectCounts) { … }

void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
                           VisitedVirtualBasesSetTy &VisitedVirtualBases) { … }

/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
struct VCallOffsetMap { … };

static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
                                    const CXXMethodDecl *RHS) { … }

bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
                                                const CXXMethodDecl *RHS) { … }

bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD,
                                    CharUnits OffsetOffset) { … }

CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) { … }

/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
class VCallAndVBaseOffsetBuilder { … };

void
VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
                                                    bool BaseIsVirtual,
                                                    CharUnits RealBaseOffset) { … }

CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const { … }

void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base,
                                                 CharUnits VBaseOffset) { … }

void
VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
                                            CharUnits OffsetInLayoutClass) { … }

/// ItaniumVTableBuilder - Class for building vtable layout information.
class ItaniumVTableBuilder { … };

void ItaniumVTableBuilder::AddThunk(const CXXMethodDecl *MD,
                                    const ThunkInfo &Thunk) { … }

OverriddenMethodsSetTy;

/// Visit all the methods overridden by the given method recursively,
/// in a depth-first pre-order. The Visitor's visitor method returns a bool
/// indicating whether to continue the recursion for the given overridden
/// method (i.e. returning false stops the iteration).
template <class VisitorTy>
static void
visitAllOverriddenMethods(const CXXMethodDecl *MD, VisitorTy &Visitor) { … }

/// ComputeAllOverriddenMethods - Given a method decl, will return a set of all
/// the overridden methods that the function decl overrides.
static void
ComputeAllOverriddenMethods(const CXXMethodDecl *MD,
                            OverriddenMethodsSetTy& OverriddenMethods) { … }

void ItaniumVTableBuilder::ComputeThisAdjustments() { … }

ReturnAdjustment
ItaniumVTableBuilder::ComputeReturnAdjustment(BaseOffset Offset) { … }

BaseOffset ItaniumVTableBuilder::ComputeThisAdjustmentBaseOffset(
    BaseSubobject Base, BaseSubobject Derived) const { … }

ThisAdjustment ItaniumVTableBuilder::ComputeThisAdjustment(
    const CXXMethodDecl *MD, CharUnits BaseOffsetInLayoutClass,
    FinalOverriders::OverriderInfo Overrider) { … }

void ItaniumVTableBuilder::AddMethod(const CXXMethodDecl *MD,
                                     ReturnAdjustment ReturnAdjustment) { … }

/// OverridesIndirectMethodInBase - Return whether the given member function
/// overrides any methods in the set of given bases.
/// Unlike OverridesMethodInBase, this checks "overriders of overriders".
/// For example, if we have:
///
/// struct A { virtual void f(); }
/// struct B : A { virtual void f(); }
/// struct C : B { virtual void f(); }
///
/// OverridesIndirectMethodInBase will return true if given C::f as the method
/// and { A } as the set of bases.
static bool OverridesIndirectMethodInBases(
    const CXXMethodDecl *MD,
    ItaniumVTableBuilder::PrimaryBasesSetVectorTy &Bases) { … }

bool ItaniumVTableBuilder::IsOverriderUsed(
    const CXXMethodDecl *Overrider, CharUnits BaseOffsetInLayoutClass,
    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
    CharUnits FirstBaseOffsetInLayoutClass) const { … }

BasesSetVectorTy;

/// FindNearestOverriddenMethod - Given a method, returns the overridden method
/// from the nearest base. Returns null if no method was found.
/// The Bases are expected to be sorted in a base-to-derived order.
static const CXXMethodDecl *
FindNearestOverriddenMethod(const CXXMethodDecl *MD,
                            BasesSetVectorTy &Bases) { … }

void ItaniumVTableBuilder::AddMethods(
    BaseSubobject Base, CharUnits BaseOffsetInLayoutClass,
    const CXXRecordDecl *FirstBaseInPrimaryBaseChain,
    CharUnits FirstBaseOffsetInLayoutClass,
    PrimaryBasesSetVectorTy &PrimaryBases) { … }

void ItaniumVTableBuilder::LayoutVTable() { … }

void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
    BaseSubobject Base, bool BaseIsMorallyVirtual,
    bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) { … }

void
ItaniumVTableBuilder::LayoutSecondaryVTables(BaseSubobject Base,
                                             bool BaseIsMorallyVirtual,
                                             CharUnits OffsetInLayoutClass) { … }

void ItaniumVTableBuilder::DeterminePrimaryVirtualBases(
    const CXXRecordDecl *RD, CharUnits OffsetInLayoutClass,
    VisitedVirtualBasesSetTy &VBases) { … }

void ItaniumVTableBuilder::LayoutVTablesForVirtualBases(
    const CXXRecordDecl *RD, VisitedVirtualBasesSetTy &VBases) { … }

static void printThunkMethod(const ThunkInfo &Info, raw_ostream &Out) { … }

/// dumpLayout - Dump the vtable layout.
void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) { … }
}

static VTableLayout::AddressPointsIndexMapTy
MakeAddressPointIndices(const VTableLayout::AddressPointsMapTy &addressPoints,
                        unsigned numVTables) { … }

VTableLayout::VTableLayout(ArrayRef<size_t> VTableIndices,
                           ArrayRef<VTableComponent> VTableComponents,
                           ArrayRef<VTableThunkTy> VTableThunks,
                           const AddressPointsMapTy &AddressPoints)
    : … { … }

VTableLayout::~VTableLayout() { … }

bool VTableContextBase::hasVtableSlot(const CXXMethodDecl *MD) { … }

ItaniumVTableContext::ItaniumVTableContext(
    ASTContext &Context, VTableComponentLayout ComponentLayout)
    : … { … }

ItaniumVTableContext::~ItaniumVTableContext() { … }

uint64_t ItaniumVTableContext::getMethodVTableIndex(GlobalDecl GD) { … }

CharUnits
ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
                                                 const CXXRecordDecl *VBase) { … }

GlobalDecl ItaniumVTableContext::findOriginalMethod(GlobalDecl GD) { … }

const CXXMethodDecl *
ItaniumVTableContext::findOriginalMethodInMap(const CXXMethodDecl *MD) const { … }

static std::unique_ptr<VTableLayout>
CreateVTableLayout(const ItaniumVTableBuilder &Builder) { … }

void
ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) { … }

std::unique_ptr<VTableLayout>
ItaniumVTableContext::createConstructionVTableLayout(
    const CXXRecordDecl *MostDerivedClass, CharUnits MostDerivedClassOffset,
    bool MostDerivedClassIsVirtual, const CXXRecordDecl *LayoutClass) { … }

namespace {

// Vtables in the Microsoft ABI are different from the Itanium ABI.
//
// The main differences are:
//  1. Separate vftable and vbtable.
//
//  2. Each subobject with a vfptr gets its own vftable rather than an address
//     point in a single vtable shared between all the subobjects.
//     Each vftable is represented by a separate section and virtual calls
//     must be done using the vftable which has a slot for the function to be
//     called.
//
//  3. Virtual method definitions expect their 'this' parameter to point to the
//     first vfptr whose table provides a compatible overridden method.  In many
//     cases, this permits the original vf-table entry to directly call
//     the method instead of passing through a thunk.
//     See example before VFTableBuilder::ComputeThisOffset below.
//
//     A compatible overridden method is one which does not have a non-trivial
//     covariant-return adjustment.
//
//     The first vfptr is the one with the lowest offset in the complete-object
//     layout of the defining class, and the method definition will subtract
//     that constant offset from the parameter value to get the real 'this'
//     value.  Therefore, if the offset isn't really constant (e.g. if a virtual
//     function defined in a virtual base is overridden in a more derived
//     virtual base and these bases have a reverse order in the complete
//     object), the vf-table may require a this-adjustment thunk.
//
//  4. vftables do not contain new entries for overrides that merely require
//     this-adjustment.  Together with #3, this keeps vf-tables smaller and
//     eliminates the need for this-adjustment thunks in many cases, at the cost
//     of often requiring redundant work to adjust the "this" pointer.
//
//  5. Instead of VTT and constructor vtables, vbtables and vtordisps are used.
//     Vtordisps are emitted into the class layout if a class has
//      a) a user-defined ctor/dtor
//     and
//      b) a method overriding a method in a virtual base.
//
//  To get a better understanding of this code,
//  you might want to see examples in test/CodeGenCXX/microsoft-abi-vtables-*.cpp

class VFTableBuilder { … };

} // end namespace

// Let's study one class hierarchy as an example:
//   struct A {
//     virtual void f();
//     int x;
//   };
//
//   struct B : virtual A {
//     virtual void f();
//   };
//
// Record layouts:
//   struct A:
//   0 |   (A vftable pointer)
//   4 |   int x
//
//   struct B:
//   0 |   (B vbtable pointer)
//   4 |   struct A (virtual base)
//   4 |     (A vftable pointer)
//   8 |     int x
//
// Let's assume we have a pointer to the A part of an object of dynamic type B:
//   B b;
//   A *a = (A*)&b;
//   a->f();
//
// In this hierarchy, f() belongs to the vftable of A, so B::f() expects
// "this" parameter to point at the A subobject, which is B+4.
// In the B::f() prologue, it adjusts "this" back to B by subtracting 4,
// performed as a *static* adjustment.
//
// Interesting thing happens when we alter the relative placement of A and B
// subobjects in a class:
//   struct C : virtual B { };
//
//   C c;
//   A *a = (A*)&c;
//   a->f();
//
// Respective record layout is:
//   0 |   (C vbtable pointer)
//   4 |   struct A (virtual base)
//   4 |     (A vftable pointer)
//   8 |     int x
//  12 |   struct B (virtual base)
//  12 |     (B vbtable pointer)
//
// The final overrider of f() in class C is still B::f(), so B+4 should be
// passed as "this" to that code.  However, "a" points at B-8, so the respective
// vftable entry should hold a thunk that adds 12 to the "this" argument before
// performing a tail call to B::f().
//
// With this example in mind, we can now calculate the 'this' argument offset
// for the given method, relative to the beginning of the MostDerivedClass.
CharUnits
VFTableBuilder::ComputeThisOffset(FinalOverriders::OverriderInfo Overrider) { … }

// Things are getting even more complex when the "this" adjustment has to
// use a dynamic offset instead of a static one, or even two dynamic offsets.
// This is sometimes required when a virtual call happens in the middle of
// a non-most-derived class construction or destruction.
//
// Let's take a look at the following example:
//   struct A {
//     virtual void f();
//   };
//
//   void foo(A *a) { a->f(); }  // Knows nothing about siblings of A.
//
//   struct B : virtual A {
//     virtual void f();
//     B() {
//       foo(this);
//     }
//   };
//
//   struct C : virtual B {
//     virtual void f();
//   };
//
// Record layouts for these classes are:
//   struct A
//   0 |   (A vftable pointer)
//
//   struct B
//   0 |   (B vbtable pointer)
//   4 |   (vtordisp for vbase A)
//   8 |   struct A (virtual base)
//   8 |     (A vftable pointer)
//
//   struct C
//   0 |   (C vbtable pointer)
//   4 |   (vtordisp for vbase A)
//   8 |   struct A (virtual base)  // A precedes B!
//   8 |     (A vftable pointer)
//  12 |   struct B (virtual base)
//  12 |     (B vbtable pointer)
//
// When one creates an object of type C, the C constructor:
// - initializes all the vbptrs, then
// - calls the A subobject constructor
//   (initializes A's vfptr with an address of A vftable), then
// - calls the B subobject constructor
//   (initializes A's vfptr with an address of B vftable and vtordisp for A),
//   that in turn calls foo(), then
// - initializes A's vfptr with an address of C vftable and zeroes out the
//   vtordisp
//   FIXME: if a structor knows it belongs to MDC, why doesn't it use a vftable
//   without vtordisp thunks?
//   FIXME: how are vtordisp handled in the presence of nooverride/final?
//
// When foo() is called, an object with a layout of class C has a vftable
// referencing B::f() that assumes a B layout, so the "this" adjustments are
// incorrect, unless an extra adjustment is done.  This adjustment is called
// "vtordisp adjustment".  Vtordisp basically holds the difference between the
// actual location of a vbase in the layout class and the location assumed by
// the vftable of the class being constructed/destructed.  Vtordisp is only
// needed if "this" escapes a
// structor (or we can't prove otherwise).
// [i.e. vtordisp is a dynamic adjustment for a static adjustment, which is an
// estimation of a dynamic adjustment]
//
// foo() gets a pointer to the A vbase and doesn't know anything about B or C,
// so it just passes that pointer as "this" in a virtual call.
// If there was no vtordisp, that would just dispatch to B::f().
// However, B::f() assumes B+8 is passed as "this",
// yet the pointer foo() passes along is B-4 (i.e. C+8).
// An extra adjustment is needed, so we emit a thunk into the B vftable.
// This vtordisp thunk subtracts the value of vtordisp
// from the "this" argument (-12) before making a tailcall to B::f().
//
// Let's consider an even more complex example:
//   struct D : virtual B, virtual C {
//     D() {
//       foo(this);
//     }
//   };
//
//   struct D
//   0 |   (D vbtable pointer)
//   4 |   (vtordisp for vbase A)
//   8 |   struct A (virtual base)  // A precedes both B and C!
//   8 |     (A vftable pointer)
//  12 |   struct B (virtual base)  // B precedes C!
//  12 |     (B vbtable pointer)
//  16 |   struct C (virtual base)
//  16 |     (C vbtable pointer)
//
// When D::D() calls foo(), we find ourselves in a thunk that should tailcall
// to C::f(), which assumes C+8 as its "this" parameter.  This time, foo()
// passes along A, which is C-8.  The A vtordisp holds
//   "D.vbptr[index_of_A] - offset_of_A_in_D"
// and we statically know offset_of_A_in_D, so can get a pointer to D.
// When we know it, we can make an extra vbtable lookup to locate the C vbase
// and one extra static adjustment to calculate the expected value of C+8.
void VFTableBuilder::CalculateVtordispAdjustment(
    FinalOverriders::OverriderInfo Overrider, CharUnits ThisOffset,
    ThisAdjustment &TA) { … }

static void GroupNewVirtualOverloads(
    const CXXRecordDecl *RD,
    SmallVector<const CXXMethodDecl *, 10> &VirtualMethods) { … }

static bool isDirectVBase(const CXXRecordDecl *Base, const CXXRecordDecl *RD) { … }

void VFTableBuilder::AddMethods(BaseSubobject Base, unsigned BaseDepth,
                                const CXXRecordDecl *LastVBase,
                                BasesSetVectorTy &VisitedBases) { … }

static void PrintBasePath(const VPtrInfo::BasePath &Path, raw_ostream &Out) { … }

static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out,
                                         bool ContinueFirstLine) { … }

void VFTableBuilder::dumpLayout(raw_ostream &Out) { … }

static bool setsIntersect(const llvm::SmallPtrSet<const CXXRecordDecl *, 4> &A,
                          ArrayRef<const CXXRecordDecl *> B) { … }

static bool rebucketPaths(VPtrInfoVector &Paths);

/// Produces MSVC-compatible vbtable data.  The symbols produced by this
/// algorithm match those produced by MSVC 2012 and newer, which is different
/// from MSVC 2010.
///
/// MSVC 2012 appears to minimize the vbtable names using the following
/// algorithm.  First, walk the class hierarchy in the usual order, depth first,
/// left to right, to find all of the subobjects which contain a vbptr field.
/// Visiting each class node yields a list of inheritance paths to vbptrs.  Each
/// record with a vbptr creates an initially empty path.
///
/// To combine paths from child nodes, the paths are compared to check for
/// ambiguity.  Paths are "ambiguous" if multiple paths have the same set of
/// components in the same order.  Each group of ambiguous paths is extended by
/// appending the class of the base from which it came.  If the current class
/// node produced an ambiguous path, its path is extended with the current class.
/// After extending paths, MSVC again checks for ambiguity, and extends any
/// ambiguous path which wasn't already extended.  Because each node yields an
/// unambiguous set of paths, MSVC doesn't need to extend any path more than once
/// to produce an unambiguous set of paths.
///
/// TODO: Presumably vftables use the same algorithm.
void MicrosoftVTableContext::computeVTablePaths(bool ForVBTables,
                                                const CXXRecordDecl *RD,
                                                VPtrInfoVector &Paths) { … }

static bool extendPath(VPtrInfo &P) { … }

static bool rebucketPaths(VPtrInfoVector &Paths) { … }

MicrosoftVTableContext::~MicrosoftVTableContext() { … }

namespace {
FullPathTy;
}

// This recursive function finds all paths from a subobject centered at
// (RD, Offset) to the subobject located at IntroducingObject.
static void findPathsToSubobject(ASTContext &Context,
                                 const ASTRecordLayout &MostDerivedLayout,
                                 const CXXRecordDecl *RD, CharUnits Offset,
                                 BaseSubobject IntroducingObject,
                                 FullPathTy &FullPath,
                                 std::list<FullPathTy> &Paths) { … }

// Return the paths which are not subsets of other paths.
static void removeRedundantPaths(std::list<FullPathTy> &FullPaths) { … }

static CharUnits getOffsetOfFullPath(ASTContext &Context,
                                     const CXXRecordDecl *RD,
                                     const FullPathTy &FullPath) { … }

// We want to select the path which introduces the most covariant overrides.  If
// two paths introduce overrides which the other path doesn't contain, issue a
// diagnostic.
static const FullPathTy *selectBestPath(ASTContext &Context,
                                        const CXXRecordDecl *RD,
                                        const VPtrInfo &Info,
                                        std::list<FullPathTy> &FullPaths) { … }

static void computeFullPathsForVFTables(ASTContext &Context,
                                        const CXXRecordDecl *RD,
                                        VPtrInfoVector &Paths) { … }

static bool vfptrIsEarlierInMDC(const ASTRecordLayout &Layout,
                                const MethodVFTableLocation &LHS,
                                const MethodVFTableLocation &RHS) { … }

void MicrosoftVTableContext::computeVTableRelatedInformation(
    const CXXRecordDecl *RD) { … }

void MicrosoftVTableContext::dumpMethodLocations(
    const CXXRecordDecl *RD, const MethodVFTableLocationsTy &NewMethods,
    raw_ostream &Out) { … }

const VirtualBaseInfo &MicrosoftVTableContext::computeVBTableRelatedInformation(
    const CXXRecordDecl *RD) { … }

unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived,
                                                 const CXXRecordDecl *VBase) { … }

const VPtrInfoVector &
MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) { … }

const VPtrInfoVector &
MicrosoftVTableContext::getVFPtrOffsets(const CXXRecordDecl *RD) { … }

const VTableLayout &
MicrosoftVTableContext::getVFTableLayout(const CXXRecordDecl *RD,
                                         CharUnits VFPtrOffset) { … }

MethodVFTableLocation
MicrosoftVTableContext::getMethodVFTableLocation(GlobalDecl GD) { … }