MicrosoftVBTables.h revision 285830
1//===--- MicrosoftVBTables.h - Virtual Base Table Emission ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This class generates data about MSVC virtual base tables. 11// 12//===----------------------------------------------------------------------===// 13 14#include "clang/AST/BaseSubobject.h" 15#include "clang/Basic/LLVM.h" 16#include "llvm/ADT/SmallPtrSet.h" 17#include "llvm/ADT/ArrayRef.h" 18#include "llvm/IR/GlobalVariable.h" 19#include <vector> 20 21namespace clang { 22 23class ASTRecordLayout; 24 25namespace CodeGen { 26 27class CodeGenModule; 28 29struct VBTableInfo { 30 VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject, 31 llvm::GlobalVariable *GV) 32 : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject), GV(GV) { } 33 34 /// The vbtable will hold all of the virtual bases of ReusingBase. This may 35 /// or may not be the same class as VBPtrSubobject.Base. A derived class will 36 /// reuse the vbptr of the first non-virtual base subobject that has one. 37 const CXXRecordDecl *ReusingBase; 38 39 /// The vbptr is stored inside this subobject. 40 BaseSubobject VBPtrSubobject; 41 42 /// The GlobalVariable for this vbtable. 43 llvm::GlobalVariable *GV; 44 45 /// \brief Emits a definition for GV by setting it's initializer. 46 void EmitVBTableDefinition(CodeGenModule &CGM, const CXXRecordDecl *RD, 47 llvm::GlobalVariable::LinkageTypes Linkage) const; 48}; 49 50// These are embedded in a DenseMap and the elements are large, so we don't want 51// SmallVector. 52typedef std::vector<VBTableInfo> VBTableVector; 53 54struct VBTablePath; 55 56typedef llvm::SmallVector<VBTablePath *, 6> VBTablePathVector; 57 58/// Produces MSVC-compatible vbtable data. The symbols produced by this builder 59/// match those produced by MSVC 2012, which is different from MSVC 2010. 60/// 61/// Unlike Itanium, which uses only one vtable per class, MSVC uses a different 62/// symbol for every "address point" installed in base subobjects. As a result, 63/// we have to compute unique symbols for every table. Since there can be 64/// multiple non-virtual base subobjects of the same class, combining the most 65/// derived class with the base containing the vtable is insufficient. The most 66/// trivial algorithm would be to mangle in the entire path from base to most 67/// derived, but that would be too easy and would create unnecessarily large 68/// symbols. ;) 69/// 70/// MSVC 2012 appears to minimize the vbtable names using the following 71/// algorithm. First, walk the class hierarchy in the usual order, depth first, 72/// left to right, to find all of the subobjects which contain a vbptr field. 73/// Visiting each class node yields a list of inheritance paths to vbptrs. Each 74/// record with a vbptr creates an initially empty path. 75/// 76/// To combine paths from child nodes, the paths are compared to check for 77/// ambiguity. Paths are "ambiguous" if multiple paths have the same set of 78/// components in the same order. Each group of ambiguous paths is extended by 79/// appending the class of the base from which it came. If the current class 80/// node produced an ambiguous path, its path is extended with the current class. 81/// After extending paths, MSVC again checks for ambiguity, and extends any 82/// ambiguous path which wasn't already extended. Because each node yields an 83/// unambiguous set of paths, MSVC doesn't need to extend any path more than once 84/// to produce an unambiguous set of paths. 85/// 86/// The VBTableBuilder class attempts to implement this algorithm by repeatedly 87/// bucketing paths together by sorting them. 88/// 89/// TODO: Presumably vftables use the same algorithm. 90/// 91/// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting 92/// duplicate vbtables with different symbols. 93class VBTableBuilder { 94public: 95 VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived); 96 97 void enumerateVBTables(VBTableVector &VBTables); 98 99private: 100 bool hasVBPtr(const CXXRecordDecl *RD); 101 102 llvm::GlobalVariable *getAddrOfVBTable(const CXXRecordDecl *ReusingBase, 103 ArrayRef<const CXXRecordDecl *> BasePath); 104 105 /// Enumerates paths to bases with vbptrs. The paths elements are compressed 106 /// to contain only the classes necessary to form an unambiguous path. 107 void findUnambiguousPaths(const CXXRecordDecl *ReusingBase, 108 BaseSubobject CurSubobject, 109 VBTablePathVector &Paths); 110 111 void extendPath(VBTablePath *Info, bool SecondPass); 112 113 bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart, 114 bool SecondPass = false); 115 116 CodeGenModule &CGM; 117 118 const CXXRecordDecl *MostDerived; 119 120 /// Caches the layout of the most derived class. 121 const ASTRecordLayout &DerivedLayout; 122 123 /// Set of vbases to avoid re-visiting the same vbases. 124 llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen; 125}; 126 127} // namespace CodeGen 128 129} // namespace clang 130