[llvm-pdbdump] Re-write the record layout code to be more resilient.

This reworks the way virtual bases are handled, and also the way
padding is detected across multiple levels of aggregates, producing
a much more accurate result.

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

1 files changed, 149 insertions, 197 deletions

diff --git a/lib/DebugInfo/PDB/UDTLayout.cpp b/lib/DebugInfo/PDB/UDTLayout.cpp
index 61cef093d4c..6c6bb26ad1b 100644
--- a/lib/DebugInfo/PDB/UDTLayout.cpp
+++ b/lib/DebugInfo/PDB/UDTLayout.cpp
@@ -16,6 +16,7 @@
 #include "llvm/DebugInfo/PDB/PDBSymbolExe.h"
 #include "llvm/DebugInfo/PDB/PDBSymbolFunc.h"
 #include "llvm/DebugInfo/PDB/PDBSymbolTypeBaseClass.h"
+#include "llvm/DebugInfo/PDB/PDBSymbolTypeBuiltin.h"
 #include "llvm/DebugInfo/PDB/PDBSymbolTypePointer.h"
 #include "llvm/DebugInfo/PDB/PDBSymbolTypeUDT.h"
 #include "llvm/DebugInfo/PDB/PDBSymbolTypeVTable.h"
@@ -39,36 +40,48 @@ static uint32_t getTypeLength(const PDBSymbol &Symbol) {
   return RawType.getLength();
 }
 
-StorageItemBase::StorageItemBase(const UDTLayoutBase &Parent,
-                                 const PDBSymbol &Symbol,
-                                 const std::string &Name,
-                                 uint32_t OffsetInParent, uint32_t Size)
-    : Parent(Parent), Symbol(Symbol), Name(Name),
-      OffsetInParent(OffsetInParent), SizeOf(Size) {
+LayoutItemBase::LayoutItemBase(const UDTLayoutBase *Parent,
+                               const PDBSymbol *Symbol, const std::string &Name,
+                               uint32_t OffsetInParent, uint32_t Size,
+                               bool IsElided)
+    : Symbol(Symbol), Parent(Parent), Name(Name),
+      OffsetInParent(OffsetInParent), SizeOf(Size), LayoutSize(Size),
+      IsElided(IsElided) {
   UsedBytes.resize(SizeOf, true);
 }
 
-uint32_t StorageItemBase::deepPaddingSize() const {
-  // sizeof(Field) - sizeof(typeof(Field)) is trailing padding.
-  return SizeOf - getTypeLength(Symbol);
+uint32_t LayoutItemBase::deepPaddingSize() const {
+  return UsedBytes.size() - UsedBytes.count();
+}
+
+uint32_t LayoutItemBase::tailPadding() const {
+  int Last = UsedBytes.find_last();
+
+  return UsedBytes.size() - (Last + 1);
 }
 
+
 DataMemberLayoutItem::DataMemberLayoutItem(
-    const UDTLayoutBase &Parent, std::unique_ptr<PDBSymbolData> DataMember)
-    : StorageItemBase(Parent, *DataMember, DataMember->getName(),
-                      DataMember->getOffset(), getTypeLength(*DataMember)),
-      DataMember(std::move(DataMember)) {
-  auto Type = this->DataMember->getType();
+    const UDTLayoutBase &Parent, std::unique_ptr<PDBSymbolData> Member)
+    : LayoutItemBase(&Parent, Member.get(), Member->getName(),
+                     Member->getOffset(), getTypeLength(*Member), false),
+      DataMember(std::move(Member)) {
+  auto Type = DataMember->getType();
   if (auto UDT = unique_dyn_cast<PDBSymbolTypeUDT>(Type)) {
-    // UDT data members might have padding in between fields, but otherwise
-    // a member should occupy its entire storage.
-    UsedBytes.resize(SizeOf, false);
     UdtLayout = llvm::make_unique<ClassLayout>(std::move(UDT));
+    UsedBytes = UdtLayout->usedBytes();
   }
 }
 
+VBPtrLayoutItem::VBPtrLayoutItem(const UDTLayoutBase &Parent,
+                                 std::unique_ptr<PDBSymbolTypeBuiltin> Sym,
+                                 uint32_t Offset, uint32_t Size)
+    : LayoutItemBase(&Parent, Sym.get(), "<vbptr>", Offset, Size, false),
+      Type(std::move(Sym)) {
+}
+
 const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
-  return *dyn_cast<PDBSymbolData>(&Symbol);
+  return *dyn_cast<PDBSymbolData>(Symbol);
 }
 
 bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
@@ -77,36 +90,43 @@ const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
   return *UdtLayout;
 }
 
