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