1//===- bolt/Rewrite/DebugNames.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 "bolt/Core/DebugNames.h"
10#include "bolt/Core/BinaryContext.h"
11#include "llvm/DebugInfo/DWARF/DWARFExpression.h"
12#include "llvm/DebugInfo/DWARF/DWARFTypeUnit.h"
13#include "llvm/Support/EndianStream.h"
14#include "llvm/Support/LEB128.h"
15#include <cstdint>
16#include <optional>
17
18namespace llvm {
19namespace bolt {
20DWARF5AcceleratorTable::DWARF5AcceleratorTable(
21 const bool CreateDebugNames, BinaryContext &BC,
22 DebugStrWriter &MainBinaryStrWriter)
23 : BC(BC), MainBinaryStrWriter(MainBinaryStrWriter) {
24 NeedToCreate = CreateDebugNames || BC.getDebugNamesSection();
25 if (!NeedToCreate)
26 return;
27 FullTableBuffer = std::make_unique<DebugStrBufferVector>();
28 FullTableStream = std::make_unique<raw_svector_ostream>(args&: *FullTableBuffer);
29 StrBuffer = std::make_unique<DebugStrBufferVector>();
30 StrStream = std::make_unique<raw_svector_ostream>(args&: *StrBuffer);
31 EntriesBuffer = std::make_unique<DebugStrBufferVector>();
32 Entriestream = std::make_unique<raw_svector_ostream>(args&: *EntriesBuffer);
33 AugStringBuffer = std::make_unique<DebugStrBufferVector>();
34 AugStringtream = std::make_unique<raw_svector_ostream>(args&: *AugStringBuffer);
35
36 // Binary has split-dwarf CUs.
37 // Even thought for non-skeleton-cu all names are in .debug_str.dwo section,
38 // for the .debug_names contributions they are in .debug_str section.
39 if (BC.getNumDWOCUs()) {
40 DataExtractor StrData(BC.DwCtx->getDWARFObj().getStrSection(),
41 BC.DwCtx->isLittleEndian(), 0);
42 uint64_t Offset = 0;
43 uint64_t StrOffset = 0;
44 while (StrData.isValidOffset(offset: Offset)) {
45 Error Err = Error::success();
46 const char *CStr = StrData.getCStr(OffsetPtr: &Offset, Err: &Err);
47 if (Err) {
48 NeedToCreate = false;
49 BC.errs() << "BOLT-WARNING: [internal-dwarf-error]: Could not extract "
50 "string from .debug_str section at offset: "
51 << Twine::utohexstr(Val: StrOffset) << ".\n";
52 return;
53 }
54 auto R = StrCacheToOffsetMap.try_emplace(
55 Key: llvm::hash_value(S: llvm::StringRef(CStr)), Args&: StrOffset);
56 if (!R.second)
57 BC.errs()
58 << "BOLT-WARNING: [internal-dwarf-error]: collision occured on "
59 << CStr << " at offset : 0x" << Twine::utohexstr(Val: StrOffset)
60 << ". Previous string offset is: 0x"
61 << Twine::utohexstr(Val: R.first->second) << ".\n";
62 StrOffset = Offset;
63 }
64 }
65}
66
67void DWARF5AcceleratorTable::setCurrentUnit(DWARFUnit &Unit,
68 const uint64_t UnitStartOffset) {
69 CurrentUnit = nullptr;
70 CurrentUnitOffset = UnitStartOffset;
71 std::optional<uint64_t> DWOID = Unit.getDWOId();
72 // We process skeleton CUs after DWO Units for it.
73 // Patching offset in CU list to correct one.
74 if (!Unit.isDWOUnit() && DWOID) {
75 auto Iter = CUOffsetsToPatch.find(Val: *DWOID);
76 // Check in case no entries were added from non skeleton DWO section.
77 if (Iter != CUOffsetsToPatch.end())
78 CUList[Iter->second] = UnitStartOffset;
79 }
80}
81
82void DWARF5AcceleratorTable::addUnit(DWARFUnit &Unit,
83 const std::optional<uint64_t> &DWOID) {
84 constexpr uint32_t BADCUOFFSET = 0xBADBAD;
85 StrSection = Unit.getStringSection();
86 if (Unit.isTypeUnit()) {
87 if (DWOID) {
88 // We adding an entry for a DWO TU. The DWO CU might not have any entries,
89 // so need to add it to the list pre-emptively.
90 auto Iter = CUOffsetsToPatch.insert(KV: {*DWOID, CUList.size()});
91 if (Iter.second)
92 CUList.push_back(Elt: BADCUOFFSET);
93 const uint64_t TUHash = cast<DWARFTypeUnit>(Val: &Unit)->getTypeHash();
94 if (!TUHashToIndexMap.count(Val: TUHash)) {
95 TUHashToIndexMap.insert(KV: {TUHash, ForeignTUList.size()});
96 ForeignTUList.push_back(Elt: TUHash);
97 }
98 } else {
99 LocalTUList.push_back(Elt: CurrentUnitOffset);
100 }
101 } else {
102 if (DWOID) {
103 // This is a path for split dwarf without type units.
104 // We process DWO Units before Skeleton CU. So at this point we don't know
105 // the offset of Skeleton CU. Adding CULit index to a map to patch later
106 // with the correct offset.
107 auto Iter = CUOffsetsToPatch.insert(KV: {*DWOID, CUList.size()});
108 if (Iter.second)
109 CUList.push_back(Elt: BADCUOFFSET);
110 } else {
111 CUList.push_back(Elt: CurrentUnitOffset);
112 }
113 }
114}
115
116// Returns true if DW_TAG_variable should be included in .debug-names based on
117// section 6.1.1.1 for DWARF5 spec.
118static bool shouldIncludeVariable(const DWARFUnit &Unit, const DIE &Die) {
119 const DIEValue LocAttrInfo =
120 Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_location);
121 if (!LocAttrInfo)
122 return false;
123 if (!(doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Exprloc,
124 DwarfVersion: Unit.getVersion()) ||
125 doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Block,
126 DwarfVersion: Unit.getVersion())))
127 return false;
128 std::vector<uint8_t> Sblock;
129 auto constructVect =
130 [&](const DIEValueList::const_value_range &Iter) -> void {
131 for (const DIEValue &Val : Iter)
132 Sblock.push_back(x: Val.getDIEInteger().getValue());
133 };
134 if (doesFormBelongToClass(Form: LocAttrInfo.getForm(), FC: DWARFFormValue::FC_Exprloc,
135 DwarfVersion: Unit.getVersion()))
136 constructVect(LocAttrInfo.getDIELoc().values());
137 else
138 constructVect(LocAttrInfo.getDIEBlock().values());
139 ArrayRef<uint8_t> Expr = ArrayRef<uint8_t>(Sblock);
140 DataExtractor Data(StringRef((const char *)Expr.data(), Expr.size()),
141 Unit.getContext().isLittleEndian(), 0);
142 DWARFExpression LocExpr(Data, Unit.getAddressByteSize(),
143 Unit.getFormParams().Format);
144 for (const DWARFExpression::Operation &Expr : LocExpr)
145 if (Expr.getCode() == dwarf::DW_OP_addrx ||
146 Expr.getCode() == dwarf::DW_OP_form_tls_address ||
147 Expr.getCode() == dwarf::DW_OP_GNU_push_tls_address)
148 return true;
149 return false;
150}
151
152bool static canProcess(const DWARFUnit &Unit, const DIE &Die,
153 std::string &NameToUse, const bool TagsOnly) {
154 if (Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_declaration))
155 return false;
156 switch (Die.getTag()) {
157 case dwarf::DW_TAG_base_type:
158 case dwarf::DW_TAG_class_type:
159 case dwarf::DW_TAG_enumeration_type:
160 case dwarf::DW_TAG_imported_declaration:
161 case dwarf::DW_TAG_pointer_type:
162 case dwarf::DW_TAG_structure_type:
163 case dwarf::DW_TAG_typedef:
164 case dwarf::DW_TAG_unspecified_type:
165 case dwarf::DW_TAG_union_type:
166 if (TagsOnly || Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name))
167 return true;
168 return false;
169 case dwarf::DW_TAG_namespace:
170 // According to DWARF5 spec namespaces without DW_AT_name needs to have
171 // "(anonymous namespace)"
172 if (!Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name))
173 NameToUse = "(anonymous namespace)";
174 return true;
175 case dwarf::DW_TAG_inlined_subroutine:
176 case dwarf::DW_TAG_label:
177 case dwarf::DW_TAG_subprogram:
178 if (TagsOnly || Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_low_pc) ||
179 Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_high_pc) ||
180 Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_ranges) ||
181 Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_entry_pc))
182 return true;
183 return false;
184 case dwarf::DW_TAG_variable:
185 return TagsOnly || shouldIncludeVariable(Unit, Die);
186 default:
187 break;
188 }
189 return false;
190}
191
192bool DWARF5AcceleratorTable::canGenerateEntryWithCrossCUReference(
193 const DWARFUnit &Unit, const DIE &Die,
194 const DWARFAbbreviationDeclaration::AttributeSpec &AttrSpec) {
195 if (!isCreated())
196 return false;
197 std::string NameToUse = "";
198 if (!canProcess(Unit, Die, NameToUse, TagsOnly: true))
199 return false;
200 return (AttrSpec.Attr == dwarf::Attribute::DW_AT_abstract_origin ||
201 AttrSpec.Attr == dwarf::Attribute::DW_AT_specification) &&
202 AttrSpec.Form == dwarf::DW_FORM_ref_addr;
203}
204/// Returns name offset in String Offset section.
205static uint64_t getNameOffset(BinaryContext &BC, DWARFUnit &Unit,
206 const uint64_t Index) {
207 const DWARFSection &StrOffsetsSection = Unit.getStringOffsetSection();
208 const std::optional<StrOffsetsContributionDescriptor> &Contr =
209 Unit.getStringOffsetsTableContribution();
210 if (!Contr) {
211 BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not get "
212 "StringOffsetsTableContribution for unit at offset: "
213 << Twine::utohexstr(Val: Unit.getOffset()) << ".\n";
214 return 0;
215 }
216
217 const uint8_t DwarfOffsetByteSize = Contr->getDwarfOffsetByteSize();
218 return support::endian::read32le(P: StrOffsetsSection.Data.data() + Contr->Base +
219 Index * DwarfOffsetByteSize);
220}
221
222static uint64_t getEntryID(const BOLTDWARF5AccelTableData &Entry) {
223 return reinterpret_cast<uint64_t>(&Entry);
224}
225
226uint32_t DWARF5AcceleratorTable::getUnitID(const DWARFUnit &Unit,
227 const std::optional<uint64_t> &DWOID,
228 bool &IsTU) {
229 IsTU = Unit.isTypeUnit();
230 if (IsTU) {
231 if (DWOID) {
232 const uint64_t TUHash = cast<DWARFTypeUnit>(Val: &Unit)->getTypeHash();
233 auto Iter = TUHashToIndexMap.find(Val: TUHash);
234 assert(Iter != TUHashToIndexMap.end() && "Could not find TU hash in map");
235 return Iter->second;
236 }
237 return LocalTUList.size() - 1;
238 }
239 return CUList.size() - 1;
240}
241
242std::optional<std::string> DWARF5AcceleratorTable::getName(
243 DWARFUnit &Unit, const std::optional<uint64_t> &DWOID,
244 const std::string &NameToUse, DIEValue ValName) {
245 if ((!ValName || ValName.getForm() == dwarf::DW_FORM_string) &&
246 NameToUse.empty())
247 return std::nullopt;
248 std::string Name = "";
249 uint64_t NameIndexOffset = 0;
250 if (NameToUse.empty()) {
251 NameIndexOffset = ValName.getDIEInteger().getValue();
252 if (ValName.getForm() != dwarf::DW_FORM_strp)
253 NameIndexOffset = getNameOffset(BC, Unit, Index: NameIndexOffset);
254 // Counts on strings end with '\0'.
255 Name = std::string(&StrSection.data()[NameIndexOffset]);
256 } else {
257 Name = NameToUse;
258 }
259 auto &It = Entries[Name];
260 if (It.Values.empty()) {
261 if (DWOID && NameToUse.empty()) {
262 // For DWO Unit the offset is in the .debug_str.dwo section.
263 // Need to find offset for the name in the .debug_str section.
264 llvm::hash_code Hash = llvm::hash_value(S: llvm::StringRef(Name));
265 auto ItCache = StrCacheToOffsetMap.find(Val: Hash);
266 if (ItCache == StrCacheToOffsetMap.end())
267 NameIndexOffset = MainBinaryStrWriter.addString(Str: Name);
268 else
269 NameIndexOffset = ItCache->second;
270 }
271 if (!NameToUse.empty())
272 NameIndexOffset = MainBinaryStrWriter.addString(Str: Name);
273 It.StrOffset = NameIndexOffset;
274 // This is the same hash function used in DWARF5AccelTableData.
275 It.HashValue = caseFoldingDjbHash(Buffer: Name);
276 }
277 return Name;
278}
279
280std::optional<BOLTDWARF5AccelTableData *> DWARF5AcceleratorTable::addEntry(
281 DWARFUnit &DU, const DIE &CurrDie, const std::optional<uint64_t> &DWOID,
282 const std::optional<BOLTDWARF5AccelTableData *> &Parent,
283 const std::optional<std::string> &Name,
284 const uint32_t NumberParentsInChain) {
285 if (!Name)
286 return std::nullopt;
287
288 auto &It = Entries[*Name];
289 bool IsTU = false;
290 uint32_t DieTag = CurrDie.getTag();
291 uint32_t UnitID = getUnitID(Unit: DU, DWOID, IsTU);
292 std::optional<unsigned> SecondIndex = std::nullopt;
293 if (IsTU && DWOID) {
294 auto Iter = CUOffsetsToPatch.find(Val: *DWOID);
295 if (Iter == CUOffsetsToPatch.end())
296 BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
297 "DWO ID in CU offsets for second Unit Index "
298 << *Name << ". For DIE at offset: "
299 << Twine::utohexstr(Val: CurrentUnitOffset + CurrDie.getOffset())
300 << ".\n";
301 SecondIndex = Iter->second;
302 }
303 std::optional<uint64_t> ParentOffset =
304 (Parent ? std::optional<uint64_t>(getEntryID(Entry: **Parent)) : std::nullopt);
305 // This will be only populated in writeEntry, in order to keep only the parent
306 // entries, and keep the footprint down.
307 if (ParentOffset)
308 EntryRelativeOffsets.insert(KV: {*ParentOffset, 0});
309 bool IsParentRoot = false;
310 // If there is no parent and no valid Entries in parent chain this is a root
311 // to be marked with a flag.
312 if (!Parent && !NumberParentsInChain)
313 IsParentRoot = true;
314 It.Values.push_back(x: new (Allocator) BOLTDWARF5AccelTableData(
315 CurrDie.getOffset(), ParentOffset, DieTag, UnitID, IsParentRoot, IsTU,
316 SecondIndex));
317 return It.Values.back();
318}
319
320std::optional<BOLTDWARF5AccelTableData *>
321DWARF5AcceleratorTable::processReferencedDie(
322 DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID,
323 const std::optional<BOLTDWARF5AccelTableData *> &Parent,
324 const std::string &NameToUse, const uint32_t NumberParentsInChain,
325 const dwarf::Attribute &Attr) {
326 DIEValue Value = Die.findAttribute(Attribute: Attr);
327 if (!Value)
328 return std::nullopt;
329 auto getReferenceDie = [&](const DIEValue &Value, const DIE *RefDieUsed)
330 -> std::optional<std::pair<DWARFUnit *, const DIE *>> {
331 if (!Value)
332 return std::nullopt;
333 if (Value.getForm() == dwarf::DW_FORM_ref_addr) {
334 auto Iter = CrossCUDies.find(Val: Value.getDIEInteger().getValue());
335 if (Iter == CrossCUDies.end()) {
336 BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
337 "referenced DIE in CrossCUDies for "
338 << Twine::utohexstr(Val: Value.getDIEInteger().getValue())
339 << ".\n";
340 return std::nullopt;
341 }
342 return Iter->second;
343 }
344 const DIEEntry &DIEENtry = Value.getDIEEntry();
345 return {{&Unit, &DIEENtry.getEntry()}};
346 };
347
348 DIEValue AttrValLinkageName;
349 DIEValue AttrValName = Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name);
350 DWARFUnit *RefUnit = &Unit;
351 const DIE *RefDieUsed = &Die;
352 // It is possible to have DW_TAG_subprogram only with DW_AT_linkage_name that
353 // DW_AT_abstract_origin/DW_AT_specification point to.
354 while (!AttrValName) {
355 std::optional<std::pair<DWARFUnit *, const DIE *>> RefDUDie =
356 getReferenceDie(Value, RefDieUsed);
357 if (!RefDUDie)
358 break;
359 RefUnit = RefDUDie->first;
360 const DIE &RefDie = *RefDUDie->second;
361 RefDieUsed = &RefDie;
362 if (!AttrValLinkageName)
363 AttrValLinkageName =
364 RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_linkage_name);
365 AttrValName = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_name);
366 Value = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_abstract_origin);
367 if (!Value)
368 Value = RefDie.findAttribute(Attribute: dwarf::Attribute::DW_AT_specification);
369 }
370 addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent,
371 Name: getName(Unit&: *RefUnit, DWOID, NameToUse, ValName: AttrValLinkageName),
372 NumberParentsInChain);
373 return addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent,
374 Name: getName(Unit&: *RefUnit, DWOID, NameToUse, ValName: AttrValName),
375 NumberParentsInChain);
376}
377
378std::optional<BOLTDWARF5AccelTableData *>
379DWARF5AcceleratorTable::addAccelTableEntry(
380 DWARFUnit &Unit, const DIE &Die, const std::optional<uint64_t> &DWOID,
381 const uint32_t NumberParentsInChain,
382 std::optional<BOLTDWARF5AccelTableData *> &Parent) {
383 if (Unit.getVersion() < 5 || !NeedToCreate)
384 return std::nullopt;
385 std::string NameToUse = "";
386
387 if (!canProcess(Unit, Die, NameToUse, TagsOnly: false))
388 return std::nullopt;
389
390 // Adds a Unit to either CU, LocalTU or ForeignTU list the first time we
391 // encounter it.
392 // Invoking it here so that we don't add Units that don't have any entries.
393 if (&Unit != CurrentUnit) {
394 CurrentUnit = &Unit;
395 addUnit(Unit, DWOID);
396 }
397
398 // Minor optimization not to add entry twice for DW_TAG_namespace if it has no
399 // DW_AT_name.
400 std::optional<BOLTDWARF5AccelTableData *> LinkageEntry = std::nullopt;
401 DIEValue NameVal = Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_name);
402 DIEValue LinkageNameVal =
403 Die.findAttribute(Attribute: dwarf::Attribute::DW_AT_linkage_name);
404 if (!(Die.getTag() == dwarf::DW_TAG_namespace && !NameVal))
405 LinkageEntry = addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent,
406 Name: getName(Unit, DWOID, NameToUse, ValName: LinkageNameVal),
407 NumberParentsInChain);
408
409 std::optional<BOLTDWARF5AccelTableData *> NameEntry =
410 addEntry(DU&: Unit, CurrDie: Die, DWOID, Parent,
411 Name: getName(Unit, DWOID, NameToUse, ValName: NameVal), NumberParentsInChain);
412 if (NameEntry)
413 return NameEntry;
414
415 // The DIE doesn't have DW_AT_name or DW_AT_linkage_name, so we need to see if
416 // we can follow other attributes to find them. For the purposes of
417 // determining whether a debug information entry has a particular
418 // attribute (such as DW_AT_name), if debug information entry A has a
419 // DW_AT_specification or DW_AT_abstract_origin attribute pointing to another
420 // debug information entry B, any attributes of B are considered to be
421 // part of A.
422 if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie(
423 Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain,
424 Attr: dwarf::Attribute::DW_AT_abstract_origin))
425 return *Entry;
426 if (std::optional<BOLTDWARF5AccelTableData *> Entry = processReferencedDie(
427 Unit, Die, DWOID, Parent, NameToUse, NumberParentsInChain,
428 Attr: dwarf::Attribute::DW_AT_specification))
429 return *Entry;
430
431 // This point can be hit by DW_TAG_varialbe that has no DW_AT_name.
432 return std::nullopt;
433}
434
435/// Algorithm from llvm implementation.
436void DWARF5AcceleratorTable::computeBucketCount() {
437 // First get the number of unique hashes.
438 std::vector<uint32_t> Uniques;
439 Uniques.reserve(n: Entries.size());
440 for (const auto &E : Entries)
441 Uniques.push_back(x: E.second.HashValue);
442 array_pod_sort(Start: Uniques.begin(), End: Uniques.end());
443 std::vector<uint32_t>::iterator P = llvm::unique(R&: Uniques);
444
445 UniqueHashCount = std::distance(first: Uniques.begin(), last: P);
446
447 if (UniqueHashCount > 1024)
448 BucketCount = UniqueHashCount / 4;
449 else if (UniqueHashCount > 16)
450 BucketCount = UniqueHashCount / 2;
451 else
452 BucketCount = std::max<uint32_t>(a: UniqueHashCount, b: 1);
453}
454
455/// Bucket code as in: AccelTableBase::finalize()
456void DWARF5AcceleratorTable::finalize() {
457 if (!NeedToCreate)
458 return;
459 // Figure out how many buckets we need, then compute the bucket contents and
460 // the final ordering. The hashes and offsets can be emitted by walking these
461 // data structures.
462 computeBucketCount();
463
464 // Compute bucket contents and final ordering.
465 Buckets.resize(new_size: BucketCount);
466 for (auto &E : Entries) {
467 uint32_t Bucket = E.second.HashValue % BucketCount;
468 Buckets[Bucket].push_back(x: &E.second);
469 }
470
471 // Sort the contents of the buckets by hash value so that hash collisions end
472 // up together. Stable sort makes testing easier and doesn't cost much more.
473 for (HashList &Bucket : Buckets) {
474 llvm::stable_sort(Range&: Bucket, C: [](const HashData *LHS, const HashData *RHS) {
475 return LHS->HashValue < RHS->HashValue;
476 });
477 for (HashData *H : Bucket)
478 llvm::stable_sort(Range&: H->Values, C: [](const BOLTDWARF5AccelTableData *LHS,
479 const BOLTDWARF5AccelTableData *RHS) {
480 return LHS->getDieOffset() < RHS->getDieOffset();
481 });
482 }
483
484 CUIndexForm = DIEInteger::BestForm(/*IsSigned*/ false, Int: CUList.size() - 1);
485 TUIndexForm = DIEInteger::BestForm(
486 /*IsSigned*/ false, Int: LocalTUList.size() + ForeignTUList.size() - 1);
487 const dwarf::FormParams FormParams{.Version: 5, .AddrSize: 4, .Format: dwarf::DwarfFormat::DWARF32, .DwarfUsesRelocationsAcrossSections: false};
488 CUIndexEncodingSize = *dwarf::getFixedFormByteSize(Form: CUIndexForm, Params: FormParams);
489 TUIndexEncodingSize = *dwarf::getFixedFormByteSize(Form: TUIndexForm, Params: FormParams);
490}
491
492std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
493DWARF5AcceleratorTable::getIndexForEntry(
494 const BOLTDWARF5AccelTableData &Value) const {
495 // The foreign TU list immediately follows the local TU list and they both
496 // use the same index, so that if there are N local TU entries, the index for
497 // the first foreign TU is N.
498 if (Value.isTU())
499 return {{.Index: (Value.getSecondUnitID() ? (unsigned)LocalTUList.size() : 0) +
500 Value.getUnitID(),
501 .Encoding: {.Index: dwarf::DW_IDX_type_unit, .Form: TUIndexForm}}};
502 if (CUList.size() > 1)
503 return {{.Index: Value.getUnitID(), .Encoding: {.Index: dwarf::DW_IDX_compile_unit, .Form: CUIndexForm}}};
504 return std::nullopt;
505}
506
507std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
508DWARF5AcceleratorTable::getSecondIndexForEntry(
509 const BOLTDWARF5AccelTableData &Value) const {
510 if (Value.isTU() && CUList.size() > 1 && Value.getSecondUnitID())
511 return {
512 {.Index: *Value.getSecondUnitID(), .Encoding: {.Index: dwarf::DW_IDX_compile_unit, .Form: CUIndexForm}}};
513 return std::nullopt;
514}
515
516void DWARF5AcceleratorTable::populateAbbrevsMap() {
517 for (auto &Bucket : getBuckets()) {
518 for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
519 for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
520 const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
521 getIndexForEntry(Value: *Value);
522 // For entries that need to refer to the foreign type units and to
523 // the CU.
524 const std::optional<DWARF5AccelTable::UnitIndexAndEncoding>
525 SecondEntryRet = getSecondIndexForEntry(Value: *Value);
526 DebugNamesAbbrev Abbrev(Value->getDieTag());
527 if (EntryRet)
528 Abbrev.addAttribute(Attr: EntryRet->Encoding);
529 if (SecondEntryRet)
530 Abbrev.addAttribute(Attr: SecondEntryRet->Encoding);
531 Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_die_offset, .Form: dwarf::DW_FORM_ref4});
532 if (std::optional<uint64_t> Offset = Value->getParentDieOffset())
533 Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_parent, .Form: dwarf::DW_FORM_ref4});
534 else if (Value->isParentRoot())
535 Abbrev.addAttribute(
536 Attr: {.Index: dwarf::DW_IDX_parent, .Form: dwarf::DW_FORM_flag_present});
537 FoldingSetNodeID ID;
538 Abbrev.Profile(ID);
539 void *InsertPos;
540 if (DebugNamesAbbrev *Existing =
541 AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) {
542 Value->setAbbrevNumber(Existing->getNumber());
543 continue;
544 }
545 DebugNamesAbbrev *NewAbbrev =
546 new (Alloc) DebugNamesAbbrev(std::move(Abbrev));
547 AbbreviationsVector.push_back(Elt: NewAbbrev);
548 NewAbbrev->setNumber(AbbreviationsVector.size());
549 AbbreviationsSet.InsertNode(N: NewAbbrev, InsertPos);
550 Value->setAbbrevNumber(NewAbbrev->getNumber());
551 }
552 }
553 }
554}
555
556void DWARF5AcceleratorTable::writeEntry(BOLTDWARF5AccelTableData &Entry) {
557 const uint64_t EntryID = getEntryID(Entry);
558 if (EntryRelativeOffsets.find(Val: EntryID) != EntryRelativeOffsets.end())
559 EntryRelativeOffsets[EntryID] = EntriesBuffer->size();
560
561 const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
562 getIndexForEntry(Value: Entry);
563 // For forgeign type (FTU) units that need to refer to the FTU and to the CU.
564 const std::optional<DWARF5AccelTable::UnitIndexAndEncoding> SecondEntryRet =
565 getSecondIndexForEntry(Value: Entry);
566 const unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
567 assert(AbbrevIndex < AbbreviationsVector.size() &&
568 "Entry abbrev index is outside of abbreviations vector range.");
569 const DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
570 encodeULEB128(Value: Entry.getAbbrevNumber(), OS&: *Entriestream);
571 auto writeIndex = [&](uint32_t Index, uint32_t IndexSize) -> void {
572 switch (IndexSize) {
573 default:
574 llvm_unreachable("Unsupported Index Size!");
575 break;
576 case 1:
577 support::endian::write(os&: *Entriestream, value: static_cast<uint8_t>(Index),
578 endian: llvm::endianness::little);
579 break;
580 case 2:
581 support::endian::write(os&: *Entriestream, value: static_cast<uint16_t>(Index),
582 endian: llvm::endianness::little);
583 break;
584 case 4:
585 support::endian::write(os&: *Entriestream, value: static_cast<uint32_t>(Index),
586 endian: llvm::endianness::little);
587 break;
588 };
589 };
590
591 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
592 Abbrev->getAttributes()) {
593 switch (AttrEnc.Index) {
594 default: {
595 llvm_unreachable("Unexpected index attribute!");
596 break;
597 }
598 case dwarf::DW_IDX_compile_unit: {
599 const unsigned CUIndex =
600 SecondEntryRet ? SecondEntryRet->Index : EntryRet->Index;
601 writeIndex(CUIndex, CUIndexEncodingSize);
602 break;
603 }
604 case dwarf::DW_IDX_type_unit: {
605 writeIndex(EntryRet->Index, TUIndexEncodingSize);
606 break;
607 }
608 case dwarf::DW_IDX_die_offset: {
609 assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
610 support::endian::write(os&: *Entriestream,
611 value: static_cast<uint32_t>(Entry.getDieOffset()),
612 endian: llvm::endianness::little);
613 break;
614 }
615 case dwarf::DW_IDX_parent: {
616 assert(
617 (AttrEnc.Form == dwarf::DW_FORM_ref4 && Entry.getParentDieOffset()) ||
618 AttrEnc.Form == dwarf::DW_FORM_flag_present);
619 if (std::optional<uint64_t> ParentOffset = Entry.getParentDieOffset()) {
620 Entry.setPatchOffset(EntriesBuffer->size());
621 support::endian::write(os&: *Entriestream, value: static_cast<uint32_t>(UINT32_MAX),
622 endian: llvm::endianness::little);
623 }
624 break;
625 }
626 }
627 }
628}
629
630void DWARF5AcceleratorTable::writeEntries() {
631 for (auto &Bucket : getBuckets()) {
632 for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
633 Hash->EntryOffset = EntriesBuffer->size();
634 for (BOLTDWARF5AccelTableData *Value : Hash->Values) {
635 writeEntry(Entry&: *Value);
636 }
637 support::endian::write(os&: *Entriestream, value: static_cast<uint8_t>(0),
638 endian: llvm::endianness::little);
639 }
640 }
641 // Patching parent offsets.
642 for (auto &Bucket : getBuckets()) {
643 for (DWARF5AcceleratorTable::HashData *Hash : Bucket) {
644 for (BOLTDWARF5AccelTableData *Entry : Hash->Values) {
645 std::optional<uint64_t> ParentOffset = Entry->getParentDieOffset();
646 if (!ParentOffset)
647 continue;
648 if (const auto Iter = EntryRelativeOffsets.find(Val: *ParentOffset);
649 Iter != EntryRelativeOffsets.end()) {
650 const uint64_t PatchOffset = Entry->getPatchOffset();
651 uint32_t *Ptr =
652 reinterpret_cast<uint32_t *>(&EntriesBuffer->data()[PatchOffset]);
653 *Ptr = Iter->second;
654 } else {
655 BC.errs() << "BOLT-WARNING: [internal-dwarf-warning]: Could not find "
656 "entry with offset "
657 << *ParentOffset << "\n";
658 }
659 }
660 }
661 }
662}
663
664void DWARF5AcceleratorTable::writeAugmentationString() {
665 // String needs to be multiple of 4 bytes.
666 *AugStringtream << "BOLT";
667 AugmentationStringSize = AugStringBuffer->size();
668}
669
670/// Calculates size of .debug_names header without Length field.
671static constexpr uint32_t getDebugNamesHeaderSize() {
672 constexpr uint16_t VersionLength = sizeof(uint16_t);
673 constexpr uint16_t PaddingLength = sizeof(uint16_t);
674 constexpr uint32_t CompUnitCountLength = sizeof(uint32_t);
675 constexpr uint32_t LocalTypeUnitCountLength = sizeof(uint32_t);
676 constexpr uint32_t ForeignTypeUnitCountLength = sizeof(uint32_t);
677 constexpr uint32_t BucketCountLength = sizeof(uint32_t);
678 constexpr uint32_t NameCountLength = sizeof(uint32_t);
679 constexpr uint32_t AbbrevTableSizeLength = sizeof(uint32_t);
680 constexpr uint32_t AugmentationStringSizeLenght = sizeof(uint32_t);
681 return VersionLength + PaddingLength + CompUnitCountLength +
682 LocalTypeUnitCountLength + ForeignTypeUnitCountLength +
683 BucketCountLength + NameCountLength + AbbrevTableSizeLength +
684 AugmentationStringSizeLenght;
685}
686
687void DWARF5AcceleratorTable::emitHeader() const {
688 constexpr uint32_t HeaderSize = getDebugNamesHeaderSize();
689 // Header Length
690 support::endian::write(os&: *FullTableStream,
691 value: static_cast<uint32_t>(HeaderSize + StrBuffer->size() +
692 AugmentationStringSize),
693 endian: llvm::endianness::little);
694 // Version
695 support::endian::write(os&: *FullTableStream, value: static_cast<uint16_t>(5),
696 endian: llvm::endianness::little);
697 // Padding
698 support::endian::write(os&: *FullTableStream, value: static_cast<uint16_t>(0),
699 endian: llvm::endianness::little);
700 // Compilation Unit Count
701 support::endian::write(os&: *FullTableStream, value: static_cast<uint32_t>(CUList.size()),
702 endian: llvm::endianness::little);
703 // Local Type Unit Count
704 support::endian::write(os&: *FullTableStream,
705 value: static_cast<uint32_t>(LocalTUList.size()),
706 endian: llvm::endianness::little);
707 // Foreign Type Unit Count
708 support::endian::write(os&: *FullTableStream,
709 value: static_cast<uint32_t>(ForeignTUList.size()),
710 endian: llvm::endianness::little);
711 // Bucket Count
712 support::endian::write(os&: *FullTableStream, value: static_cast<uint32_t>(BucketCount),
713 endian: llvm::endianness::little);
714 // Name Count
715 support::endian::write(os&: *FullTableStream,
716 value: static_cast<uint32_t>(Entries.size()),
717 endian: llvm::endianness::little);
718 // Abbrev Table Size
719 support::endian::write(os&: *FullTableStream,
720 value: static_cast<uint32_t>(AbbrevTableSize),
721 endian: llvm::endianness::little);
722 // Augmentation String Size
723 support::endian::write(os&: *FullTableStream,
724 value: static_cast<uint32_t>(AugmentationStringSize),
725 endian: llvm::endianness::little);
726
727 emitAugmentationString();
728 FullTableStream->write(Ptr: StrBuffer->data(), Size: StrBuffer->size());
729}
730
731void DWARF5AcceleratorTable::emitCUList() const {
732 for (const uint32_t CUID : CUList)
733 support::endian::write(os&: *StrStream, value: CUID, endian: llvm::endianness::little);
734}
735void DWARF5AcceleratorTable::emitTUList() const {
736 for (const uint32_t TUID : LocalTUList)
737 support::endian::write(os&: *StrStream, value: TUID, endian: llvm::endianness::little);
738
739 for (const uint64_t TUID : ForeignTUList)
740 support::endian::write(os&: *StrStream, value: TUID, endian: llvm::endianness::little);
741}
742void DWARF5AcceleratorTable::emitBuckets() const {
743 uint32_t Index = 1;
744 for (const auto &Bucket : enumerate(First: getBuckets())) {
745 const uint32_t TempIndex = Bucket.value().empty() ? 0 : Index;
746 support::endian::write(os&: *StrStream, value: TempIndex, endian: llvm::endianness::little);
747 Index += Bucket.value().size();
748 }
749}
750void DWARF5AcceleratorTable::emitHashes() const {
751 for (const auto &Bucket : getBuckets()) {
752 for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
753 support::endian::write(os&: *StrStream, value: Hash->HashValue,
754 endian: llvm::endianness::little);
755 }
756}
757void DWARF5AcceleratorTable::emitStringOffsets() const {
758 for (const auto &Bucket : getBuckets()) {
759 for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
760 support::endian::write(os&: *StrStream, value: static_cast<uint32_t>(Hash->StrOffset),
761 endian: llvm::endianness::little);
762 }
763}
764void DWARF5AcceleratorTable::emitOffsets() const {
765 for (const auto &Bucket : getBuckets()) {
766 for (const DWARF5AcceleratorTable::HashData *Hash : Bucket)
767 support::endian::write(os&: *StrStream,
768 value: static_cast<uint32_t>(Hash->EntryOffset),
769 endian: llvm::endianness::little);
770 }
771}
772void DWARF5AcceleratorTable::emitAbbrevs() {
773 const uint32_t AbbrevTableStart = StrBuffer->size();
774 for (const auto *Abbrev : AbbreviationsVector) {
775 encodeULEB128(Value: Abbrev->getNumber(), OS&: *StrStream);
776 encodeULEB128(Value: Abbrev->getDieTag(), OS&: *StrStream);
777 for (const auto &AttrEnc : Abbrev->getAttributes()) {
778 encodeULEB128(Value: AttrEnc.Index, OS&: *StrStream);
779 encodeULEB128(Value: AttrEnc.Form, OS&: *StrStream);
780 }
781 encodeULEB128(Value: 0, OS&: *StrStream);
782 encodeULEB128(Value: 0, OS&: *StrStream);
783 }
784 encodeULEB128(Value: 0, OS&: *StrStream);
785 AbbrevTableSize = StrBuffer->size() - AbbrevTableStart;
786}
787void DWARF5AcceleratorTable::emitData() {
788 StrStream->write(Ptr: EntriesBuffer->data(), Size: EntriesBuffer->size());
789}
790void DWARF5AcceleratorTable::emitAugmentationString() const {
791 FullTableStream->write(Ptr: AugStringBuffer->data(), Size: AugStringBuffer->size());
792}
793void DWARF5AcceleratorTable::emitAccelTable() {
794 if (!NeedToCreate)
795 return;
796 finalize();
797 populateAbbrevsMap();
798 writeEntries();
799 writeAugmentationString();
800 emitCUList();
801 emitTUList();
802 emitBuckets();
803 emitHashes();
804 emitStringOffsets();
805 emitOffsets();
806 emitAbbrevs();
807 emitData();
808 emitHeader();
809}
810} // namespace bolt
811} // namespace llvm
812

source code of bolt/lib/Core/DebugNames.cpp