Move VTable builder to AST

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@140510 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 2404 insertions, 0 deletions

diff --git a/lib/AST/VTableBuilder.cpp b/lib/AST/VTableBuilder.cpp
new file mode 100644
index 0000000000..49032b49ef
--- /dev/null
+++ b/lib/AST/VTableBuilder.cpp
@@ -0,0 +1,2404 @@
+//===--- VTableBuilder.cpp - C++ vtable layout builder --------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This contains code dealing with generation of the layout of virtual tables.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/VTableBuilder.h"
+#include "clang/AST/CXXInheritance.h"
+#include "clang/AST/RecordLayout.h"
+#include "clang/Basic/TargetInfo.h"
+#include "llvm/Support/Format.h"
+#include <algorithm>
+#include <cstdio>
+
+using namespace clang;
+
+#define DUMP_OVERRIDERS 0
+
+namespace {
+
+/// BaseOffset - Represents an offset from a derived class to a direct or
+/// indirect base class.
+struct BaseOffset {
+  /// DerivedClass - The derived class.
+  const CXXRecordDecl *DerivedClass;
+  
+  /// VirtualBase - If the path from the derived class to the base class
+  /// involves a virtual base class, this holds its declaration.
+  const CXXRecordDecl *VirtualBase;
+
+  /// NonVirtualOffset - The offset from the derived class to the base class.
+  /// (Or the offset from the virtual base class to the base class, if the 
+  /// path from the derived class to the base class involves a virtual base
+  /// class.
+  CharUnits NonVirtualOffset;
+  
+  BaseOffset() : DerivedClass(0), VirtualBase(0), 
+    NonVirtualOffset(CharUnits::Zero()) { }
+  BaseOffset(const CXXRecordDecl *DerivedClass,
+             const CXXRecordDecl *VirtualBase, CharUnits NonVirtualOffset)
+    : DerivedClass(DerivedClass), VirtualBase(VirtualBase), 
+    NonVirtualOffset(NonVirtualOffset) { }
+
+  bool isEmpty() const { return NonVirtualOffset.isZero() && !VirtualBase; }
+};
+
+/// FinalOverriders - Contains the final overrider member functions for all
+/// member functions in the base subobjects of a class.
+class FinalOverriders {
+public:
+  /// OverriderInfo - Information about a final overrider.
+  struct OverriderInfo {
+    /// Method - The method decl of the overrider.
+    const CXXMethodDecl *Method;
+
+    /// Offset - the base offset of the overrider in the layout class.
+    CharUnits Offset;
+    
+    OverriderInfo() : Method(0), Offset(CharUnits::Zero()) { }
+  };
+
+private:
+  /// MostDerivedClass - The most derived class for which the final overriders
+  /// are stored.
+  const CXXRecordDecl *MostDerivedClass;
+  
+  /// MostDerivedClassOffset - If we're building final overriders for a 
+  /// construction vtable, this holds the offset from the layout class to the
+  /// most derived class.
+  const CharUnits MostDerivedClassOffset;
+
+  /// LayoutClass - The class we're using for layout information. Will be 
+  /// different than the most derived class if the final overriders are for a
+  /// construction vtable.  
+  const CXXRecordDecl *LayoutClass;  
+
+  ASTContext &Context;
+  
+  /// MostDerivedClassLayout - the AST record layout of the most derived class.
+  const ASTRecordLayout &MostDerivedClassLayout;
+
+  /// MethodBaseOffsetPairTy - Uniquely identifies a member function
+  /// in a base subobject.
+  typedef std::pair<const CXXMethodDecl *, CharUnits> MethodBaseOffsetPairTy;
+
+  typedef llvm::DenseMap<MethodBaseOffsetPairTy,
+                         OverriderInfo> OverridersMapTy;
+  
+  /// OverridersMap - The final overriders for all virtual member functions of 
+  /// all the base subobjects of the most derived class.
+  OverridersMapTy OverridersMap;
+  
+  /// SubobjectsToOffsetsMapTy - A mapping from a base subobject (represented
+  /// as a record decl and a subobject number) and its offsets in the most
+  /// derived class as well as the layout class.
+  typedef llvm::DenseMap<std::pair<const CXXRecordDecl *, unsigned>, 
+                         CharUnits> SubobjectOffsetMapTy;
+
+  typedef llvm::DenseMap<const CXXRecordDecl *, unsigned> SubobjectCountMapTy;
+  
+  /// ComputeBaseOffsets - Compute the offsets for all base subobjects of the
+  /// given base.
+  void ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
+                          CharUnits OffsetInLayoutClass,
+                          SubobjectOffsetMapTy &SubobjectOffsets,
+                          SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
+                          SubobjectCountMapTy &SubobjectCounts);
+
+  typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
+  
+  /// dump - dump the final overriders for a base subobject, and all its direct
+  /// and indirect base subobjects.
+  void dump(raw_ostream &Out, BaseSubobject Base,
+            VisitedVirtualBasesSetTy& VisitedVirtualBases);
+  
+public:
+  FinalOverriders(const CXXRecordDecl *MostDerivedClass,
+                  CharUnits MostDerivedClassOffset,
+                  const CXXRecordDecl *LayoutClass);
+
+  /// getOverrider - Get the final overrider for the given method declaration in
+  /// the subobject with the given base offset. 
+  OverriderInfo getOverrider(const CXXMethodDecl *MD, 
+                             CharUnits BaseOffset) const {
+    assert(OverridersMap.count(std::make_pair(MD, BaseOffset)) && 
+           "Did not find overrider!");
+    
+    return OverridersMap.lookup(std::make_pair(MD, BaseOffset));
+  }
+  
+  /// dump - dump the final overriders.
+  void dump() {
+    VisitedVirtualBasesSetTy VisitedVirtualBases;
+    dump(llvm::errs(), BaseSubobject(MostDerivedClass, CharUnits::Zero()), 
+         VisitedVirtualBases);
+  }
+  
+};
+
+#define DUMP_OVERRIDERS 0
+
+FinalOverriders::FinalOverriders(const CXXRecordDecl *MostDerivedClass,
+                                 CharUnits MostDerivedClassOffset,
+                                 const CXXRecordDecl *LayoutClass)
+  : MostDerivedClass(MostDerivedClass), 
+  MostDerivedClassOffset(MostDerivedClassOffset), LayoutClass(LayoutClass),
+  Context(MostDerivedClass->getASTContext()),
+  MostDerivedClassLayout(Context.getASTRecordLayout(MostDerivedClass)) {
+
+  // Compute base offsets.
+  SubobjectOffsetMapTy SubobjectOffsets;
+  SubobjectOffsetMapTy SubobjectLayoutClassOffsets;
+  SubobjectCountMapTy SubobjectCounts;
+  ComputeBaseOffsets(BaseSubobject(MostDerivedClass, CharUnits::Zero()), 
+                     /*IsVirtual=*/false,
+                     MostDerivedClassOffset, 
+                     SubobjectOffsets, SubobjectLayoutClassOffsets, 
+                     SubobjectCounts);
+
+  // Get the the final overriders.
+  CXXFinalOverriderMap FinalOverriders;
+  MostDerivedClass->getFinalOverriders(FinalOverriders);
+
+  for (CXXFinalOverriderMap::const_iterator I = FinalOverriders.begin(),
+       E = FinalOverriders.end(); I != E; ++I) {
+    const CXXMethodDecl *MD = I->first;
+    const OverridingMethods& Methods = I->second;
+
+    for (OverridingMethods::const_iterator I = Methods.begin(),
+         E = Methods.end(); I != E; ++I) {
+      unsigned SubobjectNumber = I->first;
+      assert(SubobjectOffsets.count(std::make_pair(MD->getParent(), 
+                                                   SubobjectNumber)) &&
+             "Did not find subobject offset!");
+      
+      CharUnits BaseOffset = SubobjectOffsets[std::make_pair(MD->getParent(),
+                                                            SubobjectNumber)];
+
+      assert(I->second.size() == 1 && "Final overrider is not unique!");
+      const UniqueVirtualMethod &Method = I->second.front();
+
+      const CXXRecordDecl *OverriderRD = Method.Method->getParent();
+      assert(SubobjectLayoutClassOffsets.count(
+             std::make_pair(OverriderRD, Method.Subobject))
+             && "Did not find subobject offset!");
+      CharUnits OverriderOffset =
+        SubobjectLayoutClassOffsets[std::make_pair(OverriderRD, 
+                                                   Method.Subobject)];
+
+      OverriderInfo& Overrider = OverridersMap[std::make_pair(MD, BaseOffset)];
+      assert(!Overrider.Method && "Overrider should not exist yet!");
+      
+      Overrider.Offset = OverriderOffset;
+      Overrider.Method = Method.Method;
+    }
+  }
+
+#if DUMP_OVERRIDERS
+  // And dump them (for now).
+  dump();
+#endif
+}
+
+static BaseOffset ComputeBaseOffset(ASTContext &Context, 
+                                    const CXXRecordDecl *DerivedRD,
+                                    const CXXBasePath &Path) {
+  CharUnits NonVirtualOffset = CharUnits::Zero();
+
+  unsigned NonVirtualStart = 0;
+  const CXXRecordDecl *VirtualBase = 0;
+  
+  // First, look for the virtual base class.
+  for (unsigned I = 0, E = Path.size(); I != E; ++I) {
+    const CXXBasePathElement &Element = Path[I];
+    
+    if (Element.Base->isVirtual()) {
+      // FIXME: Can we break when we find the first virtual base?
+      // (If we can't, can't we just iterate over the path in reverse order?)
+      NonVirtualStart = I + 1;
+      QualType VBaseType = Element.Base->getType();
+      VirtualBase = 
+        cast<CXXRecordDecl>(VBaseType->getAs<RecordType>()->getDecl());
+    }
+  }
+  
+  // Now compute the non-virtual offset.
+  for (unsigned I = NonVirtualStart, E = Path.size(); I != E; ++I) {
+    const CXXBasePathElement &Element = Path[I];
+    
+    // Check the base class offset.
+    const ASTRecordLayout &Layout = Context.getASTRecordLayout(Element.Class);
+
+    const RecordType *BaseType = Element.Base->getType()->getAs<RecordType>();
+    const CXXRecordDecl *Base = cast<CXXRecordDecl>(BaseType->getDecl());
+
+    NonVirtualOffset += Layout.getBaseClassOffset(Base);
+  }
+  
+  // FIXME: This should probably use CharUnits or something. Maybe we should
+  // even change the base offsets in ASTRecordLayout to be specified in 
+  // CharUnits.
+  return BaseOffset(DerivedRD, VirtualBase, NonVirtualOffset);
+  
+}
+
+static BaseOffset ComputeBaseOffset(ASTContext &Context, 
+                                    const CXXRecordDecl *BaseRD,
+                                    const CXXRecordDecl *DerivedRD) {
+  CXXBasePaths Paths(/*FindAmbiguities=*/false,
+                     /*RecordPaths=*/true, /*DetectVirtual=*/false);
+  
+  if (!const_cast<CXXRecordDecl *>(DerivedRD)->
+      isDerivedFrom(const_cast<CXXRecordDecl *>(BaseRD), Paths)) {
+    llvm_unreachable("Class must be derived from the passed in base class!");
+  }
+
+  return ComputeBaseOffset(Context, DerivedRD, Paths.front());
+}
+
+static BaseOffset
+ComputeReturnAdjustmentBaseOffset(ASTContext &Context, 
+                                  const CXXMethodDecl *DerivedMD,
+                                  const CXXMethodDecl *BaseMD) {
+  const FunctionType *BaseFT = BaseMD->getType()->getAs<FunctionType>();
+  const FunctionType *DerivedFT = DerivedMD->getType()->getAs<FunctionType>();
+  
+  // Canonicalize the return types.
+  CanQualType CanDerivedReturnType = 
+    Context.getCanonicalType(DerivedFT->getResultType());
+  CanQualType CanBaseReturnType = 
+    Context.getCanonicalType(BaseFT->getResultType());
+  
+  assert(CanDerivedReturnType->getTypeClass() == 
+         CanBaseReturnType->getTypeClass() && 
+         "Types must have same type class!");
+  
+  if (CanDerivedReturnType == CanBaseReturnType) {
+    // No adjustment needed.
+    return BaseOffset();
+  }
+  
+  if (isa<ReferenceType>(CanDerivedReturnType)) {
+    CanDerivedReturnType = 
+      CanDerivedReturnType->getAs<ReferenceType>()->getPointeeType();
+    CanBaseReturnType = 
+      CanBaseReturnType->getAs<ReferenceType>()->getPointeeType();
+  } else if (isa<PointerType>(CanDerivedReturnType)) {
+    CanDerivedReturnType = 
+      CanDerivedReturnType->getAs<PointerType>()->getPointeeType();
+    CanBaseReturnType = 
+      CanBaseReturnType->getAs<PointerType>()->getPointeeType();
+  } else {
+    llvm_unreachable("Unexpected return type!");
+  }
+  
+  // We need to compare unqualified types here; consider
+  //   const T *Base::foo();
+  //   T *Derived::foo();
+  if (CanDerivedReturnType.getUnqualifiedType() == 
+      CanBaseReturnType.getUnqualifiedType()) {
+    // No adjustment needed.
+    return BaseOffset();
+  }
+  
+  const CXXRecordDecl *DerivedRD = 
+    cast<CXXRecordDecl>(cast<RecordType>(CanDerivedReturnType)->getDecl());
+  
+  const CXXRecordDecl *BaseRD = 
+    cast<CXXRecordDecl>(cast<RecordType>(CanBaseReturnType)->getDecl());
+
+  return ComputeBaseOffset(Context, BaseRD, DerivedRD);
+}
+
+void 
+FinalOverriders::ComputeBaseOffsets(BaseSubobject Base, bool IsVirtual,
+                              CharUnits OffsetInLayoutClass,
+                              SubobjectOffsetMapTy &SubobjectOffsets,
+                              SubobjectOffsetMapTy &SubobjectLayoutClassOffsets,
+                              SubobjectCountMapTy &SubobjectCounts) {
+  const CXXRecordDecl *RD = Base.getBase();
+  
+  unsigned SubobjectNumber = 0;
+  if (!IsVirtual)
+    SubobjectNumber = ++SubobjectCounts[RD];
+
+  // Set up the subobject to offset mapping.
+  assert(!SubobjectOffsets.count(std::make_pair(RD, SubobjectNumber))
+         && "Subobject offset already exists!");
+  assert(!SubobjectLayoutClassOffsets.count(std::make_pair(RD, SubobjectNumber)) 
+         && "Subobject offset already exists!");
+
+  SubobjectOffsets[std::make_pair(RD, SubobjectNumber)] = Base.getBaseOffset();
+  SubobjectLayoutClassOffsets[std::make_pair(RD, SubobjectNumber)] =
+    OffsetInLayoutClass;
+  
+  // Traverse our bases.
+  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
+       E = RD->bases_end(); I != E; ++I) {
+    const CXXRecordDecl *BaseDecl = 
+      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
+
+    CharUnits BaseOffset;
+    CharUnits BaseOffsetInLayoutClass;
+    if (I->isVirtual()) {
+      // Check if we've visited this virtual base before.
+      if (SubobjectOffsets.count(std::make_pair(BaseDecl, 0)))
+        continue;
+
+      const ASTRecordLayout &LayoutClassLayout =
+        Context.getASTRecordLayout(LayoutClass);
+
+      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
+      BaseOffsetInLayoutClass = 
+        LayoutClassLayout.getVBaseClassOffset(BaseDecl);
+    } else {
+      const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
+      CharUnits Offset = Layout.getBaseClassOffset(BaseDecl);
+    
+      BaseOffset = Base.getBaseOffset() + Offset;
+      BaseOffsetInLayoutClass = OffsetInLayoutClass + Offset;
+    }
+
+    ComputeBaseOffsets(BaseSubobject(BaseDecl, BaseOffset), 
+                       I->isVirtual(), BaseOffsetInLayoutClass, 
+                       SubobjectOffsets, SubobjectLayoutClassOffsets, 
+                       SubobjectCounts);
+  }
+}
+
+void FinalOverriders::dump(raw_ostream &Out, BaseSubobject Base,
+                           VisitedVirtualBasesSetTy &VisitedVirtualBases) {
+  const CXXRecordDecl *RD = Base.getBase();
+  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
+
+  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
+       E = RD->bases_end(); I != E; ++I) {
+    const CXXRecordDecl *BaseDecl = 
+      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
+    
+    // Ignore bases that don't have any virtual member functions.
+    if (!BaseDecl->isPolymorphic())
+      continue;
+
+    CharUnits BaseOffset;
+    if (I->isVirtual()) {
+      if (!VisitedVirtualBases.insert(BaseDecl)) {
+        // We've visited this base before.
+        continue;
+      }
+      
+      BaseOffset = MostDerivedClassLayout.getVBaseClassOffset(BaseDecl);
+    } else {
+      BaseOffset = Layout.getBaseClassOffset(BaseDecl) + Base.getBaseOffset();
+    }
+
+    dump(Out, BaseSubobject(BaseDecl, BaseOffset), VisitedVirtualBases);
+  }
+
+  Out << "Final overriders for (" << RD->getQualifiedNameAsString() << ", ";
+  Out << Base.getBaseOffset().getQuantity() << ")\n";
+
+  // Now dump the overriders for this base subobject.
+  for (CXXRecordDecl::method_iterator I = RD->method_begin(), 
+       E = RD->method_end(); I != E; ++I) {
+    const CXXMethodDecl *MD = *I;
+
+    if (!MD->isVirtual())
+      continue;
+  
+    OverriderInfo Overrider = getOverrider(MD, Base.getBaseOffset());
+
+    Out << "  " << MD->getQualifiedNameAsString() << " - (";
+    Out << Overrider.Method->getQualifiedNameAsString();
+    Out << ", " << ", " << Overrider.Offset.getQuantity() << ')';
+
+    BaseOffset Offset;
+    if (!Overrider.Method->isPure())
+      Offset = ComputeReturnAdjustmentBaseOffset(Context, Overrider.Method, MD);
+
+    if (!Offset.isEmpty()) {
+      Out << " [ret-adj: ";
+      if (Offset.VirtualBase)
+        Out << Offset.VirtualBase->getQualifiedNameAsString() << " vbase, ";
+             
+      Out << Offset.NonVirtualOffset.getQuantity() << " nv]";
+    }
+    
+    Out << "\n";
+  }  
+}
+
+/// VCallOffsetMap - Keeps track of vcall offsets when building a vtable.
+struct VCallOffsetMap {
+  
+  typedef std::pair<const CXXMethodDecl *, CharUnits> MethodAndOffsetPairTy;
+  
+  /// Offsets - Keeps track of methods and their offsets.
+  // FIXME: This should be a real map and not a vector.
+  SmallVector<MethodAndOffsetPairTy, 16> Offsets;
+
+  /// MethodsCanShareVCallOffset - Returns whether two virtual member functions
+  /// can share the same vcall offset.
+  static bool MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
+                                         const CXXMethodDecl *RHS);
+
+public:
+  /// AddVCallOffset - Adds a vcall offset to the map. Returns true if the
+  /// add was successful, or false if there was already a member function with
+  /// the same signature in the map.
+  bool AddVCallOffset(const CXXMethodDecl *MD, CharUnits OffsetOffset);
+  
+  /// getVCallOffsetOffset - Returns the vcall offset offset (relative to the
+  /// vtable address point) for the given virtual member function.
+  CharUnits getVCallOffsetOffset(const CXXMethodDecl *MD);
+  
+  // empty - Return whether the offset map is empty or not.
+  bool empty() const { return Offsets.empty(); }
+};
+
+static bool HasSameVirtualSignature(const CXXMethodDecl *LHS,
+                                    const CXXMethodDecl *RHS) {
+  ASTContext &C = LHS->getASTContext(); // TODO: thread this down
+  CanQual<FunctionProtoType>
+    LT = C.getCanonicalType(LHS->getType()).getAs<FunctionProtoType>(),
+    RT = C.getCanonicalType(RHS->getType()).getAs<FunctionProtoType>();
+
+  // Fast-path matches in the canonical types.
+  if (LT == RT) return true;
+
+  // Force the signatures to match.  We can't rely on the overrides
+  // list here because there isn't necessarily an inheritance
+  // relationship between the two methods.
+  if (LT.getQualifiers() != RT.getQualifiers() ||
+      LT->getNumArgs() != RT->getNumArgs())
+    return false;
+  for (unsigned I = 0, E = LT->getNumArgs(); I != E; ++I)
+    if (LT->getArgType(I) != RT->getArgType(I))
+      return false;
+  return true;
+}
+
+bool VCallOffsetMap::MethodsCanShareVCallOffset(const CXXMethodDecl *LHS,
+                                                const CXXMethodDecl *RHS) {
+  assert(LHS->isVirtual() && "LHS must be virtual!");
+  assert(RHS->isVirtual() && "LHS must be virtual!");
+  
+  // A destructor can share a vcall offset with another destructor.
+  if (isa<CXXDestructorDecl>(LHS))
+    return isa<CXXDestructorDecl>(RHS);
+
+  // FIXME: We need to check more things here.
+  
+  // The methods must have the same name.
+  DeclarationName LHSName = LHS->getDeclName();
+  DeclarationName RHSName = RHS->getDeclName();
+  if (LHSName != RHSName)
+    return false;
+
+  // And the same signatures.
+  return HasSameVirtualSignature(LHS, RHS);
+}
+
+bool VCallOffsetMap::AddVCallOffset(const CXXMethodDecl *MD, 
+                                    CharUnits OffsetOffset) {
+  // Check if we can reuse an offset.
+  for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
+    if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
+      return false;
+  }
+  
+  // Add the offset.
+  Offsets.push_back(MethodAndOffsetPairTy(MD, OffsetOffset));
+  return true;
+}
+
+CharUnits VCallOffsetMap::getVCallOffsetOffset(const CXXMethodDecl *MD) {
+  // Look for an offset.
+  for (unsigned I = 0, E = Offsets.size(); I != E; ++I) {
+    if (MethodsCanShareVCallOffset(Offsets[I].first, MD))
+      return Offsets[I].second;
+  }
+  
+  llvm_unreachable("Should always find a vcall offset offset!");
+}
+
+/// VCallAndVBaseOffsetBuilder - Class for building vcall and vbase offsets.
+class VCallAndVBaseOffsetBuilder {
+public:
+  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 
+    VBaseOffsetOffsetsMapTy;
+
+private:
+  /// MostDerivedClass - The most derived class for which we're building vcall
+  /// and vbase offsets.
+  const CXXRecordDecl *MostDerivedClass;
+  
+  /// LayoutClass - The class we're using for layout information. Will be 
+  /// different than the most derived class if we're building a construction
+  /// vtable.
+  const CXXRecordDecl *LayoutClass;
+  
+  /// Context - The ASTContext which we will use for layout information.
+  ASTContext &Context;
+
+  /// Components - vcall and vbase offset components
+  typedef SmallVector<VTableComponent, 64> VTableComponentVectorTy;
+  VTableComponentVectorTy Components;
+  
+  /// VisitedVirtualBases - Visited virtual bases.
+  llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBases;
+  
+  /// VCallOffsets - Keeps track of vcall offsets.
+  VCallOffsetMap VCallOffsets;
+
+
+  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets,
+  /// relative to the address point.
+  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
+  
+  /// FinalOverriders - The final overriders of the most derived class.
+  /// (Can be null when we're not building a vtable of the most derived class).
+  const FinalOverriders *Overriders;
+
+  /// AddVCallAndVBaseOffsets - Add vcall offsets and vbase offsets for the
+  /// given base subobject.
+  void AddVCallAndVBaseOffsets(BaseSubobject Base, bool BaseIsVirtual,
+                               CharUnits RealBaseOffset);
+  
+  /// AddVCallOffsets - Add vcall offsets for the given base subobject.
+  void AddVCallOffsets(BaseSubobject Base, CharUnits VBaseOffset);
+  
+  /// AddVBaseOffsets - Add vbase offsets for the given class.
+  void AddVBaseOffsets(const CXXRecordDecl *Base, 
+                       CharUnits OffsetInLayoutClass);
+  
+  /// getCurrentOffsetOffset - Get the current vcall or vbase offset offset in
+  /// chars, relative to the vtable address point.
+  CharUnits getCurrentOffsetOffset() const;
+  
+public:
+  VCallAndVBaseOffsetBuilder(const CXXRecordDecl *MostDerivedClass,
+                             const CXXRecordDecl *LayoutClass,
+                             const FinalOverriders *Overriders,
+                             BaseSubobject Base, bool BaseIsVirtual,
+                             CharUnits OffsetInLayoutClass)
+    : MostDerivedClass(MostDerivedClass), LayoutClass(LayoutClass), 
+    Context(MostDerivedClass->getASTContext()), Overriders(Overriders) {
+      
+    // Add vcall and vbase offsets.
+    AddVCallAndVBaseOffsets(Base, BaseIsVirtual, OffsetInLayoutClass);
+  }
+  
+  /// Methods for iterating over the components.
+  typedef VTableComponentVectorTy::const_reverse_iterator const_iterator;
+  const_iterator components_begin() const { return Components.rbegin(); }
+  const_iterator components_end() const { return Components.rend(); }
+  
+  const VCallOffsetMap &getVCallOffsets() const { return VCallOffsets; }
+  const VBaseOffsetOffsetsMapTy &getVBaseOffsetOffsets() const {
+    return VBaseOffsetOffsets;
+  }
+};
+  
+void 
+VCallAndVBaseOffsetBuilder::AddVCallAndVBaseOffsets(BaseSubobject Base,
+                                                    bool BaseIsVirtual,
+                                                    CharUnits RealBaseOffset) {
+  const ASTRecordLayout &Layout = Context.getASTRecordLayout(Base.getBase());
+  
+  // Itanium C++ ABI 2.5.2:
+  //   ..in classes sharing a virtual table with a primary base class, the vcall
+  //   and vbase offsets added by the derived class all come before the vcall
+  //   and vbase offsets required by the base class, so that the latter may be
+  //   laid out as required by the base class without regard to additions from
+  //   the derived class(es).
+
+  // (Since we're emitting the vcall and vbase offsets in reverse order, we'll
+  // emit them for the primary base first).
+  if (const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase()) {
+    bool PrimaryBaseIsVirtual = Layout.isPrimaryBaseVirtual();
+
+    CharUnits PrimaryBaseOffset;
+    
+    // Get the base offset of the primary base.
+    if (PrimaryBaseIsVirtual) {
+      assert(Layout.getVBaseClassOffsetInBits(PrimaryBase) == 0 &&
+             "Primary vbase should have a zero offset!");
+      
+      const ASTRecordLayout &MostDerivedClassLayout =
+        Context.getASTRecordLayout(MostDerivedClass);
+      
+      PrimaryBaseOffset = 
+        MostDerivedClassLayout.getVBaseClassOffset(PrimaryBase);
+    } else {
+      assert(Layout.getBaseClassOffsetInBits(PrimaryBase) == 0 &&
+             "Primary base should have a zero offset!");
+
+      PrimaryBaseOffset = Base.getBaseOffset();
+    }
+
+    AddVCallAndVBaseOffsets(
+      BaseSubobject(PrimaryBase,PrimaryBaseOffset),
+      PrimaryBaseIsVirtual, RealBaseOffset);
+  }
+
+  AddVBaseOffsets(Base.getBase(), RealBaseOffset);
+
+  // We only want to add vcall offsets for virtual bases.
+  if (BaseIsVirtual)
+    AddVCallOffsets(Base, RealBaseOffset);
+}
+
+CharUnits VCallAndVBaseOffsetBuilder::getCurrentOffsetOffset() const {
+  // OffsetIndex is the index of this vcall or vbase offset, relative to the 
+  // vtable address point. (We subtract 3 to account for the information just
+  // above the address point, the RTTI info, the offset to top, and the
+  // vcall offset itself).
+  int64_t OffsetIndex = -(int64_t)(3 + Components.size());
+    
+  CharUnits PointerWidth = 
+    Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
+  CharUnits OffsetOffset = PointerWidth * OffsetIndex;
+  return OffsetOffset;
+}
+
+void VCallAndVBaseOffsetBuilder::AddVCallOffsets(BaseSubobject Base, 
+                                                 CharUnits VBaseOffset) {
+  const CXXRecordDecl *RD = Base.getBase();
+  const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
+
+  const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
+
+  // Handle the primary base first.
+  // We only want to add vcall offsets if the base is non-virtual; a virtual
+  // primary base will have its vcall and vbase offsets emitted already.
+  if (PrimaryBase && !Layout.isPrimaryBaseVirtual()) {
+    // Get the base offset of the primary base.
+    assert(Layout.getBaseClassOffsetInBits(PrimaryBase) == 0 &&
+           "Primary base should have a zero offset!");
+
+    AddVCallOffsets(BaseSubobject(PrimaryBase, Base.getBaseOffset()),
+                    VBaseOffset);
+  }
+  
+  // Add the vcall offsets.
+  for (CXXRecordDecl::method_iterator I = RD->method_begin(),
+       E = RD->method_end(); I != E; ++I) {
+    const CXXMethodDecl *MD = *I;
+    
+    if (!MD->isVirtual())
+      continue;
+
+    CharUnits OffsetOffset = getCurrentOffsetOffset();
+    
+    // Don't add a vcall offset if we already have one for this member function
+    // signature.
+    if (!VCallOffsets.AddVCallOffset(MD, OffsetOffset))
+      continue;
+
+    CharUnits Offset = CharUnits::Zero();
+
+    if (Overriders) {
+      // Get the final overrider.
+      FinalOverriders::OverriderInfo Overrider = 
+        Overriders->getOverrider(MD, Base.getBaseOffset());
+      
+      /// The vcall offset is the offset from the virtual base to the object 
+      /// where the function was overridden.
+      Offset = Overrider.Offset - VBaseOffset;
+    }
+    
+    Components.push_back(
+      VTableComponent::MakeVCallOffset(Offset));
+  }
+
+  // And iterate over all non-virtual bases (ignoring the primary base).
+  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
+       E = RD->bases_end(); I != E; ++I) {
+  
+    if (I->isVirtual())
+      continue;
+
+    const CXXRecordDecl *BaseDecl =
+      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
+    if (BaseDecl == PrimaryBase)
+      continue;
+
+    // Get the base offset of this base.
+    CharUnits BaseOffset = Base.getBaseOffset() + 
+      Layout.getBaseClassOffset(BaseDecl);
+    
+    AddVCallOffsets(BaseSubobject(BaseDecl, BaseOffset), 
+                    VBaseOffset);
+  }
+}
+
+void 
+VCallAndVBaseOffsetBuilder::AddVBaseOffsets(const CXXRecordDecl *RD,
+                                            CharUnits OffsetInLayoutClass) {
+  const ASTRecordLayout &LayoutClassLayout = 
+    Context.getASTRecordLayout(LayoutClass);
+
+  // Add vbase offsets.
+  for (CXXRecordDecl::base_class_const_iterator I = RD->bases_begin(),
+       E = RD->bases_end(); I != E; ++I) {
+    const CXXRecordDecl *BaseDecl =
+      cast<CXXRecordDecl>(I->getType()->getAs<RecordType>()->getDecl());
+
+    // Check if this is a virtual base that we haven't visited before.
+    if (I->isVirtual() && VisitedVirtualBases.insert(BaseDecl)) {
+      CharUnits Offset = 
+        LayoutClassLayout.getVBaseClassOffset(BaseDecl) - OffsetInLayoutClass;
+
+      // Add the vbase offset offset.
+      assert(!VBaseOffsetOffsets.count(BaseDecl) &&
+             "vbase offset offset already exists!");
+
+      CharUnits VBaseOffsetOffset = getCurrentOffsetOffset();
+      VBaseOffsetOffsets.insert(
+          std::make_pair(BaseDecl, VBaseOffsetOffset));
+
+      Components.push_back(
+          VTableComponent::MakeVBaseOffset(Offset));
+    }
+
+    // Check the base class looking for more vbase offsets.
+    AddVBaseOffsets(BaseDecl, OffsetInLayoutClass);
+  }
+}
+
+/// VTableBuilder - Class for building vtable layout information.
+class VTableBuilder {
+public:
+  /// PrimaryBasesSetVectorTy - A set vector of direct and indirect 
+  /// primary bases.
+  typedef llvm::SmallSetVector<const CXXRecordDecl *, 8> 
+    PrimaryBasesSetVectorTy;
+  
+  typedef llvm::DenseMap<const CXXRecordDecl *, CharUnits> 
+    VBaseOffsetOffsetsMapTy;
+  
+  typedef llvm::DenseMap<BaseSubobject, uint64_t> 
+    AddressPointsMapTy;
+
+private:
+  /// VTables - Global vtable information.
+  VTableContext &VTables;
+  
+  /// MostDerivedClass - The most derived class for which we're building this
+  /// vtable.
+  const CXXRecordDecl *MostDerivedClass;
+
+  /// MostDerivedClassOffset - If we're building a construction vtable, this
+  /// holds the offset from the layout class to the most derived class.
+  const CharUnits MostDerivedClassOffset;
+  
+  /// MostDerivedClassIsVirtual - Whether the most derived class is a virtual 
+  /// base. (This only makes sense when building a construction vtable).
+  bool MostDerivedClassIsVirtual;
+  
+  /// LayoutClass - The class we're using for layout information. Will be 
+  /// different than the most derived class if we're building a construction
+  /// vtable.
+  const CXXRecordDecl *LayoutClass;
+  
+  /// Context - The ASTContext which we will use for layout information.
+  ASTContext &Context;
+  
+  /// FinalOverriders - The final overriders of the most derived class.
+  const FinalOverriders Overriders;
+
+  /// VCallOffsetsForVBases - Keeps track of vcall offsets for the virtual
+  /// bases in this vtable.
+  llvm::DenseMap<const CXXRecordDecl *, VCallOffsetMap> VCallOffsetsForVBases;
+
+  /// VBaseOffsetOffsets - Contains the offsets of the virtual base offsets for
+  /// the most derived class.
+  VBaseOffsetOffsetsMapTy VBaseOffsetOffsets;
+  
+  /// Components - The components of the vtable being built.
+  SmallVector<VTableComponent, 64> Components;
+
+  /// AddressPoints - Address points for the vtable being built.
+  AddressPointsMapTy AddressPoints;
+
+  /// MethodInfo - Contains information about a method in a vtable.
+  /// (Used for computing 'this' pointer adjustment thunks.
+  struct MethodInfo {
+    /// BaseOffset - The base offset of this method.
+    const CharUnits BaseOffset;
+    
+    /// BaseOffsetInLayoutClass - The base offset in the layout class of this
+    /// method.
+    const CharUnits BaseOffsetInLayoutClass;
+    
+    /// VTableIndex - The index in the vtable that this method has.
+    /// (For destructors, this is the index of the complete destructor).
+    const uint64_t VTableIndex;
+    
+    MethodInfo(CharUnits BaseOffset, CharUnits BaseOffsetInLayoutClass, 
+               uint64_t VTableIndex)
+      : BaseOffset(BaseOffset), 
+      BaseOffsetInLayoutClass(BaseOffsetInLayoutClass),
+      VTableIndex(VTableIndex) { }
+    
+    MethodInfo() 
+      : BaseOffset(CharUnits::Zero()), 
+      BaseOffsetInLayoutClass(CharUnits::Zero()), 
+      VTableIndex(0) { }
+  };
+  
+  typedef llvm::DenseMap<const CXXMethodDecl *, MethodInfo> MethodInfoMapTy;
+  
+  /// MethodInfoMap - The information for all methods in the vtable we're
+  /// currently building.
+  MethodInfoMapTy MethodInfoMap;
+  
+  typedef llvm::DenseMap<uint64_t, ThunkInfo> VTableThunksMapTy;
+  
+  /// VTableThunks - The thunks by vtable index in the vtable currently being 
+  /// built.
+  VTableThunksMapTy VTableThunks;
+
+  typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
+  typedef llvm::DenseMap<const CXXMethodDecl *, ThunkInfoVectorTy> ThunksMapTy;
+  
+  /// Thunks - A map that contains all the thunks needed for all methods in the
+  /// most derived class for which the vtable is currently being built.
+  ThunksMapTy Thunks;
+  
+  /// AddThunk - Add a thunk for the given method.
+  void AddThunk(const CXXMethodDecl *MD, const ThunkInfo &Thunk);
+  
+  /// ComputeThisAdjustments - Compute the 'this' pointer adjustments for the
+  /// part of the vtable we're currently building.
+  void ComputeThisAdjustments();
+  
+  typedef llvm::SmallPtrSet<const CXXRecordDecl *, 4> VisitedVirtualBasesSetTy;
+
+  /// PrimaryVirtualBases - All known virtual bases who are a primary base of
+  /// some other base.
+  VisitedVirtualBasesSetTy PrimaryVirtualBases;
+
+  /// ComputeReturnAdjustment - Compute the return adjustment given a return
+  /// adjustment base offset.
+  ReturnAdjustment ComputeReturnAdjustment(BaseOffset Offset);
+  
+  /// ComputeThisAdjustmentBaseOffset - Compute the base offset for adjusting
+  /// the 'this' pointer from the base subobject to the derived subobject.
+  BaseOffset ComputeThisAdjustmentBaseOffset(BaseSubobject Base,
+                                             BaseSubobject Derived) const;
+
+  /// ComputeThisAdjustment - Compute the 'this' pointer adjustment for the
+  /// given virtual member function, its offset in the layout class and its
+  /// final overrider.
+  ThisAdjustment 
+  ComputeThisAdjustment(const CXXMethodDecl *MD, 
+                        CharUnits BaseOffsetInLayoutClass,
+                        FinalOverriders::OverriderInfo Overrider);
+
+  /// AddMethod - Add a single virtual member function to the vtable
+  /// components vector.
+  void AddMethod(const CXXMethodDecl *MD, ReturnAdjustment ReturnAdjustment);
+
+  /// IsOverriderUsed - Returns whether the overrider will ever be used in this
+  /// part of the vtable. 
+  ///
+  /// Itanium C++ ABI 2.5.2:
+  ///
+  ///   struct A { virtual void f(); };
+  ///   struct B : virtual public A { int i; };
+  ///   struct C : virtual public A { int j; };
+  ///   struct D : public B, public C {};
+  ///
+  ///   When B and C are declared, A is a primary base in each case, so although
+  ///   vcall offsets are allocated in the A-in-B and A-in-C vtables, no this
+  ///   adjustment is required and no thunk is generated. However, inside D
+  ///   objects, A is no longer a primary base of C, so if we allowed calls to
+  ///   C::f() to use the copy of A's vtable in the C subobject, we would need
+  ///   to adjust this from C* to B::A*, which would require a third-party 
+  ///   thunk. Since we require that a call to C::f() first convert to A*, 
+  ///   C-in-D's copy of A's vtable is never referenced, so this is not 
+  ///   necessary.
+  bool IsOverriderUsed(const CXXMethodDecl *Overrider,
+                       CharUnits BaseOffsetInLayoutClass,
+                       const CXXRecordDecl *FirstBaseInPrimaryBaseChain,