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