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