MicrosoftVBTables.h revision 263508 
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