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 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 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 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 58 uint32_t LayoutItemBase::deepPaddingSize() const { 59 return UsedBytes.size() - UsedBytes.count(); 60 } 61 62 uint32_t LayoutItemBase::tailPadding() const { 63 int Last = UsedBytes.find_last(); 64 65 return UsedBytes.size() - (Last + 1); 66 } 67 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 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 87 const PDBSymbolData &DataMemberLayoutItem::getDataMember() { 88 return *dyn_cast<PDBSymbolData>(Symbol); 89 } 90 91 bool DataMemberLayoutItem::hasUDTLayout() const { return UdtLayout != nullptr; } 92 93 const ClassLayout &DataMemberLayoutItem::getUDTLayout() const { 94 return *UdtLayout; 95 } 96 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 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 118 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 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 143 ClassLayout::ClassLayout(std::unique_ptr<PDBSymbolTypeUDT> UDT) 144 : ClassLayout(*UDT) { 145 OwnedStorage = std::move(UDT); 146 } 147 148 uint32_t ClassLayout::immediatePadding() const { 149 return SizeOf - ImmediateUsedBytes.count(); 150 } 151 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 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 268 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 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