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 21 namespace clang { 22 23 class ASTRecordLayout; 24 25 namespace CodeGen { 26 27 class CodeGenModule; 28 29 struct 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. 52 typedef std::vector<VBTableInfo> VBTableVector; 53 54 struct VBTablePath; 55 56 typedef 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. 93 class VBTableBuilder { 94 public: 95 VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived); 96 97 void enumerateVBTables(VBTableVector &VBTables); 98 99 private: 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
