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 "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/MCExpr.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 /// The class is templated in its data type. This allows us to emit both dyamic
 187 /// and static data entries. A callback abstract the logic to provide a CU
 188 /// index for a given entry, which is different per data type, but identical
 189 /// for every entry in the same table.
 190 template <typename DataT>
 191 class Dwarf5AccelTableWriter : public AccelTableWriter {
 192   struct Header {
 193     uint16_t Version = 5;
 194     uint16_t Padding = 0;
 195     uint32_t CompUnitCount;
 196     uint32_t LocalTypeUnitCount = 0;
 197     uint32_t ForeignTypeUnitCount = 0;
 198     uint32_t BucketCount;
 199     uint32_t NameCount;
 200     uint32_t AbbrevTableSize = 0;
 201     uint32_t AugmentationStringSize = sizeof(AugmentationString);
 202     char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
 203
 204     Header(uint32_t CompUnitCount, uint32_t BucketCount, uint32_t NameCount)
 205         : CompUnitCount(CompUnitCount), BucketCount(BucketCount),
 206           NameCount(NameCount) {}
 207
 208     void emit(Dwarf5AccelTableWriter &Ctx);
 209   };
 210   struct AttributeEncoding {
 211     dwarf::Index Index;
 212     dwarf::Form Form;
 213   };
 214
 215   Header Header;
 216   DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
 217   ArrayRef<MCSymbol *> CompUnits;
 218   llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry;
 219   MCSymbol *ContributionEnd = nullptr;
 220   MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
 221   MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
 222   MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
 223
 224   DenseSet<uint32_t> getUniqueTags() const;
 225
 226   // Right now, we emit uniform attributes for all tags.
 227   SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
 228
 229   void emitCUList() const;
 230   void emitBuckets() const;
 231   void emitStringOffsets() const;
 232   void emitAbbrevs() const;
 233   void emitEntry(const DataT &Entry) const;
 234   void emitData() const;
 235
 236 public:
 237   Dwarf5AccelTableWriter(
 238       AsmPrinter *Asm, const AccelTableBase &Contents,
 239       ArrayRef<MCSymbol *> CompUnits,
 240       llvm::function_ref<unsigned(const DataT &)> GetCUIndexForEntry);
 241
 242   void emit();
 243 };
 244 } // namespace
 245
 246 void AccelTableWriter::emitHashes() const {
 247   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 248   unsigned BucketIdx = 0;
 249   for (auto &Bucket : Contents.getBuckets()) {
 250     for (auto &Hash : Bucket) {
 251       uint32_t HashValue = Hash->HashValue;
 252       if (SkipIdenticalHashes && PrevHash == HashValue)
 253         continue;
 254       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
 255       Asm->emitInt32(HashValue);
 256       PrevHash = HashValue;
 257     }
 258     BucketIdx++;
 259   }
 260 }
 261
 262 void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
 263   const auto &Buckets = Contents.getBuckets();
 264   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 265   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 266     for (auto *Hash : Buckets[i]) {
 267       uint32_t HashValue = Hash->HashValue;
 268       if (SkipIdenticalHashes && PrevHash == HashValue)
 269         continue;
 270       PrevHash = HashValue;
 271       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
 272       Asm->emitLabelDifference(Hash->Sym, Base, Asm->getDwarfOffsetByteSize());
 273     }
 274   }
 275 }
 276
 277 void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
 278   Asm->OutStreamer->AddComment("Header Magic");
 279   Asm->emitInt32(Magic);
 280   Asm->OutStreamer->AddComment("Header Version");
 281   Asm->emitInt16(Version);
 282   Asm->OutStreamer->AddComment("Header Hash Function");
 283   Asm->emitInt16(HashFunction);
 284   Asm->OutStreamer->AddComment("Header Bucket Count");
 285   Asm->emitInt32(BucketCount);
 286   Asm->OutStreamer->AddComment("Header Hash Count");
 287   Asm->emitInt32(HashCount);
 288   Asm->OutStreamer->AddComment("Header Data Length");
 289   Asm->emitInt32(HeaderDataLength);
 290 }
 291
 292 void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
 293   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
 294   Asm->emitInt32(DieOffsetBase);
 295   Asm->OutStreamer->AddComment("HeaderData Atom Count");
 296   Asm->emitInt32(Atoms.size());
 297
 298   for (const Atom &A : Atoms) {
 299     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
 300     Asm->emitInt16(A.Type);
 301     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
 302     Asm->emitInt16(A.Form);
 303   }
 304 }
 305
 306 void AppleAccelTableWriter::emitBuckets() const {
 307   const auto &Buckets = Contents.getBuckets();
 308   unsigned index = 0;
 309   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 310     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
 311     if (!Buckets[i].empty())
 312       Asm->emitInt32(index);
 313     else
 314       Asm->emitInt32(std::numeric_limits<uint32_t>::max());
 315     // Buckets point in the list of hashes, not to the data. Do not increment
 316     // the index multiple times in case of hash collisions.
 317     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 318     for (auto *HD : Buckets[i]) {
 319       uint32_t HashValue = HD->HashValue;
 320       if (PrevHash != HashValue)
 321         ++index;
 322       PrevHash = HashValue;
 323     }
 324   }
 325 }
 326
 327 void AppleAccelTableWriter::emitData() const {
 328   const auto &Buckets = Contents.getBuckets();
 329   for (const AccelTableBase::HashList &Bucket : Buckets) {
 330     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 331     for (auto &Hash : Bucket) {
 332       // Terminate the previous entry if there is no hash collision with the
 333       // current one.
 334       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
 335           PrevHash != Hash->HashValue)
 336         Asm->emitInt32(0);
 337       // Remember to emit the label for our offset.
 338       Asm->OutStreamer->emitLabel(Hash->Sym);
 339       Asm->OutStreamer->AddComment(Hash->Name.getString());
 340       Asm->emitDwarfStringOffset(Hash->Name);
 341       Asm->OutStreamer->AddComment("Num DIEs");
 342       Asm->emitInt32(Hash->Values.size());
 343       for (const auto *V : Hash->Values)
 344         static_cast<const AppleAccelTableData *>(V)->emit(Asm);
 345       PrevHash = Hash->HashValue;
 346     }
 347     // Emit the final end marker for the bucket.
 348     if (!Bucket.empty())
 349       Asm->emitInt32(0);
 350   }
 351 }
 352
 353 void AppleAccelTableWriter::emit() const {
 354   Header.emit(Asm);
 355   HeaderData.emit(Asm);
 356   emitBuckets();
 357   emitHashes();
 358   emitOffsets(SecBegin);
 359   emitData();
 360 }
 361
 362 template <typename DataT>
 363 void Dwarf5AccelTableWriter<DataT>::Header::emit(Dwarf5AccelTableWriter &Ctx) {
 364   assert(CompUnitCount > 0 && "Index must have at least one CU.");
 365
 366   AsmPrinter *Asm = Ctx.Asm;
 367   Ctx.ContributionEnd =
 368       Asm->emitDwarfUnitLength("names", "Header: unit length");
 369   Asm->OutStreamer->AddComment("Header: version");
 370   Asm->emitInt16(Version);
 371   Asm->OutStreamer->AddComment("Header: padding");
 372   Asm->emitInt16(Padding);
 373   Asm->OutStreamer->AddComment("Header: compilation unit count");
 374   Asm->emitInt32(CompUnitCount);
 375   Asm->OutStreamer->AddComment("Header: local type unit count");
 376   Asm->emitInt32(LocalTypeUnitCount);
 377   Asm->OutStreamer->AddComment("Header: foreign type unit count");
 378   Asm->emitInt32(ForeignTypeUnitCount);
 379   Asm->OutStreamer->AddComment("Header: bucket count");
 380   Asm->emitInt32(BucketCount);
 381   Asm->OutStreamer->AddComment("Header: name count");
 382   Asm->emitInt32(NameCount);
 383   Asm->OutStreamer->AddComment("Header: abbreviation table size");
 384   Asm->emitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
 385   Asm->OutStreamer->AddComment("Header: augmentation string size");
 386   assert(AugmentationStringSize % 4 == 0);
 387   Asm->emitInt32(AugmentationStringSize);
 388   Asm->OutStreamer->AddComment("Header: augmentation string");
 389   Asm->OutStreamer->emitBytes({AugmentationString, AugmentationStringSize});
 390 }
 391
 392 template <typename DataT>
 393 DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
 394   DenseSet<uint32_t> UniqueTags;
 395   for (auto &Bucket : Contents.getBuckets()) {
 396     for (auto *Hash : Bucket) {
 397       for (auto *Value : Hash->Values) {
 398         unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
 399         UniqueTags.insert(Tag);
 400       }
 401     }
 402   }
 403   return UniqueTags;
 404 }
 405
 406 template <typename DataT>
 407 SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
 408 Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
 409   SmallVector<AttributeEncoding, 2> UA;
 410   if (CompUnits.size() > 1) {
 411     size_t LargestCUIndex = CompUnits.size() - 1;
 412     dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
 413     UA.push_back({dwarf::DW_IDX_compile_unit, Form});
 414   }
 415   UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
 416   return UA;
 417 }
 418
 419 template <typename DataT>
 420 void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
 421   for (const auto &CU : enumerate(CompUnits)) {
 422     Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
 423     Asm->emitDwarfSymbolReference(CU.value());
 424   }
 425 }
 426
 427 template <typename DataT>
 428 void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
 429   uint32_t Index = 1;
 430   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 431     Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
 432     Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
 433     Index += Bucket.value().size();
 434   }
 435 }
 436
 437 template <typename DataT>
 438 void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
 439   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 440     for (auto *Hash : Bucket.value()) {
 441       DwarfStringPoolEntryRef String = Hash->Name;
 442       Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
 443                                    ": " + String.getString());
 444       Asm->emitDwarfStringOffset(String);
 445     }
 446   }
 447 }
 448
 449 template <typename DataT>
 450 void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
 451   Asm->OutStreamer->emitLabel(AbbrevStart);
 452   for (const auto &Abbrev : Abbreviations) {
 453     Asm->OutStreamer->AddComment("Abbrev code");
 454     assert(Abbrev.first != 0);
 455     Asm->emitULEB128(Abbrev.first);
 456     Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
 457     Asm->emitULEB128(Abbrev.first);
 458     for (const auto &AttrEnc : Abbrev.second) {
 459       Asm->emitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
 460       Asm->emitULEB128(AttrEnc.Form,
 461                        dwarf::FormEncodingString(AttrEnc.Form).data());
 462     }
 463     Asm->emitULEB128(0, "End of abbrev");
 464     Asm->emitULEB128(0, "End of abbrev");
 465   }
 466   Asm->emitULEB128(0, "End of abbrev list");
 467   Asm->OutStreamer->emitLabel(AbbrevEnd);
 468 }
 469
 470 template <typename DataT>
 471 void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
 472   auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
 473   assert(AbbrevIt != Abbreviations.end() &&
 474          "Why wasn't this abbrev generated?");
 475
 476   Asm->emitULEB128(AbbrevIt->first, "Abbreviation code");
 477   for (const auto &AttrEnc : AbbrevIt->second) {
 478     Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
 479     switch (AttrEnc.Index) {
 480     case dwarf::DW_IDX_compile_unit: {
 481       DIEInteger ID(getCUIndexForEntry(Entry));
 482       ID.emitValue(Asm, AttrEnc.Form);
 483       break;
 484     }
 485     case dwarf::DW_IDX_die_offset:
 486       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
 487       Asm->emitInt32(Entry.getDieOffset());
 488       break;
 489     default:
 490       llvm_unreachable("Unexpected index attribute!");
 491     }
 492   }
 493 }
 494
 495 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
 496   Asm->OutStreamer->emitLabel(EntryPool);
 497   for (auto &Bucket : Contents.getBuckets()) {
 498     for (auto *Hash : Bucket) {
 499       // Remember to emit the label for our offset.
 500       Asm->OutStreamer->emitLabel(Hash->Sym);
 501       for (const auto *Value : Hash->Values)
 502         emitEntry(*static_cast<const DataT *>(Value));
 503       Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
 504       Asm->emitInt8(0);
 505     }
 506   }
 507 }
 508
 509 template <typename DataT>
 510 Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
 511     AsmPrinter *Asm, const AccelTableBase &Contents,
 512     ArrayRef<MCSymbol *> CompUnits,
 513     llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry)
 514     : AccelTableWriter(Asm, Contents, false),
 515       Header(CompUnits.size(), Contents.getBucketCount(),
 516              Contents.getUniqueNameCount()),
 517       CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
 518   DenseSet<uint32_t> UniqueTags = getUniqueTags();
 519   SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
 520
 521   Abbreviations.reserve(UniqueTags.size());
 522   for (uint32_t Tag : UniqueTags)
 523     Abbreviations.try_emplace(Tag, UniformAttributes);
 524 }
 525
 526 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() {
 527   Header.emit(*this);
 528   emitCUList();
 529   emitBuckets();
 530   emitHashes();
 531   emitStringOffsets();
 532   emitOffsets(EntryPool);
 533   emitAbbrevs();
 534   emitData();
 535   Asm->OutStreamer->emitValueToAlignment(4, 0);
 536   Asm->OutStreamer->emitLabel(ContributionEnd);
 537 }
 538
 539 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
 540                                    StringRef Prefix, const MCSymbol *SecBegin,
 541                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
 542   Contents.finalize(Asm, Prefix);
 543   AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
 544 }
 545
 546 void llvm::emitDWARF5AccelTable(
 547     AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
 548     const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
 549   std::vector<MCSymbol *> CompUnits;
 550   SmallVector<unsigned, 1> CUIndex(CUs.size());
 551   int Count = 0;
 552   for (const auto &CU : enumerate(CUs)) {
 553     if (CU.value()->getCUNode()->getNameTableKind() !=
 554         DICompileUnit::DebugNameTableKind::Default)
 555       continue;
 556     CUIndex[CU.index()] = Count++;
 557     assert(CU.index() == CU.value()->getUniqueID());
 558     const DwarfCompileUnit *MainCU =
 559         DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
 560     CompUnits.push_back(MainCU->getLabelBegin());
 561   }
 562
 563   if (CompUnits.empty())
 564     return;
 565
 566   Asm->OutStreamer->SwitchSection(
 567       Asm->getObjFileLowering().getDwarfDebugNamesSection());
 568
 569   Contents.finalize(Asm, "names");
 570   Dwarf5AccelTableWriter<DWARF5AccelTableData>(
 571       Asm, Contents, CompUnits,
 572       [&](const DWARF5AccelTableData &Entry) {
 573         const DIE *CUDie = Entry.getDie().getUnitDie();
 574         return CUIndex[DD.lookupCU(CUDie)->getUniqueID()];
 575       })
 576       .emit();
 577 }
 578
 579 void llvm::emitDWARF5AccelTable(
 580     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
 581     ArrayRef<MCSymbol *> CUs,
 582     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
 583         getCUIndexForEntry) {
 584   Contents.finalize(Asm, "names");
 585   Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
 586                                                      getCUIndexForEntry)
 587       .emit();
 588 }
 589
 590 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
 591   assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
 592          "The section offset exceeds the limit.");
 593   Asm->emitInt32(Die.getDebugSectionOffset());
 594 }
 595
 596 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
 597   assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
 598          "The section offset exceeds the limit.");
 599   Asm->emitInt32(Die.getDebugSectionOffset());
 600   Asm->emitInt16(Die.getTag());
 601   Asm->emitInt8(0);
 602 }
 603
 604 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
 605   Asm->emitInt32(Offset);
 606 }
 607
 608 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
 609   Asm->emitInt32(Offset);
 610   Asm->emitInt16(Tag);
 611   Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
 612                                           : 0);
 613   Asm->emitInt32(QualifiedNameHash);
 614 }
 615
 616 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
 617 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
 618 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
 619 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
 620
 621 #ifndef NDEBUG
 622 void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
 623   OS << "Magic: " << format("0x%x", Magic) << "\n"
 624      << "Version: " << Version << "\n"
 625      << "Hash Function: " << HashFunction << "\n"
 626      << "Bucket Count: " << BucketCount << "\n"
 627      << "Header Data Length: " << HeaderDataLength << "\n";
 628 }
 629
 630 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
 631   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
 632      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
 633 }
 634
 635 void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
 636   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
 637   for (auto Atom : Atoms)
 638     Atom.print(OS);
 639 }
 640
 641 void AppleAccelTableWriter::print(raw_ostream &OS) const {
 642   Header.print(OS);
 643   HeaderData.print(OS);
 644   Contents.print(OS);
 645   SecBegin->print(OS, nullptr);
 646 }
 647
 648 void AccelTableBase::HashData::print(raw_ostream &OS) const {
 649   OS << "Name: " << Name.getString() << "\n";
 650   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
 651   OS << "  Symbol: ";
 652   if (Sym)
 653     OS << *Sym;
 654   else
 655     OS << "<none>";
 656   OS << "\n";
 657   for (auto *Value : Values)
 658     Value->print(OS);
 659 }
 660
 661 void AccelTableBase::print(raw_ostream &OS) const {
 662   // Print Content.
 663   OS << "Entries: \n";
 664   for (const auto &Entry : Entries) {
 665     OS << "Name: " << Entry.first() << "\n";
 666     for (auto *V : Entry.second.Values)
 667       V->print(OS);
 668   }
 669
 670   OS << "Buckets and Hashes: \n";
 671   for (auto &Bucket : Buckets)
 672     for (auto &Hash : Bucket)
 673       Hash->print(OS);
 674
 675   OS << "Data: \n";
 676   for (auto &E : Entries)
 677     E.second.print(OS);
 678 }
 679
 680 void DWARF5AccelTableData::print(raw_ostream &OS) const {
 681   OS << "  Offset: " << getDieOffset() << "\n";
 682   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 683 }
 684
 685 void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
 686   OS << "  Offset: " << getDieOffset() << "\n";
 687   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 688 }
 689
 690 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
 691   OS << "  Offset: " << Die.getOffset() << "\n";
 692 }
 693
 694 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
 695   OS << "  Offset: " << Die.getOffset() << "\n";
 696   OS << "  Tag: " << dwarf::TagString(Die.getTag()) << "\n";
 697 }
 698
 699 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
 700   OS << "  Static Offset: " << Offset << "\n";
 701 }
 702
 703 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
 704   OS << "  Static Offset: " << Offset << "\n";
 705   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
 706   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
 707   OS << "  ObjCClassIsImplementation: "
 708      << (ObjCClassIsImplementation ? "true" : "false");
 709   OS << "\n";
 710 }
 711 #endif