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
getSymbolType(const PDBSymbol & Symbol)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
getTypeLength(const PDBSymbol & Symbol)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
LayoutItemBase(const UDTLayoutBase * Parent,const PDBSymbol * Symbol,const std::string & Name,uint32_t OffsetInParent,uint32_t Size,bool IsElided)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
deepPaddingSize() const58 uint32_t LayoutItemBase::deepPaddingSize() const {
59 return UsedBytes.size() - UsedBytes.count();
60 }
61
tailPadding() const62 uint32_t LayoutItemBase::tailPadding() const {
63 int Last = UsedBytes.find_last();
64
65 return UsedBytes.size() - (Last + 1);
66 }
67
DataMemberLayoutItem(const UDTLayoutBase & Parent,std::unique_ptr<PDBSymbolData> Member)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
VBPtrLayoutItem(const UDTLayoutBase & Parent,std::unique_ptr<PDBSymbolTypeBuiltin> Sym,uint32_t Offset,uint32_t Size)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
getDataMember()87 const PDBSymbolData &DataMemberLayoutItem::getDataMember() {
88 return *dyn_cast<PDBSymbolData>(Symbol);
89 }
90
hasUDTLayout() const91 bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; }
92
getUDTLayout() const93 const ClassLayout &DataMemberLayoutItem::getUDTLayout() const {
94 return *UdtLayout;
95 }
96
VTableLayoutItem(const UDTLayoutBase & Parent,std::unique_ptr<PDBSymbolTypeVTable> VT)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
UDTLayoutBase(const UDTLayoutBase * Parent,const PDBSymbol & Sym,const std::string & Name,uint32_t OffsetInParent,uint32_t Size,bool IsElided)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
tailPadding() const118 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
ClassLayout(const PDBSymbolTypeUDT & UDT)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
ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)143 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT)
144 : ClassLayout(*UDT) {
145 OwnedStorage = std::move(UDT);
146 }
147
immediatePadding() const148 uint32_t ClassLayout::immediatePadding() const {
149 return SizeOf - ImmediateUsedBytes.count();
150 }
151
BaseClassLayout(const UDTLayoutBase & Parent,uint32_t OffsetInParent,bool Elide,std::unique_ptr<PDBSymbolTypeBaseClass> B)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
initializeChildren(const PDBSymbol & Sym)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
hasVBPtrAtOffset(uint32_t Off) const268 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
addChildToLayout(std::unique_ptr<LayoutItemBase> Child)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 }
304