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