xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp (revision 9f23cbd6cae82fd77edfad7173432fa8dccd0a95)
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 "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/StringMap.h"
17 #include "llvm/ADT/Twine.h"
18 #include "llvm/BinaryFormat/Dwarf.h"
19 #include "llvm/CodeGen/AsmPrinter.h"
20 #include "llvm/CodeGen/DIE.h"
21 #include "llvm/MC/MCStreamer.h"
22 #include "llvm/MC/MCSymbol.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Target/TargetLoweringObjectFile.h"
25 #include <algorithm>
26 #include <cstddef>
27 #include <cstdint>
28 #include <limits>
29 #include <vector>
30 
31 using namespace llvm;
32 
33 void AccelTableBase::computeBucketCount() {
34   // First get the number of unique hashes.
35   std::vector<uint32_t> Uniques;
36   Uniques.reserve(Entries.size());
37   for (const auto &E : Entries)
38     Uniques.push_back(E.second.HashValue);
39   array_pod_sort(Uniques.begin(), Uniques.end());
40   std::vector<uint32_t>::iterator P =
41       std::unique(Uniques.begin(), Uniques.end());
42 
43   UniqueHashCount = std::distance(Uniques.begin(), P);
44 
45   if (UniqueHashCount > 1024)
46     BucketCount = UniqueHashCount / 4;
47   else if (UniqueHashCount > 16)
48     BucketCount = UniqueHashCount / 2;
49   else
50     BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
51 }
52 
53 void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
54   // Create the individual hash data outputs.
55   for (auto &E : Entries) {
56     // Unique the entries.
57     llvm::stable_sort(E.second.Values,
58                       [](const AccelTableData *A, const AccelTableData *B) {
59                         return *A < *B;
60                       });
61     E.second.Values.erase(
62         std::unique(E.second.Values.begin(), E.second.Values.end()),
63         E.second.Values.end());
64   }
65 
66   // Figure out how many buckets we need, then compute the bucket contents and
67   // the final ordering. The hashes and offsets can be emitted by walking these
68   // data structures. We add temporary symbols to the data so they can be
69   // referenced when emitting the offsets.
70   computeBucketCount();
71 
72   // Compute bucket contents and final ordering.
73   Buckets.resize(BucketCount);
74   for (auto &E : Entries) {
75     uint32_t Bucket = E.second.HashValue % BucketCount;
76     Buckets[Bucket].push_back(&E.second);
77     E.second.Sym = Asm->createTempSymbol(Prefix);
78   }
79 
80   // Sort the contents of the buckets by hash value so that hash collisions end
81   // up together. Stable sort makes testing easier and doesn't cost much more.
82   for (auto &Bucket : Buckets)
83     llvm::stable_sort(Bucket, [](HashData *LHS, HashData *RHS) {
84       return LHS->HashValue < RHS->HashValue;
85     });
86 }
87 
88 namespace {
89 /// Base class for writing out Accelerator tables. It holds the common
90 /// functionality for the two Accelerator table types.
91 class AccelTableWriter {
92 protected:
93   AsmPrinter *const Asm;          ///< Destination.
94   const AccelTableBase &Contents; ///< Data to emit.
95 
96   /// Controls whether to emit duplicate hash and offset table entries for names
97   /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
98   /// tables do.
99   const bool SkipIdenticalHashes;
100 
101   void emitHashes() const;
102 
103   /// Emit offsets to lists of entries with identical names. The offsets are
104   /// relative to the Base argument.
105   void emitOffsets(const MCSymbol *Base) const;
106 
107 public:
108   AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
109                    bool SkipIdenticalHashes)
110       : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
111   }
112 };
113 
114 class AppleAccelTableWriter : public AccelTableWriter {
115   using Atom = AppleAccelTableData::Atom;
116 
117   /// The fixed header of an Apple Accelerator Table.
118   struct Header {
119     uint32_t Magic = MagicHash;
120     uint16_t Version = 1;
121     uint16_t HashFunction = dwarf::DW_hash_function_djb;
122     uint32_t BucketCount;
123     uint32_t HashCount;
124     uint32_t HeaderDataLength;
125 
126     /// 'HASH' magic value to detect endianness.
127     static const uint32_t MagicHash = 0x48415348;
128 
129     Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
130         : BucketCount(BucketCount), HashCount(UniqueHashCount),
131           HeaderDataLength(DataLength) {}
132 
133     void emit(AsmPrinter *Asm) const;
134 #ifndef NDEBUG
135     void print(raw_ostream &OS) const;
136     void dump() const { print(dbgs()); }
137 #endif
138   };
139 
140   /// The HeaderData describes the structure of an Apple accelerator table
141   /// through a list of Atoms.
142   struct HeaderData {
143     /// In the case of data that is referenced via DW_FORM_ref_* the offset
144     /// base is used to describe the offset for all forms in the list of atoms.
145     uint32_t DieOffsetBase;
146 
147     const SmallVector<Atom, 4> Atoms;
148 
149     HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
150         : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
151 
152     void emit(AsmPrinter *Asm) const;
153 #ifndef NDEBUG
154     void print(raw_ostream &OS) const;
155     void dump() const { print(dbgs()); }
156 #endif
157   };
158 
159   Header Header;
160   HeaderData HeaderData;
161   const MCSymbol *SecBegin;
162 
163   void emitBuckets() const;
164   void emitData() const;
165 
166 public:
167   AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
168                         ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
169       : AccelTableWriter(Asm, Contents, true),
170         Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
171                8 + (Atoms.size() * 4)),
172         HeaderData(Atoms), SecBegin(SecBegin) {}
173 
174   void emit() const;
175 
176 #ifndef NDEBUG
177   void print(raw_ostream &OS) const;
178   void dump() const { print(dbgs()); }
179 #endif
180 };
181 
182 /// Class responsible for emitting a DWARF v5 Accelerator Table. The only
183 /// public function is emit(), which performs the actual emission.
184 ///
185 /// The class is templated in its data type. This allows us to emit both dyamic
186 /// and static data entries. A callback abstract the logic to provide a CU
187 /// index for a given entry, which is different per data type, but identical
188 /// for every entry in the same table.
189 template <typename DataT>
190 class Dwarf5AccelTableWriter : public AccelTableWriter {
191   struct Header {
192     uint16_t Version = 5;
193     uint16_t Padding = 0;
194     uint32_t CompUnitCount;
195     uint32_t LocalTypeUnitCount = 0;
196     uint32_t ForeignTypeUnitCount = 0;
197     uint32_t BucketCount;
198     uint32_t NameCount;
199     uint32_t AbbrevTableSize = 0;
200     uint32_t AugmentationStringSize = sizeof(AugmentationString);
201     char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
202 
203     Header(uint32_t CompUnitCount, uint32_t BucketCount, uint32_t NameCount)
204         : CompUnitCount(CompUnitCount), BucketCount(BucketCount),
205           NameCount(NameCount) {}
206 
207     void emit(Dwarf5AccelTableWriter &Ctx);
208   };
209   struct AttributeEncoding {
210     dwarf::Index Index;
211     dwarf::Form Form;
212   };
213 
214   Header Header;
215   DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
216   ArrayRef<MCSymbol *> CompUnits;
217   llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry;
218   MCSymbol *ContributionEnd = nullptr;
219   MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
220   MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
221   MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
222 
223   DenseSet<uint32_t> getUniqueTags() const;
224 
225   // Right now, we emit uniform attributes for all tags.
226   SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
227 
228   void emitCUList() const;
229   void emitBuckets() const;
230   void emitStringOffsets() const;
231   void emitAbbrevs() const;
232   void emitEntry(const DataT &Entry) const;
233   void emitData() const;
234 
235 public:
236   Dwarf5AccelTableWriter(
237       AsmPrinter *Asm, const AccelTableBase &Contents,
238       ArrayRef<MCSymbol *> CompUnits,
239       llvm::function_ref<unsigned(const DataT &)> GetCUIndexForEntry);
240 
241   void emit();
242 };
243 } // namespace
244 
245 void AccelTableWriter::emitHashes() const {
246   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
247   unsigned BucketIdx = 0;
248   for (const auto &Bucket : Contents.getBuckets()) {
249     for (const auto &Hash : Bucket) {
250       uint32_t HashValue = Hash->HashValue;
251       if (SkipIdenticalHashes && PrevHash == HashValue)
252         continue;
253       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
254       Asm->emitInt32(HashValue);
255       PrevHash = HashValue;
256     }
257     BucketIdx++;
258   }
259 }
260 
261 void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
262   const auto &Buckets = Contents.getBuckets();
263   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
264   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
265     for (auto *Hash : Buckets[i]) {
266       uint32_t HashValue = Hash->HashValue;
267       if (SkipIdenticalHashes && PrevHash == HashValue)
268         continue;
269       PrevHash = HashValue;
270       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
271       Asm->emitLabelDifference(Hash->Sym, Base, Asm->getDwarfOffsetByteSize());
272     }
273   }
274 }
275 
276 void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
277   Asm->OutStreamer->AddComment("Header Magic");
278   Asm->emitInt32(Magic);
279   Asm->OutStreamer->AddComment("Header Version");
280   Asm->emitInt16(Version);
281   Asm->OutStreamer->AddComment("Header Hash Function");
282   Asm->emitInt16(HashFunction);
283   Asm->OutStreamer->AddComment("Header Bucket Count");
284   Asm->emitInt32(BucketCount);
285   Asm->OutStreamer->AddComment("Header Hash Count");
286   Asm->emitInt32(HashCount);
287   Asm->OutStreamer->AddComment("Header Data Length");
288   Asm->emitInt32(HeaderDataLength);
289 }
290 
291 void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
292   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
293   Asm->emitInt32(DieOffsetBase);
294   Asm->OutStreamer->AddComment("HeaderData Atom Count");
295   Asm->emitInt32(Atoms.size());
296 
297   for (const Atom &A : Atoms) {
298     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
299     Asm->emitInt16(A.Type);
300     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
301     Asm->emitInt16(A.Form);
302   }
303 }
304 
305 void AppleAccelTableWriter::emitBuckets() const {
306   const auto &Buckets = Contents.getBuckets();
307   unsigned index = 0;
308   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
309     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
310     if (!Buckets[i].empty())
311       Asm->emitInt32(index);
312     else
313       Asm->emitInt32(std::numeric_limits<uint32_t>::max());
314     // Buckets point in the list of hashes, not to the data. Do not increment
315     // the index multiple times in case of hash collisions.
316     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
317     for (auto *HD : Buckets[i]) {
318       uint32_t HashValue = HD->HashValue;
319       if (PrevHash != HashValue)
320         ++index;
321       PrevHash = HashValue;
322     }
323   }
324 }
325 
326 void AppleAccelTableWriter::emitData() const {
327   const auto &Buckets = Contents.getBuckets();
328   for (const AccelTableBase::HashList &Bucket : Buckets) {
329     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
330     for (const auto &Hash : Bucket) {
331       // Terminate the previous entry if there is no hash collision with the
332       // current one.
333       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
334           PrevHash != Hash->HashValue)
335         Asm->emitInt32(0);
336       // Remember to emit the label for our offset.
337       Asm->OutStreamer->emitLabel(Hash->Sym);
338       Asm->OutStreamer->AddComment(Hash->Name.getString());
339       Asm->emitDwarfStringOffset(Hash->Name);
340       Asm->OutStreamer->AddComment("Num DIEs");
341       Asm->emitInt32(Hash->Values.size());
342       for (const auto *V : Hash->Values)
343         static_cast<const AppleAccelTableData *>(V)->emit(Asm);
344       PrevHash = Hash->HashValue;
345     }
346     // Emit the final end marker for the bucket.
347     if (!Bucket.empty())
348       Asm->emitInt32(0);
349   }
350 }
351 
352 void AppleAccelTableWriter::emit() const {
353   Header.emit(Asm);
354   HeaderData.emit(Asm);
355   emitBuckets();
356   emitHashes();
357   emitOffsets(SecBegin);
358   emitData();
359 }
360 
361 template <typename DataT>
362 void Dwarf5AccelTableWriter<DataT>::Header::emit(Dwarf5AccelTableWriter &Ctx) {
363   assert(CompUnitCount > 0 && "Index must have at least one CU.");
364 
365   AsmPrinter *Asm = Ctx.Asm;
366   Ctx.ContributionEnd =
367       Asm->emitDwarfUnitLength("names", "Header: unit length");
368   Asm->OutStreamer->AddComment("Header: version");
369   Asm->emitInt16(Version);
370   Asm->OutStreamer->AddComment("Header: padding");
371   Asm->emitInt16(Padding);
372   Asm->OutStreamer->AddComment("Header: compilation unit count");
373   Asm->emitInt32(CompUnitCount);
374   Asm->OutStreamer->AddComment("Header: local type unit count");
375   Asm->emitInt32(LocalTypeUnitCount);
376   Asm->OutStreamer->AddComment("Header: foreign type unit count");
377   Asm->emitInt32(ForeignTypeUnitCount);
378   Asm->OutStreamer->AddComment("Header: bucket count");
379   Asm->emitInt32(BucketCount);
380   Asm->OutStreamer->AddComment("Header: name count");
381   Asm->emitInt32(NameCount);
382   Asm->OutStreamer->AddComment("Header: abbreviation table size");
383   Asm->emitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
384   Asm->OutStreamer->AddComment("Header: augmentation string size");
385   assert(AugmentationStringSize % 4 == 0);
386   Asm->emitInt32(AugmentationStringSize);
387   Asm->OutStreamer->AddComment("Header: augmentation string");
388   Asm->OutStreamer->emitBytes({AugmentationString, AugmentationStringSize});
389 }
390 
391 template <typename DataT>
392 DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
393   DenseSet<uint32_t> UniqueTags;
394   for (auto &Bucket : Contents.getBuckets()) {
395     for (auto *Hash : Bucket) {
396       for (auto *Value : Hash->Values) {
397         unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
398         UniqueTags.insert(Tag);
399       }
400     }
401   }
402   return UniqueTags;
403 }
404 
405 template <typename DataT>
406 SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
407 Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
408   SmallVector<AttributeEncoding, 2> UA;
409   if (CompUnits.size() > 1) {
410     size_t LargestCUIndex = CompUnits.size() - 1;
411     dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
412     UA.push_back({dwarf::DW_IDX_compile_unit, Form});
413   }
414   UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
415   return UA;
416 }
417 
418 template <typename DataT>
419 void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
420   for (const auto &CU : enumerate(CompUnits)) {
421     Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
422     Asm->emitDwarfSymbolReference(CU.value());
423   }
424 }
425 
426 template <typename DataT>
427 void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
428   uint32_t Index = 1;
429   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
430     Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
431     Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
432     Index += Bucket.value().size();
433   }
434 }
435 
436 template <typename DataT>
437 void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
438   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
439     for (auto *Hash : Bucket.value()) {
440       DwarfStringPoolEntryRef String = Hash->Name;
441       Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
442                                    ": " + String.getString());
443       Asm->emitDwarfStringOffset(String);
444     }
445   }
446 }
447 
448 template <typename DataT>
449 void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
450   Asm->OutStreamer->emitLabel(AbbrevStart);
451   for (const auto &Abbrev : Abbreviations) {
452     Asm->OutStreamer->AddComment("Abbrev code");
453     assert(Abbrev.first != 0);
454     Asm->emitULEB128(Abbrev.first);
455     Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
456     Asm->emitULEB128(Abbrev.first);
457     for (const auto &AttrEnc : Abbrev.second) {
458       Asm->emitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
459       Asm->emitULEB128(AttrEnc.Form,
460                        dwarf::FormEncodingString(AttrEnc.Form).data());
461     }
462     Asm->emitULEB128(0, "End of abbrev");
463     Asm->emitULEB128(0, "End of abbrev");
464   }
465   Asm->emitULEB128(0, "End of abbrev list");
466   Asm->OutStreamer->emitLabel(AbbrevEnd);
467 }
468 
469 template <typename DataT>
470 void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
471   auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
472   assert(AbbrevIt != Abbreviations.end() &&
473          "Why wasn't this abbrev generated?");
474 
475   Asm->emitULEB128(AbbrevIt->first, "Abbreviation code");
476   for (const auto &AttrEnc : AbbrevIt->second) {
477     Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
478     switch (AttrEnc.Index) {
479     case dwarf::DW_IDX_compile_unit: {
480       DIEInteger ID(getCUIndexForEntry(Entry));
481       ID.emitValue(Asm, AttrEnc.Form);
482       break;
483     }
484     case dwarf::DW_IDX_die_offset:
485       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
486       Asm->emitInt32(Entry.getDieOffset());
487       break;
488     default:
489       llvm_unreachable("Unexpected index attribute!");
490     }
491   }
492 }
493 
494 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
495   Asm->OutStreamer->emitLabel(EntryPool);
496   for (auto &Bucket : Contents.getBuckets()) {
497     for (auto *Hash : Bucket) {
498       // Remember to emit the label for our offset.
499       Asm->OutStreamer->emitLabel(Hash->Sym);
500       for (const auto *Value : Hash->Values)
501         emitEntry(*static_cast<const DataT *>(Value));
502       Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
503       Asm->emitInt8(0);
504     }
505   }
506 }
507 
508 template <typename DataT>
509 Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
510     AsmPrinter *Asm, const AccelTableBase &Contents,
511     ArrayRef<MCSymbol *> CompUnits,
512     llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry)
513     : AccelTableWriter(Asm, Contents, false),
514       Header(CompUnits.size(), Contents.getBucketCount(),
515              Contents.getUniqueNameCount()),
516       CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
517   DenseSet<uint32_t> UniqueTags = getUniqueTags();
518   SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
519 
520   Abbreviations.reserve(UniqueTags.size());
521   for (uint32_t Tag : UniqueTags)
522     Abbreviations.try_emplace(Tag, UniformAttributes);
523 }
524 
525 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() {
526   Header.emit(*this);
527   emitCUList();
528   emitBuckets();
529   emitHashes();
530   emitStringOffsets();
531   emitOffsets(EntryPool);
532   emitAbbrevs();
533   emitData();
534   Asm->OutStreamer->emitValueToAlignment(Align(4), 0);
535   Asm->OutStreamer->emitLabel(ContributionEnd);
536 }
537 
538 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
539                                    StringRef Prefix, const MCSymbol *SecBegin,
540                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
541   Contents.finalize(Asm, Prefix);
542   AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
543 }
544 
545 void llvm::emitDWARF5AccelTable(
546     AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
547     const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
548   std::vector<MCSymbol *> CompUnits;
549   SmallVector<unsigned, 1> CUIndex(CUs.size());
550   int Count = 0;
551   for (const auto &CU : enumerate(CUs)) {
552     if (CU.value()->getCUNode()->getNameTableKind() !=
553         DICompileUnit::DebugNameTableKind::Default)
554       continue;
555     CUIndex[CU.index()] = Count++;
556     assert(CU.index() == CU.value()->getUniqueID());
557     const DwarfCompileUnit *MainCU =
558         DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
559     CompUnits.push_back(MainCU->getLabelBegin());
560   }
561 
562   if (CompUnits.empty())
563     return;
564 
565   Asm->OutStreamer->switchSection(
566       Asm->getObjFileLowering().getDwarfDebugNamesSection());
567 
568   Contents.finalize(Asm, "names");
569   Dwarf5AccelTableWriter<DWARF5AccelTableData>(
570       Asm, Contents, CompUnits,
571       [&](const DWARF5AccelTableData &Entry) {
572         const DIE *CUDie = Entry.getDie().getUnitDie();
573         return CUIndex[DD.lookupCU(CUDie)->getUniqueID()];
574       })
575       .emit();
576 }
577 
578 void llvm::emitDWARF5AccelTable(
579     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
580     ArrayRef<MCSymbol *> CUs,
581     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
582         getCUIndexForEntry) {
583   Contents.finalize(Asm, "names");
584   Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
585                                                      getCUIndexForEntry)
586       .emit();
587 }
588 
589 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
590   assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
591          "The section offset exceeds the limit.");
592   Asm->emitInt32(Die.getDebugSectionOffset());
593 }
594 
595 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
596   assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
597          "The section offset exceeds the limit.");
598   Asm->emitInt32(Die.getDebugSectionOffset());
599   Asm->emitInt16(Die.getTag());
600   Asm->emitInt8(0);
601 }
602 
603 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
604   Asm->emitInt32(Offset);
605 }
606 
607 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
608   Asm->emitInt32(Offset);
609   Asm->emitInt16(Tag);
610   Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
611                                           : 0);
612   Asm->emitInt32(QualifiedNameHash);
613 }
614 
615 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
616 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
617 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
618 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
619 
620 #ifndef NDEBUG
621 void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
622   OS << "Magic: " << format("0x%x", Magic) << "\n"
623      << "Version: " << Version << "\n"
624      << "Hash Function: " << HashFunction << "\n"
625      << "Bucket Count: " << BucketCount << "\n"
626      << "Header Data Length: " << HeaderDataLength << "\n";
627 }
628 
629 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
630   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
631      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
632 }
633 
634 void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
635   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
636   for (auto Atom : Atoms)
637     Atom.print(OS);
638 }
639 
640 void AppleAccelTableWriter::print(raw_ostream &OS) const {
641   Header.print(OS);
642   HeaderData.print(OS);
643   Contents.print(OS);
644   SecBegin->print(OS, nullptr);
645 }
646 
647 void AccelTableBase::HashData::print(raw_ostream &OS) const {
648   OS << "Name: " << Name.getString() << "\n";
649   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
650   OS << "  Symbol: ";
651   if (Sym)
652     OS << *Sym;
653   else
654     OS << "<none>";
655   OS << "\n";
656   for (auto *Value : Values)
657     Value->print(OS);
658 }
659 
660 void AccelTableBase::print(raw_ostream &OS) const {
661   // Print Content.
662   OS << "Entries: \n";
663   for (const auto &Entry : Entries) {
664     OS << "Name: " << Entry.first() << "\n";
665     for (auto *V : Entry.second.Values)
666       V->print(OS);
667   }
668 
669   OS << "Buckets and Hashes: \n";
670   for (const auto &Bucket : Buckets)
671     for (const auto &Hash : Bucket)
672       Hash->print(OS);
673 
674   OS << "Data: \n";
675   for (const auto &E : Entries)
676     E.second.print(OS);
677 }
678 
679 void DWARF5AccelTableData::print(raw_ostream &OS) const {
680   OS << "  Offset: " << getDieOffset() << "\n";
681   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
682 }
683 
684 void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
685   OS << "  Offset: " << getDieOffset() << "\n";
686   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
687 }
688 
689 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
690   OS << "  Offset: " << Die.getOffset() << "\n";
691 }
692 
693 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
694   OS << "  Offset: " << Die.getOffset() << "\n";
695   OS << "  Tag: " << dwarf::TagString(Die.getTag()) << "\n";
696 }
697 
698 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
699   OS << "  Static Offset: " << Offset << "\n";
700 }
701 
702 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
703   OS << "  Static Offset: " << Offset << "\n";
704   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
705   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
706   OS << "  ObjCClassIsImplementation: "
707      << (ObjCClassIsImplementation ? "true" : "false");
708   OS << "\n";
709 }
710 #endif
711