diff options
Diffstat (limited to 'lib/CodeGen/CGVTables.cpp')
| -rw-r--r-- | lib/CodeGen/CGVTables.cpp | 3185 |
1 files changed, 3185 insertions, 0 deletions
diff --git a/lib/CodeGen/CGVTables.cpp b/lib/CodeGen/CGVTables.cpp new file mode 100644 index 0000000000..c099047f1c --- /dev/null +++ b/lib/CodeGen/CGVTables.cpp @@ -0,0 +1,3185 @@ +//===--- CGVtables.cpp - Emit LLVM Code for C++ vtables -------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This contains code dealing with C++ code generation of virtual tables. +// +//===----------------------------------------------------------------------===// + +#include "CodeGenModule.h" +#include "CodeGenFunction.h" +#include "clang/AST/CXXInheritance.h" +#include "clang/AST/RecordLayout.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SetVector.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/Format.h" +#include <algorithm> +#include <cstdio> + +using namespace clang; +using namespace CodeGen; + +namespace { + +/// BaseOffset - Represents an offset from a derived class to a direct or +/// indirect base class. +struct BaseOffset { + /// DerivedClass - The derived class. + const CXXRecordDecl *DerivedClass; + + /// VirtualBase - If the path from the derived class to the base class + /// involves a virtual base class, this holds its declaration. + const CXXRecordDecl *VirtualBase; + + /// NonVirtualOffset - The offset from the derived class to the base class. + /// (Or the offset from the virtual base class to the base class, if the + /// path from the derived class to the base class involves a virtual base + /// class. + int64_t NonVirtualOffset; + + BaseOffset() : DerivedClass(0), VirtualBase(0), NonVirtualOffset(0) { } + BaseOffset(const CXXRecordDecl *DerivedClass, + const CXXRecordDecl *VirtualBase, int64_t NonVirtualOffset) + : DerivedClass(DerivedClass), VirtualBase(VirtualBase), + NonVirtualOffset(NonVirtualOffset) { } + + bool isEmpty() const { return !NonVirtualOffset && !VirtualBase; } +}; + +/// FinalOverriders - Contains the final overrider member functions for all +/// member functions in the base subobjects of a class. +class FinalOverriders { +public: + /// OverriderInfo - Information about a final overrider. + struct OverriderInfo { + /// Method - The method decl of the overrider. + const CXXMethodDecl *Method; + + /// Offset - the base offset of the overrider in the layout class. + uint64_t Offset; + + OverriderInfo() : Method(0), Offset(0) { } + }; + +private: + /// MostDerivedClass - The most derived class for which the final overriders + /// are stored. + const CXXRecordDecl *MostDerivedClass; + + /// MostDerivedClassOffset - If we're building final overriders for a + /// construction vtable, this holds the offset from the layout class to the + /// most derived class. + const uint64_t MostDerivedClassOffset; + + /// LayoutClass - The class we're using for layout information. Will be + /// different than the most derived class if the final overriders are for a + /// construction vtable. + const CXXRecordDecl *LayoutClass; + + ASTContext &Context; + + /// MostDerivedClassLayout - the AST record layout of the most derived class. + const ASTRecordLayout &MostDerivedClassLayout; + + /// BaseSubobjectMethodPairTy - Uniquely identifies a member function + /// in a base subobject. + typedef std::pair<BaseSubobject, const CXXMethodDecl *> + BaseSubobjectMethodPairTy; + + typedef llvm::DenseMap<BaseSubobjectMethodPairTy, + OverriderInfo> OverridersMapTy; + + /// OverridersMap - The final overriders for all virtual member functions of + /// all the base subobjects of the most derived class. + OverridersMapTy OverridersMap; + + /// VisitedVirtualBases - A set of all the visited virtual bases, used to + /// avoid visiting virtual bases more than once. + llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases; + + typedef llvm::DenseMap<BaseSubobjectMethodPairTy, BaseOffset> + AdjustmentOffsetsMapTy; + + /// ReturnAdjustments - Holds return adjustments for all the overriders that + /// need to perform return value adjustments. + AdjustmentOffsetsMapTy ReturnAdjustments; + + // FIXME: We might be able to get away with making this a SmallSet. + typedef llvm::SmallSetVector<uint64_t, 2> OffsetSetVectorTy; + + /// SubobjectOffsetsMapTy - This map is used for keeping track of all the + /// base subobject offsets that a single class declaration might refer to. + /// + /// For example, in: + /// + /// struct A { virtual void f(); }; + /// struct B1 : A { }; + /// struct B2 : A { }; + /// struct C : B1, B2 { virtual void f(); }; + /// + /// when we determine that C::f() overrides A::f(), we need to update the + /// overriders map for both A-in-B1 and A-in-B2 and the subobject offsets map + /// will have the subobject offsets for both A copies. + typedef llvm::DenseMap<const CXXRecordDecl *, OffsetSetVectorTy> + SubobjectOffsetsMapTy; + + /// ComputeFinalOverriders - Compute the final overriders for a given base + /// subobject (and all its direct and indirect bases). + void ComputeFinalOverriders(BaseSubobject Base, + bool BaseSubobjectIsVisitedVBase, + uint64_t OffsetInLayoutClass, + SubobjectOffsetsMapTy &Offsets); + + /// AddOverriders - Add the final overriders for this base subobject to the + /// map of final overriders. + void AddOverriders(BaseSubobject Base, uint64_t OffsetInLayoutClass, + SubobjectOffsetsMapTy &Offsets); + + /// PropagateOverrider - Propagate the NewMD overrider to all the functions + /// that OldMD overrides. For example, if we have: + /// + /// struct A { virtual void f(); }; + /// struct B : A { virtual void f(); }; + /// struct C : B { virtual void f(); }; + /// + /// and we want to override B::f with C::f, we also need to override A::f with + /// C::f. + void PropagateOverrider(const CXXMethodDecl *OldMD, + BaseSubobject NewBase, + uint64_t OverriderOffsetInLayoutClass, + const CXXMethodDecl *NewMD, + SubobjectOffsetsMapTy &Offsets); + + static void MergeSubobjectOffsets(const SubobjectOffsetsMapTy &NewOffsets, + SubobjectOffsetsMapTy &Offsets); + +public: + FinalOverriders(const CXXRecordDecl *MostDerivedClass, + uint64_t MostDerivedClassOffset, + const CXXRecordDecl *LayoutClass); + + /// getOverrider - Get the final overrider for the given method declaration in + /// the given base subobject. + OverriderInfo getOverrider(BaseSubobject Base, + const CXXMethodDecl *MD) const { + assert(OverridersMap.count(std::make_pair(Base, MD)) && + "Did not find overrider!"); + + return OverridersMap.lookup(std::make_pair(Base, MD)); + } + + /// getReturnAdjustmentOffset - Get the return adjustment offset for the + /// method decl in the given base subobject. Returns an empty base offset if + /// no adjustment is needed. + BaseOffset getReturnAdjustmentOffset(BaseSubobject Base, + const CXXMethodDecl *MD) const { + return ReturnAdjustments.lookup(std::make_pair(Base, MD)); + } + + /// dump - dump the final overriders. + void dump() { + assert(VisitedVirtualBases.empty() && + "Visited virtual bases aren't empty!"); + dump(llvm::errs(), BaseSubobject(MostDerivedClass, 0)); + VisitedVirtualBases.clear(); + } + + /// dump - dump the final overriders for a base subobject, and all its direct + /// and indirect base subobjects. + void dump(llvm::raw_ostream &Out, BaseSubobject Base); +}; + +#define DUMP_OVERRIDERS 0 + +FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass, + uint64_t MostDerivedClassOffset, + const CXXRecordDecl *LayoutClass) + : MostDerivedClass(MostDerivedClass), + MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass), + Context(MostDerivedClass->getASTContext()), + MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) { + + // Compute the final overriders. + SubobjectOffsetsMapTy Offsets; + ComputeFinalOverriders(BaseSubobject(MostDerivedClass, 0), + /*BaseSubobjectIsVisitedVBase=*/false, + MostDerivedClassOffset, Offsets); + VisitedVirtualBases.clear(); + +#if DUMP_OVERRIDERS + // And dump them (for now). + dump(); + + // Also dump the base offsets (for now). + for (SubobjectOffsetsMapTy::const_iterator I = Offsets.begin(), + E = Offsets.end(); I != E; ++I) { + const OffsetSetVectorTy& OffsetSetVector = I->second; + + llvm::errs() << "Base offsets for "; + llvm::errs() << I->first->getQualifiedNameAsString() << '\n'; + + for (unsigned I = 0, E = OffsetSetVector.size(); I != E; ++I) + llvm::errs() << " " << I << " - " << OffsetSetVector[I] / 8 << '\n'; + } +#endif +} + +void FinalOverriders::AddOverriders(BaseSubobject Base, + uint64_t OffsetInLayoutClass, + SubobjectOffsetsMapTy &Offsets) { + const CXXRecordDecl *RD = Base.getBase(); + + for (CXXRecordDecl::method_iterator I = RD->method_begin(), + E = RD->method_end(); I != E; ++I) { + const CXXMethodDecl *MD = *I; + + if (!MD->isVirtual()) + continue; + + // First, propagate the overrider. + PropagateOverrider(MD, Base, OffsetInLayoutClass, MD, Offsets); + + // Add the overrider as the final overrider of itself. + OverriderInfo& Overrider = OverridersMap[std::make_pair(Base, MD)]; + assert(!Overrider.Method && "Overrider should not exist yet!"); + + Overrider.Offset = OffsetInLayoutClass; + Overrider.Method = MD; + } +} + +static BaseOffset ComputeBaseOffset(ASTContext &Context, + const CXXRecordDecl *DerivedRD, + const CXXBasePath &Path) { + int64_t NonVirtualOffset = 0; + + unsigned NonVirtualStart = 0; + const CXXRecordDecl *VirtualBase = 0; + + // First, look for the virtual base class. + for (unsigned I = 0, E = Path.size(); I != E; ++I) { + const CXXBasePathElement &Element = Path[I]; + + if (Element.Base->isVirtual()) { + // FIXME: Can we break when we find the first virtual base? + // (If we can't, can't we just iterate over the path in reverse order?) + NonVirtualStart = I + 1; + QualType VBaseType = Element.Base->getType(); + VirtualBase = + cast<CXXRecordDecl>(VBaseType->getAs<RecordType>()->getDecl()); + } + } + + // Now compute the non-virtual offset. + for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) { + const CXXBasePathElement &Element = Path[I]; + + // Check the base class offset. + const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class); + + const RecordType *BaseType = Element.Base->getType()->getAs<RecordType>(); + const CXXRecordDecl *Base = cast<CXXRecordDecl>(BaseType->getDecl()); + + NonVirtualOffset += Layout.getBaseClassOffset(Base); + } + + // FIXME: This should probably use CharUnits or something. Maybe we should + // even change the base offsets in ASTRecordLayout to be specified in + // CharUnits. + return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset / 8); + +} + +static BaseOffset ComputeBaseOffset(ASTContext &Context, + const CXXRecordDecl *BaseRD, + const CXXRecordDecl *DerivedRD) { + CXXBasePaths Paths(/*FindAmbiguities=*/false, + /*RecordPaths=*/true, /*DetectVirtual=*/false); + + if (!const_cast<CXXRecordDecl *>(DerivedRD)-> + isDerivedFrom(const_cast<CXXRecordDecl *>(BaseRD), Paths)) { + assert(false && "Class must be derived from the passed in base class!"); + return BaseOffset(); + } + + return ComputeBaseOffset(Context, DerivedRD, Paths.front()); +} + +static BaseOffset +ComputeReturnAdjustmentBaseOffset(ASTContext &Context, + const CXXMethodDecl *DerivedMD, + const CXXMethodDecl *BaseMD) { + const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>(); + const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>(); + + // Canonicalize the return types. + CanQualType CanDerivedReturnType = + Context.getCanonicalType(DerivedFT->getResultType()); + CanQualType CanBaseReturnType = + Context.getCanonicalType(BaseFT->getResultType()); + + assert(CanDerivedReturnType->getTypeClass() == + CanBaseReturnType->getTypeClass() && + "Types must have same type class!"); + + if (CanDerivedReturnType == CanBaseReturnType) { + // No adjustment needed. + return BaseOffset(); + } + + if (isa<ReferenceType>(CanDerivedReturnType)) { + CanDerivedReturnType = + CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType(); + CanBaseReturnType = + CanBaseReturnType->getAs<ReferenceType>()->getPointeeType(); + } else if (isa<PointerType>(CanDerivedReturnType)) { + CanDerivedReturnType = + CanDerivedReturnType->getAs<PointerType>()->getPointeeType(); + CanBaseReturnType = + CanBaseReturnType->getAs<PointerType>()->getPointeeType(); + } else { + assert(false && "Unexpected return type!"); + } + + // We need to compare unqualified types here; consider + // const T *Base::foo(); + // T *Derived::foo(); + if (CanDerivedReturnType.getUnqualifiedType() == + CanBaseReturnType.getUnqualifiedType()) { + // No adjustment needed. + return BaseOffset(); + } + + const CXXRecordDecl *DerivedRD = + cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl()); + + const CXXRecordDecl *BaseRD = + cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl()); + + return ComputeBaseOffset(Context, BaseRD, DerivedRD); +} + +void FinalOverriders::PropagateOverrider(const CXXMethodDecl *OldMD, + BaseSubobject NewBase, + uint64_t OverriderOffsetInLayoutClass, + const CXXMethodDecl *NewMD, + SubobjectOffsetsMapTy &Offsets) { + for (CXXMethodDecl::method_iterator I = OldMD->begin_overridden_methods(), + E = OldMD->end_overridden_methods(); I != E; ++I) { + const CXXMethodDecl *OverriddenMD = *I; + const CXXRecordDecl *OverriddenRD = OverriddenMD->getParent(); + + // We want to override OverriddenMD in all subobjects, for example: + // + /// struct A { virtual void f(); }; + /// struct B1 : A { }; + /// struct B2 : A { }; + /// struct C : B1, B2 { virtual void f(); }; + /// + /// When overriding A::f with C::f we need to do so in both A subobjects. + const OffsetSetVectorTy &OffsetVector = Offsets[OverriddenRD]; + + // Go through all the subobjects. + for (unsigned I = 0, E = OffsetVector.size(); I != E; ++I) { + uint64_t Offset = OffsetVector[I]; + + BaseSubobject OverriddenSubobject = BaseSubobject(OverriddenRD, Offset); + BaseSubobjectMethodPairTy SubobjectAndMethod = + std::make_pair(OverriddenSubobject, OverriddenMD); + + OverriderInfo &Overrider = OverridersMap[SubobjectAndMethod]; + + assert(Overrider.Method && "Did not find existing overrider!"); + + // Check if we need return adjustments or base adjustments. + // (We don't want to do this for pure virtual member functions). + if (!NewMD->isPure()) { + // Get the return adjustment base offset. + BaseOffset ReturnBaseOffset = + ComputeReturnAdjustmentBaseOffset(Context, NewMD, OverriddenMD); + + if (!ReturnBaseOffset.isEmpty()) { + // Store the return adjustment base offset. + ReturnAdjustments[SubobjectAndMethod] = ReturnBaseOffset; + } + } + + // Set the new overrider. + Overrider.Offset = OverriderOffsetInLayoutClass; + Overrider.Method = NewMD; + + // And propagate it further. + PropagateOverrider(OverriddenMD, NewBase, OverriderOffsetInLayoutClass, + NewMD, Offsets); + } + } +} + +void +FinalOverriders::MergeSubobjectOffsets(const SubobjectOffsetsMapTy &NewOffsets, + SubobjectOffsetsMapTy &Offsets) { + // Iterate over the new offsets. + for (SubobjectOffsetsMapTy::const_iterator I = NewOffsets.begin(), + E = NewOffsets.end(); I != E; ++I) { + const CXXRecordDecl *NewRD = I->first; + const OffsetSetVectorTy& NewOffsetVector = I->second; + + OffsetSetVectorTy &OffsetVector = Offsets[NewRD]; + + // Merge the new offsets set vector into the old. + OffsetVector.insert(NewOffsetVector.begin(), NewOffsetVector.end()); + } +} + +void FinalOverriders::ComputeFinalOverriders(BaseSubobject Base, + bool BaseSubobjectIsVisitedVBase, + uint64_t OffsetInLayoutClass, + SubobjectOffsetsMapTy &Offsets) { + const CXXRecordDecl *RD = Base.getBase(); + const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); + + SubobjectOffsetsMapTy NewOffsets; + + for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), + E = RD->bases_end(); I != E; ++I) { + const CXXRecordDecl *BaseDecl = + cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); + + // Ignore bases that don't have any virtual member functions. + if (!BaseDecl->isPolymorphic()) + continue; + + bool IsVisitedVirtualBase = BaseSubobjectIsVisitedVBase; + uint64_t BaseOffset; + uint64_t BaseOffsetInLayoutClass; + if (I->isVirtual()) { + if (!VisitedVirtualBases.insert(BaseDecl)) + IsVisitedVirtualBase = true; + BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); + + const ASTRecordLayout &LayoutClassLayout = + Context.getASTRecordLayout(LayoutClass); + BaseOffsetInLayoutClass = + LayoutClassLayout.getVBaseClassOffset(BaseDecl); + } else { + BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset(); + BaseOffsetInLayoutClass = Layout.getBaseClassOffset(BaseDecl) + + OffsetInLayoutClass; + } + + // Compute the final overriders for this base. + // We always want to compute the final overriders, even if the base is a + // visited virtual base. Consider: + // + // struct A { + // virtual void f(); + // virtual void g(); + // }; + // + // struct B : virtual A { + // void f(); + // }; + // + // struct C : virtual A { + // void g (); + // }; + // + // struct D : B, C { }; + // + // Here, we still want to compute the overriders for A as a base of C, + // because otherwise we'll miss that C::g overrides A::f. + ComputeFinalOverriders(BaseSubobject(BaseDecl, BaseOffset), + IsVisitedVirtualBase, BaseOffsetInLayoutClass, + NewOffsets); + } + + /// Now add the overriders for this particular subobject. + /// (We don't want to do this more than once for a virtual base). + if (!BaseSubobjectIsVisitedVBase) + AddOverriders(Base, OffsetInLayoutClass, NewOffsets); + + // And merge the newly discovered subobject offsets. + MergeSubobjectOffsets(NewOffsets, Offsets); + + /// Finally, add the offset for our own subobject. + Offsets[RD].insert(Base.getBaseOffset()); +} + +void FinalOverriders::dump(llvm::raw_ostream &Out, BaseSubobject Base) { + const CXXRecordDecl *RD = Base.getBase(); + const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); + + for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(), + E = RD->bases_end(); I != E; ++I) { + const CXXRecordDecl *BaseDecl = + cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl()); + + // Ignore bases that don't have any virtual member functions. + if (!BaseDecl->isPolymorphic()) + continue; + + uint64_t BaseOffset; + if (I->isVirtual()) { + if (!VisitedVirtualBases.insert(BaseDecl)) { + // We've visited this base before. + continue; + } + + BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl); + } else { + BaseOffset = Layout.getBaseClassOffset(BaseDecl) + + Base.getBaseOffset(); + } + + dump(Out, BaseSubobject(BaseDecl, BaseOffset)); + } + + Out << "Final overriders for (" << RD->getQualifiedNameAsString() << ", "; + Out << Base.getBaseOffset() / 8 << ")\n"; + + // Now dump the overriders for this base subobject. + for (CXXRecordDecl::method_iterator I = RD->method_begin(), + E = RD->method_end(); I != E; ++I) { + const CXXMethodDecl *MD = *I; + + if (!MD->isVirtual()) + continue; + + OverriderInfo Overrider = getOverrider(Base, MD); + + Out << " " << MD->getQualifiedNameAsString() << " - ("; + Out << Overrider.Method->getQualifiedNameAsString(); + Out << ", " << ", " << Overrider.Offset / 8 << ')'; + + AdjustmentOffsetsMapTy::const_iterator AI = + ReturnAdjustments.find(std::make_pair(Base, MD)); + if (AI != ReturnAdjustments.end()) { + const BaseOffset &Offset = AI->second; + + Out << " [ret-adj: "; + if (Offset.VirtualBase) + Out << Offset.VirtualBase->getQualifiedNameAsString() << " vbase, "; + + Out << Offset.NonVirtualOffset << " nv]"; + } + + Out << "\n"; + } +} + +/// VtableComponent - Represents a single component in a vtable. +class VtableComponent { +public: + enum Kind { + CK_VCallOffset, + CK_VBaseOffset, + CK_OffsetToTop, + CK_RTTI, + CK_FunctionPointer, + + /// CK_CompleteDtorPointer - A pointer to the complete destructor. + CK_CompleteDtorPointer, + + /// CK_DeletingDtorPointer - A pointer to the deleting destructor. + CK_DeletingDtorPointer, + + /// CK_UnusedFunctionPointer - In some cases, a vtable function pointer + /// will end up never being called. Such vtable function pointers are + /// represented as a CK_UnusedFunctionPointer. + CK_UnusedFunctionPointer + }; + + static VtableComponent MakeVCallOffset(int64_t Offset) { + return VtableComponent(CK_VCallOffset, Offset); + } + + static VtableComponent MakeVBaseOffset(int64_t Offset) { + return VtableComponent(CK_VBaseOffset, Offset); + } + + static VtableComponent MakeOffsetToTop(int64_t Offset) { + return VtableComponent(CK_OffsetToTop, Offset); + } + + static VtableComponent MakeRTTI(const CXXRecordDecl *RD) { + return VtableComponent(CK_RTTI, reinterpret_cast<uintptr_t>(RD)); + } + + static VtableComponent MakeFunction(const CXXMethodDecl *MD) { + assert(!isa<CXXDestructorDecl>(MD) && + "Don't use MakeFunction with destructors!"); + + return VtableComponent(CK_FunctionPointer, + reinterpret_cast<uintptr_t>(MD)); + } + + static VtableComponent MakeCompleteDtor(const CXXDestructorDecl *DD) { + return VtableComponent(CK_CompleteDtorPointer, + reinterpret_cast<uintptr_t>(DD)); + } + + static VtableComponent MakeDeletingDtor(const CXXDestructorDecl *DD) { + return VtableComponent(CK_DeletingDtorPointer, + reinterpret_cast<uintptr_t>(DD)); + } + + static VtableComponent MakeUnusedFunction(const CXXMethodDecl *MD) { + assert(!isa<CXXDestructorDecl>(MD) && + "Don't use MakeUnusedFunction with destructors!"); + return VtableComponent(CK_UnusedFunctionPointer, + reinterpret_cast<uintptr_t>(MD)); + } + + static VtableComponent getFromOpaqueInteger(uint64_t I) { + return VtableComponent(I); + } + + /// getKind - Get the kind of this vtable component. + Kind getKind() const { + return (Kind)(Value & 0x7); + } + + int64_t getVCallOffset() const { + assert(getKind() == CK_VCallOffset && "Invalid component kind!"); + + return getOffset(); + } + + int64_t getVBaseOffset() const { + assert(getKind() == CK_VBaseOffset && "Invalid component kind!"); + + return getOffset(); + } + + int64_t getOffsetToTop() const { + assert(getKind() == CK_OffsetToTop && "Invalid component kind!"); + + return getOffset(); + } + + const CXXRecordDecl *getRTTIDecl() const { + assert(getKind() == CK_RTTI && "Invalid component kind!"); + + return reinterpret_cast<CXXRecordDecl *>(getPointer()); + } + + const CXXMethodDecl *getFunctionDecl() const { + assert(getKind() == CK_FunctionPointer); + + return reinterpret_cast<CXXMethodDecl *>(getPointer()); + } + + const CXXDestructorDecl *getDestructorDecl() const { + assert((getKind() == CK_CompleteDtorPointer || + getKind() == CK_DeletingDtorPointer) && "Invalid component kind!"); + + return reinterpret_cast<CXXDestructorDecl *>(getPointer()); + } + + const CXXMethodDecl *getUnusedFunctionDecl() const { + assert(getKind() == CK_UnusedFunctionPointer); + + return reinterpret_cast<CXXMethodDecl *>(getPointer()); + } + +private: + VtableComponent(Kind ComponentKind, int64_t Offset) { + assert((ComponentKind == CK_VCallOffset || + ComponentKind == CK_VBaseOffset || + ComponentKind == CK_OffsetToTop) && "Invalid component kind!"); + assert(Offset <= ((1LL << 56) - 1) && "Offset is too big!"); + + Value = ((Offset << 3) | ComponentKind); + } + + VtableComponent(Kind ComponentKind, uintptr_t Ptr) { + assert((ComponentKind == CK_RTTI || + ComponentKind == CK_FunctionPointer || + ComponentKind == CK_CompleteDtorPointer || + ComponentKind == CK_DeletingDtorPointer || + ComponentKind == CK_UnusedFunctionPointer) && + "Invalid component kind!"); + + assert((Ptr & 7) == 0 && "Pointer not sufficiently aligned!"); + + Value = Ptr | ComponentKind; + } + + int64_t getOffset() const { + assert((getKind() == CK_VCallOffset || getKind() == CK_VBaseOffset || + getKind() == CK_OffsetToTop) && "Invalid component kind!"); + + return Value >> 3; + } + + uintptr_t getPointer() const { + assert((getKind() == CK_RTTI || + getKind() == CK_FunctionPointer || + getKind() == CK_CompleteDtorPointer || + getKind() == CK_DeletingDtorPointer || + getKind() == CK_UnusedFunctionPointer) && + "Invalid component kind!"); + + return static_cast<uintptr_t>(Value & ~7ULL); + } + + explicit VtableComponent(uint64_t Value) + : Value(Value) { } + + /// The kind is stored in the lower 3 bits of the value. For offsets, we + /// make use of the facts that classes can't be larger than 2^55 bytes, + /// so we store the offset in the lower part of the 61 bytes that remain. + /// (The reason that we're not simply using a PointerIntPair here is that we + /// need the offsets to be 64-bit, even when on a 32-bit machine). + int64_t Value; +}; + +/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable. +struct VCallOffsetMap { + + typedef std::pair<const CXXMethodDecl *, int64_t> MethodAndOffsetPairTy; + + /// Offsets - Keeps track of methods and their offsets. + // FIXME: This should be a real map and not a vector. + llvm::SmallVector<MethodAndOffsetPairTy, 16> Offsets; + + /// MethodsCanShareVCallOffset - Returns whether two virtual member functions + /// can share the same vcall offset. + static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, + const CXXMethodDecl *RHS); + +public: + /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the + /// add was successful, or false if there was already a member function with + /// the same signature in the map. + bool AddVCallOffset(const CXXMethodDecl *MD, int64_t OffsetOffset); + + /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the + /// vtable address point) for the given virtual member function. + int64_t getVCallOffsetOffset(const CXXMethodDecl *MD); + + // empty - Return whether the offset map is empty or not. + bool empty() const { return Offsets.empty(); } +}; + +static bool HasSameVirtualSignature(const CXXMethodDecl *LHS, + const CXXMethodDecl *RHS) { + ASTContext &C = LHS->getASTContext(); // TODO: thread this down + CanQual<FunctionProtoType> + LT = C.getCanonicalType(LHS->getType()).getAs<FunctionProtoType>(), + RT = C.getCanonicalType(RHS->getType()).getAs<FunctionProtoType>(); + + // Fast-path matches in the canonical types. + if (LT == RT) return true; + + // Force the signatures to match. We can't rely on the overrides + // list here because there isn't necessarily an inheritance + // relationship between the two methods. + if (LT.getQualifiers() != RT.getQualifiers() || + LT->getNumArgs() != RT->getNumArgs()) + return false; + for (unsigned I = 0, E = LT->getNumArgs(); I != E; ++I) + if (LT->getArgType(I) != RT->getArgType(I)) + return false; + return true; +} + +bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS, + const CXXMethodDecl *RHS) { + assert(LHS->isVirtual() && "LHS must be virtual!"); + assert(RHS->isVirtual() && "LHS must be virtual!"); + + // A destructor can share a vcall offset with another destructor. + if (isa<CXXDestructorDecl>(LHS)) + return isa<CXXDestructorDecl>(RHS); + + // FIXME: We need to check more things here. + + // The methods must have the same name. + DeclarationName LHSName = LHS->getDeclName(); + DeclarationName RHSName = RHS->getDeclName(); + if (LHSName != RHSName) + return false; + + // And the same signatures. + return HasSameVirtualSignature(LHS, RHS); +} + +bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD, + int64_t OffsetOffset) { + // Check if we can reuse an offset. + for (unsigned I = 0, E = Offsets.size(); I != E; ++I) { + if (MethodsCanShareVCallOffset(Offsets[I].first, MD)) + return false; + } + + // Add the offset. + Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset)); + return true; +} + +int64_t VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) { + // Look for an offset. + for (unsigned I = 0, E = Offsets.size(); I != E; ++I) { + if (MethodsCanShareVCallOffset(Offsets[I].first, MD)) + return Offsets[I].second; + } + + assert(false && "Should always find a vcall offset offset!"); + return 0; +} + +/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets. +class VCallAndVBaseOffsetBuilder { +public: + typedef llvm::DenseMap<const CXXRecordDecl *, int64_t> + VBaseOffsetOffsetsMapTy; + +private: + /// MostDerivedClass - The most derived class for which we're building vcall + /// and vbase offsets. + const CXXRecordDecl *MostDerivedClass; + + /// LayoutClass - The class we're using for layout information. Will be + /// different than the most derived class if we're building a construction + /// vtable. + const CXXRecordDecl *LayoutClass; + + /// Context - The ASTContext which we will use for layout information. + ASTContext &Context; + + /// Components - vcall and vbase offset components + typedef llvm::SmallVector<VtableComponent, 64> VtableComponentVectorTy; + VtableComponentVectorTy Components; + + /// VisitedVirtualBases - Visited virtual bases. + llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases; + + /// VCallOffsets - Keeps track of vcall offsets. + VCallOffsetMap VCallOffsets; + + + /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets, + /// relative to the address point. + VBaseOffsetOffsetsMapTy VBaseOffsetOffsets; + + /// FinalOverriders - The final overriders of the most derived class. + /// (Can be null when we're not building a vtable of the most derived class). + const FinalOverriders *Overriders; + + /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the + /// given base subobject. + void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual, + uint64_t RealBaseOffset); + + /// AddVCallOffsets - Add vcall offsets for the given base subobject. + void AddVCallOffsets(BaseSubobject Base, uint64_t VBaseOffset); + + /// AddVBaseOffsets - Add vbase offsets for the given class. + void AddVBaseOffsets(const CXXRecordDecl *Base, uint64_t OffsetInLayoutClass); + + /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in + /// bytes, relative to the vtable address point. + int64_t getCurrentOffsetOffset() const; + +public: + VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass, + const CXXRecordDecl *LayoutClass, + const FinalOverriders *Overriders, + BaseSubobject Base, bool BaseIsVirtual, + uint64_t OffsetInLayoutClass) + : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass), + Context(MostDerivedClass->getASTContext()), Overriders(Overriders) { + + // Add vcall and vbase offsets. + AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass); + } + + /// Methods for iterating over the components. + typedef VtableComponentVectorTy::const_reverse_iterator const_iterator; + const_iterator components_begin() const { return Components.rbegin(); } + const_iterator components_end() const { return Components.rend(); } + + const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; } + const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const { + return VBaseOffsetOffsets; + } +}; + +void +VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base, + bool BaseIsVirtual, + uint64_t RealBaseOffset) { + const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase()); + + // Itanium C++ ABI 2.5.2: + // ..in classes sharing a virtual table with a primary base class, the vcall + // and vbase offsets added by the derived class all come before the vcall + // and vbase offsets required by the base class, so that the latter may be + // laid out as required by the base class without regard to additions from + // the derived class(es). + + // (Since we're emitting the vcall and vbase offsets in reverse order, we'll + // emit them for the primary base first). + if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) { + bool PrimaryBaseIsVirtual = Layout.getPrimaryBaseWasVirtual(); + + uint64_t PrimaryBaseOffset; + + // Get the base offset of the primary base. + if (PrimaryBaseIsVirtual) { + assert(Layout.getVBaseClassOffset(PrimaryBase) == 0 && + "Primary vbase should have a zero offset!"); + + const ASTRecordLayout &MostDerivedClassLayout = + Context.getASTRecordLayout(MostDerivedClass); + + PrimaryBaseOffset = + MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase); + } else { + assert(Layout.getBaseClassOffset(PrimaryBase) == 0 && + "Primary base should have a zero offset!"); + + PrimaryBaseOffset = Base.getBaseOffset(); + } + + AddVCallAndVBaseOffsets(BaseSubobject(PrimaryBase, PrimaryBaseOffset), + PrimaryBaseIsVirtual, RealBaseOffset); + } + + AddVBaseOffsets(Base.getBase(), RealBaseOffset); + + // We only want to add vcall offsets for virtual bases. + if (BaseIsVirtual) + AddVCallOffsets(Base, RealBaseOffset); +} + +int64_t VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const { + // OffsetIndex is the index of this vcall or vbase offset, relative to the + // vtable address point. (We subtract 3 to account for the information just + // above the address point, the RTTI info, the offset to top, and the + // vcall offset itself). + int64_t OffsetIndex = -(int64_t)(3 + Components.size()); + + // FIXME: We shouldn't use / 8 here. + int64_t OffsetOffset = OffsetIndex * + (int64_t)Context.Target.getPointerWidth(0) / 8; + + return OffsetOffset; +} + +void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base, + uint64_t VBaseOffset) { + const CXXRecordDecl *RD = Base.getBase(); + const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); + + const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase(); + + // Handle the primary base first. + if (Prim |