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

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