lib/CodeGen/AsmPrinter/AccelTable.cpp

   1 //===- llvm/CodeGen/AsmPrinter/AccelTable.cpp - Accelerator Tables --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains support for writing accelerator tables.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/AccelTable.h"
  15 #include "DwarfCompileUnit.h"
  16 #include "llvm/ADT/STLExtras.h"
  17 #include "llvm/ADT/StringMap.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/MCExpr.h"
  23 #include "llvm/MC/MCStreamer.h"
  24 #include "llvm/MC/MCSymbol.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/Target/TargetLoweringObjectFile.h"
  27 #include <algorithm>
  28 #include <cstddef>
  29 #include <cstdint>
  30 #include <limits>
  31 #include <vector>
  32
  33 using namespace llvm;
  34
  35 void AccelTableBase::computeBucketCount() {
  36   // First get the number of unique hashes.
  37   std::vector<uint32_t> Uniques;
  38   Uniques.reserve(Entries.size());
  39   for (const auto &E : Entries)
  40     Uniques.push_back(E.second.HashValue);
  41   array_pod_sort(Uniques.begin(), Uniques.end());
  42   std::vector<uint32_t>::iterator P =
  43       std::unique(Uniques.begin(), Uniques.end());
  44
  45   UniqueHashCount = std::distance(Uniques.begin(), P);
  46
  47   if (UniqueHashCount > 1024)
  48     BucketCount = UniqueHashCount / 4;
  49   else if (UniqueHashCount > 16)
  50     BucketCount = UniqueHashCount / 2;
  51   else
  52     BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
  53 }
  54
  55 void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
  56   // Create the individual hash data outputs.
  57   for (auto &E : Entries) {
  58     // Unique the entries.
  59     std::stable_sort(E.second.Values.begin(), E.second.Values.end(),
  60                      [](const AccelTableData *A, const AccelTableData *B) {
  61                        return *A < *B;
  62                      });
  63     E.second.Values.erase(
  64         std::unique(E.second.Values.begin(), E.second.Values.end()),
  65         E.second.Values.end());
  66   }
  67
  68   // Figure out how many buckets we need, then compute the bucket contents and
  69   // the final ordering. The hashes and offsets can be emitted by walking these
  70   // data structures. We add temporary symbols to the data so they can be
  71   // referenced when emitting the offsets.
  72   computeBucketCount();
  73
  74   // Compute bucket contents and final ordering.
  75   Buckets.resize(BucketCount);
  76   for (auto &E : Entries) {
  77     uint32_t Bucket = E.second.HashValue % BucketCount;
  78     Buckets[Bucket].push_back(&E.second);
  79     E.second.Sym = Asm->createTempSymbol(Prefix);
  80   }
  81
  82   // Sort the contents of the buckets by hash value so that hash collisions end
  83   // up together. Stable sort makes testing easier and doesn't cost much more.
  84   for (auto &Bucket : Buckets)
  85     std::stable_sort(Bucket.begin(), Bucket.end(),
  86                      [](HashData *LHS, HashData *RHS) {
  87                        return LHS->HashValue < RHS->HashValue;
  88                      });
  89 }
  90
  91 namespace {
  92 /// Base class for writing out Accelerator tables. It holds the common
  93 /// functionality for the two Accelerator table types.
  94 class AccelTableWriter {
  95 protected:
  96   AsmPrinter *const Asm;          ///< Destination.
  97   const AccelTableBase &Contents; ///< Data to emit.
  98
  99   /// Controls whether to emit duplicate hash and offset table entries for names
 100   /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
 101   /// tables do.
 102   const bool SkipIdenticalHashes;
 103
 104   void emitHashes() const;
 105
 106   /// Emit offsets to lists of entries with identical names. The offsets are
 107   /// relative to the Base argument.
 108   void emitOffsets(const MCSymbol *Base) const;
 109
 110 public:
 111   AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
 112                    bool SkipIdenticalHashes)
 113       : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
 114   }
 115 };
 116
 117 class AppleAccelTableWriter : public AccelTableWriter {
 118   using Atom = AppleAccelTableData::Atom;
 119
 120   /// The fixed header of an Apple Accelerator Table.
 121   struct Header {
 122     uint32_t Magic = MagicHash;
 123     uint16_t Version = 1;
 124     uint16_t HashFunction = dwarf::DW_hash_function_djb;
 125     uint32_t BucketCount;
 126     uint32_t HashCount;
 127     uint32_t HeaderDataLength;
 128
 129     /// 'HASH' magic value to detect endianness.
 130     static const uint32_t MagicHash = 0x48415348;
 131
 132     Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
 133         : BucketCount(BucketCount), HashCount(UniqueHashCount),
 134           HeaderDataLength(DataLength) {}
 135
 136     void emit(AsmPrinter *Asm) const;
 137 #ifndef NDEBUG
 138     void print(raw_ostream &OS) const;
 139     void dump() const { print(dbgs()); }
 140 #endif
 141   };
 142
 143   /// The HeaderData describes the structure of an Apple accelerator table
 144   /// through a list of Atoms.
 145   struct HeaderData {
 146     /// In the case of data that is referenced via DW_FORM_ref_* the offset
 147     /// base is used to describe the offset for all forms in the list of atoms.
 148     uint32_t DieOffsetBase;
 149
 150     const SmallVector<Atom, 4> Atoms;
 151
 152     HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
 153         : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
 154
 155     void emit(AsmPrinter *Asm) const;
 156 #ifndef NDEBUG
 157     void print(raw_ostream &OS) const;
 158     void dump() const { print(dbgs()); }
 159 #endif
 160   };
 161
 162   Header Header;
 163   HeaderData HeaderData;
 164   const MCSymbol *SecBegin;
 165
 166   void emitBuckets() const;
 167   void emitData() const;
 168
 169 public:
 170   AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
 171                         ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
 172       : AccelTableWriter(Asm, Contents, true),
 173         Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
 174                8 + (Atoms.size() * 4)),
 175         HeaderData(Atoms), SecBegin(SecBegin) {}
 176
 177   void emit() const;
 178
 179 #ifndef NDEBUG
 180   void print(raw_ostream &OS) const;
 181   void dump() const { print(dbgs()); }
 182 #endif
 183 };
 184
 185 /// Class responsible for emitting a DWARF v5 Accelerator Table. The only
 186 /// public function is emit(), which performs the actual emission.
 187 ///
 188 /// The class is templated in its data type. This allows us to emit both dyamic
 189 /// and static data entries. A callback abstract the logic to provide a CU
 190 /// index for a given entry, which is different per data type, but identical
 191 /// for every entry in the same table.
 192 template <typename DataT>
 193 class Dwarf5AccelTableWriter : public AccelTableWriter {
 194   struct Header {
 195     uint32_t UnitLength = 0;
 196     uint16_t Version = 5;
 197     uint16_t Padding = 0;
 198     uint32_t CompUnitCount;
 199     uint32_t LocalTypeUnitCount = 0;
 200     uint32_t ForeignTypeUnitCount = 0;
 201     uint32_t BucketCount;
 202     uint32_t NameCount;
 203     uint32_t AbbrevTableSize = 0;
 204     uint32_t AugmentationStringSize = sizeof(AugmentationString);
 205     char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
 206
 207     Header(uint32_t CompUnitCount, uint32_t BucketCount, uint32_t NameCount)
 208         : CompUnitCount(CompUnitCount), BucketCount(BucketCount),
 209           NameCount(NameCount) {}
 210
 211     void emit(const Dwarf5AccelTableWriter &Ctx) const;
 212   };
 213   struct AttributeEncoding {
 214     dwarf::Index Index;
 215     dwarf::Form Form;
 216   };
 217
 218   Header Header;
 219   DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
 220   ArrayRef<MCSymbol *> CompUnits;
 221   llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry;
 222   MCSymbol *ContributionStart = Asm->createTempSymbol("names_start");
 223   MCSymbol *ContributionEnd = Asm->createTempSymbol("names_end");
 224   MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
 225   MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
 226   MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
 227
 228   DenseSet<uint32_t> getUniqueTags() const;
 229
 230   // Right now, we emit uniform attributes for all tags.
 231   SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
 232
 233   void emitCUList() const;
 234   void emitBuckets() const;
 235   void emitStringOffsets() const;
 236   void emitAbbrevs() const;
 237   void emitEntry(const DataT &Entry) const;
 238   void emitData() const;
 239
 240 public:
 241   Dwarf5AccelTableWriter(
 242       AsmPrinter *Asm, const AccelTableBase &Contents,
 243       ArrayRef<MCSymbol *> CompUnits,
 244       llvm::function_ref<unsigned(const DataT &)> GetCUIndexForEntry);
 245
 246   void emit() const;
 247 };
 248 } // namespace
 249
 250 void AccelTableWriter::emitHashes() const {
 251   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 252   unsigned BucketIdx = 0;
 253   for (auto &Bucket : Contents.getBuckets()) {
 254     for (auto &Hash : Bucket) {
 255       uint32_t HashValue = Hash->HashValue;
 256       if (SkipIdenticalHashes && PrevHash == HashValue)
 257         continue;
 258       Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
 259       Asm->emitInt32(HashValue);
 260       PrevHash = HashValue;
 261     }
 262     BucketIdx++;
 263   }
 264 }
 265
 266 void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
 267   const auto &Buckets = Contents.getBuckets();
 268   uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 269   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 270     for (auto *Hash : Buckets[i]) {
 271       uint32_t HashValue = Hash->HashValue;
 272       if (SkipIdenticalHashes && PrevHash == HashValue)
 273         continue;
 274       PrevHash = HashValue;
 275       Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
 276       Asm->EmitLabelDifference(Hash->Sym, Base, sizeof(uint32_t));
 277     }
 278   }
 279 }
 280
 281 void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
 282   Asm->OutStreamer->AddComment("Header Magic");
 283   Asm->emitInt32(Magic);
 284   Asm->OutStreamer->AddComment("Header Version");
 285   Asm->emitInt16(Version);
 286   Asm->OutStreamer->AddComment("Header Hash Function");
 287   Asm->emitInt16(HashFunction);
 288   Asm->OutStreamer->AddComment("Header Bucket Count");
 289   Asm->emitInt32(BucketCount);
 290   Asm->OutStreamer->AddComment("Header Hash Count");
 291   Asm->emitInt32(HashCount);
 292   Asm->OutStreamer->AddComment("Header Data Length");
 293   Asm->emitInt32(HeaderDataLength);
 294 }
 295
 296 void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
 297   Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
 298   Asm->emitInt32(DieOffsetBase);
 299   Asm->OutStreamer->AddComment("HeaderData Atom Count");
 300   Asm->emitInt32(Atoms.size());
 301
 302   for (const Atom &A : Atoms) {
 303     Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
 304     Asm->emitInt16(A.Type);
 305     Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
 306     Asm->emitInt16(A.Form);
 307   }
 308 }
 309
 310 void AppleAccelTableWriter::emitBuckets() const {
 311   const auto &Buckets = Contents.getBuckets();
 312   unsigned index = 0;
 313   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 314     Asm->OutStreamer->AddComment("Bucket " + Twine(i));
 315     if (!Buckets[i].empty())
 316       Asm->emitInt32(index);
 317     else
 318       Asm->emitInt32(std::numeric_limits<uint32_t>::max());
 319     // Buckets point in the list of hashes, not to the data. Do not increment
 320     // the index multiple times in case of hash collisions.
 321     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 322     for (auto *HD : Buckets[i]) {
 323       uint32_t HashValue = HD->HashValue;
 324       if (PrevHash != HashValue)
 325         ++index;
 326       PrevHash = HashValue;
 327     }
 328   }
 329 }
 330
 331 void AppleAccelTableWriter::emitData() const {
 332   const auto &Buckets = Contents.getBuckets();
 333   for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
 334     uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
 335     for (auto &Hash : Buckets[i]) {
 336       // Terminate the previous entry if there is no hash collision with the
 337       // current one.
 338       if (PrevHash != std::numeric_limits<uint64_t>::max() &&
 339           PrevHash != Hash->HashValue)
 340         Asm->emitInt32(0);
 341       // Remember to emit the label for our offset.
 342       Asm->OutStreamer->EmitLabel(Hash->Sym);
 343       Asm->OutStreamer->AddComment(Hash->Name.getString());
 344       Asm->emitDwarfStringOffset(Hash->Name);
 345       Asm->OutStreamer->AddComment("Num DIEs");
 346       Asm->emitInt32(Hash->Values.size());
 347       for (const auto *V : Hash->Values)
 348         static_cast<const AppleAccelTableData *>(V)->emit(Asm);
 349       PrevHash = Hash->HashValue;
 350     }
 351     // Emit the final end marker for the bucket.
 352     if (!Buckets[i].empty())
 353       Asm->emitInt32(0);
 354   }
 355 }
 356
 357 void AppleAccelTableWriter::emit() const {
 358   Header.emit(Asm);
 359   HeaderData.emit(Asm);
 360   emitBuckets();
 361   emitHashes();
 362   emitOffsets(SecBegin);
 363   emitData();
 364 }
 365
 366 template <typename DataT>
 367 void Dwarf5AccelTableWriter<DataT>::Header::emit(
 368     const Dwarf5AccelTableWriter &Ctx) const {
 369   assert(CompUnitCount > 0 && "Index must have at least one CU.");
 370
 371   AsmPrinter *Asm = Ctx.Asm;
 372   Asm->OutStreamer->AddComment("Header: unit length");
 373   Asm->EmitLabelDifference(Ctx.ContributionEnd, Ctx.ContributionStart,
 374                            sizeof(uint32_t));
 375   Asm->OutStreamer->EmitLabel(Ctx.ContributionStart);
 376   Asm->OutStreamer->AddComment("Header: version");
 377   Asm->emitInt16(Version);
 378   Asm->OutStreamer->AddComment("Header: padding");
 379   Asm->emitInt16(Padding);
 380   Asm->OutStreamer->AddComment("Header: compilation unit count");
 381   Asm->emitInt32(CompUnitCount);
 382   Asm->OutStreamer->AddComment("Header: local type unit count");
 383   Asm->emitInt32(LocalTypeUnitCount);
 384   Asm->OutStreamer->AddComment("Header: foreign type unit count");
 385   Asm->emitInt32(ForeignTypeUnitCount);
 386   Asm->OutStreamer->AddComment("Header: bucket count");
 387   Asm->emitInt32(BucketCount);
 388   Asm->OutStreamer->AddComment("Header: name count");
 389   Asm->emitInt32(NameCount);
 390   Asm->OutStreamer->AddComment("Header: abbreviation table size");
 391   Asm->EmitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
 392   Asm->OutStreamer->AddComment("Header: augmentation string size");
 393   assert(AugmentationStringSize % 4 == 0);
 394   Asm->emitInt32(AugmentationStringSize);
 395   Asm->OutStreamer->AddComment("Header: augmentation string");
 396   Asm->OutStreamer->EmitBytes({AugmentationString, AugmentationStringSize});
 397 }
 398
 399 template <typename DataT>
 400 DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
 401   DenseSet<uint32_t> UniqueTags;
 402   for (auto &Bucket : Contents.getBuckets()) {
 403     for (auto *Hash : Bucket) {
 404       for (auto *Value : Hash->Values) {
 405         unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
 406         UniqueTags.insert(Tag);
 407       }
 408     }
 409   }
 410   return UniqueTags;
 411 }
 412
 413 template <typename DataT>
 414 SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
 415 Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
 416   SmallVector<AttributeEncoding, 2> UA;
 417   if (CompUnits.size() > 1) {
 418     size_t LargestCUIndex = CompUnits.size() - 1;
 419     dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
 420     UA.push_back({dwarf::DW_IDX_compile_unit, Form});
 421   }
 422   UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
 423   return UA;
 424 }
 425
 426 template <typename DataT>
 427 void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
 428   for (const auto &CU : enumerate(CompUnits)) {
 429     Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
 430     Asm->emitDwarfSymbolReference(CU.value());
 431   }
 432 }
 433
 434 template <typename DataT>
 435 void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
 436   uint32_t Index = 1;
 437   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 438     Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
 439     Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
 440     Index += Bucket.value().size();
 441   }
 442 }
 443
 444 template <typename DataT>
 445 void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
 446   for (const auto &Bucket : enumerate(Contents.getBuckets())) {
 447     for (auto *Hash : Bucket.value()) {
 448       DwarfStringPoolEntryRef String = Hash->Name;
 449       Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
 450                                    ": " + String.getString());
 451       Asm->emitDwarfStringOffset(String);
 452     }
 453   }
 454 }
 455
 456 template <typename DataT>
 457 void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
 458   Asm->OutStreamer->EmitLabel(AbbrevStart);
 459   for (const auto &Abbrev : Abbreviations) {
 460     Asm->OutStreamer->AddComment("Abbrev code");
 461     assert(Abbrev.first != 0);
 462     Asm->EmitULEB128(Abbrev.first);
 463     Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
 464     Asm->EmitULEB128(Abbrev.first);
 465     for (const auto &AttrEnc : Abbrev.second) {
 466       Asm->EmitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
 467       Asm->EmitULEB128(AttrEnc.Form,
 468                        dwarf::FormEncodingString(AttrEnc.Form).data());
 469     }
 470     Asm->EmitULEB128(0, "End of abbrev");
 471     Asm->EmitULEB128(0, "End of abbrev");
 472   }
 473   Asm->EmitULEB128(0, "End of abbrev list");
 474   Asm->OutStreamer->EmitLabel(AbbrevEnd);
 475 }
 476
 477 template <typename DataT>
 478 void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
 479   auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
 480   assert(AbbrevIt != Abbreviations.end() &&
 481          "Why wasn't this abbrev generated?");
 482
 483   Asm->EmitULEB128(AbbrevIt->first, "Abbreviation code");
 484   for (const auto &AttrEnc : AbbrevIt->second) {
 485     Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
 486     switch (AttrEnc.Index) {
 487     case dwarf::DW_IDX_compile_unit: {
 488       DIEInteger ID(getCUIndexForEntry(Entry));
 489       ID.EmitValue(Asm, AttrEnc.Form);
 490       break;
 491     }
 492     case dwarf::DW_IDX_die_offset:
 493       assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
 494       Asm->emitInt32(Entry.getDieOffset());
 495       break;
 496     default:
 497       llvm_unreachable("Unexpected index attribute!");
 498     }
 499   }
 500 }
 501
 502 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
 503   Asm->OutStreamer->EmitLabel(EntryPool);
 504   for (auto &Bucket : Contents.getBuckets()) {
 505     for (auto *Hash : Bucket) {
 506       // Remember to emit the label for our offset.
 507       Asm->OutStreamer->EmitLabel(Hash->Sym);
 508       for (const auto *Value : Hash->Values)
 509         emitEntry(*static_cast<const DataT *>(Value));
 510       Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
 511       Asm->emitInt32(0);
 512     }
 513   }
 514 }
 515
 516 template <typename DataT>
 517 Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
 518     AsmPrinter *Asm, const AccelTableBase &Contents,
 519     ArrayRef<MCSymbol *> CompUnits,
 520     llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry)
 521     : AccelTableWriter(Asm, Contents, false),
 522       Header(CompUnits.size(), Contents.getBucketCount(),
 523              Contents.getUniqueNameCount()),
 524       CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
 525   DenseSet<uint32_t> UniqueTags = getUniqueTags();
 526   SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
 527
 528   Abbreviations.reserve(UniqueTags.size());
 529   for (uint32_t Tag : UniqueTags)
 530     Abbreviations.try_emplace(Tag, UniformAttributes);
 531 }
 532
 533 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() const {
 534   Header.emit(*this);
 535   emitCUList();
 536   emitBuckets();
 537   emitHashes();
 538   emitStringOffsets();
 539   emitOffsets(EntryPool);
 540   emitAbbrevs();
 541   emitData();
 542   Asm->OutStreamer->EmitValueToAlignment(4, 0);
 543   Asm->OutStreamer->EmitLabel(ContributionEnd);
 544 }
 545
 546 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
 547                                    StringRef Prefix, const MCSymbol *SecBegin,
 548                                    ArrayRef<AppleAccelTableData::Atom> Atoms) {
 549   Contents.finalize(Asm, Prefix);
 550   AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
 551 }
 552
 553 void llvm::emitDWARF5AccelTable(
 554     AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
 555     const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
 556   std::vector<MCSymbol *> CompUnits;
 557   SmallVector<unsigned, 1> CUIndex(CUs.size());
 558   int Count = 0;
 559   for (const auto &CU : enumerate(CUs)) {
 560     if (CU.value()->getCUNode()->getNameTableKind() ==
 561         DICompileUnit::DebugNameTableKind::None)
 562       continue;
 563     CUIndex[CU.index()] = Count++;
 564     assert(CU.index() == CU.value()->getUniqueID());
 565     const DwarfCompileUnit *MainCU =
 566         DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
 567     CompUnits.push_back(MainCU->getLabelBegin());
 568   }
 569
 570   if (CompUnits.empty())
 571     return;
 572
 573   Asm->OutStreamer->SwitchSection(
 574       Asm->getObjFileLowering().getDwarfDebugNamesSection());
 575
 576   Contents.finalize(Asm, "names");
 577   Dwarf5AccelTableWriter<DWARF5AccelTableData>(
 578       Asm, Contents, CompUnits,
 579       [&](const DWARF5AccelTableData &Entry) {
 580         const DIE *CUDie = Entry.getDie().getUnitDie();
 581         return CUIndex[DD.lookupCU(CUDie)->getUniqueID()];
 582       })
 583       .emit();
 584 }
 585
 586 void llvm::emitDWARF5AccelTable(
 587     AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
 588     ArrayRef<MCSymbol *> CUs,
 589     llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
 590         getCUIndexForEntry) {
 591   Contents.finalize(Asm, "names");
 592   Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
 593                                                      getCUIndexForEntry)
 594       .emit();
 595 }
 596
 597 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
 598   Asm->emitInt32(Die.getDebugSectionOffset());
 599 }
 600
 601 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
 602   Asm->emitInt32(Die.getDebugSectionOffset());
 603   Asm->emitInt16(Die.getTag());
 604   Asm->emitInt8(0);
 605 }
 606
 607 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
 608   Asm->emitInt32(Offset);
 609 }
 610
 611 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
 612   Asm->emitInt32(Offset);
 613   Asm->emitInt16(Tag);
 614   Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
 615                                           : 0);
 616   Asm->emitInt32(QualifiedNameHash);
 617 }
 618
 619 #ifndef _MSC_VER
 620 // The lines below are rejected by older versions (TBD) of MSVC.
 621 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
 622 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
 623 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
 624 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
 625 #else
 626 // FIXME: Erase this path once the minimum MSCV version has been bumped.
 627 const SmallVector<AppleAccelTableData::Atom, 4>
 628     AppleAccelTableOffsetData::Atoms = {
 629         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 630 const SmallVector<AppleAccelTableData::Atom, 4> AppleAccelTableTypeData::Atoms =
 631     {Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 632      Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 633      Atom(dwarf::DW_ATOM_type_flags, dwarf::DW_FORM_data1)};
 634 const SmallVector<AppleAccelTableData::Atom, 4>
 635     AppleAccelTableStaticOffsetData::Atoms = {
 636         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4)};
 637 const SmallVector<AppleAccelTableData::Atom, 4>
 638     AppleAccelTableStaticTypeData::Atoms = {
 639         Atom(dwarf::DW_ATOM_die_offset, dwarf::DW_FORM_data4),
 640         Atom(dwarf::DW_ATOM_die_tag, dwarf::DW_FORM_data2),
 641         Atom(5, dwarf::DW_FORM_data1), Atom(6, dwarf::DW_FORM_data4)};
 642 #endif
 643
 644 #ifndef NDEBUG
 645 void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
 646   OS << "Magic: " << format("0x%x", Magic) << "\n"
 647      << "Version: " << Version << "\n"
 648      << "Hash Function: " << HashFunction << "\n"
 649      << "Bucket Count: " << BucketCount << "\n"
 650      << "Header Data Length: " << HeaderDataLength << "\n";
 651 }
 652
 653 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
 654   OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
 655      << "Form: " << dwarf::FormEncodingString(Form) << "\n";
 656 }
 657
 658 void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
 659   OS << "DIE Offset Base: " << DieOffsetBase << "\n";
 660   for (auto Atom : Atoms)
 661     Atom.print(OS);
 662 }
 663
 664 void AppleAccelTableWriter::print(raw_ostream &OS) const {
 665   Header.print(OS);
 666   HeaderData.print(OS);
 667   Contents.print(OS);
 668   SecBegin->print(OS, nullptr);
 669 }
 670
 671 void AccelTableBase::HashData::print(raw_ostream &OS) const {
 672   OS << "Name: " << Name.getString() << "\n";
 673   OS << "  Hash Value: " << format("0x%x", HashValue) << "\n";
 674   OS << "  Symbol: ";
 675   if (Sym)
 676     OS << *Sym;
 677   else
 678     OS << "<none>";
 679   OS << "\n";
 680   for (auto *Value : Values)
 681     Value->print(OS);
 682 }
 683
 684 void AccelTableBase::print(raw_ostream &OS) const {
 685   // Print Content.
 686   OS << "Entries: \n";
 687   for (const auto &Entry : Entries) {
 688     OS << "Name: " << Entry.first() << "\n";
 689     for (auto *V : Entry.second.Values)
 690       V->print(OS);
 691   }
 692
 693   OS << "Buckets and Hashes: \n";
 694   for (auto &Bucket : Buckets)
 695     for (auto &Hash : Bucket)
 696       Hash->print(OS);
 697
 698   OS << "Data: \n";
 699   for (auto &E : Entries)
 700     E.second.print(OS);
 701 }
 702
 703 void DWARF5AccelTableData::print(raw_ostream &OS) const {
 704   OS << "  Offset: " << getDieOffset() << "\n";
 705   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 706 }
 707
 708 void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
 709   OS << "  Offset: " << getDieOffset() << "\n";
 710   OS << "  Tag: " << dwarf::TagString(getDieTag()) << "\n";
 711 }
 712
 713 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
 714   OS << "  Offset: " << Die.getOffset() << "\n";
 715 }
 716
 717 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
 718   OS << "  Offset: " << Die.getOffset() << "\n";
 719   OS << "  Tag: " << dwarf::TagString(Die.getTag()) << "\n";
 720 }
 721
 722 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
 723   OS << "  Static Offset: " << Offset << "\n";
 724 }
 725
 726 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
 727   OS << "  Static Offset: " << Offset << "\n";
 728   OS << "  QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
 729   OS << "  Tag: " << dwarf::TagString(Tag) << "\n";
 730   OS << "  ObjCClassIsImplementation: "
 731      << (ObjCClassIsImplementation ? "true" : "false");
 732   OS << "\n";
 733 }
 734 #endif