From d376a04b6c147248b0ee7f81ef9d4317f6f8113c Mon Sep 17 00:00:00 2001 From: Reid Kleckner Date: Fri, 3 Jan 2014 00:14:35 +0000 Subject: [PATCH] [ms-cxxabi] Move VBTableBuilder from CodeGen over to AST/VTableBuilder.cpp Summary: No functionality change. This code should live here long-term because we should be able to use it to compute correct vftable names. It turns out that the most natural way to implement the naming algorithm is to use a caching layer similar to what we already have for virtual table info in VTableContext. Subsequent changes will take advantage of this to fix PR17748, where we have a vbtable name collision. Reviewers: majnemer CC: cfe-commits Differential Revision: http://llvm-reviews.chandlerc.com/D2499 git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@198380 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/VTableBuilder.h | 64 +++++-- lib/AST/VTableBuilder.cpp | 272 +++++++++++++++++++++++++++--- lib/CodeGen/CMakeLists.txt | 1 - lib/CodeGen/MicrosoftCXXABI.cpp | 145 +++++++++++++--- lib/CodeGen/MicrosoftVBTables.cpp | 233 ------------------------- lib/CodeGen/MicrosoftVBTables.h | 129 -------------- 6 files changed, 417 insertions(+), 427 deletions(-) delete mode 100644 lib/CodeGen/MicrosoftVBTables.cpp delete mode 100644 lib/CodeGen/MicrosoftVBTables.h diff --git a/include/clang/AST/VTableBuilder.h b/include/clang/AST/VTableBuilder.h index 02061d437d..355df9bbfb 100644 --- a/include/clang/AST/VTableBuilder.h +++ b/include/clang/AST/VTableBuilder.h @@ -20,7 +20,7 @@ #include "clang/AST/RecordLayout.h" #include "clang/Basic/ABI.h" #include "llvm/ADT/SetVector.h" -#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DenseMap.h" #include namespace clang { @@ -409,6 +409,43 @@ struct VFPtrInfo { CharUnits VFPtrFullOffset; }; +/// Holds information for a virtual base table for a single subobject. A record +/// may contain as many vbptrs as there are base subobjects. +struct VBTableInfo { + VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject) + : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject) { } + + /// The vbtable will hold all of the virtual bases of ReusingBase. This may + /// or may not be the same class as VBPtrSubobject.Base. A derived class will + /// reuse the vbptr of the first non-virtual base subobject that has one. + const CXXRecordDecl *ReusingBase; + + /// The vbptr is stored inside this subobject. + BaseSubobject VBPtrSubobject; + + /// The bases from the inheritance path that got used to mangle the vbtable + /// name. This is not really a full path like a CXXBasePath. It holds the + /// subset of records that need to be mangled into the vbtable symbol name in + /// order to get a unique name. + llvm::SmallVector MangledPath; +}; + +// FIXME: Don't store these by value, they contain vectors. +typedef SmallVector VBTableVector; + +/// All virtual base related information about a given record decl. Includes +/// information on all virtual base tables and the path components that are used +/// to mangle them. +struct VirtualBaseInfo { + /// A map from virtual base to vbtable index for doing a conversion from the + /// the derived class to the a base. + llvm::DenseMap VBTableIndices; + + /// Information on all virtual base tables used when this record is the most + /// derived class. + VBTableVector VBTables; +}; + class MicrosoftVTableContext : public VTableContextBase { public: struct MethodVFTableLocation { @@ -465,6 +502,8 @@ private: typedef llvm::DenseMap VFTableLayoutMapTy; VFTableLayoutMapTy VFTableLayouts; + llvm::DenseMap VBaseInfo; + typedef llvm::SmallSetVector BasesSetVectorTy; void enumerateVFPtrs(const CXXRecordDecl *MostDerivedClass, const ASTRecordLayout &MostDerivedClassLayout, @@ -482,18 +521,14 @@ private: const MethodVFTableLocationsTy &NewMethods, raw_ostream &); - typedef std::pair ClassPairTy; - typedef llvm::DenseMap VBTableIndicesTy; - VBTableIndicesTy VBTableIndices; - llvm::DenseSet ComputedVBTableIndices; - - void computeVBTableRelatedInformation(const CXXRecordDecl *RD); + const VirtualBaseInfo * + computeVBTableRelatedInformation(const CXXRecordDecl *RD); public: MicrosoftVTableContext(ASTContext &Context) : VTableContextBase(/*MS=*/true), Context(Context) {} - ~MicrosoftVTableContext() { llvm::DeleteContainerSeconds(VFTableLayouts); } + ~MicrosoftVTableContext(); const VFPtrListTy &getVFPtrOffsets(const CXXRecordDecl *RD); @@ -515,16 +550,13 @@ public: /// The vbtable is an array of i32 offsets. The first entry is a self entry, /// and the rest are offsets from the vbptr to virtual bases. unsigned getVBTableIndex(const CXXRecordDecl *Derived, - const CXXRecordDecl *VBase) { - computeVBTableRelatedInformation(Derived); - ClassPairTy Pair(Derived, VBase); - assert(VBTableIndices.count(Pair) == 1 && - "VBase must be a vbase of Derived"); - return VBTableIndices[Pair]; - } + const CXXRecordDecl *VBase); + + const VBTableVector &enumerateVBTables(const CXXRecordDecl *RD); static bool classof(const VTableContextBase *VT) { return VT->isMicrosoft(); } }; -} + +} // namespace clang #endif diff --git a/lib/AST/VTableBuilder.cpp b/lib/AST/VTableBuilder.cpp index 4b8bc1e4c5..e23eb32b4f 100644 --- a/lib/AST/VTableBuilder.cpp +++ b/lib/AST/VTableBuilder.cpp @@ -2633,6 +2633,8 @@ public: void dumpLayout(raw_ostream &); }; +} // end namespace + /// InitialOverriddenDefinitionCollector - Finds the set of least derived bases /// that define the given method. struct InitialOverriddenDefinitionCollector { @@ -2997,6 +2999,7 @@ void PrintBasePath(const VFPtrInfo::BasePath &Path, raw_ostream &Out) { } } +namespace { struct MicrosoftThunkInfoStableSortComparator { bool operator() (const ThunkInfo &LHS, const ThunkInfo &RHS) { if (LHS.This != RHS.This) @@ -3010,6 +3013,7 @@ struct MicrosoftThunkInfoStableSortComparator { return false; } }; +} static void dumpMicrosoftThunkAdjustment(const ThunkInfo &TI, raw_ostream &Out, bool ContinueFirstLine) { @@ -3160,6 +3164,220 @@ void VFTableBuilder::dumpLayout(raw_ostream &Out) { } } } + +namespace { + +struct VBTablePath; +typedef llvm::SmallVector VBTablePathVector; + +/// Produces MSVC-compatible vbtable data. The symbols produced by this builder +/// match those produced by MSVC 2012, which is different from MSVC 2010. +/// +/// Unlike Itanium, which uses only one vtable per class, MSVC uses a different +/// symbol for every "address point" installed in base subobjects. As a result, +/// we have to compute unique symbols for every table. Since there can be +/// multiple non-virtual base subobjects of the same class, combining the most +/// derived class with the base containing the vtable is insufficient. The most +/// trivial algorithm would be to mangle in the entire path from base to most +/// derived, but that would be too easy and would create unnecessarily large +/// symbols. ;) +/// +/// 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. +/// +/// The VBTableBuilder class attempts to implement this algorithm by repeatedly +/// bucketing paths together by sorting them. +/// +/// TODO: Presumably vftables use the same algorithm. +/// +/// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting +/// duplicate vbtables with different symbols. + +class VBTableBuilder { +public: + VBTableBuilder(ASTContext &Context, const CXXRecordDecl *MostDerived); + + void enumerateVBTables(VBTableVector &VBTables); + +private: + bool hasVBPtr(const CXXRecordDecl *RD); + + /// Enumerates paths to bases with vbptrs. The paths elements are compressed + /// to contain only the classes necessary to form an unambiguous path. + void findUnambiguousPaths(const CXXRecordDecl *ReusingBase, + BaseSubobject CurSubobject, + VBTablePathVector &Paths); + + void extendPath(VBTablePath *Info, bool SecondPass); + + bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, + bool SecondPass = false); + + ASTContext &Context; + + const CXXRecordDecl *MostDerived; + + /// Caches the layout of the most derived class. + const ASTRecordLayout &DerivedLayout; + + /// Set of vbases to avoid re-visiting the same vbases. + llvm::SmallPtrSet VBasesSeen; +}; + +/// Holds intermediate data about a path to a vbptr inside a base subobject. +struct VBTablePath { + VBTablePath(const VBTableInfo &VBInfo) + : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { } + + /// All the data needed to build a vbtable, minus the GlobalVariable whose + /// name we haven't computed yet. + VBTableInfo VBInfo; + + /// Next base to use for disambiguation. Can be null if we've already + /// disambiguated this path once. + const CXXRecordDecl *NextBase; +}; + +} // end namespace + +VBTableBuilder::VBTableBuilder(ASTContext &Context, + const CXXRecordDecl *MostDerived) + : Context(Context), MostDerived(MostDerived), + DerivedLayout(Context.getASTRecordLayout(MostDerived)) {} + +void VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) { + VBTablePathVector Paths; + findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived, + CharUnits::Zero()), Paths); + for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end(); + I != E; ++I) { + VBTablePath *P = *I; + VBTables.push_back(P->VBInfo); + } +} + + +void VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase, + BaseSubobject CurSubobject, + VBTablePathVector &Paths) { + size_t PathsStart = Paths.size(); + bool ReuseVBPtrFromBase = true; + const CXXRecordDecl *CurBase = CurSubobject.getBase(); + const ASTRecordLayout &Layout = Context.getASTRecordLayout(CurBase); + + // If this base has a vbptr, then we've found a path. These are not full + // paths, so we don't use CXXBasePath. + if (Layout.hasOwnVBPtr()) { + ReuseVBPtrFromBase = false; + VBTablePath *Info = new VBTablePath(VBTableInfo(ReusingBase, CurSubobject)); + Paths.push_back(Info); + } + + // Recurse onto any bases which themselves have virtual bases. + for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(), + E = CurBase->bases_end(); I != E; ++I) { + const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl(); + if (!Base->getNumVBases()) + continue; // Bases without virtual bases have no vbptrs. + CharUnits NextOffset; + const CXXRecordDecl *NextReusingBase = Base; + if (I->isVirtual()) { + if (!VBasesSeen.insert(Base)) + continue; // Don't visit virtual bases twice. + NextOffset = DerivedLayout.getVBaseClassOffset(Base); + } else { + NextOffset = (CurSubobject.getBaseOffset() + + Layout.getBaseClassOffset(Base)); + + // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr + // from the first non-virtual base with vbases for its vbptr. + if (ReuseVBPtrFromBase) { + NextReusingBase = ReusingBase; + ReuseVBPtrFromBase = false; + } + } + + size_t NumPaths = Paths.size(); + findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset), + Paths); + + // Tag paths through this base with the base itself. We might use it to + // disambiguate. + for (size_t I = NumPaths, E = Paths.size(); I != E; ++I) + Paths[I]->NextBase = Base; + } + + bool AmbiguousPaths = rebucketPaths(Paths, PathsStart); + if (AmbiguousPaths) + rebucketPaths(Paths, PathsStart, /*SecondPass=*/true); + +#ifndef NDEBUG + // Check that the paths are in fact unique. + for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) { + assert(Paths[I]->VBInfo.MangledPath != Paths[I - 1]->VBInfo.MangledPath && + "vbtable paths are not unique"); + } +#endif +} + +static bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) { + return LHS->VBInfo.MangledPath < RHS->VBInfo.MangledPath; +} + +void VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) { + assert(P->NextBase || SecondPass); + if (P->NextBase) { + P->VBInfo.MangledPath.push_back(P->NextBase); + P->NextBase = 0; // Prevent the path from being extended twice. + } +} + +bool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, + bool SecondPass) { + // What we're essentially doing here is bucketing together ambiguous paths. + // Any bucket with more than one path in it gets extended by NextBase, which + // is usually the direct base of the inherited the vbptr. This code uses a + // sorted vector to implement a multiset to form the buckets. Note that the + // ordering is based on pointers, but it doesn't change our output order. The + // current algorithm is designed to match MSVC 2012's names. + // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft. + VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1); + std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare); + bool AmbiguousPaths = false; + for (size_t I = 0, E = PathsSorted.size(); I != E;) { + // Scan forward to find the end of the bucket. + size_t BucketStart = I; + do { + ++I; + } while (I != E && PathsSorted[BucketStart]->VBInfo.MangledPath == + PathsSorted[I]->VBInfo.MangledPath); + + // If this bucket has multiple paths, extend them all. + if (I - BucketStart > 1) { + AmbiguousPaths = true; + for (size_t II = BucketStart; II != I; ++II) + extendPath(PathsSorted[II], SecondPass); + } + } + return AmbiguousPaths; +} + +MicrosoftVTableContext::~MicrosoftVTableContext() { + llvm::DeleteContainerSeconds(VFTableLayouts); + llvm::DeleteContainerSeconds(VBaseInfo); } void MicrosoftVTableContext::enumerateVFPtrs( @@ -3373,39 +3591,51 @@ void MicrosoftVTableContext::dumpMethodLocations( } } -void MicrosoftVTableContext::computeVBTableRelatedInformation( +const VirtualBaseInfo *MicrosoftVTableContext::computeVBTableRelatedInformation( const CXXRecordDecl *RD) { - if (ComputedVBTableIndices.count(RD)) - return; - ComputedVBTableIndices.insert(RD); + VirtualBaseInfo *&Entry = VBaseInfo[RD]; + if (Entry) + return Entry; - const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); - BasesSetVectorTy VisitedBases; + Entry = new VirtualBaseInfo(); + + VBTableBuilder(Context, RD).enumerateVBTables(Entry->VBTables); // First, see if the Derived class shared the vbptr with a non-virtual base. + const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD); if (const CXXRecordDecl *VBPtrBase = Layout.getBaseSharingVBPtr()) { - // If the Derived class shares the vbptr with a non-virtual base, - // it inherits its vbase indices. - computeVBTableRelatedInformation(VBPtrBase); - for (CXXRecordDecl::base_class_const_iterator I = VBPtrBase->vbases_begin(), - E = VBPtrBase->vbases_end(); I != E; ++I) { - const CXXRecordDecl *SubVBase = I->getType()->getAsCXXRecordDecl(); - assert(VBTableIndices.count(ClassPairTy(VBPtrBase, SubVBase))); - VBTableIndices[ClassPairTy(RD, SubVBase)] = - VBTableIndices[ClassPairTy(VBPtrBase, SubVBase)]; - VisitedBases.insert(SubVBase); - } + // If the Derived class shares the vbptr with a non-virtual base, the shared + // virtual bases come first so that the layout is the same. + const VirtualBaseInfo *BaseInfo = + computeVBTableRelatedInformation(VBPtrBase); + Entry->VBTableIndices.insert(BaseInfo->VBTableIndices.begin(), + BaseInfo->VBTableIndices.end()); } // New vbases are added to the end of the vbtable. // Skip the self entry and vbases visited in the non-virtual base, if any. - unsigned VBTableIndex = 1 + VisitedBases.size(); + unsigned VBTableIndex = 1 + Entry->VBTableIndices.size(); for (CXXRecordDecl::base_class_const_iterator I = RD->vbases_begin(), - E = RD->vbases_end(); I != E; ++I) { + E = RD->vbases_end(); + I != E; ++I) { const CXXRecordDecl *CurVBase = I->getType()->getAsCXXRecordDecl(); - if (VisitedBases.insert(CurVBase)) - VBTableIndices[ClassPairTy(RD, CurVBase)] = VBTableIndex++; + if (!Entry->VBTableIndices.count(CurVBase)) + Entry->VBTableIndices[CurVBase] = VBTableIndex++; } + + return Entry; +} + +unsigned MicrosoftVTableContext::getVBTableIndex(const CXXRecordDecl *Derived, + const CXXRecordDecl *VBase) { + const VirtualBaseInfo *VBInfo = computeVBTableRelatedInformation(Derived); + assert(VBInfo->VBTableIndices.count(VBase)); + return VBInfo->VBTableIndices.find(VBase)->second; +} + +const VBTableVector & +MicrosoftVTableContext::enumerateVBTables(const CXXRecordDecl *RD) { + return computeVBTableRelatedInformation(RD)->VBTables; } const MicrosoftVTableContext::VFPtrListTy & diff --git a/lib/CodeGen/CMakeLists.txt b/lib/CodeGen/CMakeLists.txt index c78d17b6a0..2bac3485d7 100644 --- a/lib/CodeGen/CMakeLists.txt +++ b/lib/CodeGen/CMakeLists.txt @@ -55,7 +55,6 @@ add_clang_library(clangCodeGen CodeGenTypes.cpp ItaniumCXXABI.cpp MicrosoftCXXABI.cpp - MicrosoftVBTables.cpp ModuleBuilder.cpp TargetInfo.cpp ) diff --git a/lib/CodeGen/MicrosoftCXXABI.cpp b/lib/CodeGen/MicrosoftCXXABI.cpp index 62b7f43022..3a16525d69 100644 --- a/lib/CodeGen/MicrosoftCXXABI.cpp +++ b/lib/CodeGen/MicrosoftCXXABI.cpp @@ -17,7 +17,6 @@ #include "CGCXXABI.h" #include "CodeGenModule.h" #include "CGVTables.h" -#include "MicrosoftVBTables.h" #include "clang/AST/Decl.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/VTableBuilder.h" @@ -28,6 +27,12 @@ using namespace CodeGen; namespace { +/// Holds all the vbtable globals for a given class. +struct VBTableGlobals { + const VBTableVector *VBTables; + SmallVector Globals; +}; + class MicrosoftCXXABI : public CGCXXABI { public: MicrosoftCXXABI(CodeGenModule &CGM) : CGCXXABI(CGM) {} @@ -189,6 +194,13 @@ public: void emitVirtualInheritanceTables(const CXXRecordDecl *RD); + llvm::GlobalVariable * + getAddrOfVBTable(const VBTableInfo &VBT, const CXXRecordDecl *RD, + llvm::GlobalVariable::LinkageTypes Linkage); + + void emitVBTableDefinition(const VBTableInfo &VBT, const CXXRecordDecl *RD, + llvm::GlobalVariable *GV) const; + void setThunkLinkage(llvm::Function *Thunk, bool ForVTable) { Thunk->setLinkage(llvm::GlobalValue::WeakAnyLinkage); } @@ -312,7 +324,7 @@ private: void EmitVBPtrStores(CodeGenFunction &CGF, const CXXRecordDecl *RD); /// \brief Caching wrapper around VBTableBuilder::enumerateVBTables(). - const VBTableVector &EnumerateVBTables(const CXXRecordDecl *RD); + const VBTableGlobals &enumerateVBTables(const CXXRecordDecl *RD); /// \brief Generate a thunk for calling a virtual member function MD. llvm::Function *EmitVirtualMemPtrThunk(const CXXMethodDecl *MD, @@ -369,7 +381,7 @@ private: /// \brief All the vbtables which have been referenced. - llvm::DenseMap VBTablesMap; + llvm::DenseMap VBTablesMap; /// Info on the global variable used to guard initialization of static locals. /// The BitIndex field is only used for externally invisible declarations. @@ -550,21 +562,23 @@ void MicrosoftCXXABI::EmitCXXConstructors(const CXXConstructorDecl *D) { void MicrosoftCXXABI::EmitVBPtrStores(CodeGenFunction &CGF, const CXXRecordDecl *RD) { + llvm::GlobalVariable::LinkageTypes Linkage = CGM.getVTableLinkage(RD); llvm::Value *ThisInt8Ptr = CGF.Builder.CreateBitCast(getThisValue(CGF), CGM.Int8PtrTy, "this.int8"); - const VBTableVector &VBTables = EnumerateVBTables(RD); - for (VBTableVector::const_iterator I = VBTables.begin(), E = VBTables.end(); - I != E; ++I) { + const VBTableGlobals &VBGlobals = enumerateVBTables(RD); + for (unsigned I = 0, E = VBGlobals.VBTables->size(); I != E; ++I) { + const VBTableInfo &VBT = (*VBGlobals.VBTables)[I]; + llvm::GlobalVariable *GV = VBGlobals.Globals[I]; const ASTRecordLayout &SubobjectLayout = - CGM.getContext().getASTRecordLayout(I->VBPtrSubobject.getBase()); - uint64_t Offs = (I->VBPtrSubobject.getBaseOffset() + + CGM.getContext().getASTRecordLayout(VBT.VBPtrSubobject.getBase()); + uint64_t Offs = (VBT.VBPtrSubobject.getBaseOffset() + SubobjectLayout.getVBPtrOffset()).getQuantity(); llvm::Value *VBPtr = CGF.Builder.CreateConstInBoundsGEP1_64(ThisInt8Ptr, Offs); - VBPtr = CGF.Builder.CreateBitCast(VBPtr, I->GV->getType()->getPointerTo(0), - "vbptr." + I->ReusingBase->getName()); - CGF.Builder.CreateStore(I->GV, VBPtr); + VBPtr = CGF.Builder.CreateBitCast(VBPtr, GV->getType()->getPointerTo(0), + "vbptr." + VBT.ReusingBase->getName()); + CGF.Builder.CreateStore(GV, VBPtr); } } @@ -986,20 +1000,30 @@ void MicrosoftCXXABI::EmitVirtualDestructorCall(CodeGenFunction &CGF, ImplicitParam, Context.IntTy, 0, 0); } -const VBTableVector & -MicrosoftCXXABI::EnumerateVBTables(const CXXRecordDecl *RD) { +const VBTableGlobals & +MicrosoftCXXABI::enumerateVBTables(const CXXRecordDecl *RD) { // At this layer, we can key the cache off of a single class, which is much - // easier than caching at the GlobalVariable layer. - llvm::DenseMap::iterator I; - bool added; - llvm::tie(I, added) = VBTablesMap.insert(std::make_pair(RD, VBTableVector())); - VBTableVector &VBTables = I->second; - if (!added) - return VBTables; - - VBTableBuilder(CGM, RD).enumerateVBTables(VBTables); + // easier than caching each vbtable individually. + llvm::DenseMap::iterator Entry; + bool Added; + llvm::tie(Entry, Added) = VBTablesMap.insert(std::make_pair(RD, VBTableGlobals())); + VBTableGlobals &VBGlobals = Entry->second; + if (!Added) + return VBGlobals; + + MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext(); + VBGlobals.VBTables = &Context.enumerateVBTables(RD); + + // Cache the globals for all vbtables so we don't have to recompute the + // mangled names. + llvm::GlobalVariable::LinkageTypes Linkage = CGM.getVTableLinkage(RD); + for (VBTableVector::const_iterator I = VBGlobals.VBTables->begin(), + E = VBGlobals.VBTables->end(); + I != E; ++I) { + VBGlobals.Globals.push_back(getAddrOfVBTable(*I, RD, Linkage)); + } - return VBTables; + return VBGlobals; } llvm::Function * @@ -1039,13 +1063,80 @@ MicrosoftCXXABI::EmitVirtualMemPtrThunk(const CXXMethodDecl *MD, } void MicrosoftCXXABI::emitVirtualInheritanceTables(const CXXRecordDecl *RD) { - const VBTableVector &VBTables = EnumerateVBTables(RD); - llvm::GlobalVariable::LinkageTypes Linkage = CGM.getVTableLinkage(RD); + const VBTableGlobals &VBGlobals = enumerateVBTables(RD); + for (unsigned I = 0, E = VBGlobals.VBTables->size(); I != E; ++I) { + const VBTableInfo &VBT = (*VBGlobals.VBTables)[I]; + llvm::GlobalVariable *GV = VBGlobals.Globals[I]; + emitVBTableDefinition(VBT, RD, GV); + } +} + +llvm::GlobalVariable * +MicrosoftCXXABI::getAddrOfVBTable(const VBTableInfo &VBT, + const CXXRecordDecl *RD, + llvm::GlobalVariable::LinkageTypes Linkage) { + SmallString<256> OutName; + llvm::raw_svector_ostream Out(OutName); + MicrosoftMangleContext &Mangler = + cast(CGM.getCXXABI().getMangleContext()); + Mangler.mangleCXXVBTable(RD, VBT.MangledPath, Out); + Out.flush(); + StringRef Name = OutName.str(); + + llvm::ArrayType *VBTableType = + llvm::ArrayType::get(CGM.IntTy, 1 + VBT.ReusingBase->getNumVBases()); + + assert(!CGM.getModule().getNamedGlobal(Name) && + "vbtable with this name already exists: mangling bug?"); + llvm::GlobalVariable *GV = + CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType, Linkage); + GV->setUnnamedAddr(true); + return GV; +} + +void MicrosoftCXXABI::emitVBTableDefinition(const VBTableInfo &VBT, + const CXXRecordDecl *RD, + llvm::GlobalVariable *GV) const { + const CXXRecordDecl *ReusingBase = VBT.ReusingBase; + + assert(RD->getNumVBases() && ReusingBase->getNumVBases() && + "should only emit vbtables for classes with vbtables"); - for (VBTableVector::const_iterator I = VBTables.begin(), E = VBTables.end(); + const ASTRecordLayout &BaseLayout = + CGM.getContext().getASTRecordLayout(VBT.VBPtrSubobject.getBase()); + const ASTRecordLayout &DerivedLayout = + CGM.getContext().getASTRecordLayout(RD); + + SmallVector Offsets(1 + ReusingBase->getNumVBases(), 0); + + // The offset from ReusingBase's vbptr to itself always leads. + CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset(); + Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity()); + + MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext(); + for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(), + E = ReusingBase->vbases_end(); I != E; ++I) { - I->EmitVBTableDefinition(CGM, RD, Linkage); + const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl(); + CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase); + assert(!Offset.isNegative()); + // Make it relative to the subobject vbptr. + Offset -= VBT.VBPtrSubobject.getBaseOffset() + VBPtrOffset; + unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase); + assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?"); + Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity()); } + + assert(Offsets.size() == + cast(cast(GV->getType()) + ->getElementType())->getNumElements()); + llvm::ArrayType *VBTableType = + llvm::ArrayType::get(CGM.IntTy, Offsets.size()); + llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets); + GV->setInitializer(Init); + + // Set the right visibility. + CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable); } llvm::Value *MicrosoftCXXABI::performThisAdjustment(CodeGenFunction &CGF, diff --git a/lib/CodeGen/MicrosoftVBTables.cpp b/lib/CodeGen/MicrosoftVBTables.cpp deleted file mode 100644 index dabf52c1cc..0000000000 --- a/lib/CodeGen/MicrosoftVBTables.cpp +++ /dev/null @@ -1,233 +0,0 @@ -//===--- MicrosoftVBTables.cpp - Virtual Base Table Emission --------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This class generates data about MSVC virtual base tables. -// -//===----------------------------------------------------------------------===// - -#include "MicrosoftVBTables.h" -#include "CodeGenModule.h" -#include "CGCXXABI.h" - -namespace clang { -namespace CodeGen { - -/// Holds intermediate data about a path to a vbptr inside a base subobject. -struct VBTablePath { - VBTablePath(const VBTableInfo &VBInfo) - : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { } - - /// All the data needed to build a vbtable, minus the GlobalVariable whose - /// name we haven't computed yet. - VBTableInfo VBInfo; - - /// Next base to use for disambiguation. Can be null if we've already - /// disambiguated this path once. - const CXXRecordDecl *NextBase; - - /// Path is not really a full path like a CXXBasePath. It holds the subset of - /// records that need to be mangled into the vbtable symbol name in order to get - /// a unique name. - llvm::SmallVector Path; -}; - -VBTableBuilder::VBTableBuilder(CodeGenModule &CGM, - const CXXRecordDecl *MostDerived) - : CGM(CGM), MostDerived(MostDerived), - DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {} - -void VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) { - VBTablePathVector Paths; - findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived, - CharUnits::Zero()), Paths); - for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end(); - I != E; ++I) { - VBTablePath *P = *I; - P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path); - VBTables.push_back(P->VBInfo); - } -} - - -void VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase, - BaseSubobject CurSubobject, - VBTablePathVector &Paths) { - size_t PathsStart = Paths.size(); - bool ReuseVBPtrFromBase = true; - const CXXRecordDecl *CurBase = CurSubobject.getBase(); - const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase); - - // If this base has a vbptr, then we've found a path. These are not full - // paths, so we don't use CXXBasePath. - if (Layout.hasOwnVBPtr()) { - ReuseVBPtrFromBase = false; - VBTablePath *Info = new VBTablePath( - VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0)); - Paths.push_back(Info); - } - - // Recurse onto any bases which themselves have virtual bases. - for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(), - E = CurBase->bases_end(); I != E; ++I) { - const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl(); - if (!Base->getNumVBases()) - continue; // Bases without virtual bases have no vbptrs. - CharUnits NextOffset; - const CXXRecordDecl *NextReusingBase = Base; - if (I->isVirtual()) { - if (!VBasesSeen.insert(Base)) - continue; // Don't visit virtual bases twice. - NextOffset = DerivedLayout.getVBaseClassOffset(Base); - } else { - NextOffset = (CurSubobject.getBaseOffset() + - Layout.getBaseClassOffset(Base)); - - // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr - // from the first non-virtual base with vbases for its vbptr. - if (ReuseVBPtrFromBase) { - NextReusingBase = ReusingBase; - ReuseVBPtrFromBase = false; - } - } - - size_t NumPaths = Paths.size(); - findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset), - Paths); - - // Tag paths through this base with the base itself. We might use it to - // disambiguate. - for (size_t I = NumPaths, E = Paths.size(); I != E; ++I) - Paths[I]->NextBase = Base; - } - - bool AmbiguousPaths = rebucketPaths(Paths, PathsStart); - if (AmbiguousPaths) - rebucketPaths(Paths, PathsStart, /*SecondPass=*/true); - -#ifndef NDEBUG - // Check that the paths are in fact unique. - for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) { - assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique"); - } -#endif -} - -static bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) { - return LHS->Path < RHS->Path; -} - -void VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) { - assert(P->NextBase || SecondPass); - if (P->NextBase) { - P->Path.push_back(P->NextBase); - P->NextBase = 0; // Prevent the path from being extended twice. - } -} - -bool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, - bool SecondPass) { - // What we're essentially doing here is bucketing together ambiguous paths. - // Any bucket with more than one path in it gets extended by NextBase, which - // is usually the direct base of the inherited the vbptr. This code uses a - // sorted vector to implement a multiset to form the buckets. Note that the - // ordering is based on pointers, but it doesn't change our output order. The - // current algorithm is designed to match MSVC 2012's names. - // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft. - VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1); - std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare); - bool AmbiguousPaths = false; - for (size_t I = 0, E = PathsSorted.size(); I != E;) { - // Scan forward to find the end of the bucket. - size_t BucketStart = I; - do { - ++I; - } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path); - - // If this bucket has multiple paths, extend them all. - if (I - BucketStart > 1) { - AmbiguousPaths = true; - for (size_t II = BucketStart; II != I; ++II) - extendPath(PathsSorted[II], SecondPass); - } - } - return AmbiguousPaths; -} - -llvm::GlobalVariable * -VBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase, - ArrayRef BasePath) { - // Caching at this layer is redundant with the caching in EnumerateVBTables(). - - SmallString<256> OutName; - llvm::raw_svector_ostream Out(OutName); - MicrosoftMangleContext &Mangler = - cast(CGM.getCXXABI().getMangleContext()); - Mangler.mangleCXXVBTable(MostDerived, BasePath, Out); - Out.flush(); - StringRef Name = OutName.str(); - - llvm::ArrayType *VBTableType = - llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases()); - - assert(!CGM.getModule().getNamedGlobal(Name) && - "vbtable with this name already exists: mangling bug?"); - llvm::GlobalVariable *VBTable = - CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType, - llvm::GlobalValue::ExternalLinkage); - VBTable->setUnnamedAddr(true); - return VBTable; -} - -void VBTableInfo::EmitVBTableDefinition( - CodeGenModule &CGM, const CXXRecordDecl *RD, - llvm::GlobalVariable::LinkageTypes Linkage) const { - assert(RD->getNumVBases() && ReusingBase->getNumVBases() && - "should only emit vbtables for classes with vbtables"); - - const ASTRecordLayout &BaseLayout = - CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase()); - const ASTRecordLayout &DerivedLayout = - CGM.getContext().getASTRecordLayout(RD); - - SmallVector Offsets(1 + ReusingBase->getNumVBases(), 0); - - // The offset from ReusingBase's vbptr to itself always leads. - CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset(); - Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity()); - - MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext(); - for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(), - E = ReusingBase->vbases_end(); I != E; ++I) { - const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl(); - CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase); - assert(!Offset.isNegative()); - // Make it relative to the subobject vbptr. - Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset; - unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase); - assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?"); - Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity()); - } - - assert(Offsets.size() == - cast(cast(GV->getType()) - ->getElementType())->getNumElements()); - llvm::ArrayType *VBTableType = - llvm::ArrayType::get(CGM.IntTy, Offsets.size()); - llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets); - GV->setInitializer(Init); - - // Set the correct linkage. - GV->setLinkage(Linkage); - - // Set the right visibility. - CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable); -} - -} // namespace CodeGen -} // namespace clang diff --git a/lib/CodeGen/MicrosoftVBTables.h b/lib/CodeGen/MicrosoftVBTables.h deleted file mode 100644 index 4ad8e07582..0000000000 --- a/lib/CodeGen/MicrosoftVBTables.h +++ /dev/null @@ -1,129 +0,0 @@ -//===--- MicrosoftVBTables.h - Virtual Base Table Emission ----------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This class generates data about MSVC virtual base tables. -// -//===----------------------------------------------------------------------===// - -#include "clang/AST/BaseSubobject.h" -#include "clang/Basic/LLVM.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/ArrayRef.h" -#include "llvm/IR/GlobalVariable.h" -#include - -namespace clang { - -class ASTRecordLayout; - -namespace CodeGen { - -class CodeGenModule; - -struct VBTableInfo { - VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject, - llvm::GlobalVariable *GV) - : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject), GV(GV) { } - - /// The vbtable will hold all of the virtual bases of ReusingBase. This may - /// or may not be the same class as VBPtrSubobject.Base. A derived class will - /// reuse the vbptr of the first non-virtual base subobject that has one. - const CXXRecordDecl *ReusingBase; - - /// The vbptr is stored inside this subobject. - BaseSubobject VBPtrSubobject; - - /// The GlobalVariable for this vbtable. - llvm::GlobalVariable *GV; - - /// \brief Emits a definition for GV by setting it's initializer. - void EmitVBTableDefinition(CodeGenModule &CGM, const CXXRecordDecl *RD, - llvm::GlobalVariable::LinkageTypes Linkage) const; -}; - -// These are embedded in a DenseMap and the elements are large, so we don't want -// SmallVector. -typedef std::vector VBTableVector; - -struct VBTablePath; - -typedef llvm::SmallVector VBTablePathVector; - -/// Produces MSVC-compatible vbtable data. The symbols produced by this builder -/// match those produced by MSVC 2012, which is different from MSVC 2010. -/// -/// Unlike Itanium, which uses only one vtable per class, MSVC uses a different -/// symbol for every "address point" installed in base subobjects. As a result, -/// we have to compute unique symbols for every table. Since there can be -/// multiple non-virtual base subobjects of the same class, combining the most -/// derived class with the base containing the vtable is insufficient. The most -/// trivial algorithm would be to mangle in the entire path from base to most -/// derived, but that would be too easy and would create unnecessarily large -/// symbols. ;) -/// -/// 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. -/// -/// The VBTableBuilder class attempts to implement this algorithm by repeatedly -/// bucketing paths together by sorting them. -/// -/// TODO: Presumably vftables use the same algorithm. -/// -/// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting -/// duplicate vbtables with different symbols. -class VBTableBuilder { -public: - VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived); - - void enumerateVBTables(VBTableVector &VBTables); - -private: - bool hasVBPtr(const CXXRecordDecl *RD); - - llvm::GlobalVariable *getAddrOfVBTable(const CXXRecordDecl *ReusingBase, - ArrayRef BasePath); - - /// Enumerates paths to bases with vbptrs. The paths elements are compressed - /// to contain only the classes necessary to form an unambiguous path. - void findUnambiguousPaths(const CXXRecordDecl *ReusingBase, - BaseSubobject CurSubobject, - VBTablePathVector &Paths); - - void extendPath(VBTablePath *Info, bool SecondPass); - - bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, - bool SecondPass = false); - - CodeGenModule &CGM; - - const CXXRecordDecl *MostDerived; - - /// Caches the layout of the most derived class. - const ASTRecordLayout &DerivedLayout; - - /// Set of vbases to avoid re-visiting the same vbases. - llvm::SmallPtrSet VBasesSeen; -}; - -} // namespace CodeGen - -} // namespace clang -- 2.40.0