1//===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===//
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// This file contains support for writing accelerator tables.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/CodeGen/AccelTable.h"
14#include "DwarfCompileUnit.h"
15#include "DwarfUnit.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/Twine.h"
19#include "llvm/BinaryFormat/Dwarf.h"
20#include "llvm/CodeGen/AsmPrinter.h"
21#include "llvm/CodeGen/DIE.h"
22#include "llvm/MC/MCStreamer.h"
23#include "llvm/MC/MCSymbol.h"
24#include "llvm/Support/LEB128.h"
25#include "llvm/Support/raw_ostream.h"
26#include "llvm/Target/TargetLoweringObjectFile.h"
27#include <cstddef>
28#include <cstdint>
29#include <limits>
30#include <vector>
31
32using namespace llvm;
33
34void AccelTableBase::computeBucketCount() {
35 SmallVector<uint32_t, 0> Uniques;
36 Uniques.reserve(N: Entries.size());
37 for (const auto &E : Entries)
38 Uniques.push_back(Elt: E.second.HashValue);
39 llvm::sort(C&: Uniques);
40 UniqueHashCount = llvm::unique(R&: Uniques) - Uniques.begin();
41 BucketCount = dwarf::getDebugNamesBucketCount(UniqueHashCount);
42}
43
44void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
45 // Create the individual hash data outputs.
46 for (auto &E : Entries) {
47 // Unique the entries.
48 llvm::stable_sort(Range&: E.second.Values,
49 C: [](const AccelTableData *A, const AccelTableData *B) {
50 return *A < *B;
51 });
52 E.second.Values.erase(first: llvm::unique(R&: E.second.Values), last: E.second.Values.end());
53 }
54
55 // Figure out how many buckets we need, then compute the bucket contents and
56 // the final ordering. The hashes and offsets can be emitted by walking these
57 // data structures. We add temporary symbols to the data so they can be
58 // referenced when emitting the offsets.
59 computeBucketCount();
60
61 // Compute bucket contents and final ordering.
62 Buckets.resize(new_size: BucketCount);
63 for (auto &E : Entries) {
64 uint32_t Bucket = E.second.HashValue % BucketCount;
65 Buckets[Bucket].push_back(x: &E.second);
66 E.second.Sym = Asm->createTempSymbol(Name: Prefix);
67 }
68
69 // Sort the contents of the buckets by hash value so that hash collisions end
70 // up together. Stable sort makes testing easier and doesn't cost much more.
71 for (auto &Bucket : Buckets)
72 llvm::stable_sort(Range&: Bucket, C: [](HashData *LHS, HashData *RHS) {
73 return LHS->HashValue < RHS->HashValue;
74 });
75}
76
77namespace {
78/// Base class for writing out Accelerator tables. It holds the common
79/// functionality for the two Accelerator table types.
80class AccelTableWriter {
81protected:
82 AsmPrinter *const Asm; ///< Destination.
83 const AccelTableBase &Contents; ///< Data to emit.
84
85 /// Controls whether to emit duplicate hash and offset table entries for names
86 /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
87 /// tables do.
88 const bool SkipIdenticalHashes;
89
90 void emitHashes() const;
91
92 /// Emit offsets to lists of entries with identical names. The offsets are
93 /// relative to the Base argument.
94 void emitOffsets(const MCSymbol *Base) const;
95
96public:
97 AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
98 bool SkipIdenticalHashes)
99 : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
100 }
101};
102
103class AppleAccelTableWriter : public AccelTableWriter {
104 using Atom = AppleAccelTableData::Atom;
105
106 /// The fixed header of an Apple Accelerator Table.
107 struct Header {
108 uint32_t Magic = MagicHash;
109 uint16_t Version = 1;
110 uint16_t HashFunction = dwarf::DW_hash_function_djb;
111 uint32_t BucketCount;
112 uint32_t HashCount;
113 uint32_t HeaderDataLength;
114
115 /// 'HASH' magic value to detect endianness.
116 static const uint32_t MagicHash = 0x48415348;
117
118 Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
119 : BucketCount(BucketCount), HashCount(UniqueHashCount),
120 HeaderDataLength(DataLength) {}
121
122 void emit(AsmPrinter *Asm) const;
123#ifndef NDEBUG
124 void print(raw_ostream &OS) const;
125 void dump() const { print(dbgs()); }
126#endif
127 };
128
129 /// The HeaderData describes the structure of an Apple accelerator table
130 /// through a list of Atoms.
131 struct HeaderData {
132 /// In the case of data that is referenced via DW_FORM_ref_* the offset
133 /// base is used to describe the offset for all forms in the list of atoms.
134 uint32_t DieOffsetBase;
135
136 const SmallVector<Atom, 4> Atoms;
137
138 HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
139 : DieOffsetBase(Offset), Atoms(AtomList) {}
140
141 void emit(AsmPrinter *Asm) const;
142#ifndef NDEBUG
143 void print(raw_ostream &OS) const;
144 void dump() const { print(dbgs()); }
145#endif
146 };
147
148 Header Header;
149 HeaderData HeaderData;
150 const MCSymbol *SecBegin;
151
152 void emitBuckets() const;
153 void emitData() const;
154
155public:
156 AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
157 ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
158 : AccelTableWriter(Asm, Contents, true),
159 Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
160 8 + (Atoms.size() * 4)),
161 HeaderData(Atoms), SecBegin(SecBegin) {}
162
163 void emit() const;
164
165#ifndef NDEBUG
166 void print(raw_ostream &OS) const;
167 void dump() const { print(dbgs()); }
168#endif
169};
170
171/// Class responsible for emitting a DWARF v5 Accelerator Table. The only
172/// public function is emit(), which performs the actual emission.
173///
174/// A callback abstracts the logic to provide a CU index for a given entry.
175class Dwarf5AccelTableWriter : public AccelTableWriter {
176 struct Header {
177 uint16_t Version = 5;
178 uint16_t Padding = 0;
179 uint32_t CompUnitCount;
180 uint32_t LocalTypeUnitCount = 0;
181 uint32_t ForeignTypeUnitCount = 0;
182 uint32_t BucketCount = 0;
183 uint32_t NameCount = 0;
184 uint32_t AbbrevTableSize = 0;
185 uint32_t AugmentationStringSize = sizeof(AugmentationString);
186 char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
187
188 Header(uint32_t CompUnitCount, uint32_t LocalTypeUnitCount,
189 uint32_t ForeignTypeUnitCount, uint32_t BucketCount,
190 uint32_t NameCount)
191 : CompUnitCount(CompUnitCount), LocalTypeUnitCount(LocalTypeUnitCount),
192 ForeignTypeUnitCount(ForeignTypeUnitCount), BucketCount(BucketCount),
193 NameCount(NameCount) {}
194
195 void emit(Dwarf5AccelTableWriter &Ctx);
196 };
197
198 Header Header;
199 /// FoldingSet that uniques the abbreviations.
200 FoldingSet<DebugNamesAbbrev> AbbreviationsSet;
201 /// Vector containing DebugNames abbreviations for iteration in order.
202 SmallVector<DebugNamesAbbrev *, 5> AbbreviationsVector;
203 /// The bump allocator to use when creating DIEAbbrev objects in the uniqued
204 /// storage container.
205 BumpPtrAllocator Alloc;
206 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits;
207 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits;
208 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
209 const DWARF5AccelTableData &)>
210 getIndexForEntry;
211 MCSymbol *ContributionEnd = nullptr;
212 MCSymbol *AbbrevStart = Asm->createTempSymbol(Name: "names_abbrev_start");
213 MCSymbol *AbbrevEnd = Asm->createTempSymbol(Name: "names_abbrev_end");
214 MCSymbol *EntryPool = Asm->createTempSymbol(Name: "names_entries");
215 // Indicates if this module is built with Split Dwarf enabled.
216 bool IsSplitDwarf = false;
217 /// Stores the DIE offsets which are indexed by this table.
218 DenseSet<OffsetAndUnitID> IndexedOffsets;
219
220 void populateAbbrevsMap();
221
222 void emitCUList() const;
223 void emitTUList() const;
224 void emitBuckets() const;
225 void emitStringOffsets() const;
226 void emitAbbrevs() const;
227 void emitEntry(
228 const DWARF5AccelTableData &Entry,
229 const DenseMap<OffsetAndUnitID, uint64_t> &DIEOffsetToAccelEntryOffset);
230 uint64_t getEntrySize(const DWARF5AccelTableData &Entry) const;
231 void emitData();
232
233public:
234 Dwarf5AccelTableWriter(
235 AsmPrinter *Asm, const AccelTableBase &Contents,
236 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,
237 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,
238 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
239 const DWARF5AccelTableData &)>
240 getIndexForEntry,
241 bool IsSplitDwarf);
242 ~Dwarf5AccelTableWriter() {
243 for (DebugNamesAbbrev *Abbrev : AbbreviationsVector)
244 Abbrev->~DebugNamesAbbrev();
245 }
246 void emit();
247};
248} // namespace
249
250void AccelTableWriter::emitHashes() const {
251 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
252 unsigned BucketIdx = 0;
253 for (const auto &Bucket : Contents.getBuckets()) {
254 for (const auto &Hash : Bucket) {
255 uint32_t HashValue = Hash->HashValue;
256 if (SkipIdenticalHashes && PrevHash == HashValue)
257 continue;
258 Asm->OutStreamer->AddComment(T: "Hash in Bucket " + Twine(BucketIdx));
259 Asm->emitInt32(Value: HashValue);
260 PrevHash = HashValue;
261 }
262 BucketIdx++;
263 }
264}
265
266void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
267 const auto &Buckets = Contents.getBuckets();
268 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
269 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
270 for (auto *Hash : Buckets[i]) {
271 uint32_t HashValue = Hash->HashValue;
272 if (SkipIdenticalHashes && PrevHash == HashValue)
273 continue;
274 PrevHash = HashValue;
275 Asm->OutStreamer->AddComment(T: "Offset in Bucket " + Twine(i));
276 Asm->emitLabelDifference(Hi: Hash->Sym, Lo: Base, Size: Asm->getDwarfOffsetByteSize());
277 }
278 }
279}
280
281void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
282 Asm->OutStreamer->AddComment(T: "Header Magic");
283 Asm->emitInt32(Value: Magic);
284 Asm->OutStreamer->AddComment(T: "Header Version");
285 Asm->emitInt16(Value: Version);
286 Asm->OutStreamer->AddComment(T: "Header Hash Function");
287 Asm->emitInt16(Value: HashFunction);
288 Asm->OutStreamer->AddComment(T: "Header Bucket Count");
289 Asm->emitInt32(Value: BucketCount);
290 Asm->OutStreamer->AddComment(T: "Header Hash Count");
291 Asm->emitInt32(Value: HashCount);
292 Asm->OutStreamer->AddComment(T: "Header Data Length");
293 Asm->emitInt32(Value: HeaderDataLength);
294}
295
296void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
297 Asm->OutStreamer->AddComment(T: "HeaderData Die Offset Base");
298 Asm->emitInt32(Value: DieOffsetBase);
299 Asm->OutStreamer->AddComment(T: "HeaderData Atom Count");
300 Asm->emitInt32(Value: Atoms.size());
301
302 for (const Atom &A : Atoms) {
303 Asm->OutStreamer->AddComment(T: dwarf::AtomTypeString(Atom: A.Type));
304 Asm->emitInt16(Value: A.Type);
305 Asm->OutStreamer->AddComment(T: dwarf::FormEncodingString(Encoding: A.Form));
306 Asm->emitInt16(Value: A.Form);
307 }
308}
309
310void AppleAccelTableWriter::emitBuckets() const {
311 const auto &Buckets = Contents.getBuckets();
312 unsigned index = 0;
313 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
314 Asm->OutStreamer->AddComment(T: "Bucket " + Twine(i));
315 if (!Buckets[i].empty())
316 Asm->emitInt32(Value: index);
317 else
318 Asm->emitInt32(Value: std::numeric_limits<uint32_t>::max());
319 // Buckets point in the list of hashes, not to the data. Do not increment
320 // the index multiple times in case of hash collisions.
321 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
322 for (auto *HD : Buckets[i]) {
323 uint32_t HashValue = HD->HashValue;
324 if (PrevHash != HashValue)
325 ++index;
326 PrevHash = HashValue;
327 }
328 }
329}
330
331void AppleAccelTableWriter::emitData() const {
332 const auto &Buckets = Contents.getBuckets();
333 for (const AccelTableBase::HashList &Bucket : Buckets) {
334 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
335 for (const auto &Hash : Bucket) {
336 // Terminate the previous entry if there is no hash collision with the
337 // current one.
338 if (PrevHash != std::numeric_limits<uint64_t>::max() &&
339 PrevHash != Hash->HashValue)
340 Asm->emitInt32(Value: 0);
341 // Remember to emit the label for our offset.
342 Asm->OutStreamer->emitLabel(Symbol: Hash->Sym);
343 Asm->OutStreamer->AddComment(T: Hash->Name.getString());
344 Asm->emitDwarfStringOffset(S: Hash->Name);
345 Asm->OutStreamer->AddComment(T: "Num DIEs");
346 Asm->emitInt32(Value: Hash->Values.size());
347 for (const auto *V : Hash->getValues<const AppleAccelTableData *>())
348 V->emit(Asm);
349 PrevHash = Hash->HashValue;
350 }
351 // Emit the final end marker for the bucket.
352 if (!Bucket.empty())
353 Asm->emitInt32(Value: 0);
354 }
355}
356
357void AppleAccelTableWriter::emit() const {
358 Header.emit(Asm);
359 HeaderData.emit(Asm);
360 emitBuckets();
361 emitHashes();
362 emitOffsets(Base: SecBegin);
363 emitData();
364}
365
366DWARF5AccelTableData::DWARF5AccelTableData(const DIE &Die,
367 const uint32_t UnitID,
368 const bool IsTU)
369 : OffsetVal(&Die), DieTag(Die.getTag()), AbbrevNumber(0), IsTU(IsTU),
370 UnitID(UnitID) {}
371
372void Dwarf5AccelTableWriter::Header::emit(Dwarf5AccelTableWriter &Ctx) {
373 assert(CompUnitCount > 0 && "Index must have at least one CU.");
374
375 AsmPrinter *Asm = Ctx.Asm;
376 Ctx.ContributionEnd =
377 Asm->emitDwarfUnitLength(Prefix: "names", Comment: "Header: unit length");
378 Asm->OutStreamer->AddComment(T: "Header: version");
379 Asm->emitInt16(Value: Version);
380 Asm->OutStreamer->AddComment(T: "Header: padding");
381 Asm->emitInt16(Value: Padding);
382 Asm->OutStreamer->AddComment(T: "Header: compilation unit count");
383 Asm->emitInt32(Value: CompUnitCount);
384 Asm->OutStreamer->AddComment(T: "Header: local type unit count");
385 Asm->emitInt32(Value: LocalTypeUnitCount);
386 Asm->OutStreamer->AddComment(T: "Header: foreign type unit count");
387 Asm->emitInt32(Value: ForeignTypeUnitCount);
388 Asm->OutStreamer->AddComment(T: "Header: bucket count");
389 Asm->emitInt32(Value: BucketCount);
390 Asm->OutStreamer->AddComment(T: "Header: name count");
391 Asm->emitInt32(Value: NameCount);
392 Asm->OutStreamer->AddComment(T: "Header: abbreviation table size");
393 Asm->emitLabelDifference(Hi: Ctx.AbbrevEnd, Lo: Ctx.AbbrevStart, Size: sizeof(uint32_t));
394 Asm->OutStreamer->AddComment(T: "Header: augmentation string size");
395 assert(AugmentationStringSize % 4 == 0);
396 Asm->emitInt32(Value: AugmentationStringSize);
397 Asm->OutStreamer->AddComment(T: "Header: augmentation string");
398 Asm->OutStreamer->emitBytes(Data: {AugmentationString, AugmentationStringSize});
399}
400
401std::optional<uint64_t>
402DWARF5AccelTableData::getDefiningParentDieOffset(const DIE &Die) {
403 if (auto *Parent = Die.getParent();
404 Parent && !Parent->findAttribute(Attribute: dwarf::Attribute::DW_AT_declaration))
405 return Parent->getOffset();
406 return {};
407}
408
409static std::optional<dwarf::Form>
410getFormForIdxParent(const DenseSet<OffsetAndUnitID> &IndexedOffsets,
411 std::optional<OffsetAndUnitID> ParentOffset) {
412 // No parent information
413 if (!ParentOffset)
414 return std::nullopt;
415 // Parent is indexed by this table.
416 if (IndexedOffsets.contains(V: *ParentOffset))
417 return dwarf::Form::DW_FORM_ref4;
418 // Parent is not indexed by this table.
419 return dwarf::Form::DW_FORM_flag_present;
420}
421
422void DebugNamesAbbrev::Profile(FoldingSetNodeID &ID) const {
423 ID.AddInteger(I: DieTag);
424 for (const DebugNamesAbbrev::AttributeEncoding &Enc : AttrVect) {
425 ID.AddInteger(I: Enc.Index);
426 ID.AddInteger(I: Enc.Form);
427 }
428}
429
430void Dwarf5AccelTableWriter::populateAbbrevsMap() {
431 for (auto &Bucket : Contents.getBuckets()) {
432 for (auto *Hash : Bucket) {
433 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>()) {
434 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
435 getIndexForEntry(*Value);
436 std::optional<dwarf::Form> MaybeParentForm = getFormForIdxParent(
437 IndexedOffsets, ParentOffset: Value->getParentDieOffsetAndUnitID());
438 DebugNamesAbbrev Abbrev(Value->getDieTag());
439 if (EntryRet)
440 Abbrev.addAttribute(Attr: EntryRet->Encoding);
441 Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_die_offset, .Form: dwarf::DW_FORM_ref4});
442 if (MaybeParentForm)
443 Abbrev.addAttribute(Attr: {.Index: dwarf::DW_IDX_parent, .Form: *MaybeParentForm});
444 FoldingSetNodeID ID;
445 Abbrev.Profile(ID);
446 FoldingSetInsertToken Token;
447 if (DebugNamesAbbrev *Existing = AbbreviationsSet.lookup(ID, Token)) {
448 Value->setAbbrevNumber(Existing->getNumber());
449 continue;
450 }
451 DebugNamesAbbrev *NewAbbrev =
452 new (Alloc) DebugNamesAbbrev(std::move(Abbrev));
453 AbbreviationsVector.push_back(Elt: NewAbbrev);
454 NewAbbrev->setNumber(AbbreviationsVector.size());
455 AbbreviationsSet.insert(N: NewAbbrev, Token);
456 Value->setAbbrevNumber(NewAbbrev->getNumber());
457 }
458 }
459 }
460}
461
462void Dwarf5AccelTableWriter::emitCUList() const {
463 for (const auto &CU : enumerate(First: CompUnits)) {
464 Asm->OutStreamer->AddComment(T: "Compilation unit " + Twine(CU.index()));
465 if (std::holds_alternative<MCSymbol *>(v: CU.value()))
466 Asm->emitDwarfSymbolReference(Label: std::get<MCSymbol *>(v: CU.value()));
467 else
468 Asm->emitDwarfLengthOrOffset(Value: std::get<uint64_t>(v: CU.value()));
469 }
470}
471
472void Dwarf5AccelTableWriter::emitTUList() const {
473 for (const auto &TU : enumerate(First: TypeUnits)) {
474 Asm->OutStreamer->AddComment(T: "Type unit " + Twine(TU.index()));
475 if (std::holds_alternative<MCSymbol *>(v: TU.value()))
476 Asm->emitDwarfSymbolReference(Label: std::get<MCSymbol *>(v: TU.value()));
477 else if (IsSplitDwarf)
478 Asm->emitInt64(Value: std::get<uint64_t>(v: TU.value()));
479 else
480 Asm->emitDwarfLengthOrOffset(Value: std::get<uint64_t>(v: TU.value()));
481 }
482}
483
484void Dwarf5AccelTableWriter::emitBuckets() const {
485 uint32_t Index = 1;
486 for (const auto &Bucket : enumerate(First: Contents.getBuckets())) {
487 Asm->OutStreamer->AddComment(T: "Bucket " + Twine(Bucket.index()));
488 Asm->emitInt32(Value: Bucket.value().empty() ? 0 : Index);
489 Index += Bucket.value().size();
490 }
491}
492
493void Dwarf5AccelTableWriter::emitStringOffsets() const {
494 for (const auto &Bucket : enumerate(First: Contents.getBuckets())) {
495 for (auto *Hash : Bucket.value()) {
496 DwarfStringPoolEntryRef String = Hash->Name;
497 Asm->OutStreamer->AddComment(T: "String in Bucket " + Twine(Bucket.index()) +
498 ": " + String.getString());
499 Asm->emitDwarfStringOffset(S: String);
500 }
501 }
502}
503
504void Dwarf5AccelTableWriter::emitAbbrevs() const {
505 Asm->OutStreamer->emitLabel(Symbol: AbbrevStart);
506 for (const DebugNamesAbbrev *Abbrev : AbbreviationsVector) {
507 Asm->OutStreamer->AddComment(T: "Abbrev code");
508 Asm->emitULEB128(Value: Abbrev->getNumber());
509 Asm->OutStreamer->AddComment(T: dwarf::TagString(Tag: Abbrev->getDieTag()));
510 Asm->emitULEB128(Value: Abbrev->getDieTag());
511 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
512 Abbrev->getAttributes()) {
513 Asm->emitULEB128(Value: AttrEnc.Index, Desc: dwarf::IndexString(Idx: AttrEnc.Index).data());
514 Asm->emitULEB128(Value: AttrEnc.Form,
515 Desc: dwarf::FormEncodingString(Encoding: AttrEnc.Form).data());
516 }
517 Asm->emitULEB128(Value: 0, Desc: "End of abbrev");
518 Asm->emitULEB128(Value: 0, Desc: "End of abbrev");
519 }
520 Asm->emitULEB128(Value: 0, Desc: "End of abbrev list");
521 Asm->OutStreamer->emitLabel(Symbol: AbbrevEnd);
522}
523
524void Dwarf5AccelTableWriter::emitEntry(
525 const DWARF5AccelTableData &Entry,
526 const DenseMap<OffsetAndUnitID, uint64_t> &DIEOffsetToAccelEntryOffset) {
527 unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
528 assert(AbbrevIndex < AbbreviationsVector.size() &&
529 "Entry abbrev index is outside of abbreviations vector range.");
530 DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
531 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
532 getIndexForEntry(Entry);
533 std::optional<OffsetAndUnitID> MaybeParentOffset =
534 Entry.getParentDieOffsetAndUnitID();
535
536 Asm->emitULEB128(Value: Entry.getAbbrevNumber(), Desc: "Abbreviation code");
537
538 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
539 Abbrev->getAttributes()) {
540 Asm->OutStreamer->AddComment(T: dwarf::IndexString(Idx: AttrEnc.Index));
541 switch (AttrEnc.Index) {
542 case dwarf::DW_IDX_compile_unit:
543 case dwarf::DW_IDX_type_unit: {
544 DIEInteger ID(EntryRet->Index);
545 ID.emitValue(Asm, Form: AttrEnc.Form);
546 break;
547 }
548 case dwarf::DW_IDX_die_offset:
549 assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
550 Asm->emitInt32(Value: Entry.getDieOffset());
551 break;
552 case dwarf::DW_IDX_parent: {
553 if (AttrEnc.Form == dwarf::Form::DW_FORM_flag_present)
554 break;
555 auto It = DIEOffsetToAccelEntryOffset.find(Val: *MaybeParentOffset);
556 assert(It != DIEOffsetToAccelEntryOffset.end());
557 Asm->emitInt32(Value: It->second);
558 break;
559 }
560 default:
561 llvm_unreachable("Unexpected index attribute!");
562 }
563 }
564}
565
566uint64_t
567Dwarf5AccelTableWriter::getEntrySize(const DWARF5AccelTableData &Entry) const {
568 unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
569 assert(AbbrevIndex < AbbreviationsVector.size());
570 DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
571 uint64_t Size = getULEB128Size(Value: Entry.getAbbrevNumber());
572 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
573 getIndexForEntry(Entry);
574 for (const auto &AttrEnc : Abbrev->getAttributes()) {
575 switch (AttrEnc.Index) {
576 case dwarf::DW_IDX_compile_unit:
577 case dwarf::DW_IDX_type_unit:
578 Size += DIEInteger(EntryRet->Index)
579 .sizeOf(FormParams: Asm->getDwarfFormParams(), Form: AttrEnc.Form);
580 break;
581 case dwarf::DW_IDX_die_offset:
582 Size += 4;
583 break;
584 case dwarf::DW_IDX_parent:
585 if (AttrEnc.Form != dwarf::Form::DW_FORM_flag_present)
586 Size += 4;
587 break;
588 default:
589 llvm_unreachable("Unexpected index attribute!");
590 }
591 }
592 return Size;
593}
594
595void Dwarf5AccelTableWriter::emitData() {
596 // Pre-compute entry pool offsets for DW_IDX_parent references.
597 DenseMap<OffsetAndUnitID, uint64_t> DIEOffsetToAccelEntryOffset;
598 uint64_t Offset = 0;
599 for (auto &Bucket : Contents.getBuckets()) {
600 for (auto *Hash : Bucket) {
601 for (const auto *Value : Hash->getValues<DWARF5AccelTableData *>()) {
602 DIEOffsetToAccelEntryOffset.try_emplace(Key: Value->getDieOffsetAndUnitID(),
603 Args&: Offset);
604 Offset += getEntrySize(Entry: *Value);
605 }
606 Offset += 1; // End of list
607 }
608 }
609
610 Asm->OutStreamer->emitLabel(Symbol: EntryPool);
611 for (auto &Bucket : Contents.getBuckets()) {
612 for (auto *Hash : Bucket) {
613 // Remember to emit the label for our offset.
614 Asm->OutStreamer->emitLabel(Symbol: Hash->Sym);
615 for (const auto *Value : Hash->getValues<DWARF5AccelTableData *>())
616 emitEntry(Entry: *Value, DIEOffsetToAccelEntryOffset);
617 Asm->OutStreamer->AddComment(T: "End of list: " + Hash->Name.getString());
618 Asm->emitInt8(Value: 0);
619 }
620 }
621}
622
623Dwarf5AccelTableWriter::Dwarf5AccelTableWriter(
624 AsmPrinter *Asm, const AccelTableBase &Contents,
625 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,
626 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,
627 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
628 const DWARF5AccelTableData &)>
629 getIndexForEntry,
630 bool IsSplitDwarf)
631 : AccelTableWriter(Asm, Contents, false),
632 Header(CompUnits.size(), IsSplitDwarf ? 0 : TypeUnits.size(),
633 IsSplitDwarf ? TypeUnits.size() : 0, Contents.getBucketCount(),
634 Contents.getUniqueNameCount()),
635 CompUnits(CompUnits), TypeUnits(TypeUnits),
636 getIndexForEntry(std::move(getIndexForEntry)),
637 IsSplitDwarf(IsSplitDwarf) {
638
639 for (auto &Bucket : Contents.getBuckets())
640 for (auto *Hash : Bucket)
641 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>())
642 IndexedOffsets.insert(V: Value->getDieOffsetAndUnitID());
643
644 populateAbbrevsMap();
645}
646
647void Dwarf5AccelTableWriter::emit() {
648 Header.emit(Ctx&: *this);
649 emitCUList();
650 emitTUList();
651 emitBuckets();
652 emitHashes();
653 emitStringOffsets();
654 emitOffsets(Base: EntryPool);
655 emitAbbrevs();
656 emitData();
657 Asm->OutStreamer->emitValueToAlignment(Alignment: Align(4), Fill: 0);
658 Asm->OutStreamer->emitLabel(Symbol: ContributionEnd);
659}
660
661void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
662 StringRef Prefix, const MCSymbol *SecBegin,
663 ArrayRef<AppleAccelTableData::Atom> Atoms) {
664 Contents.finalize(Asm, Prefix);
665 AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
666}
667
668void llvm::emitDWARF5AccelTable(
669 AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD,
670 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
671 TUVectorTy TUSymbols = Contents.getTypeUnitsSymbols();
672 std::vector<std::variant<MCSymbol *, uint64_t>> CompUnits;
673 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;
674 SmallVector<unsigned, 1> CUIndex(CUs.size());
675 DenseMap<unsigned, unsigned> TUIndex(TUSymbols.size());
676 int CUCount = 0;
677 int TUCount = 0;
678 for (const auto &CU : enumerate(First&: CUs)) {
679 switch (CU.value()->getCUNode()->getNameTableKind()) {
680 case DICompileUnit::DebugNameTableKind::Default:
681 case DICompileUnit::DebugNameTableKind::Apple:
682 break;
683 default:
684 continue;
685 }
686 CUIndex[CU.index()] = CUCount++;
687 assert(CU.index() == CU.value()->getUniqueID());
688 const DwarfCompileUnit *MainCU =
689 DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
690 CompUnits.push_back(x: MainCU->getLabelBegin());
691 }
692
693 for (const auto &TU : TUSymbols) {
694 TUIndex[TU.UniqueID] = TUCount++;
695 if (DD.useSplitDwarf())
696 TypeUnits.push_back(x: std::get<uint64_t>(v: TU.LabelOrSignature));
697 else
698 TypeUnits.push_back(x: std::get<MCSymbol *>(v: TU.LabelOrSignature));
699 }
700
701 if (CompUnits.empty())
702 return;
703
704 Asm->OutStreamer->switchSection(
705 Section: Asm->getObjFileLowering().getDwarfDebugNamesSection());
706
707 Contents.finalize(Asm, Prefix: "names");
708 dwarf::Form CUIndexForm =
709 DIEInteger::BestForm(/*IsSigned*/ false, Int: CompUnits.size() - 1);
710 dwarf::Form TUIndexForm =
711 DIEInteger::BestForm(/*IsSigned*/ false, Int: TypeUnits.size() - 1);
712 Dwarf5AccelTableWriter(
713 Asm, Contents, CompUnits, TypeUnits,
714 [&](const DWARF5AccelTableData &Entry)
715 -> std::optional<DWARF5AccelTable::UnitIndexAndEncoding> {
716 if (Entry.isTU())
717 return {{.Index: TUIndex[Entry.getUnitID()],
718 .Encoding: {.Index: dwarf::DW_IDX_type_unit, .Form: TUIndexForm}}};
719 if (CUIndex.size() > 1)
720 return {{.Index: CUIndex[Entry.getUnitID()],
721 .Encoding: {.Index: dwarf::DW_IDX_compile_unit, .Form: CUIndexForm}}};
722 return std::nullopt;
723 },
724 DD.useSplitDwarf())
725 .emit();
726}
727
728void DWARF5AccelTable::addTypeUnitSymbol(DwarfTypeUnit &U) {
729 TUSymbolsOrHashes.push_back(Elt: {.LabelOrSignature: U.getLabelBegin(), .UniqueID: U.getUniqueID()});
730}
731
732void DWARF5AccelTable::addTypeUnitSignature(DwarfTypeUnit &U) {
733 TUSymbolsOrHashes.push_back(Elt: {.LabelOrSignature: U.getTypeSignature(), .UniqueID: U.getUniqueID()});
734}
735
736void llvm::emitDWARF5AccelTable(
737 AsmPrinter *Asm, DWARF5AccelTable &Contents,
738 ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs,
739 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
740 const DWARF5AccelTableData &)>
741 getIndexForEntry) {
742 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;
743 Contents.finalize(Asm, Prefix: "names");
744 Dwarf5AccelTableWriter(Asm, Contents, CUs, TypeUnits, getIndexForEntry, false)
745 .emit();
746}
747
748void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
749 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
750 "The section offset exceeds the limit.");
751 Asm->emitInt32(Value: Die.getDebugSectionOffset());
752}
753
754void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
755 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
756 "The section offset exceeds the limit.");
757 Asm->emitInt32(Value: Die.getDebugSectionOffset());
758 Asm->emitInt16(Value: Die.getTag());
759 Asm->emitInt8(Value: 0);
760}
761
762void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
763 Asm->emitInt32(Value: Offset);
764}
765
766void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
767 Asm->emitInt32(Value: Offset);
768 Asm->emitInt16(Value: Tag);
769 Asm->emitInt8(Value: ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
770 : 0);
771 Asm->emitInt32(Value: QualifiedNameHash);
772}
773
774#ifndef NDEBUG
775void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
776 OS << "Magic: " << format("0x%x", Magic) << "\n"
777 << "Version: " << Version << "\n"
778 << "Hash Function: " << HashFunction << "\n"
779 << "Bucket Count: " << BucketCount << "\n"
780 << "Header Data Length: " << HeaderDataLength << "\n";
781}
782
783void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
784 OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
785 << "Form: " << dwarf::FormEncodingString(Form) << "\n";
786}
787
788void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
789 OS << "DIE Offset Base: " << DieOffsetBase << "\n";
790 for (auto Atom : Atoms)
791 Atom.print(OS);
792}
793
794void AppleAccelTableWriter::print(raw_ostream &OS) const {
795 Header.print(OS);
796 HeaderData.print(OS);
797 Contents.print(OS);
798 SecBegin->print(OS, nullptr);
799}
800
801void AccelTableBase::HashData::print(raw_ostream &OS) const {
802 OS << "Name: " << Name.getString() << "\n";
803 OS << " Hash Value: " << format("0x%x", HashValue) << "\n";
804 OS << " Symbol: ";
805 if (Sym)
806 OS << *Sym;
807 else
808 OS << "<none>";
809 OS << "\n";
810 for (auto *Value : Values)
811 Value->print(OS);
812}
813
814void AccelTableBase::print(raw_ostream &OS) const {
815 // Print Content.
816 OS << "Entries: \n";
817 for (const auto &[Name, Data] : Entries) {
818 OS << "Name: " << Name << "\n";
819 for (auto *V : Data.Values)
820 V->print(OS);
821 }
822
823 OS << "Buckets and Hashes: \n";
824 for (const auto &Bucket : Buckets)
825 for (const auto &Hash : Bucket)
826 Hash->print(OS);
827
828 OS << "Data: \n";
829 for (const auto &E : Entries)
830 E.second.print(OS);
831}
832
833void DWARF5AccelTableData::print(raw_ostream &OS) const {
834 OS << " Offset: " << getDieOffset() << "\n";
835 OS << " Tag: " << dwarf::TagString(getDieTag()) << "\n";
836}
837
838void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
839 OS << " Offset: " << Die.getOffset() << "\n";
840}
841
842void AppleAccelTableTypeData::print(raw_ostream &OS) const {
843 OS << " Offset: " << Die.getOffset() << "\n";
844 OS << " Tag: " << dwarf::TagString(Die.getTag()) << "\n";
845}
846
847void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
848 OS << " Static Offset: " << Offset << "\n";
849}
850
851void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
852 OS << " Static Offset: " << Offset << "\n";
853 OS << " QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
854 OS << " Tag: " << dwarf::TagString(Tag) << "\n";
855 OS << " ObjCClassIsImplementation: "
856 << (ObjCClassIsImplementation ? "true" : "false");
857 OS << "\n";
858}
859#endif
860