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

source code of llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp