llvm/lib/CodeGen/AsmPrinter/AccelTable.cpp

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