1259701Sdim//===--- MicrosoftVBTables.cpp - Virtual Base Table Emission --------------===// 2259701Sdim// 3259701Sdim// The LLVM Compiler Infrastructure 4259701Sdim// 5259701Sdim// This file is distributed under the University of Illinois Open Source 6259701Sdim// License. See LICENSE.TXT for details. 7259701Sdim// 8259701Sdim//===----------------------------------------------------------------------===// 9259701Sdim// 10259701Sdim// This class generates data about MSVC virtual base tables. 11259701Sdim// 12259701Sdim//===----------------------------------------------------------------------===// 13259701Sdim 14259701Sdim#include "MicrosoftVBTables.h" 15259701Sdim#include "CodeGenModule.h" 16259701Sdim#include "CGCXXABI.h" 17259701Sdim 18259701Sdimnamespace clang { 19259701Sdimnamespace CodeGen { 20259701Sdim 21259701Sdim/// Holds intermediate data about a path to a vbptr inside a base subobject. 22259701Sdimstruct VBTablePath { 23259701Sdim VBTablePath(const VBTableInfo &VBInfo) 24259701Sdim : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { } 25259701Sdim 26259701Sdim /// All the data needed to build a vbtable, minus the GlobalVariable whose 27259701Sdim /// name we haven't computed yet. 28259701Sdim VBTableInfo VBInfo; 29259701Sdim 30259701Sdim /// Next base to use for disambiguation. Can be null if we've already 31259701Sdim /// disambiguated this path once. 32259701Sdim const CXXRecordDecl *NextBase; 33259701Sdim 34259701Sdim /// Path is not really a full path like a CXXBasePath. It holds the subset of 35259701Sdim /// records that need to be mangled into the vbtable symbol name in order to get 36259701Sdim /// a unique name. 37259701Sdim llvm::SmallVector<const CXXRecordDecl *, 1> Path; 38259701Sdim}; 39259701Sdim 40259701SdimVBTableBuilder::VBTableBuilder(CodeGenModule &CGM, 41259701Sdim const CXXRecordDecl *MostDerived) 42259701Sdim : CGM(CGM), MostDerived(MostDerived), 43259701Sdim DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {} 44259701Sdim 45259701Sdimvoid VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) { 46259701Sdim VBTablePathVector Paths; 47259701Sdim findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived, 48259701Sdim CharUnits::Zero()), Paths); 49259701Sdim for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end(); 50259701Sdim I != E; ++I) { 51259701Sdim VBTablePath *P = *I; 52259701Sdim P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path); 53259701Sdim VBTables.push_back(P->VBInfo); 54259701Sdim } 55259701Sdim} 56259701Sdim 57259701Sdim 58259701Sdimvoid VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase, 59259701Sdim BaseSubobject CurSubobject, 60259701Sdim VBTablePathVector &Paths) { 61259701Sdim size_t PathsStart = Paths.size(); 62259701Sdim bool ReuseVBPtrFromBase = true; 63259701Sdim const CXXRecordDecl *CurBase = CurSubobject.getBase(); 64259701Sdim const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase); 65259701Sdim 66259701Sdim // If this base has a vbptr, then we've found a path. These are not full 67259701Sdim // paths, so we don't use CXXBasePath. 68259701Sdim if (Layout.hasOwnVBPtr()) { 69259701Sdim ReuseVBPtrFromBase = false; 70259701Sdim VBTablePath *Info = new VBTablePath( 71259701Sdim VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0)); 72259701Sdim Paths.push_back(Info); 73259701Sdim } 74259701Sdim 75259701Sdim // Recurse onto any bases which themselves have virtual bases. 76259701Sdim for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(), 77259701Sdim E = CurBase->bases_end(); I != E; ++I) { 78259701Sdim const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl(); 79259701Sdim if (!Base->getNumVBases()) 80259701Sdim continue; // Bases without virtual bases have no vbptrs. 81259701Sdim CharUnits NextOffset; 82259701Sdim const CXXRecordDecl *NextReusingBase = Base; 83259701Sdim if (I->isVirtual()) { 84259701Sdim if (!VBasesSeen.insert(Base)) 85259701Sdim continue; // Don't visit virtual bases twice. 86259701Sdim NextOffset = DerivedLayout.getVBaseClassOffset(Base); 87259701Sdim } else { 88259701Sdim NextOffset = (CurSubobject.getBaseOffset() + 89259701Sdim Layout.getBaseClassOffset(Base)); 90259701Sdim 91259701Sdim // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr 92259701Sdim // from the first non-virtual base with vbases for its vbptr. 93259701Sdim if (ReuseVBPtrFromBase) { 94259701Sdim NextReusingBase = ReusingBase; 95259701Sdim ReuseVBPtrFromBase = false; 96259701Sdim } 97259701Sdim } 98259701Sdim 99259701Sdim size_t NumPaths = Paths.size(); 100259701Sdim findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset), 101259701Sdim Paths); 102259701Sdim 103259701Sdim // Tag paths through this base with the base itself. We might use it to 104259701Sdim // disambiguate. 105259701Sdim for (size_t I = NumPaths, E = Paths.size(); I != E; ++I) 106259701Sdim Paths[I]->NextBase = Base; 107259701Sdim } 108259701Sdim 109259701Sdim bool AmbiguousPaths = rebucketPaths(Paths, PathsStart); 110259701Sdim if (AmbiguousPaths) 111259701Sdim rebucketPaths(Paths, PathsStart, /*SecondPass=*/true); 112259701Sdim 113259701Sdim#ifndef NDEBUG 114259701Sdim // Check that the paths are in fact unique. 115259701Sdim for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) { 116259701Sdim assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique"); 117259701Sdim } 118259701Sdim#endif 119259701Sdim} 120259701Sdim 121259701Sdimstatic bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) { 122259701Sdim return LHS->Path < RHS->Path; 123259701Sdim} 124259701Sdim 125259701Sdimvoid VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) { 126259701Sdim assert(P->NextBase || SecondPass); 127259701Sdim if (P->NextBase) { 128259701Sdim P->Path.push_back(P->NextBase); 129259701Sdim P->NextBase = 0; // Prevent the path from being extended twice. 130259701Sdim } 131259701Sdim} 132259701Sdim 133259701Sdimbool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, 134259701Sdim bool SecondPass) { 135259701Sdim // What we're essentially doing here is bucketing together ambiguous paths. 136259701Sdim // Any bucket with more than one path in it gets extended by NextBase, which 137259701Sdim // is usually the direct base of the inherited the vbptr. This code uses a 138259701Sdim // sorted vector to implement a multiset to form the buckets. Note that the 139259701Sdim // ordering is based on pointers, but it doesn't change our output order. The 140259701Sdim // current algorithm is designed to match MSVC 2012's names. 141259701Sdim // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft. 142259701Sdim VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1); 143259701Sdim std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare); 144259701Sdim bool AmbiguousPaths = false; 145259701Sdim for (size_t I = 0, E = PathsSorted.size(); I != E;) { 146259701Sdim // Scan forward to find the end of the bucket. 147259701Sdim size_t BucketStart = I; 148259701Sdim do { 149259701Sdim ++I; 150259701Sdim } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path); 151259701Sdim 152259701Sdim // If this bucket has multiple paths, extend them all. 153259701Sdim if (I - BucketStart > 1) { 154259701Sdim AmbiguousPaths = true; 155259701Sdim for (size_t II = BucketStart; II != I; ++II) 156259701Sdim extendPath(PathsSorted[II], SecondPass); 157259701Sdim } 158259701Sdim } 159259701Sdim return AmbiguousPaths; 160259701Sdim} 161259701Sdim 162259701Sdimllvm::GlobalVariable * 163259701SdimVBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase, 164259701Sdim ArrayRef<const CXXRecordDecl *> BasePath) { 165259701Sdim // Caching at this layer is redundant with the caching in EnumerateVBTables(). 166259701Sdim 167259701Sdim SmallString<256> OutName; 168259701Sdim llvm::raw_svector_ostream Out(OutName); 169259701Sdim MicrosoftMangleContext &Mangler = 170259701Sdim cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext()); 171259701Sdim Mangler.mangleCXXVBTable(MostDerived, BasePath, Out); 172259701Sdim Out.flush(); 173259701Sdim StringRef Name = OutName.str(); 174259701Sdim 175259701Sdim llvm::ArrayType *VBTableType = 176259701Sdim llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases()); 177259701Sdim 178259701Sdim assert(!CGM.getModule().getNamedGlobal(Name) && 179259701Sdim "vbtable with this name already exists: mangling bug?"); 180259701Sdim llvm::GlobalVariable *VBTable = 181259701Sdim CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType, 182259701Sdim llvm::GlobalValue::ExternalLinkage); 183259701Sdim VBTable->setUnnamedAddr(true); 184259701Sdim return VBTable; 185259701Sdim} 186259701Sdim 187259701Sdimvoid VBTableInfo::EmitVBTableDefinition( 188259701Sdim CodeGenModule &CGM, const CXXRecordDecl *RD, 189259701Sdim llvm::GlobalVariable::LinkageTypes Linkage) const { 190259701Sdim assert(RD->getNumVBases() && ReusingBase->getNumVBases() && 191259701Sdim "should only emit vbtables for classes with vbtables"); 192259701Sdim 193259701Sdim const ASTRecordLayout &BaseLayout = 194259701Sdim CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase()); 195259701Sdim const ASTRecordLayout &DerivedLayout = 196259701Sdim CGM.getContext().getASTRecordLayout(RD); 197259701Sdim 198259701Sdim SmallVector<llvm::Constant *, 4> Offsets(1 + ReusingBase->getNumVBases(), 0); 199259701Sdim 200259701Sdim // The offset from ReusingBase's vbptr to itself always leads. 201259701Sdim CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset(); 202259701Sdim Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity()); 203259701Sdim 204259701Sdim MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext(); 205259701Sdim for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(), 206259701Sdim E = ReusingBase->vbases_end(); I != E; ++I) { 207259701Sdim const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl(); 208259701Sdim CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase); 209259701Sdim assert(!Offset.isNegative()); 210259701Sdim // Make it relative to the subobject vbptr. 211259701Sdim Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset; 212259701Sdim unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase); 213259701Sdim assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?"); 214259701Sdim Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity()); 215259701Sdim } 216259701Sdim 217259701Sdim assert(Offsets.size() == 218259701Sdim cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType()) 219259701Sdim ->getElementType())->getNumElements()); 220259701Sdim llvm::ArrayType *VBTableType = 221259701Sdim llvm::ArrayType::get(CGM.IntTy, Offsets.size()); 222259701Sdim llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets); 223259701Sdim GV->setInitializer(Init); 224259701Sdim 225259701Sdim // Set the correct linkage. 226259701Sdim GV->setLinkage(Linkage); 227259701Sdim 228259701Sdim // Set the right visibility. 229259701Sdim CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable); 230259701Sdim} 231259701Sdim 232259701Sdim} // namespace CodeGen 233259701Sdim} // namespace clang 234