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