LLVM 22.0.0git
AccelTable.cpp
Go to the documentation of this file.
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
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"
21#include "llvm/CodeGen/DIE.h"
22#include "llvm/MC/MCStreamer.h"
23#include "llvm/MC/MCSymbol.h"
26#include <cstddef>
27#include <cstdint>
28#include <limits>
29#include <vector>
30
31using namespace llvm;
32
35 Uniques.reserve(Entries.size());
36 for (const auto &E : Entries)
37 Uniques.push_back(E.second.HashValue);
38 llvm::sort(Uniques);
39 UniqueHashCount = llvm::unique(Uniques) - Uniques.begin();
41}
42
44 // Create the individual hash data outputs.
45 for (auto &E : Entries) {
46 // Unique the entries.
47 llvm::stable_sort(E.second.Values,
48 [](const AccelTableData *A, const AccelTableData *B) {
49 return *A < *B;
50 });
51 E.second.Values.erase(llvm::unique(E.second.Values), E.second.Values.end());
52 }
53
54 // Figure out how many buckets we need, then compute the bucket contents and
55 // the final ordering. The hashes and offsets can be emitted by walking these
56 // data structures. We add temporary symbols to the data so they can be
57 // referenced when emitting the offsets.
59
60 // Compute bucket contents and final ordering.
61 Buckets.resize(BucketCount);
62 for (auto &E : Entries) {
63 uint32_t Bucket = E.second.HashValue % BucketCount;
64 Buckets[Bucket].push_back(&E.second);
65 E.second.Sym = Asm->createTempSymbol(Prefix);
66 }
67
68 // Sort the contents of the buckets by hash value so that hash collisions end
69 // up together. Stable sort makes testing easier and doesn't cost much more.
70 for (auto &Bucket : Buckets)
71 llvm::stable_sort(Bucket, [](HashData *LHS, HashData *RHS) {
72 return LHS->HashValue < RHS->HashValue;
73 });
74}
75
76namespace {
77/// Base class for writing out Accelerator tables. It holds the common
78/// functionality for the two Accelerator table types.
79class AccelTableWriter {
80protected:
81 AsmPrinter *const Asm; ///< Destination.
82 const AccelTableBase &Contents; ///< Data to emit.
83
84 /// Controls whether to emit duplicate hash and offset table entries for names
85 /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
86 /// tables do.
87 const bool SkipIdenticalHashes;
88
89 void emitHashes() const;
90
91 /// Emit offsets to lists of entries with identical names. The offsets are
92 /// relative to the Base argument.
93 void emitOffsets(const MCSymbol *Base) const;
94
95public:
96 AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
97 bool SkipIdenticalHashes)
98 : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
99 }
100};
101
102class AppleAccelTableWriter : public AccelTableWriter {
103 using Atom = AppleAccelTableData::Atom;
104
105 /// The fixed header of an Apple Accelerator Table.
106 struct Header {
107 uint32_t Magic = MagicHash;
108 uint16_t Version = 1;
109 uint16_t HashFunction = dwarf::DW_hash_function_djb;
110 uint32_t BucketCount;
111 uint32_t HashCount;
112 uint32_t HeaderDataLength;
113
114 /// 'HASH' magic value to detect endianness.
115 static const uint32_t MagicHash = 0x48415348;
116
117 Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
118 : BucketCount(BucketCount), HashCount(UniqueHashCount),
119 HeaderDataLength(DataLength) {}
120
121 void emit(AsmPrinter *Asm) const;
122#ifndef NDEBUG
123 void print(raw_ostream &OS) const;
124 void dump() const { print(dbgs()); }
125#endif
126 };
127
128 /// The HeaderData describes the structure of an Apple accelerator table
129 /// through a list of Atoms.
130 struct HeaderData {
131 /// In the case of data that is referenced via DW_FORM_ref_* the offset
132 /// base is used to describe the offset for all forms in the list of atoms.
133 uint32_t DieOffsetBase;
134
135 const SmallVector<Atom, 4> Atoms;
136
137 HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
138 : DieOffsetBase(Offset), Atoms(AtomList) {}
139
140 void emit(AsmPrinter *Asm) const;
141#ifndef NDEBUG
142 void print(raw_ostream &OS) const;
143 void dump() const { print(dbgs()); }
144#endif
145 };
146
147 Header Header;
148 HeaderData HeaderData;
149 const MCSymbol *SecBegin;
150
151 void emitBuckets() const;
152 void emitData() const;
153
154public:
155 AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
156 ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
157 : AccelTableWriter(Asm, Contents, true),
158 Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
159 8 + (Atoms.size() * 4)),
160 HeaderData(Atoms), SecBegin(SecBegin) {}
161
162 void emit() const;
163
164#ifndef NDEBUG
165 void print(raw_ostream &OS) const;
166 void dump() const { print(dbgs()); }
167#endif
168};
169
170/// Class responsible for emitting a DWARF v5 Accelerator Table. The only
171/// public function is emit(), which performs the actual emission.
172///
173/// A callback abstracts the logic to provide a CU index for a given entry.
174class Dwarf5AccelTableWriter : public AccelTableWriter {
175 struct Header {
176 uint16_t Version = 5;
177 uint16_t Padding = 0;
178 uint32_t CompUnitCount;
179 uint32_t LocalTypeUnitCount = 0;
180 uint32_t ForeignTypeUnitCount = 0;
181 uint32_t BucketCount = 0;
182 uint32_t NameCount = 0;
183 uint32_t AbbrevTableSize = 0;
184 uint32_t AugmentationStringSize = sizeof(AugmentationString);
185 char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
186
187 Header(uint32_t CompUnitCount, uint32_t LocalTypeUnitCount,
188 uint32_t ForeignTypeUnitCount, uint32_t BucketCount,
189 uint32_t NameCount)
190 : CompUnitCount(CompUnitCount), LocalTypeUnitCount(LocalTypeUnitCount),
191 ForeignTypeUnitCount(ForeignTypeUnitCount), BucketCount(BucketCount),
192 NameCount(NameCount) {}
193
194 void emit(Dwarf5AccelTableWriter &Ctx);
195 };
196
197 Header Header;
198 /// FoldingSet that uniques the abbreviations.
199 FoldingSet<DebugNamesAbbrev> AbbreviationsSet;
200 /// Vector containing DebugNames abbreviations for iteration in order.
201 SmallVector<DebugNamesAbbrev *, 5> AbbreviationsVector;
202 /// The bump allocator to use when creating DIEAbbrev objects in the uniqued
203 /// storage container.
207 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
208 const DWARF5AccelTableData &)>
209 getIndexForEntry;
210 MCSymbol *ContributionEnd = nullptr;
211 MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
212 MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
213 MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
214 // Indicates if this module is built with Split Dwarf enabled.
215 bool IsSplitDwarf = false;
216 /// Stores the DIE offsets which are indexed by this table.
217 DenseSet<OffsetAndUnitID> IndexedOffsets;
218
219 void populateAbbrevsMap();
220
221 void emitCUList() const;
222 void emitTUList() const;
223 void emitBuckets() const;
224 void emitStringOffsets() const;
225 void emitAbbrevs() const;
226 void emitEntry(
227 const DWARF5AccelTableData &Entry,
228 const DenseMap<OffsetAndUnitID, MCSymbol *> &DIEOffsetToAccelEntryLabel,
229 DenseSet<MCSymbol *> &EmittedAccelEntrySymbols);
230 void emitData();
231
232public:
233 Dwarf5AccelTableWriter(
234 AsmPrinter *Asm, const AccelTableBase &Contents,
235 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,
236 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,
237 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
238 const DWARF5AccelTableData &)>
239 getIndexForEntry,
240 bool IsSplitDwarf);
241 ~Dwarf5AccelTableWriter() {
242 for (DebugNamesAbbrev *Abbrev : AbbreviationsVector)
243 Abbrev->~DebugNamesAbbrev();
244 }
245 void emit();
246};
247} // namespace
248
249void AccelTableWriter::emitHashes() const {
250 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
251 unsigned BucketIdx = 0;
252 for (const auto &Bucket : Contents.getBuckets()) {
253 for (const auto &Hash : Bucket) {
254 uint32_t HashValue = Hash->HashValue;
255 if (SkipIdenticalHashes && PrevHash == HashValue)
256 continue;
257 Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
258 Asm->emitInt32(HashValue);
259 PrevHash = HashValue;
260 }
261 BucketIdx++;
262 }
263}
264
265void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
266 const auto &Buckets = Contents.getBuckets();
267 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
268 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
269 for (auto *Hash : Buckets[i]) {
270 uint32_t HashValue = Hash->HashValue;
271 if (SkipIdenticalHashes && PrevHash == HashValue)
272 continue;
273 PrevHash = HashValue;
274 Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
275 Asm->emitLabelDifference(Hash->Sym, Base, Asm->getDwarfOffsetByteSize());
276 }
277 }
278}
279
280void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
281 Asm->OutStreamer->AddComment("Header Magic");
282 Asm->emitInt32(Magic);
283 Asm->OutStreamer->AddComment("Header Version");
284 Asm->emitInt16(Version);
285 Asm->OutStreamer->AddComment("Header Hash Function");
286 Asm->emitInt16(HashFunction);
287 Asm->OutStreamer->AddComment("Header Bucket Count");
288 Asm->emitInt32(BucketCount);
289 Asm->OutStreamer->AddComment("Header Hash Count");
290 Asm->emitInt32(HashCount);
291 Asm->OutStreamer->AddComment("Header Data Length");
292 Asm->emitInt32(HeaderDataLength);
293}
294
295void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
296 Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
297 Asm->emitInt32(DieOffsetBase);
298 Asm->OutStreamer->AddComment("HeaderData Atom Count");
299 Asm->emitInt32(Atoms.size());
300
301 for (const Atom &A : Atoms) {
302 Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
303 Asm->emitInt16(A.Type);
304 Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
305 Asm->emitInt16(A.Form);
306 }
307}
308
309void AppleAccelTableWriter::emitBuckets() const {
310 const auto &Buckets = Contents.getBuckets();
311 unsigned index = 0;
312 for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
313 Asm->OutStreamer->AddComment("Bucket " + Twine(i));
314 if (!Buckets[i].empty())
315 Asm->emitInt32(index);
316 else
317 Asm->emitInt32(std::numeric_limits<uint32_t>::max());
318 // Buckets point in the list of hashes, not to the data. Do not increment
319 // the index multiple times in case of hash collisions.
320 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
321 for (auto *HD : Buckets[i]) {
322 uint32_t HashValue = HD->HashValue;
323 if (PrevHash != HashValue)
324 ++index;
325 PrevHash = HashValue;
326 }
327 }
328}
329
330void AppleAccelTableWriter::emitData() const {
331 const auto &Buckets = Contents.getBuckets();
332 for (const AccelTableBase::HashList &Bucket : Buckets) {
333 uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
334 for (const auto &Hash : Bucket) {
335 // Terminate the previous entry if there is no hash collision with the
336 // current one.
337 if (PrevHash != std::numeric_limits<uint64_t>::max() &&
338 PrevHash != Hash->HashValue)
339 Asm->emitInt32(0);
340 // Remember to emit the label for our offset.
341 Asm->OutStreamer->emitLabel(Hash->Sym);
342 Asm->OutStreamer->AddComment(Hash->Name.getString());
343 Asm->emitDwarfStringOffset(Hash->Name);
344 Asm->OutStreamer->AddComment("Num DIEs");
345 Asm->emitInt32(Hash->Values.size());
346 for (const auto *V : Hash->getValues<const AppleAccelTableData *>())
347 V->emit(Asm);
348 PrevHash = Hash->HashValue;
349 }
350 // Emit the final end marker for the bucket.
351 if (!Bucket.empty())
352 Asm->emitInt32(0);
353 }
354}
355
356void AppleAccelTableWriter::emit() const {
357 Header.emit(Asm);
358 HeaderData.emit(Asm);
359 emitBuckets();
360 emitHashes();
361 emitOffsets(SecBegin);
362 emitData();
363}
364
366 const uint32_t UnitID,
367 const bool IsTU)
368 : OffsetVal(&Die), DieTag(Die.getTag()), AbbrevNumber(0), IsTU(IsTU),
369 UnitID(UnitID) {}
370
371void Dwarf5AccelTableWriter::Header::emit(Dwarf5AccelTableWriter &Ctx) {
372 assert(CompUnitCount > 0 && "Index must have at least one CU.");
373
374 AsmPrinter *Asm = Ctx.Asm;
375 Ctx.ContributionEnd =
376 Asm->emitDwarfUnitLength("names", "Header: unit length");
377 Asm->OutStreamer->AddComment("Header: version");
378 Asm->emitInt16(Version);
379 Asm->OutStreamer->AddComment("Header: padding");
380 Asm->emitInt16(Padding);
381 Asm->OutStreamer->AddComment("Header: compilation unit count");
382 Asm->emitInt32(CompUnitCount);
383 Asm->OutStreamer->AddComment("Header: local type unit count");
384 Asm->emitInt32(LocalTypeUnitCount);
385 Asm->OutStreamer->AddComment("Header: foreign type unit count");
386 Asm->emitInt32(ForeignTypeUnitCount);
387 Asm->OutStreamer->AddComment("Header: bucket count");
388 Asm->emitInt32(BucketCount);
389 Asm->OutStreamer->AddComment("Header: name count");
390 Asm->emitInt32(NameCount);
391 Asm->OutStreamer->AddComment("Header: abbreviation table size");
392 Asm->emitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
393 Asm->OutStreamer->AddComment("Header: augmentation string size");
394 assert(AugmentationStringSize % 4 == 0);
395 Asm->emitInt32(AugmentationStringSize);
396 Asm->OutStreamer->AddComment("Header: augmentation string");
397 Asm->OutStreamer->emitBytes({AugmentationString, AugmentationStringSize});
398}
399
400std::optional<uint64_t>
402 if (auto *Parent = Die.getParent();
403 Parent && !Parent->findAttribute(dwarf::Attribute::DW_AT_declaration))
404 return Parent->getOffset();
405 return {};
406}
407
408static std::optional<dwarf::Form>
410 std::optional<OffsetAndUnitID> ParentOffset) {
411 // No parent information
412 if (!ParentOffset)
413 return std::nullopt;
414 // Parent is indexed by this table.
415 if (IndexedOffsets.contains(*ParentOffset))
416 return dwarf::Form::DW_FORM_ref4;
417 // Parent is not indexed by this table.
418 return dwarf::Form::DW_FORM_flag_present;
419}
420
422 ID.AddInteger(DieTag);
423 for (const DebugNamesAbbrev::AttributeEncoding &Enc : AttrVect) {
424 ID.AddInteger(Enc.Index);
425 ID.AddInteger(Enc.Form);
426 }
427}
428
429void Dwarf5AccelTableWriter::populateAbbrevsMap() {
430 for (auto &Bucket : Contents.getBuckets()) {
431 for (auto *Hash : Bucket) {
432 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>()) {
433 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
434 getIndexForEntry(*Value);
435 std::optional<dwarf::Form> MaybeParentForm = getFormForIdxParent(
436 IndexedOffsets, Value->getParentDieOffsetAndUnitID());
437 DebugNamesAbbrev Abbrev(Value->getDieTag());
438 if (EntryRet)
439 Abbrev.addAttribute(EntryRet->Encoding);
440 Abbrev.addAttribute({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
441 if (MaybeParentForm)
442 Abbrev.addAttribute({dwarf::DW_IDX_parent, *MaybeParentForm});
444 Abbrev.Profile(ID);
445 void *InsertPos;
446 if (DebugNamesAbbrev *Existing =
447 AbbreviationsSet.FindNodeOrInsertPos(ID, InsertPos)) {
448 Value->setAbbrevNumber(Existing->getNumber());
449 continue;
450 }
451 DebugNamesAbbrev *NewAbbrev =
452 new (Alloc) DebugNamesAbbrev(std::move(Abbrev));
453 AbbreviationsVector.push_back(NewAbbrev);
454 NewAbbrev->setNumber(AbbreviationsVector.size());
455 AbbreviationsSet.InsertNode(NewAbbrev, InsertPos);
456 Value->setAbbrevNumber(NewAbbrev->getNumber());
457 }
458 }
459 }
460}
461
462void Dwarf5AccelTableWriter::emitCUList() const {
463 for (const auto &CU : enumerate(CompUnits)) {
464 Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
465 if (std::holds_alternative<MCSymbol *>(CU.value()))
466 Asm->emitDwarfSymbolReference(std::get<MCSymbol *>(CU.value()));
467 else
468 Asm->emitDwarfLengthOrOffset(std::get<uint64_t>(CU.value()));
469 }
470}
471
472void Dwarf5AccelTableWriter::emitTUList() const {
473 for (const auto &TU : enumerate(TypeUnits)) {
474 Asm->OutStreamer->AddComment("Type unit " + Twine(TU.index()));
475 if (std::holds_alternative<MCSymbol *>(TU.value()))
476 Asm->emitDwarfSymbolReference(std::get<MCSymbol *>(TU.value()));
477 else if (IsSplitDwarf)
478 Asm->emitInt64(std::get<uint64_t>(TU.value()));
479 else
480 Asm->emitDwarfLengthOrOffset(std::get<uint64_t>(TU.value()));
481 }
482}
483
484void Dwarf5AccelTableWriter::emitBuckets() const {
485 uint32_t Index = 1;
486 for (const auto &Bucket : enumerate(Contents.getBuckets())) {
487 Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
488 Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
489 Index += Bucket.value().size();
490 }
491}
492
493void Dwarf5AccelTableWriter::emitStringOffsets() const {
494 for (const auto &Bucket : enumerate(Contents.getBuckets())) {
495 for (auto *Hash : Bucket.value()) {
496 DwarfStringPoolEntryRef String = Hash->Name;
497 Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
498 ": " + String.getString());
499 Asm->emitDwarfStringOffset(String);
500 }
501 }
502}
503
504void Dwarf5AccelTableWriter::emitAbbrevs() const {
505 Asm->OutStreamer->emitLabel(AbbrevStart);
506 for (const DebugNamesAbbrev *Abbrev : AbbreviationsVector) {
507 Asm->OutStreamer->AddComment("Abbrev code");
508 Asm->emitULEB128(Abbrev->getNumber());
509 Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev->getDieTag()));
510 Asm->emitULEB128(Abbrev->getDieTag());
511 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
512 Abbrev->getAttributes()) {
513 Asm->emitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
514 Asm->emitULEB128(AttrEnc.Form,
515 dwarf::FormEncodingString(AttrEnc.Form).data());
516 }
517 Asm->emitULEB128(0, "End of abbrev");
518 Asm->emitULEB128(0, "End of abbrev");
519 }
520 Asm->emitULEB128(0, "End of abbrev list");
521 Asm->OutStreamer->emitLabel(AbbrevEnd);
522}
523
524void Dwarf5AccelTableWriter::emitEntry(
525 const DWARF5AccelTableData &Entry,
526 const DenseMap<OffsetAndUnitID, MCSymbol *> &DIEOffsetToAccelEntryLabel,
527 DenseSet<MCSymbol *> &EmittedAccelEntrySymbols) {
528 unsigned AbbrevIndex = Entry.getAbbrevNumber() - 1;
529 assert(AbbrevIndex < AbbreviationsVector.size() &&
530 "Entry abbrev index is outside of abbreviations vector range.");
531 DebugNamesAbbrev *Abbrev = AbbreviationsVector[AbbrevIndex];
532 std::optional<DWARF5AccelTable::UnitIndexAndEncoding> EntryRet =
533 getIndexForEntry(Entry);
534 std::optional<OffsetAndUnitID> MaybeParentOffset =
535 Entry.getParentDieOffsetAndUnitID();
536 auto EntrySymbolIt =
537 DIEOffsetToAccelEntryLabel.find(Entry.getDieOffsetAndUnitID());
538 assert(EntrySymbolIt != DIEOffsetToAccelEntryLabel.end());
539 MCSymbol *EntrySymbol = EntrySymbolIt->getSecond();
540
541 // Emit the label for this Entry, so that IDX_parents may refer to it.
542 // Note: a DIE may have multiple accelerator Entries; this check avoids
543 // creating/emitting multiple labels for the same DIE.
544 if (EmittedAccelEntrySymbols.insert(EntrySymbol).second)
545 Asm->OutStreamer->emitLabel(EntrySymbol);
546
547 Asm->emitULEB128(Entry.getAbbrevNumber(), "Abbreviation code");
548
549 for (const DebugNamesAbbrev::AttributeEncoding &AttrEnc :
550 Abbrev->getAttributes()) {
551 Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
552 switch (AttrEnc.Index) {
553 case dwarf::DW_IDX_compile_unit:
554 case dwarf::DW_IDX_type_unit: {
555 DIEInteger ID(EntryRet->Index);
556 ID.emitValue(Asm, AttrEnc.Form);
557 break;
558 }
559 case dwarf::DW_IDX_die_offset:
560 assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
561 Asm->emitInt32(Entry.getDieOffset());
562 break;
563 case dwarf::DW_IDX_parent: {
564 if (AttrEnc.Form == dwarf::Form::DW_FORM_flag_present)
565 break;
566 auto ParentSymbolIt = DIEOffsetToAccelEntryLabel.find(*MaybeParentOffset);
567 assert(ParentSymbolIt != DIEOffsetToAccelEntryLabel.end());
568 Asm->emitLabelDifference(ParentSymbolIt->getSecond(), EntryPool, 4);
569 break;
570 }
571 default:
572 llvm_unreachable("Unexpected index attribute!");
573 }
574 }
575}
576
577void Dwarf5AccelTableWriter::emitData() {
578 DenseMap<OffsetAndUnitID, MCSymbol *> DIEOffsetToAccelEntryLabel;
579
580 for (OffsetAndUnitID Offset : IndexedOffsets)
581 DIEOffsetToAccelEntryLabel.insert({Offset, Asm->createTempSymbol("")});
582
583 Asm->OutStreamer->emitLabel(EntryPool);
584 DenseSet<MCSymbol *> EmittedAccelEntrySymbols;
585 for (auto &Bucket : Contents.getBuckets()) {
586 for (auto *Hash : Bucket) {
587 // Remember to emit the label for our offset.
588 Asm->OutStreamer->emitLabel(Hash->Sym);
589 for (const auto *Value : Hash->getValues<DWARF5AccelTableData *>())
590 emitEntry(*Value, DIEOffsetToAccelEntryLabel, EmittedAccelEntrySymbols);
591 Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
592 Asm->emitInt8(0);
593 }
594 }
595}
596
597Dwarf5AccelTableWriter::Dwarf5AccelTableWriter(
598 AsmPrinter *Asm, const AccelTableBase &Contents,
599 ArrayRef<std::variant<MCSymbol *, uint64_t>> CompUnits,
600 ArrayRef<std::variant<MCSymbol *, uint64_t>> TypeUnits,
601 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
602 const DWARF5AccelTableData &)>
603 getIndexForEntry,
604 bool IsSplitDwarf)
605 : AccelTableWriter(Asm, Contents, false),
606 Header(CompUnits.size(), IsSplitDwarf ? 0 : TypeUnits.size(),
607 IsSplitDwarf ? TypeUnits.size() : 0, Contents.getBucketCount(),
608 Contents.getUniqueNameCount()),
609 CompUnits(CompUnits), TypeUnits(TypeUnits),
610 getIndexForEntry(std::move(getIndexForEntry)),
611 IsSplitDwarf(IsSplitDwarf) {
612
613 for (auto &Bucket : Contents.getBuckets())
614 for (auto *Hash : Bucket)
615 for (auto *Value : Hash->getValues<DWARF5AccelTableData *>())
616 IndexedOffsets.insert(Value->getDieOffsetAndUnitID());
617
618 populateAbbrevsMap();
619}
620
621void Dwarf5AccelTableWriter::emit() {
622 Header.emit(*this);
623 emitCUList();
624 emitTUList();
625 emitBuckets();
626 emitHashes();
627 emitStringOffsets();
628 emitOffsets(EntryPool);
629 emitAbbrevs();
630 emitData();
631 Asm->OutStreamer->emitValueToAlignment(Align(4), 0);
632 Asm->OutStreamer->emitLabel(ContributionEnd);
633}
634
636 StringRef Prefix, const MCSymbol *SecBegin,
638 Contents.finalize(Asm, Prefix);
639 AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
640}
641
643 AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD,
644 ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
645 TUVectorTy TUSymbols = Contents.getTypeUnitsSymbols();
646 std::vector<std::variant<MCSymbol *, uint64_t>> CompUnits;
647 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;
648 SmallVector<unsigned, 1> CUIndex(CUs.size());
649 DenseMap<unsigned, unsigned> TUIndex(TUSymbols.size());
650 int CUCount = 0;
651 int TUCount = 0;
652 for (const auto &CU : enumerate(CUs)) {
653 switch (CU.value()->getCUNode()->getNameTableKind()) {
656 break;
657 default:
658 continue;
659 }
660 CUIndex[CU.index()] = CUCount++;
661 assert(CU.index() == CU.value()->getUniqueID());
662 const DwarfCompileUnit *MainCU =
663 DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
664 CompUnits.push_back(MainCU->getLabelBegin());
665 }
666
667 for (const auto &TU : TUSymbols) {
668 TUIndex[TU.UniqueID] = TUCount++;
669 if (DD.useSplitDwarf())
670 TypeUnits.push_back(std::get<uint64_t>(TU.LabelOrSignature));
671 else
672 TypeUnits.push_back(std::get<MCSymbol *>(TU.LabelOrSignature));
673 }
674
675 if (CompUnits.empty())
676 return;
677
678 Asm->OutStreamer->switchSection(
679 Asm->getObjFileLowering().getDwarfDebugNamesSection());
680
681 Contents.finalize(Asm, "names");
682 dwarf::Form CUIndexForm =
683 DIEInteger::BestForm(/*IsSigned*/ false, CompUnits.size() - 1);
684 dwarf::Form TUIndexForm =
685 DIEInteger::BestForm(/*IsSigned*/ false, TypeUnits.size() - 1);
686 Dwarf5AccelTableWriter(
687 Asm, Contents, CompUnits, TypeUnits,
688 [&](const DWARF5AccelTableData &Entry)
689 -> std::optional<DWARF5AccelTable::UnitIndexAndEncoding> {
690 if (Entry.isTU())
691 return {{TUIndex[Entry.getUnitID()],
692 {dwarf::DW_IDX_type_unit, TUIndexForm}}};
693 if (CUIndex.size() > 1)
694 return {{CUIndex[Entry.getUnitID()],
695 {dwarf::DW_IDX_compile_unit, CUIndexForm}}};
696 return std::nullopt;
697 },
698 DD.useSplitDwarf())
699 .emit();
700}
701
703 TUSymbolsOrHashes.push_back({U.getLabelBegin(), U.getUniqueID()});
704}
705
707 TUSymbolsOrHashes.push_back({U.getTypeSignature(), U.getUniqueID()});
708}
709
711 AsmPrinter *Asm, DWARF5AccelTable &Contents,
712 ArrayRef<std::variant<MCSymbol *, uint64_t>> CUs,
713 llvm::function_ref<std::optional<DWARF5AccelTable::UnitIndexAndEncoding>(
714 const DWARF5AccelTableData &)>
715 getIndexForEntry) {
716 std::vector<std::variant<MCSymbol *, uint64_t>> TypeUnits;
717 Contents.finalize(Asm, "names");
718 Dwarf5AccelTableWriter(Asm, Contents, CUs, TypeUnits, getIndexForEntry, false)
719 .emit();
720}
721
723 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
724 "The section offset exceeds the limit.");
725 Asm->emitInt32(Die.getDebugSectionOffset());
726}
727
729 assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
730 "The section offset exceeds the limit.");
731 Asm->emitInt32(Die.getDebugSectionOffset());
732 Asm->emitInt16(Die.getTag());
733 Asm->emitInt8(0);
734}
735
737 Asm->emitInt32(Offset);
738}
739
741 Asm->emitInt32(Offset);
742 Asm->emitInt16(Tag);
744 : 0);
745 Asm->emitInt32(QualifiedNameHash);
746}
747
752
753#ifndef NDEBUG
754void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
755 OS << "Magic: " << format("0x%x", Magic) << "\n"
756 << "Version: " << Version << "\n"
757 << "Hash Function: " << HashFunction << "\n"
758 << "Bucket Count: " << BucketCount << "\n"
759 << "Header Data Length: " << HeaderDataLength << "\n";
760}
761
763 OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
764 << "Form: " << dwarf::FormEncodingString(Form) << "\n";
765}
766
767void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
768 OS << "DIE Offset Base: " << DieOffsetBase << "\n";
769 for (auto Atom : Atoms)
770 Atom.print(OS);
771}
772
773void AppleAccelTableWriter::print(raw_ostream &OS) const {
774 Header.print(OS);
775 HeaderData.print(OS);
776 Contents.print(OS);
777 SecBegin->print(OS, nullptr);
778}
779
781 OS << "Name: " << Name.getString() << "\n";
782 OS << " Hash Value: " << format("0x%x", HashValue) << "\n";
783 OS << " Symbol: ";
784 if (Sym)
785 OS << *Sym;
786 else
787 OS << "<none>";
788 OS << "\n";
789 for (auto *Value : Values)
790 Value->print(OS);
791}
792
794 // Print Content.
795 OS << "Entries: \n";
796 for (const auto &[Name, Data] : Entries) {
797 OS << "Name: " << Name << "\n";
798 for (auto *V : Data.Values)
799 V->print(OS);
800 }
801
802 OS << "Buckets and Hashes: \n";
803 for (const auto &Bucket : Buckets)
804 for (const auto &Hash : Bucket)
805 Hash->print(OS);
806
807 OS << "Data: \n";
808 for (const auto &E : Entries)
809 E.second.print(OS);
810}
811
813 OS << " Offset: " << getDieOffset() << "\n";
814 OS << " Tag: " << dwarf::TagString(getDieTag()) << "\n";
815}
816
818 OS << " Offset: " << Die.getOffset() << "\n";
819}
820
822 OS << " Offset: " << Die.getOffset() << "\n";
823 OS << " Tag: " << dwarf::TagString(Die.getTag()) << "\n";
824}
825
827 OS << " Static Offset: " << Offset << "\n";
828}
829
831 OS << " Static Offset: " << Offset << "\n";
832 OS << " QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
833 OS << " Tag: " << dwarf::TagString(Tag) << "\n";
834 OS << " ObjCClassIsImplementation: "
835 << (ObjCClassIsImplementation ? "true" : "false");
836 OS << "\n";
837}
838#endif
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static std::optional< unsigned > getTag(const TargetRegisterInfo *TRI, const MachineInstr &MI, const LoadInfo &LI)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Prepare AGPR Alloc
static std::optional< dwarf::Form > getFormForIdxParent(const DenseSet< OffsetAndUnitID > &IndexedOffsets, std::optional< OffsetAndUnitID > ParentOffset)
This file contains support for writing accelerator tables.
Function Alias Analysis false
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
basic Basic Alias true
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseSet and SmallDenseSet classes.
This file contains constants used for implementing Dwarf debug support.
This file contains some templates that are useful if you are working with the STL at all.
A base class holding non-template-dependant functionality of the AccelTable class.
Definition AccelTable.h:136
std::vector< HashData * > HashList
Definition AccelTable.h:161
LLVM_ABI void computeBucketCount()
LLVM_ABI void finalize(AsmPrinter *Asm, StringRef Prefix)
void print(raw_ostream &OS) const
ArrayRef< HashList > getBuckets() const
Definition AccelTable.h:184
StringEntries Entries
Definition AccelTable.h:169
Interface which the different types of accelerator table data have to conform.
Definition AccelTable.h:115
A base class for different implementations of Data classes for Apple Accelerator Tables.
Definition AccelTable.h:233
void emit(AsmPrinter *Asm) const override
void print(raw_ostream &OS) const override
static constexpr Atom Atoms[]
Definition AccelTable.h:482
static constexpr Atom Atoms[]
Definition AccelTable.h:519
void emit(AsmPrinter *Asm) const override
void print(raw_ostream &OS) const override
void emit(AsmPrinter *Asm) const override
void print(raw_ostream &OS) const override
static constexpr Atom Atoms[]
Definition AccelTable.h:545
void print(raw_ostream &OS) const override
void emit(AsmPrinter *Asm) const override
static constexpr Atom Atoms[]
Definition AccelTable.h:501
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:41
This class is intended to be used as a driving class for all asm writers.
Definition AsmPrinter.h:90
An integer value DIE.
Definition DIE.h:169
static dwarf::Form BestForm(bool IsSigned, uint64_t Int)
Choose the best form for integer.
Definition DIE.h:176
A structured debug information entry.
Definition DIE.h:828
LLVM_ABI DIEValue findAttribute(dwarf::Attribute Attribute) const
Find a value in the DIE with the attribute given.
Definition DIE.cpp:210
LLVM_ABI DIE * getParent() const
Definition DIE.cpp:172
The Data class implementation for DWARF v5 accelerator table.
Definition AccelTable.h:293
void print(raw_ostream &OS) const override
unsigned getDieTag() const
Definition AccelTable.h:319
std::variant< const DIE *, uint64_t > OffsetVal
Definition AccelTable.h:357
LLVM_ABI DWARF5AccelTableData(const DIE &Die, const uint32_t UnitID, const bool IsTU)
static LLVM_ABI std::optional< uint64_t > getDefiningParentDieOffset(const DIE &Die)
If Die has a non-null parent and the parent is not a declaration, return its offset.
uint64_t getDieOffset() const
Definition AccelTable.h:310
LLVM_ABI void addTypeUnitSignature(DwarfTypeUnit &U)
Add a type unit Signature.
const TUVectorTy & getTypeUnitsSymbols()
Returns type units that were constructed.
Definition AccelTable.h:413
LLVM_ABI void addTypeUnitSymbol(DwarfTypeUnit &U)
Add a type unit start symbol.
void setNumber(uint32_t AbbrevNumber)
Set abbreviation tag index.
Definition AccelTable.h:380
const SmallVector< AttributeEncoding, 1 > & getAttributes() const
Returns attributes for an abbreviation.
Definition AccelTable.h:388
LLVM_ABI void Profile(FoldingSetNodeID &ID) const
Used to gather unique data for the abbreviation folding set.
uint32_t getNumber() const
Get abbreviation tag index.
Definition AccelTable.h:382
iterator find(const_arg_type_t< KeyT > Val)
Definition DenseMap.h:165
iterator end()
Definition DenseMap.h:81
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition DenseMap.h:214
Implements a dense probed hash-table based set.
Definition DenseSet.h:269
Collects and handles dwarf debug information.
Definition DwarfDebug.h:351
bool useSplitDwarf() const
Returns whether or not to change the current debug info for the split dwarf proposal support.
Definition DwarfDebug.h:824
DwarfStringPoolEntryRef: Dwarf string pool entry reference.
MCSymbol * getLabelBegin() const
Get the the symbol for start of the section for this unit.
Definition DwarfUnit.h:105
void InsertNode(T *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition FoldingSet.h:516
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition FoldingSet.h:508
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition FoldingSet.h:330
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition MCSymbol.h:42
LLVM_ABI void print(raw_ostream &OS, const MCAsmInfo *MAI) const
print - Print the value to the stream OS.
Definition MCSymbol.cpp:59
void reserve(size_type N)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
Definition StringRef.h:55
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
LLVM Value Representation.
Definition Value.h:75
LLVM_ABI void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:194
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition DenseSet.h:169
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
LLVM_ABI StringRef FormEncodingString(unsigned Encoding)
Definition Dwarf.cpp:105
LLVM_ABI StringRef IndexString(unsigned Idx)
Definition Dwarf.cpp:781
LLVM_ABI StringRef AtomTypeString(unsigned Atom)
Definition Dwarf.cpp:683
LLVM_ABI StringRef TagString(unsigned Tag)
Definition Dwarf.cpp:21
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ Entry
Definition COFF.h:862
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
uint32_t getDebugNamesBucketCount(uint32_t UniqueHashCount)
Definition Dwarf.h:955
@ DW_FLAG_type_implementation
Definition Dwarf.h:946
@ DW_hash_function_djb
Definition Dwarf.h:951
bool empty() const
Definition BasicBlock.h:101
constexpr uint16_t Magic
Definition SFrame.h:32
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
@ Offset
Definition DWP.cpp:477
FunctionAddr VTableAddr Value
Definition InstrProf.h:137
void stable_sort(R &&Range)
Definition STLExtras.h:2038
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition STLExtras.h:1657
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
Definition STLExtras.h:2452
SmallVector< TypeUnitMetaInfo, 1 > TUVectorTy
Definition AccelTable.h:402
auto unique(Range &&R, Predicate P)
Definition STLExtras.h:2056
LLVM_ABI void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, StringRef Prefix, const MCSymbol *SecBegin, ArrayRef< AppleAccelTableData::Atom > Atoms)
FunctionAddr VTableAddr uintptr_t uintptr_t Version
Definition InstrProf.h:302
void sort(IteratorTy Start, IteratorTy End)
Definition STLExtras.h:1624
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
BumpPtrAllocatorImpl BumpPtrAllocator
The standard BumpPtrAllocator which just uses the default template parameters.
Definition Allocator.h:383
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition Format.h:126
FunctionAddr VTableAddr uintptr_t uintptr_t Data
Definition InstrProf.h:189
ArrayRef(const T &OneElt) -> ArrayRef< T >
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1847
LLVM_ABI void emitDWARF5AccelTable(AsmPrinter *Asm, DWARF5AccelTable &Contents, const DwarfDebug &DD, ArrayRef< std::unique_ptr< DwarfCompileUnit > > CUs)
Represents a group of entries with identical name (and hence, hash value).
Definition AccelTable.h:141
void print(raw_ostream &OS) const
DwarfStringPoolEntryRef Name
Definition AccelTable.h:142
std::vector< AccelTableData * > Values
Definition AccelTable.h:144
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition Alignment.h:39
An Atom defines the form of the data in an Apple accelerator table.
Definition AccelTable.h:238
const uint16_t Form
DWARF Form.
Definition AccelTable.h:242
void print(raw_ostream &OS) const
const uint16_t Type
Atom Type.
Definition AccelTable.h:240
Helper class to identify an entry in DWARF5AccelTable based on their DIE offset and UnitID.
Definition AccelTable.h:261