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