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