-uint32_t DataMemberLayoutItem::deepPaddingSize() const {
-  uint32_t Result = StorageItemBase::deepPaddingSize();
-  if (UdtLayout)
-    Result += UdtLayout->deepPaddingSize();
-  return Result;
-}
-
 VTableLayoutItem::VTableLayoutItem(const UDTLayoutBase &Parent,
-                                   std::unique_ptr<PDBSymbolTypeVTable> VTable)
-    : StorageItemBase(Parent, *VTable, "<vtbl>", 0, getTypeLength(*VTable)),
-      VTable(std::move(VTable)) {
-  auto VTableType = cast<PDBSymbolTypePointer>(this->VTable->getType());
+                                   std::unique_ptr<PDBSymbolTypeVTable> VT)
+    : LayoutItemBase(&Parent, VT.get(), "<vtbl>", 0, getTypeLength(*VT), false),
+      VTable(std::move(VT)) {
+  auto VTableType = cast<PDBSymbolTypePointer>(VTable->getType());
   ElementSize = VTableType->getLength();
+}
 
-  Shape =
-      unique_dyn_cast<PDBSymbolTypeVTableShape>(VTableType->getPointeeType());
-  if (Shape)
-    VTableFuncs.resize(Shape->getCount());
+UDTLayoutBase::UDTLayoutBase(const UDTLayoutBase *Parent, const PDBSymbol &Sym,
+                             const std::string &Name, uint32_t OffsetInParent,
+                             uint32_t Size, bool IsElided)
+    : LayoutItemBase(Parent, &Sym, Name, OffsetInParent, Size, IsElided) {
+  // UDT storage comes from a union of all the children's storage, so start out
+  // uninitialized.
+  UsedBytes.reset(0, Size);
+
+  initializeChildren(Sym);
+  if (LayoutSize < Size)
+    UsedBytes.resize(LayoutSize);
 }
 
