MicrosoftVBTables.cpp revision 263508
138738Sbrian//===--- MicrosoftVBTables.cpp - Virtual Base Table Emission --------------===// 238738Sbrian// 337Srgrimes// The LLVM Compiler Infrastructure 437Srgrimes// 537Srgrimes// This file is distributed under the University of Illinois Open Source 637Srgrimes// License. See LICENSE.TXT for details. 737Srgrimes// 837Srgrimes//===----------------------------------------------------------------------===// 937Srgrimes// 1037Srgrimes// This class generates data about MSVC virtual base tables. 11476Srgrimes// 1237Srgrimes//===----------------------------------------------------------------------===// 1337Srgrimes 1437Srgrimes#include "MicrosoftVBTables.h" 1537Srgrimes#include "CodeGenModule.h" 1637Srgrimes#include "CGCXXABI.h" 1737Srgrimes 1837Srgrimesnamespace clang { 1937Srgrimesnamespace CodeGen { 2037Srgrimes 2137Srgrimes/// Holds intermediate data about a path to a vbptr inside a base subobject. 2237Srgrimesstruct VBTablePath { 2337Srgrimes VBTablePath(const VBTableInfo &VBInfo) 2437Srgrimes : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { } 2537Srgrimes 2637Srgrimes /// All the data needed to build a vbtable, minus the GlobalVariable whose 2737Srgrimes /// name we haven't computed yet. 2837Srgrimes VBTableInfo VBInfo; 2937Srgrimes 3037Srgrimes /// Next base to use for disambiguation. Can be null if we've already 3137Srgrimes /// disambiguated this path once. 321141Sache const CXXRecordDecl *NextBase; 331141Sache 341141Sache /// Path is not really a full path like a CXXBasePath. It holds the subset of 351141Sache /// records that need to be mangled into the vbtable symbol name in order to get 361141Sache /// a unique name. 377708Srgrimes llvm::SmallVector<const CXXRecordDecl *, 1> Path; 3811137Sjoerg}; 3911137Sjoerg 401141SacheVBTableBuilder::VBTableBuilder(CodeGenModule &CGM, 4111137Sjoerg const CXXRecordDecl *MostDerived) 4211137Sjoerg : CGM(CGM), MostDerived(MostDerived), 4311137Sjoerg DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {} 4411137Sjoerg 4511137Sjoergvoid VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) { 4611137Sjoerg VBTablePathVector Paths; 4711137Sjoerg findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived, 4811137Sjoerg CharUnits::Zero()), Paths); 4911137Sjoerg for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end(); 501141Sache I != E; ++I) { 511141Sache VBTablePath *P = *I; 521141Sache P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path); 531141Sache VBTables.push_back(P->VBInfo); 541141Sache } 551141Sache} 561141Sache 571141Sache 581141Sachevoid VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase, 591141Sache BaseSubobject CurSubobject, 601141Sache VBTablePathVector &Paths) { 611141Sache size_t PathsStart = Paths.size(); 621141Sache bool ReuseVBPtrFromBase = true; 631182Srgrimes const CXXRecordDecl *CurBase = CurSubobject.getBase(); 641144Sache const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase); 651141Sache 661141Sache // If this base has a vbptr, then we've found a path. These are not full 671141Sache // paths, so we don't use CXXBasePath. 681141Sache if (Layout.hasOwnVBPtr()) { 691182Srgrimes ReuseVBPtrFromBase = false; 701141Sache VBTablePath *Info = new VBTablePath( 711141Sache VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0)); 721141Sache Paths.push_back(Info); 731141Sache } 741141Sache 751141Sache // Recurse onto any bases which themselves have virtual bases. 761141Sache for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(), 771141Sache E = CurBase->bases_end(); I != E; ++I) { 781141Sache const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl(); 791141Sache if (!Base->getNumVBases()) 801141Sache continue; // Bases without virtual bases have no vbptrs. 811141Sache CharUnits NextOffset; 821141Sache const CXXRecordDecl *NextReusingBase = Base; 831141Sache if (I->isVirtual()) { 841141Sache if (!VBasesSeen.insert(Base)) 851141Sache continue; // Don't visit virtual bases twice. 861141Sache NextOffset = DerivedLayout.getVBaseClassOffset(Base); 871141Sache } else { 881141Sache NextOffset = (CurSubobject.getBaseOffset() + 891141Sache Layout.getBaseClassOffset(Base)); 901141Sache 911141Sache // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr 921141Sache // from the first non-virtual base with vbases for its vbptr. 931141Sache if (ReuseVBPtrFromBase) { 941141Sache NextReusingBase = ReusingBase; 951141Sache ReuseVBPtrFromBase = false; 961141Sache } 971141Sache } 981141Sache 991141Sache size_t NumPaths = Paths.size(); 1001141Sache findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset), 1011141Sache Paths); 1021141Sache 1031141Sache // Tag paths through this base with the base itself. We might use it to 10432578Spst // disambiguate. 10532578Spst for (size_t I = NumPaths, E = Paths.size(); I != E; ++I) 10632578Spst Paths[I]->NextBase = Base; 10732578Spst } 10832578Spst 10932578Spst bool AmbiguousPaths = rebucketPaths(Paths, PathsStart); 11032578Spst if (AmbiguousPaths) 11132578Spst rebucketPaths(Paths, PathsStart, /*SecondPass=*/true); 11232578Spst 1131141Sache#ifndef NDEBUG 1141141Sache // Check that the paths are in fact unique. 11537Srgrimes for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) { 11637Srgrimes assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique"); 11737Srgrimes } 11837Srgrimes#endif 11937Srgrimes} 12037Srgrimes 12137Srgrimesstatic bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) { 12237Srgrimes return LHS->Path < RHS->Path; 12337Srgrimes} 12437Srgrimes 12537Srgrimesvoid VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) { 12637Srgrimes assert(P->NextBase || SecondPass); 12737Srgrimes if (P->NextBase) { 12837Srgrimes P->Path.push_back(P->NextBase); 12937Srgrimes P->NextBase = 0; // Prevent the path from being extended twice. 13037Srgrimes } 13137Srgrimes} 13237Srgrimes 1337708Srgrimesbool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, 13437Srgrimes bool SecondPass) { 13537Srgrimes // What we're essentially doing here is bucketing together ambiguous paths. 13637Srgrimes // Any bucket with more than one path in it gets extended by NextBase, which 137145Srgrimes // is usually the direct base of the inherited the vbptr. This code uses a 13837Srgrimes // sorted vector to implement a multiset to form the buckets. Note that the 13937Srgrimes // ordering is based on pointers, but it doesn't change our output order. The 14037Srgrimes // current algorithm is designed to match MSVC 2012's names. 14137Srgrimes // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft. 14237Srgrimes VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1); 143145Srgrimes std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare); 144145Srgrimes bool AmbiguousPaths = false; 145145Srgrimes for (size_t I = 0, E = PathsSorted.size(); I != E;) { 146145Srgrimes // Scan forward to find the end of the bucket. 147145Srgrimes size_t BucketStart = I; 148145Srgrimes do { 149145Srgrimes ++I; 150145Srgrimes } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path); 151145Srgrimes 152145Srgrimes // If this bucket has multiple paths, extend them all. 153145Srgrimes if (I - BucketStart > 1) { 154145Srgrimes AmbiguousPaths = true; 155145Srgrimes for (size_t II = BucketStart; II != I; ++II) 156145Srgrimes extendPath(PathsSorted[II], SecondPass); 157145Srgrimes } 158145Srgrimes } 159145Srgrimes return AmbiguousPaths; 16037Srgrimes} 16137Srgrimes 16237Srgrimesllvm::GlobalVariable * 16337SrgrimesVBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase, 16437Srgrimes ArrayRef<const CXXRecordDecl *> BasePath) { 16537Srgrimes // Caching at this layer is redundant with the caching in EnumerateVBTables(). 16637Srgrimes 16737Srgrimes SmallString<256> OutName; 16837Srgrimes llvm::raw_svector_ostream Out(OutName); 16937Srgrimes MicrosoftMangleContext &Mangler = 17037Srgrimes cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext()); 17137Srgrimes Mangler.mangleCXXVBTable(MostDerived, BasePath, Out); 17237Srgrimes Out.flush(); 17337Srgrimes StringRef Name = OutName.str(); 17437Srgrimes 17537Srgrimes llvm::ArrayType *VBTableType = 17637Srgrimes llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases()); 17737Srgrimes 17837Srgrimes assert(!CGM.getModule().getNamedGlobal(Name) && 17937Srgrimes "vbtable with this name already exists: mangling bug?"); 18037Srgrimes llvm::GlobalVariable *VBTable = 18137Srgrimes CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType, 18237Srgrimes llvm::GlobalValue::ExternalLinkage); 18337Srgrimes VBTable->setUnnamedAddr(true); 18437Srgrimes return VBTable; 18537Srgrimes} 18637Srgrimes 18737Srgrimesvoid VBTableInfo::EmitVBTableDefinition( 18837Srgrimes CodeGenModule &CGM, const CXXRecordDecl *RD, 18937Srgrimes llvm::GlobalVariable::LinkageTypes Linkage) const { 19037Srgrimes assert(RD->getNumVBases() && ReusingBase->getNumVBases() && 19137Srgrimes "should only emit vbtables for classes with vbtables"); 19237Srgrimes 19311137Sjoerg const ASTRecordLayout &BaseLayout = 19411137Sjoerg CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase()); 19511137Sjoerg const ASTRecordLayout &DerivedLayout = 19611137Sjoerg CGM.getContext().getASTRecordLayout(RD); 19713439Sjkh 19813439Sjkh SmallVector<llvm::Constant *, 4> Offsets(1 + ReusingBase->getNumVBases(), 0); 19913439Sjkh 20013439Sjkh // The offset from ReusingBase's vbptr to itself always leads. 20113439Sjkh CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset(); 20213439Sjkh Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity()); 20319558Sjkh 20419558Sjkh MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext(); 20522517Sjkh for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(), 20622517Sjkh E = ReusingBase->vbases_end(); I != E; ++I) { 20722517Sjkh const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl(); 20822528Sjulian CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase); 20922528Sjulian assert(!Offset.isNegative()); 21022528Sjulian // Make it relative to the subobject vbptr. 21122528Sjulian Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset; 21222528Sjulian unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase); 21322528Sjulian assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?"); 21422528Sjulian Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity()); 215 } 216 217 assert(Offsets.size() == 218 cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType()) 219 ->getElementType())->getNumElements()); 220 llvm::ArrayType *VBTableType = 221 llvm::ArrayType::get(CGM.IntTy, Offsets.size()); 222 llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets); 223 GV->setInitializer(Init); 224 225 // Set the correct linkage. 226 GV->setLinkage(Linkage); 227 228 // Set the right visibility. 229 CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable); 230} 231 232} // namespace CodeGen 233} // namespace clang 234