1259701Sdim//===--- MicrosoftVBTables.h - 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 "clang/AST/BaseSubobject.h" 15259701Sdim#include "clang/Basic/LLVM.h" 16259701Sdim#include "llvm/ADT/SmallPtrSet.h" 17259701Sdim#include "llvm/ADT/ArrayRef.h" 18259701Sdim#include "llvm/IR/GlobalVariable.h" 19259701Sdim#include <vector> 20259701Sdim 21259701Sdimnamespace clang { 22259701Sdim 23259701Sdimclass ASTRecordLayout; 24259701Sdim 25259701Sdimnamespace CodeGen { 26259701Sdim 27259701Sdimclass CodeGenModule; 28259701Sdim 29259701Sdimstruct VBTableInfo { 30259701Sdim VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject, 31259701Sdim llvm::GlobalVariable *GV) 32259701Sdim : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject), GV(GV) { } 33259701Sdim 34259701Sdim /// The vbtable will hold all of the virtual bases of ReusingBase. This may 35259701Sdim /// or may not be the same class as VBPtrSubobject.Base. A derived class will 36259701Sdim /// reuse the vbptr of the first non-virtual base subobject that has one. 37259701Sdim const CXXRecordDecl *ReusingBase; 38259701Sdim 39259701Sdim /// The vbptr is stored inside this subobject. 40259701Sdim BaseSubobject VBPtrSubobject; 41259701Sdim 42259701Sdim /// The GlobalVariable for this vbtable. 43259701Sdim llvm::GlobalVariable *GV; 44259701Sdim 45259701Sdim /// \brief Emits a definition for GV by setting it's initializer. 46259701Sdim void EmitVBTableDefinition(CodeGenModule &CGM, const CXXRecordDecl *RD, 47259701Sdim llvm::GlobalVariable::LinkageTypes Linkage) const; 48259701Sdim}; 49259701Sdim 50259701Sdim// These are embedded in a DenseMap and the elements are large, so we don't want 51259701Sdim// SmallVector. 52259701Sdimtypedef std::vector<VBTableInfo> VBTableVector; 53259701Sdim 54259701Sdimstruct VBTablePath; 55259701Sdim 56259701Sdimtypedef llvm::SmallVector<VBTablePath *, 6> VBTablePathVector; 57259701Sdim 58259701Sdim/// Produces MSVC-compatible vbtable data. The symbols produced by this builder 59259701Sdim/// match those produced by MSVC 2012, which is different from MSVC 2010. 60259701Sdim/// 61259701Sdim/// Unlike Itanium, which uses only one vtable per class, MSVC uses a different 62259701Sdim/// symbol for every "address point" installed in base subobjects. As a result, 63259701Sdim/// we have to compute unique symbols for every table. Since there can be 64259701Sdim/// multiple non-virtual base subobjects of the same class, combining the most 65259701Sdim/// derived class with the base containing the vtable is insufficient. The most 66259701Sdim/// trivial algorithm would be to mangle in the entire path from base to most 67259701Sdim/// derived, but that would be too easy and would create unnecessarily large 68259701Sdim/// symbols. ;) 69259701Sdim/// 70259701Sdim/// MSVC 2012 appears to minimize the vbtable names using the following 71259701Sdim/// algorithm. First, walk the class hierarchy in the usual order, depth first, 72259701Sdim/// left to right, to find all of the subobjects which contain a vbptr field. 73259701Sdim/// Visiting each class node yields a list of inheritance paths to vbptrs. Each 74259701Sdim/// record with a vbptr creates an initially empty path. 75259701Sdim/// 76259701Sdim/// To combine paths from child nodes, the paths are compared to check for 77259701Sdim/// ambiguity. Paths are "ambiguous" if multiple paths have the same set of 78259701Sdim/// components in the same order. Each group of ambiguous paths is extended by 79259701Sdim/// appending the class of the base from which it came. If the current class 80259701Sdim/// node produced an ambiguous path, its path is extended with the current class. 81259701Sdim/// After extending paths, MSVC again checks for ambiguity, and extends any 82259701Sdim/// ambiguous path which wasn't already extended. Because each node yields an 83259701Sdim/// unambiguous set of paths, MSVC doesn't need to extend any path more than once 84259701Sdim/// to produce an unambiguous set of paths. 85259701Sdim/// 86259701Sdim/// The VBTableBuilder class attempts to implement this algorithm by repeatedly 87259701Sdim/// bucketing paths together by sorting them. 88259701Sdim/// 89259701Sdim/// TODO: Presumably vftables use the same algorithm. 90259701Sdim/// 91259701Sdim/// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting 92259701Sdim/// duplicate vbtables with different symbols. 93259701Sdimclass VBTableBuilder { 94259701Sdimpublic: 95259701Sdim VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived); 96259701Sdim 97259701Sdim void enumerateVBTables(VBTableVector &VBTables); 98259701Sdim 99259701Sdimprivate: 100259701Sdim bool hasVBPtr(const CXXRecordDecl *RD); 101259701Sdim 102259701Sdim llvm::GlobalVariable *getAddrOfVBTable(const CXXRecordDecl *ReusingBase, 103259701Sdim ArrayRef<const CXXRecordDecl *> BasePath); 104259701Sdim 105259701Sdim /// Enumerates paths to bases with vbptrs. The paths elements are compressed 106259701Sdim /// to contain only the classes necessary to form an unambiguous path. 107259701Sdim void findUnambiguousPaths(const CXXRecordDecl *ReusingBase, 108259701Sdim BaseSubobject CurSubobject, 109259701Sdim VBTablePathVector &Paths); 110259701Sdim 111259701Sdim void extendPath(VBTablePath *Info, bool SecondPass); 112259701Sdim 113259701Sdim bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, 114259701Sdim bool SecondPass = false); 115259701Sdim 116259701Sdim CodeGenModule &CGM; 117259701Sdim 118259701Sdim const CXXRecordDecl *MostDerived; 119259701Sdim 120259701Sdim /// Caches the layout of the most derived class. 121259701Sdim const ASTRecordLayout &DerivedLayout; 122259701Sdim 123259701Sdim /// Set of vbases to avoid re-visiting the same vbases. 124259701Sdim llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen; 125259701Sdim}; 126259701Sdim 127259701Sdim} // namespace CodeGen 128259701Sdim 129259701Sdim} // namespace clang 130