contrib/llvm/lib/DebugInfo/PDB/UDTLayout.cpp

   1 //===- UDTLayout.cpp ------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/PDB/UDTLayout.h"
  10 #include "llvm/ADT/ArrayRef.h"
  11 #include "llvm/ADT/BitVector.h"
  12 #include "llvm/ADT/STLExtras.h"
  13 #include "llvm/DebugInfo/PDB/IPDBRawSymbol.h"
  14 #include "llvm/DebugInfo/PDB/IPDBSession.h"
  15 #include "llvm/DebugInfo/PDB/PDBSymbol.h"
  16 #include "llvm/DebugInfo/PDB/PDBSymbolData.h"
  17 #include "llvm/DebugInfo/PDB/PDBSymbolFunc.h"
  18 #include "llvm/DebugInfo/PDB/PDBSymbolTypeBaseClass.h"
  19 #include "llvm/DebugInfo/PDB/PDBSymbolTypeBuiltin.h"
  20 #include "llvm/DebugInfo/PDB/PDBSymbolTypePointer.h"
  21 #include "llvm/DebugInfo/PDB/PDBSymbolTypeUDT.h"
  22 #include "llvm/DebugInfo/PDB/PDBSymbolTypeVTable.h"
  23 #include "llvm/DebugInfo/PDB/PDBTypes.h"
  24 #include "llvm/Support/Casting.h"
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <cstdint>
  28 #include <memory>
  29
  30 using namespace llvm;
  31 using namespace llvm::pdb;
  32
  33 static std::unique_ptr<PDBSymbol> getSymbolType(const PDBSymbol &Symbol) {
  34   const IPDBSession &Session = Symbol.getSession();
  35   const IPDBRawSymbol &RawSymbol = Symbol.getRawSymbol();
  36   uint32_t TypeId = RawSymbol.getTypeId();
  37   return Session.getSymbolById(TypeId);
  38 }
  39
  40 static uint32_t getTypeLength(const PDBSymbol &Symbol) {
  41   auto SymbolType = getSymbolType(Symbol);
  42   const IPDBRawSymbol &RawType = SymbolType->getRawSymbol();
  43
  44   return RawType.getLength();
  45 }
  46
  47 LayoutItemBase::LayoutItemBase(const UDTLayoutBase *Parent,
  48                                const PDBSymbol *Symbol, const std::string &Name,
  49                                uint32_t OffsetInParent, uint32_t Size,
  50                                bool IsElided)
  51     : Symbol(Symbol), Parent(Parent), Name(Name),
  52       OffsetInParent(OffsetInParent), SizeOf(Size), LayoutSize(Size),
  53       IsElided(IsElided) {
  54   UsedBytes.resize(SizeOf, true);
  55 }
  56
  57 uint32_t LayoutItemBase::deepPaddingSize() const {
  58   return UsedBytes.size() - UsedBytes.count();
  59 }
  60
  61 uint32_t LayoutItemBase::tailPadding() const {
  62   int Last = UsedBytes.find_last();
  63
  64   return UsedBytes.size() - (Last + 1);
  65 }
  66
  67 DataMemberLayoutItem::DataMemberLayoutItem(
  68     const UDTLayoutBase &Parent, std::unique_ptr<PDBSymbolData> Member)
  69     : LayoutItemBase(&Parent, Member.get(), Member->getName(),
  70                      Member->getOffset(), getTypeLength(*Member), false),
  71       DataMember(std::move(Member)) {
  72   auto Type = DataMember->getType();
  73   if (auto UDT = unique_dyn_cast<PDBSymbolTypeUDT>(Type)) {
  74     UdtLayout = llvm::make_unique<ClassLayout>(std::move(UDT));
  75     UsedBytes = UdtLayout->usedBytes();
  76   }
  77 }
  78
  79 VBPtrLayoutItem::VBPtrLayoutItem(const UDTLayoutBase &Parent,
  80                                  std::unique_ptr<PDBSymbolTypeBuiltin> Sym,
  81                                  uint32_t Offset, uint32_t Size)
  82     : LayoutItemBase(&Parent, Sym.get(), "<vbptr>", Offset, Size, false),
  83       Type(std::move(Sym)) {
  84 }
  85
  86 const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
  87   return *dyn_cast<PDBSymbolData>(Symbol);
  88 }
  89
  90 bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
  91
  92 const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
  93   return *UdtLayout;
  94 }
  95
  96 VTableLayoutItem::VTableLayoutItem(const UDTLayoutBase &Parent,
  97                                    std::unique_ptr<PDBSymbolTypeVTable> VT)
  98     : LayoutItemBase(&Parent, VT.get(), "<vtbl>", 0, getTypeLength(*VT), false),
  99       VTable(std::move(VT)) {
 100   auto VTableType = cast<PDBSymbolTypePointer>(VTable->getType());
 101   ElementSize = VTableType->getLength();
 102 }
 103
 104 UDTLayoutBase::UDTLayoutBase(const UDTLayoutBase *Parent, const PDBSymbol &Sym,
 105                              const std::string &Name, uint32_t OffsetInParent,
 106                              uint32_t Size, bool IsElided)
 107     : LayoutItemBase(Parent, &Sym, Name, OffsetInParent, Size, IsElided) {
 108   // UDT storage comes from a union of all the children's storage, so start out
 109   // uninitialized.
 110   UsedBytes.reset(0, Size);
 111
 112   initializeChildren(Sym);
 113   if (LayoutSize < Size)
 114     UsedBytes.resize(LayoutSize);
 115 }
 116
 117 uint32_t UDTLayoutBase::tailPadding() const {
 118   uint32_t Abs = LayoutItemBase::tailPadding();
 119   if (!LayoutItems.empty()) {
 120     const LayoutItemBase *Back = LayoutItems.back();
 121     uint32_t ChildPadding = Back->LayoutItemBase::tailPadding();
 122     if (Abs < ChildPadding)
 123       Abs = 0;
 124     else
 125       Abs -= ChildPadding;
 126   }
 127   return Abs;
 128 }
 129
 130 ClassLayout::ClassLayout(const PDBSymbolTypeUDT &UDT)
 131     : UDTLayoutBase(nullptr, UDT, UDT.getName(), 0, UDT.getLength(), false),
 132       UDT(UDT) {
 133   ImmediateUsedBytes.resize(SizeOf, false);
 134   for (auto &LI : LayoutItems) {
 135     uint32_t Begin = LI->getOffsetInParent();
 136     uint32_t End = Begin + LI->getLayoutSize();
 137     End = std::min(SizeOf, End);
 138     ImmediateUsedBytes.set(Begin, End);
 139   }
 140 }
 141
 142 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
 143     : ClassLayout(*UDT) {
 144   OwnedStorage = std::move(UDT);
 145 }
 146
 147 uint32_t ClassLayout::immediatePadding() const {
 148   return SizeOf - ImmediateUsedBytes.count();
 149 }
 150
 151 BaseClassLayout::BaseClassLayout(const UDTLayoutBase &Parent,
 152                                  uint32_t OffsetInParent, bool Elide,
 153                                  std::unique_ptr<PDBSymbolTypeBaseClass> B)
 154     : UDTLayoutBase(&Parent, *B, B->getName(), OffsetInParent, B->getLength(),
 155                     Elide),
 156       Base(std::move(B)) {
 157   if (isEmptyBase()) {
 158     // Special case an empty base so that it doesn't get treated as padding.
 159     UsedBytes.resize(1);
 160     UsedBytes.set(0);
 161   }
 162   IsVirtualBase = Base->isVirtualBaseClass();
 163 }
 164
 165 void UDTLayoutBase::initializeChildren(const PDBSymbol &Sym) {
 166   // Handled bases first, followed by VTables, followed by data members,
 167   // followed by functions, followed by other.  This ordering is necessary
 168   // so that bases and vtables get initialized before any functions which
 169   // may override them.
 170   UniquePtrVector<PDBSymbolTypeBaseClass> Bases;
 171   UniquePtrVector<PDBSymbolTypeVTable> VTables;
 172   UniquePtrVector<PDBSymbolData> Members;
 173   UniquePtrVector<PDBSymbolTypeBaseClass> VirtualBaseSyms;
 174
 175   auto Children = Sym.findAllChildren();
 176   while (auto Child = Children->getNext()) {
 177     if (auto Base = unique_dyn_cast<PDBSymbolTypeBaseClass>(Child)) {
 178       if (Base->isVirtualBaseClass())
 179         VirtualBaseSyms.push_back(std::move(Base));
 180       else
 181         Bases.push_back(std::move(Base));
 182     }
 183     else if (auto Data = unique_dyn_cast<PDBSymbolData>(Child)) {
 184       if (Data->getDataKind() == PDB_DataKind::Member)
 185         Members.push_back(std::move(Data));
 186       else
 187         Other.push_back(std::move(Data));
 188     } else if (auto VT = unique_dyn_cast<PDBSymbolTypeVTable>(Child))
 189       VTables.push_back(std::move(VT));
 190     else if (auto Func = unique_dyn_cast<PDBSymbolFunc>(Child))
 191       Funcs.push_back(std::move(Func));
 192     else {
 193       Other.push_back(std::move(Child));
 194     }
 195   }
 196
 197   // We don't want to have any re-allocations in the list of bases, so make
 198   // sure to reserve enough space so that our ArrayRefs don't get invalidated.
 199   AllBases.reserve(Bases.size() + VirtualBaseSyms.size());
 200
 201   // Only add non-virtual bases to the class first.  Only at the end of the
 202   // class, after all non-virtual bases and data members have been added do we
 203   // add virtual bases.  This way the offsets are correctly aligned when we go
 204   // to lay out virtual bases.
 205   for (auto &Base : Bases) {
 206     uint32_t Offset = Base->getOffset();
 207     // Non-virtual bases never get elided.
 208     auto BL = llvm::make_unique<BaseClassLayout>(*this, Offset, false,
 209                                                  std::move(Base));
 210
 211     AllBases.push_back(BL.get());
 212     addChildToLayout(std::move(BL));
 213   }
 214   NonVirtualBases = AllBases;
 215
 216   assert(VTables.size() <= 1);
 217   if (!VTables.empty()) {
 218     auto VTLayout =
 219         llvm::make_unique<VTableLayoutItem>(*this, std::move(VTables[0]));
 220
 221     VTable = VTLayout.get();
 222
 223     addChildToLayout(std::move(VTLayout));
 224   }
 225
 226   for (auto &Data : Members) {
 227     auto DM = llvm::make_unique<DataMemberLayoutItem>(*this, std::move(Data));
 228
 229     addChildToLayout(std::move(DM));
 230   }
 231
 232   // Make sure add virtual bases before adding functions, since functions may be
 233   // overrides of virtual functions declared in a virtual base, so the VTables
 234   // and virtual intros need to be correctly initialized.
 235   for (auto &VB : VirtualBaseSyms) {
 236     int VBPO = VB->getVirtualBasePointerOffset();
 237     if (!hasVBPtrAtOffset(VBPO)) {
 238       if (auto VBP = VB->getRawSymbol().getVirtualBaseTableType()) {
 239         auto VBPL = llvm::make_unique<VBPtrLayoutItem>(*this, std::move(VBP),
 240                                                        VBPO, VBP->getLength());
 241         VBPtr = VBPL.get();
 242         addChildToLayout(std::move(VBPL));
 243       }
 244     }
 245
 246     // Virtual bases always go at the end.  So just look for the last place we
 247     // ended when writing something, and put our virtual base there.
 248     // Note that virtual bases get elided unless this is a top-most derived
 249     // class.
 250     uint32_t Offset = UsedBytes.find_last() + 1;
 251     bool Elide = (Parent != nullptr);
 252     auto BL =
 253         llvm::make_unique<BaseClassLayout>(*this, Offset, Elide, std::move(VB));
 254     AllBases.push_back(BL.get());
 255
 256     // Only lay this virtual base out directly inside of *this* class if this
 257     // is a top-most derived class.  Keep track of it regardless, but only
 258     // physically lay it out if it's a topmost derived class.
 259     addChildToLayout(std::move(BL));
 260   }
 261   VirtualBases = makeArrayRef(AllBases).drop_front(NonVirtualBases.size());
 262
 263   if (Parent != nullptr)
 264     LayoutSize = UsedBytes.find_last() + 1;
 265 }
 266
 267 bool UDTLayoutBase::hasVBPtrAtOffset(uint32_t Off) const {
 268   if (VBPtr && VBPtr->getOffsetInParent() == Off)
 269     return true;
 270   for (BaseClassLayout *BL : AllBases) {
 271     if (BL->hasVBPtrAtOffset(Off - BL->getOffsetInParent()))
 272       return true;
 273   }
 274   return false;
 275 }
 276
 277 void UDTLayoutBase::addChildToLayout(std::unique_ptr<LayoutItemBase> Child) {
 278   uint32_t Begin = Child->getOffsetInParent();
 279
 280   if (!Child->isElided()) {
 281     BitVector ChildBytes = Child->usedBytes();
 282
 283     // Suppose the child occupies 4 bytes starting at offset 12 in a 32 byte
 284     // class.  When we call ChildBytes.resize(32), the Child's storage will
 285     // still begin at offset 0, so we need to shift it left by offset bytes
 286     // to get it into the right position.
 287     ChildBytes.resize(UsedBytes.size());
 288     ChildBytes <<= Child->getOffsetInParent();
 289     UsedBytes |= ChildBytes;
 290
 291     if (ChildBytes.count() > 0) {
 292       auto Loc = std::upper_bound(LayoutItems.begin(), LayoutItems.end(), Begin,
 293                                   [](uint32_t Off, const LayoutItemBase *Item) {
 294                                     return (Off < Item->getOffsetInParent());
 295                                   });
 296
 297       LayoutItems.insert(Loc, Child.get());
 298     }
 299   }
 300
 301   ChildStorage.push_back(std::move(Child));
 302 }