1 files changed, 233 insertions, 0 deletions
diff --git a/lib/CodeGen/MicrosoftVBTables.cpp b/lib/CodeGen/MicrosoftVBTables.cpp
new file mode 100644
index 0000000..dabf52c
--- /dev/null
+++ b/lib/CodeGen/MicrosoftVBTables.cpp
@@ -0,0 +1,233 @@
+//===--- MicrosoftVBTables.cpp - Virtual Base Table Emission --------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This class generates data about MSVC virtual base tables.
+//
+//===----------------------------------------------------------------------===//
+
+#include "MicrosoftVBTables.h"
+#include "CodeGenModule.h"
+#include "CGCXXABI.h"
+
+namespace clang {
+namespace CodeGen {
+
+/// Holds intermediate data about a path to a vbptr inside a base subobject.
+struct VBTablePath {
+  VBTablePath(const VBTableInfo &VBInfo)
+    : VBInfo(VBInfo), NextBase(VBInfo.VBPtrSubobject.getBase()) { }
+
+  /// All the data needed to build a vbtable, minus the GlobalVariable whose
+  /// name we haven't computed yet.
+  VBTableInfo VBInfo;
+
+  /// Next base to use for disambiguation.  Can be null if we've already
+  /// disambiguated this path once.
+  const CXXRecordDecl *NextBase;
+
+  /// Path is not really a full path like a CXXBasePath.  It holds the subset of
+  /// records that need to be mangled into the vbtable symbol name in order to get
+  /// a unique name.
+  llvm::SmallVector<const CXXRecordDecl *, 1> Path;
+};
+
+VBTableBuilder::VBTableBuilder(CodeGenModule &CGM,
+                               const CXXRecordDecl *MostDerived)
+    : CGM(CGM), MostDerived(MostDerived),
+      DerivedLayout(CGM.getContext().getASTRecordLayout(MostDerived)) {}
+
+void VBTableBuilder::enumerateVBTables(VBTableVector &VBTables) {
+  VBTablePathVector Paths;
+  findUnambiguousPaths(MostDerived, BaseSubobject(MostDerived,
+                                                  CharUnits::Zero()), Paths);
+  for (VBTablePathVector::iterator I = Paths.begin(), E = Paths.end();
+       I != E; ++I) {
+    VBTablePath *P = *I;
+    P->VBInfo.GV = getAddrOfVBTable(P->VBInfo.ReusingBase, P->Path);
+    VBTables.push_back(P->VBInfo);
+  }
+}
+
+
+void VBTableBuilder::findUnambiguousPaths(const CXXRecordDecl *ReusingBase,
+                                          BaseSubobject CurSubobject,
+                                          VBTablePathVector &Paths) {
+  size_t PathsStart = Paths.size();
+  bool ReuseVBPtrFromBase = true;
+  const CXXRecordDecl *CurBase = CurSubobject.getBase();
+  const ASTRecordLayout &Layout = CGM.getContext().getASTRecordLayout(CurBase);
+
+  // If this base has a vbptr, then we've found a path.  These are not full
+  // paths, so we don't use CXXBasePath.
+  if (Layout.hasOwnVBPtr()) {
+    ReuseVBPtrFromBase = false;
+    VBTablePath *Info = new VBTablePath(
+      VBTableInfo(ReusingBase, CurSubobject, /*GV=*/0));
+    Paths.push_back(Info);
+  }
+
+  // Recurse onto any bases which themselves have virtual bases.
+  for (CXXRecordDecl::base_class_const_iterator I = CurBase->bases_begin(),
+       E = CurBase->bases_end(); I != E; ++I) {
+    const CXXRecordDecl *Base = I->getType()->getAsCXXRecordDecl();
+    if (!Base->getNumVBases())
+      continue;  // Bases without virtual bases have no vbptrs.
+    CharUnits NextOffset;
+    const CXXRecordDecl *NextReusingBase = Base;
+    if (I->isVirtual()) {
+      if (!VBasesSeen.insert(Base))
+        continue;  // Don't visit virtual bases twice.
+      NextOffset = DerivedLayout.getVBaseClassOffset(Base);
+    } else {
+      NextOffset = (CurSubobject.getBaseOffset() +
+                    Layout.getBaseClassOffset(Base));
+
+      // If CurBase didn't have a vbptr, then ReusingBase will reuse the vbptr
+      // from the first non-virtual base with vbases for its vbptr.
+      if (ReuseVBPtrFromBase) {
+        NextReusingBase = ReusingBase;
+        ReuseVBPtrFromBase = false;
+      }
+    }
+
+    size_t NumPaths = Paths.size();
+    findUnambiguousPaths(NextReusingBase, BaseSubobject(Base, NextOffset),
+                         Paths);
+
+    // Tag paths through this base with the base itself.  We might use it to
+    // disambiguate.
+    for (size_t I = NumPaths, E = Paths.size(); I != E; ++I)
+      Paths[I]->NextBase = Base;
+  }
+
+  bool AmbiguousPaths = rebucketPaths(Paths, PathsStart);
+  if (AmbiguousPaths)
+    rebucketPaths(Paths, PathsStart, /*SecondPass=*/true);
+
+#ifndef NDEBUG
+  // Check that the paths are in fact unique.
+  for (size_t I = PathsStart + 1, E = Paths.size(); I != E; ++I) {
+    assert(Paths[I]->Path != Paths[I - 1]->Path && "vbtable paths are not unique");
+  }
+#endif
+}
+
+static bool pathCompare(VBTablePath *LHS, VBTablePath *RHS) {
+  return LHS->Path < RHS->Path;
+}
+
+void VBTableBuilder::extendPath(VBTablePath *P, bool SecondPass) {
+  assert(P->NextBase || SecondPass);
+  if (P->NextBase) {
+    P->Path.push_back(P->NextBase);
+    P->NextBase = 0;  // Prevent the path from being extended twice.
+  }
+}
+
+bool VBTableBuilder::rebucketPaths(VBTablePathVector &Paths, size_t PathsStart,
+                                   bool SecondPass) {
+  // What we're essentially doing here is bucketing together ambiguous paths.
+  // Any bucket with more than one path in it gets extended by NextBase, which
+  // is usually the direct base of the inherited the vbptr.  This code uses a
+  // sorted vector to implement a multiset to form the buckets.  Note that the
+  // ordering is based on pointers, but it doesn't change our output order.  The
+  // current algorithm is designed to match MSVC 2012's names.
+  // TODO: Implement MSVC 2010 or earlier names to avoid extra vbtable cruft.
+  VBTablePathVector PathsSorted(&Paths[PathsStart], &Paths.back() + 1);
+  std::sort(PathsSorted.begin(), PathsSorted.end(), pathCompare);
+  bool AmbiguousPaths = false;
+  for (size_t I = 0, E = PathsSorted.size(); I != E;) {
+    // Scan forward to find the end of the bucket.
+    size_t BucketStart = I;
+    do {
+      ++I;
+    } while (I != E && PathsSorted[BucketStart]->Path == PathsSorted[I]->Path);
+
+    // If this bucket has multiple paths, extend them all.
+    if (I - BucketStart > 1) {
+      AmbiguousPaths = true;
+      for (size_t II = BucketStart; II != I; ++II)
+        extendPath(PathsSorted[II], SecondPass);
+    }
+  }
+  return AmbiguousPaths;
+}
+
+llvm::GlobalVariable *
+VBTableBuilder::getAddrOfVBTable(const CXXRecordDecl *ReusingBase,
+                                 ArrayRef<const CXXRecordDecl *> BasePath) {
+  // Caching at this layer is redundant with the caching in EnumerateVBTables().
+
+  SmallString<256> OutName;
+  llvm::raw_svector_ostream Out(OutName);
+  MicrosoftMangleContext &Mangler =
+      cast<MicrosoftMangleContext>(CGM.getCXXABI().getMangleContext());
+  Mangler.mangleCXXVBTable(MostDerived, BasePath, Out);
+  Out.flush();
+  StringRef Name = OutName.str();
+
+  llvm::ArrayType *VBTableType =
+    llvm::ArrayType::get(CGM.IntTy, 1 + ReusingBase->getNumVBases());
+
+  assert(!CGM.getModule().getNamedGlobal(Name) &&
+         "vbtable with this name already exists: mangling bug?");
+  llvm::GlobalVariable *VBTable =
+    CGM.CreateOrReplaceCXXRuntimeVariable(Name, VBTableType,
+                                          llvm::GlobalValue::ExternalLinkage);
+  VBTable->setUnnamedAddr(true);
+  return VBTable;
+}
+
+void VBTableInfo::EmitVBTableDefinition(
+    CodeGenModule &CGM, const CXXRecordDecl *RD,
+    llvm::GlobalVariable::LinkageTypes Linkage) const {
+  assert(RD->getNumVBases() && ReusingBase->getNumVBases() &&
+         "should only emit vbtables for classes with vbtables");
+
+  const ASTRecordLayout &BaseLayout =
+    CGM.getContext().getASTRecordLayout(VBPtrSubobject.getBase());
+  const ASTRecordLayout &DerivedLayout =
+    CGM.getContext().getASTRecordLayout(RD);
+
+  SmallVector<llvm::Constant *, 4> Offsets(1 + ReusingBase->getNumVBases(), 0);
+
+  // The offset from ReusingBase's vbptr to itself always leads.
+  CharUnits VBPtrOffset = BaseLayout.getVBPtrOffset();
+  Offsets[0] = llvm::ConstantInt::get(CGM.IntTy, -VBPtrOffset.getQuantity());
+
+  MicrosoftVTableContext &Context = CGM.getMicrosoftVTableContext();
+  for (CXXRecordDecl::base_class_const_iterator I = ReusingBase->vbases_begin(),
+       E = ReusingBase->vbases_end(); I != E; ++I) {
+    const CXXRecordDecl *VBase = I->getType()->getAsCXXRecordDecl();
+    CharUnits Offset = DerivedLayout.getVBaseClassOffset(VBase);
+    assert(!Offset.isNegative());
+    // Make it relative to the subobject vbptr.
+    Offset -= VBPtrSubobject.getBaseOffset() + VBPtrOffset;
+    unsigned VBIndex = Context.getVBTableIndex(ReusingBase, VBase);
+    assert(Offsets[VBIndex] == 0 && "The same vbindex seen twice?");
+    Offsets[VBIndex] = llvm::ConstantInt::get(CGM.IntTy, Offset.getQuantity());
+  }
+
+  assert(Offsets.size() ==
+         cast<llvm::ArrayType>(cast<llvm::PointerType>(GV->getType())
+                               ->getElementType())->getNumElements());
+  llvm::ArrayType *VBTableType =
+    llvm::ArrayType::get(CGM.IntTy, Offsets.size());
+  llvm::Constant *Init = llvm::ConstantArray::get(VBTableType, Offsets);
+  GV->setInitializer(Init);
+
+  // Set the correct linkage.
+  GV->setLinkage(Linkage);
+
+  // Set the right visibility.
+  CGM.setTypeVisibility(GV, RD, CodeGenModule::TVK_ForVTable);
+}
+
+} // namespace CodeGen
+} // namespace clang