• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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