-UDTLayoutBase::UDTLayoutBase(const PDBSymbol &Symbol, const std::string &Name,
-                             uint32_t Size)
-    : SymbolBase(Symbol), Name(Name), SizeOf(Size) {
-  UsedBytes.resize(Size);
-  ChildrenPerByte.resize(Size);
-  initializeChildren(Symbol);
+uint32_t UDTLayoutBase::tailPadding() const {
+  uint32_t Abs = LayoutItemBase::tailPadding();
+  if (!LayoutItems.empty()) {
+    const LayoutItemBase *Back = LayoutItems.back();
+    uint32_t ChildPadding = Back->LayoutItemBase::tailPadding();
+    if (Abs < ChildPadding)
+      Abs = 0;
+    else
+      Abs -= ChildPadding;
+  }
+  return Abs;
 }
 
 ClassLayout::ClassLayout(const PDBSymbolTypeUDT &UDT)
-    : UDTLayoutBase(UDT, UDT.getName(), UDT.getLength()), UDT(UDT) {}
+    : UDTLayoutBase(nullptr, UDT, UDT.getName(), 0, UDT.getLength(), false),
+      UDT(UDT) {}
 
 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
     : ClassLayout(*UDT) {
@@ -114,23 +134,17 @@ ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
 }
 
 BaseClassLayout::BaseClassLayout(const UDTLayoutBase &Parent,
-                                 std::unique_ptr<PDBSymbolTypeBaseClass> Base)
-    : UDTLayoutBase(*Base, Base->getName(), Base->getLength()),
-      StorageItemBase(Parent, *Base, Base->getName(), Base->getOffset(),
-                      Base->getLength()),
-      Base(std::move(Base)) {
-  IsVirtualBase = this->Base->isVirtualBaseClass();
-}
-
-uint32_t UDTLayoutBase::shallowPaddingSize() const {
-  return UsedBytes.size() - UsedBytes.count();
-}
-
-uint32_t UDTLayoutBase::deepPaddingSize() const {
-  uint32_t Result = shallowPaddingSize();
-  for (auto &Child : ChildStorage)
-    Result += Child->deepPaddingSize();
-  return Result;
+                                 uint32_t OffsetInParent, bool Elide,
+                                 std::unique_ptr<PDBSymbolTypeBaseClass> B)
+    : UDTLayoutBase(&Parent, *B, B->getName(), OffsetInParent, B->getLength(),
+                    Elide),
+      Base(std::move(B)) {
+  if (isEmptyBase()) {
+    // Special case an empty base so that it doesn't get treated as padding.
+    UsedBytes.resize(1);
+    UsedBytes.set(0);
+  }
+  IsVirtualBase = Base->isVirtualBaseClass();
 }
 
 void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
@@ -138,15 +152,16 @@ void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
   // followed by functions, followed by other.  This ordering is necessary
   // so that bases and vtables get initialized before any functions which
   // may override them.
-
   UniquePtrVector<PDBSymbolTypeBaseClass> Bases;
   UniquePtrVector<PDBSymbolTypeVTable> VTables;
   UniquePtrVector<PDBSymbolData> Members;
+  UniquePtrVector<PDBSymbolTypeBaseClass> VirtualBaseSyms;
+
   auto Children = Sym.findAllChildren();
   while (auto Child = Children->getNext()) {
     if (auto Base = unique_dyn_cast<PDBSymbolTypeBaseClass>(Child)) {
       if (Base->isVirtualBaseClass())
-        VirtualBases.push_back(std::move(Base));
+        VirtualBaseSyms.push_back(std::move(Base));
       else
         Bases.push_back(std::move(Base));
     }
@@ -164,20 +179,33 @@ void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
       Other.push_back(std::move(Child));
   }
 
+  // We don't want to have any re-allocations in the list of bases, so make
+  // sure to reserve enough space so that our ArrayRefs don't get invalidated.
+  AllBases.reserve(Bases.size() + VirtualBaseSyms.size());
+
+  // Only add non-virtual bases to the class first.  Only at the end of the
+  // class, after all non-virtual bases and data members have been added do we
+  // add virtual bases.  This way the offsets are correctly aligned when we go
+  // to lay out virtual bases.
   for (auto &Base : Bases) {
-    auto BL = llvm::make_unique<BaseClassLayout>(*this, std::move(Base));
-    BaseClasses.push_back(BL.get());
+    uint32_t Offset = Base->getOffset();
+    // Non-virtual bases never get elided.
+    auto BL = llvm::make_unique<BaseClassLayout>(*this, Offset, false,
+                                                 std::move(Base));
 
+    AllBases.push_back(BL.get());
     addChildToLayout(std::move(BL));
   }
+  NonVirtualBases = AllBases;
 
-  for (auto &VT : VTables) {
-    auto VTLayout = llvm::make_unique<VTableLayoutItem>(*this, std::move(VT));
+  assert(VTables.size() <= 1);
+  if (!VTables.empty()) {
+    auto VTLayout =
+        llvm::make_unique<VTableLayoutItem>(*this, std::move(VTables[0]));
 
     VTable = VTLayout.get();
 
     addChildToLayout(std::move(VTLayout));
-    continue;
   }
 
   for (auto &Data : Members) {
@@ -186,150 +214,74 @@ void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
     addChildToLayout(std::move(DM));
   }
 
-  for (auto &Func : Funcs) {
-    if (!Func->isVirtual())
-      continue;
+  // Make sure add virtual bases before adding functions, since functions may be
+  // overrides of virtual functions declared in a virtual base, so the VTables
+  // and virtual intros need to be correctly initialized.
+  for (auto &VB : VirtualBaseSyms) {
+    int VBPO = VB->getVirtualBasePointerOffset();
+    if (!hasVBPtrAtOffset(VBPO)) {
+      if (auto VBP = VB->getRawSymbol().getVirtualBaseTableType()) {
+        auto VBPL = llvm::make_unique<VBPtrLayoutItem>(*this, std::move(VBP),
+                                                       VBPO, VBP->getLength());
+        VBPtr = VBPL.get();
+        addChildToLayout(std::move(VBPL));
+      }
+    }
 
-    if (Func->isIntroVirtualFunction())
-      addVirtualIntro(*Func);
-    else
-      addVirtualOverride(*Func);
+    // Virtual bases always go at the end.  So just look for the last place we
+    // ended when writing something, and put our virtual base there.
+    // Note that virtual bases get elided unless this is a top-most derived
+    // class.
+    uint32_t Offset = UsedBytes.find_last() + 1;
+    bool Elide = (Parent != nullptr);
+    auto BL =
+        llvm::make_unique<BaseClassLayout>(*this, Offset, Elide, std::move(VB));
+    AllBases.push_back(BL.get());
+
+    // Only lay this virtual base out directly inside of *this* class if this
+    // is a top-most derived class.  Keep track of it regardless, but only
+    // physically lay it out if it's a topmost derived class.
+    addChildToLayout(std::move(BL));
   }
+  VirtualBases = makeArrayRef(AllBases).drop_front(NonVirtualBases.size());
+
+  if (Parent != nullptr)
+    LayoutSize = UsedBytes.find_last() + 1;
 }
 
-void UDTLayoutBase::addVirtualIntro(PDBSymbolFunc &Func) {
-  // Kind of a hack, but we prefer the more common destructor name that people
-  // are familiar with, e.g. ~ClassName.  It seems there are always both and
-  // the vector deleting destructor overwrites the nice destructor, so just
-  // ignore the vector deleting destructor.
-  if (Func.getName() == "__vecDelDtor")
-    return;
-
-  if (!VTable) {
-    // FIXME: Handle this.  What's most likely happening is we have an intro
-    // virtual in a derived class where the base also has an intro virtual.
-    // In this case the vtable lives in the base.  What we really need is
-    // for each UDTLayoutBase to contain a list of all its vtables, and
-    // then propagate this list up the hierarchy so that derived classes have
-    // direct access to their bases' vtables.
-    return;
+bool UDTLayoutBase::hasVBPtrAtOffset(uint32_t Off) const {
+  if (VBPtr && VBPtr->getOffsetInParent() == Off)
+    return true;
+  for (BaseClassLayout *BL : AllBases) {
+    if (BL->hasVBPtrAtOffset(Off - BL->getOffsetInParent()))
+      return true;
   }
-
-  uint32_t Stride = VTable->getElementSize();
-
-  uint32_t Index = Func.getVirtualBaseOffset();
-  assert(Index % Stride == 0);
-  Index /= Stride;
-
-  VTable->setFunction(Index, Func);
+  return false;
 }
 
-VTableLayoutItem *UDTLayoutBase::findVTableAtOffset(uint32_t RelativeOffset) {
-  if (VTable && VTable->getOffsetInParent() == RelativeOffset)
-    return VTable;
-  for (auto Base : BaseClasses) {
-    uint32_t Begin = Base->getOffsetInParent();
-    uint32_t End = Begin + Base->getSize();
-    if (RelativeOffset < Begin || RelativeOffset >= End)
-      continue;
-
-    return Base->findVTableAtOffset(RelativeOffset - Begin);
-  }
+void UDTLayoutBase::addChildToLayout(std::unique_ptr<LayoutItemBase> Child) {
+  uint32_t Begin = Child->getOffsetInParent();
 
-  return nullptr;
-}
+  if (!Child->isElided()) {
+    BitVector ChildBytes = Child->usedBytes();
 
-void UDTLayoutBase::addVirtualOverride(PDBSymbolFunc &Func) {
-  auto Signature = Func.getSignature();
-  auto ThisAdjust = Signature->getThisAdjust();
-  // ThisAdjust tells us which VTable we're looking for.  Specifically, it's
-  // the offset into the current class of the VTable we're looking for.  So
-  // look through the base hierarchy until we find one such that
-  // AbsoluteOffset(VT) == ThisAdjust
-  VTableLayoutItem *VT = findVTableAtOffset(ThisAdjust);
-  if (!VT) {
-    // FIXME: There really should be a vtable here.  If there's not it probably
-    // means that the vtable is in a virtual base, which we don't yet support.
-    assert(!VirtualBases.empty());
-    return;
-  }
-  int32_t OverrideIndex = -1;
-  // Now we've found the VTable.  Func will not have a virtual base offset set,
-  // so instead we need to compare names and signatures.  We iterate each item
-  // in the VTable.  All items should already have non null entries because they
-  // were initialized by the intro virtual, which was guaranteed to come before.
-  for (auto ItemAndIndex : enumerate(VT->funcs())) {
-    auto Item = ItemAndIndex.value();
-    assert(Item);
-    // If the name doesn't match, this isn't an override.  Note that it's ok
-    // for the return type to not match (e.g. co-variant return).
-    if (Item->getName() != Func.getName()) {
-      if (Item->isDestructor() && Func.isDestructor()) {
-        OverrideIndex = ItemAndIndex.index();
-        break;
-      }
-      continue;
-    }
-    // Now make sure it's the right overload.  Get the signature of the existing
-    // vtable method and make sure it has the same arglist and the same cv-ness.
-    auto ExistingSig = Item->getSignature();
-    if (ExistingSig->isConstType() != Signature->isConstType())
-      continue;
-    if (ExistingSig->isVolatileType() != Signature->isVolatileType())
-      continue;
-
-    // Now compare arguments.  Using the raw bytes of the PDB this would be
-    // trivial
-    // because there is an ArgListId and they should be identical.  But DIA
-    // doesn't
-    // expose this, so the best we can do is iterate each argument and confirm
-    // that
-    // each one is identical.
-    if (ExistingSig->getCount() != Signature->getCount())
-      continue;
-    bool IsMatch = true;
-    auto ExistingEnumerator = ExistingSig->getArguments();
-    auto NewEnumerator = Signature->getArguments();
-    for (uint32_t I = 0; I < ExistingEnumerator->getChildCount(); ++I) {
-      auto ExistingArg = ExistingEnumerator->getNext();
-      auto NewArg = NewEnumerator->getNext();
-      if (ExistingArg->getSymIndexId() != NewArg->getSymIndexId()) {
-        IsMatch = false;
-        break;
-      }
-    }
-    if (!IsMatch)
-      continue;
+    // Suppose the child occupies 4 bytes starting at offset 12 in a 32 byte
+    // class.  When we call ChildBytes.resize(32), the Child's storage will
+    // still begin at offset 0, so we need to shift it left by offset bytes
+    // to get it into the right position.
+    ChildBytes.resize(UsedBytes.size());
+    ChildBytes <<= Child->getOffsetInParent();
+    UsedBytes |= ChildBytes;
 
-    // It's a match!  Stick the new function into the VTable.
-    OverrideIndex = ItemAndIndex.index();
-    break;
-  }
-  if (OverrideIndex == -1) {
-    // FIXME: This is probably due to one of the other FIXMEs in this file.
-    return;
-  }
-  VT->setFunction(OverrideIndex, Func);
-}
+    if (ChildBytes.count() > 0) {
+      auto Loc = std::upper_bound(LayoutItems.begin(), LayoutItems.end(), Begin,
+                                  [](uint32_t Off, const LayoutItemBase *Item) {
+                                    return (Off < Item->getOffsetInParent());
+                                  });
 
-void UDTLayoutBase::addChildToLayout(std::unique_ptr<StorageItemBase> Child) {
-  uint32_t Begin = Child->getOffsetInParent();
-  uint32_t End = Begin + Child->getSize();
-  // Due to the empty base optimization, End might point outside the bounds of
-  // the parent class.  If that happens, just clamp the value.
-  End = std::min(End, getClassSize());
-
-  UsedBytes.set(Begin, End);
-  while (Begin != End) {
-    ChildrenPerByte[Begin].push_back(Child.get());
-    ++Begin;
+      LayoutItems.insert(Loc, Child.get());
+    }
   }
 
-  auto Loc = std::upper_bound(
-      ChildStorage.begin(), ChildStorage.end(), Begin,
-      [](uint32_t Off, const std::unique_ptr<StorageItemBase> &Item) {
-        return Off < Item->getOffsetInParent();
-      });
-
-  ChildStorage.insert(Loc, std::move(Child));
+  ChildStorage.push_back(std::move(Child));
 }
\ No newline at end of file