1 //===--- MicrosoftVBTables.h - Virtual Base Table Emission ----------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This class generates data about MSVC virtual base tables.
12 //===----------------------------------------------------------------------===//
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"
23 class ASTRecordLayout;
30 VBTableInfo(const CXXRecordDecl *ReusingBase, BaseSubobject VBPtrSubobject,
31 llvm::GlobalVariable *GV)
32 : ReusingBase(ReusingBase), VBPtrSubobject(VBPtrSubobject), GV(GV) { }
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;
39 /// The vbptr is stored inside this subobject.
40 BaseSubobject VBPtrSubobject;
42 /// The GlobalVariable for this vbtable.
43 llvm::GlobalVariable *GV;
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;
50 // These are embedded in a DenseMap and the elements are large, so we don't want
52 typedef std::vector<VBTableInfo> VBTableVector;
56 typedef llvm::SmallVector<VBTablePath *, 6> VBTablePathVector;
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.
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
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.
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.
86 /// The VBTableBuilder class attempts to implement this algorithm by repeatedly
87 /// bucketing paths together by sorting them.
89 /// TODO: Presumably vftables use the same algorithm.
91 /// TODO: Implement the MSVC 2010 name mangling scheme to avoid emitting
92 /// duplicate vbtables with different symbols.
93 class VBTableBuilder {
95 VBTableBuilder(CodeGenModule &CGM, const CXXRecordDecl *MostDerived);
97 void enumerateVBTables(VBTableVector &VBTables);
100 bool hasVBPtr(const CXXRecordDecl *RD);
102 llvm::GlobalVariable *getAddrOfVBTable(const CXXRecordDecl *ReusingBase,
103 ArrayRef<const CXXRecordDecl *> BasePath);
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);
111 void extendPath(VBTablePath *Info, bool SecondPass);
113 bool rebucketPaths(VBTablePathVector &Paths, size_t PathsStart,
114 bool SecondPass = false);
118 const CXXRecordDecl *MostDerived;
120 /// Caches the layout of the most derived class.
121 const ASTRecordLayout &DerivedLayout;
123 /// Set of vbases to avoid re-visiting the same vbases.
124 llvm::SmallPtrSet<const CXXRecordDecl*, 4> VBasesSeen;
127 } // namespace CodeGen