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
33using namespace llvm;
34using namespace llvm::pdb;
35
36static 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
43static uint32_t getTypeLength(const PDBSymbol &Symbol) {
44  auto SymbolType = getSymbolType(Symbol);
45  const IPDBRawSymbol &RawType = SymbolType->getRawSymbol();
46
47  return RawType.getLength();
48}
49
50LayoutItemBase::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
60uint32_t LayoutItemBase::deepPaddingSize() const {
61  return UsedBytes.size() - UsedBytes.count();
62}
63
64uint32_t LayoutItemBase::tailPadding() const {
65  int Last = UsedBytes.find_last();
66
67  return UsedBytes.size() - (Last + 1);
68}
69
70DataMemberLayoutItem::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
82VBPtrLayoutItem::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
89const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
90  return *cast<PDBSymbolData>(Symbol);
91}
92
93bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
94
95const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
96  return *UdtLayout;
97}
98
99VTableLayoutItem::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
107UDTLayoutBase::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
120uint32_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
133ClassLayout::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
145ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
146    : ClassLayout(*UDT) {
147  OwnedStorage = std::move(UDT);
148}
149
150uint32_t ClassLayout::immediatePadding() const {
151  return SizeOf - ImmediateUsedBytes.count();
152}
153
154BaseClassLayout::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
168void 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
270bool 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
280void 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}
306