LLVM  16.0.0git
AccelTable.cpp
Go to the documentation of this file.
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/MCStreamer.h"
22 #include "llvm/MC/MCSymbol.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include "llvm/Target/TargetLoweringObjectFile.h"
25 #include <algorithm>
26 #include <cstddef>
27 #include <cstdint>
28 #include <limits>
29 #include <vector>
30 
31 using namespace llvm;
32 
33 void AccelTableBase::computeBucketCount() {
34  // First get the number of unique hashes.
35  std::vector<uint32_t> Uniques;
36  Uniques.reserve(Entries.size());
37  for (const auto &E : Entries)
38  Uniques.push_back(E.second.HashValue);
39  array_pod_sort(Uniques.begin(), Uniques.end());
40  std::vector<uint32_t>::iterator P =
41  std::unique(Uniques.begin(), Uniques.end());
42 
43  UniqueHashCount = std::distance(Uniques.begin(), P);
44 
45  if (UniqueHashCount > 1024)
46  BucketCount = UniqueHashCount / 4;
47  else if (UniqueHashCount > 16)
48  BucketCount = UniqueHashCount / 2;
49  else
50  BucketCount = std::max<uint32_t>(UniqueHashCount, 1);
51 }
52 
53 void AccelTableBase::finalize(AsmPrinter *Asm, StringRef Prefix) {
54  // Create the individual hash data outputs.
55  for (auto &E : Entries) {
56  // Unique the entries.
57  llvm::stable_sort(E.second.Values,
58  [](const AccelTableData *A, const AccelTableData *B) {
59  return *A < *B;
60  });
61  E.second.Values.erase(
62  std::unique(E.second.Values.begin(), E.second.Values.end()),
63  E.second.Values.end());
64  }
65 
66  // Figure out how many buckets we need, then compute the bucket contents and
67  // the final ordering. The hashes and offsets can be emitted by walking these
68  // data structures. We add temporary symbols to the data so they can be
69  // referenced when emitting the offsets.
70  computeBucketCount();
71 
72  // Compute bucket contents and final ordering.
73  Buckets.resize(BucketCount);
74  for (auto &E : Entries) {
75  uint32_t Bucket = E.second.HashValue % BucketCount;
76  Buckets[Bucket].push_back(&E.second);
77  E.second.Sym = Asm->createTempSymbol(Prefix);
78  }
79 
80  // Sort the contents of the buckets by hash value so that hash collisions end
81  // up together. Stable sort makes testing easier and doesn't cost much more.
82  for (auto &Bucket : Buckets)
83  llvm::stable_sort(Bucket, [](HashData *LHS, HashData *RHS) {
84  return LHS->HashValue < RHS->HashValue;
85  });
86 }
87 
88 namespace {
89 /// Base class for writing out Accelerator tables. It holds the common
90 /// functionality for the two Accelerator table types.
91 class AccelTableWriter {
92 protected:
93  AsmPrinter *const Asm; ///< Destination.
94  const AccelTableBase &Contents; ///< Data to emit.
95 
96  /// Controls whether to emit duplicate hash and offset table entries for names
97  /// with identical hashes. Apple tables don't emit duplicate entries, DWARF v5
98  /// tables do.
99  const bool SkipIdenticalHashes;
100 
101  void emitHashes() const;
102 
103  /// Emit offsets to lists of entries with identical names. The offsets are
104  /// relative to the Base argument.
105  void emitOffsets(const MCSymbol *Base) const;
106 
107 public:
108  AccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
109  bool SkipIdenticalHashes)
110  : Asm(Asm), Contents(Contents), SkipIdenticalHashes(SkipIdenticalHashes) {
111  }
112 };
113 
114 class AppleAccelTableWriter : public AccelTableWriter {
115  using Atom = AppleAccelTableData::Atom;
116 
117  /// The fixed header of an Apple Accelerator Table.
118  struct Header {
119  uint32_t Magic = MagicHash;
120  uint16_t Version = 1;
121  uint16_t HashFunction = dwarf::DW_hash_function_djb;
122  uint32_t BucketCount;
123  uint32_t HashCount;
124  uint32_t HeaderDataLength;
125 
126  /// 'HASH' magic value to detect endianness.
127  static const uint32_t MagicHash = 0x48415348;
128 
129  Header(uint32_t BucketCount, uint32_t UniqueHashCount, uint32_t DataLength)
130  : BucketCount(BucketCount), HashCount(UniqueHashCount),
131  HeaderDataLength(DataLength) {}
132 
133  void emit(AsmPrinter *Asm) const;
134 #ifndef NDEBUG
135  void print(raw_ostream &OS) const;
136  void dump() const { print(dbgs()); }
137 #endif
138  };
139 
140  /// The HeaderData describes the structure of an Apple accelerator table
141  /// through a list of Atoms.
142  struct HeaderData {
143  /// In the case of data that is referenced via DW_FORM_ref_* the offset
144  /// base is used to describe the offset for all forms in the list of atoms.
145  uint32_t DieOffsetBase;
146 
147  const SmallVector<Atom, 4> Atoms;
148 
149  HeaderData(ArrayRef<Atom> AtomList, uint32_t Offset = 0)
150  : DieOffsetBase(Offset), Atoms(AtomList.begin(), AtomList.end()) {}
151 
152  void emit(AsmPrinter *Asm) const;
153 #ifndef NDEBUG
154  void print(raw_ostream &OS) const;
155  void dump() const { print(dbgs()); }
156 #endif
157  };
158 
159  Header Header;
160  HeaderData HeaderData;
161  const MCSymbol *SecBegin;
162 
163  void emitBuckets() const;
164  void emitData() const;
165 
166 public:
167  AppleAccelTableWriter(AsmPrinter *Asm, const AccelTableBase &Contents,
168  ArrayRef<Atom> Atoms, const MCSymbol *SecBegin)
169  : AccelTableWriter(Asm, Contents, true),
170  Header(Contents.getBucketCount(), Contents.getUniqueHashCount(),
171  8 + (Atoms.size() * 4)),
172  HeaderData(Atoms), SecBegin(SecBegin) {}
173 
174  void emit() const;
175 
176 #ifndef NDEBUG
177  void print(raw_ostream &OS) const;
178  void dump() const { print(dbgs()); }
179 #endif
180 };
181 
182 /// Class responsible for emitting a DWARF v5 Accelerator Table. The only
183 /// public function is emit(), which performs the actual emission.
184 ///
185 /// The class is templated in its data type. This allows us to emit both dyamic
186 /// and static data entries. A callback abstract the logic to provide a CU
187 /// index for a given entry, which is different per data type, but identical
188 /// for every entry in the same table.
189 template <typename DataT>
190 class Dwarf5AccelTableWriter : public AccelTableWriter {
191  struct Header {
192  uint16_t Version = 5;
193  uint16_t Padding = 0;
194  uint32_t CompUnitCount;
195  uint32_t LocalTypeUnitCount = 0;
196  uint32_t ForeignTypeUnitCount = 0;
197  uint32_t BucketCount;
198  uint32_t NameCount;
199  uint32_t AbbrevTableSize = 0;
200  uint32_t AugmentationStringSize = sizeof(AugmentationString);
201  char AugmentationString[8] = {'L', 'L', 'V', 'M', '0', '7', '0', '0'};
202 
203  Header(uint32_t CompUnitCount, uint32_t BucketCount, uint32_t NameCount)
204  : CompUnitCount(CompUnitCount), BucketCount(BucketCount),
205  NameCount(NameCount) {}
206 
207  void emit(Dwarf5AccelTableWriter &Ctx);
208  };
209  struct AttributeEncoding {
210  dwarf::Index Index;
211  dwarf::Form Form;
212  };
213 
214  Header Header;
215  DenseMap<uint32_t, SmallVector<AttributeEncoding, 2>> Abbreviations;
216  ArrayRef<MCSymbol *> CompUnits;
217  llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry;
218  MCSymbol *ContributionEnd = nullptr;
219  MCSymbol *AbbrevStart = Asm->createTempSymbol("names_abbrev_start");
220  MCSymbol *AbbrevEnd = Asm->createTempSymbol("names_abbrev_end");
221  MCSymbol *EntryPool = Asm->createTempSymbol("names_entries");
222 
223  DenseSet<uint32_t> getUniqueTags() const;
224 
225  // Right now, we emit uniform attributes for all tags.
226  SmallVector<AttributeEncoding, 2> getUniformAttributes() const;
227 
228  void emitCUList() const;
229  void emitBuckets() const;
230  void emitStringOffsets() const;
231  void emitAbbrevs() const;
232  void emitEntry(const DataT &Entry) const;
233  void emitData() const;
234 
235 public:
236  Dwarf5AccelTableWriter(
237  AsmPrinter *Asm, const AccelTableBase &Contents,
238  ArrayRef<MCSymbol *> CompUnits,
239  llvm::function_ref<unsigned(const DataT &)> GetCUIndexForEntry);
240 
241  void emit();
242 };
243 } // namespace
244 
245 void AccelTableWriter::emitHashes() const {
246  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
247  unsigned BucketIdx = 0;
248  for (const auto &Bucket : Contents.getBuckets()) {
249  for (const auto &Hash : Bucket) {
250  uint32_t HashValue = Hash->HashValue;
251  if (SkipIdenticalHashes && PrevHash == HashValue)
252  continue;
253  Asm->OutStreamer->AddComment("Hash in Bucket " + Twine(BucketIdx));
254  Asm->emitInt32(HashValue);
255  PrevHash = HashValue;
256  }
257  BucketIdx++;
258  }
259 }
260 
261 void AccelTableWriter::emitOffsets(const MCSymbol *Base) const {
262  const auto &Buckets = Contents.getBuckets();
263  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
264  for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
265  for (auto *Hash : Buckets[i]) {
266  uint32_t HashValue = Hash->HashValue;
267  if (SkipIdenticalHashes && PrevHash == HashValue)
268  continue;
269  PrevHash = HashValue;
270  Asm->OutStreamer->AddComment("Offset in Bucket " + Twine(i));
271  Asm->emitLabelDifference(Hash->Sym, Base, Asm->getDwarfOffsetByteSize());
272  }
273  }
274 }
275 
276 void AppleAccelTableWriter::Header::emit(AsmPrinter *Asm) const {
277  Asm->OutStreamer->AddComment("Header Magic");
278  Asm->emitInt32(Magic);
279  Asm->OutStreamer->AddComment("Header Version");
280  Asm->emitInt16(Version);
281  Asm->OutStreamer->AddComment("Header Hash Function");
282  Asm->emitInt16(HashFunction);
283  Asm->OutStreamer->AddComment("Header Bucket Count");
284  Asm->emitInt32(BucketCount);
285  Asm->OutStreamer->AddComment("Header Hash Count");
286  Asm->emitInt32(HashCount);
287  Asm->OutStreamer->AddComment("Header Data Length");
288  Asm->emitInt32(HeaderDataLength);
289 }
290 
291 void AppleAccelTableWriter::HeaderData::emit(AsmPrinter *Asm) const {
292  Asm->OutStreamer->AddComment("HeaderData Die Offset Base");
293  Asm->emitInt32(DieOffsetBase);
294  Asm->OutStreamer->AddComment("HeaderData Atom Count");
295  Asm->emitInt32(Atoms.size());
296 
297  for (const Atom &A : Atoms) {
298  Asm->OutStreamer->AddComment(dwarf::AtomTypeString(A.Type));
299  Asm->emitInt16(A.Type);
300  Asm->OutStreamer->AddComment(dwarf::FormEncodingString(A.Form));
301  Asm->emitInt16(A.Form);
302  }
303 }
304 
305 void AppleAccelTableWriter::emitBuckets() const {
306  const auto &Buckets = Contents.getBuckets();
307  unsigned index = 0;
308  for (size_t i = 0, e = Buckets.size(); i < e; ++i) {
309  Asm->OutStreamer->AddComment("Bucket " + Twine(i));
310  if (!Buckets[i].empty())
311  Asm->emitInt32(index);
312  else
313  Asm->emitInt32(std::numeric_limits<uint32_t>::max());
314  // Buckets point in the list of hashes, not to the data. Do not increment
315  // the index multiple times in case of hash collisions.
316  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
317  for (auto *HD : Buckets[i]) {
318  uint32_t HashValue = HD->HashValue;
319  if (PrevHash != HashValue)
320  ++index;
321  PrevHash = HashValue;
322  }
323  }
324 }
325 
326 void AppleAccelTableWriter::emitData() const {
327  const auto &Buckets = Contents.getBuckets();
328  for (const AccelTableBase::HashList &Bucket : Buckets) {
329  uint64_t PrevHash = std::numeric_limits<uint64_t>::max();
330  for (const auto &Hash : Bucket) {
331  // Terminate the previous entry if there is no hash collision with the
332  // current one.
333  if (PrevHash != std::numeric_limits<uint64_t>::max() &&
334  PrevHash != Hash->HashValue)
335  Asm->emitInt32(0);
336  // Remember to emit the label for our offset.
337  Asm->OutStreamer->emitLabel(Hash->Sym);
338  Asm->OutStreamer->AddComment(Hash->Name.getString());
339  Asm->emitDwarfStringOffset(Hash->Name);
340  Asm->OutStreamer->AddComment("Num DIEs");
341  Asm->emitInt32(Hash->Values.size());
342  for (const auto *V : Hash->Values)
343  static_cast<const AppleAccelTableData *>(V)->emit(Asm);
344  PrevHash = Hash->HashValue;
345  }
346  // Emit the final end marker for the bucket.
347  if (!Bucket.empty())
348  Asm->emitInt32(0);
349  }
350 }
351 
352 void AppleAccelTableWriter::emit() const {
353  Header.emit(Asm);
354  HeaderData.emit(Asm);
355  emitBuckets();
356  emitHashes();
357  emitOffsets(SecBegin);
358  emitData();
359 }
360 
361 template <typename DataT>
362 void Dwarf5AccelTableWriter<DataT>::Header::emit(Dwarf5AccelTableWriter &Ctx) {
363  assert(CompUnitCount > 0 && "Index must have at least one CU.");
364 
365  AsmPrinter *Asm = Ctx.Asm;
366  Ctx.ContributionEnd =
367  Asm->emitDwarfUnitLength("names", "Header: unit length");
368  Asm->OutStreamer->AddComment("Header: version");
369  Asm->emitInt16(Version);
370  Asm->OutStreamer->AddComment("Header: padding");
371  Asm->emitInt16(Padding);
372  Asm->OutStreamer->AddComment("Header: compilation unit count");
373  Asm->emitInt32(CompUnitCount);
374  Asm->OutStreamer->AddComment("Header: local type unit count");
375  Asm->emitInt32(LocalTypeUnitCount);
376  Asm->OutStreamer->AddComment("Header: foreign type unit count");
377  Asm->emitInt32(ForeignTypeUnitCount);
378  Asm->OutStreamer->AddComment("Header: bucket count");
379  Asm->emitInt32(BucketCount);
380  Asm->OutStreamer->AddComment("Header: name count");
381  Asm->emitInt32(NameCount);
382  Asm->OutStreamer->AddComment("Header: abbreviation table size");
383  Asm->emitLabelDifference(Ctx.AbbrevEnd, Ctx.AbbrevStart, sizeof(uint32_t));
384  Asm->OutStreamer->AddComment("Header: augmentation string size");
385  assert(AugmentationStringSize % 4 == 0);
386  Asm->emitInt32(AugmentationStringSize);
387  Asm->OutStreamer->AddComment("Header: augmentation string");
388  Asm->OutStreamer->emitBytes({AugmentationString, AugmentationStringSize});
389 }
390 
391 template <typename DataT>
392 DenseSet<uint32_t> Dwarf5AccelTableWriter<DataT>::getUniqueTags() const {
393  DenseSet<uint32_t> UniqueTags;
394  for (auto &Bucket : Contents.getBuckets()) {
395  for (auto *Hash : Bucket) {
396  for (auto *Value : Hash->Values) {
397  unsigned Tag = static_cast<const DataT *>(Value)->getDieTag();
398  UniqueTags.insert(Tag);
399  }
400  }
401  }
402  return UniqueTags;
403 }
404 
405 template <typename DataT>
406 SmallVector<typename Dwarf5AccelTableWriter<DataT>::AttributeEncoding, 2>
407 Dwarf5AccelTableWriter<DataT>::getUniformAttributes() const {
408  SmallVector<AttributeEncoding, 2> UA;
409  if (CompUnits.size() > 1) {
410  size_t LargestCUIndex = CompUnits.size() - 1;
411  dwarf::Form Form = DIEInteger::BestForm(/*IsSigned*/ false, LargestCUIndex);
412  UA.push_back({dwarf::DW_IDX_compile_unit, Form});
413  }
414  UA.push_back({dwarf::DW_IDX_die_offset, dwarf::DW_FORM_ref4});
415  return UA;
416 }
417 
418 template <typename DataT>
419 void Dwarf5AccelTableWriter<DataT>::emitCUList() const {
420  for (const auto &CU : enumerate(CompUnits)) {
421  Asm->OutStreamer->AddComment("Compilation unit " + Twine(CU.index()));
422  Asm->emitDwarfSymbolReference(CU.value());
423  }
424 }
425 
426 template <typename DataT>
427 void Dwarf5AccelTableWriter<DataT>::emitBuckets() const {
428  uint32_t Index = 1;
429  for (const auto &Bucket : enumerate(Contents.getBuckets())) {
430  Asm->OutStreamer->AddComment("Bucket " + Twine(Bucket.index()));
431  Asm->emitInt32(Bucket.value().empty() ? 0 : Index);
432  Index += Bucket.value().size();
433  }
434 }
435 
436 template <typename DataT>
437 void Dwarf5AccelTableWriter<DataT>::emitStringOffsets() const {
438  for (const auto &Bucket : enumerate(Contents.getBuckets())) {
439  for (auto *Hash : Bucket.value()) {
440  DwarfStringPoolEntryRef String = Hash->Name;
441  Asm->OutStreamer->AddComment("String in Bucket " + Twine(Bucket.index()) +
442  ": " + String.getString());
443  Asm->emitDwarfStringOffset(String);
444  }
445  }
446 }
447 
448 template <typename DataT>
449 void Dwarf5AccelTableWriter<DataT>::emitAbbrevs() const {
450  Asm->OutStreamer->emitLabel(AbbrevStart);
451  for (const auto &Abbrev : Abbreviations) {
452  Asm->OutStreamer->AddComment("Abbrev code");
453  assert(Abbrev.first != 0);
454  Asm->emitULEB128(Abbrev.first);
455  Asm->OutStreamer->AddComment(dwarf::TagString(Abbrev.first));
456  Asm->emitULEB128(Abbrev.first);
457  for (const auto &AttrEnc : Abbrev.second) {
458  Asm->emitULEB128(AttrEnc.Index, dwarf::IndexString(AttrEnc.Index).data());
459  Asm->emitULEB128(AttrEnc.Form,
460  dwarf::FormEncodingString(AttrEnc.Form).data());
461  }
462  Asm->emitULEB128(0, "End of abbrev");
463  Asm->emitULEB128(0, "End of abbrev");
464  }
465  Asm->emitULEB128(0, "End of abbrev list");
466  Asm->OutStreamer->emitLabel(AbbrevEnd);
467 }
468 
469 template <typename DataT>
470 void Dwarf5AccelTableWriter<DataT>::emitEntry(const DataT &Entry) const {
471  auto AbbrevIt = Abbreviations.find(Entry.getDieTag());
472  assert(AbbrevIt != Abbreviations.end() &&
473  "Why wasn't this abbrev generated?");
474 
475  Asm->emitULEB128(AbbrevIt->first, "Abbreviation code");
476  for (const auto &AttrEnc : AbbrevIt->second) {
477  Asm->OutStreamer->AddComment(dwarf::IndexString(AttrEnc.Index));
478  switch (AttrEnc.Index) {
479  case dwarf::DW_IDX_compile_unit: {
480  DIEInteger ID(getCUIndexForEntry(Entry));
481  ID.emitValue(Asm, AttrEnc.Form);
482  break;
483  }
484  case dwarf::DW_IDX_die_offset:
485  assert(AttrEnc.Form == dwarf::DW_FORM_ref4);
486  Asm->emitInt32(Entry.getDieOffset());
487  break;
488  default:
489  llvm_unreachable("Unexpected index attribute!");
490  }
491  }
492 }
493 
494 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emitData() const {
495  Asm->OutStreamer->emitLabel(EntryPool);
496  for (auto &Bucket : Contents.getBuckets()) {
497  for (auto *Hash : Bucket) {
498  // Remember to emit the label for our offset.
499  Asm->OutStreamer->emitLabel(Hash->Sym);
500  for (const auto *Value : Hash->Values)
501  emitEntry(*static_cast<const DataT *>(Value));
502  Asm->OutStreamer->AddComment("End of list: " + Hash->Name.getString());
503  Asm->emitInt8(0);
504  }
505  }
506 }
507 
508 template <typename DataT>
509 Dwarf5AccelTableWriter<DataT>::Dwarf5AccelTableWriter(
510  AsmPrinter *Asm, const AccelTableBase &Contents,
511  ArrayRef<MCSymbol *> CompUnits,
512  llvm::function_ref<unsigned(const DataT &)> getCUIndexForEntry)
513  : AccelTableWriter(Asm, Contents, false),
514  Header(CompUnits.size(), Contents.getBucketCount(),
515  Contents.getUniqueNameCount()),
516  CompUnits(CompUnits), getCUIndexForEntry(std::move(getCUIndexForEntry)) {
517  DenseSet<uint32_t> UniqueTags = getUniqueTags();
518  SmallVector<AttributeEncoding, 2> UniformAttributes = getUniformAttributes();
519 
520  Abbreviations.reserve(UniqueTags.size());
521  for (uint32_t Tag : UniqueTags)
522  Abbreviations.try_emplace(Tag, UniformAttributes);
523 }
524 
525 template <typename DataT> void Dwarf5AccelTableWriter<DataT>::emit() {
526  Header.emit(*this);
527  emitCUList();
528  emitBuckets();
529  emitHashes();
530  emitStringOffsets();
531  emitOffsets(EntryPool);
532  emitAbbrevs();
533  emitData();
534  Asm->OutStreamer->emitValueToAlignment(4, 0);
535  Asm->OutStreamer->emitLabel(ContributionEnd);
536 }
537 
538 void llvm::emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents,
539  StringRef Prefix, const MCSymbol *SecBegin,
540  ArrayRef<AppleAccelTableData::Atom> Atoms) {
541  Contents.finalize(Asm, Prefix);
542  AppleAccelTableWriter(Asm, Contents, Atoms, SecBegin).emit();
543 }
544 
545 void llvm::emitDWARF5AccelTable(
546  AsmPrinter *Asm, AccelTable<DWARF5AccelTableData> &Contents,
547  const DwarfDebug &DD, ArrayRef<std::unique_ptr<DwarfCompileUnit>> CUs) {
548  std::vector<MCSymbol *> CompUnits;
549  SmallVector<unsigned, 1> CUIndex(CUs.size());
550  int Count = 0;
551  for (const auto &CU : enumerate(CUs)) {
552  if (CU.value()->getCUNode()->getNameTableKind() !=
553  DICompileUnit::DebugNameTableKind::Default)
554  continue;
555  CUIndex[CU.index()] = Count++;
556  assert(CU.index() == CU.value()->getUniqueID());
557  const DwarfCompileUnit *MainCU =
558  DD.useSplitDwarf() ? CU.value()->getSkeleton() : CU.value().get();
559  CompUnits.push_back(MainCU->getLabelBegin());
560  }
561 
562  if (CompUnits.empty())
563  return;
564 
565  Asm->OutStreamer->switchSection(
566  Asm->getObjFileLowering().getDwarfDebugNamesSection());
567 
568  Contents.finalize(Asm, "names");
569  Dwarf5AccelTableWriter<DWARF5AccelTableData>(
570  Asm, Contents, CompUnits,
571  [&](const DWARF5AccelTableData &Entry) {
572  const DIE *CUDie = Entry.getDie().getUnitDie();
573  return CUIndex[DD.lookupCU(CUDie)->getUniqueID()];
574  })
575  .emit();
576 }
577 
578 void llvm::emitDWARF5AccelTable(
579  AsmPrinter *Asm, AccelTable<DWARF5AccelTableStaticData> &Contents,
580  ArrayRef<MCSymbol *> CUs,
581  llvm::function_ref<unsigned(const DWARF5AccelTableStaticData &)>
582  getCUIndexForEntry) {
583  Contents.finalize(Asm, "names");
584  Dwarf5AccelTableWriter<DWARF5AccelTableStaticData>(Asm, Contents, CUs,
585  getCUIndexForEntry)
586  .emit();
587 }
588 
589 void AppleAccelTableOffsetData::emit(AsmPrinter *Asm) const {
590  assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
591  "The section offset exceeds the limit.");
592  Asm->emitInt32(Die.getDebugSectionOffset());
593 }
594 
595 void AppleAccelTableTypeData::emit(AsmPrinter *Asm) const {
596  assert(Die.getDebugSectionOffset() <= UINT32_MAX &&
597  "The section offset exceeds the limit.");
598  Asm->emitInt32(Die.getDebugSectionOffset());
599  Asm->emitInt16(Die.getTag());
600  Asm->emitInt8(0);
601 }
602 
603 void AppleAccelTableStaticOffsetData::emit(AsmPrinter *Asm) const {
604  Asm->emitInt32(Offset);
605 }
606 
607 void AppleAccelTableStaticTypeData::emit(AsmPrinter *Asm) const {
608  Asm->emitInt32(Offset);
609  Asm->emitInt16(Tag);
610  Asm->emitInt8(ObjCClassIsImplementation ? dwarf::DW_FLAG_type_implementation
611  : 0);
612  Asm->emitInt32(QualifiedNameHash);
613 }
614 
615 constexpr AppleAccelTableData::Atom AppleAccelTableTypeData::Atoms[];
616 constexpr AppleAccelTableData::Atom AppleAccelTableOffsetData::Atoms[];
617 constexpr AppleAccelTableData::Atom AppleAccelTableStaticOffsetData::Atoms[];
618 constexpr AppleAccelTableData::Atom AppleAccelTableStaticTypeData::Atoms[];
619 
620 #ifndef NDEBUG
621 void AppleAccelTableWriter::Header::print(raw_ostream &OS) const {
622  OS << "Magic: " << format("0x%x", Magic) << "\n"
623  << "Version: " << Version << "\n"
624  << "Hash Function: " << HashFunction << "\n"
625  << "Bucket Count: " << BucketCount << "\n"
626  << "Header Data Length: " << HeaderDataLength << "\n";
627 }
628 
629 void AppleAccelTableData::Atom::print(raw_ostream &OS) const {
630  OS << "Type: " << dwarf::AtomTypeString(Type) << "\n"
631  << "Form: " << dwarf::FormEncodingString(Form) << "\n";
632 }
633 
634 void AppleAccelTableWriter::HeaderData::print(raw_ostream &OS) const {
635  OS << "DIE Offset Base: " << DieOffsetBase << "\n";
636  for (auto Atom : Atoms)
637  Atom.print(OS);
638 }
639 
640 void AppleAccelTableWriter::print(raw_ostream &OS) const {
641  Header.print(OS);
642  HeaderData.print(OS);
643  Contents.print(OS);
644  SecBegin->print(OS, nullptr);
645 }
646 
647 void AccelTableBase::HashData::print(raw_ostream &OS) const {
648  OS << "Name: " << Name.getString() << "\n";
649  OS << " Hash Value: " << format("0x%x", HashValue) << "\n";
650  OS << " Symbol: ";
651  if (Sym)
652  OS << *Sym;
653  else
654  OS << "<none>";
655  OS << "\n";
656  for (auto *Value : Values)
657  Value->print(OS);
658 }
659 
660 void AccelTableBase::print(raw_ostream &OS) const {
661  // Print Content.
662  OS << "Entries: \n";
663  for (const auto &Entry : Entries) {
664  OS << "Name: " << Entry.first() << "\n";
665  for (auto *V : Entry.second.Values)
666  V->print(OS);
667  }
668 
669  OS << "Buckets and Hashes: \n";
670  for (const auto &Bucket : Buckets)
671  for (const auto &Hash : Bucket)
672  Hash->print(OS);
673 
674  OS << "Data: \n";
675  for (const auto &E : Entries)
676  E.second.print(OS);
677 }
678 
679 void DWARF5AccelTableData::print(raw_ostream &OS) const {
680  OS << " Offset: " << getDieOffset() << "\n";
681  OS << " Tag: " << dwarf::TagString(getDieTag()) << "\n";
682 }
683 
684 void DWARF5AccelTableStaticData::print(raw_ostream &OS) const {
685  OS << " Offset: " << getDieOffset() << "\n";
686  OS << " Tag: " << dwarf::TagString(getDieTag()) << "\n";
687 }
688 
689 void AppleAccelTableOffsetData::print(raw_ostream &OS) const {
690  OS << " Offset: " << Die.getOffset() << "\n";
691 }
692 
693 void AppleAccelTableTypeData::print(raw_ostream &OS) const {
694  OS << " Offset: " << Die.getOffset() << "\n";
695  OS << " Tag: " << dwarf::TagString(Die.getTag()) << "\n";
696 }
697 
698 void AppleAccelTableStaticOffsetData::print(raw_ostream &OS) const {
699  OS << " Static Offset: " << Offset << "\n";
700 }
701 
702 void AppleAccelTableStaticTypeData::print(raw_ostream &OS) const {
703  OS << " Static Offset: " << Offset << "\n";
704  OS << " QualifiedNameHash: " << format("%x\n", QualifiedNameHash) << "\n";
705  OS << " Tag: " << dwarf::TagString(Tag) << "\n";
706  OS << " ObjCClassIsImplementation: "
707  << (ObjCClassIsImplementation ? "true" : "false");
708  OS << "\n";
709 }
710 #endif
i
i
Definition: README.txt:29
AsmPrinter.h
llvm::array_pod_sort
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1521
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MCSymbol
MCSymbol - Instances of this class represent a symbol name in the MC file, and MCSymbols are created ...
Definition: MCSymbol.h:41
print
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
Definition: ArchiveWriter.cpp:189
llvm::cl::Prefix
@ Prefix
Definition: CommandLine.h:160
llvm::AccelTableBase::UniqueHashCount
uint32_t UniqueHashCount
Definition: AccelTable.h:165
llvm::AppleAccelTableStaticOffsetData::Offset
uint32_t Offset
Definition: AccelTable.h:372
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::DwarfCompileUnit
Definition: DwarfCompileUnit.h:46
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1183
llvm::enumerate
detail::enumerator< R > enumerate(R &&TheRange)
Given an input range, returns a new range whose values are are pair (A,B) such that A is the 0-based ...
Definition: STLExtras.h:2079
llvm::dwarf::Form
Form
Definition: Dwarf.h:132
llvm::sys::fs::getUniqueID
std::error_code getUniqueID(const Twine Path, UniqueID &Result)
Definition: Path.cpp:787
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1875
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::AppleAccelTableStaticTypeData::ObjCClassIsImplementation
bool ObjCClassIsImplementation
Definition: AccelTable.h:401
llvm::sys::path::end
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
llvm::sys::path::begin
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:226
llvm::AccelTableBase::Entries
StringEntries Entries
Definition: AccelTable.h:161
llvm::DIE
A structured debug information entry.
Definition: DIE.h:739
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::AppleAccelTableTypeData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:693
STLExtras.h
llvm::AccelTable
This class holds an abstract representation of an Accelerator Table, consisting of a sequence of buck...
Definition: AccelTable.h:195
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::DIE::getTag
dwarf::Tag getTag() const
Definition: DIE.h:775
llvm::dwarf::Tag
Tag
Definition: Dwarf.h:105
llvm::detail::DenseSetImpl::insert
std::pair< iterator, bool > insert(const ValueT &V)
Definition: DenseSet.h:206
llvm::AccelTableData
Interface which the different types of accelerator table data have to conform.
Definition: AccelTable.h:113
llvm::dwarf::IndexString
StringRef IndexString(unsigned Idx)
Definition: Dwarf.cpp:683
llvm::DwarfStringPoolEntryRef
DwarfStringPoolEntryRef: Dwarf string pool entry reference.
Definition: DwarfStringPoolEntry.h:44
llvm::AccelTableBase::computeBucketCount
void computeBucketCount()
Definition: AccelTable.cpp:33
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::DWARF5AccelTableData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:679
llvm::dwarf::AtomTypeString
StringRef AtomTypeString(unsigned Atom)
Definition: Dwarf.cpp:587
LHS
Value * LHS
Definition: X86PartialReduction.cpp:75
llvm::AppleAccelTableStaticTypeData::emit
void emit(AsmPrinter *Asm) const override
Definition: AccelTable.cpp:607
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AppleAccelTableData::Atom
An Atom defines the form of the data in an Apple accelerator table.
Definition: AccelTable.h:224
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
Twine.h
llvm::dwarf::DW_FLAG_type_implementation
@ DW_FLAG_type_implementation
Definition: Dwarf.h:522
llvm::AccelTableBase::HashData
Represents a group of entries with identical name (and hence, hash value).
Definition: AccelTable.h:139
MCSymbol.h
false
Definition: StackSlotColoring.cpp:141
llvm::dwarf::Index
Index
Definition: Dwarf.h:472
AccelTable.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::AppleAccelTableStaticOffsetData::emit
void emit(AsmPrinter *Asm) const override
Definition: AccelTable.cpp:603
llvm::detail::DenseSetImpl::size
size_type size() const
Definition: DenseSet.h:81
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
llvm::StringRef::data
const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:123
llvm::IndexedInstrProf::Version
const uint64_t Version
Definition: InstrProf.h:1027
llvm::DIEInteger
An integer value DIE.
Definition: DIE.h:163
StringMap.h
llvm::AccelTableBase
A base class holding non-template-dependant functionality of the AccelTable class.
Definition: AccelTable.h:134
llvm::DIE::getDebugSectionOffset
uint64_t getDebugSectionOffset() const
Get the absolute offset within the .debug_info or .debug_types section for this DIE.
Definition: DIE.cpp:191
llvm::emitAppleAccelTableImpl
void emitAppleAccelTableImpl(AsmPrinter *Asm, AccelTableBase &Contents, StringRef Prefix, const MCSymbol *SecBegin, ArrayRef< AppleAccelTableData::Atom > Atoms)
Definition: AccelTable.cpp:538
llvm::MCSymbol::print
void print(raw_ostream &OS, const MCAsmInfo *MAI) const
print - Print the value to the stream OS.
Definition: MCSymbol.cpp:58
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::dwarf::FormEncodingString
StringRef FormEncodingString(unsigned Encoding)
Definition: Dwarf.cpp:105
DIE.h
llvm::AppleAccelTableTypeData::emit
void emit(AsmPrinter *Asm) const override
Definition: AccelTable.cpp:595
llvm::DwarfDebug::lookupCU
DwarfCompileUnit * lookupCU(const DIE *Die)
Find the matching DwarfCompileUnit for the given CU DIE.
Definition: DwarfDebug.h:808
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::AccelTableBase::print
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:660
llvm::DenseSet< uint32_t >
llvm::AMDGPU::Hwreg::Offset
Offset
Definition: SIDefines.h:416
Index
uint32_t Index
Definition: ELFObjHandler.cpp:82
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::DwarfDebug
Collects and handles dwarf debug information.
Definition: DwarfDebug.h:294
uint64_t
llvm::DWARF5AccelTableStaticData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:684
llvm::DWARF5AccelTableStaticData
Definition: AccelTable.h:269
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::AppleAccelTableStaticTypeData::QualifiedNameHash
uint32_t QualifiedNameHash
Definition: AccelTable.h:399
llvm::DenseMap
Definition: DenseMap.h:714
llvm::DwarfDebug::useSplitDwarf
bool useSplitDwarf() const
Returns whether or not to change the current debug info for the split dwarf proposal support.
Definition: DwarfDebug.h:735
llvm::AppleAccelTableStaticOffsetData::Atoms
static constexpr Atom Atoms[]
Definition: AccelTable.h:363
llvm::Value::print
void print(raw_ostream &O, bool IsForDebug=false) const
Implement operator<< on Value.
Definition: AsmWriter.cpp:4588
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::move
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1676
llvm::StringMapImpl::size
unsigned size() const
Definition: StringMap.h:95
llvm::AppleAccelTableOffsetData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:689
llvm::size
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
Definition: STLExtras.h:1599
llvm::AccelTableBase::Buckets
BucketList Buckets
Definition: AccelTable.h:168
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Dwarf.h
llvm::msf::Magic
static const char Magic[]
Definition: MSFCommon.h:23
llvm::AppleAccelTableStaticTypeData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:702
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
TargetLoweringObjectFile.h
uint32_t
DwarfCompileUnit.h
llvm::format
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:124
llvm::DWARF5AccelTableData
The Data class implementation for DWARF v5 accelerator table.
Definition: AccelTable.h:249
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::stable_sort
void stable_sort(R &&Range)
Definition: STLExtras.h:1762
llvm::AppleAccelTableData
A base class for different implementations of Data classes for Apple Accelerator Tables.
Definition: AccelTable.h:219
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:269
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
std
Definition: BitVector.h:851
uint16_t
llvm::AppleAccelTableTypeData::Atoms
static constexpr Atom Atoms[]
Definition: AccelTable.h:345
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::AsmPrinter
This class is intended to be used as a driving class for all asm writers.
Definition: AsmPrinter.h:82
llvm::unique
auto unique(Range &&R, Predicate P)
Definition: STLExtras.h:1780
llvm::DICompileUnit::DebugNameTableKind::Default
@ Default
llvm::AppleAccelTableOffsetData::Atoms
static constexpr Atom Atoms[]
Definition: AccelTable.h:326
llvm::pdb::PDB_ColorItem::Padding
@ Padding
llvm::DIEInteger::BestForm
static dwarf::Form BestForm(bool IsSigned, uint64_t Int)
Choose the best form for integer.
Definition: DIE.h:170
llvm::AppleAccelTableStaticTypeData::Atoms
static constexpr Atom Atoms[]
Definition: AccelTable.h:388
llvm::dwarf::DW_hash_function_djb
@ DW_hash_function_djb
Definition: Dwarf.h:527
MCStreamer.h
llvm::AccelTableBase::HashData::print
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:647
llvm::AccelTableBase::BucketCount
uint32_t BucketCount
Definition: AccelTable.h:164
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::AccelTableBase::HashList
std::vector< HashData * > HashList
Definition: AccelTable.h:153
llvm::HexStyle::Asm
@ Asm
0ffh
Definition: MCInstPrinter.h:34
llvm::AppleAccelTableStaticOffsetData::print
void print(raw_ostream &OS) const override
Definition: AccelTable.cpp:698
llvm::dwarf::TagString
StringRef TagString(unsigned Tag)
Definition: Dwarf.cpp:21
llvm::pdb::String
@ String
Definition: PDBTypes.h:408
llvm::AppleAccelTableOffsetData::emit
void emit(AsmPrinter *Asm) const override
Definition: AccelTable.cpp:589
raw_ostream.h
llvm::AppleAccelTableData::Atom::print
void print(raw_ostream &OS) const
Definition: AccelTable.cpp:629
CU
Definition: AArch64AsmBackend.cpp:504
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::DwarfCompileUnit::getLabelBegin
MCSymbol * getLabelBegin() const
Definition: DwarfCompileUnit.h:295
llvm::AccelTableBase::finalize
void finalize(AsmPrinter *Asm, StringRef Prefix)
Definition: AccelTable.cpp:53
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58
llvm::AppleAccelTableOffsetData::Die
const DIE & Die
Definition: AccelTable.h:335
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38
llvm::emitDWARF5AccelTable
void emitDWARF5AccelTable(AsmPrinter *Asm, AccelTable< DWARF5AccelTableData > &Contents, const DwarfDebug &DD, ArrayRef< std::unique_ptr< DwarfCompileUnit >> CUs)
Definition: AccelTable.cpp:545
Generated on Sun Aug 14 2022 17:13:43 for LLVM by   doxygen 1.8.17