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