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