1//===--- MicrosoftVBTables.cpp - 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 "MicrosoftVBTables.h"
15#include "CodeGenModule.h"
16#include "CGCXXABI.h"
17
18namespace clang {
19namespace CodeGen {
20
21/// Holds intermediate data about a path to a vbptr inside a base subobject.
22struct VBTablePath {
23  VBTablePath(const VBTableInfo &VBInfo)
24    : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { }
25
26  /// All the data needed to build a vbtable, minus the GlobalVariable whose
27  /// name we haven't computed yet.
28  VBTableInfo VBInfo;
29
30  /// Next base to use for disambiguation.  Can be null if we've already
31  /// disambiguated this path once.
32  const CXXRecordDecl *NextBase;
33
34  /// Path is not really a full path like a CXXBasePath.  It holds the subset of
35  /// records that need to be mangled into the vbtable symbol name in order to get
36  /// a unique name.
37  llvm::SmallVector<const CXXRecordDecl *, 1> Path;
38};
39
40VBTableBuilder::VBTableBuilder(CodeGenModule &CGM,
41                               const CXXRecordDecl *MostDerived)
42    : CGM(CGM), MostDerived(MostDerived),
43      DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {}
44
45void VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) {
46  VBTablePathVector Paths;
47  findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived,
48                                                  CharUnits::Zero()), Paths);
49  for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end();
50       I != E; ++I) {
51    VBTablePath *P = *I;
52    P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path);
53    VBTables.push_back(P->VBInfo);
54  }
55}
56
57
58void VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase,
59                                          BaseSubobject CurSubobject,
60                                          VBTablePathVector &Paths) {
61  size_t PathsStart = Paths.size();
62  bool ReuseVBPtrFromBase = true;
63  const CXXRecordDecl *CurBase = CurSubobject.getBase();
64  const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase);
65
66  // If this base has a vbptr, then we've found a path.  These are not full
67  // paths, so we don't use CXXBasePath.
68  if (Layout.hasOwnVBPtr()) {
69    ReuseVBPtrFromBase = false;
70    VBTablePath *Info = new VBTablePath(
71      VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0));
72    Paths.push_back(Info);
73  }
74
75  // Recurse onto any bases which themselves have virtual bases.
76  for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(),
77       E = CurBase->bases_end(); I != E; ++I) {
78    const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl();
79    if (!Base->getNumVBases())
80      continue;  // Bases without virtual bases have no vbptrs.
81    CharUnits NextOffset;
82    const CXXRecordDecl *NextReusingBase = Base;
83    if (I->isVirtual()) {
84      if (!VBasesSeen.insert(Base))
85        continue;  // Don't visit virtual bases twice.
86      NextOffset = DerivedLayout.getVBaseClassOffset(Base);
87    } else {
88      NextOffset = (CurSubobject.getBaseOffset() +
89                    Layout.getBaseClassOffset(Base));
90
91      // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr
92      // from the first non-virtual base with vbases for its vbptr.
93      if (ReuseVBPtrFromBase) {
94        NextReusingBase = ReusingBase;
95        ReuseVBPtrFromBase = false;
96      }
97    }
98
99    size_t NumPaths = Paths.size();
100    findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset),
101                         Paths);
102
103    // Tag paths through this base with the base itself.  We might use it to
104    // disambiguate.
105    for (size_t I = NumPaths, E = Paths.size(); I != E; ++I)
106      Paths[I]->NextBase = Base;
107  }
108
109  bool AmbiguousPaths = rebucketPaths(Paths, PathsStart);
110  if (AmbiguousPaths)
111    rebucketPaths(Paths, PathsStart, /*SecondPass=*/true);
112
113#ifndef NDEBUG
114  // Check that the paths are in fact unique.
115  for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) {
116    assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique");
117  }
118#endif
119}
120
121static bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) {
122  return LHS->Path < RHS->Path;
123}
124
125void VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) {
126  assert(P->NextBase || SecondPass);
127  if (P->NextBase) {
128    P->Path.push_back(P->NextBase);
129    P->NextBase = 0;  // Prevent the path from being extended twice.
130  }
131}
132
133bool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart,
134                                   bool SecondPass) {
135  // What we're essentially doing here is bucketing together ambiguous paths.
136  // Any bucket with more than one path in it gets extended by NextBase, which
137  // is usually the direct base of the inherited the vbptr.  This code uses a
138  // sorted vector to implement a multiset to form the buckets.  Note that the
139  // ordering is based on pointers, but it doesn't change our output order.  The
140  // current algorithm is designed to match MSVC 2012's names.
141  // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft.
142  VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1);
143  std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare);
144  bool AmbiguousPaths = false;
145  for (size_t I = 0, E = PathsSorted.size(); I != E;) {
146    // Scan forward to find the end of the bucket.
147    size_t BucketStart = I;
148    do {
149      ++I;
150    } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path);
151
152    // If this bucket has multiple paths, extend them all.
153    if (I - BucketStart > 1) {
154      AmbiguousPaths = true;
155      for (size_t II = BucketStart; II != I; ++II)
156        extendPath(PathsSorted[II], SecondPass);
157    }
158  }
159  return AmbiguousPaths;
160}
161
162llvm::GlobalVariable *
163VBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase,
164                                 ArrayRef<const CXXRecordDecl *> BasePath) {
165  // Caching at this layer is redundant with the caching in EnumerateVBTables().
166
167  SmallString<256> OutName;
168  llvm::raw_svector_ostream Out(OutName);
169  MicrosoftMangleContext &Mangler =
170      cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext());
171  Mangler.mangleCXXVBTable(MostDerived, BasePath, Out);
172  Out.flush();
173  StringRef Name = OutName.str();
174
175  llvm::ArrayType *VBTableType =
176    llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases());
177
178  assert(!CGM.getModule().getNamedGlobal(Name) &&
179         "vbtable with this name already exists: mangling bug?");
180  llvm::GlobalVariable *VBTable =
181    CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType,
182                                          llvm::GlobalValue::ExternalLinkage);
183  VBTable->setUnnamedAddr(true);
184  return VBTable;
185}
186
187void VBTableInfo::EmitVBTableDefinition(
188    CodeGenModule &CGM, const CXXRecordDecl *RD,
189    llvm::GlobalVariable::LinkageTypes Linkage) const {
190  assert(RD->getNumVBases() && ReusingBase->getNumVBases() &&
191         "should only emit vbtables for classes with vbtables");
192
193  const ASTRecordLayout &BaseLayout =
194    CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase());
195  const ASTRecordLayout &DerivedLayout =
196    CGM.getContext().getASTRecordLayout(RD);
197
198  SmallVector<llvm::Constant *, 4> Offsets(1 + ReusingBase->getNumVBases(), 0);
199
200  // The offset from ReusingBase's vbptr to itself always leads.
201  CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset();
202  Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity());
203
204  MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext();
205  for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(),
206       E = ReusingBase->vbases_end(); I != E; ++I) {
207    const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl();
208    CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase);
209    assert(!Offset.isNegative());
210    // Make it relative to the subobject vbptr.
211    Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset;
212    unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase);
213    assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?");
214    Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity());
215  }
216
217  assert(Offsets.size() ==
218         cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType())
219                               ->getElementType())->getNumElements());
220  llvm::ArrayType *VBTableType =
221    llvm::ArrayType::get(CGM.IntTy, Offsets.size());
222  llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets);
223  GV->setInitializer(Init);
224
225  // Set the correct linkage.
226  GV->setLinkage(Linkage);
227
228  // Set the right visibility.
229  CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable);
230}
231
232} // namespace CodeGen
233} // namespace clang
234