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