CodeGen: New vtable group representation: struct of vtable arrays.

[pcc]

Summary

In a future change, this representation will allow us to use the new inrange
annotation on getelementptr to allow the optimizer to split vtable groups.

[pcc]

An amendment to the Itanium ABI requiring that a conforming program may not
adjust a virtual table pointer loaded from an object to another virtual table
in the same virtual table group would seem to be all that would be required
to guarantee that this scheme will be ABI compatible with future compilers,
and I'd be happy to drive such an amendment.

Actually, now that I've taken a closer look at the Itanium ABI, I think we're already covered, as the ABI specifies the calling sequence for virtual calls (https://mentorembedded.github.io/cxx-abi/abi.html#vcall.caller). As mentioned in that section, it would seem that the caller has to pass a pointer to the chosen subobject as the this pointer. This would seem to require that the caller choose a virtual function pointer appropriate to the chosen subobject, rather than some other subobject in another virtual table group (such a virtual function would by definition require a different this adjustment).

[pcc]

Use new representation: D22793

[pcc]

For reference, here is the text of the proposal I sent to cxx-abi-dev:

Hi all,

The ABI currently requires that virtual tables for a class appear consecutively in a virtual table group. I would like to propose a restriction that would require that compilers may only access the virtual table associated with the address point stored in an object's virtual table pointer, and may not rely on any knowledge that the compiler may have about the relative layout of other virtual tables in the virtual table group.

The purpose of this restriction is to allow an implementation to split a virtual table group along virtual table boundaries.

Motivation

There are at least two scenarios which would benefit from vtable splitting: clients which want to place data either before or after the ABI-required part of a virtual table, and clients which want to control the layout of virtual tables for performance or security reasons.

As an example of the first scenario, when performing whole-program virtual call optimization, Clang will apply an optimization known as virtual constant propagation [0], which causes data to be laid out at a specific offset from the address point of each virtual table in a hierarchy. If that virtual table appears in a virtual table group, padding is required to place the data at an appropriate offset for each class. Because of the current restriction that vtables must appear consecutively, the optimizer may need to add more padding than necessary, or inhibit the optimization entirely if it would require too much padding.

As an example of the second scenario, an implementation may wish to lay out virtual tables hierarchically either in order to increase the likelihood of a cache hit when repeatedly making the same virtual call over a set of heterogeneous objects, or to efficiently implement a security mitigation (specifically control flow integrity [1]) based on checking virtual table addresses for set membership. Placing only virtual tables (rather than virtual table groups) consecutively would likely increase the cache hit likelihood further and reduces the amount of metadata required to implement set membership checks.

In an experiment involving the Chromium web browser, I have measured a binary size decrease of 1.5%, and a median performance improvement of about 1% on Chromium's layout benchmarks when comparing a binary compiled with control flow integrity and whole-program virtual call optimization against a binary compiled with control flow integrity, whole-program virtual call optimization and a prototype implementation of vtable splitting.

Commentary

Although the ABI specifies [2] the calling convention for virtual calls, which requires the call to be made using the this-adjustment appropriate for the object from which the virtual table pointer was loaded, the as-if rule could in principle allow a program to make a call using a different virtual table if the virtual table group contains multiple secondary virtual tables, as the distance between these virtual tables would be fixed (the same would be possible for all virtual tables if the dynamic type were known, but in that case the program could just call the appropriate virtual function directly).

The purported benefit would be to avoid an additional virtual pointer load from the object in cases where consecutive calls are made to virtual functions introduced in different bases. However, it seems to me that cases where this is beneficial would be rare: not only would you need at least three bases and a derived class which does not override any of the called virtual functions, but when performing two consecutive calls it seems likely that the vtable would need to be reloaded anyway, either from the object or from the stack, especially with majority caller-save ABIs such as x86-64, or in any event because the first virtual call may have changed the object's dynamic type. It seems (according to experiments [3] carried out at godbolt.org) that all major compilers (gcc, clang, icc) do already use the appropriate vtable group and therefore are compliant with the proposed restriction.

(There would also seem to be nothing preventing an implementation from choosing to load the RTTI pointer or offset-to-top from another virtual table group. However I would consider this even less likely to be beneficial than a virtual call via another virtual table.)

The ABI specifies that the vtables in a group shall be laid out consecutively when referenced via a vtable group symbol, and I'm not proposing to change this. The effect of this proposal would be to allow a vtable to be split if the vtable group symbol is not referenced directly by name outside of the translation unit(s) participating in the optimization. This may be the case when a class has internal linkage, or if the program is linked with LTO, which allows the compiler to know which symbols are referenced outside of the LTO'd part of the program.

Wording

I propose to add two paragraphs to the section of the ABI describing virtual table groups, as follows:

diff --git a/abi.html b/abi.html
index 79cda2c..fce0c60 100644

• a/abi.html

+++ b/abi.html
@@ -1193,6 +1193,18 @@ and again excluding primary bases
(which share virtual tables with the classes for which they are primary).
</ul>

+<p>
+When performing a virtual call or loading any other data from an address
+derived from the address point stored in an object's virtual table pointer,
+a program may only load from the virtual table associated with that address
+point, and not from any other virtual table in the same virtual table group
+which might be presumed to be located at a fixed offset from the address
+point as a result of the above layout algorithm.
+
+<p>
+The purpose of this restriction is to allow an implementation to split a
+virtual table group along virtual table boundaries if its symbol is not
+visible to other translation units.

<p>
<a name="vtable-construction">

Thanks,
Peter

[0] http://lists.llvm.org/pipermail/llvm-dev/2016-January/094600.html
[1] http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html
[2] https://mentorembedded.github.io/cxx-abi/abi.html#vcall.caller
[3] https://godbolt.org/g/wX7Ay6 is a three-bases test case by Richard Smith, https://godbolt.org/g/7eG8A1 is a dynamic-type-known test case by me

[pcc]

Refresh and split out the inrange changes into a separate patch

[pcc]

This should now be ready for review and unblocked by other changes (I split out the inrange annotation to D24431).

[pcc]

Refresh

[pcc]

Ping

[pcc]

Refresh

[pcc]

John, may I ask you to take a look?

[rjmccall]

This seems reasonable to me. Just a few representational / API requests.

clang/include/clang/AST/VTableBuilder.h

222 ↗

(On Diff #80709)

Please use a struct instead of std::pair.

225 ↗

(On Diff #80709)

Does this actually grow, or should you use a representation more like VTableComponents? Or something custom that exploits the fact that, in the vast majority of cases, this vector will have size 1?

243 ↗

(On Diff #80709)

Since you're changing this interface anyway, would you mind fixing it to use ArrayRef for VTableComponents and VTableThunks, too?

260 ↗

(On Diff #80709)

I know you didn't add this line, but could you remove this cast? IsMicrosoftABI is not a local variable.

Also, the assert above suggests that this can be:

... = AddressPoint.find(Base)->second;

which should be slightly more efficient than lookup(). Also, I think the assertion becomes unnecessary at that point.

clang/lib/AST/VTableBuilder.cpp

986 ↗

(On Diff #80709)

Assuming you stop storing a std::vector in the VTableLayout, you should make this a SmallVector.

clang/lib/CodeGen/CGVTables.cpp

644 ↗

(On Diff #80709)

SmallVector, please.

648 ↗

(On Diff #80709)

This seems like a completely reasonable query to add to VTableLayout:

unsigned getVTableSize(unsigned vtableIndex) const;

or maybe:

ArrayRef<VTableComponent> getVTableComponents(unsigned vtableIndex) const;

I guess you'll also need a getNumVTables().

[pcc]

• Address review comments

clang/include/clang/AST/VTableBuilder.h

225 ↗

(On Diff #80709)

I wrapped up the code for VTableComponents and VTableThunks into a class, and used it here with some special handling for the size == 1 case.

260 ↗

(On Diff #80709)

Also, I think the assertion becomes unnecessary at that point.

Yes, and so does IsMicrosoftABI.

Also removed a similar assertion from one of the callers in CGVTT.cpp.

[rjmccall]

A couple minor suggestions, then LGTM.

clang/include/clang/AST/VTableBuilder.h

255 ↗

(On Diff #80844)

Maybe this ought to be in LLVM as OwnedArrayRef? And the more minimal implementation approach would be to inherit from MutableArrayRef<T> and just add a destructor and a move constructor.

The implicit conversion to ArrayRef is dangerous, but only in ways that ArrayRef is already dangerous.

260 ↗

(On Diff #80844)

Ah. Yes, that's a reasonable solution.

clang/lib/AST/VTableBuilder.cpp

986 ↗

(On Diff #80844)

Same comment here. Might as well give this enough capacity for any reasonably foreseeable case.

clang/lib/CodeGen/CGVTables.cpp

641 ↗

(On Diff #80844)

While 1 is definitely the most likely size, adding small amounts of extra inline capacity to a temporary SmallVector has basically zero cost, and of course those cases do happen. 4 sounds reasonable.

[pcc]

• Address review comments

[pcc]

clang/include/clang/AST/VTableBuilder.h

255 ↗

(On Diff #80844)

Good suggestions -- sent out D27723.

[rjmccall]

LGTM, thanks!

include/clang/AST/VTableBuilder.h

 public:
   typedef std::pair<uint64_t, ThunkInfo> VTableThunkTy;
 
   typedef const VTableComponent *vtable_component_iterator;
   typedef const VTableThunkTy *vtable_thunk_iterator;
   typedef llvm::iterator_range<vtable_component_iterator>
       vtable_component_range;
 
-  typedef llvm::DenseMap<BaseSubobject, uint64_t> AddressPointsMapTy;
+  typedef llvm::DenseMap<BaseSubobject, std::pair<unsigned, unsigned>>
+      AddressPointsMapTy;
 
 private:
+  std::vector<size_t> VTableIndices;
+
   uint64_t NumVTableComponents;
   std::unique_ptr<VTableComponent[]> VTableComponents;
 
   /// \brief Contains thunks needed by vtables, sorted by indices.
   uint64_t NumVTableThunks;
   std::unique_ptr<VTableThunkTy[]> VTableThunks;
 
   /// \brief Address points for all vtables.
   AddressPointsMapTy AddressPoints;
 
   bool IsMicrosoftABI;
 
 public:
-  VTableLayout(uint64_t NumVTableComponents,
+  VTableLayout(ArrayRef<size_t> VTableIndices, uint64_t NumVTableComponents,
                const VTableComponent *VTableComponents,
-               uint64_t NumVTableThunks,
-               const VTableThunkTy *VTableThunks,
-               const AddressPointsMapTy &AddressPoints,
-               bool IsMicrosoftABI);
+               uint64_t NumVTableThunks, const VTableThunkTy *VTableThunks,
+               const AddressPointsMapTy &AddressPoints, bool IsMicrosoftABI);
   ~VTableLayout();
 
   ArrayRef<VTableComponent> vtable_components() const {
     return {VTableComponents.get(), NumVTableComponents};
   }
 
   ArrayRef<VTableThunkTy> vtable_thunks() const {
     return {VTableThunks.get(), NumVTableThunks};
   }
 
-  uint64_t getAddressPoint(BaseSubobject Base) const {
+  std::pair<unsigned, unsigned> getAddressPoint(BaseSubobject Base) const {
     assert(AddressPoints.count(Base) &&
            "Did not find address point!");
 
-    uint64_t AddressPoint = AddressPoints.lookup(Base);
-    assert(AddressPoint != 0 || IsMicrosoftABI);
+    std::pair<unsigned, unsigned> AddressPoint = AddressPoints.lookup(Base);
+    assert(AddressPoint.second != 0 || IsMicrosoftABI);
     (void)IsMicrosoftABI;
 
     return AddressPoint;
   }
 
   const AddressPointsMapTy &getAddressPoints() const {
     return AddressPoints;
   }
+
+  /// Get the component indices of the first component of each virtual table in
+  /// the virtual table group.
+  ArrayRef<size_t> getVTableIndices() const {
+    return VTableIndices;
+  }
 };
 
 class VTableContextBase {
 public:
   typedef SmallVector<ThunkInfo, 1> ThunkInfoVectorTy;
 
   bool isMicrosoft() const { return IsMicrosoftABI; }
 

lib/AST/VTableBuilder.cpp

 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;
+  typedef VTableLayout::AddressPointsMapTy AddressPointsMapTy;
 
   typedef llvm::DenseMap<GlobalDecl, int64_t> MethodVTableIndicesTy;
 
 private:
   /// VTables - Global vtable information.
   ItaniumVTableContext &VTables;
   
   /// MostDerivedClass - The most derived class for which we're building this
private:
 
   /// 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.
private:
 
   /// isBuildingConstructionVTable - Return whether this vtable builder is
   /// building a construction vtable.
   bool isBuildingConstructorVTable() const { 
     return MostDerivedClass != LayoutClass;
   }
 
 public:
+  /// Component indices of the first component of each of the vtables in the
+  /// vtable group.
+  std::vector<size_t> VTableIndices;
+
   ItaniumVTableBuilder(ItaniumVTableContext &VTables,
                        const CXXRecordDecl *MostDerivedClass,
                        CharUnits MostDerivedClassOffset,
                        bool MostDerivedClassIsVirtual,
                        const CXXRecordDecl *LayoutClass)
       : VTables(VTables), MostDerivedClass(MostDerivedClass),
         MostDerivedClassOffset(MostDerivedClassOffset),
         MostDerivedClassIsVirtual(MostDerivedClassIsVirtual),
if (IsAppleKext)
     Components.push_back(VTableComponent::MakeVCallOffset(CharUnits::Zero()));
 }
 
 void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
     BaseSubobject Base, bool BaseIsMorallyVirtual,
     bool BaseIsVirtualInLayoutClass, CharUnits OffsetInLayoutClass) {
   assert(Base.getBase()->isDynamicClass() && "class does not have a vtable!");
 
+  unsigned VTableIndex = Components.size();
+  VTableIndices.push_back(VTableIndex);
+
   // Add vcall and vbase offsets for this vtable.
   VCallAndVBaseOffsetBuilder Builder(MostDerivedClass, LayoutClass, &Overriders,
                                      Base, BaseIsVirtualInLayoutClass, 
                                      OffsetInLayoutClass);
   Components.append(Builder.components_begin(), Builder.components_end());
   
   // Check if we need to add these vcall offsets.
   if (BaseIsVirtualInLayoutClass && !Builder.getVCallOffsets().empty()) {
void ItaniumVTableBuilder::LayoutPrimaryAndSecondaryVTables(
   }
 
   // Compute 'this' pointer adjustments.
   ComputeThisAdjustments();
 
   // Add all address points.
   while (true) {
     AddressPoints.insert(std::make_pair(
         BaseSubobject(RD, OffsetInLayoutClass),
-      AddressPoint));
+        std::pair<unsigned, unsigned>{VTableIndices.size() - 1,
+                                      AddressPoint - VTableIndex}));
 
     const ASTRecordLayout &Layout = Context.getASTRecordLayout(RD);
     const CXXRecordDecl *PrimaryBase = Layout.getPrimaryBase();
     
     if (!PrimaryBase)
       break;
     
     if (Layout.isPrimaryBaseVirtual()) {
void ItaniumVTableBuilder::dumpLayout(raw_ostream &Out) {
 
   // Iterate through the address points and insert them into a new map where
   // they are keyed by the index and not the base object.
   // Since an address point can be shared by multiple subobjects, we use an
   // STL multimap.
   std::multimap<uint64_t, BaseSubobject> AddressPointsByIndex;
   for (const auto &AP : AddressPoints) {
     const BaseSubobject &Base = AP.first;
-    uint64_t Index = AP.second;
+    uint64_t Index = VTableIndices[AP.second.first] + AP.second.second;
 
     AddressPointsByIndex.insert(std::make_pair(Index, Base));
   }
   
   for (unsigned I = 0, E = Components.size(); I != E; ++I) {
     uint64_t Index = I;
 
     Out << llvm::format("%4d | ", I);
for (const auto &I : IndicesMap) {
           << '\n';
     }
   }
 
   Out << '\n';
 }
 }
 
-VTableLayout::VTableLayout(uint64_t NumVTableComponents,
+VTableLayout::VTableLayout(ArrayRef<size_t> VTableIndices,
+                           uint64_t NumVTableComponents,
                            const VTableComponent *VTableComponents,
                            uint64_t NumVTableThunks,
                            const VTableThunkTy *VTableThunks,
                            const AddressPointsMapTy &AddressPoints,
                            bool IsMicrosoftABI)
-  : NumVTableComponents(NumVTableComponents),
+    : VTableIndices(VTableIndices), NumVTableComponents(NumVTableComponents),
       VTableComponents(new VTableComponent[NumVTableComponents]),
       NumVTableThunks(NumVTableThunks),
       VTableThunks(new VTableThunkTy[NumVTableThunks]),
-    AddressPoints(AddressPoints),
-    IsMicrosoftABI(IsMicrosoftABI) {
+      AddressPoints(AddressPoints), IsMicrosoftABI(IsMicrosoftABI) {
   std::copy(VTableComponents, VTableComponents+NumVTableComponents,
             this->VTableComponents.get());
   std::copy(VTableThunks, VTableThunks+NumVTableThunks,
             this->VTableThunks.get());
   std::sort(this->VTableThunks.get(),
             this->VTableThunks.get() + NumVTableThunks,
             [](const VTableLayout::VTableThunkTy &LHS,
                const VTableLayout::VTableThunkTy &RHS) {
ItaniumVTableContext::getVirtualBaseOffsetOffset(const CXXRecordDecl *RD,
   
   return I->second;
 }
 
 static VTableLayout *CreateVTableLayout(const ItaniumVTableBuilder &Builder) {
   SmallVector<VTableLayout::VTableThunkTy, 1>
     VTableThunks(Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
 
-  return new VTableLayout(Builder.getNumVTableComponents(),
-                          Builder.vtable_component_begin(),
-                          VTableThunks.size(),
-                          VTableThunks.data(),
-                          Builder.getAddressPoints(),
+  return new VTableLayout(Builder.VTableIndices,
+                          Builder.getNumVTableComponents(),
+                          Builder.vtable_component_begin(), VTableThunks.size(),
+                          VTableThunks.data(), Builder.getAddressPoints(),
                           /*IsMicrosoftABI=*/false);
 }
 
 void
 ItaniumVTableContext::computeVTableRelatedInformation(const CXXRecordDecl *RD) {
   const VTableLayout *&Entry = VTableLayouts[RD];
 
   // Check if we've computed this information before.
void MicrosoftVTableContext::computeVTableRelatedInformation(
   for (const VPtrInfo *VFPtr : *VFPtrs) {
     VFTableBuilder Builder(*this, RD, VFPtr);
 
     VFTableIdTy id(RD, VFPtr->FullOffsetInMDC);
     assert(VFTableLayouts.count(id) == 0);
     SmallVector<VTableLayout::VTableThunkTy, 1> VTableThunks(
         Builder.vtable_thunks_begin(), Builder.vtable_thunks_end());
     VFTableLayouts[id] = new VTableLayout(
-        Builder.getNumVTableComponents(), Builder.vtable_component_begin(),
+        {0}, Builder.getNumVTableComponents(), Builder.vtable_component_begin(),
         VTableThunks.size(), VTableThunks.data(), EmptyAddressPointsMap, true);
     Thunks.insert(Builder.thunks_begin(), Builder.thunks_end());
 
     for (const auto &Loc : Builder.vtable_locations()) {
       GlobalDecl GD = Loc.first;
       MethodVFTableLocation NewLoc = Loc.second;
       auto M = NewMethodLocations.find(GD);
       if (M == NewMethodLocations.end() || NewLoc < M->second)

lib/CodeGen/CGCXX.cpp

assert(!CGF.CGM.getTarget().getCXXABI().isMicrosoft() &&
          "No kext in Microsoft ABI");
   GD = GD.getCanonicalDecl();
   CodeGenModule &CGM = CGF.CGM;
   llvm::Value *VTable = CGM.getCXXABI().getAddrOfVTable(RD, CharUnits());
   Ty = Ty->getPointerTo()->getPointerTo();
   VTable = CGF.Builder.CreateBitCast(VTable, Ty);
   assert(VTable && "BuildVirtualCall = kext vtbl pointer is null");
   uint64_t VTableIndex = CGM.getItaniumVTableContext().getMethodVTableIndex(GD);
-  uint64_t AddressPoint =
-    CGM.getItaniumVTableContext().getVTableLayout(RD)
-       .getAddressPoint(BaseSubobject(RD, CharUnits::Zero()));
-  VTableIndex += AddressPoint;
+  const VTableLayout &VTLayout = CGM.getItaniumVTableContext().getVTableLayout(RD);
+  std::pair<unsigned, unsigned> AddressPoint =
+      VTLayout.getAddressPoint(BaseSubobject(RD, CharUnits::Zero()));
+  VTableIndex +=
+      VTLayout.getVTableIndices()[AddressPoint.first] + AddressPoint.second;
   llvm::Value *VFuncPtr =
     CGF.Builder.CreateConstInBoundsGEP1_64(VTable, VTableIndex, "vfnkxt");
   return CGF.Builder.CreateAlignedLoad(VFuncPtr, CGF.PointerAlignInBytes);
 }
 
 /// BuildAppleKextVirtualCall - This routine is to support gcc's kext ABI making
 /// indirect call to virtual functions. It makes the call through indexing
 /// into the vtable.

lib/CodeGen/CGVTT.cpp

 using namespace clang;
 using namespace CodeGen;
 
 static llvm::GlobalVariable *
 GetAddrOfVTTVTable(CodeGenVTables &CGVT, CodeGenModule &CGM,
                    const CXXRecordDecl *MostDerivedClass,
                    const VTTVTable &VTable,
                    llvm::GlobalVariable::LinkageTypes Linkage,
-                   llvm::DenseMap<BaseSubobject, uint64_t> &AddressPoints) {
+                   VTableLayout::AddressPointsMapTy &AddressPoints) {
   if (VTable.getBase() == MostDerivedClass) {
     assert(VTable.getBaseOffset().isZero() &&
            "Most derived class vtable must have a zero offset!");
     // This is a regular vtable.
     return CGM.getCXXABI().getAddrOfVTable(MostDerivedClass, CharUnits());
   }
   
   return CGVT.GenerateConstructionVTable(MostDerivedClass, 
VTables.push_back(GetAddrOfVTTVTable(*this, CGM, RD, *i, Linkage,
                                          VTableAddressPoints.back()));
   }
 
   SmallVector<llvm::Constant *, 8> VTTComponents;
   for (const VTTComponent *i = Builder.getVTTComponents().begin(),
                           *e = Builder.getVTTComponents().end(); i != e; ++i) {
     const VTTVTable &VTTVT = Builder.getVTTVTables()[i->VTableIndex];
     llvm::GlobalVariable *VTable = VTables[i->VTableIndex];
-    uint64_t AddressPoint;
+    std::pair<unsigned, unsigned> AddressPoint;
     if (VTTVT.getBase() == RD) {
       // Just get the address point for the regular vtable.
       AddressPoint =
           getItaniumVTableContext().getVTableLayout(RD).getAddressPoint(
               i->VTableBase);
-      assert(AddressPoint != 0 && "Did not find vtable address point!");
+      assert(AddressPoint.second != 0 && "Did not find vtable address point!");
     } else {
       AddressPoint = VTableAddressPoints[i->VTableIndex].lookup(i->VTableBase);
-      assert(AddressPoint != 0 && "Did not find ctor vtable address point!");
+      assert(AddressPoint.second != 0 &&
+             "Did not find ctor vtable address point!");
     }
 
      llvm::Value *Idxs[] = {
        llvm::ConstantInt::get(Int32Ty, 0),
-       llvm::ConstantInt::get(Int32Ty, AddressPoint)
+       llvm::ConstantInt::get(Int32Ty, AddressPoint.first),
+       llvm::ConstantInt::get(Int32Ty, AddressPoint.second),
      };
 
-     llvm::Constant *Init = llvm::ConstantExpr::getInBoundsGetElementPtr(
-         VTable->getValueType(), VTable, Idxs);
+     llvm::Constant *Init = llvm::ConstantExpr::getGetElementPtr(
+         VTable->getValueType(), VTable, Idxs, /*InBounds=*/true,
+         /*InRangeIndex=*/1);
 
      Init = llvm::ConstantExpr::getBitCast(Init, Int8PtrTy);
 
      VTTComponents.push_back(Init);
   }
 
   llvm::Constant *Init = llvm::ConstantArray::get(ArrayType, VTTComponents);
 

lib/CodeGen/CGVTables.h

namespace CodeGen {
   class CodeGenModule;
 
 class CodeGenVTables {
   CodeGenModule &CGM;
 
   VTableContextBase *VTContext;
 
   /// VTableAddressPointsMapTy - Address points for a single vtable.
-  typedef llvm::DenseMap<BaseSubobject, uint64_t> VTableAddressPointsMapTy;
+  typedef VTableLayout::AddressPointsMapTy VTableAddressPointsMapTy;
 
   typedef std::pair<const CXXRecordDecl *, BaseSubobject> BaseSubobjectPairTy;
   typedef llvm::DenseMap<BaseSubobjectPairTy, uint64_t> SubVTTIndiciesMapTy;
   
   /// SubVTTIndicies - Contains indices into the various sub-VTTs.
   SubVTTIndiciesMapTy SubVTTIndicies;
 
   typedef llvm::DenseMap<BaseSubobjectPairTy, uint64_t>
public:
     
   /// GenerateClassData - Generate all the class data required to be
   /// generated upon definition of a KeyFunction.  This includes the
   /// vtable, the RTTI data structure (if RTTI is enabled) and the VTT
   /// (if the class has virtual bases).
   void GenerateClassData(const CXXRecordDecl *RD);
 
   bool isVTableExternal(const CXXRecordDecl *RD);
+
+  /// Returns the type of a vtable with the given layout. Normally a struct of
+  /// arrays of pointers, with one struct element for each vtable in the vtable
+  /// group.
+  llvm::Type *GetVTableType(const CXXRecordDecl *RD,
+                            const VTableLayout &VTLayout);
 };
 
 } // end namespace CodeGen
 } // end namespace clang
 #endif

lib/CodeGen/CGVTables.cpp

case VTableComponent::CK_DeletingDtorPointer: {
     }
   }
 
   case VTableComponent::CK_UnusedFunctionPointer:
     return llvm::ConstantExpr::getNullValue(Int8PtrTy);
   }
 }
 
+llvm::Type *CodeGenVTables::GetVTableType(const CXXRecordDecl *RD,
+                                          const VTableLayout &VTLayout) {
+  ArrayRef<size_t> Idxs = VTLayout.getVTableIndices();
+
+  std::vector<llvm::Type *> Tys;
+  for (unsigned I = 0, E = Idxs.size(); I != E; ++I) {
+    size_t ThisIndex = Idxs[I];
+    size_t NextIndex =
+        (I + 1 == E) ? VTLayout.vtable_components().size() : Idxs[I + 1];
+    Tys.push_back(llvm::ArrayType::get(CGM.Int8PtrTy, NextIndex - ThisIndex));
+  }
+
+  return llvm::StructType::get(CGM.getLLVMContext(), Tys);
+}
+ 
 llvm::Constant *
 CodeGenVTables::CreateVTableInitializer(const VTableLayout &VTLayout,
                                         llvm::Constant *RTTI) {
   SmallVector<llvm::Constant *, 64> Inits;
   unsigned NextVTableThunkIndex = 0;
 
-  for (unsigned I = 0, E = VTLayout.vtable_components().size(); I != E; ++I) {
+  ArrayRef<size_t> Idxs = VTLayout.getVTableIndices();
+  for (unsigned I = 0, E = Idxs.size(); I != E; ++I) {
+    size_t ThisIndex = Idxs[I];
+    size_t NextIndex =
+        (I + 1 == E) ? VTLayout.vtable_components().size() : Idxs[I + 1];
+    SmallVector<llvm::Constant *, 64> ArrayInits;
+    for (unsigned I = ThisIndex; I != NextIndex; ++I) {
       llvm::Constant *Init =
           CreateVTableComponent(I, VTLayout, RTTI, NextVTableThunkIndex);
-    Inits.push_back(llvm::ConstantExpr::getBitCast(Init, CGM.Int8PtrTy));
+      ArrayInits.push_back(llvm::ConstantExpr::getBitCast(Init, CGM.Int8PtrTy));
     }
-
     llvm::ArrayType *ArrayType =
-      llvm::ArrayType::get(CGM.Int8PtrTy, VTLayout.vtable_components().size());
-  return llvm::ConstantArray::get(ArrayType, Inits);
+        llvm::ArrayType::get(CGM.Int8PtrTy, NextIndex - ThisIndex);
+    Inits.push_back(llvm::ConstantArray::get(ArrayType, ArrayInits));
+  }
+
+  return llvm::ConstantStruct::getAnon(Inits);
 }
 
 llvm::GlobalVariable *
 CodeGenVTables::GenerateConstructionVTable(const CXXRecordDecl *RD, 
                                       const BaseSubobject &Base, 
                                       bool BaseIsVirtual, 
                                    llvm::GlobalVariable::LinkageTypes Linkage,
                                       VTableAddressPointsMapTy& AddressPoints) {
CodeGenVTables::GenerateConstructionVTable(const CXXRecordDecl *RD,
   // Get the mangled construction vtable name.
   SmallString<256> OutName;
   llvm::raw_svector_ostream Out(OutName);
   cast<ItaniumMangleContext>(CGM.getCXXABI().getMangleContext())
       .mangleCXXCtorVTable(RD, Base.getBaseOffset().getQuantity(),
                            Base.getBase(), Out);
   StringRef Name = OutName.str();
 
-  llvm::ArrayType *ArrayType =
-      llvm::ArrayType::get(CGM.Int8PtrTy, VTLayout->vtable_components().size());
+  llvm::Type *VTType = GetVTableType(RD, *VTLayout);
 
   // Construction vtable symbols are not part of the Itanium ABI, so we cannot
   // guarantee that they actually will be available externally. Instead, when
   // emitting an available_externally VTT, we provide references to an internal
   // linkage construction vtable. The ABI only requires complete-object vtables
   // to be the same for all instances of a type, not construction vtables.
   if (Linkage == llvm::GlobalVariable::AvailableExternallyLinkage)
     Linkage = llvm::GlobalVariable::InternalLinkage;
 
   // Create the variable that will hold the construction vtable.
   llvm::GlobalVariable *VTable = 
-    CGM.CreateOrReplaceCXXRuntimeVariable(Name, ArrayType, Linkage);
+    CGM.CreateOrReplaceCXXRuntimeVariable(Name, VTType, Linkage);
   CGM.setGlobalVisibility(VTable, RD);
 
   // V-tables are always unnamed_addr.
   VTable->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
 
   llvm::Constant *RTTI = CGM.GetAddrOfRTTIDescriptor(
       CGM.getContext().getTagDeclType(Base.getBase()));
 
void CodeGenModule::EmitVTableTypeMetadata(llvm::GlobalVariable *VTable,
 
   CharUnits PointerWidth =
       Context.toCharUnitsFromBits(Context.getTargetInfo().getPointerWidth(0));
 
   typedef std::pair<const CXXRecordDecl *, unsigned> BSEntry;
   std::vector<BSEntry> BitsetEntries;
   // Create a bit set entry for each address point.
   for (auto &&AP : VTLayout.getAddressPoints())
-    BitsetEntries.push_back(std::make_pair(AP.first.getBase(), AP.second));
+    BitsetEntries.push_back(std::make_pair(
+        AP.first.getBase(),
+        VTLayout.getVTableIndices()[AP.second.first] + AP.second.second));
 
   // Sort the bit set entries for determinism.
   std::sort(BitsetEntries.begin(), BitsetEntries.end(),
             [this](const BSEntry &E1, const BSEntry &E2) {
     if (&E1 == &E2)
       return false;
 
     std::string S1;

lib/CodeGen/ItaniumCXXABI.cpp

llvm::Value *ItaniumCXXABI::getVTableAddressPointInStructor(
   return getVTableAddressPoint(Base, VTableClass);
 }
 
 llvm::Constant *
 ItaniumCXXABI::getVTableAddressPoint(BaseSubobject Base,
                                      const CXXRecordDecl *VTableClass) {
   llvm::GlobalValue *VTable = getAddrOfVTable(VTableClass, CharUnits());
 
-  // Find the appropriate vtable within the vtable group.
-  uint64_t AddressPoint = CGM.getItaniumVTableContext()
+  // Find the appropriate vtable within the vtable group, and the address point
+  // within that vtable.
+  std::pair<unsigned, unsigned> AddressPoint = CGM.getItaniumVTableContext()
                                                    .getVTableLayout(VTableClass)
                                                    .getAddressPoint(Base);
   llvm::Value *Indices[] = {
     llvm::ConstantInt::get(CGM.Int32Ty, 0),
-    llvm::ConstantInt::get(CGM.Int32Ty, AddressPoint)
+    llvm::ConstantInt::get(CGM.Int32Ty, AddressPoint.first),
+    llvm::ConstantInt::get(CGM.Int32Ty, AddressPoint.second),
   };
 
-  return llvm::ConstantExpr::getInBoundsGetElementPtr(VTable->getValueType(),
-                                                      VTable, Indices);
+  return llvm::ConstantExpr::getGetElementPtr(VTable->getValueType(), VTable,
+                                              Indices, /*InBounds=*/true,
+                                              /*InRangeIndex=*/1);
 }
 
 llvm::Value *ItaniumCXXABI::getVTableAddressPointInStructorWithVTT(
     CodeGenFunction &CGF, const CXXRecordDecl *VTableClass, BaseSubobject Base,
     const CXXRecordDecl *NearestVBase) {
   assert((Base.getBase()->getNumVBases() || NearestVBase != nullptr) &&
          NeedsVTTParameter(CGF.CurGD) && "This class doesn't have VTT");
 
llvm::GlobalVariable *ItaniumCXXABI::getAddrOfVTable(const CXXRecordDecl *RD,
 
   // Queue up this vtable for possible deferred emission.
   CGM.addDeferredVTable(RD);
 
   SmallString<256> Name;
   llvm::raw_svector_ostream Out(Name);
   getMangleContext().mangleCXXVTable(RD, Out);
 
-  ItaniumVTableContext &VTContext = CGM.getItaniumVTableContext();
-  llvm::ArrayType *ArrayType = llvm::ArrayType::get(
-      CGM.Int8PtrTy, VTContext.getVTableLayout(RD).vtable_components().size());
+  const VTableLayout &VTLayout =
+      CGM.getItaniumVTableContext().getVTableLayout(RD);
+  llvm::Type *VTableType = CGM.getVTables().GetVTableType(RD, VTLayout);
 
   VTable = CGM.CreateOrReplaceCXXRuntimeVariable(
-      Name, ArrayType, llvm::GlobalValue::ExternalLinkage);
+      Name, VTableType, llvm::GlobalValue::ExternalLinkage);
   VTable->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
 
   if (RD->hasAttr<DLLImportAttr>())
     VTable->setDLLStorageClass(llvm::GlobalValue::DLLImportStorageClass);
   else if (RD->hasAttr<DLLExportAttr>())
     VTable->setDLLStorageClass(llvm::GlobalValue::DLLExportStorageClass);
 
   return VTable;

lib/CodeGen/MicrosoftCXXABI.cpp

if (llvm::GlobalValue *VFTable =
     VFTablesMap[ID] = VFTable;
     VTable = VTableAliasIsRequred
                  ? cast<llvm::GlobalVariable>(
                        cast<llvm::GlobalAlias>(VFTable)->getBaseObject())
                  : cast<llvm::GlobalVariable>(VFTable);
     return VTable;
   }
 
-  uint64_t NumVTableSlots =
-      VTContext.getVFTableLayout(RD, VFPtr->FullOffsetInMDC)
-          .vtable_components()
-          .size();
+  const VTableLayout &VTLayout =
+      VTContext.getVFTableLayout(RD, VFPtr->FullOffsetInMDC);
   llvm::GlobalValue::LinkageTypes VTableLinkage =
       VTableAliasIsRequred ? llvm::GlobalValue::PrivateLinkage : VFTableLinkage;
 
   StringRef VTableName = VTableAliasIsRequred ? StringRef() : VFTableName.str();
 
-  llvm::ArrayType *VTableType =
-      llvm::ArrayType::get(CGM.Int8PtrTy, NumVTableSlots);
+  llvm::Type *VTableType = CGM.getVTables().GetVTableType(RD, VTLayout);
 
   // Create a backing variable for the contents of VTable.  The VTable may
   // or may not include space for a pointer to RTTI data.
   llvm::GlobalValue *VFTable;
   VTable = new llvm::GlobalVariable(CGM.getModule(), VTableType,
                                     /*isConstant=*/true, VTableLinkage,
                                     /*Initializer=*/nullptr, VTableName);
   VTable->setUnnamedAddr(llvm::GlobalValue::UnnamedAddr::Global);
 
   llvm::Comdat *C = nullptr;
   if (!VFTableComesFromAnotherTU &&
       (llvm::GlobalValue::isWeakForLinker(VFTableLinkage) ||
        (llvm::GlobalValue::isLocalLinkage(VFTableLinkage) &&
         VTableAliasIsRequred)))
     C = CGM.getModule().getOrInsertComdat(VFTableName.str());
 
   // Only insert a pointer into the VFTable for RTTI data if we are not
   // importing it.  We never reference the RTTI data directly so there is no
   // need to make room for it.
   if (VTableAliasIsRequred) {
-    llvm::Value *GEPIndices[] = {llvm::ConstantInt::get(CGM.IntTy, 0),
-                                 llvm::ConstantInt::get(CGM.IntTy, 1)};
+    llvm::Value *GEPIndices[] = {llvm::ConstantInt::get(CGM.Int32Ty, 0),
+                                 llvm::ConstantInt::get(CGM.Int32Ty, 0),
+                                 llvm::ConstantInt::get(CGM.Int32Ty, 1)};
     // Create a GEP which points just after the first entry in the VFTable,
     // this should be the location of the first virtual method.
     llvm::Constant *VTableGEP = llvm::ConstantExpr::getInBoundsGetElementPtr(
         VTable->getValueType(), VTable, GEPIndices);
     if (llvm::GlobalValue::isWeakForLinker(VFTableLinkage)) {
       VFTableLinkage = llvm::GlobalValue::ExternalLinkage;
       if (C)
         C->setSelectionKind(llvm::Comdat::Largest);