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
30using namespace llvm;
31using namespace llvm::pdb;
32
33static 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
40static uint32_t getTypeLength(const PDBSymbol &Symbol) {
41  auto SymbolType = getSymbolType(Symbol);
42  const IPDBRawSymbol &RawType = SymbolType->getRawSymbol();
43
44  return RawType.getLength();
45}
46
47LayoutItemBase::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
57uint32_t LayoutItemBase::deepPaddingSize() const {
58  return UsedBytes.size() - UsedBytes.count();
59}
60
61uint32_t LayoutItemBase::tailPadding() const {
62  int Last = UsedBytes.find_last();
63
64  return UsedBytes.size() - (Last + 1);
65}
66
67DataMemberLayoutItem::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 = std::make_unique<ClassLayout>(std::move(UDT));
75    UsedBytes = UdtLayout->usedBytes();
76  }
77}
78
79VBPtrLayoutItem::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
86const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
87  return *cast<PDBSymbolData>(Symbol);
88}
89
90bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
91
92const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
93  return *UdtLayout;
94}
95
96VTableLayoutItem::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
104UDTLayoutBase::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
117uint32_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
130ClassLayout::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
142ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
143    : ClassLayout(*UDT) {
144  OwnedStorage = std::move(UDT);
145}
146
147uint32_t ClassLayout::immediatePadding() const {
148  return SizeOf - ImmediateUsedBytes.count();
149}
150
151BaseClassLayout::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
165void 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 = std::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        std::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 = std::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 = std::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        std::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
267bool 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
277void 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}
303