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     std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
  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     std::stable_sort(Bucket.begin(), Bucket.end(),
  85                      [](HashData *LHS, HashData *RHS) {
  86                        return LHS->HashValue < RHS->HashValue;
  87                      });
  88 }
  89
  90 namespace {
  91 /// Base class for writing out Accelerator tables. It holds the common
  92 /// functionality for the two Accelerator table types.
  93 class AccelTableWriter {
  94 protected:
  95   AsmPrinter *const Asm;          ///< Destination.
  96   const AccelTableBase &Contents; ///< Data to emit.
  97
  98   /// Controls whether to emit duplicate hash and offset table entries for names
  99   /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
 100   /// tables do.
 101   const bool SkipIdenticalHashes;
 102
 103   void emitHashes() const;
 104
 105   /// Emit offsets to lists of entries with identical names. The offsets are
 106   /// relative to the Base argument.
 107   void emitOffsets(const MCSymbol *Base) const;
 108
 109 public:
 110   AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
 111                    bool SkipIdenticalHashes)
 112       : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
 113   }
 114 };
 115
 116 class AppleAccelTableWriter : public AccelTableWriter {
 117   using Atom = AppleAccelTableData::Atom;
 118
 119   /// The fixed header of an Apple Accelerator Table.
 120   struct Header {
 121     uint32_t Magic = MagicHash;
 122     uint16_t Version = 1;
 123     uint16_t HashFunction = dwarf::DW_hash_function_djb;
 124     uint32_t BucketCount;
 125     uint32_t HashCount;
 126     uint32_t HeaderDataLength;
 127
 128     /// 'HASH' magic value to detect endianness.
 129     static const uint32_t MagicHash = 0x48415348;
 130
 131     Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
 132         : BucketCount(BucketCount), HashCount(UniqueHashCount),
 133           HeaderDataLength(DataLength) {}
 134
 135     void emit(AsmPrinter *Asm) const;
 136 #ifndef NDEBUG
 137     void print(raw_ostream &OS) const;
 138     void dump() const { print(dbgs()); }
 139 #endif
 140   };
 141
 142   /// The HeaderData describes the structure of an Apple accelerator table
 143   /// through a list of Atoms.
 144   struct HeaderData {
 145     /// In the case of data that is referenced via DW_FORM_ref_* the offset
 146     /// base is used to describe the offset for all forms in the list of atoms.
 147     uint32_t DieOffsetBase;
 148
 149     const SmallVector<Atom, 4> Atoms;
 150
 151     HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
 152         : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
 153
 154     void emit(AsmPrinter *Asm) const;
 155 #ifndef NDEBUG
 156     void print(raw_ostream &OS) const;
 157     void dump() const { print(dbgs()); }
 158 #endif
 159   };
 160
 161   Header Header;
 162   HeaderData HeaderData;
 163   const MCSymbol *SecBegin;
 164
 165   void emitBuckets() const;
 166   void emitData() const;
 167
 168 public:
 169   AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
 170                         ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
 171       : AccelTableWriter(Asm, Contents, true),
 172         Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
 173                8 + (Atoms.size() * 4)),
 174         HeaderData(Atoms), SecBegin(SecBegin) {}
 175
 176   void emit() const;
 177
 178 #ifndef NDEBUG
 179   void print(raw_ostream &OS) const;
 180   void dump() const { print(dbgs()); }
 181 #endif
 182 };
 183
 184 /// Class responsible for emitting a DWARF v5 Accelerator Table. The only
 185 /// public function is emit(), which performs the actual emission.
 186 ///
 187 /// The class is templated in its data type. This allows us to emit both dyamic
 188 /// and static data entries. A callback abstract the logic to provide a CU
 189 /// index for a given entry, which is different per data type, but identical
 190 /// for every entry in the same table.
 191 template <typename DataT>
 192 class Dwarf5AccelTableWriter : public AccelTableWriter {
 193   struct Header {
 194     uint32_t UnitLength = 0;
 195     uint16_t Version = 5;
 196     uint16_t Padding = 0;
 197     uint32_t CompUnitCount;
 198     uint32_t LocalTypeUnitCount = 0;
 199     uint32_t ForeignTypeUnitCount = 0;
 200     uint32_t BucketCount;
 201     uint32_t NameCount;
 202     uint32_t AbbrevTableSize = 0;
 203     uint32_t AugmentationStringSize = sizeof(AugmentationString);
 204     char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
 205
 206     Header(uint32_t CompUnitCount, uint32_t BucketCount, uint32_t NameCount)
 207         : CompUnitCount(CompUnitCount), BucketCount(BucketCount),
 208           NameCount(NameCount) {}
 209
 210     void emit(const Dwarf5AccelTableWriter &Ctx) const;
 211   };
 212   struct AttributeEncoding {
 213     dwarf::Index Index;
 214     dwarf::Form Form;
 215   };
 216
 217   Header Header;
 218   DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
 219   ArrayRef<MCSymbol *> CompUnits;
 220   llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry;
 221   MCSymbol *ContributionStart = Asm->createTempSymbol("names_start");
 222   MCSymbol *ContributionEnd = Asm->createTempSymbol("names_end");
 223   MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
 224   MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
 225   MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
 226
 227   DenseSet<uint32_t> getUniqueTags() const;
 228
 229   // Right now, we emit uniform attributes for all tags.
 230   SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
 231
 232   void emitCUList() const;
 233   void emitBuckets() const;
 234   void emitStringOffsets() const;
 235   void emitAbbrevs() const;
 236   void emitEntry(const DataT &Entry) const;
 237   void emitData() const;
 238
 239 public:
 240   Dwarf5AccelTableWriter(
 241       AsmPrinter *Asm, const AccelTableBase &Contents,
 242       ArrayRef<MCSymbol *> CompUnits,
 243       llvm::function_ref<unsigned(const DataT &)> GetCUIndexForEntry);
 244
 245   void emit() const;
 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 (auto &Bucket : Contents.getBuckets()) {
 253     for (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, sizeof(uint32_t));
 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 (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 333     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 334     for (auto &Hash : Buckets[i]) {
 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->Values)
 347         static_cast<const AppleAccelTableData *>(V)->emit(Asm);
 348       PrevHash = Hash->HashValue;
 349     }
 350     // Emit the final end marker for the bucket.
 351     if (!Buckets[i].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 template <typename DataT>
 366 void Dwarf5AccelTableWriter<DataT>::Header::emit(
 367     const Dwarf5AccelTableWriter &Ctx) const {
 368   assert(CompUnitCount > 0 && "Index must have at least one CU.");
 369
 370   AsmPrinter *Asm = Ctx.Asm;
 371   Asm->OutStreamer->AddComment("Header: unit length");
 372   Asm->EmitLabelDifference(Ctx.ContributionEnd, Ctx.ContributionStart,
 373                            sizeof(uint32_t));
 374   Asm->OutStreamer->EmitLabel(Ctx.ContributionStart);
 375   Asm->OutStreamer->AddComment("Header: version");
 376   Asm->emitInt16(Version);
 377   Asm->OutStreamer->AddComment("Header: padding");
 378   Asm->emitInt16(Padding);
 379   Asm->OutStreamer->AddComment("Header: compilation unit count");
 380   Asm->emitInt32(CompUnitCount);
 381   Asm->OutStreamer->AddComment("Header: local type unit count");
 382   Asm->emitInt32(LocalTypeUnitCount);
 383   Asm->OutStreamer->AddComment("Header: foreign type unit count");
 384   Asm->emitInt32(ForeignTypeUnitCount);
 385   Asm->OutStreamer->AddComment("Header: bucket count");
 386   Asm->emitInt32(BucketCount);
 387   Asm->OutStreamer->AddComment("Header: name count");
 388   Asm->emitInt32(NameCount);
 389   Asm->OutStreamer->AddComment("Header: abbreviation table size");
 390   Asm->EmitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
 391   Asm->OutStreamer->AddComment("Header: augmentation string size");
 392   assert(AugmentationStringSize % 4 == 0);
 393   Asm->emitInt32(AugmentationStringSize);
 394   Asm->OutStreamer->AddComment("Header: augmentation string");
 395   Asm->OutStreamer->EmitBytes({AugmentationString, AugmentationStringSize});
 396 }
 397
 398 template <typename DataT>
 399 DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
 400   DenseSet<uint32_t> UniqueTags;
 401   for (auto &Bucket : Contents.getBuckets()) {
 402     for (auto *Hash : Bucket) {
 403       for (auto *Value : Hash->Values) {
 404         unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
 405         UniqueTags.insert(Tag);
 406       }
 407     }
 408   }
 409   return UniqueTags;
 410 }
 411
 412 template <typename DataT>
 413 SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
 414 Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
 415   SmallVector<AttributeEncoding, 2> UA;
 416   if (CompUnits.size() > 1) {
 417     size_t LargestCUIndex = CompUnits.size() - 1;
 418     dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
 419     UA.push_back({dwarf::DW_IDX_compile_unit, Form});
 420   }
 421   UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
 422   return UA;
 423 }
 424
 425 template <typename DataT>
 426 void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
 427   for (const auto &CU : enumerate(CompUnits)) {
 428     Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
 429     Asm->emitDwarfSymbolReference(CU.value());
 430   }
 431 }
 432
 433 template <typename DataT>
 434 void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
 435   uint32_t Index = 1;
 436   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 437     Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
 438     Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
 439     Index += Bucket.value().size();
 440   }
 441 }
 442
 443 template <typename DataT>
 444 void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
 445   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 446     for (auto *Hash : Bucket.value()) {
 447       DwarfStringPoolEntryRef String = Hash->Name;
 448       Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
 449                                    ": " + String.getString());
 450       Asm->emitDwarfStringOffset(String);
 451     }
 452   }
 453 }
 454
 455 template <typename DataT>
 456 void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
 457   Asm->OutStreamer->EmitLabel(AbbrevStart);
 458   for (const auto &Abbrev : Abbreviations) {
 459     Asm->OutStreamer->AddComment("Abbrev code");
 460     assert(Abbrev.first != 0);
 461     Asm->EmitULEB128(Abbrev.first);
 462     Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
 463     Asm->EmitULEB128(Abbrev.first);
 464     for (const auto &AttrEnc : Abbrev.second) {
 465       Asm->EmitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
 466       Asm->EmitULEB128(AttrEnc.Form,
 467                        dwarf::FormEncodingString(AttrEnc.Form).data());
 468     }
 469     Asm->EmitULEB128(0, "End of abbrev");
 470     Asm->EmitULEB128(0, "End of abbrev");
 471   }
 472   Asm->EmitULEB128(0, "End of abbrev list");
 473   Asm->OutStreamer->EmitLabel(AbbrevEnd);
 474 }
 475
 476 template <typename DataT>
 477 void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
 478   auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
 479   assert(AbbrevIt != Abbreviations.end() &&
 480          "Why wasn't this abbrev generated?");
 481
 482   Asm->EmitULEB128(AbbrevIt->first, "Abbreviation code");
 483   for (const auto &AttrEnc : AbbrevIt->second) {
 484     Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
 485     switch (AttrEnc.Index) {
 486     case dwarf::DW_IDX_compile_unit: {
 487       DIEInteger ID(getCUIndexForEntry(Entry));
 488       ID.EmitValue(Asm, AttrEnc.Form);
 489       break;
 490     }
 491     case dwarf::DW_IDX_die_offset:
 492       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
 493       Asm->emitInt32(Entry.getDieOffset());
 494       break;
 495     default:
 496       llvm_unreachable("Unexpected index attribute!");
 497     }
 498   }
 499 }
 500
 501 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
 502   Asm->OutStreamer->EmitLabel(EntryPool);
 503   for (auto &Bucket : Contents.getBuckets()) {
 504     for (auto *Hash : Bucket) {
 505       // Remember to emit the label for our offset.
 506       Asm->OutStreamer->EmitLabel(Hash->Sym);
 507       for (const auto *Value : Hash->Values)
 508         emitEntry(*static_cast<const DataT *>(Value));
 509       Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
 510       Asm->emitInt32(0);
 511     }
 512   }
 513 }
 514
 515 template <typename DataT>
 516 Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
 517     AsmPrinter *Asm, const AccelTableBase &Contents,
 518     ArrayRef<MCSymbol *> CompUnits,
 519     llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry)
 520     : AccelTableWriter(Asm, Contents, false),
 521       Header(CompUnits.size(), Contents.getBucketCount(),
 522              Contents.getUniqueNameCount()),
 523       CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
 524   DenseSet<uint32_t> UniqueTags = getUniqueTags();
 525   SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
 526
 527   Abbreviations.reserve(UniqueTags.size());
 528   for (uint32_t Tag : UniqueTags)
 529     Abbreviations.try_emplace(Tag, UniformAttributes);
 530 }
 531
 532 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() const {
 533   Header.emit(*this);
 534   emitCUList();
 535   emitBuckets();
 536   emitHashes();
 537   emitStringOffsets();
 538   emitOffsets(EntryPool);
 539   emitAbbrevs();
 540   emitData();
 541   Asm->OutStreamer->EmitValueToAlignment(4, 0);
 542   Asm->OutStreamer->EmitLabel(ContributionEnd);
 543 }
 544
 545 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
 546                                    StringRef Prefix, const MCSymbol *SecBegin,
 547                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
 548   Contents.finalize(Asm, Prefix);
 549   AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
 550 }
 551
 552 void llvm::emitDWARF5AccelTable(
 553     AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
 554     const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
 555   std::vector<MCSymbol *> CompUnits;
 556   SmallVector<unsigned, 1> CUIndex(CUs.size());
 557   int Count = 0;
 558   for (const auto &CU : enumerate(CUs)) {
 559     if (CU.value()->getCUNode()->getNameTableKind() ==
 560         DICompileUnit::DebugNameTableKind::None)
 561       continue;
 562     CUIndex[CU.index()] = Count++;
 563     assert(CU.index() == CU.value()->getUniqueID());
 564     const DwarfCompileUnit *MainCU =
 565         DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
 566     CompUnits.push_back(MainCU->getLabelBegin());
 567   }
 568
 569   if (CompUnits.empty())
 570     return;
 571
 572   Asm->OutStreamer->SwitchSection(
 573       Asm->getObjFileLowering().getDwarfDebugNamesSection());
 574
 575   Contents.finalize(Asm, "names");
 576   Dwarf5AccelTableWriter<DWARF5AccelTableData>(
 577       Asm, Contents, CompUnits,
 578       [&](const DWARF5AccelTableData &Entry) {
 579         const DIE *CUDie = Entry.getDie().getUnitDie();
 580         return CUIndex[DD.lookupCU(CUDie)->getUniqueID()];
 581       })
 582       .emit();
 583 }
 584
 585 void llvm::emitDWARF5AccelTable(
 586     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
 587     ArrayRef<MCSymbol *> CUs,
 588     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
 589         getCUIndexForEntry) {
 590   Contents.finalize(Asm, "names");
 591   Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
 592                                                      getCUIndexForEntry)
 593       .emit();
 594 }
 595
 596 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
 597   Asm->emitInt32(Die.getDebugSectionOffset());
 598 }
 599
 600 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
 601   Asm->emitInt32(Die.getDebugSectionOffset());
 602   Asm->emitInt16(Die.getTag());
 603   Asm->emitInt8(0);
 604 }
 605
 606 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
 607   Asm->emitInt32(Offset);
 608 }
 609
 610 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
 611   Asm->emitInt32(Offset);
 612   Asm->emitInt16(Tag);
 613   Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
 614                                           : 0);
 615   Asm->emitInt32(QualifiedNameHash);
 616 }
 617
 618 #ifndef _MSC_VER
 619 // The lines below are rejected by older versions (TBD) of MSVC.
 620 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
 621 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
 622 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
 623 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
 624 #else
 625 // FIXME: Erase this path once the minimum MSCV version has been bumped.
 626 const SmallVector<AppleAccelTableData::Atom, 4>
 627     AppleAccelTableOffsetData::Atoms = {
 628         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 629 const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms =
 630     {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 631      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 632      Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
 633 const SmallVector<AppleAccelTableData::Atom, 4>
 634     AppleAccelTableStaticOffsetData::Atoms = {
 635         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 636 const SmallVector<AppleAccelTableData::Atom, 4>
 637     AppleAccelTableStaticTypeData::Atoms = {
 638         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 639         Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 640         Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
 641 #endif
 642
 643 #ifndef NDEBUG
 644 void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
 645   OS << "Magic: " << format("0x%x", Magic) << "\n"
 646      << "Version: " << Version << "\n"
 647      << "Hash Function: " << HashFunction << "\n"
 648      << "Bucket Count: " << BucketCount << "\n"
 649      << "Header Data Length: " << HeaderDataLength << "\n";
 650 }
 651
 652 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
 653   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
 654      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
 655 }
 656
 657 void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
 658   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
 659   for (auto Atom : Atoms)
 660     Atom.print(OS);
 661 }
 662
 663 void AppleAccelTableWriter::print(raw_ostream &OS) const {
 664   Header.print(OS);
 665   HeaderData.print(OS);
 666   Contents.print(OS);
 667   SecBegin->print(OS, nullptr);
 668 }
 669
 670 void AccelTableBase::HashData::print(raw_ostream &OS) const {
 671   OS << "Name: " << Name.getString() << "\n";
 672   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
 673   OS << "  Symbol: ";
 674   if (Sym)
 675     OS << *Sym;
 676   else
 677     OS << "<none>";
 678   OS << "\n";
 679   for (auto *Value : Values)
 680     Value->print(OS);
 681 }
 682
 683 void AccelTableBase::print(raw_ostream &OS) const {
 684   // Print Content.
 685   OS << "Entries: \n";
 686   for (const auto &Entry : Entries) {
 687     OS << "Name: " << Entry.first() << "\n";
 688     for (auto *V : Entry.second.Values)
 689       V->print(OS);
 690   }
 691
 692   OS << "Buckets and Hashes: \n";
 693   for (auto &Bucket : Buckets)
 694     for (auto &Hash : Bucket)
 695       Hash->print(OS);
 696
 697   OS << "Data: \n";
 698   for (auto &E : Entries)
 699     E.second.print(OS);
 700 }
 701
 702 void DWARF5AccelTableData::print(raw_ostream &OS) const {
 703   OS << "  Offset: " << getDieOffset() << "\n";
 704   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 705 }
 706
 707 void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
 708   OS << "  Offset: " << getDieOffset() << "\n";
 709   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 710 }
 711
 712 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
 713   OS << "  Offset: " << Die.getOffset() << "\n";
 714 }
 715
 716 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
 717   OS << "  Offset: " << Die.getOffset() << "\n";
 718   OS << "  Tag: " << dwarf::TagString(Die.getTag()) << "\n";
 719 }
 720
 721 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
 722   OS << "  Static Offset: " << Offset << "\n";
 723 }
 724
 725 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
 726   OS << "  Static Offset: " << Offset << "\n";
 727   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
 728   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
 729   OS << "  ObjCClassIsImplementation: "
 730      << (ObjCClassIsImplementation ? "true" : "false");
 731   OS << "\n";
 732 }
 733 #endif